21 - Equivalence relations

!Screenshot 2023-10-26 at 8.31.09 PM.png
!Screenshot 2023-10-26 at 8.32.53 PM.png

In Class Practice

Hint for 21.1
Follow example 20.14. Then use the definition of an equivalence class.

Draw a diagram for 21.2

E 21.4 Proof
Let A = {1, 2, 3, 4, 5} and S = {{1, 2}, {3, 4}, {5}}

Define

$R=\{(1,2),(2,1),(1,1),(2,2),(3,4),(4,3),(3,3),(4,4),(5,5)\}$

Proof. Let A, R, S be as stated above. We show that R is an equivalence relation.

(Reflexive): Let $a\in A$. There is an $X\in S$ such that $a\in X$. Hence $(a,a)\in R$. So $aRa$. Therefore $R$ is reflexive.

(Symmetric.) Let $a,b\in A$. Assume that $aRb$. Then $(a,b)\in R$. So there is a set $X\in S$ such that $a,b\in X$. Hence $bRa$ so $(b,a)\in R$. Thus $R$ is symmetric.

(Transitive.) Let a, b, c ∈ A and assume aRb and bRc. Then there is some X ∈ S such that a,b ∈ X, and there is some Y ∈ S such that b,c ∈ Y. Since the elements ofSaredisjoint,b∈Xandb∈Y impliesthatX=Y.Therefore,bothaandcare in X, and aRc. Therefore R is transitive.

Show that a, b in X

HW 21

Ben Finch

E 21.1
Reflexive.
Proof. We see that for each $x\in A$ there exists $(x,x)\in R$. Thus $R$ is reflexive. $◻$

Symmetric.
Proof. We see that for each $(a,b)\in R$ there exists $(b,a)\in R$. Thus $R$ is symmetric. $◻$

Transitive.
Disproof. Fix a = 1, b = 2, c = 3. We see $aRb$ and $bRc$ since $(1,2)\in R$ and $(2,3)\in R$. However $a\mathrm{R̸}c$ since $(1,3)\notin R$. Thus R is not transitive.

Antisymmetric.
Disproof. Fix $a=1$, $b=2$. We have $aRb$ and $bRa$ since $(a,b)\in R$ and $(b,a)\in R$, but $a\ne b$. Thus R is not antisymmetric.

Since R is not transitive, R is not an equivalence relation.

E 21.2
Let $A=\{1,2,3,4,5\}$. The equivalence relations are {1, 2, 3} and {4, 5}.

Equivalence classes:
[1] = {1, 2, 3}
[2] = {1, 2, 3}
[3] = {1, 2, 3}
[4] = {4, 5}
[5] =

E 21.3
The following ordered pairs must be in R.

E 21.4
[1] = {1, 2}
[2] = {1, 2}
[3] = {3, 4}
[4] = {3, 4}
[5] =

E 21.5
a)
Proof.
Let A = $\mathbb{R}-\{0\}$.
$a\sim b$ if $ab>0$.
We aim to prove that $\sim$ is an equivalence relation on $A$.

Reflexive. Assume $a\in A$. Then $aRa$ since $a\cdot a=a^2>0$. Thus $\sim$ is reflexive.

Symmetric. Let $a,b\in A$. Assume $aRb$. Then $a\cdot b>0$. Thus $b\cdot a>0$. Hence $bRa$. Thus $\sim$ is symmetric.

Transitive. Let $a,b,c\in A$. Assume $aRb$ and $bRc$. Then $a\cdot b>0$ and $b\cdot c>0$. We use the facts that:

• multiplying two positive real numbers yields a positive number
• multiplying two negative real numbers yields a positive number

We have two cases.

Case 1: $a>0$. Then $b$ is positive since $a\cdot b>0$. Then $c$ is positive since $b\cdot c>0$. Thus $a\cdot c>0$ so we have $aRc$.

Case 2: $a<0$. Then $b$ is negative since $a\cdot b>0$. Then $c$ is negative since $b\cdot c>0$. Thus $a\cdot c>0$ so we have $aRc$.

Thus $\sim$ is transitive.

Since $\sim$ is reflexive, symmetric, and transitive, it is an equivalence relation. $◻$

b)
Using the facts that:

• multiplying two positive real numbers yields a positive number
• multiplying two negative real numbers yields a positive number
• multiplying a positive real number with a negative number yields a negative number

we see that the equivalence classes are

1. {$x\in \mathbb{R}$ : $x>0$}
2. {$x\in \mathbb{R}$ : $x<0$}

E 21.6
Proof.
Let A - the set of humans with English names.

$\alpha \approx \beta$ if the name of $\alpha$ and the name of $\beta$ start with the same letter.

Reflexive.
Assume that $\alpha$ is A. Then $\alpha$ starts with the same letter as $\alpha$ so $\alpha \approx \alpha$. So $\approx$ is reflexive.

Symmetric.
Assume that $\alpha \approx \beta$. Then $\alpha ,\beta$ start with the same letter. Thus $\beta \approx \alpha$. So $\approx$ is symmetric.

Transitive.
Assume that $\alpha \approx \beta$ and $\beta \approx \gamma$. Then $\alpha ,\beta$ have the begin with the same letter and $\beta ,\gamma$ begin with the same letter. Then $\alpha ,\gamma$ begin with the same letter so $\alpha \approx \gamma$. Thus $\approx$ is transitive.

Since $\approx$ is reflexive, symmetric, and transitive, $\approx$ is an equivalence relation on A. $◻$

b) The equivalence classes of $\approx$ are the groups of English names that begin with the same letter.

E 21.7
Let $R$ be a reflexive, symmetric, and antisymmetric relation on a set $A$. We want to show that $R$ is an equality relation, or in other words, for any $x$, $y$ $\in$ $A$, we have $xRy$ if and only if $x=y$.

Proof:

We will prove both directions:

$\Rightarrow$ Suppose $xRy$ for some $x$, $y$ in $A$. Use the antisymmetry of $R$ which states that if $xRy$ and $yRx$, then $x=y$. We have $xRy$ by assumption, and since $R$ is symmetric (which means if $xRy$, then $yRx$), we also have $yRx$. Therefore, by antisymmetry of $R$, we must have $x=y$.

$\Leftarrow$ Suppose $x=y$ for some $x$, $y$ in $A$. We want to show $xRy$. Because $R$ is a reflexive relation we know that $xRx$. But since $x=y$, we can replace $x$ with $y$ and conclude $yRy$, or equivalently $xRy$.

Therefore, we have proven that for any $x$, $y$ in $A$, $xRy$ if and only if $x=y$. Hence, $R$ is an equality relation on $A$. $◻$