# iterative conception of set --> axiom of regularity

In the book Mathematical Logic by Joseph R. Shoenfield, he describes the iterative conception of set/cumulative hierarchy. The explanation is posted below and marked with a *.

The author explains also, why the axioms of ZFC are true under the interpretation of the cumulative hierarchy/the iterative conception of set:

To see that the regularity axiom is true, let x be a nonempty set, and let y be a member of x formed at as early a stage as possible. Since the members of y must be formed at a still earlier stage, they are not members of x. Hence y is a minimal element of x.

• I don't understand this. Why can he choose an y that is formed at as early as possible? Why couldn't it be the case that for every element y in x there is some y' in x such that y' is formed at an earlier stage as y?

* We now turn to an investigation of set theory. The great interest in sets is due partly to the important role which they have played in modern mathematics. But even without this, the notion of a set is so natural that it would call for investigation. A set (or class) is a collection of objects. These objects may be numbers, functions, physical objects, or even sets. Since there are no restrictions on the objects which may be members of sets, it would seem that we can specify a set by specifying for each object in the universe whether or not that object is a member of the set. However, this leads immediately to the Russell paradox. For let us specify a set A by specifying that an object x is a member of A iff x is a set and x is not a member of x. Then A is a member of A iff A is not a member of A; and this is a contradiction. A closer examination of the paradox shows that it does not really contradict the intuitive notion of a set. According to this notion, a set A is formed by gathering together certain objects to form a single object, which is the set A. Thus before the set A is formed, we must have available all of the objects which are to be members of A. It follows that the set A is not one of the possible members of A; so the Russell paradox disappears. We are thus led to the following description of the construction of sets. We start with certain objects which are not sets and do not involve sets in their construction. We call these objects urelements. We then form sets in successive stages. At each stage we have available the urelements and the sets formed at earlier stages; and we form into sets all collections of these objects. A collection is to be a set only if it is formed at some stage in this construction. We can carry out this construction with any collection of urelements. If we carry it out with no urelements, the sets which we obtain are called pure sets. It turns out that these are sufficient for mathematical purposes; and they are also sufficient to illustrate all the problems which arise in the general case. We shall therefore restrict ourselves to this case, and henceforth take set or class to mean pure set. When can a collection of sets be formed into a set? For each set x in the collection, let Sx be the stage at which x is formed. Then we can form a set of this collection iff there is a stage S which follows all the Sx. However, such a stage may fail to exist. For example, every stage may be an Sx. Thus we want an answer 2389.1 AXIOMS FOR SETS 239 to the following question: given a collection of stages, under what conditions is there a stage which follows every stage in the collection? Since we wish to allow a set to be as arbitrary a collection as possible, we agree that there shall be such a stage whenever possible, i.e., whenever we can visualize a situation in which all the stages in the collection are completed. This is a rather vague principle; but we can conclude some precise results from it. For example, given a stage S, there is to be a stage following S. If a collection consists of an infinite sequence Su S2,... of stages, then we can visualize a situation in which all of these stages are completed; so there is to be a stage after all the Sn. Another important example is the following. Suppose that we have a set A, and that we have assigned a stage Sa to each element a of A. Since we can visualize the collection A as a single object (viz., the set A)9 we can also visualize the collection of stages Sa as a single object; so we can visualize a situation in which all these stages are completed. Hence there is to be a stage which follows all of the stages Sa. This result is called the principle of cofinality.

• Paragraphing is welcomed on MSE. – Matemáticos Chibchas Apr 27 '16 at 5:40

Stages in the cumulative hierarchy are well-ordered - there is no infinite decreasing sequence of stages (as would be required for your counterexample $y, y', y'', . . .$).

EDIT: I think I may be confused about exactly what you're asking. If you're asking "How do we know the cumulative hierarchy is well-founded," then the answer is "Because that's part of the definition." If you're asking "But why do we define it that way", ah then that's a lot more interesting! A good answer to that question would take a lot of space; but the crucial points are:

• We don't seem to lose anything this way (in particular, we can represent ill-founded sets inside a well-founded class).

• It greatly simplifies the structure of the universe we consider.

• And it meshes with a common picture of "iterative process" - it's not clear how to iterate something in an ill-founded way!

Towards that last point, see http://www.jstor.org/stable/2025204?seq=8#page_scan_tab_contents (Boolos, "The iterative conception of set" - note that there's another article of the same name by Forster, which you may find interesting as well - http://journals.cambridge.org/action/displayFulltext?type=1&fid=1908776&jid=RSL&volumeId=1&issueId=01&aid=1908772), especially page 222.

• @euerrrrrrr That's just part of the definition of the cumulative hierarchy - that it is indexed in a well-founded way. If you drop the axiom of regularity, then the cumulative hierarchy is a possibly proper subclass of the universe. The point is that the axiom of regularity is true of this subclass, and we choose to restrict attention to it because (1) we don't really lose anything in doing so, and (2) it is much tamer. – Noah Schweber Jan 25 '16 at 19:06
• Also, my answer is not just the statement of the axiom of regularity; the axiom of regularity says $\forall x\not=\emptyset \exists y\in x(y\cap x=\emptyset)$. That regularity holds in the cumulative hierarchy takes a small argument, which Shoenfield produces. – Noah Schweber Jan 25 '16 at 19:09
• @euerrrrrrr While the cumulative hierarchy is informal, I think the word "defined" is appropriate. Also, Shoenfield was not the first person to talk about it - his paragraph isn't the end-all-be-all on the subject. The cumulative hierarchy is (post Fraenkel, so far as I know) defined as a process (powerset and union) iterated along a (class-sized) well-ordering; so well-ordered stages is built into it. I think you should look up some early (pre-Shoenfield) sources on the cumulative hierarchy, or some surveys about it's history. – Noah Schweber Jan 25 '16 at 19:13
• @euerrrrrrr See my edit - does this improve things? (By the way, you shouldn't accept this if it doesn't answer your question - I'm not annoyed about my answer not being satisfying.) – Noah Schweber Jan 25 '16 at 19:20
• though not a very funny one ... ;-( – euerrrrrrr Jan 25 '16 at 19:38