Iterating a Concept of Sets

By Brandon Mitchell

If you:

A)     Recognized the (admittedly belaboured) pun in the title and

B)      Then opened the article to read it

then this article is likely beneath you.

If however, you were just interested in an article about sets, then this very well may prove both interesting and helpful!

Maybe you too, like me, had the naive concept of sets presented at some point in your academic career. The lecturer  quickly proved it to be incoherent and with equal rapidity moved on to the briefest introduction of the ‘iterative conception’ possible. This followed shortly thereafter with a presentation of the standard Zermelo axioms.

If so, then it’s likely that you too, like me, felt as if you were the fat kid in an academic game of dodge-ball, suffering lasting wounds to your most sensitive parts, as axioms, lemmas and proofs were thrown at you while all your classmates seemed well able to deal with this dizzying and exhausting experience.

Maybe you too, like me, found that introduction both perplexing and disconcerting, leaving one wondering where we began and why…immediately followed by wondering where precisely we ended up…and why…

Well, that was my relationship with the foundational aspects of set theory until recently coming across a paper by George Boolos appearing in a 1971 edition of the Journal of Philosophy[1]. In it, he helpfully takes the reader through what has been called the ‘naive’ conception, then introduces the iterative conception and most importantly grounds the Zermelo axioms in the characteristics which make up the iterative conception.

My hope here is to reiterate these steps, taken at dizzying speed in the lecture hall, with perhaps a bit more clarity.

Boolos begins, as do I, with the notion of a set itself and Georg Cantor’s definition that a set is, ‘a totality of definite elements that can be combined into a whole by a law’[2]. Putting aside the relative obscurity of many of the concepts employed by Cantor, a few things about sets remain. They are meant to be a definite collection of things. Being a definite collection of things and only a definite collection of things, sets are to be identified by their members. Should two sets contain all and only the very same things, then they are the same sets.

Axiom of Extensionality: ∀A ∀B ∀x ((x ∈ A ↔ x ∈ B) → A = B)

Combine the extensionality concept with a collection of predicates which lack vagueness and it seems natural, given the law of excluded middle, to suppose that for any given predicate there are two sets, one of things to which the predicate applies and the other those things to which the predicate does not apply. Boolos sums the thought up as ‘Every predicate has an extension.’

Naive ‘Separation’: For all predicates F, ∃B ∀x (x ∈ B ↔ Fx)

The thought here is that the totality of predicates then defines the universe of sets. That is, all the sets that we can talk about, describe and otherwise play with. Extensionality and Naive Separation combine to form what we’ll call the ‘Naive Theory’.

By specifying certain specific formulas for Fx, we get some of the familiar axioms:

Sy = y is a set

∃y(Sy ˄ ∀x(x ∈ y ↔ x ≠ x)) – Null Set

∃y(Sy ˄ ∀x(x ∈ y ↔ (x = z ˅ x = w))) – Pairing

∃y(Sy ˄ ∀x(x ∈ y ↔ ∃w(x ∈ w ˄ w ∈ z))) – Union

∃y(Sy ˄ ∀x(x ∈ y ↔ (Sx ˄ x=x))) – Universal Set

Unfortunately there is a predicate that we can put in for Fx which leads to a logical contradiction.

Consider:

∃y(Sy ˄ ∀x(x ∈ y ↔ x ∉ x))

This says that there is a set of things which are not members of themselves. Let A be such a set.

Then:

∀x(x ∈ A ↔ x ∉ x)

Since the thought is that there are things which are and are not F then anything that we may talk about either is or is not in the extension of F. So the universal quantifier ranges over our set A.

So:

A ∈ A ↔ A ∉ A

As a result, we can’t say that there is a set corresponding to the extension of any predicate.

And while the above is the most decisive objection to the naive concept of sets, there are yet others.

Above, we arrived at the notion of a universal set by placing x = x for Fx. Since everything is self identical then the universal set contains everything, including itself. And as you’ll remember, two sets are the same when they have the same members. Sets are defined in terms of  their members. But the universal set has itself as a member.

If x = {a,b,c,x} and y = {a,b,c,y} does x = y? It would seem that it does. But this is still an awkward situation.

Similarly awkward is:

x = {a,b,c,y} and y = {d,e,f,x}. So x = {a,b,c,{d,e,f,x}} which equals {a,b,c,{d,e,f,{a,b,c,y}}} and so on and so forth.

Where a ∈ b and b ∈ c and c ∈ a, then we can call these sets ungrounded, a seemingly circular definition holds between them.

And while these issues of ungroundedness and self membership may not be logically problematic like the contradiction, they might be things we’d like to avoid in our iteration of sets.

So we look for another way for imagining the universe of sets.

In part II, I’ll present this new way, the Iterative Conception.



[1] George Boolos. ‘The Iterative Conception of Set’. Journal of Philosophy. Vol 8, No 68. April 1971. Pgs 215-231

[2] Georg Cantor. Gesammelte Abhandlungen, Zermelo ed. Berlin 1932.

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>