DMAT_L4

Disjoint coverings

Definition 1(Definition).

Let $A$ be an infinite set. Let $\mathbf{D}=\{D_i:i\in I\}$, where $|D_i|={\aleph }_0$, and $D_i\cap D_j=\varnothing$ for all $i\ne j\in I$, and ${\bigcup }_{i\in I}{D}_i=A$. Then, $\mathbf{D}$ is called a disjoint covering of $A$.

To prove the theorem stated in the previous lecture, we need the following theorem:

Theorem 2(Theorem).

Every infinite set has a disjoint covering.

Proof
Let $A$ be an infinite set.
Define $P\equiv \{(B,\mathbf{D}):B\subset A,\mathbf{D}\text{ is a disjoint covereing of }B\}$. We know that $P$ is non empty, since countable subsets of $A$ have the trivial covering.
Define a partial order by $(B_1,{\mathbf{D}}_1)\le (B_2,{\mathbf{D}}_2)$ if $B_1\subset B_2$ and ${\mathbf{D}}_1\subset {\mathbf{D}}_2$.

Let $C$ be any chain in $(P,\le )$.
$C=\{(B_i,{\mathbf{D}}_i):i\in I\}$.
For all $i,j\in I$, either $(B_i,{\mathbf{D}}_i)\le (B_j,{\mathbf{D}}_j)$, or vice versa.
Let $B={\bigcup }_{i\in I}{B}_i$ and $\mathbf{D}={\bigcup }_{i\in I}{\mathbf{D}}_i$. It is easy to see that $\mathbf{D}$ is a disjoint covering for $B$. $(B,\mathbf{D})\in P$, so Zorn’s lemma is applicable. Let $(\hat{B},\hat{\mathbf{D}})$ be the maximal element.

If $\hat{B}=A$, we are done.
If $\hat{B}$ is a proper subset of $A$, two cases:

• $A\setminus \hat{B}$ is finite: Change the covering by appending the finite elements to some ${\hat{\mathbf{D}}}_i$. Does not create a contradiction.
• If it is infinite, you can take a countable subset of it and add it to $\hat{\mathbf{D}}$, contradicting the maximality of $(\hat{B},\hat{\mathbf{D}})$.

---

More properties of infinite cardinals

Now we’re equipped to have a crack at these.

Theorem 3(Theorem).

Let $A$ and $B$ be any infinite sets.

1. $|A|+|A|=|A|$
2. $|A|\le |B|$ $⟹$ $|A|+|B|=|B|$.
3. $|A||A|=|A|$

Proof of 1

We have to construct a bijection from $(A\times \{1\})\cup (A\times \{2\})\to A$. Define $A_1\equiv A\times \{1\}$, $A_2\equiv A\times \{2\}$. Let $A$ have a disjoint covering $A=\bigcup D_i$. This gives us disjoint coverings for $A_1$ and $A_2$: $A_1=\bigcup (D_i\times \{1\})$, $A_2=\bigcup (D_i\times \{2\})$.

Define $\varphi :\{D_i\times \{1\}\}\cup \{D_i\cup \{2\}\}\to \{D_i\}$ such that it maps the elements of $(D_k\times \{1\})\cup (D_k\times \{2\})$ to $D_k$ alternatively, i.e, if the elements of $D_k$ were $d_1,d_2,\dots$, $\varphi$ would map $(d_1,1)\mapsto d_1$, $(d_1,2)\mapsto d_2$, $(d_2,1)\mapsto d_3$, and so on. Note that $\varphi$ is a bijection. Thus, $|A\times \{1\}\cup A\times \{2\}|=|A|$, i.e, $|A|+|A|=|A|$.

Proof of 2

Let If $|A|\le |B|$, we have $|B|\le |A\cup B|\le |B\cup B|$, since trivial injections exist from sets on the left of the inequalities to sets on the right. It follows that $|B|\le |A|+|B|\le |B|+|B|=|B|$. From the Schröder–Bernstein theorem, it follows that $|A|+|B|=|B|$.

Proof of 3

To obtain an bijection from $A\times A\to A$, define
$P\equiv \{(B,f)|f:B\times B\to B,f\text{ is bijective},B\subset A\}$. Define a partial order on $P$ by $(B_1,f_1)\le (B_2,f_2)$ if $B_1\subset B_2$ and $f_1\subset f_2$. Let $C$ be any chain in $(P,\le )$. $C=\{(B_i,f_i)|i\in I\}$. Let $B=\bigcup B_i$ and $f=\bigcup f_i$. It is evident that $f:B\times B\to B$ is bijective. Thus, $(B,f)\in P$, and every chain in $(P,\le )$ has an upper bound. From Zorn’s lemma, $(P,\le )$ must have a maximal element $(\hat{B},\hat{f})$.

If $|\hat{B}|=|A|$, i.e, there exists a bijection between $\hat{B}$ and $A$, we are done. So, assume $|\hat{B}|\ne |A|$. Note that $|A\setminus \hat{B}|\ge |\hat{B}|$, since otherwise $|A|=|(A\setminus \hat{B})\cup |\hat{B}||=|A\setminus \hat{B}|+|\hat{B}|=|\hat{B}|$. So there must exist $\overline{B}\subset A\setminus \hat{B}$ such that $|\overline{B}|=|\hat{B}|$. Let $\tilde{B}=\hat{B}\cup \overline{B}$. Now, $\tilde{B}\times \tilde{B}=\hat{B}\times \hat{B}\cup \overline{B}\times \hat{B}\cup \hat{B}\times \overline{B}\cup \overline{B}\times \overline{B}$. Note that since $|\hat{B}||\hat{B}|=|\hat{B}|$,

$$\begin{array}{rl}& |\overline{B}\times \hat{B}\cup \hat{B}\times \overline{B}\cup \overline{B}\times \overline{B}|\\ =& |\overline{B}||\hat{B}|+|\hat{B}||\overline{B}|+|\overline{B}||\overline{B}|\\ =& |\hat{B}|\end{array}$$

So, there must exist a bijection $\overline{f}:\overline{B}\times \hat{B}\cup \hat{B}\times \overline{B}\cup \overline{B}\times \overline{B}\to \overline{B}$. Define $\tilde{f}:\tilde{B}\times \tilde{B}\to \tilde{B}$ like so:

$$\begin{array}{r}\tilde{f}(x,y)=\{\begin{array}{ll}\hat{f}(x,y)& (x,y)\in \hat{B}\times \hat{B}\\ \overline{f}(x,y)& \text{otherwise}\end{array}\end{array}$$

and notice $(\tilde{B},\tilde{f})\in P$ and $(\tilde{B},\tilde{f})\ge (\hat{B},\hat{f})$, which contradicts the maximality of $(\hat{B},\hat{f})$.