# Terry Tao's computational perspective on set theory

In one of his 2010 blog posts, A computational perspective on set theory, Terry Tao writes:

The standard modern foundation of mathematics is constructed using set theory. With these foundations, the mathematical universe of objects one studies contains not only the “primitive” mathematical objects such as numbers and points, but also sets of these objects, sets of sets of objects, and so forth. (In a pure set theory, the primitive objects would themselves be sets as well; this is useful for studying the foundations of mathematics, but for most mathematical purposes it is more convenient, and less conceptually confusing, to refrain from modeling primitive objects as sets.) One has to carefully impose a suitable collection of axioms on these sets, in order to avoid paradoxes such as Russell’s paradox; but with a standard axiom system such as Zermelo-Fraenkel-Choice (ZFC), all actual paradoxes that we know of are eliminated.

It appears that he is not using what he calls a "pure set theory" to construct the foundations of mathematics, because he is not modeling all primitive objects as sets. This would appear to disqualify ZFC, as it is typically presented as a one-sorted theory, even though he mentions ZFC by name as a way of eliminating known paradoxes, and works from the axioms of ZFC in the Set Theory section of his 2009 post, The “no self-defeating object” argument. I doubt a mathematician of his caliber would be content to work in a theory with axioms that are unclear, so I'm trying to pin down the details of his set theory. Is he working in a many-sorted version of ZFC, one that allows urelements? Or is he working in ZFC and saying that while at their core, all primitive objects are sets, we should try not to dwell on that and let it get in the way of studying them as we're used to?

• The original Zermelo's axiomatization has urelements. – Mauro ALLEGRANZA Jun 1 '16 at 19:45
• For TT's approach to set theory, you can see his Analysis I (2006): Ch.3 Set theory. – Mauro ALLEGRANZA Jun 1 '16 at 19:47
• @MauroALLEGRANZA Okay, I'll check it out. – justin Jun 1 '16 at 19:50
• It seems to me that he uses only natural numbers has objects that are not sets. – Mauro ALLEGRANZA Jun 1 '16 at 19:54
• @MauroALLEGRANZA Also functions; on page 66 he writes, "functions are not sets. However, we do consider functions to be a type of object." I'll keep going through the book. – justin Jun 2 '16 at 1:42

The simplest answer is that he is using certain objects such as natural numbers and functions via their abstracted properties (called interfaces in programming languages), instead of pinning down any specific objects that have those properties (called implementations in programming languages). The reason is that we usually care about the interfaces, and rarely about how exactly they are implemented.

Remember that usually mathematical objects do not come alone but as members of some structure, and the properties we want them to have is better understood as properties of the structure as a single whole. That also means that we are free to change the structure as long as it satisfies the same properties.

The typical example is the natural numbers. Almost all the time we only care about the properties that they have in relation to one another, like $0 < 1 < 2 < 3 < \cdots$, and induction over the natural numbers. These properties are all required to hold regardless of how the collection of natural numbers is actually formed. ZFC has many ways of exhibiting a model of PA, and in fact Zermelo's original construction of one of these models was different from the now standard von Neumann construction. The reason we use the latter now is one of the rare cases where we find that it is more convenient to have the natural numbers be a transitive set, so that they are von Neumann ordinals. There are technical advantages to that, because we can use the inbuilt symbol $\in$ for the ordering on ordinals. One can say that we like the structure of natural numbers to internally satisfy PA and externally be a substructure of the structure of ordinals, so there is special reason to privilege the von Neumann construction of natural numbers.

Another typical example is the real numbers. This time we never in practice care how they are constructed. As long as they satisfy the field properties and the second-order completeness axiom, that is good enough. One can say that we only need the structure of the reals to satisfy internal properties, and we don't care about any external properties. So whether use choose the Cauchy sequences of rationals or Dedekind cuts of the rationals or decimal sequences, it doesn't matter at all. The only point at which it matters is the when you want to construct the structure to show that there is some instance satisfying the desired properties, where in some weak systems some of these are not possible to construct. Thereafter we use real numbers only via their interface.

Similarly for functions. In ZFC they can be encoded as special kinds of subsets of the cartesian product of the domain and codomain, but in practice we don't care, and sometimes don't want that restriction, when dealing with class functions for example. You see, you think of the powerset symbol $\mathcal{P}$ as a function, don't you? But it can't be a set in ZFC unless you want a contradiction. Same for the cardinality map, and in general for any function-like thing whose domain or codomain is not a set. One could work in the strictly stronger MK set theory to avoid that issue, but the point remains that we don't really care how functions are implemented as long as we can use them the way we expect them to function.

To ensure that the mathematical structures one uses can be constructed in ZFC, one just has to make sure that either there is a set in ZFC that satisfies the desired interface (such as for natural numbers and reals), or there is a syntactic translation from one's proof to a proof in ZFC (such as proofs using class functions, which often but not always can be translated systematically into proofs that work in ZFC, simply by replacing the use of those functions by formulae), or that one is working in a conservative extension of ZFC (such as using full abbreviation power).

Tao's reference to pure set theory alludes to the construction of the natural numbers starting with the empty set. In von Neumann's version of it, we define $0=\varnothing$, $1=\{\varnothing\}$, $2=\{\varnothing,\{\varnothing\}\}$ and more generally $n+1=\{0,1,\ldots n\}$. One can proceed in this vein and define the rational numbers and the real numbers as certain types of sets. In this picture, numbers are not "primitive" as Tao says, or "atoms" for short. Then the von Neumann rank of $n$ is precisely $n$, the von Neumann rank of any infinite set of rational numbers is $\omega$ (the least infinite ordinal), and the von Neumann rank of a real number is $\omega+1$.

Practically speaking, in many branches of mathematics it is convenient to consider numbers as atoms and proceed from there.

For example, to build the superstructure (universe) over the set $\mathbb{R}$ one notices that every $x\in\mathbb{R}$ is an atom in the sense that $x\cap\mathbb{R}=\varnothing$ and moreover $x\cap V(\mathbb{R})=\varnothing$ where $V(\mathbb{R})$ is the universe over $\mathbb{R}$.

This point of view is helpful in building exotic extensions $V(\mathbb{R})\subseteq {}^{\ast}V(\mathbb{R})$ that Tao is very fond of; see e.g., this.

• You mean $n+1=n\cup\{n\}$. – Akiva Weinberger Jun 3 '16 at 16:52
• @AkivaWeinberger, that's equivalent to what I wrote. – Mikhail Katz Jun 5 '16 at 6:46
• No, it's not. $\{n,\{n\}\}$ has two elements and a rank of $n+2$ and contains $\{n\}$ as an element; $n\cup\{n\}$ has $n+1$ elements and a rank of $n+1$ and does not contain $\{n\}$ as an element. (But it's all a detail, anyway) – Akiva Weinberger Jun 5 '16 at 10:11
• @AkivaWeinberger, but $n+1$ is supposed to contain $n$ as an element. Furthermore, you are misreading the curly brace notation. Here $n$ contains each of the smaller numbers as an element. – Mikhail Katz Jun 5 '16 at 14:25
• It is supposed to contain $n$ as an element, but not $\{n\}$, is my point. Besides, you wrote that $1=\{\varnothing\}$, whereas if we had $n+1=\{n,\{n\}\}$ you would get $1=\{\varnothing,\{\varnothing\}\}$ by substituting in $n=0=\varnothing$. – Akiva Weinberger Jun 5 '16 at 15:20