22 - Equivalence classes and partitions

!Screenshot 2023-10-30 at 10.03.06 AM.png

1. No equivalence class is empty
2. Every element of $A$ is in some equivalence class
3. Any two classes are either disjoint or equal

Partition

!Screenshot 2023-10-30 at 10.07.48 AM.png

Let A =

The following is a partition of A:

P = {{1}, {2}, {3, 4, 5}}

!Screenshot 2023-10-30 at 10.10.39 AM.png

!Screenshot 2023-10-30 at 10.15.42 AM.png

!Screenshot 2023-10-30 at 10.17.47 AM.png
Transversal - EXAM QUESTION?

In class practice

Define a relation on by (a, b)

HW 22

Ben Finch

E 22.1
One part:

Two Parts:

1. {{1, 2},{3, 4}}
2. {{1},{2, 3, 4}}
3. {{1, 2, 4},{3}}
4. {{1, 3, 4},{2}}
5. {{1, 4}{2, 3}}
6. {{2, 3}, {1, 4}}
7. {{1, 3}, {2, 4}}

Three Parts:

1. {{1}, {2}, {3, 4}}
2. {{1, 2}, {3}, {4}}
3. {{1}, {2, 3}, {4}}
4. {{1, 3}, {2}, {4}}
5. {{1, 4}, {2}, {3}}
6. {{1}, {2, 4}, {3}}

Four parts:

E 22.2
a) No. Given that the sizes of the equivalence classes for $a,b$, and $c$ are different, none of these elements can be related by $\sim$.

b) There are four equivalence. Since 9/10 elements are represented by [a], [b], [c], there must be one missing, call it $d$. So the final equivalence class is [d].

E 22.3
a) [(3, 4)] = $\{(c,d)\in {\mathbb{R}}^2:25=c^2+d^2\}$
!375

b) $[(a,b)]$ = $\{(c,d)\in {\mathbb{R}}^2:a^2+b^2=c^2+d^2\}$
c)
Proof.

Let $K$ be the set $[0,\mathrm{\infty })\times \{0\}$.

Consider any $(a,b)\in {\mathbb{R}}^2$. Define the point $p=(\sqrt{a^2+b^2},0)$. Clearly, $p\in K$. We know that $(a,b)\sim p$ since

Therefore, each equivalence class under $\sim$ has at least one representative in $K$.

Next, we aim to show that this representative is unique. Assume there exist two distinct points $p_1=(r_1,0)$ and $p_2=(r_2,0)$ in $K$ such that $(a,b)\sim p_1$ and $(a,b)\sim p_2$. Then, we have

Since $r_1,r_2\ge 0$, we must have $r_1=r_2$, contradicting the assumption that $p_1$ and $p_2$ are distinct. Hence, each equivalence class under $\sim$ has at most one representative in $K$.

Therefore, the set $[0,\mathrm{\infty })\times \{0\}$ is a transversal of $\sim$. $◻$

E 22.4
Let W be the set of all words in the English language. Define a relation on W by $\alpha \approx \beta$ if $\alpha$ and $\beta$ have the same first letter.

a)
Reflexive.
Let $\alpha \in W$. Then $\alpha$ starts with the same letter as $\alpha$. Thus $\approx$ is reflexive.

Symmetric.
Let $\alpha ,\beta \in W$. Assume $\alpha \approx \beta$. Then $\alpha ,\beta$ start with the same letter. Thus $\beta$ and $\alpha$ start with the same letter. So $\approx$ is symmetric.

Transitive
Let $\alpha ,\beta ,\gamma \in W$. Assume $\alpha \approx \beta$ and $\beta \approx \gamma$. Then $\alpha ,\beta$ start with the same letter and $\beta ,\gamma$ start with the same letter. Therefore $\alpha ,\gamma$ start with the same letter. So $\approx$ is transitive.

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

b)

1. "cannot"
2. "continue"
3. "creating"
4. "crafty"
5. "calculations"
6. "cookie"

c) 26, one for each letter in the alphabet.

d)

E 22.5
Let $A$ be a set with $n$ elements. Define a relation ∼ on $\mathcal{P}(A)$ by $X\sim Y$ if $|X|=|Y|$, for any $X,Y\in \mathcal{P}(A)$.

a)
Reflexive. Let $X\in \mathcal{P}(A)$. Then $|X|=|X|$. So $\sim$ is reflexive.

Symmetric. Let $X,Y\in \mathcal{P}(A)$. Assume $X\sim Y$, so $|X|=|Y|$. Then $|Y|=|X|.$ So $\sim$ is symmetric.

Transitive. Let $X,Y,Z\in \mathcal{P}(A)$. Assume $X\sim Y$ and $Y\sim Z$. Then $|X|=|Y|$ and $|Y|=|Z|$. So $|X|=|Z|$. So $\sim$ is transitive.

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

b) The equivalence classes of $\sim$ consist of all elements (sets) in $\mathcal{P}(A)$ that have the same length. For example, [2] is the set containing all combinations (sets) of any two elements in $A$.

c) There are $n$ equivalence classes.

d) A transversal of $\sim$ would be the set containing exactly one element from each equivalence class. So it would include exactly one set with length 1, one set with length 2, ..., and one set with length $n$.

e) Let [a] be an equivalence class of $\sim$. Then by property of power sets, there are $(\genfrac{}{}{0ex}{}{n}{a})$ elements in [a].

E 22.6
Let $A=\{1,2,...,10\}$. For each $i\in A$, define

$S_i$ ={$X\in P(A)$ : $i$ is the least element of $X$}

Let $P=\{\varnothing ,S_1,...,S_{10}\}$

a)
Proof.
We aim to show:

1. No set in $P$ is empty.
2. The sets in $P$ are disjoint.
3. The union of the sets in $P$ is $\mathcal{P}(A)$.

No set in $P$ is empty:
$\{\mathrm{\varnothing }\}$ is clearly non-empty as it contains the empty set. For $S_i$, if $i$ exists in $A$ then the set $\{i\}$ belongs to $S_i$ because $i$ is the least element of $\{i\}$. Therefore, $S_i$ is non-empty for each $i$.

The sets in $P$ are disjoint:
Assume there are sets $S_i$ and $S_j$ such that $i\ne j$ and their intersection is non-empty. Let $X$ be an element in this intersection. By definition of $S_i$ and $S_j$, $i$ and $j$ would both be the least elements of $X$, which is a contradiction. Thus, $S_i$ and $S_j$ cannot have any common elements and are therefore disjoint. $\{\mathrm{\varnothing }\}$ is also disjoint with any $S_i$.

The union of the sets in $P$ is $\mathcal{P}(A)$:
Let $X$ be an element in $\mathcal{P}(A)$. If $X=\mathrm{\varnothing }$, then $X$ belongs to $\{\mathrm{\varnothing }\}$. If $X\ne \mathrm{\varnothing }$, then $X$ has a least element $i$. Therefore, $X$ belongs to $S_i$. Thus, every set in $\mathcal{P}(A)$ belongs to some set in $P$, which means the union of the sets in $P$ is $\mathcal{P}(A)$.

Thus $P$ is a partition of $\mathcal{P}(A)$. $◻$

b) There are 11, one for each element in A, plus the empty set.

c) $T=\{\varnothing ,\{1\},\{2\},\dots ,\{10\}\}$

d) [{8,9,10}]={{8},{8,9},{8,10},{8,9,10}}

e) $2^8=256$

E 22.7
$1⟹2$
Assume that $x\sim y$. By symmetry we have $y\sim x$. Then by definition of equivalence classes (21.11), $y,x\in [x]$ and $x,y\in [y]$. Thus the intersection of $[x]$ and $[y]$ contains at minimum $x$ and $y$ and therefore is nonempty.

$2⟹3$
Assume that $x$ and $y$ intersect nontrivially. Let $z$ be some element such that $z\in [x]$ and $z\in [y]$. Thus $x\sim z$ and $y\sim z$. By the transitive property, $x\sim y$. This implies that every element in $[y]$ is related to $x$, or $[y]\subseteq [x]$.

By a similar argument, since, by symmetry we have $y\sim x$, every element in $[x]$ is related to $y$, and hence, every element in $[x]$ belongs to $[y]$. This means $[x]\subseteq [y]$.

Putting these two statements together, we get $x=y$.

$3⟹1$
Assume that $[x]=[y]$.
Certainly! Let's prove that (3 \implies 1):

This means every element in $[x]$ is also in $[y]$ and vice-versa. We know $x\in [x]$ by definition of an equivalence class. Since $[x]=[y]$, we also have $x\in [y]$.

Now, by definition of equivalence classes, if $x\in [y]$, then $x\sim y$. $◻$

E 22.8
Proof.

Assume that $[a]=\overline{a}$ for all $a\in A$. We aim to prove that for any $a,b\in A$, we have $a\sim b$ iff $b\approx a$

$⟹$
Assume $a\sim b$ for some $a,b\in A$. By the definition of equivalence classes, this means $b\in [a]$. Then $b\in \overline{a}$. By the definition of equivalence under $\approx$, this means $a\approx b$. Thus, we have shown that if $a\sim b$, then $a\approx b$.

$⟸$
Assume $a\approx b$ for some $a,b\in A$. By the definition of equivalence classes, this means $b\in \overline{a}$. Then $b\in [a]$. By the definition of equivalence under $\sim$, this means $a\sim b$. Thus, we have shown that if $a\approx b$, then $a\sim b$.

Since we have shown both directions, we conclude that $a\sim b$ if and only if $a\approx b$ for all $a,b\in A$. Therefore, the two equivalence relations $\sim$ and $\approx$ are the same.

Hence, if two equivalence classes are the same, then the relations are the same. $◻$