Krdytkyu

I read this question about infinite collections of infinite sets and it got me wondering what if we extended this to infinite collection of infinite collections of infinite sets. And so on. Can we keep going approaching infinity? If we label the first type of set by some order "order" like $2$ because it's a collection of collections and the word "collection" appears twice.

We can see an (edit: countably) infinite set as a sequence of elements indexed by some value from a countable set like ${x_i~:~iinBbb N}$. What can we say about the existence and countability of such sets with respect to the order?

In a good sense, the answer is yes - indeed, we can "get to infinity and keep going!"

We can't get to infinity in the most obvious way, at least in standard set theory, because the Axiom of Foundation rules out anything like $$ani bni cni ...$$ However, there is still a sense in which we can get "infinitely deep" sets. (I'm going to allow finite elements, for simplicity; I think what you're really interested in is "deep" sets, and these fit the bill.)

Consider the set $$I={{}, {{}}, {{{}}}, {{{{}}}}, ...}$$ It is a set of "mixed type" - it contains a set, a set containing a set, a set containing a set containing a set, ...

And we can keep going: $$J={I, {I}, {{I}}, {{{I}}}, ...}$$ And going: $$K={J, {J}, {{J}}, {{{J}}}, ...}$$ It's helpful at this point to think of sets as trees. E.g. the set $${{}, {{}}}$$ is a tree with

• 
  

  A root note (the outermost pair of curly braces) with two "children," child $1$ (= ${}$) and child $2$ $(={{}})$.

  
  
  
  
  

  • Child $1$ has no further children - it's a leaf.

  
  

  • Child $2$ has exactly one child, which is then a leaf.

  
  
  
  

So our tree looks sort of like an "L" (the root being the "corner" of the L). The more complicated sets $I,J,K,...$ described above are infinite trees, which you should try to draw (at least $I$); their key features are that nodes can "branch" infinitely often (this happens whenever the node in question has infinitely many elements) but there are no actual infinite branches (that is, we don't get $ani bni cni ...$ ad infinitum).

There is a useful tool for describing such sets, or trees: rank. The rank of a set is an ordinal - possibly infinite - and is defined recursively as follows:

The rank of $A$ is the smallest ordinal $alpha$ such that every element of $A$ has rank $<alpha$.

For example:

• What's the rank of ${}$? Well, ${}$ has no elements at all, so every ordinal $alpha$ has the property "all elements of ${}$ have rank $<alpha$" vacuously. So the rank of ${}$ is just the smallest ordinal, which is $0$.




• What's the rank of ${{}}$? Well, it has one element, of rank $0$; so its rank is the least ordinal $>0$, namely $1$.




• What's the rank of ${{{}}}$? Well, you should be able to guess that it's $2$; can you prove it?




• Now a fun one - what's the rank of the set $I$ above? Well, each element of $I$ has finite rank, but the ranks of the elements of $I$ are arbitrarily large finite numbers. So the rank of $I$ is the smallest infinite ordinal - namely, $omega$.




• Similarly, ${I}$ has rank $omega+1$, ${{I}}$ has rank $omega+2$, and so on.




• What about $J$? Well, its elements have ranks $omega,omega+1,omega+2,omega+3,...$, so its rank is $omega+omega$.




• And $K$ - unsurprsingly - has rank $omega+omega+omega$.

Exercise: can you cook up a set with rank $omega^2$?

Indeed, it turns out that the situation is "as rich as possible:"

For every ordinal $alpha$, there is a set of rank $alpha$.

Conversely:

Every set has a rank.

This last observation actually says a bit more: there is a way of "building up" the entire set-theoretic universe by "going up in rank" - namely, the cumulative hierarchy. It also lets us prove theorems about sets by transfinite induction (on their ranks).