PDA

View Full Version : Incorrect proof



tegra97
04-17-2007, 05:13 PM
Claim: Let R be an equivalence relation on the set A, and let x,y, and z be elements of A. If x belongs to y/R and z does not belong to x/R, then z does not belong to y/R.


Proof: Assume that x belongs to y/R and z belongs to x/R. Then yRx and xRz. By transititvity, yRz, so z belongs to y/R. Therefore, if x belongs to y/R and z does not belong to x/R, then z does not belong to y/R.

Can someone tell me why this proof is incorrect. Thanks.

daon
04-17-2007, 05:33 PM
Claim: Let R be an equivalence relation on the set A, and let x,y, and z be elements of A. If x belongs to y/R and z does not belong to x/R, then z does not belong to y/R.


Proof: Assume that x belongs to y/R and z belongs to x/R. Then yRx and xRz. By transititvity, yRz, so z belongs to y/R. Therefore, if x belongs to y/R and z does not belong to x/R, then z does not belong to y/R.

Can someone tell me why this proof is incorrect. Thanks.


I'm not familiar with your notations, but I think y/R means the equivilance class of y. If thats true, then it looks like an okay proof to me. Your teacher may be hung up on the first sentence, because it LOOKS like you're assuming a different hypothesis than what has been given. Here's a better version:

If x is in y/R, this means that x/R = y/R. So if z is not in x/R its not in y/R.

pka
04-17-2007, 05:36 PM
GIVEN Let R be an equivalence relation on the set A, and let x,y, and z be elements of A. If x belongs to y/R and z does not belong to x/R, PROVE z does not belong to y/R.

PROOF: Assume that x belongs to y/R and z belongs to y/R; then yRx and yRz.
By symmetry we have xRy and yRz; by transititvity, xRz, so z belongs to x/R.
That is a contradiction. So z belongs to y/R is false.


If x is in y/R, this means that x/R = y/R. So if z is not in x/R its not in y/R.
daon, I think that that is what he is asks to prove.
I agree with his instructor that his is not a proof.

tegra97
04-17-2007, 05:55 PM
Thanks doan and pka you guys have been very helpful.