An Intro to Sets III

Mike

2021-09-27 (Last Modified: 2021-11-06)

Page content

This is the third entry introducing some of the basics of set theory. Once we’re done with this, we’ll have a better grasp on some of what underlies the algebraic structures we were dealing with.

Mini-lemma: Cardinality is non-decreasing

Let $ \alpha \leq \beta $ be two ordinals, then $ |\alpha| \leq |\beta| $.

Proof

This proof is the essential part of the Cantor-Bernstein Theorem (the argument is mostly the same as theirs). We are going to prove that if $ \gamma = |\beta| $, and $ \gamma \subseteq \alpha $, then $ \gamma = |\alpha| $.

Suppose we have

$$ \begin{align} &\gamma \subseteq \alpha \subseteq \beta \\ &f : \beta \xrightarrow{\text{1-1, onto}} \gamma \\ \end{align} $$

This means that we have a bijection from $ \beta $ onto $ \gamma $, which might be a proper subset of $ \alpha $. We can’t use $ f $ directly to form a bijection from $ \beta $ onto $ \alpha $ because if $ \gamma $ is a proper subset, then it’s range will be too small.

On the other hand, if we take the identity function from $\beta$ onto $ \alpha $ we couldn’t be guaranteed a 1-1 function, because we would have to figure out what to do with $ \beta \setminus \alpha $.

The Cantor-Bernstein argument starts by considering

\[ f (\beta \setminus \alpha) = f(\beta) \setminus f(\alpha) \]

This maps the part of $ \beta $ outside $ \alpha $ inside $ \gamma $. We’d like to just use the identity within $ \alpha $, but the image of $ \beta \setminus \alpha $ is “in the way”. That is, it is preventing our hybrid “identity + part of $ f $” function from being 1-1. Thus, we need to move what would go there so that it “gets out of the way”. We do that by diverting anything that’s in $ f(\beta) \setminus f(\alpha) $ or it’s image $ f \circ f (\beta) \setminus f \circ f (\alpha) $, or that’s image, etc… We just keep on continuing this process.

We define a sequence of sets as follows:

$$ \begin{split} \beta_0 &= \beta \\ &\vdots \\ \beta_{n+1} &= f(\beta_n) \\ \end{split} \;\;\;\; \begin{split} \alpha_0 &= \alpha \\ &\vdots \\ \alpha_{n+1} &= f(\alpha_n) \\ \end{split} $$

and now to form our bijection we apply:

$$ g(x) := \begin{cases} f(x), &x \in \bigcup\limits_{0 \leq n \in \mathbb{Z}} \left (\beta_{n} \setminus \alpha_{n} \right ) \\ x, &\text{ otherwise } \\ \end{cases} $$

$ g $ is onto $ \alpha $ because if $ x $ is not in the image of one of the $ \beta_n \setminus \alpha_n $, then it is handled by the identity function on $ \alpha $. It is 1-1 because it is the disjoint union of two 1-1 functions. It’s domain is all of $ \beta $, so we have shown that

\[ g : \beta \xrightarrow{\text{1-1, onto}} \alpha \]

Now, notice that

\[ f \circ g^{-1} : \alpha \xrightarrow{\text{1-1, onto}} \gamma \]

thus $ |\alpha| = \gamma $.

QED

Corollaries: Inequalities

Let $S$ and $T$ be arbitrary sets. Then,

$\exists f: S \xrightarrow{\text{onto}} T$, if and only if $ |T| \leq |S| $.
$ \exists f: S \xrightarrow{\text{1-1}} T$, if and only if $ |S| \leq |T| $.
$ |S| \leq |T| $ and $ |T| \leq |S| $, if and only if $ |S| = |T| $

Proof

Note: in this proof, we make use of “$ f \upharpoonright X $”, which means “$f$ restricted to the set $X$, where $X$ is a subset of the domain of $f$.”

Proof of 1:

First, suppose that $\exists f: S \xrightarrow{\text{onto}} T$, then let $ <_1 $ well-order $S$. Now define

$$ \begin{align} S’ &:= \{ s \in S | \forall t <_{1} f(t) \neq f(s) \} \\ a <_{2} b &:= \begin{cases} a \in S’, &&b \in S \setminus S’ \\ a <_{1} b, &&a \text{ and } b \in S’ \\ a <_1 b, &&a \text{ and } b \in S \setminus S’ \end{cases} \\ \end{align} $$

What we’ve done with $<_2$ is defined another order in which every element of $ S’ $ comes before every element of $ S \setminus S’ $. Notice that $ <_2 $ also well-orders $S$.

Notice that

\[ (f \upharpoonright S’) : S’ \xrightarrow{\text{1-1, onto}} T \]

Since $f \upharpoonright S’ $ is a bijection from $S’$ to $T$, $ (f \upharpoonright S’)^{-1} $ exists (and is a bijection), so we can define an order, $<_3$ on $T$ as

\[ a <_3 b := (f\upharpoonright S’)^{-1}(a) <_2 (f\upharpoonright S’)^{-1}(b) \]

$ <_3 $ well-orders $T$ since $ <_2 $ well-orders $S’$, and now $f\upharpoonright S’$ is an increasing function.

Therefore, we can map $S$ and $T$ to ordinals,

$$ \begin{align} \text{Type}(S, <_2) &\mapsto \beta \\ \text{Type}(T, <_3) &\mapsto \alpha \\ \end{align} $$

where $ \alpha \subseteq \beta $, thus, by the previous lemma, $ |T| \leq |S| $.

Now, suppose $ |T| \leq |S| $. Then there are two bijections,

$$ \begin{align} f : T \xrightarrow{\text{1-1, onto}} \alpha \\ g : S \xrightarrow{\text{1-1, onto}} \beta \\ \end{align} $$

where $ \alpha \subseteq \beta $. Let

\[ S’ := \{ s \in S | f(s) \in \alpha \}\]

Now, by the Axiom of Choice we can pick an arbitrary element of $T$, let that be $ t $. Then the function,

$$ h(x) := \begin{cases} f^{-1} \circ (g \upharpoonright \alpha) (x), &x \in S’ \\ t, &x \not\in S’ \\ \end{cases} $$

is a function from $ S $ onto $T$.

Proof of 2:

Suppose that $ \exists f: S \xrightarrow{\text{1-1}} T$, and by the Axiom of Choice let $ s $ be an arbitrary element of $S$.

\[ f : S \xrightarrow{\text{1-1, onto}} \text{Range}(f) \subseteq T \]

is a bijection, so

\[ f^{-1} : \text{Range}(f) \subseteq T \xrightarrow{\text{1-1, onto}} S \]

exists. We can then form the function,

$$ h(t) := \begin{cases} f^{-1}(t), &t \in \text{Range}(f) \\ s, &t \not\in \text{Range}(f) \\ \end{cases} $$

which is a function from $T$ onto $S$ and thus, by 1, we have that $ |S| \leq |T| $.

Now, suppose $ |S| \leq |T| $. Then, by 1, we have

\[ f : T \xrightarrow{\text{onto}} S \]

We can well-order $T$, just as we did to $S$ in the proof of part 1, to get

\[ f \upharpoonright T’ : T’ \xrightarrow{\text{1-1, onto}} S \]

then

\[ (f \upharpoonright T’)^{-1} : S \xrightarrow{\text{1-1, onto}} T’ \subseteq T \]

Proof of 3:

This is a direct consequence of the fact that cardinals are also ordinals and 3 is true for ordinals.

QED

Theorem: One of Cantor’s

Let $S$ be a set, then $ P(S) $, the power set of $S$ does not have the same cardinality as $S$. In fact, it has a larger cardinality.

Proof

Suppose, for a contradiction, that there is a set whose power set has the same cardinality as it does. Then we have $S$ and a bijection,

\[ f : S \rightarrow P(S) \]

Now, consider

\[ X := \{ s \in S | s \not\in f(s) \} \]

What might $ f^{-1}(X) $ be? Let’s call it $x$. There are then two cases to consider:

$ x \in X $. In this case, $ x \in f(x) $, so $ x $ cannot belong to $X$. A contradiction.
$ x \not\in X $. In this case, $ x \not\in f(x) $, so $ x $ must belong to $X$, a contradiction.

Those are the only possibilities, and neither works. Thus, we cannot have such an $f$. Note that there are at least as many elements of $ P(S) $ as there are elements of $S$ (consider the singleton sets $ \{ s\} $ for each $ s \in S $), so $ P(S) $ must have larger cardinality by the previous corollary.

QED

The Axiom of Infinity guarantees the existence of an infinite set. The theorem we just proved shows that it’s power set must be “bigger” (i.e. it must have a larger cardinality). Clearly, this process won’t end. We could construct the power set of the power set, etc… Therefore, there are an infinite number of infinite cardinals. We’ll go into this more later. It actually has practical implications on a wide-range of mathematics, especially in analysis.

We’ll finish by defining something which comes up quite often in math:

Definition: Countable

We define:

$ \omega_{0} $ to be the least infinite ordinal.
$ \aleph_{0} $ to be the least infinite cardinal.

A set $S$, such that $ |S| \leq \aleph_0 $ is said to be countable.

On the other hand, a set $S$, such that $ |S| > \aleph_0 $ is said to be uncountable.

Definition: Ordinal Arithmetic

Ordinal addition is not, in general, commutative. It is always increasing in the right argument. We sometimes use $ \alpha \dotplus \beta $ to emphasize that the addition is Ordinal and not Cardinal addition. Similarly, we’ll write “$ \dot{\times} $” to specify Ordinal multiplication, if the context isn’t already clear. Sometimes we’ll use them, even when the context is clear, as it is below.

Note, we’re not always consistent in our notation. We’ve shortened “the successor ordinal of $ \alpha $” as “$ \alpha + 1$” (or “$ \alpha \dotplus 1 $”). It’s customary to write “$ n $” for every finite ordinal, instead of expressing it as a set. This means that, when we’re treating it as an ordinal, we will usually write “$ 0 $” instead of “$ \emptyset $” from now on.

In what follows, let $ \alpha $ be an arbitrary ordinal.

Addition:

\[\alpha \dotplus 0 := \alpha \]

In an earlier entry we calculated

\[ \alpha \dotplus 1 = \alpha \cup \{ \alpha \} \]

Let $ \beta = \gamma \dotplus 1 $, then

\[ \alpha \dotplus \beta := (\alpha \dotplus \gamma) \dotplus 1 \]

Let $ \lambda $ be a limit ordinal, then

\[ \alpha \dotplus \lambda := \sup\limits_{\beta \in \lambda} \{ \alpha \dotplus \beta \} \]

Multiplication:

\[ \alpha \dot{\times} 0 := 0 \]

Let $ \beta = \gamma \dotplus 1 $, then

\[ \alpha \dot{\times} \beta := (\alpha \dot{\times} \gamma) \dotplus \alpha \]

Let $ \lambda $ be a limit ordinal, then

\[ \alpha \dot{\times} \lambda := \sup\limits_{\beta \in \lambda} \{ \alpha \dot{\times} \beta \} \]

Exponentiation:

if $ 0 < \alpha $, then

\[ \alpha^{0} := 1 \]

if $ \beta = \gamma \dotplus 1 $, then

\[ \alpha^{\beta} := (\alpha^{\gamma} ) \dot{\times} \alpha \]

if $ \lambda $ is a limit ordinal, then

\[ \alpha^{\lambda} := \sup\limits_{\beta \in \lambda} \{ \alpha^{\beta} \} \]

Definition: Cardinal Arithmetic

Let $ \alpha $ and $ \beta $ be arbitrary cardinals, then

$ \alpha + \beta $ is equal to

\[ | \{ 0 \} \times \alpha \cup \{ 1 \} \times \beta | \]

where “$ \times $” in the formula is the Cartesian Product

$ \alpha \times \beta $ is equal to

\[ | \alpha \times \beta | \]

where, once again, the “$ \times $” in the formula is the Cartesian Product.

$ \alpha^{\beta} $ is equal to

\[ | \{f \in P(\beta \times \alpha) | f : \beta \rightarrow \alpha \} | \]

Definition: Successor and Limit Cardinals

Let $ \kappa $ be a cardinal, then we define $ \kappa^{+} $ to be the least cardinal greater than $ \kappa $.

If $ \mu = \kappa^{+} $, for some cardinal, $ \kappa $, then $ \mu $ is said to be a successor cardinal.

If $ \lambda $ is a cardinal, such that there is no cardinal $ \mu $, such that $ \mu^{+} = \lambda $, then $ \lambda $ is said to be a limit cardinal.

Mini-lemma: cardinality of power set

Let $ S $ be a set, then $ |P(S)| = 2^{|S|} $.

Proof

Let $ \alpha = |S| $, then let

\[ f : S \xrightarrow{\text{1-1, onto}} \alpha \]

so we can map subsets of $S$ to the set of functions

\[ \{ g \in P(\alpha \times 2) | g : \alpha \rightarrow 2 \} \]

where we are going to treat $2$ as the set $ \{ 0,1 \} $, which is what it is when viewed as an ordinal. Also note, that $2$ is a cardinal (as are all finite ordinals).

We map them as follows

$$ \begin{align} S &\supseteq A \xmapsto{\text{1-1, onto}} \chi_{ f(A) } \\ &\text{where} \\ f(A) &:= \{ \beta \in \alpha | \exists a \in A, f(a) = \beta \} \\ \end{align} $$

where $ \chi_{f(A)} $ is the characteristic function of $ f(A) \subseteq \alpha $. I.e.

$$ \chi_{f(A)}(\beta) := \begin{cases} &1, &&\beta \in A \\ &0, &&\beta \not\in A \\ \end{cases} $$

It is 1-1, because any two distinct subsets of $S$ will be mapped by $f$ to two distinct subsets of $\alpha$, since $f$ is a bijection. It is onto, because any function

\[ g : \alpha \rightarrow 2 \]

defines a subset of $ \alpha $ by

\[ B_{g} := \{ b \in \alpha | g(b) = 1 \} \]

which defines a subset of $S$ by

\[ \{ s \in S | f(s) \in B_{g} \} \]

QED

By this theorem of Cantor’s, we now have proved that for all cardinals, $ \kappa $, we have

\[ \kappa \lneq 2^{\kappa} \]

In particular (and famously),

\[ \aleph_0 \lneq 2^{\aleph_0} \]

That’s all for this entry. We’ve only just barely scratched the surface of Set Theory. We’ll return to it later. In the next entry, we will be returning to Algebra!

Thanks for reading!!