DMAT_L3

Zorn’s lemma

An chain is a subset of a partial order in which any two elements are comparable (basically, a totally ordered subset). Zorn’s lemma is equivalent to the axiom of choice.

Theorem 1(Zorn's Lemma).

Let $(S,\le )$ be any partially ordered set such that every chain $C$ has an upper bound. Then, $S$ has a maximal element.

A maximal element has no element greater or equal to it. It is NOT greater that or equal to every element in the set.

---

Properties of infinite cardinals

Theorem 2(Theorem).

For all $A,B$ either $|A|\le |B|$, $|A|\ge |B|$.

Proof
Let $|A|=\alpha$ and $|B|=\beta$. Assume $A$ and $B$ are infinite, since the finite case is easily handled.

Define $S\equiv \{(C,f):C\subset A,f:C\to B\text{ is injective}\}$.

$S$ is a partial order, with $(C_1,f_1)\le (C_2,f_2)$ if $C_1\subset C_2$ and $f_1\subset f_2$, i.e, $f_2{|}_{C_1}=f_1$.

Let $K$ be any chain in $S$. Let

$$C^{\prime }=\bigcup _{(C,f)\in K}C$$ $$f^{\prime }=\bigcup _{(C,f)\in K}f$$

Clearly, $f^{\prime }$ is well defined, and is injective. Thus, $(C^{\prime },f^{\prime })\in S$ is an upper bound for $K$. By Zorn’s lemma, $S$ has a maximal element $(M,g)$, $M\subset A$, $g:M\to B$, injective.

If $M=A$, we are done, since we have found an injection from $A$ to $B$, i.e, $A\le B$.
Suppose $M\subset A$ (proper subset), and $g(M)$ is a proper subset of $B$. Then, we can contradict the maximality of $(M,g)$ by extending it in a basic manner. If $g(M)=B$, we have found a surjection from $B$ to $A$, so $A\ge B$.

Theorem 3(Theorem).

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

• $|A|+|A|=|A|$
• $|A||A|=|A|$
• $|A|\le |B|$ $⟹$ $|A|+|B|=|B|$.

We will need the following theorem:

Theorem 4(Theorem).

Every infinite set $A$ has a disjoint covering of countable sets.

Coming up in the next lecture.

---

More cardinal arithmetic

The cardinality of $\mathbb{N}$ is denoted by ${\aleph }_0$. The cardinality of the reals is denoted by $c$. We know that the cardinality of $\mathbb{R}$ and the interval $[0,1]$ is the same (several bijections exist, like the stereographic projection of a unit circle onto the real line, or the sigmoid function). Also, the cardinality of $[0,1]$ is the same as the cardinality of $\{0,1{\}}^{\mathbb{N}}$ (set of all binary sequences). Thus, the cardinality of $\mathbb{R}$ is $|\{0,1{\}}^{\mathbb{N}}|=2^{{\aleph }_0}$.

Now, several non-trivial conclusions can be drawn using cardinal arithmetic.

• $|{\mathbb{R}}^n|=|\mathbb{R}\times \mathbb{R}\times \cdots \times \mathbb{R}|=|\mathbb{R}{|}^n=(2^{{\aleph }_0}{)}^n=2^{{\aleph }_{0}n}$. Now, ${\aleph }_{0}n=|\mathbb{N}\times \{1,2,\dots ,n\}|=|\mathbb{N}|$. Thus, $|{\mathbb{R}}^n|=|\mathbb{R}|$.
• Similarly, since $|\mathbb{N}\times \mathbb{N}|=|\mathbb{N}|$, we have $|{\mathbb{R}}^{\mathbb{N}}|=|\mathbb{R}|$, and $|{\mathbb{R}}^{\mathbb{Q}}|=|\mathbb{R}|$.
• That is about as far as we can stretch it, since Cantor’s Theorem forces the cardinality of the power set of $\mathbb{R}$ to be greater than $\mathbb{R}$.
• $|{\mathbb{R}}^{\mathbb{R}}|=2^{{\aleph }_{0}c}=2^c$.

Interesting note: while the set of all functions from $\mathbb{R}$ to $\mathbb{R}$ has cardinality $2^c$, the set of all continuous functions from $\mathbb{R}$ to $\mathbb{R}$ has cardinality $c$. This is because a continuous function is fully determined by the values it takes on a dense subset of its domain (Rudin, 4.4 page=3). So the cardinality of the set is equal to ${\mathbb{R}}^{\mathbb{Q}}$, and hence to $\mathbb{R}$.