The iterative conception of set

The conception of the set was always giving food for thought since Cantor introduced it formally in his famous work ‘Contributions to the Founding of The Theory of Transfinite Numbers’ (which was later translated in English by Philip. E. B. Jourdain). Cantor described the set as a totality of definite elements that can be combined into a whole by a law. Although this description is still a bit blur, it immediately results in two properties of the sets:

i) that every set has elements or members (and we can write this, given a set X, as { x \in X \Leftrightarrow x } is an element in { X }.

ii) that a set { X } is fully determined by it’s elements. This means that given two sets { X,Y }, we have { X=Y \Leftrightarrow ( \forall x ) [ x \in A \Leftrightarrow x \in B] }.

The second property is called the extension property. Lets us call this conception of set, naive conception.
If one has studied the basic proof and results of the basic theory based on the naive conception of the set, he might see that they are based basically on:

i) The extension property ii) The comprehension principle.

What is the comprehension principle? Well in general words, it says that for any predicate, there is a set of all and only those things to which it applies. Can there be two such sets i.e. can there be two sets such whose members are exactly the things to which the predicate applies? If we consider the extension principle, it can be at most one set. To clarify this, let us write the comprehension principle in mathematical terms.

For every { n-part } definite condition (by which we mean a condition { P } such that for every { n-items}, { \overrightarrow{x}= (x_1,x_2, \dots, x_n ) }, { P(\overrightarrow{x}) } is defined without question if its true or not){ P }, there exists a set

{ A = \lbrace \overrightarrow{x} | P( \overrightarrow{x}) \rbrace }
with members exactly these {n-items } which satisfy { P(\overrightarrow{x}) } such as for every { \overrightarrow{x} }

{ \overrightarrow{x} \in A \Leftrightarrow P( \overrightarrow{x} ) }.

So, if we had a second set { B \neq A } which satisfied the above condition, then by the extension property, { B=A }. So there is a most one set { A } satisfying this condition.

The comprehension principle seems very strong. How could there be not a collection or set of just those things to which any given predicate is applied?’ writes George Boolos. Russell’s paradox though comes to indicate the inconsistency of naive set theory.

No set can contain all and only those sets which do not contain themselves.
If such as a set existed then,if it contained itself,then, as it contains only those sets which do not contain themselves, it would not contain itself, whereas if it did not contain itself, then as it contains all those sets which do not contain themselves, it would contain itself. You may have to read one or two times more. Lets see how we write it 1st order language:

Consider, using the comprehension principle, the set { R= \lbrace x | x } is set and { x \not\in x \rbrace }.
Then by the definition of { R } we have that

{ R \in R \Leftrightarrow R \not\in R } , which is a paradox.

The famous letter of Russell to Gottlob Frege described this paradox and consequently the inconsistency of the naive set theory. Many solutions were proposed; from the French mathematician PoincarĂ©, or from the Dutch topologist Brouwer. Even Russell with his famous theory of types tried to cast away the paradoxes. But all these, for various reasons, were put aside, and Zermelo’s axiomatic set theory in 1908 took over. In Zermelo’s theory the first iterative conception of set took place.
To begin with, iterative conception of set focuses mainly on how a set contains itself. If we see our previous thoughts on Russell’s paradox once again, we observe that we started with a set that contains all sets, and therefore itself. A set can include itself but can it contain itself? Suppose that we have in a table some elements (there can be one or none elements too), some things. If we bind them together we can now argue that we have a set. But we do not suppose that what we have now in the table (that we call it a set) could have been one of the things we combined. You see, the word now is very important.

When I was younger, the idea of, if you allow me to say, the time an arbitrary set is formed (or as I used to call it, the time of the set) troubled my mind. I had this particular example in my mind, and I was trying to find ways to determine `when’ do we really stop constructing our set and have it `definition-ready’ (with applications, such as avoiding the paradox of the set containing itself and not containing itself).
It made me so happy when I found this iterative conception of set where `time words’ were used, such as `stage’,`formed at’, `earlier than’, `keep on going’. The idea is beautiful and I am going to copy it directly from George Boolos’s article (see references):

‘A set is any collection that is formed at some stage of the following process: Begin with individuals (if there are any). An individual is an object that is not a set; individuals do not contain members. At stage zero (we count from zero instead of one) form all possible collections individuals. If there are no individuals, only one collection, the null set, which contains no members, is formed at this { 0th } stage. If there is only one individual, two sets are formed: the null set and the set containing just that one individual. If there are two individuals, four sets are formed; and in general, if there are { n } individuals, {2^n } sets are formed. Perhaps there are infinitely many individuals. Still, we assume that one of the collections formed at stage zero is the collection of all individuals, however many of them there may be. At stage one, form all possible collections of individuals and sets formed at stage zero. If there are any individuals, at stage one some sets are formed that contain both individuals and sets formed at stage zero. Of course some sets are formed that contain only sets formed at stage zero. At stage two, form all possible collections of individuals, sets formed at stage zero, and sets formed at stage one. At stage three, form all possible collections of individuals and sets formed at stages zero, one, and two. At stage four, form all possible collections of individuals and sets formed at stages zero, one, two, and three. Keep on going in this way, at each stage forming all possible collections of individuals and sets formed at earlier stages. Immediately after all of stages zero, one, two, three,…, there is a stage; call it stage omega. At stage omega, form all possible collections of individuals formed at stages zero, one, two,… . One of these collections will be the set of all sets formed at stages zero, one, two, … . After stage omega there is a stage omega plus one. At stage omega plus one form all possible collections of individuals and sets formed at stages zero, one, two…, and omega. At stage omega plus two form all possible collections of individuals and sets formed at stages zero, one, two,..-. omega, and omega plus one. At stage omega plus three form all possible collections of individuals and sets formed at earlier stages. Keep on going in this way. Immediately after all of stages zero, one, two omega, omega plus one, omega plus two,…, there is a stage, call it stage omega plus omega (or omega times two). At stage omega plus omega form all possible collections of individuals and sets formed at earlier stages. At stage omega plus omega plus one … omega plus omega plus omega (or omega times three)… … (omega times four)… … omega times omega Keep on going in this way . According to this description, sets are formed over and over again: in fact, according to it, a set is formed at every stage later than that at which it is first formed. We could continue to say this if we liked; instead we shall say that a set is formed only once, namely, at the earliest stage at which, on our old way of speaking, it would have been said to be formed.

So this it the rough statement of the iterative conception of the set. There can be a set of all sets because every set is formed at some earlier stage; it’s members are only individuals or sets formed at an earlier stage.

Exercise:
Prove that there are not two sets { x, y } which belong to each other.

Note: Can you find the analogy between inductively constructing sets and inductively constructing natural numbers?

References:

[1]Boolos G.: ‘The Iterative Conception of Set’ in Philosophy of Mathematics,selected readings by Paul Benacerraf and Hilary Putnam, 1983, Cambridge University Press, pp. 486-493.

[2]Kamareddine F, Laan T., Nederpelt, R.(2004): A Modern perspective on Type Theory, Kluer Academic Publishers.

[3]Moschovakis Y.(1994): Notes on Set Theory, Springer-Verlag New York.

Advertisements

Leave a Reply

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


%d bloggers like this: