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 […]

I am looking for references discussing two inequalities that come up in the study of the dynamics of Newton's method on real-valued polynomials (in one variable). The inequalities are fairly different, but it seems to make sense to ask about both of them in the same post. Most of the details below are fairly elementary, they are mostly included for comp […]

Let $C$ be the standard Cantor middle-third set. As a consequence of the Baire category theorem, there are numbers $r$ such that $C+r$ consists solely of irrational numbers, see here. What would be an explicit example of a number $r$ with this property? Short of an explicit example, are there any references addressing this question? A natural approach would […]

Not necessarily. That $\mathfrak m$ is consistently singular is proved in MR0947850 (89m:03045) Kunen, Kenneth. Where $\mathsf{MA}$ first fails. J. Symbolic Logic 53(2), (1988), 429–433. There, Ken shows that $\mathfrak{m}$ can be singular of cofinality $\omega_1$. (Both links above are behind paywalls.)

Ignas: It is not possible to provide an explicit expression for a non-linear solution. The reason is that (it is a folklore result that) an additive $f:{\mathbb R}\to{\mathbb R}$ is linear iff it is measurable. (This result can be found in a variety of places, it is a standard exercise in measure theory books. As of this writing, there is a short proof here. […]

MR2449474 (2009j:03067) Woodin, W. Hugh. A tt version of the Posner-Robinson theorem. Computational prospects of infinity. Part II. Presented talks, 355–392, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., 15, World Sci. Publ., Hackensack, NJ, 2008. The proof is nice, invoking both recursion-theoretic and set-theoretic tools. Hugh uses a Prikry-like f […]

There is a general argument without choice: Suppose ${\mathfrak m}+{\mathfrak m}={\mathfrak m}$, and ${\mathfrak m}+{\mathfrak n}=2^{\mathfrak m}$. Then ${\mathfrak n}=2^{\mathfrak m}.\,$ This gives the result. The argument is part of a nice result of Specker showing that if CH holds for both a cardinal ${\mathfrak m}$ and its power set $2^{\mathfrak m}$, th […]

By Fermat's little theorem, $t^p\equiv t\pmod p$ for any $t$, so if $p\mid x^p+y^p$ then in fact $p\mid x+y$ (or $y\equiv -x\pmod p$). Now, since $p$ is odd, $$x^p+y^p=(x+y)(x^{p-1}-x^{p-2}y+x^{p-3}y^2-\cdots+y^{p-1}).$$ The first term is a multiple of $p$, as explained above. The second is $$\sum_{k=0}^{p-1}(-1)^k x^{p-1-k}y^k=\sum_{k=0}^{p-1}x^{p-1-k} […]

Your idea is sound, but it requires more work. As pointed out, you have only described so far a very small subcollection of the Borel sets. Instead, show that you can associate to each Borel set a code that keeps track of the "history" of its construction starting from basic open sets, and then count the number of such codes. There is a lot of leew […]

Recently, I was reading Hardy's Orders of Infinity (available here or here): Godfrey Harold Hardy. Orders of infinity. The Infinitärcalcül of Paul du Bois-Reymond. Reprint of the 1910 edition. Cambridge Tracts in Mathematics and Mathematical Physics, No. 12. Hafner Publishing Co., New York, 1971. MR0349922 (50 #2415). The book discusses this result, so […]

[…] 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 […]