13 | February | 2008 | A kind of library

116b- Homework 5

February 13, 2008

Due Tuesday February 19 at the beginning of lecture.

Leave a Comment » | 116b: Computability and incompleteness | Permalink
Posted by andrescaicedo

We showed that $\mathsf{ACA}_0$ proves the completeness theorem. We then proved the second incompleteness theorem using the result on completeness, the fact that if a model of $\mathsf{ACA}_0$ thinks that it contains a model of $\mathsf{ACA}_0$ then we can really see this latter model, and the diagonal lemma.

Leave a Comment » | 116b: Computability and incompleteness | Permalink
Posted by andrescaicedo

You are currently browsing the A kind of library blog archives for the day Wednesday, February 13th, 2008.
Categories

Categories
Search

Mathematical links
My pages
Others
Mathoverflow
- On the structure of maximal Ramsey colorings October 25, 2021
  For positive integers $a_1,\dots,a_n$, recall that the multicolor Ramsey number $R(a_1,\dots,a_n)$ is the smallest integer $N$ such that if the edges of the complete graph $K_N$ are colored with the $n$ colors $1,\dots,n$, then there is some $i\le n$ and a set of $a_i$ vertices, all of whose edges received color $i$. A maximal Ramsey$(a_1,\dots,a_n)$-colorin […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for How to rearrange only negative part of a conditionally convergent series to get any sum greater then initial? November 29, 2010
  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 […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Are there any non-linear solutions of Cauchy's equation $f(x+y)=f(x)+f(y)$ without assuming the Axiom of Choice? March 6, 2011
  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 (Intern […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Axiom of choice: ultrafilter vs. Vitali set July 6, 2011
  Stefan, "low" cardinalities do not change by passing from $L({\mathbb R})$ to $L({\mathbb R})[{\mathcal U}]$, so the answer to the second question is that the existence of a nonprincipal ultrafilter does not imply the existence of a Vitali set. More precisely: Assume determinacy in $L({\mathbb R})$. Then $2^\omega/E_0$ is a successor cardinal to ${ […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Most memorable titles October 31, 2010
  Marginalia to a theorem of Silver (see also this link) by Keith I. Devlin and R. B. Jensen, 1975. A humble title and yet, undoubtedly, one of the most important papers of all time in set theory.
  Andrés E. Caicedo
Math.StackExchange
- Answer by Andrés E. Caicedo for Why isn't the equal sign part of the set theory language? August 12, 2021
  Equality is part of the background (first-order) logic, so it is included, but there is no need to mention it. The situation is the same in many other theories. If you want to work in a language without equality, on the other hand, then this is mentioned explicitly. It is true that from extensionality (and logical axioms), one can prove that two sets are equ […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Well-ordering of the reals in ZF with constructibility? April 19, 2018
  $L$ has such a nice canonical structure that one can use it to define a global well-ordering. That is, there is a formula $\phi(u,v)$ that (provably in $\mathsf{ZF}$) well-orders all of $L$, so that its restriction to any specific set $A$ in $L$ is a set well-ordering of $A$. The well-ordering $\varphi$ you are asking about can be obtained as the restriction […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Incompleteness in reverse July 7, 2021
  Gödel sentences are by construction $\Pi^0_1$ statements, that is, they have the form "for all $n$ ...", where ... is a recursive statement (think "a statement that a computer can decide"). For instance, the typical Gödel sentence for a system $T$ coming from the second incompleteness theorem says that "for all $n$ that code a proof […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Is there an idempotent element in a finite semigroup? April 9, 2013
  When I first saw the question, I remembered there was a proof on MO using Ramsey theory, but couldn't remember how the argument went, so I came up with the following, that I first posted as a comment: A cute proof using Schur's theorem: Fix $a$ in your semigroup $S$, and color $n$ and $m$ with the same color whenever $a^n=a^m$. By Schur's theo […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for MSC of Point Set Topology (Mathematical Subject Classification) February 20, 2021
  It depends on what you are doing. I assume by lower level you really mean high level, or general, or 2-digit class. In that case, 54 is general topology, 26 is real functions, 03 is mathematical logic and foundations. "Point-set topology" most likely refers to the stuff in 54, or to the theory of Baire functions, as in 26A21, or to descriptive set […]
  Andrés E. Caicedo
February 2008

M T W T F S S

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

« Jan Mar »
Archives
- June 2019 (2)
- February 2019 (7)
- December 2018 (1)
- 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 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 Paul Larson 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

	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …
	Anthea M. on No durians
	580 -Some choiceless… on 580 -Some choiceless results…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…

A kind of library

116b- Homework 5

116b- Lecture 10

Categories

Recent Comments

Mathematical links

My pages

Others

Mathoverflow

Math.StackExchange

Archives