Partitions, Equivalence Classes and Subsets

[gbean]

Homework Statement

Suppose A_{\lambda}, \lambda in L, represents a partition of the nonempty set A. Define R on A by xRy <=> there is a subset A{\lambda} such that x is in A{\lambda} and y is in A{\lambda}. Prove that R is an equivalence relation on A and that the equivalence classes of R are the subsets A{\lambda}.

Homework Equations

Equivalence relation: ~ that is reflexive, symmetric, and transitive.
Partition: Mutually disjoint sets that divide up the parent set; the union of the partition is the whole set
Equivalence classes: AKA the partition sets

The Attempt at a Solution

To be an equivalence relation, it has to be reflexive, symmetric, and transitive.
xRx: There is a subset A_{\lambda} such that x and x are in it.
Assume xRy. There is a subset A_{\lambda} such that x and y are in it. It follows that yRx.
Assume xRy, yRz. There is a subset A_{\lambda} such that x and y are in it. There is a subset such that y and z are in it. It follows that xRz.

I'm not sure how to prove that the equivalence classes are the subsets A_{\lambda}? Isn't that just by definition, that the partition sets are the equivalence classes?

 

[HallsofIvy]

You need to prove that all points in a given subset are equivalent and that if x and y are equivalent, then they are in the same subset. That will prove that the subsets are equivalence classes.

 

[gbean]

You need to prove that all points in a given subset are equivalent and that if x and y are equivalent, then they are in the same subset. That will prove that the subsets are equivalence classes.

How do I prove that all points in a given subset are equivalent? Wasn't that just given by the fact that it's an equivalence relation?

 

[gbean]

So I know that any two elements of Alambda are related but no element in Alambda is related to an element in Abeta (lambda does not equal beta).

Check equivalence relation: xRx means that x and x are in Alambda, which is true, so it's reflexive.
xRy => yRx. xRy means that x and y are in Alambda, and y and x being in Alambda follows, so it's symmetric.
xRy, yRz => xRz. xRy means that x and y are in Alambda, so x and y are equivalent. y and z are in Alambda also, because x is related to y, so z must be related to y and must be in Alambda. It follows that xRz because they are in the same subset.

Is this a better interpretation? Does it answer both questions?

 

[vela]

Assume xRy, yRz. There is a subset A_{\lambda} such that x and y are in it. There is a subset such that y and z are in it. It follows that xRz.

You need to provide more steps here. Right now, you're just asserting what you're trying to prove. Once you fix this, you're done with proving R is an equivalence relation.

To finish the rest of the problem, you want to do the following:

Let x ∈ A. You have two sets: [x], the equivalence class to which x belongs, and A_λ, the set in the partition that has x as an element. You want to prove [x] ⊂ A_λ and A_λ ⊂ [x] because this is what it means for the two sets to be equal.

To prove [x] ⊂ A_λ, assume y ∈ [x] and show that this implies y ∈ A_λ. This is what HallsofIvy meant when he said you have to show if x and y are equivalent, then they are in the same subset.

Similarly, to prove the other direction, assume y ∈ A_λ and show that this implies y ∈ [x]. This what HallsofIvy meant when he said you have to show all points in a given subset are equivalent.

 

[gbean]

To prove [x] ⊂ A_λ, assume y ∈ [x] and show that this implies y ∈ A_λ. This is what HallsofIvy meant when he said you have to show if x and y are equivalent, then they are in the same subset.

Is this it?
y ∈ [x] => yRx => y ∈ A_λ

Similarly, to prove the other direction, assume y ∈ A_λ and show that this implies y ∈ [x]. This what HallsofIvy meant when he said you have to show all points in a given subset are equivalent.

Is this it?
y ∈ A_λ => yRx => y ∈ [x]

Hence [x] = A_λ.

Is this sufficient to prove transitivity, as well?

Thank you so much!

 

[vela]

Is this it?
y ∈ [x] => yRx => y ∈ A_λ

Is this it?
y ∈ A_λ => yRx => y ∈ [x]

Hence [x] = A_λ.

Yup, though you obviously need to provide the context around this stuff for the complete proof.

Is this sufficient to prove transitivity, as well?

No. To show transitivity, you start with xRy and yRz. Now xRy means there's some subset A_i that contains both x and y; similarly, yRz means there's some subset A_j that contains both y and z. At this point, you've said nothing about the relationship of these two sets, A_i and A_j. They could be different elements of the partition, in which case you can't conclude xRz. You need to explain why they're not so that you can conclude xRz.

 

[gbean]

Yup, though you obviously need to provide the context around this stuff for the complete proof.

No. To show transitivity, you start with xRy and yRz. Now xRy means there's some subset A_i that contains both x and y; similarly, yRz means there's some subset A_j that contains both y and z. At this point, you've said nothing about the relationship of these two sets, A_i and A_j. They could be different elements of the partition, in which case you can't conclude xRz. You need to explain why they're not so that you can conclude xRz.

Is this sufficient?
Proof by contradiction
Assume Ai =/= Aj. Then the intersection of Ai and Aj = empty set. But this is a contradiction because y is an element of Ai and is an element of Aj. Hence, Ai = Aj.

 

[vela]

Yup. Good work!

I thought I should point out in the reasoning to show [x] ⊂ A_λ, you're using the same idea. You have xRy, which means there's a set A_i that has both x and y as an element. Because x is in both A_i and A_λ means you're talking about the same set. It might be worth mentioning this explicitly.

 

[gbean]

Nevermind, got it! Thank you.