2

Wiki says that Goodstein's theorem is provable in ZF, since we have ordinal theory in ZF.

My question is, is the axiom of replacement necessary in the proof? (which is the only axiom that occurs in ZF but not in Z) Could we construct the whole ordinal theory without the axiom schema of replacement?

user65526
  • 1,373
Minghui Ouyang
  • 924

1 Answers1

6

The axiom of replacement is not necessary for the proof. The axiom of replacement is needed for certain aspects of the theory of the ordinals, but the proof of Goodstein's theorem just needs a certain relatively small countable well-ordered set, which can be done in Z using a certain well-ordering of the natural numbers.

To explain a little more, the axiom of replacement is needed to construct the von Neumann ordinal associated to any well-ordered set. The von Neumann ordinals are defined so that each ordinal is the set of all the previous ordinals, so that the order relation on them is just the element relation $\in$. This is useful for various technical purposes, but is not at all necessary for most applications of ordinals, since usually all you need is a well-ordered set with a desired isomorphism type. The axiom of replacement is also needed to construct certain very large (from the perspective of "ordinary" mathematics) sets that are needed in certain arguments. For instance, you can't prove that $\mathbb{N}\cup\mathcal{P}(\mathbb{N})\cup\mathcal{P}(\mathcal{P}(\mathbb{N}))\cup\dots$ is a set without repacement. Nothing of this sort is needed for Goodstein's theorem or most other applications of ordinals, though.

Eric Wofsey
  • 330,363
  • "relatively small" you mean the ordinal type of the well-ordered set is less than the first fixed point of $\epsilon : \alpha \to \omega ^ \alpha$? – Minghui Ouyang Jun 12 '17 at 07:29
  • @Minghui No, of course not. – Andrés E. Caicedo Jun 12 '17 at 11:35
  • @AndrésE.Caicedo So what's your understanding? In Eric's answer, He mentioned that actually we don't need the corresponding ordinals of the Goodstein sequences but a well-ordered set isomorphic to it. Also, the first "unconsturctable" order type in Z is the first fixed point $\epsilon_0$ of $\epsilon$. That's what I thought. – Minghui Ouyang Jun 12 '17 at 14:39
  • 1
    @MinghuiOuyang Goodstein's theorem can be proved in a mild extension of Peano Arithmetic. No set theory is needed. – Andrés E. Caicedo Jun 12 '17 at 14:51
  • @AndrésE.Caicedo You mean we don't need ordinals in the proof of Goodstein's theorem at all? – Minghui Ouyang Jun 12 '17 at 15:36
  • @MinghuiOuyang: Yes, I was referring to a well-ordered set of order-type $\epsilon_0$. Such a well-ordered set is easy to construct in Z; indeed, Z can construct much much longer well-ordered sets (uncountable well-ordered sets, for instance). – Eric Wofsey Jun 12 '17 at 15:49
  • @EricWofsey Thanks for your answer. By the way I don't know how to construct a well-ordered set of order-type great than or equal to $\epsilon_0$ or furthermore some uncountable order-types. Could you give a short overview? – Minghui Ouyang Jun 12 '17 at 16:34
  • It's difficult to provide an overview that would be helpful without knowing what you do or don't know. Are you familiar with the general theory of well-ordered sets? Do you know how to construct a well-ordered set of order-type $\omega^\omega$, for instance? I would suggest you ask that question as a new question, including information about your background to help answerers give an answer at the appropriate level. – Eric Wofsey Jun 12 '17 at 16:55
  • @EricWofsey Okey, thanks for your advice. – Minghui Ouyang Jun 13 '17 at 16:30