In an earlier blog post , on modelling arithmetic in set theory, we looked at modelling the natural numbers in set theory, using some of the basic axioms of set theory to get there. Interestingly, though, we can go the other way, and model set theory from within the natural numbers. Using some tricks with the binary expansions of natural numbers, we get what’s called the Ackermann interpretation of set theory, where the basic axioms of set theory come out true. Given that we only need these basic axioms to start talking about the natural numbers, this is quite a surprising result!
Here we’ll go through and see how exactly the Ackermann interpretation of set theory works, and why it makes the basic axioms of set theory (up to the axiom of infinity) work. We’ll then stretch the interpretation to the transfinite ordinals, using infinite binary expansions of infinite ordinals, and see what we can get out of that.
The Ackermann interpretation
Let’s first say how exactly we’ll be interpreting the natural numbers as sets. At first glance, it doesn’t look like any nice set-theoretic interpretations hold between the natural numbers—certainly not the membership relation—since we seem to only have the standard ordering relation $<$. It doesn’t seem like there’s any good way of getting out an interpretation of set theory just from a straight line of numbers.
It helps to remember how we can represent power sets as binary strings, though. If we have a sensible ordering over some collection of sets, then we can construct a binary string that denotes a set, where if the $i\th$ bit of the binary string is a $1$, then the $i\th$ element of our collection is an element of the set. Similarly, we can take a set ranging over our ordered collection, and construct a binary string that represents it.
We can state this more formally. Given a set $A$ with $k$ elements, calling those elements $a_1, a_2, a_3, \dots, a_k$, we can denote a subset of $A$ by a $k$-length binary string. We have the $i\th$ bit of the string equal to $1$ iff $a_i$ is in that subset. For instance, if our set $A$ is $\set{0,1,2,3,4,5}$, then the binary string $001101$ represents the subset $\set{2,3,5}$ (and note here that we read our binary strings from left to right). The binary string $111111$ just represents the set $A$ itself, and the binary string $000000$ represents the empty set.
We also know that binary strings represent numbers as well. We can represent the set $\set{2,3,5}$ above by the binary string $001101$, but we can also represent it by the number $44$, by converting the binary string into a decimal number (again, with the least significant bit to the left of the binary string).
Using these facts, we can interpret natural numbers as sets of natural numbers. We take a natural number $n$, look at its binary expansion $n_2$, and say that the natural number $m$ is a member of the set represented by $n_2$ iff the $m\th$ digit of $n_2$ is a one. For instance, the natural number $44$ has the binary expansion $001101$, and since the $2\nd$, $3\rd$ and $5\th$ bits of the binary expansion of $44$ are $1$s, it follows that the natural number $44$ represents the set of natural numbers $\set{2,3,5}$. If we wanted, we could then look at the binary expansions of $2$, $3$, and $5$, interpret them as sets, and ultimately describe the set denoted by the natural number $44$ in terms of just the empty set and sets containing the empty set.
Every natural number corresponds to exactly one binary string, and every binary string corresponds to exactly one set of natural numbers, and so we have a legitimate interpretation of natural numbers as sets of natural numbers. From this, using the set of natural numbers as our universe, and the relation described above as the set-membership relation, we get a model that looks like a model of set theory.
That’s the Ackermann interpretation of set theory! We interpret sets as natural numbers via the binary strings that represent those numbers. With that, we can start doing set theory on the natural numbers. Let’s see which axioms hold.
The axioms that follow
Let’s now see what axioms we can get out of the Ackermann interpretation.
Extensionality
The axiom of extensionality states that two sets are equal iff they have the same elements. Does the Ackermann interpretation satisfy the axiom of extensionality? Yes. If two sets are equal—recall that in the Ackermann interpretation sets are really elements of the natural numbers—then the numbers that represent those sets will be equal. But then the unique binary expansions of those numbers will be equal, and hence the two sets will have the same elements. Likewise, if two sets have the same elements then the binary strings that represent those sets will be equal. If that’s the case, then the numbers that represent those sets will be equal as well. So if two sets in the Ackermann interpretation have the same elements, then they’re equal. That gets us the axiom of Extensionality.
Empty Set
The empty set axiom states that there exists a set with no elements. The Ackermann interpretation satisfies this axiom as well; consider the natural number $0$ (here we assume that the natural numbers start from zero!). The binary expansion of $0$ is $0$, and since no digit of that binary expansion is a $1$, it follows that the set represented by $0$ contains no elements. Hence we have an empty set in the Ackermann interpretation.
If we’d starting counting the natural numbers from $1$ instead, we’d still get a set theory; it would just fail to satisfy the empty set axiom. In particular, the sets represented by $1$ and $2$ would both contain themselves and only themselves, and every set would have an infinite descending chain of membership relations. That then gives us an interesting set theory with what are called Quine atoms (namely sets that contain only themselves), but here we’ll focus on the usual set theory with an empty set, and so count our naturals starting from $0$.
Pair set
The pair set axiom states that, given two sets $x$ and $y$, there is a set whose elements are precisely the sets $x$ and $y$. In the Ackermann interpretation, given two sets $n$ and $m$, we can satisfy the pair set axiom by constructing a binary string whose $n\th$ and $m\th$ digits are $1$, and all other digits are $0$. Interpreting that as a set, we have a set whose only two elements are $n$ and $m$. So we’ve satisfied the pair set axiom.
Comprehension
The axiom of comprehension (strictly speaking, the axiom scheme of comprehension) states that, given some set $x$ and some first-order formula in the language of set theory $\phi$, there exists a set $y$ whose elements are precisely the elements of $x$ that satisfy the formula $\phi$ i.e. where $\phi(x)$ comes out true.
We can satisfy the comprehension axiom in the Ackermann interpretation by a neat fact about the sizes of sets. Since every natural number has a finitely long binary expansion (and let’s not worry too much about how we’ve defined "finite" here), it follows that every set in the Ackermann interpretation is finite. Since every such set is finite, it follows that every subset of an Ackermann set is finite as well. Since every finite set has a binary string that represents it, it follows that any subset of a given set $X$ where all members of that subset satisfy some formula $\phi$ must be represented by some finite set. So it follows that for every set $x$ and formula $\phi$ there does exist a set $y$ of precisely the sets in $x$ satisfying $\phi$.
Union
The union axiom states that, given some set $X$, there is a set $\bigcup X$ whose elements are precisely those of all the elements of elements of $X$. That’s a bit of a mouthful, but it might help to know that $\bigcup\set{x, y} = x \union y$. Formally speaking, we’re asking for a set $\bigcup X$ where some set $x$ is an element of $\bigcup X$ just when there exists some other set $y$ such that $x \in y$ and $y \in X$.
Does the Ackermann interpretation satisfy this axiom? Yes. Given a set $X$ represented as a binary string, we take every position in that string that is a $1$, take the binary expansion of each of those positions, and then take the logical disjunction over all those binary strings.
We can think of this as saying that the set $x$ is an element of $\bigcup X$ just when there exists some binary string $y$ where the $x\th$ bit of $y$ is a $1$, and the $y\th$ bit of $X$ is a $1$. That gets us the union set $\bigcup X$, as we wanted.
Powerset
The powerset axiom states that, given a set $X$, there is a set $\pow{X}$ whose elements are precisely the subsets of $X$. The Ackermann interpretation again satisfies this axiom; the key here is that every set has a finite number of elements (given that every natural number has only a finite number of digits in its binary expansion), and so there are only finitely many subsets of a given set. Hence, there are only finitely many digits that are $1$ in the powerset $\pow{X}$, and so there exists a well-formed binary string that represents the powerset of any given set.
Sequences (?)
As an aside, the sequence $\emptyset, \pow{\emptyset}, \pow{\pow{\emptyset}}, \dots$ has a particularly neat representation when read as a series of natural numbers. Recalling that we can expand the above sequence of powersets as
\[ \emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}}, \dots\]
we can then represent these sets by the binary strings
\[ 0, 1, 11, 1111, \dots \]
which already shows us an interesting pattern; writing these as natural numbers we get the sequence
\[ 0, 1, 3, 15, \dots \]
where the $n\th$ value of the sequence is equal to $2^{2^{n-1}} - 1$ (starting our counting from $1$). Alternatively, we can understand the elements of this sequence as the natural numbers whose binary expansion is the number $1$ repeated $k$ times, where $k$ is a power of two.
Similarly nice properties arise from the sequence of Zermelo numerals, which is the sequence of sets of the form
\[ \emptyset, \set{\emptyset}, \set{\set{\emptyset}}, \set{\set{\set{\emptyset}}}, \dots .\]
Writing those as binary strings, we get the sequence
\[ 0, 1, 01, 0001, \dots\]
which we can expand out into the sequence of natural numbers
\[ 0, 1, 2, 4, \dots .\]
So the sequence of Zermelo numerals, in the Ackermann interpretation, is represented by the sequence of powers of two. It’s nice when a natural sequence interpreted one way is a natural sequence interpreted another.
So properties of sequences of sets can be expressed in terms of properties of sequences of natural numbers, when interpreting sets under the Ackermann interpretation.
Infinity
Here we run into trouble. The axiom of infinity states that there exists an inductive set, or rather a set $X$ where $\emptyset$ is an element and, for each $x$ in $X$, the successor $x^+$ is an element. Recall that $x^+$ is standardly taken to be $x \cup \set{x}$ (though we can also use the Zermelo numerals here as well, and take $x^+ = \set{x}$), and so the axiom of infinity states that there exists a set with infinitely many elements (hence the name). There are no natural numbers whose binary representations are infinitely long, however, and so there can be no natural number that represents an inductive set. So the Ackermann interpretation doesn’t satisfy the axiom of infinity.
Still, we’ve got impressively far with a fairly simply interpretation of the natural numbers as sets, and given that we don’t need the axiom of infinity to do basic arithmetic and define arbitrarily good approximations of the natural numbers, we can just about define the natural numbers from inside the natural numbers. This is neat.
Extension to the transfinite ordinals
That all being said, we don’t have to stop at the axiom of infinity. If we stretch the Ackermann interpretation a bit, we can get an inductive set, and call it $\omega$. We represent the set $\omega$ by the binary string $1111\dots$. The binary string representing $\omega$ is infinitely long, and so has infinitely many members. In particular, for every element $x$ of $\omega$, the successor set $x^+$ is an element of $\omega$ as well. So we’ve satisfied the axiom of infinity by introducing the set $\omega$ represented by the infinite binary string $1111\dots$.
What we’ve done here is extend the Ackermann interpretation to the transfinite ordinals. The transfinite ordinals, put very basically, are what you get if you keep going with the natural numbers. If you ever played a game as a child where you tried to say the largest number, one person said ‘‘infinity!’’, and another said ‘‘infinity plus one!’’, then you started counting into the transfinite ordinals. There are plenty of good proper formal introductions to the transfinite ordinals—Goldrei’s textbook [1] is a good one (alongside an introduction to the whole of set theory)—so here I’ll avoid doing a more proper formal introduction.
We’ll now let sets be arbitrarily long infinite binary strings. We’ve already seen the set $\omega$, represented by the infinite binary string $1111\dots$. We also have the set $\omega + 1$, represented by the infinite binary string $1111\dots\ 1$. We continue adding digits to the right-hand side in the same manner as we did with the finite Ackermann sets. For instance, the set $1111\dots\ 101$ would contain every set represented by a natural number, as well as the sets represented by $\omega$ and $\omega + 2$.
This gets a bit confusing, as we know have to distinguish between the sets $\omega$ and $\omega + 2$, which are just objects in set theory, and the ordinals that represent sets $\omega$ and $\omega + 2$, which we take binary expansions of and then view as sets in our transfinite Ackermann theory. To illustrate this, the ordinal $\omega + 4$, when expanded into the infinite binary string $1111\dots 001$ and interpreted as a set, does not contain the ordinals $\omega + 1$ nor $\omega$. The set $\omega+4$, however, does contain the ordinals $\omega + 1$ and $\omega$; it’s an ordinal, so contains all ordinals smaller than it. This all gets confusing, and so from here on out I’ll assume that a given ordinal $\alpha$ denotes a set in the transfinite Ackermann interpretation, rather than is a set by itself.
Continuing on, we get larger and larger collections of infinite binary strings representing different ordinals. For instance, $\omega + \omega$ would be represented by the infinite binary string $1111\dots\ 1111\dots$. The analogy breaks down a little as you get bigger and bigger ordinals since it’s difficult to wrap your head around the binary string that represents the ordinal $\epsilon_0$, for instance. Here I’ll confess that I haven’t thought through the analogy in sufficient formal detail to be able to say whether or not we can adequately generalise the Ackermann interpretation to all ordinals, I’m afraid.
It’s fun to think about doing strange things with maths, though, so let’s think about doing strange things with maths.
Infinity, again
As mentioned above, we have an inductive set in the transfinite Ackermann interpretation. That set is the set represented by $\omega$, which contains all sets in the (finite) Ackermann interpretation. Since the successor of any finite set is finite, we know that the set represented by $\omega$ contains the empty set and all successors of the empty set. So the set represented by $\omega$ is inductive, and so the axiom of infinity is satisfied.
Replacement
The axiom of replacement (or, again, strictly the axiom scheme of replacement) says that for any set $X$ and class function $F$, there exists a set $F(X)$ that contains the image of $X$ under $F$.
Now, assuming that a class function is just a function from ordinals to ordinals, the transfinite Ackermann interpretation does satisfy Replacement. Given any set of ordinals $X$, we know there exists some infinite binary string where the $\alpha\th$ position of that string is a $1$ iff $\alpha$ is in $X$. Since the image of any set under a class function will be a set of ordinals, it follows that the image of any set under a class function can be represented as an infinite binary string, and so there exists some set in the transfinite Ackermann interpretation that is the image of $X$ under the given class function.
So we’ve satisfied the axiom of replacement in the transfinite Ackermann interpretation.
Foundation
The axiom of foundation states that, given any set $x$, there is some element $y$ of that set such that $x \intersect y = \emptyset$. More intuitively, the axiom of foundation says that all sets are well-founded; if you go down any chain of elements of the set, you’ll always eventually reach the empty set and then nothing else. Another way of putting the axiom of foundation is that it’s the axiom that there are no infinite descending $\epsilon$-chains. There are many ways of stating the axiom of foundation.
Does the transfinite Ackermann interpretation satisfy the axiom of foundation? It must. With some thought we can see that every set in the transfinite Ackermann interpretation must only contain sets strictly smaller than it (when interpreting the sets in the universe as ordinals), and so there can be no sets that contain themselves.
The only other way to violate the axiom of foundation in the transfinite Ackermann interpretation, then, would be to have an infinite descending $\epsilon$-chain. But there can be no such infinite descending $\epsilon$-chain over the ordinals; every chain of set-membership relations over the ordinals must be at most finitely long, and so we can have no infinite descending $\epsilon$-chain. So the axiom of foundation cannot be violated by any set in the transfinite Ackermann interpretation; so the transfinite Ackermann interpretation satsfies the axiom of foundation.
That’s admittedly a bit of an informal argument; recall the note about this not being an entirely formal section. But, given that binary strings are well-behaved objects, even when extended to be infinitely long, it’s at least plausible that the axiom of foundation is satisfied by the transfinite Ackermann interpretation of set theory.
Choice
The axiom of choice states that, given any set $x$, there is a choice set, call it $C$, such that for each element $y$ of $x$ we have $\size{y \intersect C} = 1$. The axiom of choice is, at least in standard set theory, equivalent to the well-ordering principle, which states that every set can be well-ordered (that is, given a set $x$, there exists a total linear order $\prec$ on the elements of $x$ where every subset of $x$ has a $\prec$-minimal element).
Assuming the equivalence between the axiom of choice and the well-ordering principle still holds in the transfinite Ackermann interpretation (which it does seem to), and perhaps stretching the definition of a well-order a little bit, the axiom of choice comes out true. Since every set in the transfinite Ackermann interpretation is represented by an ordinal, and since we have a well-ordering on the ordinals (that’s why they’re called the ordinals!), we have a well-ordering on sets in the transfinite Ackermann interpretation. Hence, the well-ordering principle and so the axiom of choice holds in the Ackermann interpretation.
This of course depends on whether or not you’re happy to induce a well-order on the sets of the transfinite Ackermann interpretation by bringing down a well-order from the universe of the model itself, and whether or not you’re happy to call that a well-order in the transfinite Ackermann interpretation as well. In any case, it doesn’t seem that the axiom of choice comes out false.
Conclusion
We’ve seen the Ackermann interpretation of set theory, where we interpret set theory out of a universe of natural numbers. We’ve then stretched that interpretation into the transfinite Ackermann interpretation of set theory, where we interpret set theory out of a universe of ordinals. Both interpretations give us a surprisingly rich theory, where we can construct something like the universe of the interpretation from within the interpretation itself.
All in all, it seems that the universes of the naturals and transfinite ordinals are rich, particularly when equipped with binary expansions of the elements of those universes. If you know how to look at something in the right way, you can see some very interesting things.
Bibliography
- [1] Derek C. Goldrei. Classical Set Theory: For guided independent study. 1996.