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 Measure theory homework question with a set of infinite measure and subsets of finite measure. September 20, 2018
  Note first that if $C$ is uncountable and for each $i\in C$ we have a real number $r_i>0$, then $\sum_i r_i=+\infty$. The point is that for some $n>0$, the family $\{i\in C: r_i>1/n\}$ is uncountable. Of course, in this case there is a countable subfamily whose sum is infinite as well. Now, let $A$ be measurable of infinite measure. If there is an u […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for What is the utility, exactly, of the Deduction Theorem? September 19, 2018
  The theorem says that to prove an implication it is enough to assume the hypothesis and proceed to prove the conclusion. Proofs of that kind tend to be more natural than proofs that conclude the implication directly. Just as in regular mathematical practice: many theorems have the form "Assuming $A$, then we have $B$", and we usually prove them by […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Huge vs. compact cardinal September 19, 2018
  A cardinal $\kappa$ is huge if and only if it is uncountable and there is a $\kappa$-complete normal ultrafilter $\mathcal U$ over some $\mathcal P(\lambda)$ such that $\{x\in\mathcal P(\lambda)\mid \mathrm{ot}(x\cap \lambda)=\kappa\}\in\mathcal U$. The immediate advantage of this formulation over the one in terms of elementary embeddings is that it shows th […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for $n^3+n September 8, 2018
  From what you did, it suffices to show that $3k^2+3k+2\le 2\cdot 3^k$ for $k\ge 4$. It seems messy to compare the polynomial and the exponential directly, so instead let's see if we can show that $3k^2+3k+2\le 2\cdot(k^3+k)$, which will do the job. For this, note that $3\le(k-1)$, since $k\ge4$, so $3k^2+3k+2\le (k^3-k^2)+(k^2-k)+2$, and you are done, w […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Are all large cardinal axioms expressible in terms of elementary embeddings? March 27, 2013
  Not exactly. First of all, there are small large cardinals, such as inaccessible or Mahlo cardinals, for which I do not know of any natural formulation in terms of embeddings. Once we reach weakly compact cardinals, we can start expressing traditional large cardinal properties in terms of embeddings, but the models involved only satisfy fragments of $\mathsf […]
  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
- 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