We begin with Aronszajn trees where the rational numbers really shine. Then we get a chance to see Hausdorff gaps, and experience eventual domination. We will see the definitions of filters and ideals, and finally, cofinality.
A map of the topics in CHAPTER 1 INFINITY: PART 2
ARONSZAJN TREES
Before we get to Aronszajn trees aka Erinshine trees (ok it is not spelled like that but that’s how it is pronounced) let us code the natural numbers with colors. We can think of the cardinality of the visible color spectrum from violet to red as the cardinality of the interval [0, 1] aka the cardinality of the continuum (each color corresponds with a wavelength and even if our eyes cannot distinguish between two very similar colors we can look at their wavelength to see the difference).
Here is a proposal for how to have a countable arrangement of colors, using the 7 main colors and black and white.
We start with the 7 main colors, followed by the 7 main colors with one white zip (we pay homage to Barnett Newman here; his work is too young for the public domain so it is not included here), then the 7 main colors mixed with one black zip, then the 7 main colors mixed with 2 white zips, then the 7 main colors mixed with 2 black zips and so on forever.
This ordering is a linear ordering.
A strict partial ordering is a binary relation < on a set C with the transitivity property:
\(\mbox{ if $\ a < b \ $ and $\ b < c \ $ then $\ a < c$}\)
and where for any a in C
\(a \nless a.\)
A partial ordering is linear
\(\mbox{ if for any } p, q \in C, \mbox{ either $\ p < q$, $\ p = q$, or $\ p > q$.}\)
There is more than one definition of tree in set theory. In this section a tree is a partially ordered set
\((T,<)\)
where for each
\(x \in T\)
the set of all predecessors of
\(x,\)
\(\{y \ : \ y < x \}\)
is well-ordered (linear order where every nonempty subset has a least element) by <.
We have seen the infinite binary tree, with uncountably many infinite paths. Let us construct another tree of height ꙍ where every level is finite. Every well-ordered set is isomorphic to an ordinal, so every
\(x \in T\)
has a set of predecessors which has an order-type, an ordinal that it is isomorphic to, and this is the rank or order of the node
\(o(x) = \mbox{ the order-type of } \{ y : y < x \}.\)
Then we can define the levels of the tree, indexed by ordinals
\(\mbox{height}(T) = \mbox{ sup}\{o(x) + 1 : x \in T \}.\)
The infinite binary tree has height ꙍ since every node has a finite order and their orders are unbounded, so that the supremum is ꙍ.
The height of a tree is the least ordinal such that the tree is empty at that level.
A branch in a tree is a linearly ordered subset of the tree that is not contained in any other linearly ordered subset (maximal chain). The length of a branch is the order-type of the branch. For example, we saw there are uncountably many ꙍ-branches in the infinite binary tree.
We will construct another infinite tree with finite levels. Will it have an infinite branch? Let us use the natural numbers coded by the colors to make the tree. This choice is getting us ready for later where the branches of an Aronszajn tree will be sequences of rational numbers. Let T be a tree where the root of the tree is any color in C, the countable set of colors:
Level 0:
For the first level, choose children of the root to be any colors that are greater than the root.
Level 1:
Since we want to create an infinite tree, we should continue. Not every node needs to have children, but at least one does. For the nodes that do have extensions, let us continue to always choose greater colors so that our branches are increasing sequences of colors from the countable color set C.
Level 2:
Since we are making an infinite tree, we must continue. At least one node on the 2nd level must have an extention, and at least one of these nodes must have an extension, and one of these nodes must have an extension and so on.
Let us see that this tree has an infinite branch. To construct an infinite branch, start with the root
Then choose a successor of the root which does not lead to a dead end, that is a successor that has infintely many successors (if there is no such node the tree is finite). That is, on the 1st level choose a node
\(x_1 \mbox{ such that } \{ y \in T : y > x_1 \} \mbox{ is infinite.}\)
On the 2nd level choose a successor
\(x_2 \mbox{ such that } \{y \in T : y > x_2\} \mbox{ is infinite.} \)
At the nth level choose a successor which has infinitely many successors and so on.
No matter the construction, an infinite tree with finite levels will have an infinite branch. This is König’s Lemma:
\(\mbox{ If $T$ is a tree of height $\omega$ }\)
\(\mbox{ such that every level of $T$ has finitely many nodes,}\)
\(\mbox{ then $T$ has an $\omega$-branch.}\)
We might wonder:
\(\mbox{ If $T$ is a tree of height $\omega_1$}\)
\(\mbox{ such that every level of $T$ has countably many nodes, }\)
\(\mbox{must $T$ have an $\omega_1$-branch?}\)
The answer is no because an Aronszajn tree is a tree of height ꙍ₁, with countable levels, which has no ꙍ₁-branch.
And we can construct an Aronszajn tree.
The idea in the construction of an Aronszajn tree is that we label the nodes with rational numbers so that each branch is an increasing sequence of rational numbers and thus no branch can be uncountable.
Let us use our color scale.
Then the rational number 3/5 is represented by
and since there are equivalent fractions to 3/5 such as 6/10, there are multiple ways to represent one rational number.
Let us see that the rational numbers are countable by finding a countable list of the rational numbers. The figures below illustrate that the positive rationals are countable, and similarly the entire set of rationals is countable. We are over-counting since we will count each equivalent fraction, but even with over-counting the result is still countable.
If we go down any row or column we might not come back, so we work the finite diagonals to make a path which encounters every rational.
Thus the set of rational numbers is countable. Therefore, when we construct an Aronszajn tree where the branches are increasing sequences of rational numbers we cannot have an uncountable branch.
An Aronszajn tree is a tree of height ꙍ₁ which has countable levels and no uncountable branch.
Constructing an Aronszajn Tree:
Let the 0th level of the tree be
\(U_0 = \{\emptyset\}.\)
For the 1st level, extend by all positive rational numbers (it is ok if we are using multiple representations of each reduced fraction).
\(U_1 = \{ (\emptyset, r) : r \in \mathbb{Q}^+ \}.\)
For the 2nd level, extend each
\(x \in U_1\)
by all rationals greater than it, so that the 2nd level the collection of sequences
\(U_2 = \{ x^{\smallfrown}r : x \in U_1, \ r \in \mathbb{Q^+}, \ r > x \}.\)
For the 3rd level of the tree, extend each
\(x \in U_2\)
by all rationals greater than it, so that the 3rd level is the collection of sequences
\(U_3 = \{ x^{\smallfrown}r : x \in U_2, \ r \in \mathbb{Q^+}, \ r > x \}.\)
The tree might look finite, but below each node are infinitely many nodes. We define the levels of the Aronszajn tree by transfinite induction (transfinite induction is like induction on the natural numbers, but it is on the ordinals and so we must also consider limit stages). Let’s continue the construction of the finite levels. Given level Uₙ, let
\(U_{n+1} = \{ x^{\smallfrown}r : x \in U_n, \ r \in \mathbb{Q^+}, \ r > x\}\)
be all of the rational extensions of every node in Uₙ.
If
\(U_n \mbox{ is countable then } U_{n+1} \mbox{ is countable}\)
since each node in Uₙ has countably many rational extensions since the rationals are countable.
Also, each level Uₙ constructed so far has the property that
\(\mbox{for every $k < n$, and every $x \in U_{k}$, and every $r > \sup x$}\)
\(\mbox{there is a $y \in U_n$ such that $x \subset y$ and $r \ge \sup y$}.\)
So far our nodes are finite sequences, but at later stages we will have to think about supremums of infinite sequences of rational numbers.
For example let n = 4, and consider our node 1/2 on the 1st level of the tree.
Take any rational number greater than 1/2 such as 1. The midpoint between these two numbers is 3/4, and we can continue in this way to make a sequence of any length that will still be below 1. Suppose we want to make a sequence of length 5:
Then in the tree, y is an extension of x on the 4th level.
It is like the q > sup x is a carrot leading us to create a sequence of any length to get an extension of x at any level above x. This property holds because of the density of the rationals and because we are taking every possible extension at every successor level.
So far we have built all of the finite levels of the Aronszajn tree, and they are all countable, and we have the carrot-leading-us-to-create-an-extension-at-any-level property between them, which we can prove by induction.
We are at the crucial moment where we construct
\(U_{\omega}\)
the first infinite level of the tree.
The tree
\(T_{\omega}\)
that we have built so far has continuum many paths, and so we cannot extend every branch to the ꙍth level. While there are uncountably many paths in
\(T_{\omega}\)
there are countably many nodes and we will choose for each node only countably many extensions to the ꙍth level. Countably many nodes times countably many extensions is still countable, so if we can do this we can construct the first infinite level of the Aronszajn tree.
For each
\(x \in T_{\omega}\)
and every
\(r > x\)
choose an ꙍ-sequence y of rationals that contains x and whose supremum is less than or equal to r using the density of the rationals.
For each node, and each rational number greater than the sup of the node, choose one y. Then let the ꙍth level be the countable collection of these y. For each path we want to extend to the ꙍth level, we need to put a rational on the ꙍth level. In the image, we just use the rational which guided us. The rank of a node is the order-type of its predecessors, so until we actually put a node on the ꙍth level, it is empty.
Then for the next level we take all rational extensions of nodes on the ꙍth level:
\(U_{\omega + 1} = \{ x^{\smallfrown}r : \ x \in U_{\omega}, \ r > x \}.\)
Given any
\(\alpha < \omega_1\)
if
\(U_{\alpha}\)
has been constructed, let
\(U_{\alpha + 1} = \{x^{\smallfrown}r : \ x \in U_{\alpha}, \ r > x\}.\)
Then if
\(U_{\alpha}\)
has the carrot-leading-us property, so does
\(U_{\alpha + 1}.\)
And if the 𝛼th level is countable so is the (𝛼 + 1)st level. We can prove these with transfinite induction, and we will know the limit levels will hold by construction below.
If α is a limit ordinal, where the levels below have been constructed, we want to construct the 𝛼th level so that the property holds and it is countable. Let
\(x \in T_{\alpha}\)
then since α is is countable there is a sequence
\(\{ \alpha_{n} \}_{n = 0}^{\infty}\)
where
\(x \in U_{\alpha_0}\)
such that
\(\lim_{n \to \infty} \alpha_n = \alpha.\)
Then for each r > x there is
\(y_n \in U_{\alpha_n}\)
such that
\(x \subset y_n \mbox{ and } \sup y < r\)
Let
\(y = \bigcup_{n \in \omega} y_n\)
and let
\(U_{\alpha} \mbox{ be the collection of all such $y$ for each $x \in T_{\alpha}$}.\)
At successor stages, take every possible rational extension. At limit levels, for each node already constructed and for each rational greater than it, choose a path to the next limit stage.
Finally, the Aronszajn tree is the union of all the levels created:
\( T = \bigcup_{\alpha < \omega_1} U_{\alpha}.\)
Each level will be countable, but there can be no uncountable branch because there is no uncountable sequence of increasing rational numbers.
Big idea: we lay down tracks for every possible route at successor steps so that for each node we can choose countably many paths to extend to the limit when we get there. In the end we get a tree of uncountable height with countable levels and no uncountable branch. ◼
There is a large cardinal property inspired by König’s Lemma and Aronsjazn trees called the tree property. A cardinal 𝜅 has the tree property if any tree of height 𝜅 with levels of size less than 𝜅 has a 𝜅-branch. We have seen that ꙍ has the tree property, while ꙍ₁ does not have the tree property.
HAUSDORFF GAPS
After all this yard work, let’s go inside and draw the curtains. Hausdorff gaps are gaps in
\(\omega^{\omega}\)
which is the set of functions
\(f: \omega \to \omega.\)
That is, the set of ꙍ-sequences of natural numbers. For example, here are two such functions. The first is the constant sequence (4, 4, 4, . . . ) and the second is the sequence of even numbers (0, 2, 4, 6, . . . ).
If you had to say which was greater, is it f or g? We could say g is greater because eventually f(n) < g(n).
This is the partial order on ꙍ-sequences of natural numbers, known as eventual domination.
\(\mbox{For $f, \ g \in \omega^{\omega}$}\)
\(f < g \mbox{ if and only if } f(n) < g(n) \mbox{ for all but finitely many } n. \)
Some such functions are incomparable.
Below is an increasing sequence of functions in
\(\omega^{\omega}\)
of length ꙍ.
And here is a decreasing sequence of functions in
\(\omega^{\omega}\)
of length ꙍ. The first element of the sequence is the function furthest to the right.
Below are both families of functions together. Every function in the decreasing family eventually dominates every function in the increasing family.
The question is: can we find
\(h : \omega \to \omega\)
such that h fits between the increasing family of functions and the decreasing family of functions? How could we do it?
In this example, both families of functions are intended to be of size ꙍ.
If both families are size ꙍ, then we can always find a function h between the increasing family and the decreasing family. That is,
\(\mbox{there are no $(\omega, \omega)$-gaps in $\omega^{\omega}$.}\)
An (𝛼,β)-gap is two families, one an increasing family of size 𝛼, the other a decreasing family of size β, where the increasing family is below the decreasing family, and where there is no
\(h: \omega \to \omega\)
that fits between the families.
Though there are no (ꙍ,ꙍ)-gaps, if we increase the size of the families to ꙍ₁ we can construct two families such that one can never find an h that fits between them. Hausdorff showed
\(\mbox{ there are $(\omega_1, \omega_1)$-gaps in $\omega^{\omega}$.} \)
FILTERS AND IDEALS
On each row below is the set of positive natural numbers (or think of any infinite set A) and the highlighted elements represent a subset. This represents the ideal of all finite subsets.
The collection of all finite subsets of an infinite set A is an ideal I because
1)
\(\emptyset \in I\)
2)
\(\mbox{ if } X, Y \in I \mbox{ then } X \cup Y \in I\)
3)
\(\mbox{ if } X \in I \mbox{ and } S \subset X \mbox{ then } S \in I.\)
The empty set is a finite set. The union of two finite sets is a finite set. And, a subset of a finite set is a finite set.
An ideal on a set captures the sets that are small. The intersection of two small sets is small because it is a subset of both sets. Condition 2 says that you can’t get into the big sets by taking finite unions of small sets.
The dual notion of an ideal is a filter. Represented below is the filter on an infinite set A which includes sets whose complement (in A) is finite, aka the co-finite subsets.
The collection of all co-finite subsets of an infinite set A is a filter F because
1)
\(A \in F\)
2)
\(\mbox{ if } X, Y \in F \mbox{ then } X \cap Y \in F\)
3)
\(\mbox{ if } X \in F \mbox{ and } X \subset Y \mbox{ then } Y \in F.\)
An infinite set is a co-finite subset of itself. The intersection of two co-finite subsets of an infinite set is a co-finite set. And, a superset of any co-finite set is a co-finite set.
A filter on a set captures the sets that are big. The union of two big sets is big because it is a superset of either set. Condition 2 says that you can’t fall into the small sets by taking finite intersections of big sets.
If I is an ideal on a set A, then
\( F = \{X \subset A : X \notin I \}\)
is a filter on A.
An ultrafilter U on a set A has the property that for every subset X of A, either
\( X \in U \mbox{ or } X \notin U.\)
A filter P on a set A is principal if there is a nonempty subset E of A such that
\( P = \{ X \subset A : E \subset X \}.\)
We might wonder if there is a nonprincipal ultrafilter where condition 2 holds for infinite intersections? These kinds of questions will lead us to large cardinals.
In the future, we will see filters defined on partial orders in the context of forcing.
COFINALITY
There once was an office located on the
\(\aleph_{\omega}\mbox{th}\)
floor of a building.
And every day, everyone took the regular way, up an
\(\aleph_{\omega}\)
sequence of steps. Everyone loved the job, but the commute was a common complaint. Until one day, when one worker made a ladder, an ꙍ-sequence of steps, a shortcut to the office.
Since there is an ꙍ-sequence of ordinals whose limit is
\(\aleph_{\omega},\)
the cofinality of
\(\aleph_{\omega}\)
is ꙍ,
\(cf(\aleph_{\omega}) = \omega.\)
If 𝛼 is a limit ordinal, the cofinality of 𝛼 is the least β such that there is a β-sequence which converges to 𝛼.
An infinite cardinal 𝜅 is regular if the cofinality of 𝜅 is 𝜅. For example, ꙍ is a regular cardinal. If a cardinal is not regular, it is singular. For example,
\(\aleph_{\omega}\)
is singular.
For offices on regular floors, there is no shortcut ladder, there is only the regular way.
We said in Part 1 that an inaccessible cardinal shares key properties with ꙍ. Being a regular cardinal is one of these key properties.
A cardinal 𝜅 is weakly inaccessible if it is an uncountable regular limit cardinal.
A cardinal 𝜅 is inaccessible if it is an uncountable regular strong limit cardinal. A strong limit means that 𝜅 is greater than the power set of any set below it.
Workers on their way to the upper offices have a lot of time to think, and start to ask themselves questions. How do we really know that we exist and all these offices exist? Do inaccessible cardinals exist? What does it really mean for an Aronszajn tree to exist? What assumptions are made in the construction? What is a set? Is there a place where CH holds?
Great images! Incredible!