Due Tuesday February 12 at the beginning of lecture.
116b- Homework 4
February 4, 2008
Leave a Comment » | 
116b: Computability and incompleteness | 
Permalink
Posted by andrescaicedo
A kind of library
Andrés E. Caicedo
-
You are currently browsing the A kind of library blog archives for the day Monday, February 4th, 2008.
Recent Comments
Mathoverflow- On the structure of maximal Ramsey colorings October 25, 2021For 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, 2010Georgii: 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, 2011It 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, 2011Stefan, "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, 2010Marginalia 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
- On the structure of maximal Ramsey colorings October 25, 2021
- Math.StackExchange
- Answer by Andrés E. Caicedo for Why isn't the equal sign part of the set theory language? August 12, 2021Equality 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, 2021Gö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, 2013When 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, 2021It 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
- Answer by Andrés E. Caicedo for Why isn't the equal sign part of the set theory language? August 12, 2021
A kind of library 