July | 2007 | A kind of library

Goodstein sequences

July 27, 2007

Will Sladek, a student at Caltech, wrote an excellent introductory paper on incompleteness in $\mathsf{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.

Update: My paper has been published.

Goodstein’s function. Revista Colombiana de Matemáticas 41 (2)(2007), 381–391. MR2585906 (2011c:03139). Zbl 1156.03053.

Advertisements

2 Comments | 116b: Computability and incompleteness | Tagged: Goodstein's function, Undecidability and incompleteness | Permalink
Posted by andrescaicedo

You are currently browsing the A kind of library blog archives for July, 2007.
Categories

Categories
Search

Mathematical links
My pages
Others
Mathoverflow
- Answer by Andrés E. Caicedo for Strong partition property + DC + existence of non-principal ultrafilter on $\omega$ August 30, 2018
  The key reference for this is MR0799042 (87d:03141). Henle, J. M.; Mathias, A. R. D.; Woodin, W. Hugh. A barren extension. In Methods in mathematical logic (Caracas, 1983), C. A. Di Prisco, editor, 195–207, Lecture Notes in Math., 1130, Springer, Berlin, 1985. There, Henle, Mathias, and Woodin start with $L(\mathbb R)$ under the assumption of determinacy (an […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Can we have an infinite sequence of decreasing cardinality all terms of which have equal sized power sets? August 12, 2018
  This is consistent, at least under a rather tame large cardinal assumption. (One can also produce examples by manipulating Dedekind finite sets, but Asaf's answer addresses this. The answer here works even in the context of $\mathsf{DC}$.) For instance, see MR3612001. Conley, Clinton T.; Miller, Benjamin D. Measure reducibility of countable Borel equiva […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Are there known examples of sets whose power set is equal in size to power set of larger sets only in absence of choice? August 11, 2018
  Let me add some comments to Asaf's answer. We are looking for situations with $|X|
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Is $Z_3+{\rm AD}$ equiconsistent with $\text{ZFC+AD}^{L(\mathbb{R})}$ May 10, 2018
  The only reference I know for precisely these matters is the handbook chapter MR2768702. Koellner, Peter; Woodin, W. Hugh. Large cardinals from determinacy. In Handbook of set theory. Vols. 1, 2, 3, 1951–2119, Springer, Dordrecht, 2010. (Particularly, section 7.) For closely related topics, see also the work of Yong Cheng (and of Cheng and Schindler) on Harr […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Does constructing non-measurable sets require the axiom of choice? October 14, 2010
  As other answers point out, yes, one needs choice. The popular/natural examples of models of ZF+DC where all sets of reals are measurable are models of determinacy, and Solovay's model. They are related in deep ways, actually, through large cardinals. (Under enough large cardinals, $L({\mathbb R})$ of $V$ is a model of determinacy and (something stronge […]
  Andrés E. Caicedo
Math.StackExchange
- Answer by Andrés E. Caicedo for Do we know that we can't define a well-ordering of the reals? June 7, 2015
  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 […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for What sets are obtained by adding $\aleph_1$ unions and intersections to the Borel algebra? October 25, 2018
  This is an excellent question! Note first that, just from cardinal arithmetic considerations, whether we obtain all sets is independent (and therefore so is whether we obtain all Lebesgue measurable sets). The right context to study this question is descriptive set theory, and indeed the problem was considered early on. For example, Sierpiński proved in Sur […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Measure on ([0,1], P([0,1])) October 17, 2018
  Surprisingly, the answer is no due to serious set-theoretic restrictions. If $X$ is an infinite set such that there is a ($\sigma$-additive) measure on $\mathcal P(X)$ that only takes the values 0 and 1, assigns 1 to $X$ and 0 to singletons, then the cardinality $\kappa=|X|$ of $X$ is much much larger than $\mathfrak c=|\mathbb R|$, the cardinality of the se […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Without the Axiom of Choice, must two nonempty sets have a surjection between them? October 9, 2018
  No, you cannot show this. For instance, it is consistent to have infinite Dedekind-finite sets whose power set is still Dedekind-finite. Now, if there is a surjection from $A$ to $\omega$, then there is an injection from $\omega$ (indeed, from $\mathcal P(\omega)$) to $\mathcal P(A)$, so $\mathcal P(A)$ is Dedekind-infinite. Thus, if $\mathcal P(X)$ is infin […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Example of a concrete irrationality test October 7, 2018
  First, there are some nice examples like $$ e=\sum_{n\ge0}\frac1{n!} $$ or Liouville-like numbers, mentioned in the answers by Wilem2, that can be easily proved to be irrational using the theorem, but for which typically there are simpler irrationality proofs: For $e$, we quickly get that $$0
  Andrés E. Caicedo
July 2007

M T W T F S S

« Mar Sep »

1

2 3 4 5 6 7 8

9 10 11 12 13 14 15

16 17 18 19 20 21 22

23 24 25 26 27 28 29

30 31
Archives
- October 2018 (2)
- August 2018 (1)
- February 2018 (1)
- October 2017 (1)
- July 2017 (1)
- September 2016 (2)
- August 2016 (3)
- July 2016 (2)
- April 2016 (1)
- October 2015 (1)
- June 2015 (1)
- May 2015 (1)
- April 2015 (7)
- March 2015 (5)
- February 2015 (7)
- January 2015 (11)
- December 2014 (2)
- November 2014 (5)
- October 2014 (6)
- September 2014 (3)
- August 2014 (3)
- April 2014 (3)
- March 2014 (5)
- February 2014 (2)
- January 2014 (2)
- December 2013 (2)
- November 2013 (10)
- October 2013 (6)
- September 2013 (7)
- August 2013 (5)
- June 2013 (1)
- May 2013 (8)
- April 2013 (7)
- March 2013 (5)
- February 2013 (9)
- January 2013 (2)
- November 2012 (1)
- September 2012 (1)
- August 2012 (3)
- May 2012 (3)
- April 2012 (10)
- March 2012 (4)
- February 2012 (13)
- January 2012 (15)
- November 2011 (8)
- October 2011 (14)
- September 2011 (7)
- August 2011 (1)
- April 2011 (1)
- March 2011 (3)
- February 2011 (4)
- January 2011 (7)
- December 2010 (1)
- November 2010 (7)
- October 2010 (12)
- September 2010 (13)
- August 2010 (3)
- May 2010 (4)
- April 2010 (11)
- March 2010 (6)
- February 2010 (12)
- December 2009 (9)
- November 2009 (11)
- October 2009 (13)
- September 2009 (19)
- August 2009 (10)
- June 2009 (1)
- May 2009 (2)
- April 2009 (14)
- March 2009 (17)
- February 2009 (19)
- January 2009 (15)
- December 2008 (5)
- November 2008 (12)
- October 2008 (17)
- September 2008 (10)
- August 2008 (3)
- June 2008 (3)
- May 2008 (15)
- April 2008 (21)
- March 2008 (10)
- February 2008 (13)
- January 2008 (11)
- September 2007 (1)
- July 2007 (1)
- March 2007 (4)
- February 2007 (20)
- January 2007 (23)
- December 2006 (4)
Alan Turing Alexander S. Kechris Alfred Tarski algebraic numbers Andras Hajnal Andreas Blass Andrew Michael Bruckner arithmetic mean-geometric mean inequality Arnoud C. M. van Rooij Augustin Cauchy Axel Thue Bernhard Riemann BEST bpfa Bukovsky-Hechler theorem compactness completeness covering property determinacy Donald A. Martin elementary embedding Emile Borel Euclidean algorithm extension field field field extension Francisco Frank Plumpton Ramsey Fred Galvin Galvin-Hajnal theorem GCH Georg Cantor Godfrey Harold Hardy Grigor Sargsyan Harvey Friedman ideal Isaac Newton James Baumgartner Jerome Keisler Johan Thim John R. Steel Karl Theodor Wilhelm Weierstrass Koenig's lemma Kurt Goedel Lech Maligranda Marion Scheepers measurable cardinal Menachem Magidor midterm mm Nowhere differentiable function Paul Erdos pfa propositional logic quartic equation Ramsey theorem Rene Baire Richard Rado Robert Solovay Saharon Shelah Samuel Coskey sch Silver's theorem Stefan Banach Stevo Todorcevic supercompact cardinals Tarski's conjecture Turing degrees ultrafilter ultrapower Undecidability and incompleteness Unsolvable problems W. Hugh Woodin Wacław Franciszek Sierpiński Wilhelmus Hendricus Schikhof

Advertisements