Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What is the shortest formal statement you can write that is provably equivalent to the Continuum Hypothesis in ZFC?

Please use only variables and the following symbols: $\forall, \exists,\lor,\land,\neg,\to, \in,=$ (parentheses may be added for convenience and do not contribute to the length of the formula). For example, symbols and expressions like $\subset,\emptyset,\{\dots\},\aleph_0,\mathcal{P}(x)$ are not allowed for purposes of this problem. Please give references if equivalence of your statement with $CH$ is not immediately obvious.

share|improve this question
21  
Why does it matter? –  François G. Dorais Dec 3 '11 at 7:43
2  
I agree that some motivation for this question would be useful. For example, if you are really asking about defining $\aleph_1$ simply then there are various equivalents of CH that do not need this. –  Juris Steprans Dec 3 '11 at 12:35
3  
When asking this question, I hoped that there is a particularly nice and short formulation that can help me to build better intuition about CH. –  Vladimir Reshetnikov Dec 3 '11 at 21:04
12  
Vladimir, such a motivation seems misguided; it would be like trying to understand how an algorithm works by looking only at the shortest possible version of it in assembly language. Of course, one wants to think about it instead in terms of higher-level defined concepts, and there is no reason not to do so. I discuss a similar issue in mathoverflow.net/questions/12370/…. –  Joel David Hamkins Dec 3 '11 at 23:11
2  
I have to fight with all my might to not post "Your Mom." –  Michael Blackmon Dec 10 '11 at 5:22
show 4 more comments

1 Answer

up vote 6 down vote accepted

I don't know if this is the shortest (number of symbols?) but in

D. Scott, "A Proof of the Independence of the Continuum Hypothesis", THEORY OF COMPUTING SYSTEMS, Volume 1, Number 2. Available at: http://www.springerlink.com/content/hh339022jt1m5183/

there is (at the bottom of page 1) a concise formulation of CH. The sentence actually uses the symbol $\mathbb{N}$ for the natural numbers, but you can get rid of it of course.

share|improve this answer
2  
Scott's sentence involves quantifiers $\forall X$ and $\forall f$. He explains in the preceding paragraph that $X$ is understood to be a subset of $\mathbb{R}$, and $f$ is understood to be a function $\mathbb{R}\to\mathbb{R}$. If these assumptions were made explicit then the sentence would become very much longer. –  Neil Strickland Dec 3 '11 at 11:14
1  
Yes sure, you are right. Scott's also goes on in the second page explaining how to use less concepts (subsets of reals can be seen as f:R->{0,1}, etc). But it is true this is not a direct answer to Vladimir's question. –  Matteo Mio Dec 3 '11 at 13:10
1  
Neil, please note Dana Scott is a lady :-) –  Tomek Kania Dec 4 '11 at 19:39
4  
en.wikipedia.org/wiki/Dana_Scott –  Matteo Mio Dec 4 '11 at 20:41
7  
Since I sometimes read comments but don't bother to follow links (usually for lack of time), I fear Tomek Kania's comment might confuse people despite Matteo Mio's correction. So let me repeat the correction without links: Dana Scott is male. –  Andreas Blass Dec 5 '11 at 0:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.