Infinity and Foundation

After the reviving effect of a week’s holiday, I have been thinking about Zermelo–Fraenkel set theory, inspired by a very nice student project I supervised (about which I hope to say something here sometime soonish). I have come across a couple of paradoxes. I believe I know the way round the first, but for the second I am unsure.

Warmup: Peano arithmetic

To begin, consider Peano arithmetic, the usual axiom system for the natural numbers. The basic ingredients are zero and the successor function: the axioms assert that zero has no predecessor but every other element has a unique predecessor (where “predecessor” means “inverse image under the successor function”). Order, addition and multiplication are functions of two variables defined by means of the successor function.

Of course, to a mathematician, the most important property of the natural numbers is that you can reach any number by starting at zero and applying the successor function repeatedly. Unfortunately, you can’t say this in first-order logic. So, instead, Peano requires that, for any property P expressed in the first-order language of the theory (with zero, successor, order, addition and multiplication as the non-logical symbols), if P(0) holds, and if P(n) implies P(n+1) for all n, then P(n) holds for all n.

Now the upward Löwenheim–Skolem theorem tells us that this first-order theory (assuming it is consistent) has unintended models; the axioms hold in structures of arbitrarily large cardinality. Moreover, the theorem of Engeler, Ryll-Nardzewski and Svenonius tells us that it even has unintended countable models. Can we say anything about these non-standard models?

Any such model contains “infinite integers”. One way to see how these arise is as follows. Adjoin a constant symbol c to the language, and add as axioms the sentences c > n for all natural numbers n (where, for example, 248 is the term in the language obtained by applying the successor function to zero 248 times). Now any finite subset of the new axioms is consistent with the Peano axioms (if c > n0 is the formula involving the largest natural number in the set, interpret c as any number greater than n0). So, by the Compactness Theorem of first-order logic, the entire set is consistent with the Peano axioms, and there is a model in which the element interpreting c is greater than every natural number.

The moral is that we can’t keep infinity out of mathematics (if we restrict ourselves to first-order logic).

The existential axioms of ZF

The following discussion takes place in Zermelo–Fraenkel set theory, with or without the Axiom of Choice (this makes a difference but not a serious one).

Raymond Smullyan asks, in one of his books, “Why is there something rather than nothing?” Most of the axioms of ZF are conditional, “If such-and-such sets exist, then some other set exists”. In the usual formulation, two axioms assert that something rather than nothing exists. The first, paradoxically, is the Empty Set axiom, asserting that there exists a set e such that, for all x, x is not a member of e. Note that, in the presence of the other axioms, this is equivalent to saying “There exists a set”. One way round, the implication is clear. In the other direction, if y is any set, then the set
{xy : xx} exists by the Selection Axiom, and clearly it is the empty set.

The other existential axiom is the Axiom of Infinity, which asserts that an infinite set exists, or, more or less, that the set of natural numbers exists. (As just explained, the Axiom of Infinity thus implies the Empty Set Axiom, but I will keep the latter for expository purposes.) This asserts that existence of a set S with two properties:

  • the empty set belongs to S;
  • if x is in S, then so is x∪{x}.

Then the intersection of all subsets of S satisfying these two properties is the natural numbers (in the von Neumann formulation).

Such a set is clearly infinite. But how do you prove that the existence of any infinite set implies the existence of a set with this property (without using the Axiom of Choice)?

Hereditarily finite set theory

If you don’t like the infinite, you might like to work in a set theory in which every set is finite; thus, given a set S, not only is S finite, but all elements of S are finite sets, all their elements are finite sets, and so on.

There is a very convenient model. I don’t know who invented this, but it is essentially the same as Richard Rado’s construction of the “random graph” (the unique countable homogeneous universal graph). The elements of the model are the natural numbers. The element x is a member of the element y if the xth digit in the base 2 expansion of y is 1 (that is, y is the sum of distinct power of 2, of which 2x is one).

This is nice, but as with Peano arithmetic, we get infinite surprises: the theory of this model has models which contain infinite sets. For let T be the set of first-order sentences satisfied by this model. Add a constant symbol c to the language, and sentences to say that c contains the first n elements of the model. (Each of these can be uniquely identified: for example, 5 = {0,{{0}}}, where 0 is the empty set.) As before, any finite set of these new axioms is consistent with T; so the entire set is consistent with T, and there exists a model of T containing a set which has as members all of the infinitely many elements of the model.

All this is not so surprising. The paradox comes from the fact that included in T is the negation of the Axiom of Infinity. So a model of a theory containing the negation of the Axiom of Infinity can contain infinite sets.

This suggests that the Axiom of Infinity is not really equivalent to the condition that there is an infinite set.

The Axiom of Foundation

The Axiom of Foundation has the job of forbidding infinite descending chains under the membership relation. However, it cannot be stated in this way by a first-order sentence, so a more ingenious method is required.

The standard formulation is that each non-empty set x has an element y such that xy is empty.

Suppose that there were an infinite descending chain

… ∈ x2 ∈ x1 ∈ x0.

Using the Axioms of Replacement and Choice, we can form a set S consisting just of elements xn satisfying these relations. But then this set fails the Axiom of Foundation; for, given any of its members, say xn, the element xn+1 is contained in both S and xn.

Note that the Axiom of Choice is used in this proof, since we have to choose one of the possible elements at each stage. The problem does not arise if the “infinite descending chain” is actually periodic. Indeed, since we may assume the Axiom of Choice here, this does not affect the paradox coming up.

A slight modification of the previous method provides us with the paradox. Adjoin infinitely many constants cn to the language, and all the formulae asserting that cn+1 is a member of cn. Any finite set of these formulae is consistent with ZFC, and again by compactness the whole collection is. But this asserts that an infinite descending chain exists, and so the Axiom of Foundation fails.

It may be that once we take the reduct which forgets the elements named by the constants cn, these elements no longer form a set of the model. But this shouldn’t matter if we have the Axiom of Choice to allow ourselves to choose elements with the right properties.

Can anyone give a better resolution?


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , . Bookmark the permalink.

5 Responses to Infinity and Foundation

  1. jbritnell2013 says:

    Is it always true that given an infinite descending chain we can form the set containing exactly those elements? It’s not clear to me how to do this using Choice and Replacement.

    The strong form of Foundation given by Mendelson is: There exists no function f with domain \omega such that f(\alpha^+) \in f(\alpha) for all $\alpha\in \omega$.

    So it seems that an infinite chain in a set X has to be understood as a function omega\rightarrow X. Your compactness argument gives the elements c_i, but I don’t see a way of constructing the function i\mapsto c_i from \omega.

  2. jbritnell2013 says:

    Sorry for the LaTeX errors—I don’t seem to be able to edit. (Also, I should have called Mendelson’s form of Foundation the “weak form”, not the “strong form”, since it only implies the usual version together with Choice.)

  3. Jon Awbrey says:

    We always encounter this multitude of problems whenever we rationalize mathematics by reducing it to logic, what’s more, of a purely deductive sort. A number of thinkers have suggested it is time — well past time — to stop counting so heavily on that idea and to join a Declaration of Independence for Mathematics.

  4. Pingback: ¿Shifting Paradigms? • 5 | Inquiry Into Inquiry

Leave a Reply

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

You are commenting using your 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