1. ## Equivalence relation

Hey

i need help with a simple proof i'm stuck with
~ is a reflexiv relation on a set M
Show:
~ is a equivalence relation $\Leftrightarrow$ $\forall x,y,z \in M \ (x \sim y) \wedge (x \sim z) \Rightarrow y \sim z$

i did this:
" $\Rightarrow$" since ~ is an equivalence relation $(x \sim y) \wedge (x \sim z) \Rightarrow (y \sim x) \wedge (x \sim z) \Rightarrow y \sim z$
first argument because ~ is symmetric second because ~ is transitiv

" $\Leftarrow$"
Reflexivity: $(x \sim y) \wedge (x \sim y) \Rightarrow (y \sim y)$
Symmetry ?
Transitivity ?

are my thoughts correct? and how do i show the last two??
thx

2. Originally Posted by LHeiner
Hey

i need help with a simple proof i'm stuck with
~ is a reflexiv relation on a set M
Show:
~ is a equivalence relation $\Leftrightarrow$ $\forall x,y,z \in M \ (x \sim y) \wedge (x \sim z) \Rightarrow y \sim z$

i did this:
" $\Rightarrow$" since ~ is an equivalence relation $(x \sim y) \wedge (x \sim z) \Rightarrow (y \sim x) \wedge (x \sim z) \Rightarrow y \sim z$
first argument because ~ is symmetric second because ~ is transitive

" $\Leftarrow$"
Reflexivity: $(x \sim y) \wedge (x \sim y) \Rightarrow (y \sim y)$
Symmetry ?
Transitivity ?

are my thoughts correct? and how do i show the last two??
thx
reflexivity is given, so you don't have to prove that. you need only prove symmetry and transitivity.

For symmetry: Hint: take x = z and see what happens in the given implication. You can use that to construct a direct proof of symmetry.

For transitivity: Hint: Take x = y and see what happens in the given implication. You can use that fact to do a proof by contradiction of transitivity.

for symmetry: $x=z : (z \sim y) \wedge (z \sim z) \Rightarrow y \sim z$ already shows that $z \sim y \Leftrightarrow y \sim z$ because we have a reflexive relation

for transitvity: suppose that ~ is not transitiv, set $x=y \Rightarrow (y \sim y) \wedge (y \sim z) \Rightarrow y \sim z$ which is a contradiction because again ~ is a reflexive relation

4. Originally Posted by LHeiner

for symmetry: $x=z : (z \sim y) \wedge (z \sim z) \Rightarrow y \sim z$ already shows that $z \sim y \Leftrightarrow y \sim z$ because we have a reflexive relation

for transitvity: suppose that ~ is not transitiv, set $x=y \Rightarrow (y \sim y) \wedge (y \sim z) \Rightarrow y \sim z$ which is a contradiction because again ~ is a reflexive relation
well, yes. that's what i said. you used a direct proof in the first case and a proof by contradiction in the second case (i would have liked for you to expound on the transitivity proof more though. your professor will see why it works, but will the average student in your class see it? you always want to write your proof simple enough so that your peers can get it)

haha, i'm sorry, my hints did give a lot away, i couldn't come up with subtler hints. it was sort of straight forward once you remembered that reflexivity was given.

5. thank you very much!

6. i would have liked for you to expound on the transitivity proof more though. your professor will see why it works, but will the average student in your class see it? you always want to write your proof simple enough so that your peers can get it
Yes, could you do that? I don't see how the following is a contradiction.
for transitvity: suppose that ~ is not transitiv, set $x=y \Rightarrow (y \sim y) \wedge (y \sim z) \Rightarrow y \sim z$ which is a contradiction because again ~ is a reflexive relation
In fact, I don't see how the following hint can be used.
For transitivity: Hint: Take x = y and see what happens in the given implication. You can use that fact to do a proof by contradiction of transitivity.
As has been said, setting x = y gives us $y \sim z \Rightarrow y \sim z$, which is a tautology. How can it be useful in making a proof by contradiction?

7. so it isn't correct?

how do you proof sym. and transitivity,then?

8. We are given that $x \sim x$ for all $x$.

So if we have $x \sim y$ than also $x \sim x$ that is $y \sim x$: symmetric.

If we know that $x \sim y~\&~y\sim z$ then by symmetry we have $y \sim x~\&~y\sim z$ by the given we have $x\sim z$.

9. Originally Posted by emakarov
Yes, could you do that? I don't see how the following is a contradiction.

In fact, I don't see how the following hint can be used.
As has been said, setting x = y gives us $y \sim z \Rightarrow y \sim z$, which is a tautology. How can it be useful in making a proof by contradiction?
Ok, here goes. For transitivity. Here's what we do. Using my hint, we have that the implication

$\displaystyle (x \sim x) \wedge (x \sim z) \implies x \sim z$ ...........(1)

is true.

Now, we wish to show that $\displaystyle (x \sim y) \wedge (y \sim z) \implies x \sim z$ (transitivity).

Assume to the contrary that $\displaystyle (x \sim y) \wedge (y \sim z)$ but $\displaystyle x \not \sim z$. Then we have $\displaystyle (x \not \sim z) \wedge (x \sim x)$ since the relation is reflexive. However, that makes the antecedent of (1) false, which makes the implication true, and so this implies that $\displaystyle x \sim z$. But that contradicts our assumption, for we assumed $\displaystyle x \not \sim z$

Plato used symmetry to prove transitivity, which is fine since symmetry was proven prior to that. I, for some reason, felt the need to do them independently *shrug*

10. Originally Posted by Jhevon
$\displaystyle (x \sim x) \wedge (x \sim z) \implies x \sim z$ ...........(1)

is true.
...
Then we have $\displaystyle (x \not \sim z) \wedge (x \sim x)$ since the relation is reflexive. However, that makes the antecedent of (1) false, which makes the implication true
The problem assumes from the beginning that ~ is reflexive. Therefore, (1) is already known to be true regardless of z; one does not have to show that its premise is false.

Originally Posted by Jhevon
and so this implies that $\displaystyle x \sim z$.
So, if A -> B is true and A is false, then B?