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- Answer by Andrés E. Caicedo for Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper? December 23, 2014This is Theorem 39 in the paper (see Theorem 4.(i) for a user-friendly preview). But the fact that $(2^\kappa)^+\to(\kappa^+)^2_\kappa$ is older (1946) and due to Erdős, see here: Paul Erdős. Some set-theoretical properties of graphs, Univ. Nac. Tucumán. Revista A. 3 (1942), 363-367 MR0009444 (5,151d). (Anyway, it is probably easier to read a more modern pre […]Andrés E. Caicedo
- Answer by Andrés E. Caicedo for The Erdős-Turán conjecture or the Erdős' conjecture? June 3, 2013One of the best places to track these things down is The mathematical coloring book, by Alexander Soifer, Springer 2009. Chapter 35 is on "Monochromatic arithmetic progressions", and section 35.4, "Paul Erdős’s Favorite Conjecture", is on the problem you ask about. As far as I can tell, the question is sometimes called the Erdős-Turán con […]Andrés E. Caicedo
- Relative densities September 12, 2013Throughout the question, we only consider primes of the form $3k+1$. A reference for cubic reciprocity is Ireland & Rosen's A Classical Introduction to Modern Number Theory. How can I count the relative density of those $p$ (of the form $3k+1$) such that the equation $2=3x^3$ has no solutions modulo $p$? Really, even pointers on how to say anything […]Andrés E. Caicedo
- On the division paradox December 22, 2022This question is partly motivated by Timothy Chow's recent question on the division paradox. Say that a set $X$ admits a paradoxical partition if and only if there is an equivalence relation $\sim$ on $X$ such that $|X|Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Relative densities December 22, 2022A solution can be obtained as suggested by Keith Conrad in the comments, via Chebotarëv's theorem. Details can be found in $\S3.4$ of Coloring the $n$-Smooth Numbers with $n$ Colors Andrés Eduardo Caicedo, Thomas A. C. Chartier, Péter Pál Pach The Electronic Journal of Combinatorics 28 (1) (2021), #P1.34, 79 pp. DOI: https://doi.org/10.37236/8492 Many t […]Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper? December 23, 2014
- Math.StackExchange
- Answer by Andrés E. Caicedo for cardinals such that $\alpha < \alpha ^ \beta$ January 31, 2023Recall that the beth ($\beth$) numbers are defined by transfinite recursion as $\beth_0=0$, $\beth_{\alpha+1}=2^{\beth_\alpha}$ and $\beth_\lambda=\sup_{\alphaAndrés E. Caicedo
- Answer by Andrés E. Caicedo for Is it possible for a function to be smooth everywhere, analytic nowhere, yet Taylor series at any point converges in a nonzero radius? January 7, 2014No, this is not possible. Dave L. Renfro wrote an excellent historical Essay on nowhere analytic $C^\infty$ functions in two parts (with numerous references). See here: 1 (dated May 9, 2002 6:18 PM), and 2 (dated May 19, 2002 8:29 PM). As indicated in part 1, in Zygmunt Zahorski. Sur l'ensemble des points singuliers d'une fonction d'une variab […]Andrés E. Caicedo
- Answer by Andrés E. Caicedo for How to check the real analyticity of a function? December 3, 2013This is a difficult question in general. Ideally, to show that $f$ is analytic at the origin, you show that in a suitable neighborhood of $0$, the error of the $n$-th Taylor polynomial approaches $0$ as $n\to\infty$. For example, for $f(x)=\sin(x)$, any derivative of $f(x)$ is one of $\sin(x)$, $\cos(x)$, $-\sin(x)$, or $-\cos(x)$, and the error given by the […]Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Borel hierarchy doesn't "collapse" before $\omega_1$ October 1, 2013To complement Yann's answer: This is a nice problem, the possible length of Borel hierarchies in different spaces or without assuming the axiom of choice. It has been studied in detail by Arnie Miller. See Arnold W. Miller. On the length of Borel hierarchies, Ann. Math. Logic, 16 (3), (1979), 233–267. MR0548475 (80m:04003), Arnold W. Miller. Long Borel […]Andrés E. Caicedo
- Answer by Andrés E. Caicedo for consistency strength of PA September 3, 2013This is a good question, because a priori $\mathsf{PA}$ lacks the flexibility of $\mathsf{ZFC}$ that allows us to deal with consistency problems semantically (by building models) and, anyway, the obvious model of most subtheories of $\mathsf{PA}$ is just the standard model. The way this is done in the context of $\mathsf{ZFC}$ is using the reflection theorem […]Andrés E. Caicedo
- Answer by Andrés E. Caicedo for cardinals such that $\alpha < \alpha ^ \beta$ January 31, 2023
A kind of library 