Iterating a Concept of Sets – Part II

By Brandon Mitchell

Picking up where we left off in part one, we’ve come to the conclusion that the naïve conception, borne of the idea that the universe of sets can be defined by simply stating for any predicate that there is a set of things which do and a set of things which do not satisfy that predicate, is not a viable starting point for a theory of sets.

We arrived at this conclusion, in part, because of the Russell set (∃y(Sy ˄ ∀x(x ∈ y ↔ x ∉ x))) and the contradiction which it produces and in part because of the confusing or inelegant nature of set self-membership.

So we are left with a question as to how we are going to define and limit a universe/s of sets.

Boolos thinks it important to consider the best alternative to the naïve theory as one which achieves maximum elegance and is not developed with a consciousness of the Russell set.

To achieve these virtues, he turns to what we’ll call the ‘iterative conception’, attributed to Ernst Zermelo and Abraham Fraenkel, both German logicians of the late 19th and early 20th centuries.

Broadly, the iterative conception begins with a collection of individuals which are not sets. At the first stage, it forms every possible collection (set) of those individuals. It then proceeds to subsequent stages, and repeating this process it forms every possible collection of those sets and individuals which appear at previous stages.

Though it may sound complex, the idea is instead very intuitive.

Let’s give an example.

Begin with some (non set) individuals. We could call them a and b. Then at the beginning stage, form all possible collections of the individuals. In this case {a}, {b} and {a,b} along with the collection of no individuals (being a possible collection of individuals), the null set. I’ll denote the null set with {0}. At the subsequent stage, form all possible collections of items (sets or non-sets) which appear at previous stages.

Note that stage 2 contains every possible collection of the things which appear at stage 1. Similarly, when the process moves to stage three, that stage contains every possible collection of things which appear at earlier stages. This will include collections of sets whose members are only those who first appeared at stage 1. Here we introduce the concept of ‘forming’. A set is ‘formed’ at stage three iff it does not appear at any preceding stage.

Iterative Theory 2

And so, taking this tack, that of creating a universe of collections based upon a definite group of fundamental objects, yields the iterative conception of sets. The conception can be put forward in a series of axioms which can in turn, along with extensionality, be used to ground the Zermelo axioms of pairing, union, power set and infinity.

Axioms of the Iterative Conception

For the axioms, we establish a binary relation ‘earlier than’ (aEb: a is earlier than b) for stages and a binary relation ‘formed at’ (aFb: a is formed at b) for sets and a unary relation ‘is a stage’ (Sx: x is a stage).

The axioms are:

  1. ∀x(Sx → ¬(xEx)) – No stage is earlier than itself, i.e. stage 1 is not earlier than stage 1, etc. This axiom is defining a property of the ‘earlier than’ relation.
  2. ∀x ∀y ∀z(Sx ∧ Sy ∧ Sz → ((xEy ∧ yEz) → xEz)) – ‘Earlier than’ is transitive. Stage 2 is earlier than stage 3. Stage 1 is earlier than stage 2 so stage 1 is earlier than stage 3.
  3. ∀x ∀y(Sx ∧ Sy→(xEy ∨ x=y ∨ yEx)) – Earlier than is connected; that is every stage stands in some relation to every other stage, i.e. either stage 3 is earlier than stage 1 or stage 3 equals stage 1 or stage 1 is earlier than stage 3.
  4. ∃x∀y(Sx ∧ ¬(x=y)→(xEy))– There is an earliest stage. In the example, stage 1 was that stage.
  5. ∀x∃y((Sx ∧ Sy) → (xEy ∧ ∀z(zEy → (zEx ∨ z=x)))) – Every stage has an immediate successor, i.e. stage 2 in the example followed immediately after stage 1 etc.
  6. ∃x(Sx ∧ ∃y(Sy ∧ yEx ∧ ∀z(Sz → (yEz → ∃a(Sa ∧ zEa ∧ aEx))))) – There is a stage. Let’s call it  X and there is another stage, let’s call it Y, earlier than X. To say it again, there are two stages, X and Y and Y is earlier than X. For any other stage Z if Z is later than Y, there is another stage A and A is later than Z and earlier than X. This is to say that there is a stage, not the earliest one, that is not immediately after any given stage.
  7. ∀x ∃s(Ss ∧ xFs ∧ ∀t(xFt → t=s)) – Every set is formed at some unique stage
  8. ∀x ∀y ∀s ∀t (Ss ∧ St ∧ xFs ∧ yFt y ∈x) → tEs)) – Every member of a given set was formed at an earlier stage than that set
  9. Where s, t and r are stages, ∀x∀s∀t(xFs ∧ tEs → ∃y∃r (y∈x ∧ yFr ∧ (t=r ∨ tEr))) – For any set and any two stages if the set was formed at a stage s and the other stage t is earlier than s then there is a y that is a member of x. Y was formed at stage r and r either is t or is after t. Every set formed at a given stage has at least one member which was formed at the immediately previous stage.
  10. This is a variation of the axiom schema of separation adapted to the iterative conception. Boolos calls them ‘specification axioms.’ They are of the form

∀x(Sx → ∃y∀z(z∈y ↔(Z ∧ ∃t(tEx ∧ zFt)))), saying that at any given stage there is a set of just those sets of which X is true and which were formed before a given stage. This is true for all formulas X. So if stage 1, as in the diagram, holds every possible collection of sets formed at stage 0, then stage 2 could only introduce new collections in-so-far as they contain sets formed at stage 1.

So how do we arrive at the Zermelo axioms from the characteristics of the iterative conception? In this article, we’ll discuss the Null Set and the Pairing Axiom. In the next article, we’ll pick up Union, the Power Set and Infinity.

Null Set

Take x=x in the specification axiom making, ∀x(Sx → ∃y∀z(z∈y ↔(z=z ∧ ∃t(tEx ∧ zFt)))). At every stage there is a set of all sets formed prior to that stage. Since this holds for all stages, it holds for Stage 0 before which there were no sets formed. So there is a set of no sets or the null set.

It was helpful for me to review our naive or alternative proof for the null set, that of creating a separation axiom replacing P with x ≠x, saying that there is a set of just those things which do not equal themselves. We could create a specification axiom with x ≠x and it would prove that there is a null set. But it would not show at what stage the null set was formed, for in using x ≠x, both sides of the conjunction (x ≠x ∧ ∃t(tEx ∧ xFt)) would be false, leaving no z  in y. With Boolos’ proof, he shows that y becomes the null set as at the first stage because ¬∃t(tEx ∧ xFt).[1]

Pairing

Zermelo’s pairing axiom [∀x ∀y ∃z ∀a (a ∈z ↔ (a=x ∨a=y))] said that for any two sets, there was another set that contained just those two. We see that the pairing axiom follows from the iterative conception as well.

Suppose the pairing axiom were false, so [∃x ∃y ∀z ∃a ¬( a ∈z ↔ (a=x ∨a=y))] all sets z have at least one member which aren’t a given x or y. Let x and y be g and h respectively.

So ∀z ∃a ¬( a ∈z ↔ (a=g ∨a=h)). All sets have at least one member that is neither g nor h. Since g and h exist, then they appeared at some stage. Let’s call that stage ‘s’. By axiom 5 there is a stage s+1. Let ‘t’ be that stage.

At stage t our specification axiom holds: ∃n∀p(p∈n ↔((p=g ∨ p=h) ∧ ∃m(mEt ∧ pFm)).

As both g and h were formed prior to t then there is a set n which only contains p and h.

Conclusion

With these two proofs, we begin to see some of the elegance of the iterative conception take shape as it gets us where we have wanted to go under the naïve notion but in a way which makes much better sense of the notion of ‘set’.

In the next (and final) article in this series, we’ll take a look at three final axioms of Zermelo-Fraenkel, Union, Power Set and Infinity.



[1] What is now interesting to consider is whether or not there is a null set at every stage, given the specification axiom with x ≠x.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>