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

  • 13
    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. – Andrés E. Caicedo Sep 29 '15 at 19:02
  • 4
    @AndrésCaicedo and if you come from a structural set theory background, ZFC et al is just the study of certain well-founded trees. – David Roberts Sep 30 '15 at 7:17
  • 2
    @AsafKaragila But their long branches may be more visible on a sunny day. – Avshalom Oct 1 '15 at 8:13
  • 2
    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. – Ben Crowell Oct 1 '15 at 23:20
  • 1
    @SebastianGoette That's indeed some point to consider. However, by similar reasoning, we should accept V=L as an axiom, which generally isn't done, because V=L is often considered too restrictive. One could interpret my question as asking why, on the other hand, foundation isn't considered to be too restrictive as well. – Wojowu Mar 2 '16 at 21:18
up vote 40 down vote accepted

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

  • 3
    Your second paragraph gives an interesting perspective. I have never thought of it this way. – Wojowu Sep 29 '15 at 19:37
  • 4
    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. – Todd Trimble Sep 29 '15 at 19:38
  • 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. – Timothy Jan 26 '17 at 19:53
  • 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? – Timothy Jan 26 '17 at 19:59
  • 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. – Timothy Jun 25 at 2:26

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.

  • 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. – Wojowu Sep 30 '15 at 14:02
  • 2
    I agree very much with this answer. – Joel David Hamkins Sep 30 '15 at 21:36
  • Shoenfield also expresses a very similar view of sethood in his paper "Axioms of set theory", in Jon Barwise & H. Jerome Keisler (eds.), Handbook of Mathematical Logic. North-Holland Pub. Co. 90 (1977), although he does not restrict his exploration to the axiom of regularity. – Avshalom Sep 30 '15 at 22:48
  • @AndreasBlass: You write "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". But not every collection of urelements is a set, and not every urelement lies at the botton of the hierarchy. For example, functions are objects that aren't sets, and thus functions are urelements. But one can't form the set of all functions. – user99916 Nov 16 '16 at 16:25
  • Also, functions do not lie at the botton of the hierarchy. Instead, on every stage $\alpha$ one can form all sets that lie on lower stages, and form all functions A --> B where A, B are sets created at a lower stage. – user99916 Nov 16 '16 at 16:26

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, thenin “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.

  • 4
    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. – Peter LeFanu Lumsdaine Mar 2 '16 at 7:50
  • I second what Peter says. Seeing that we could have $x=\{x\},y=\{y\}$ and $x\neq y$ there are two ways to avoid that: either disallow $x=\{x\}$ (which leads to certain weak version of foundation) or disallow $x\neq y$ (i.e. suppose that there is a unique set satisfying $x=\{x\}$). Now one would ask why we should go for the former and the latter. – Wojowu Mar 2 '16 at 17:27
  • Also, by similar argument we could justify certain weak version of foundation, namely: for no set $x$ can we find sets $x_1,\dots, x_n$ such that $x\in x_1\in\dots\in x_n\in x$, but I am struggling to see how this could justify full foundation. – Wojowu Mar 2 '16 at 17:29
  • @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. – Vladimir Reshetnikov Mar 2 '16 at 17:32
  • 2
    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". – Alex Kruckman Mar 2 '16 at 19:15

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.

  • 2
    "Nobody asks ..." but see here. – Andrés E. Caicedo Mar 2 '16 at 16:34
  • 1
    @Andrés: Your comment is a comment of a true mathematician. :-) – Asaf Karagila Mar 2 '16 at 17:00

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.

  • 3
    "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. – Wojowu Sep 30 '15 at 13:57
  • @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 – Thomas Benjamin Sep 30 '15 at 21:57
  • (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." – Thomas Benjamin Sep 30 '15 at 22:07
  • @Wojowu: Please take a look at Zermelo's 'proof', If you can find a copy of van Heijenoort's book. – Thomas Benjamin Sep 30 '15 at 22:12

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

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

  • 1
    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. – Wojowu Oct 1 '15 at 16:35
  • 2
    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. – Wojowu Oct 1 '15 at 16:36
  • 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. – Flash Sheridan Oct 5 '15 at 5:13
  • 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. – Todd Trimble Mar 2 '16 at 21:22

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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