Why should we believe in the axiom of regularity?

Question

Today I started reading Maddy's Believing the axioms. As I knew beforehand, it includes some discussion of ZFC axioms. However, I really hoped for a more extensive discussion of axiom of foundation/regularity.

Apparently, the reason why we usually take it is because it makes sets well-founded and makes $\in$-induction work, or because it puts all sets into a hierarchy (namely $V$). However, these reasons sound to me more like "we take this, because it's convenient". Another reason commonly given is "It's difficult to think of a set which is an element of itself". This is not a good reason, because many things are difficult to think of, and also one could argue that a set represented by $\{\{\{...\}\}\}$ should do the trick.

That brings me to my question:

Are there any "philosophical" reasons to believe that the axiom of regularity holds?

I understand that this question is quite vague and maybe too broad, but I will be thankful for any responses. ${}{}$

Answer 1

Regularity (aka Foundation) can be seen philosophically as an axiom of restriction. It is not necessarily saying “all the things you consider as sets must be well-founded”. It can be read saying “for the purposes of this set theory, we restrict our universe of discourse to just the well-founded objects”. It’s clarifying what we mean by sets, in a similar way as the extensionality axiom does.

You may find this explanation unsatisfying, since it’s fairly similar to what Maddy gives. But the point is that if you are philosophically unsure about it, the question to ask is not “Are all sets really well-founded?” but “Is it really convenient/harmless/natural to restrict attention to the well-founded sets?”

A precise statement which can be seen as justifying this is the fact that within (ZF – Regularity), one can prove that the class of well-founded objects is a model of ZF.

Edit: see this followup question and its answer for:

• a rather stronger sense in which regularity is harmless, in the presence of choice: ‘Over (ZFC – regularity), regularity has no new purely structural consequences’

• a counter-observation that in the absence of choice, over (ZF – regularity), it’s not so clearly harmless; it has consequences that can be stated in purely structural terms, such as ‘every set is isomorphic to the set of the children of some element in some well-founded extensional relation’.

Answer 2

I think of the axiom of regularity along with the axiom of extensionality as formalizing what I mean by "set". Once upon a time, before paradoxes, one could think of sets as just any collection of things. Unfortunately, axioms based on that picture, in particular the unrestricted comprehension axiom, led to contradictions, so it became clear that the original, contradictory notion of "set" must be replaced by something clearer. (People might have thought the original notion was perfectly clear, but the paradoxes show that it isn't.) The clearer picture that emerged (in a development beginning with Russell's type theory, and continuing through simple type theory) is of a cumulative hierarchy, in which sets are obtained as follows.

Begin with some non-set entities called atoms ("some" could be "none" if you want a world consisting exclusively of sets), then form all sets of these, then all sets whose elements are atoms or sets of atoms, etc. This "etc." means to build more and more levels of sets, where a set at any level has elements only from earlier levels (and the atoms constitute the lowest level). This iterative construction can be continued transfinitely, through arbitrarily long well-ordered sequences of levels.

This so-called cumulative hierarchy is what I (and most set theorists) mean when we talk about sets. A set is anything that is formed at some level of this hierarchy. This meaning of "set" has replaced older meanings.

The axiom of regularity is clearly true with this understanding of what a set is. It expresses the idea that the stages of the cumulative hierarchy come in a well-ordered sequence. (Without well-ordering, the instructions for each level, namely "form all sets whose elements are at earlier levels," would not be an inductive definition but a circularity.)

Although there are set theories that contradict regularity, I would say that any such theory (and also any theory that contradicts extensionality) is not about sets but about some different (though presumably similar) entities.

Answer 3

I feel that the Regularity is close in spirit to the Extensionality, and together they convey the idea that identity of a set is determined only by its elements. With the Extensionality alone (without Regularity) there could exist sets $x=\{x\}$ and $y=\{y\}$ such that $x\ne y$. Both sets have seemingly identical structure $\Big\{\big\{\{...\}\big\}\Big\}$, but still are not equal. How many different sets with this structure exists? Seven? A proper class? Who knows... This would be very strange and counter-intuitive universe. The Regularity rules out such things.

---

I'm reading Logical Foundations of Mathematics and Computational Complexity by Pavel Pudlák (DOI 10.1007/978-3-319-00119-7), and a similar reasoning can be found there on p. 170, "Cleaning Up the Universe". Let me quote:

$\hspace{.5cm}$ But let’s get back to set theory. The cleaning process that we are going to consider has little to do with that theory. It is rather related to the well-known Occam razor which suggests getting rid of all unnecessary concepts. Following Cantorian tradition, it is unpopular to prohibit something in set theory. If a set can exist, then in “Cantor’s Absolute” the ideal world of sets, it does exist. Hence, by forbidding some sets, we get narrow-minded, and decide to study only a part of reality. Still there are sets which most set theorists give up voluntarily. Consider, for example, a set $x$ which has a unique element which is itself; so $x = \{x\}$. Let $y$ be another set with the same property. By extensionality they are different because they contain different elements $x\ne y$. If we take the elements of their elements, it is the same and so on. Structurally they are the same, but still they are different. The axioms considered so far do not exclude such sets, but such sets will never appear in the cumulative hierarchy of sets $\{V_\alpha\}_{\alpha\in ON}$, where $ON$ denotes the class of all ordinal numbers. On the other hand, those which are in the hierarchy are nice, as they are in some sense constructed from the canonical set $\varnothing$. Therefore, we prefer to have:

The Axiom of Foundation There are no sets outside the cumulative hierarchy.

Answer 4

I know that this question is pretty old, but since it has reappeared I take the opportunity to give a justification of this axiom due to Dana Scott (I think).

First, some general remarks. I understand that to be justified is to be justified from a list of principles characterizing the notion of set-formation set theory is supposed to be about. The old cantorian notion of set-formation as unlimited/undisciplined/unrestricted gathering leads to paradoxes and has long been replaced by an ordered/organized/disciplined set-formation which became the standard conceptual basis of set theory. This new notion can be characterized by the following principles:

1) Sets ought to be determined by their elements and produced in ordered stages without upper bound. If a set is produced at some stage, then each of its elements ought to be produced at an earlier stage.

2) At each stage any plurality of sets produced in previous stages ought to determine a set.

3) Given a set and stages functionally connected to its elements, there ought to be a stage after all those given stages.

There is no need to demand that the stages are well-ordered, contrary to a common belief. Now, Dana Scott's proof:

First, a set $x$ is said to be grounded if and only if every set containing $x$ as an element has a minimal element. The relation between sets and stages, that $x$ is produced at stage $s$, is denoted by $x R s$, and the ordering of stages is denoted by $\triangleleft$.

If all elements of a set $x$ are grounded, then $x$ is also grounded. For, suppose $x$ is an element of $y$. Then, either $y$ and $x$ have no common member, in which case $x$ is minimal, or there is a $z$ such that $z \in y$ and $z \in x$. From $z \in x$, it follows that $z$ is grounded, and from $z \in y$, it follows that $y$ has a minimal element.

If $s$ is a stage, then, from the second principle, there is a unique set $G_s$ which is produced at stage $s$ and whose elements are exactly the grounded individuals related to some stage below $s$. The set $G_s$ is grounded. Moreover, if $t \triangleleft s$, then $G_t \in G_s$.

Now, let $x$ be a non-empty set. Suppose that $x R s$. Let $y$ be the set of all $G_t$, for $t \triangleleft s$, such that there is a $z \in x$ such that $z R t$. Since any such $G_t$ is grounded, there is a stage $u$ such that $G_u \in y$ and $G_u$ is minimal. Since $G_u \in y$, there is a corresponding $z \in x$, such that $z R u$. So, $z$ must be minimal. Otherwise, there are $w \in z\cap x$ and a stage $v \triangleleft u$ such that $w R v$, hence $G_v \in y$. This contradicts the minimality of $G_u$, for $G_v \in G_u$.

Answer 5

"Believing" is a tall order, and Maddy's paper suggests nothing of that sort, as far as I am aware (though, of course, it is a nice way to connote it). On the contrary: if I were to name one idea from Maddy's paper that helped me shape my view of contemporary set theory, and indeed of the message of her paper, it would be in the vicinity of the following quotation (from the introductory passages to $\S$1):

Even the most cursory look at the particular axioms of ZFC will reveal that the line between intrinsic and extrinsic justification, vague as it might be, does not fall neatly between ZFC and the rest. The fact that these few axioms are commonly enshrined in the opening pages of mathematics texts should be viewed as an historical accident, not a sign of their privileged epistemological or metaphysical status.

The notion of rank, discussed by Maddy in the paragraph about foundation, must be strongly linked (historically at least) to Russell's theory of types, as the Wikipedia article on Regularity also confirms, quoting Enderton:

The idea of rank is a descendant of Russell's concept of type.

It was probably seen as an enhancement of Russell's way of addressing the paradox.

Treating collections of objects as objects, uniformly across the universe, is what calls for stipulating regularity and what enables its violations. But the scale of uniformity provided by ZFC is perhaps rarely needed. It may be just my illusion, but I think many branches of mathematics do keep their "internal stratification of notions" that makes it pointless to even appeal to regularity.

Answer 6

Consider the following analogy (which is just a reformulation of some answers given above):

In the context of fields, you might want to ask "Why should we believe that the square root of 2 exists? Or even more inconceivable, a number $x$ satisfying $x*x=-1$?" (Nobody asks this questions nowadays, but mathematicians had been struggling with these concepts.)

A possible (perhaps superficial) answer might be: We know structures in which such irrational or imaginary objects exist; we can even analyse these structures, and do computations with these objects.

This question is similar to the question about the belief in the existence of certain large sets, such as a power set or a large cardinal.

But the question about the regularity axiom is more similar to the question "Why should I believe that multiplication is commutative?" But this is not a philosophical or ontological question, rather a notational one. There are skew fields, and there are commutative fields, but history/tradition has decided to use the short name "field" only for the latter objects.

Similarly, there are "well-founded sets" and there are "antifoundational/Aczelian sets", and many other related concepts. History, or tradition, or just The Set Theorists have decided that the short name "set" belongs to the well-founded sets only.

Answer 7

Consider first the Unrestricted Axiom of Comprehension

($\exists$y)($\forall$x)(x$\in$y $\leftrightarrow$ $\phi$(x))

and the resulting Russell paradox

y$\in$y $\leftrightarrow$ y$\notin$y

One can certainly understand the early set theorists' concern over the existence of a set y such that y$\in$y.

Consider also Cantor's proof found in his letter to Dedekind (found in van Heijenoort's "From Frege to Goedel" pp113-117 (contents; Wayback Machine) that the system of "all numbers" (all ordinal numbers) $\Omega$ and its successor $\Omega^{'}$ are "inconsistent multiplicities". In order for his 'proof' to work one must allow $\Omega$$\in$$\Omega$ and the infinite descending sequence ....$\in$$\Omega^{''}$$\in$$\Omega^{'}$$\in$$\Omega$ (obviously for the Burali-Forti paradox as well).

In Zermelo's paper "Investigations in the foundations of set theory I" (also found in van Heijenoort--pp. 199-215), one finds the Axiom of Foundation cropping up as the following "theorem":

"Every set $M$ possesses at least one subset $M_0$ that is not an element of $M$."

which he 'proves' using the Axiom of Separation.

A good introduction to the Axiom of Regularity and its philosophical and historical underpinnings is the Wikipedia entry Axiom of Regularity.

That having been said, a good (at least in my opinion) introduction to nonwellfounded set theory is the paper by Takashi Nitta, Tomoko Okada, and Athanassios Tzouvaras titled "Classification of non-well-founded sets and an application" which can be found under this title on the Web (Wayback Machine).

Answer 8

You’re not obliged to believe the axiom; see, for instance, https://en.wikipedia.org/wiki/Universal_set.