9

Here Professor Blass describes the following cumulative hierarchy of sets:

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.

We want to agree on the following principles:

  1. For every level there is a succeeding level.
  2. For every sequence of levels: $l_1,l_2,l_3,\dots$ there is a level succeeding all levels $l_1,l_2,l_3,\dots$. One might call this level "limit level".

Question:

Why is the axiom of replacement true under this interpretation of the term "set" (set = anything that is formed at some level of this hierarchy)?

Community
  • 1
djafe
  • 101
  • 5
    In The Iteractive Conception of Set (1971) George Boolos states: "We do not believe that the axioms of replacement or choice can be inferred from the iterative conception." But see George Boolos, Iteration Again (1989) for a different point of view. For another approach, see J.R.Shoenfield, Axioms of Set Theory into : Jon Barwise (editor), Handbook of Mathematical Logic (1982), page 321-on. – Mauro ALLEGRANZA Jan 11 '16 at 19:20
  • 1
    Please come up with a better title. – Asaf Karagila Jan 11 '16 at 19:27
  • The Axiom-Scheme of Replacement is an important part of 20th century foundational thinking, but most professional mathematicians have no conception whatever of what it means, when they might be using it or what a terrifyingly powerful hypothesis it is. Whilst the question as asked is very naive, it represents a valuable opportunity for logicians to try to explain what it is about. Certainly we need to keep this open. – Paul Taylor Jan 11 '16 at 19:31
  • 1
    @Paul: It seems to me that this is not the question. Rather the question is why is the axiom of choice replacement true when we consider the universe of sets described by Andreas Blass in the quoted text. – Asaf Karagila Jan 11 '16 at 19:39
  • 3
    @Paul: As for "why should we 'believe' Replacement?", this was more or less covered in the many discussions in the answers and comments of http://mathoverflow.net/questions/208711/who-needs-replacement-anyway – Asaf Karagila Jan 11 '16 at 19:41
  • 1
    Thanks to @AsafKaragila for the cross-reference, but it seems to me that Replacement is a sufficiently important and difficult issue that every opportunity to explain it is welcome. – Paul Taylor Jan 11 '16 at 19:54
  • 2
    @Paul: My point is that I think that you misread the question, and the edit exacerbates that misreading. – Asaf Karagila Jan 11 '16 at 20:00
  • @Johannes: Dude, kannste mir ma erklären, warum du das jetzt als "off-topic" deklariert hast? Der in der Frage verlinkte Thread ist doch auch auf Mathoverflow und es ist eine sehr ähnliche Frage......... – djafe Jan 12 '16 at 16:40
  • 1
    Since the OP points out that the answers given are helpful, it seems that the question was interpreted correctly by Paul Taylor and the others. In which case it should probably be closed as a duplicate to the link I provided. – Asaf Karagila Jan 12 '16 at 17:00
  • 2
    @PaulTaylor I do agree with Asaf that that edit was a bit on the presumptuous side. (I don't know that I agree with him that just because the answers were deemed 'helpful', it means your edit reflects the author's intention. On the other hand, if it does, then contra Asaf I'm not sure it duplicates David Roberts's question; I'd need to think about that more.) – Todd Trimble Jan 12 '16 at 17:40

3 Answers3

19

On the Foundations of Mathematics mailing list some years ago, Arnon Avron argued that replacement is the way mathematicians naturally construct many sets. I quote one example from his article:

When asked to write a term denoting the set of singletons of elements of $\mathbb N$, I bet that at least 999 mathematicians (either in the broad sense, including first-year students, or in a narrower sense) out of 1000 would write: $$\{\{n\}: n\in {\mathbb N}\}$$ and not $$\{x\in P(P({\mathbb N})):\exists n\in {\mathbb N}. x=\{n\}\}.$$ This is not only because the former is shorter, but because it directly translates the definition in words of this set, and precisely reflects our intuition how this set is formed/constructed. In contrast, one has to think for a while in order to get the second definition correctly (and for many students it is even difficult at first to understand why this term is a correct description of this set. Anyone who have taught a basic course in set theory or discrete mathematics has experienced this). It is clear therefore that practically everyone relies on replacement for getting this set, and not on the powerset axiom.

According to this line of thinking, replacement is an intrinsic feature of any faithful description of the universe of sets, including the cumulative hierarchy.

Timothy Chow
  • 78,129
  • 4
    Should that iterated power set be just a power set? – Steven Landsburg Jan 12 '16 at 01:16
  • 3
    @StevenLandsburg: Yes, I think so, but I'll leave it as it is because it's a quotation. – Timothy Chow Jan 12 '16 at 04:40
  • 4
    Hmm. In the standard von Neumann representation of natural numbers, $P(\mathbb N)\subseteq P(P(\mathbb N))$, so it is technically correct, but weird. – Emil Jeřábek Jan 12 '16 at 10:39
  • 3
    Technically correct - The best kind of correct ;-) – Johannes Hahn Jan 12 '16 at 18:01
  • 1
    http://www.cs.nyu.edu/pipermail/fom/2007-September/011918.html – Emil Jeřábek Jan 12 '16 at 18:07
  • @Johannes: Bring me the forms I need to fill to have you congratulated for this reference to Futurama! – Asaf Karagila Jan 12 '16 at 19:06
  • @AsafKaragila You'd need permit A38 for that. – Johannes Hahn Jan 13 '16 at 17:39
  • 1
    This answer does not convince me: after all, the “fact” that there exists a set of all sets directly translates the definition of the universe of set theory, and precisely reflects our intuition; and yet it leads to a contradiction… So, I do not think that “we tend to use the replacement axioms it spontaneously” is a good reason for believing in them! – Rémi Peyre Nov 23 '19 at 19:47
  • 1
    @RémiPeyre : What you say is true. On the other hand, it's not clear to me what more convincing answer can possibly be given to "why should I believe this axiom" than "it seems self-evident and leads to no known contradictions." (Saying that we find ourselves using it naturally is another way of saying that most people find it self-evident.) Since we're asking about an axiom we can't ask for a proof that it is correct. If this kind of justification isn't good enough then it seems to me we should just quit asking for reasons to "believe" in axioms and become formalists. – Timothy Chow Dec 16 '19 at 03:21
  • 1
    Hello! I came across the FOM post and was trying to see if anyone on MO had anything to say about it, so I found your post. I don't agree with the claim here, because clearly the sets that ordinary mathematics uses does not go beyond bounded ZFC (i.e. with Specification and Replacement restricted to bounded formulae). In particular, we can have Skolem functions witnessing Pairing and Powerset, and set-builder notation { E : x∈S ∧ Q } where E is a term with only free variable x and Q is a bounded formula, and we would be stuck in bounded ZFC but be able to do all ordinary mathematics easily. – user21820 Nov 20 '21 at 18:09
  • @user21820 The question here isn't whether unbounded replacement is needed in ordinary mathematics. It's whether mathematicians "unconsciously" construct sets using replacement. I'd claim that when mathematicians "unconsciously" use replacement, they aren't thinking about whether the formula is bounded or not. That we can recast their argument after the fact using bounded formulae is interesting, but not directly germane to the question, unless maybe you think we should never believe anything beyond the weakest axioms we need. – Timothy Chow Nov 21 '21 at 16:13
  • 1
    @TimothyChow: I don't disagree that mathematicians unconsciously use something that looks like replacement, but I disagree with saying that they unconsciously use replacement. If everything they do ends up being of the form I described, then it just shows that bounded replacement is intuitive, not that full replacement is. – user21820 Nov 21 '21 at 16:17
4

There is a wonderful blog post by Joel David Hamkins at Transfinite recursion as a fundamental principle in set theory which goes into great depth on this topic.

My answer to your question would then be "We should believe the axiom of replacement because we believe in recursion, even at the transfinite level."

Pace Nielsen
  • 18,047
  • 4
  • 72
  • 133
4

For an argument that the iterative conception implies something weaker than unrestricted Separation (implied by unrestricted Replacement), i.e. $\Sigma_2$ Replacement, see Randall Holmes 2001 http://math.boisestate.edu/~holmes/holmes/sigma1slides.ps. (According to Professor Holmes, “this contain[s] an error, which Kanamori pointed out to me and which I know how to fix.”)

Emil Jeřábek
  • 44,710
Flash Sheridan
  • 713