An Intro to Sets II

Mike

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

Math, Sets

Page content

In this entry, we continue our introduction to sets and cover more basic set theory.

Theorem: The class of ordinals is well-ordered

Let $ ON $ denote the collection of all ordinals. Then we have

$ ON $ is well-ordered by “$ \in $”
$ ON $ is not a set. It is a class of sets.

We should also note that in order for a class to be well-ordered by an order relation, $ <_w $, we have to have that for each set $X \subsetneq ON$, there is a $ <_w $-least element, $\lambda$.

Proof

Proof of 1:

Let $S$ be a non-empty set of ordinals. We will show that

\[ \epsilon = \bigcap\limits_{\sigma \in S} \sigma \]

is an ordinal, and furthermore, that it is an element of $S$.

First, we show that it is well-ordered by $ \in $. Notice that $ \epsilon \subseteq s $, where $s$ is any ordinal in $S$. Since $s$ is an ordinal, it is well-ordered by $ \in$, and therefore has a $ \in $-least element.

Second, we show that $ \epsilon $ is transitive. Let $ \gamma \in \epsilon $ and $ \delta \in \gamma $. That means that $ \gamma $ is in $ \sigma $ for every $ \sigma \in S $, and since every $ \sigma $ in $S$ is an ordinal, it is transitive, which means that $ \delta $ is also in $ \sigma $. Thus $ \delta \in \sigma $ for each $ \sigma $, which means that $ \delta \in \epsilon $. Thus $ \epsilon $ is transitive. It is therefore an ordinal.

By part 2 of the previous mini-lemma, since $ \epsilon \subseteq \sigma $ for all $ \sigma \in S $, we have either $ \epsilon = \sigma $ or $ \epsilon \in \sigma $. Suppose it is not the case that $ \epsilon = \sigma $ for any of the $ \sigma $. Then we have $ \epsilon \in \sigma $ for all of the $ \sigma \in S $. That means, by the definition of $ \epsilon $, that $ \epsilon \in \epsilon $, but we already showed earlier in this entry that no set is an element of itself. Therefore $ \epsilon = \sigma $ for some $ \sigma \in S $. $ \epsilon $ is the $ \in $-least element of $ S $.

This also shows that any two ordinals, $ \sigma$, $\tau$ , are comparable with $ \in $, just set $ S = \{ \sigma, \tau \} $. They are linearly ordered because each ordinal is linearly ordered, and smaller ordinals are elements of larger ordinals. This finishes the proof of part 1.

Proof of 2:

Suppose $ ON $ were a set. Then, since $ ON $ is well-ordered by $ \in $ and $ ON $ is transitive (which, again, follows from the linear ordering of $ ON $ by $ \in $), we would conclude that $ ON $ is itself an ordinal, and so we would have $ ON \in ON $, which we have shown cannot happen for any set.

QED

Corollary: Ordinals are subsets of each other

Let $ \alpha $ and $ \beta $ be ordinals, then at least one of the following must hold

$ \alpha \subseteq \beta $
$ \beta \subseteq \alpha $

Proof

First, if $ \alpha = \beta $, then both conditions hold.

The proceeding proof showed that if the two are distinct, then the set $ \{ \alpha, \beta \} $ has a $ \in $-least element which is equal to $ \beta \cap \alpha $. Therefore, either $ \alpha = \beta \cap \alpha $ or $ \beta = \alpha \cap \beta $. Since $ \alpha \cap \beta \subseteq \alpha $ and $ \alpha \cap \beta \subseteq \beta $, the result holds.

QED

Definition and Lemma: successor ordinal

Let $ \alpha $ be an ordinal, then

$$ \alpha + 1 := \alpha \cup \{ \alpha \} $$

is also an ordinal. It is the least ordinal greater than $ \alpha $.

Proof

First we show it is well-ordered by $ \in $. Let $ S \subseteq \alpha + 1 $ be non-empty. There are two cases to consider, either $ \{ \alpha \} = S $, in which case, $ \alpha $ is the $ \in $ least element of $S$, or $ S \cap \alpha = A $, where $A$ is non-empty. Then, since $ \alpha $ is well ordered by $\in$, it has a least element, $a$. Since $ a \in \alpha $, it doesn’t matter if $ \alpha \in S $ or not, $a$ is still the least element.

Also, by construction, every element of $ \alpha + 1 $ is either $ \in \alpha $ or is equal to $ \alpha $, so $ \in $ still orders every element of $ \alpha + 1 $. Thus $ \alpha + 1 $ is still well-ordered by $ \in $.

Next we show that $ \alpha + 1 $ is transitive. Let $ \delta \in \gamma \in \alpha + 1 $. Then, either $ \gamma \in \alpha $ or $ \gamma = \alpha $. In the first case, since $ \alpha $ is transitive, $ \delta \in \alpha $. In the second case, since $ \gamma = \alpha $, we have $ \delta \in \alpha $. In both cases, we’re fine, because by definition, $ \alpha \subsetneq \alpha + 1 $, so $ \delta \in \alpha + 1$. Thus $ \alpha + 1 $ is also an ordinal.

By definition, $ \alpha \in \alpha + 1 $, so it is clearly greater than $ \alpha $.

Finally, notice that there cannot be an ordinal $ \beta $, such that $ \alpha \in \beta \in \alpha + 1 $, this is because $ \alpha \in \beta $, and by this corollary from earlier in this entry we have, $ \alpha \subseteq \beta $. Combining those two facts, we have $ \alpha + 1 \subseteq \beta $.

Therefore, with mini lemma 2 we have either $ \alpha + 1 \in \beta $ or $ \alpha + 1 = \beta $.

QED

Definitions: sup, inf, max, min, upper bound, etc…

Let $(S, <)$ be an ordered set, and let $X$ be a subset of $S$. Then

an $s \in S$, such that for all $x \in X$, $x < s$ is called an upper bound of $X$.
an $s \in S$, such that for all $x \in X$, $ s < x$ is called a lower bound of $X$.
an $x \in X$, such that for all $y \in X$, we have $ y < x \vee y = x $ is called a maximum element of $X$.
an $ x \in X $, such that for all $y \in X$, we have $ x < y \vee y = x $ is called a minimum element of $X$.
an $s \in S$, such that $s $ is an upper bound for $X$, and for all $t \in S$, if $t$ is an upper bound for $X$, then $ s < t \vee s = t$ is called a least upper bound, or supremum of $X$.
an $s \in S$, such that $s $ is a lower bound for $X$, and for all $t \in S$, if $t$ is a lower bound for $X$, then $ t < s \vee s = t$ is called a greatest lower bound, or infimum of $X$.

Note: Just because we have given names to elements, like “maximum”, “supremum”, etc, doesn’t mean they are guaranteed to exist. We have to prove that they exist for various ordered sets. In fact, for some subsets of some ordered sets, some of these won’t exist.

For example. The subset $ [0, 1) \subsetneq \mathbb{Q}$ has no maximum, but it does have a minimum, a supremum, etc… We won’t prove this now, but we will later on, when we start covering basic real analysis.

Definition and Lemma: Limit Ordinal

Let $ S $ be a non-empty set of ordinals with no maximum, then there is an ordinal, $ \lambda $, such that $ \lambda $ is a supremum of $S$, and such a $ \lambda $ is called a limit ordinal.

Proof

We’ll prove that

$$ \begin{align} \lambda &= \bigcup S \\ &= \{ \delta | \exists \gamma, (\gamma \in S \wedge \delta \in \gamma) \} \\ \end{align} $$

is an ordinal, and that it is the least upper bound of $S$.

First, we show that $ \lambda $ is well-ordered. We showed in mini lemmas #3 that all of the elements inside ordinals are themselves ordinals. Thus $ \lambda $ is a subset of $ ON $ it is therefore well-ordered by $\in$.

Secondly, it is transitive. Consider

$$ \bigcup \bigcup S = \{ \epsilon \in \delta \in \gamma \in S \} $$

By the transitivity of each ordinal, $ \gamma $, we have $ \epsilon \in \gamma $, so

$$ \bigcup \bigcup S \subseteq \bigcup S $$

Thus $ \lambda = \bigcup S $ is transitive. Therefore, $ \lambda $ is an ordinal.

Now we prove that $ \lambda $ is an upper bound.

Let $ \sigma $ be an arbitrary element of $S$. Since $S$ has no maximum, there must be an element, $ \tau $ in $S$, such that $ \sigma \in \tau $. By definition, $ \tau \subseteq \bigcup S = \lambda $, so $ \sigma \in \lambda $. Thus $ \lambda $ is an upper bound for $S$.

Now we prove that $ \lambda $ is the least such upper bound.

Suppose that it is not the least, and that there is an ordinal $ \nu \in \lambda = \bigcup S $ that is an upper bound of $S$. By this corollary, we have $ \nu \subsetneq \bigcup S $, so there is a $ \rho \in \bigcup S \setminus \nu $. Notice also by mini lemma 2 that either $ \nu = \rho $ or $ \nu \in \rho $. However, neither of those possibilities is acceptable, as $ \rho $ is an element of an element of $S$. Thus $S$ contains an element which is strictly larger than $ \nu $.

Therefore, $ \lambda $ is the least upper bound of $S$.

QED

Corollary: Classification of Ordinals

Let $ \alpha $ be an ordinal. Then there are three possibilities:

$ \alpha = \emptyset $.
$ \alpha $ is a successor ordinal.
$ \alpha $ is a limit ordinal.

Proof

Consider the set

\[ S := \{ \beta \in \alpha \} \]

(never mind that $ S = \alpha $). Either:

$ S = \emptyset $
$ S $ has a maximum.
$ S $ does not have a maximum.

These three cases correspond to the three possibilities. It is now immediately clear that these possibilities are exhaustive.

QED

Notice, though, that we haven’t actually shown that limit ordinals exist. We’ve just shown that it’s possible that they exist. We would have to prove that there is a set of ordinals without a maximum. We can prove it, using the existence of an infinite set. We will do this later on in this entry.

Corollary: Sup always exists for ordinals

Let $ S $ be a set of ordinals. Then $ \sup(S) $ (i.e. the least upper bound for $S$) always exists.

Proof

There are three cases:

$S = \emptyset $
$ S $ has a maximum.
$ S $ does not have a maximum.

Case 1: $ \emptyset $ is an upper bound, and since it is the least ordinal, it has to be the least upper bound.

Case 2: let $ \mu = \max(S) $, then $ \mu + 1 $ is an upper bound, and we showed that it is the least ordinal greater than $ \mu $.

Case 3: This is handled by the Definition + Lemma involving limit ordinals.

QED

Definition: Order Type

Two ordered sets, $(S_1, <_1)$ and $ (S_2, <_2) $ have the same order type if and only if there exists a function, $ \phi : S_1 \rightarrow S_2 $ such that

$ \phi $ is 1 -1 and onto (i.e. a bijection)
$ x, y \in S_1 $ and $ x <_1 y $ if and only if $ \phi(x) <_2 \phi(y) $

This means that the two sets are isomorphic with regard to their orders. We will sometimes write

$$ \text{Type}(S_1, <_1) = \text{Type}(S_2, <_2) $$

Theorem: Order Type determines Ordinal

Let $ \alpha $ and $ \beta $ be ordinals. Then

$$ \begin{align} \text{Type}(\alpha, \in) &= \text{Type}(\beta, \in) \\ \implies \alpha &= \beta \\ \end{align} $$

Proof

Suppose for a contradiction that we have $ \alpha \in \beta $, but $ \text{Type}(\alpha, \in) = \text{Type}(\beta, \in) $.

This corollary earlier in this entry proved that if $ \alpha \in \beta $, then $ \alpha \subseteq \beta $. Since we are assuming they are not equal, we have $ \alpha \subsetneq \beta $. And, since we are also assuming that $ \text{Type}(\alpha, \in) = \text{Type}(\beta, \in) $, there must exist a function, $ \phi : \beta \rightarrow \alpha \subsetneq \beta $, such that $ \phi(\delta) \in \phi(\gamma) $ if and only if $ \delta \in \gamma $.

Notice that since $ \alpha \in \beta$, we have $ \phi(\alpha) \in \alpha $, which means that the set

$$ \Lambda := \{ \xi \in \beta | \phi(\xi) \in \xi \} $$

is non-empty. Since $ \beta $ is an ordinal, it is well-ordered (by definition), and so $ \Lambda $ must have a $ \in $-least element. Call that element $ \epsilon $. Notice that $ \eta = \phi(\epsilon) $ cannot be $ \in \eta $, otherwise $ \eta \in \Lambda $, but we know that $ \eta \in \epsilon $, and $ \epsilon $ is the $ \in $-least element of $ \Lambda $.

However, this is impossible, since $ \phi $ is an increasing function and $ \eta \in \epsilon $, and that would mean that we would have to have

$$ \begin{align} \eta \in &\phi(\eta) \vee \eta = \phi(\eta) \\ &\text{and} \\ &\phi(\eta) \in \phi(\epsilon) = \eta \\ \end{align} $$

QED

The next theorem says that the class of ordinals encompasses all of the possible well-order types.

Theorem: Every well-ordered set has order Type of an Ordinal

Let $ (S, <_w) $ be a well-ordered set. Then there exists an ordinal $ \alpha $, such that

$$ \text{Type}(S, <_w) = \text{Type}(\alpha, \in) $$

Proof

We’ll construct an order-preserving $ \phi: S \rightarrow \alpha $ recursively as

$$ \phi(s) := \sup(\{ \phi(t) | t <_w s \}) $$

Notice that $ \phi(a) \in \phi(b) $ if and only if $ a <_w b $. We also showed above that every set of ordinals has a supremum, so $ \phi $ must be defined for each element of $S$.

The Axiom Schema of Replacement guarantees that the range of $ \phi $ is a set (so, for example, it cannot be all of $ ON $). Furthermore, since it is an initial segment of $ON$, it is transitive and thus equal to an ordinal.

QED

Next we’ll introduce a powerful technique for building arbitrarily large sets (even classes) using induction! Because sets (and certainly classes) can be much larger than the set of natural numbers, we have to use the ordinals. Since they are a class, they can handle a lot.

Definition: Induction on Ordinals (transfinite induction)

Let $ \sigma(\alpha) $ be a formula such that

$ \sigma( \emptyset ) $ holds.
$ \sigma( \alpha + 1) $, holds whenever $ \sigma( \alpha ) $ holds.
$ \sigma( \lambda ) $, holds whenever $ \sigma( \beta ) $ holds for all $ \beta \in \lambda $ when $ \lambda $ is a limit ordinal.

Then $ \sigma( \alpha ) $ holds for all ordinals.

For a proof, (if you want one) just consider the smallest counter example. QED

Definition: Cardinal

Let $ \alpha $ be an ordinal, such that

$$ \begin{align} \exists f : &\beta \xrightarrow{\text{1-1, onto}} \alpha \\ \implies &\beta = \alpha \vee \alpha \in \beta \\ \end{align} $$

then $ \alpha $ is said to be a cardinal.

Definition: Cardinality of a Set

Let $S$ be a set, and let $\alpha$ be a cardinal, such that there exists a bijection (i.e. 1-1 onto function), $f : S \rightarrow \alpha $, then $ \alpha $ is said to be the cardinality of $S$.

This is often written “$ |S| = \alpha $”.

Mini-lemma: Same cardinality implies existence of bijection

Let $ S $ and $T$ be two sets with the same cardinality, $\alpha$, then there exists a bijection $ h : S \rightarrow T $.

Proof

$\displaystyle |S| = \alpha $ and $ \displaystyle |T| = \alpha $ implies that there are two bijections, $ f : S \rightarrow \alpha $ and $ g : T \rightarrow \alpha $, then consider the composition:

$ \displaystyle g^{-1} \circ f : S \rightarrow T $. It is a bijection from $S$ to $T$.

QED

Mini-Lemma: every Ordinal has a well-defined cardinality

Let $ \alpha $ be an ordinal, such that:

$ |\alpha| = \beta $
$ |\alpha| = \gamma $

then $ \beta = \gamma $

Proof

Without loss of generality, suppose, for a contradiction, that $ \gamma \in \beta $. Then we have two bijections:

$$ \begin{align} &f : \alpha \rightarrow \beta \\ &g : \alpha \rightarrow \gamma \\ \end{align} $$

which means that

\[ f \circ g^{-1} : \gamma \rightarrow \beta \]

is a bijection from $ \gamma $ to $ \beta $, and since bijections are onto, we have an onto function from a strictly smaller ordinal onto $ \beta $, thus $ \beta $ is not a cardinal. A contradiction.

We will also note that there is at least one candidate ordinal for the cardinality of a given ordinal. Let $ \alpha $ be an ordinal, then $ \text{id} : \alpha \rightarrow \alpha $, such that $ \text{id}(\beta) = \beta $, for all $ \beta \in \alpha $ is an onto function.

QED

Lemma: Every set can be well-ordered (Uses Axiom of Choice)

Let $S$ be a set, then there is an order, $ < $, such that $ (S, <) $ is a well-ordered set.

Proof

Let $S$ be an arbitrary set, and let

\[ \text{Ch} : P(S) \rightarrow S \]

be a choice function on $S$, whose existence is guaranteed by the Axiom of Choice. It is a function from the power set of $S$ to $S$.

We’ll well-order $S$ by using $\text{Ch}$ to map each element of $S$ to an ordinal as follows:

$$ \begin{align} s_{\emptyset} &:= \text{Ch}(S) \\ s_{\alpha} &:= \text{Ch}( S \setminus (\bigcup\limits_{\beta \in \alpha} \{ s_{\beta} \}) ) \\ \end{align} $$

where we use the second formula for all $ \alpha \ni \emptyset $. We stop when $ \displaystyle S \setminus (\bigcup\limits_{\beta \in \alpha} \{ s_{\beta} \}) = \emptyset $. What we end up with is a function, $ f : S \rightarrow ON $, where $ f(s_{\alpha}) = \alpha $. This function cannot map $S$ onto all of $ ON $, because then, by the Axiom Schema of Replacement, $ ON $ would be a set, and we’ve already shown that it can’t be a set (it is a class). Thus, the range of $f$ has to be an initial segment of $ON$, which will be equal to an ordinal. Let’s call that ordinal, $ \rho $.

Now we use our mapping to build a well-ordering as follows

\[ s_{\beta} < s_{\alpha} \Leftrightarrow \beta \in \alpha \]

By this construction, $f$ is clearly an increasing function from $(S, <)$ to $ (\rho, \in) $. Thus, $S$ has been well-ordered.

QED

Corollary: Every set has a cardinality

Let $S$ be a set, then $ |S| $ exists, and is well-defined.

Proof

By the proceeding lemma, $S$ can be well-ordered. That well-ordering provides an increasing function from $ S $ into an ordinal, $ \alpha $. That increasing function can be a bijection (as it is in the proof of the preceding lemma). That ordinal has a well-defined cardinality. That will be the cardinality of $S$.

QED

That’s all for this entry. Thanks for reading!!