To Infinity and Beyond with the Iterative Conception
By Brandon Mitchell
In the previous two articles, we’ve covered why incoherence and unintuitive set self membership led to the search for another method of grounding the Zermelo-Fraenkel axioms of set theory. We discussed how the iterative conception is perhaps a more straightforward way of understanding the universe of sets and how Pairing and the Null Set Axioms follow from the axioms which constitute the iterative conception.
We now turn to the final three axioms of Zermelo-Fraenkel; Union, Power Set and Infinity.
Axiom of Union – ∀A∃B∀x (x∈B ↔ ∃D(x∈D ∧ D∈A))
The broad gist of the axiom of union is that for any collection of sets A there is another set B which contains the members of the sets in A. (Do a visual)
So let’s assume the negation of the axiom of union giving us:
∃A∀B∃x¬(x∈B ↔ ∃D(x∈D ∧ D∈A))
This is to say that there is a collection of sets for which there is no union set.
Let’s call this collection H, so:
∀B∃x¬(x∈B ↔ ∃D(x∈D ∧ D∈H)).
By axiom 7 in the iterative conception, all sets are formed at some stage. And so H was formed at some stage. Let’s call that stage S.
By axiom 9, all possible collections of elements formed at previous stages are formed at a given stage.
So, at least one member of H was formed at S-1. Let’s call that member G.
By axiom 9 at least one member of G was formed at S-2. Let’s call that member F. (do visuals)
So to recap F ∈ G ∈ H
Changing tack, by axiom schema 10, for all stages s, ∃y∀z(z∈y ↔(∃D(z∈D ∧ D∈H) ∧ ∃t(tEs ∧ zFt)))
As a reminder, the point of the axiom schema is to capture the notion that at every stage every possible collection of items formed at previous stages appears at that stage.
The statement above says that there is a collection y which contains all z’s where z is a member of a member of H and was formed before s. Remember that we said that H was formed at the arbitrary stage S and that the last member of a member of H was formed at S-2. So we see that the union of H appears at S-1.
Power-set Axiom – ∀A∃P∀B(B ∈ P ↔ ∀C(C ∈ B → C ∈ A))
The power set axiom says that for any set A there is a set P of all the subsets of A.
Remember that the definition of subset A ⊆ B ↔ ∀C(C ∈ A → C ∈ B). This is to say that every member of A is also a member of B. Note that under this definition, B is a subset of itself.
So now let’s address how the power set axiom follows from the axioms of the iterative conception.
Again the straightforward thought is that at each stage there is formed all possible collections of sets formed at the previous stages. Let’s say there is a set A formed at some stage s. As A ⊆ A for all A, then we expect A ∈P. Axiom 10 then tells us that P will be formed at stage s+1.
And now, more formally consider the negation of the power set axiom:
∃A∀P∃B¬ (B ∈ P ↔ ∀C(C ∈ B → C ∈ A)).
This says that there is a set A which doesn’t have a power set P.
Let’s call such a set D.
So: ∀P∃B¬ (B ∈ P ↔ ∀C(C ∈ B → C ∈ D)).
So for all sets P they either have a member B which has members not in D and so is not a subset of D or B is a subset of D and is not in P.
But by axiom 10: For all stages s ∃y∀z(z∈y ↔ (∀C(C ∈ z → C ∈ A) ∧ ∃t(tEs ∧ zFt)))
This says that there is a set y of all sets z which just contain members of A where z was formed before a given stage s. This means that there is a set P above if we can find the stage at which it is formed.
Remember that we said that A ⊆ A and so A ∈P. We said that A was formed at some stage S so by our version of Axiom 10 if s is S+1 then y is P.
More formally:
∃y∀z(z∈y ↔ (∀C(C ∈ z → C ∈ A) ∧ ∃t(tEs ∧ zFt))) Let’s call such a y, V.
So: ∀z(z∈V ↔ (∀C(C ∈ z → C ∈ D) ∧ ∃t(tEs ∧ zFt))) So: ∃B¬ (B ∈ V ↔ ∀C(C ∈ B → C ∈ D))
Let’s call such a B, K. So: ¬ (K ∈ V ↔ ∀C(C ∈ K → C ∈ D)).
So: (K∈V ↔ (∀C(C ∈ K → C ∈ D) ∧ ∃t(tEs ∧ KFt))) And here we arrive at the contradiction. Our axiom says that at any stage s there is a set V of the subsets of D, but our negated axiom denies that.
Now the stage at which V is formed is determined by the stage at which K is formed. As we’ve said above, if D is formed at stage s, then K is formed at stage s and V is formed at stage s+1.
Infinity
There is a set I which contains the null set and for all x in I the von Neumann successor of x is in I.
The von Neumann successor of x is the union of x and {x}. As such, the von Neumann successor of {a, b} would be the union of {a,b} and {{a,b}} which is {a, b, {a, b}}.
The axiom of infinity first claims that there is a set which contains the null set.
We established that the null set appears at stage 1.
It also says that this set contains the von Neumann successor to all its members.
If x appears at a given stage s, then {x} appears at s+1 by Axiom 10. At stage s+2 the union of x and {x}, in other words, the von Neumann successor of x appears.
Set |
Von Neumann Successor |
{0} | {0, {0}} |
{0, {0}} | {0,{0},{0.{0}}} |
At any stage s, by axiom 10, ∃y∀z(z∈y ↔(z=z ∧ ∃t(tEx ∧ zFt)))), which is to say that at any stage there is a set of all sets formed at earlier stages. And so at any stage there is a set which contains the null set and the von Neumann successor to every member so long as that member was formed two stages earlier.
And here seems to be the purpose of axiom 6, that there is a stage, not the first one, which is not immediately after any other stage, and therefore, presumably, doesn’t include members formed at the immediately previous stage. Essentially, axiom 6 allows us to think of what would exist in light of an endless succession of stages.
Boolos, with who’s article we began this series, puts it this way, referring to the version of Axiom 10 above, ‘And if y contains x, y contains all successors of x (and there are some), for all these are formed at stages immediately after stages before s and, hence, at stages themselves before s.’
And this kind of locution is the precise reason why, writing myself, with perhaps more clarity, on the iterative conception felt worthwhile.