New Foundations

It was around the beginning of my undergraduate studies when I became interested in foundations of mathematics in general and axiomatic set theory in particular. Shortly after, I started reading parts of Abraham Fraenkel’s brilliant book Einleitung in die Mengenlehre. I read the second edition of this book, which had originally been published in the 1920ies. In his book, Fraenkel first introduces set theory in a naïve way, then discusses certain paradoxes arising from the naïve treatment, and finally presents the axiomatic set theory developed by Ernst Zermelo and himself.

A few weeks ago, I stumbled across set theory again when Sergei Tupailo gave two talks at the Institute of Cybernetics on an alternative axiomatic set theory called New Foundations. The first talk was about a classical proof by Ernst Specker, the second one was about a contribution by Tupailo himself. Tupailo’s talks caused me to have a look at these “new foundations”, which were, in fact, completely new to me. In this blog post, I want to tell you a bit about this interesting topic. Let’s start with some background.

The problem with naïve set theory

Georg Cantor, the founder of set theory, stated informally what a set is. His definition from 1895 reads as follows:

Unter einer „Menge“ verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welche die „Elemente“ von M genannt werden) zu einem Ganzen.

Well, this is German, so I will give an approximate English translation:

With “set” we mean every aggregation M of certain distinct objects m of our perception or our thinking (which are called the “elements” of M) to a whole.

A problem with this definition is that it is too permissive. For example, there are sets that contain themselves as elements. An example is the set of all mathematical objects, which contains itself, because this set itself is a mathematical object.

Sets that contain themselves as elements might not be a problem as such. However, there must also be the set of all those sets that contain themselves as elements, which can be written {xxx} using set comprehension syntax. Let this set be called A. Is A an element of itself? Well, A contains all sets x for which x ∈ x holds, so A ∈ A if and only if A ∈ A. Hmm, this does not really tell us anything. So we have the strange phenomenon of a set comprehension whose result is not precisely defined.

It gets worse if we take the set of all sets that do not contain themselves as elements, that is, the set {xx ∉ x}, which we want to call B. Is B an element of itself? B contains all x for which x ∉ x holds, so B ∈ B if and only if B ∉ B. This is clearly contradictory. It is one of the classical paradoxes of naïve set theory, called Russell’s paradox, although it was first discovered by Ernst Zermelo.

Russell’s solution

Bertrand Russell solved this paradox by introducing a type system for sets. This led to his type theory (which is called “Typentheorie” in German, not “Typtheorie” like the modern type theories). Types in Russell’s approach can be seen as natural numbers. Type 0 is the type of all things that are not sets, which are the so-called urelements. All greater types are types of sets. Thereby, a set of a type n contains only elements whose types are less than n. As a result, the expression on the left side of a ∈ or ∉ must be of smaller type than the expression on the right. So the set comprehensions {xxx} and {xxx} are type-incorrect, and the problematic constructions described above are not possible.

Zermelo’s solution

Zermelo developed an axiomatic set theory which avoids Russell’s paradox without introducing types. His set theory later became the basis of Zermelo–Fraenkel set theory, which is the most widely used set theory today.

Zermelo’s key idea was to restrict the use of set comprehension. Unrestricted set comprehension allows us to construct arbitrary sets {x ∣ φ} where x is a variable and φ is a proposition that may mention x. Zermelo, on the other hand, allowed only comprehensions of the form {xxMφ}, where M is some set. These comprehensions are usually written {xMφ}. So in Zermelo’s theory, the expressions {xx ∈ x} and {xxx} are illegal.

Of course given some base set M, the set B′ = {xMxx} does exist in Zermelo’s set theory. What about self-membership in this case? We have

B′ ∈ B′ ↔ B′ ∈ MB′ ∉ B′ ,

which is equivalent to

B′ ∉ B′ ∧ B′ ∉ M .

So there is no contradiction, and we have B′ ∉ B′.

There are set theories, like the one by von Neumann, Bernays, and Gödel, where constructions like {xxx} are allowed. However, the results of such constructions are not sets, but so-called proper classes, which makes it possible to avoid Russell’s paradox and others. An interesting fact is that all proper classes are larger than sets in the sense of Zermelo. So Zermelo’s approach avoids Russell’s paradox by restricting the size of sets.

New Foundations

New Foundations is an axiomatic set theory developed by Willard Van Orman Quine. Its name stems from Quine’s 1937 publication New Foundations for Mathematical Logic. Quine also restricted the use of set comprehension, but in a way very different from Zermelo’s approach. His idea is rooted in Russell’s type theory. However, Quine did not assign types to sets, as Russell did, but to variables in a set comprehension. So there is only one type of sets, like in Zermelo’s theory, but set comprehensions have to be well-typed. The expressions {xxx} and {xxx} are disallowed, since they are ill-typed.

The difference to Russell’s theory becomes apparent, when looking at the expression {xx = x}. In Russell’s theory, there is a set {xx = x} for every type n, which consists of all things that have a type less than n. In Quine’s theory, {xx = x} is type correct and denotes the set of all things.

So New Foundations contains a universal set, which does neither exist in Russell’s type theory nor in Zermelo–Fraenkel set theory. On the other hand, New Foundations does not admit certain sets that exist in Zermelo–Fraenkel set theory. One example is the set of all von-Neumann-style natural numbers, although each finite set of such numbers exists in New Foundations. The moral of the story is that Quine’s theory does not reject certain sets because they would be too large, but because they would not be constructable in a type-correct way.

Urelements and the axiom of choice

In Zermelo–Fraenkel set theory and in New Foundations, sets are the only mathematical objects. So there are no urelements like in Russell’s type theory. Unfortunately, this poses a problem in the case of New Foundations in conjunction with the axiom of choice.

The axiom of choice says that given a set M of non-empty sets, there exists a set N and a one-to-one correspondence between the elements of M and N such that for each x ∈ M and the corresponding y ∈ N, y ∈ x holds. Plain Zermelo–Fraenkel set theory does not contain the axiom of choice, and it has been shown that neither it nor its negation can be deduced from the Zermelo–Fraenkel axioms. It is common to add the axiom of choice to Zermelo–Fraenkel set theory, since it can be quite useful.

Plain New Foundations also does not contain the axiom of choice. However, its negation follows from the New Foundations axioms, so that it cannot be added to New Foundations without making the theory inconsistent. This is what the first of Tupailo’s abovementioned talks was about. Ruling out the axiom of choice in the first place seems to be problematic. However, Ronald Jensen introduced a version of New Foundations with urelements, which does not seem to disprove the axiom of choice.

Further reading

If you got interested in New Foundations, I can recommend to you the book Elementary Set Theory with a Universal Set by Randall Holmes, which is available online free of charge. This book is an introduction to set theory based on New Foundations with urelements. So you can learn quite a lot from it about New Foundations without being a set theory expert. At the beginning of the book, Holmes justifies his decision to use New Foundations for an introductory book on set theory:

The reason that we believe that NFU [i.e., New Foundations with urelements] is a good vehicle for learning set theory is that it allows most of the natural constructions of genuinely “naive” set theory […]. The universe of sets is actually a Boolean algebra (there is a universe; sets have complements). Finite and infinite cardinal numbers can be defined as equivalence classes under equipotence, following the original ideas of Cantor and Frege. Ordinal numbers can be defined as equivalence classes of well-orderings under similarity. The objects which cause trouble in the paradoxes of Cantor and Burali-Forti (the cardinality of the universe and the order type of the ordinals) actually exist in NFU, but do not have quite the expected properties. Many interesting large classes are actually sets: the set of all groups, the set of all topological spaces, etc. (most categories of interest, actually). The reason that the paradoxes are avoided is a restriction on the axiom of comprehension.

I am currently in chapter 12, by the way.

About these ads

4 comments on “New Foundations

  1. mekeor says:

    wow! thank you very much for that concise summary of different set theories which i really needed to understand them… thank you for not writing extremly mathematical, too :)

  2. Ben Eastaugh says:

    ‘Russell’ has two Ls.

When replying to another comment, please press that comment’s “Reply” button first.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s