Will Sladek, a student at Caltech, wrote an excellent introductory paper on incompleteness in PA, The termite and the tower. While Will was working on his paper, I wrote a short note, Goodstein’s function, on how to compute Goodstein’s function. Please let me know of any comments of corrections to either article.

[…] a nice introduction to incompleteness and Goodstein’s theorem, see Will Sladek’s paper here. Possibly related posts: (automatically generated)Partitioning numbersUS concerns of decline in […]

[…] (an undergraduate student of mine at Caltech wrote a nice paper on this a few years ago, “The termite and the tower.“). There are others. A nice one is about a game, Hercules and the […]

The argument you are looking for is given in Kanamori's book, see Theorem 28.15. For the more nuanced version of the lemma, see section 7D in Moschovakis's descriptive set theory book (particularly 7.D.5-8), or section 3.1 in the Koellner-Woodin chapter of the Handbook.

This problem is very much open. Cheng Yong calls Harrington's $\star$ the assumption that there is a real $x$ such that all $x$-admissible ordinals are $L$-cardinals. From the work of Yong we know that Second- and even Third-order arithmetic do not suffice to prove that Harrington's $\star$ implies the existence of $0^\sharp$. Whether this was poss […]

Georgii: Let me start with some brief remarks. In a series of three papers: a. Wacław Sierpiński, "Contribution à la théorie des séries divergentes", Comp. Rend. Soc. Sci. Varsovie 3 (1910) 89–93 (in Polish). b. Wacław Sierpiński, "Remarque sur la théorème de Riemann relatif aux séries semi-convergentes", Prac. Mat. Fiz. XXI (1910) 17–20 […]

What precisely do you mean by a standard model? An $\omega$-model? (That is, a model whose set of natural numbers is isomorphic to $\omega$.) Or a $\beta$-model? (That is, a model whose ordinals are well-ordered.) If the latter, the Mostowski collapse theorem tells us any such model is isomorphic in a unique way to a unique transitive model. If the former, t […]

This is Theorem 39 in the paper (see Theorem 4.(i) for a user-friendly preview). But the fact that $(2^\kappa)^+\to(\kappa^+)^2_\kappa$ is older (1946) and due to Erdős, see here: Paul Erdős. Some set-theoretical properties of graphs, Univ. Nac. Tucumán. Revista A. 3 (1942), 363-367 MR5,151d. (Anyway, it is probably easier to read a more modern presentation, […]

It is not possible to give a finitary proof of this fact. Consider, for instance, the statement that all Goodstein sequences terminate. This is an arithmetic claim, it is independent of $\mathsf{PA}$, and it is equivalent to the claim that some (very specific) computable non-increasing sequences of polynomial towers stabilize. Instead of Goodstein sequences, […]

Given any field automorphism of $\mathbb C$, the rational numbers are fixed. In fact, any number that is explicitly definable in $\mathbb C$ (in the first order language of fields) is fixed. (Actually, this means that we can only ensure that the rationals are fixed, I expand on this below.) Any construction of a wild automorphism uses the axiom of choice. Se […]

A proof can be found in Kanamori's book The higher infinite. The result follows from work of Solovay on the theory of uniform indiscernibles and work of Martin on projective scales. Look at sections 14, 28, and 30 of the book. A different approach (using the infinite partition properties of $\omega_1$ and $\omega_2$, themselves due to Solovay and Martin […]

Forcing with sufficiently homogeneous forcing that adds reals is enough to obtain the negation of $(*)$. The point is that if a formula $\phi$ defines a parameter-free well-ordering of $\mathbb R$, then for any ordinal $\alpha$, the statement "$x$ is the $\alpha$-th real in the well-ordering defined by $\phi$" uniquely characterizes $x$ in terms of […]

Assuming that $\gamma$ is finite, the argument is fairly simple: Suppose $\beta\to(\alpha)^\gamma_\delta$, and fix a bijection $f$ between $|\beta|$ and $\beta$. Consider a coloring $c:[|\beta|]^\gamma\to\delta$. Using $f$ , this gives us a coloring $c':[\beta]^\gamma\to\delta$ (here we used that $\gamma$ is finite). We want to argue that there is a $c$ […]

[…] a nice introduction to incompleteness and Goodstein’s theorem, see Will Sladek’s paper here. Possibly related posts: (automatically generated)Partitioning numbersUS concerns of decline in […]

[…] (an undergraduate student of mine at Caltech wrote a nice paper on this a few years ago, “The termite and the tower.“). There are others. A nice one is about a game, Hercules and the […]