[go: up one dir, main page]
Scribd
Upload
74 views2 pages

MA 2322 Worksheet 4 Hints/Solutions: ( (A, F (A) ) - A A) Which Is A Subset of A × A and So G

This document provides hints and solutions to problems about relations and equivalence relations. It addresses properties of relations like reflexive, symmetric, anti-symmetric, and transitive. It also discusses counting the number of equivalence relations on a set based on possible partitions of the set. Examples are given of equivalence relations that produce finite, countably infinite, and uncountable partitions of sets.

Uploaded by

Upinder Kaur
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
74 views2 pages

MA 2322 Worksheet 4 Hints/Solutions: ( (A, F (A) ) - A A) Which Is A Subset of A × A and So G

This document provides hints and solutions to problems about relations and equivalence relations. It addresses properties of relations like reflexive, symmetric, anti-symmetric, and transitive. It also discusses counting the number of equivalence relations on a set based on possible partitions of the set. Examples are given of equivalence relations that produce finite, countably infinite, and uncountable partitions of sets.

Uploaded by

Upinder Kaur
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

MA 2322

Worksheet 4 Hints/Solutions

(1) Suppose |A| = n. How many relations on A are there which are
2
(a) reflexive? 2n n
(b) symmetric? 2n 2C(n,2)
(c) anti-symmetric? 2n 3C(n,2)
(d) reflexive and symmetric? 2C(n,2)
(e) reflexive and anti-symmetric? 3C(n,2)
(f) symmetric and anti-symmetric? 2n
(g) reflexive, symmetric and anti-symmetric? 1
(2) Define a relation on the set P (Z) by A B A B 6= . Is the relation
(a) reflexive? No. = so is false.
(b) symmetric? Yes. If A B 6= then B A 6= .
(c) anti-symmetric? No. {1} {1, 2} 6= and {1, 2} {1} 6= , but {1, 2} 6= {1}.
(d) transitive? No. {1} {1, 2} 6= and {1, 2} {2} 6= but {1} {2} = .
(3) Recall that if f : A A is a function then the graph of f is the set Gf =
{(a, f (a))|a A} which is a subset of A A and so Gf defines a relation on A.
What property must the associated digraph of such a relation have? A vertex a
corresponds to an element of A, and a directed edge from vertex a to vertex b
corresponds to the fact that f (a) = b. Therefore, since f is a function and every
input has exactly one output, the property is that every vertex is the initial vertex
of exactly one edge.
(4) How many different equivalence relations are there on the set A if |A| = 5? A
partition of A can consist of 1, 2, 3, 4 or 5 sets. The number of ways to do this can
be counted by first looking at the corresponding partitions of 5 (see WS1) which
are 5, 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1, and
then counting how many ways you can distribute the 5 elements into subsets of
these sizes. We have to be careful when counting the number possible distributions
into the 2+2+1 partition. It is 3C(5,2)
, not 3C(5, 2). (Why?) You can do this in
2
3C(5,2)
1 + C(5, 4) + C(5, 3) + C(5, 3) + 2 + C(5, 2) + 1 = 52 ways, so there are this
many partitions and hence this many equivalence realtions.
(5) Let S denote the set of students in a MA2322 class, and define a relation R on
S by (a, b) R if and only if students a and b have the same major. Under
what conditions is R an equivalence relation? The relation is always reflexive and
symmetric. The transitive property can fail if there are double majors.
(6) Find an example of an equivalence relation on R for which
(a) every set in the corresponding partition is finite. aRb a = b, because
every equivalence class has one element, because a number is only equal to
itself.
(b) every set in the corresponding partition is countably infinite. aRb ab
Z. Every equivalence class has the same cardinality as Z.
(c) the corresponding partition includes at least one finite set, at least one countably infinite set and at least one uncountable set. The easiest way to do this
1

is just to choose the partition first: for example A0 = {0}, A1 = Z {0}, A2 =


R Z and then define aRb if and only if a and b belong to the same Ai .

You might also like