56
$\begingroup$

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. ${}{}$

$\endgroup$
9
  • 17
    $\begingroup$ I think it is in a sense just a matter of convenience. On the other hand, everything of interest has a well-founded "surrogate" (using Pen's expression), so there is no loss here (this is important, if you take seriosuly the idea of maximizing expressive power). All this said, foundation is really key to the way we deal with sets nowadays. Adrian Mathias once went so far as to say that modern set theory is really the study of well-foundedness. $\endgroup$ Sep 29, 2015 at 19:02
  • 6
    $\begingroup$ @AndrésCaicedo and if you come from a structural set theory background, ZFC et al is just the study of certain well-founded trees. $\endgroup$
    – David Roberts
    Sep 30, 2015 at 7:17
  • 3
    $\begingroup$ @David: You can't see the forest for the trees if you look at it this way! $\endgroup$
    – Asaf Karagila
    Sep 30, 2015 at 10:56
  • 3
    $\begingroup$ @AsafKaragila But their long branches may be more visible on a sunny day. $\endgroup$
    – Avshalom
    Oct 1, 2015 at 8:13
  • 4
    $\begingroup$ We could turn this around and ask whether there is any reason to disbelieve the axiom of regularity. A strong reason to disbelieve it would be if there were some part of mathematics (group theory, differential geometry, number theory, ...) in which we found that it was inconvenient to be restricted to the kind of sets that are well-founded. $\endgroup$
    – user21349
    Oct 1, 2015 at 23:20

8 Answers 8

61
$\begingroup$

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’.

$\endgroup$
5
  • 3
    $\begingroup$ Your second paragraph gives an interesting perspective. I have never thought of it this way. $\endgroup$
    – Wojowu
    Sep 29, 2015 at 19:37
  • 6
    $\begingroup$ Much the same explanation is given in Kunen's Set Theory: that all of mathematics takes place anyway within the universe of well-founded sets. It also leads naturally to the intuitive picture of sets called the cumulative hierarchy which, if I understand the message from this MO post and the thread underneath -- mathoverflow.net/a/208729/2926 -- imparts to ZF much of its "ontological" force. $\endgroup$
    – Todd Trimble
    Sep 29, 2015 at 19:38
  • $\begingroup$ What if there are strictly more sets and urelements than well founded objects, then we have no way of redefining the hierarchy to contain all sets and urelements. I know there is actually no such thing as a proper class since it cannot be an element. There is only such a thing as a statement that mentions a proper class. $\endgroup$
    – Timothy
    Jan 26, 2017 at 19:53
  • $\begingroup$ Does the axiom of regularity just insist on the inexistence of elements other than those that can be defined in a very constructive way like from taking the power set of a set, from which it can be proven without the axiom of choice that all cardinal numbers are smaller than some cardinal number with an aleph number? $\endgroup$
    – Timothy
    Jan 26, 2017 at 19:59
  • $\begingroup$ I think ZF without regularity is a subtheory of ZF. There's an injection from the theorems of ZF to the theorems of ZF without regularity. The formal system that only lets you prove those theorems, although it is equivalent to ZF is actually a subtheory of ZF without regularity, not a supertheory of it like ZF is. I guess some mathematicians agree that the real meaning of the theorems of ZF talk only about well-founded sets whereas others don't because the axiom of regularity and inexistence of urelements aren't disprovable either. $\endgroup$
    – Timothy
    Jun 25, 2018 at 2:26
36
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ I must admit that cumultative hierarchy spanning whole universe is how I've been justifying to myself why regularity "should" hold - it puts a kind of "order" on sets, showing which ones are "simpler" than others. $\endgroup$
    – Wojowu
    Sep 30, 2015 at 14:02
  • 6
    $\begingroup$ I agree very much with this answer. $\endgroup$ Sep 30, 2015 at 21:36
  • 1
    $\begingroup$ @Nullachtfünfzehn You seem to be mixing two different ways of viewing the mathematical universe. The first, as described by "T" in my answer at mathoverflow.net/q/90945, would indeed say that functions are not sets; they are entities of another sort (or sorts). The second, the result of interpreting T in ZFC, would replace those functions with their set-theoretic encodings, and would say that functions are sets of ordered pairs. The present question is about the second of these viewpoints, as described by ZFC. [continued in next comment] $\endgroup$ Nov 16, 2016 at 16:51
  • 1
    $\begingroup$ [continuation of previous comment] If one wants to regard the T world as a cumulative hierarchy, then every stage should involve formation not only of sets with elements from earlier stages but also of functions between them, ordered pairs of them (since ordered pairs would not be coded as sets), etc. $\endgroup$ Nov 16, 2016 at 16:54
  • 2
    $\begingroup$ @Nullachtfünfzehn I was using "circular" in the broader sense of a definition that refers to the term that is being defined. Strictly speaking, even a recursive definition is circular in this sense. (For example, the recursive definition of $n!$ includes the clause $(n+1)!=n!\cdot(n=1)$ so it defines ! in terms of !.) But we know how to remove this sort of circularity in the case of well-founded recursions. So "circular" is often limited to mean "non-well-foundedly circular", and this is what I intended in my answer. $\endgroup$ Nov 16, 2016 at 21:12
10
$\begingroup$

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.

$\endgroup$
9
  • 5
    $\begingroup$ This sounds to me more like an argument for the anti-foundation axiom, which says exactly that when you make precise the “structure” that you get by iteratively unfolding a set, there is a unique set for any such structure. Foundation is equivalent to the restricted version that there is a unique set for any well-founded such structure. $\endgroup$ Mar 2, 2016 at 7:50
  • 1
    $\begingroup$ @PeterLeFanuLumsdaine Yes, that would be another possible solution. But the Regularity seems to be much simpler to formalize (am I wrong here? could you show a formalized form of the Anti-foundation?). And the overall structure of the universe with Regularity seems "nicer" and easier to visualize. It is clear what sets are "made from", so to speak. And if I understand correctly, the regular universe is still suitable to build models of non-well-founded theories, so nothing essential is lost. $\endgroup$ Mar 2, 2016 at 17:32
  • 4
    $\begingroup$ You may already be aware of this, but AFA is a well-motivated and relatively simple to formalize anti-foundation axiom. The theories ZF - Foundation + AFA and ZF are bi-interpretable, so they're equally expressive, but I'm sympathetic to your view that Regularity provides a universe of sets that's easier to "grasp". $\endgroup$ Mar 2, 2016 at 19:15
  • 2
    $\begingroup$ I haven't read it thoroughly, but this seems like a good reference. The statement of AFA given there ("every graph has a unique decoration") is straightforward to express in the first-order language of set theory, along the lines of "for all $G$ and all $R\subseteq G^2$ there exists a unique $F$ such that $F$ is a function with domain $G$ such that for all $x$ and $y$, $R(x,y)$ if and only if $F(y)\in F(g)$." $\endgroup$ Mar 2, 2016 at 21:46
  • 1
    $\begingroup$ @AlexKruckman Thanks. I will try to explicitly write this formula as an exercise for myself. I think I now understand how it can be done. But it certainly looks more complicated than the Regularity (not to say that it makes it less interesting or inferior in any way). $\endgroup$ Mar 2, 2016 at 22:01
5
$\begingroup$

"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 intoductory 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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ "Nobody asks ..." but see here. $\endgroup$ Mar 2, 2016 at 16:34
  • 3
    $\begingroup$ @Andrés: Your comment is a comment of a true mathematician. :-) $\endgroup$
    – Asaf Karagila
    Mar 2, 2016 at 17:00
4
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ This is a very nice argument. Do you know anywhere it’s given or discussed in the literature (especially, anywhere that Dana wrote about it himself)? Also, it seems worth explicitly summarising what it says about the original question: it shows that if you believe some a priori slightly weaker principles (your 1–3 here, made precise in a suitable way), then these imply regularity. So “why should I believe regularity?” reduces to “why should I believe that sets are produced in ordered stages?”, assuming the inquirer already accepts the rest of your 1–3. $\endgroup$ Apr 9, 2019 at 16:11
  • 1
    $\begingroup$ Concerning your first question, yes I do. Shoenfield (1977) The axioms of set theory. $\endgroup$ Apr 9, 2019 at 16:14
  • 1
    $\begingroup$ @PeterLeFanuLumsdaine I believe the relevant paper by Dana is (reference copied from MathSciNet): MR0392570 (52 #13387) Scott, Dana Axiomatizing set theory. Axiomatic set theory (Proc. Sympos. Pure Math., Vol. XIII, Part II, Univ. California, Los Angeles, Calif., 1967), pp. 207–214. Amer. Math. Soc., Providence, R.I., 1974. $\endgroup$ Apr 9, 2019 at 16:20
  • 1
    $\begingroup$ Now the second question. My philosophical position is that the principles charaterizing a set-formation notion are not the kind of thing we believe, but they are the kind of thing we can adopt. If you adopt those principles, then the regularity axiom is justified, that is what is proved. The principles are prescriptive in nature, and they play the role of a correctness standard in set theory. Otherwise we would enter an infinite regress, since we could also ask "why believe in the principles?" $\endgroup$ Apr 9, 2019 at 16:21
3
$\begingroup$

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)) 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.

$\endgroup$
4
  • 3
    $\begingroup$ "One can certainly understand the early set theorists' concern over the existence of a set y such that y∈y." I slightly disagree to that. As far as I can see, and what mathematicians back in the day probably saw as well, is that what causes the paradox is not a (supposed) existence of self-containing sets, but clearly the unrestricted comprehension - after all, Russell's paradox isn't avoided if we assume regularity in any form. $\endgroup$
    – Wojowu
    Sep 30, 2015 at 13:57
  • 1
    $\begingroup$ @Wojowu: You are partially correct in that, I think. To quote Russell (from his letter to Frege: "Let $w$ be the predicate: 'to be a predicate that cannot be predicated of itself. Can $w$ be predicated of itself? From each answer its opposite follows. Therefore we must conclude that $w$ is not a predicate. Likewise there is no class (as a totality) of those classes which, each taken as a totality, do not belong to themselves. From this I conclude that under certain circumstances a definable collection [[Menge]] does not form a totality." One should beware of engaging in 20/20 $\endgroup$ Sep 30, 2015 at 21:57
  • 1
    $\begingroup$ (cont.) hindsight. Certainly they were vaguely aware unrestricted Comprehension was the cause ot the paradoxes, but were at odds of how to restrict the principle adequately. To quote Zermelo from the paper I mentioned in my answer (pg. 203) in the paragraph following of his 'proof' of Regularity from the Axiom of Separation: "It follows from the theorem that not all objects $x$ of the domain $\mathfrak B$ can be elements of one and the same set ; that is, the domain $\mathfrak B$ is itself not a set, and this disposes of the Russell antinomy so far as we are concerned." $\endgroup$ Sep 30, 2015 at 22:07
  • $\begingroup$ @Wojowu: Please take a look at Zermelo's 'proof', If you can find a copy of van Heijenoort's book. $\endgroup$ Sep 30, 2015 at 22:12
1
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ Existence of the universal set gives a contradiction even if we don't assume axiom of foundation - it follows from other axioms of ZF that the universal set doesn't exist. $\endgroup$
    – Wojowu
    Oct 1, 2015 at 16:35
  • 3
    $\begingroup$ This also doesn't answer my question, because I have asked for reasons why people should believe this axiom. Of course you don't have to believe in it, just like you don't have to believe in consistency of arithmetic. $\endgroup$
    – Wojowu
    Oct 1, 2015 at 16:36
  • 1
    $\begingroup$ I fail to see a useful parallel between disbelief in the axiom of foundation and belief in the inconsistency of arithmetic. And of course a universal set is inconsistent with the Axiom of Separation; the justification for Separation from the iterative concept of set (which others here have discussed) obviously doesn’t apply to ill-founded sets. More on this in Forster’s Oxford Logic Guide pp. 141–2, or §1 of my forthcoming Logique et Analyse article, preprint at logic-center.be/Publications/Bibliotheque. $\endgroup$ Oct 5, 2015 at 5:13
  • 4
    $\begingroup$ It sounds to me that Flash is rejecting the premise of the question: that one actually should believe it. As an answer though it's rather skeletal. $\endgroup$
    – Todd Trimble
    Mar 2, 2016 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.