Describing an equivalence relation

• Jan 22nd 2010, 02:27 AM
kimberu
Describing an equivalence relation
Let P1 = {C1, C2, ... CM} and P2 = {D1, D2, ... DN} be partitions of set A. P = {Ci ∩ Dj | Ci ∩ Dj does not equal the empty set} is also a partition of A.

If ≡1, ≡2, and ≡ denote the equivalences afforded by P1, P2, and P, describe ≡ in terms of ≡1 and ≡2.

--
Sadly I don't even understand what exactly this problem is asking me for. How do I describe ≡ at all? Any help would be very very much appreciated.
• Jan 22nd 2010, 04:03 AM
HallsofIvy
Quote:

Originally Posted by kimberu
Let P1 = {C1, C2, ... CM} and P2 = {D1, D2, ... DN} be partitions of set A. P = {Ci ∩ Dj | Ci ∩ Dj does not equal the empty set} is also a partition of A.

If ≡1, ≡2, and ≡ denote the equivalences afforded by P1, P2, and P, describe ≡ in terms of ≡1 and ≡2.

--
Sadly I don't even understand what exactly this problem is asking me for. How do I describe ≡ at all? Any help would be very very much appreciated.

The first part is asking you to show that P is a partition of of set A- that is, that every element of A is in one and only one set in P. Let x be an element of A. Since P1 is a partition of A, there is a unique set in P1 that contains x. Since P2 is a partition of A, there is a unique set in P2 that contains x. x is in \$\displaystyle P1\cap P2\$ and only that set in P.

The "equivalences" defined by P1 and P2 are: x≡1 y if and only if x and y are in the set in P1 and x≡2 y if and only if x and y are in the same set in P2. "x ≡ y" if and only if x and y are in the same set in P. Since P is made of intersections of sets in P1 and P2, in order to be in an intersection of two sets, x and y would have to both be in the same set in P1 and P2: x ≡ y if and only if x≡1 y and x≡2 y.