Relations Proof

• Apr 25th 2014, 06:00 AM
IHateProofs
Relations Proof
Let A be a nonempty subset and let B be a fixed subset of A. A relation R defined on the set of subsets of A is defined by XRY if (X intersects B) = (Y intersects B)

(a) Prove that R is an equivalence relation.
(b) Let A = {1,2,3,4,5} and B={1,3,5}. For X = {1,2,3}, find [X]

Help please? I'm working on a review before finals and I haven't seen a problem like this in months, and I can't remember how to do it. So for (a) I remember you show two cases, first that X is a subset of Y, then that Y is a subset of X, but I don't remember how to do that. I'm completely lost on (b).

• Apr 25th 2014, 08:29 AM
Plato
Re: Relations Proof
Quote:

Originally Posted by IHateProofs
Let A be a nonempty subset and let B be a fixed subset of A. A relation R defined on the set of subsets of A is defined by XRY if (X intersects B) = (Y intersects B)
(a) Prove that R is an equivalence relation.
(b) Let A = {1,2,3,4,5} and B={1,3,5}. For X = {1,2,3}, find [X]

a) Show that the relation is reflexive, symmetric, and transitive. Show us what you have done.
• Apr 26th 2014, 11:08 AM
IHateProofs
Re: Relations Proof
So after looking through months of old notes I think I finally found how to do (a). This is what I have.

Proof: We will prove this by showing that R possesses the reflexive, symmetric, and transitive properties. First we will prove that R is reflexive. Observe X ∩ B = X ∩ B. Therefore XRX and R is reflexive. Next assume XRY. Then X ∩ B = Y ∩ B. Hence Y ∩ B = X ∩ B. Therefore YRX and R is symmetric. Finally, assume XRY and YRZ. Then X ∩ B = Y ∩ B, and Y ∩ B = Z ∩ B. Hence X ∩ B = Z ∩ B. Therefore XRZ, and so R is transitive. Since R possesses the reflexive, symmetric, and transitive properties, it follows that R is an equivalence relation.

But I still can't figure out (b). I can't find anything in my old assignments about the equivalence class of a subset. If I had to guess, I'd say the answer is the super set of X ∩ B = (1,3). So [X]= {(1,3), X, (1,3,4), B, (1,2,3,4), (1,2,3,5), (1,3,4,5), A}. Is that right?
• Apr 26th 2014, 12:07 PM
Plato
Re: Relations Proof
Quote:

Originally Posted by IHateProofs
So after looking through months of old notes I think I finally found how to do (a). This is what I have.

Proof: We will prove this by showing that R possesses the reflexive, symmetric, and transitive properties. First we will prove that R is reflexive. Observe X ∩ B = X ∩ B. Therefore XRX and R is reflexive. Next assume XRY. Then X ∩ B = Y ∩ B. Hence Y ∩ B = X ∩ B. Therefore YRX and R is symmetric. Finally, assume XRY and YRZ. Then X ∩ B = Y ∩ B, and Y ∩ B = Z ∩ B. Hence X ∩ B = Z ∩ B. Therefore XRZ, and so R is transitive. Since R possesses the reflexive, symmetric, and transitive properties, it follows that R is an equivalence relation.

But I still can't figure out (b). I can't find anything in my old assignments about the equivalence class of a subset. If I had to guess, I'd say the answer is the super set of X ∩ B = (1,3). So [X]= {(1,3), X, (1,3,4), B, (1,2,3,4), (1,2,3,5), (1,3,4,5), A}. Is that right?

Yes you did the (a) part correctly.

In the part (b) your notation is off. It should be \$X\cap B=\{1,3\}\$ NOT \$(1,3)\$.
This a relation on subsets not ordered pairs.
But because \$A\cap B=B~\&~X\cap B\ne B\$ then \$A\notin [X]\$.

So redo part (b).
• Apr 27th 2014, 01:37 AM
IHateProofs
Re: Relations Proof
so...
[X]= {{1,3}, X, {1,3,4}, {1,2,3,4}}
yes?
• Apr 27th 2014, 03:43 AM
Plato
Re: Relations Proof
Quote:

Originally Posted by IHateProofs
so...
[X]= {{1,3}, X, {1,3,4}, {1,2,3,4}}
yes?

Yes.
• Apr 27th 2014, 06:34 AM
IHateProofs
Re: Relations Proof
Awesome thanks!