Skip to main content
1 of 2
Mike Battaglia
  • 4.9k
  • 19
  • 44

Simplified method of building an Aronszajn tree

There is a very interesting method to build an Aronszajn tree in Judith Roitman's "Introduction to Modern Set Theory", on pages 100-102. In short, we build a tree $T$ in which the nodes are well-ordered subsets of $\Bbb Q$, partially ordered so that $\sigma_0 ≤ \sigma_1$ iff $\sigma_0$ is an initial segment of $\sigma_1$. Each such node $\sigma$, as a subset of $\Bbb Q$, has supremum $\sup \sigma$, and we require this be also in $\Bbb Q$. The top level is the empty set, and then the next is the set of all 1-element subsets, and so on, with a certain technique used at limit ordinals to make sure the tree is not too wide.

It seems that something much simpler than what she is doing will also suffice. The basic idea is:

  1. We start with top node the empty set.
  2. At level 1, we have one node for each rational number.
  3. For successor ordinal $\alpha+1$, we take all $\Bbb Q$-subsets that are nodes at $\alpha$ - and extend each in every possible way by adding one more rational at the end.

This is all her method so far without alteration. Of particular note is that, for any node $\sigma$ with supremum $\sup \sigma$, there will be nodes $n \in \Bbb N$ levels below with supremum $q + \sup \sigma$ for each possible $q > 0$. Suppose $\alpha$ is a limit ordinal. Instead of her method, we simply do this:

  1. For every node $\sigma$ previously created with some $\sup \sigma$, there will be uncountably many branches of height $\alpha$. For each $q>0$, arbitrarily choose one such branch so that its union $\tau \subset \Bbb Q$ has supremum $\sup \tau = q + \sup \sigma$, and add it as a node at level $\alpha$.

The idea is that we can't add all branches for each limit ordinal as nodes, or else we'd have uncountable width, so we choose countably many such that we "mimic" this "arbitrarily-shifted-supremum" property that we get at successor levels. Roitman's method also does this, but in a rather complex way - instead of choosing branches, she chooses cofinal $\omega$-sequences of children cofinal in some branch, and plans out the increases in suprema rather carefully within the branch.

However, either way, each level has countable width, no branch can have uncountable height, and each node would seem to have children arbitrarily far below in the tree. So, have we perhaps succeeded in creating an Aronszajn tree? If so, what would be the point of the extra complexity in Roitman's method?

Mike Battaglia
  • 4.9k
  • 19
  • 44