Prove that these are equivalence relations.

29 Views Asked by At

1) $\mathbf{R} = \{ (x,y) \in \mathbb{N^2} : 2|x \ \land \ 2|y \}$

$$\text{reflexive: } (2|x \land 2|y)\mathbf{R}(2|y \land 2|x) \ \textbf{[True]}\\ \text{symmetric: } (2|x_1 \land 2|y_1) \mathbf{R}(2|x_2 \land 2|y_2) \implies (2|x_2 \land 2|y_2) \mathbf{R}(2|x_1 \land 2|y_1) \ \textbf{[True]}\\ \text{transitive: } (2|x_1 \land 2|y_1) \mathbf{R}(2|x_2 \land 2|y_2), (2|x_2 \land 2 | x_2)\mathbf{R}(2|x_3 \land 2|y_3) \implies (2 |x_1 \land 2|y_1)\mathbf{R}(2|x_3 \land 2|y_3) \ \textbf{[True]}\ $$

2) $\mathbf{R} = \{ (x,y) \in \mathbb{N^2} : x|y \ \lor \ y|x \}$

$$\text{reflexive: } (x|x \lor y|y) \ \textbf{[True]} \\ \text{symmetric: } (x|y \lor y|x) \implies (y|x \lor x|y) \ \textbf{[True]} \\ \text{transitive: } (x|y \ \lor \ y|x) \ , \ (y|z \ \lor z|y) \implies (x|z \lor z|x) \ \textbf{[True]} $$

are my proofs right?

1

There are 1 best solutions below

3
On BEST ANSWER

Actually, it's only 2(symmetric) and 2(transitive) you got right. For 2-reflexive, you should prove that $xRx$, which is equivalent to proving that $(x|x \vee x|x)$ (note there's no $y$).

More importantly, your notation in 1) doens't make sense. It doens't make sense at all to write $(2|\wedge 2|)R(2|\wedge2|)$, cause you have to have just a natural number on either side of $R$. Remember, it's the numbers that are related with $R$, not the conditions. Take 1(symmetric) for example. You need to show that $$ xRy \implies yRx $$ and the definition of $R$ says that $xRy$ means that $2|x\wedge 2|y$, so you need to show that $$ 2|x \wedge 2|y \implies 2|y \wedge 2|x $$ Makes sense?

You should also think about what you're actually proving - I claim that the $R$ in 1) is not an equivalence relation at all. Can you see which point fails?