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

Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC."

For example, suppose A is an abelian group such that every short exact sequence of abelian groups 0→ℤ→B→A→0 splits. Does it follow that A is free? This is known as Whitehead's Problem, and it's undecidable in ZFC.

What are some other statements that aren't directly set-theoretic, and you'd think that playing with them for a week would produce a proof or counterexample, but they turn out to be undecidable? One answer per post, please, and include a reference if possible.

share|improve this question
1  
I think this is a very good question, but the example given doesn't seem particularly outside of normal logic intuition. When you say the group is "free" it means "it can be proven that there exists a basis B such that..." so surely you need find that specific B --- that really can't follow from a description like you gave without some mechanism! –  Ilya Nikokoshev Oct 22 '09 at 21:41
1  
@ilya: I don't understand your objection to the example. The statement is that Whitehead's problem is independent of ZFC (which allows you to do things like chose elements of sets, and lots of other constructions). I agree it would be silly to say that it's independent of the empty list of axioms. –  Anton Geraschenko Oct 22 '09 at 21:49
    
Mm, I think I misunderstood what ZFC is. I wanted to point out that axiom of choice (or something) should be necessary which was obvious to the asker from the start. Apologies. –  Ilya Nikokoshev Oct 22 '09 at 22:10

26 Answers 26

"If a set X is smaller in cardinality than another set Y, then X has fewer subsets than Y."

Althought the statement sounds obvious, it is actually independent of ZFC. The statement follows from the Generalized Continuum Hypothesis, but there are models of ZFC having counterexamples, even in relatively concrete cases, where X is the natural numbers and Y is a certain uncountable set of real numbers (but nevertheless the powersets P(X) and P(Y) can be put in bijective correspondence). This situation occurs under Martin's Axiom, when CH fails.

share|improve this answer
53  
This blows my mind. –  Charles May 31 '10 at 17:29
6  
Wow! Is this a good argument for believing in GCH? –  Mozibur Ullah Dec 3 '12 at 13:14
    
@Joel Can I get a reference for this? In particular what is the meaning of 'fewer' in the statement? Does this hold because of some 'weird' failures of separation, i.e. it is unable to 'create' subsets where we normally would expect it to? I agree with Charles, this is mind-bending to say the least, and makes me doubt the conceptual robustness of ZFC, especially since it is supposed to be so good at giving us a theory of 'size'... –  Chuck Dec 31 '12 at 17:30
9  
I had meant "fewer" in the sense of cardinality. In other words, the question is whether $\kappa\lt\lambda$ implies $2^\kappa\lt 2^\lambda$. The answer is that this is independent of ZFC. It is consistent with ZFC, for example, that the power set $P(\mathbb{N})$ is bijective with $P(Y)$ for some uncountable set $Y$, such as $Y=\omega_1$. Indeed, the assertion that $2^\omega=2^{\omega_1}$ is known as Luzin's hypothesis. As for a reference, this is covered in any good graduate set theory text book, such as Jech's book Set Theory. –  Joel David Hamkins Dec 31 '12 at 18:05
    
The statement is equivalent to what is known as the "Weak GCH", which asserts $2^\lambda<2^{\lambda^+}$ for every infinite cardinal. For a viewpoint in favor of the axiom, see Baldwin's slides, "Why the Weak GCH is True!" homepages.math.uic.edu/~jbaldwin/asl07.pdf. –  Joel David Hamkins Oct 12 at 11:31

UPDATE: I edited the answer by adding details and adding a reference. In particular, I specialized from an arbitrary field to the complex numbers in response to John's comment.

Here's an example from commutative algebra. The projective dimension of a module M is defined as the minimal length of a projective resolution of M. Let S be the ring ℂ[x,y,z] and M be the module ℂ(x,y,z). Then the projective dimension of M is undecidable in ZFC. More specifically, the projective dimension of M is 2 if the continuum hypothesis holds, and it is 3 if the continuum hypothesis fails.

This follows from Barbara Osofsky's work (MR0548131); see Theorem 2.51 of Homological Dimensions of Modules. She seems to have a huge number of results which would be relevant to this question.

share|improve this answer
    
That's bizarre. If somebody tracks down a reference, I'd be curious to know: is this true for any field k? What kind of bounds on the projective dimension can you prove in ZFC? –  John Goodrick Oct 23 '09 at 13:11
13  
It has to do with the cardinality of the field. In his book Basic Homological Algebra, Scott Osbourne proves that a module generated by \aleph_m elements has projective dimension at most m+n+1, where n is the maximum projective dimension of a finitely generated submodule. What's going on here is that these modules are disgustingly infinitely generated. Something generated by \aleph_m elements can be written as a direct limit of a chain of things generated by \aleph_{m-1} elements, and you use that and induction on m to prove it. –  Eric Wofsey Oct 23 '09 at 21:02
1  
Interesting, thanks for the reference. –  John Goodrick Oct 24 '09 at 15:20

re:

Here's an example from commutative algebra. [C = complex numbers] let S be the ring C[x,y,z] and M be the module C(x,y,z). Then the projective dimension of M is 2 if the continuum hypothesis holds, and it is 3 if the continuum hypothesis fails.

Drinfeld has pointed out (see http://arxiv.org/abs/math/0309155v4 ) that the set-theoretic problems are coming from using the wrong definition of "projective". Raynaud and Gruson proved that projectivity of a module M is equivalent to the combination of three conditions:

(1) flatness

(2) decomposition as a direct sum of countably generated modules

(3) Mittag-Leffler condition

That (2) is possible for projective modules is a theorem of Kaplansky but the decomposition is non-canonical, and this is what introduces the axiom of choice into the proof of "free implies projective".

As I understood it from Drinfeld's lecture, only (1) and (3) are necessary for applications and for developing homological algebra, and (2) is undesirable because it is too strong a condition when working with infinite dimensional bundles. He proposed either "flat and Mittag-Leffler" directly, or a minor variant of that, as a definition of what he called "projectivity with a human face", that would work smoothly in the existing applications and allow a reasonable generalization to the infinite dimensional case.

Also, (1) and (3) are definable in first-order logic, so there is less chance of set theoretic problems from quantification over large or complicated structures.

share|improve this answer

If X is a compact Hausdorff space, and f is an algebra homomorphism from C(X) to some Banach Algebra, must f be continuous?

This question turns out to be independent. The affirmative answer is referred to as Kaplansky's Conjecture.

share|improve this answer
1  
Wow! (Just unbelievable :-). –  Włodzimierz Holsztyński May 16 '13 at 8:51

"There is no definable well-ordering of the real numbers."

Although many mathematicians simply believe this statement to be true, actually, it is independent of ZFC. In Goedel's constructible universe L, for example, there is a definable well-ordering of the reals, having complexity Delta^1_2 in the descriptive set-theoretic hierarchy. That is, the well-ordering is a subset of the plane RxR, and it is the projection of the complement of the projection of a Borel set (and simultaneously, the complement of another such set).

The idea that well-orders of the reals cannot in principle be described or constructed is simply not correct.

share|improve this answer
6  
I think this misconception comes down partly to a difference between formal and informal usage. To “construct a widget W with property P” often covers (informally) not just the construction of W, but also the proof of P for it. In this sense, it is indeed impossible to construct a w-o of the reals in ZFC, by the very independence result you give. –  Peter LeFanu Lumsdaine Sep 22 '10 at 14:15
    
To Peter LeFanu Lumsdaine: can you at least construct a widget W that we can prove is a well-ordering of reals if there exists at least one well-ordering? That's the case we have with P!=NP: we can give a concrete algorithm that we can prove solves an NP-complete problem if P=NP. –  Zsbán Ambrus Aug 16 '11 at 9:02
3  
Zsbán, we can prove in ZFC that there is a well-ordering. So the issue isn't existence of the well-ordering, but rather the question of whether there is a definable such well-ordering. It is consistent with ZFC that there is a very low complexity definition, and it also follows from large cardinals thought to be consistent that there is no definable such ordering anywhere in the projective hierarchy. Meanwhile, there is a particular universal definition $\varphi$ in set theory, such that any universe of set theory can be extended to one where $\varphi$ defines a well-ordering of $\mathbb{R}$. –  Joel David Hamkins Aug 16 '11 at 11:11

My favourite is the statement that if X is a set of reals, and for every sequence (a_n) of positive reals you can find a sequence of intervals (I_n) that cover X such that I_n has length at most a_n, then X is countable. I think it's of a similar strength to Martin's axiom.

share|improve this answer
13  
A set of reals with this property is usuall called strong measure zero. The question of whether such have to be countable is called the Borel Conjecture. It was first proven independent by Laver. –  Richard Dore Oct 23 '09 at 14:08
9  
@gowers : I am not sure what you mean by "of similar strength to Martin's axiom". Would you mind briefly commenting on this? –  Andres Caicedo Dec 6 '10 at 17:30
3  
(Since this was not addressed: Martin's axiom is equiconsistent with $\mathsf{ZFC}$, as is this statement, so the mention of Martin's axiom and strength is a distraction, if by strength we mean consistency strength, which is the common usage. If what is meant is that the Borel conjecture is about as useful in terms of consequences as Martin's axiom, I disagree strongly.) –  Andres Caicedo Jun 29 '13 at 4:43
    
@AndresCaicedo: I think he meant Martin's Axiom (MA) implies a counterexample. As for the other direction: A counterexample follows from axioms that are very incompatible with MA. But there are some consequences of existence and of nonexistence of counterexamples of the behavior of cardinals of the continuum. –  Boaz Tsaban Apr 24 at 21:17

This isn't an answer but an argument that there isn't really a good answer. Having done a good amount of set theory and seen how you prove some of these statements to be independent, I tend to be rather skeptical about how reasonable these statements actually sound. Typically, while these statements sound like they're talking about some ordinary mathematical object, they aren't really, because their independence comes from very large and pathological objects that are far removed from your usual mathematical experience.

For example, in the Whitehead problem, you have to realize that while abelian groups sound very down-to-earth, uncountable abelian groups can have incredibly complicated structure. As a (fairly difficult!) exercise, you can prove that a countable product Z^N of copies of Z is not free, and in fact admits no homomorphism to Z besides the obvious finite sums of projections. On the other hand, the Whitehead problem has an affirmative answer if you restrict to countable groups, and this is something you could come up with if you thought about it for a week.

share|improve this answer
4  
There's a big difference between "We don't know if there are pathological groups," and "We provably can't know if there are pathological groups." There are lots of places where things get complicated, and people either prove theorems or find counterexamples. And in most cases we just kind of assume on or the other of those is possible. It's substantially different to know that is a hopeless process. –  Richard Dore Oct 23 '09 at 0:16
1  
I guess my point is that most of the time you can't prove things when you're dealing with things that are complicated because they are very infinite. That is, when I see this kind of problem, I don't assume you can solve it. This might just be because I've done too much set theory. –  Eric Wofsey Oct 23 '09 at 0:53
    
This makes a lot of sense to me,say, in the context of Whitehead's problem. But I cannot, for instance, understand how Harvey Friedman's example could be a fact about large cardinals in disguise. It would be great if you could explain more. –  Keivan Karai Jul 4 '10 at 11:02

Harvey Friedman has devoted a large portion of his career to finding "natural" statements that are unprovable in ZFC. One example is given at the end of Martin Davis's article "The incompleteness theorem," Notices AMS 53 (2006), 414-418:

http://www.ams.org/notices/200604/fea-davis.pdf

It takes a paragraph or so to state the definitions so I won't do so here, but the point is that, unlike many other examples, which clearly make reference to uncountable sets or are just Goedelian diagonalization statements in disguise, Friedman's proposition is a purely finitary statement in graph theory whose statement gives no hint of large cardinals. Indeed it is a small perturbation of a graph-theoretical theorem with an elementary proof.

For another example of Friedman's work, see his book Boolean Relation Theory and Incompleteness, a draft of which is downloadable from his website:

https://u.osu.edu/friedman.8/foundational-adventures/boolean-relation-theory-book/

Here Friedman presents a family of innocuous-looking elementary statements about functions and sets and unions/intersections/complements. Almost all statements in the family have easy proofs in ZFC (or actually much weaker systems), but one of them requires a large cardinal axiom.

Friedman is aware that these examples don't quite reach the holy grail of a completely natural finitary mathematical statement that is independent of ZFC, but he continues to make progress in this direction. You can subscribe to the Foundations of Mathematics mailing list if you want to keep track of his latest results.

share|improve this answer

One of my favourites is

"Three clouds cover the plane"

where a subset $A \subseteq \mathbb{R}^2$ is a cloud around $a$ if every line through $a$ has a finite intersection with $A$.

This is due to Péter Komjáth; see http://www.cs.elte.hu/~kope/p28.ps.

In fact, three clouds cover the plane if and only if CH is true.

If the continuum is at most $\aleph_n$, then you can cover the plane with $n+2$ clouds (whether the reverse holds is open) (see comments).

share|improve this answer
3  
Actually it looks like the reverse is not open any longer: helios.impan.gov.pl/cgi-bin/fm/pdf?fm177-3-02 –  Justin Palumbo Jul 5 '10 at 4:13
2  
My friend Ramiro de la Vega recently obtained a result for a related concept. A spray centered at $c$ is a subset of the plane that meets every circle centered at $c$ in only finitely many points. Unlike the situation for clouds, one can prove that 3 sprays cover the plane, independently of the status of CH. See "Decompositions of the plane and the size of the continuum", Ramiro de la Vega, Fund. Math. 203 (2009), 65-74, and "Covering the plane with sprays", James H. Schmerl, Fund. Math. 208 (2010), 263-272. –  Andres Caicedo Jul 5 '10 at 5:10
1  
Speaking of stuff on the plane, a certain problem of coloring the plane with no corners is equivalent to CH too - artofproblemsolving.com/Forum/viewtopic.php?f=73&t=137999 –  Yoo Jul 5 '10 at 9:35
    
Thanks for the comments and references! –  Peter Krautzberger Jul 5 '10 at 15:29
1  
Since Justin's link leads to a paywall here's a survey by Arnold Miller math.wisc.edu/~miller/old/m873-05/setplane.ps –  Peter Krautzberger Jul 5 '10 at 15:42

Following Eric Wofsey's point, you probably are interested in things that don't involve the pathologies of arbitrary uncountable objects. Some people have argued that the only things "ordinary mathematicians" care about are things that are representable in second-order arithmetic. (This gives you arbitrary real numbers, arbitrary complete separable metric spaces, Borel and analytic sets on all of those, and similarly interesting amounts of algebraic stuff.) The project of Steven Simpson's book Subsystems of Second-Order Arithmetic is to analyze just what axioms are needed to prove which results. All of the things considered there are far weaker than ZFC. But it's interesting to discover that beyond the axioms of Peano Arithmetic and the existence of arbitrary recursive sets of natural numbers, there are exactly five natural strengths. That is, there are five levels such that very large numbers of theorems from ordinary mathematics fall at exactly one of the levels, where any theorem at one level can be proved by assuming any theorem at that level or higher. Interestingly, things like the Heine-Borel theorem and the Bolzano-Weierstrass theorem, which are often thought of as equivalent, actually fall at different levels.

Not everything falls exactly at these levels though. Some things do still depend on a version of the axiom of choice, which is above any of these five levels, and there are other results like Goodstein's theorem and Borel determinacy that are higher still (I believe).

share|improve this answer
2  
Borel Determinacy is interesting because it really uses Replacement. In fact, it was known that ZFC-Replacement was insufficient to prove Borel Determinacy before Borel Determinacy was proven. –  Richard Dore Oct 23 '09 at 4:24
    
Thanks for explanation and the reference! –  Jose Brox Nov 8 '09 at 2:38

Another example is certain strong forms of Fubini's Theorem.

If you have a real value function on the product of two closed intervals which is bounded, and which is measurable in either coordinate when you fix the other, are the two iterated integrals equal?

(In the actual Fubini's theorem you care about joint measurability, not just measurability on either coordinate.)

If you assume CH, it is easy to construct counterexamples. It turns it is also consistent to have models where it is true.

I don't have a good reference on this, if you know of one please add it in to my answer.

share|improve this answer
2  
The CH result is due to Sierpinski; the independence result was shown almost simultaneously by Chris Freiling, Harvey Friedman, and Miklos Laczkovich. See Ciesielski's survey math.wvu.edu/~kcies/prepF/56STA/STAsurvey.html –  François G. Dorais Feb 5 '10 at 22:50
1  
One nice way to get the statement to be true is using Freiling's axioms of symmetry. There's a proof of it in Chris Freiling. Axioms of symmetry: Throwing darts at the real line. The Journal of Symbolic Logic, 51, 1986. –  David R. MacIver Apr 11 '10 at 20:45
1  
One reference for strong Fubini theorems is Joe Shipman's paper, "Cardinal conditions for strong Fubini theorems," Trans. Amer. Math. Soc. 321 (1990), 465-481. –  Timothy Chow May 31 '10 at 16:57

A recent example is the question of the existence of outer automorphisms of the Calkin algebra of a separable infinite-dimensional Hilbert space (this is the algebra of all bounded operators divided by the compacts). See this paper of Farah for details.

A feature this example shares with Kaplansky's conjecture mentioned above is the use of CH for the construction of the desired object. For the other direction (proving the non-existence of an outer automorphism), which is more interesting, Farah uses a natural combinatorial axiom (OCA) which can be forced in any model of ZFC.

Wikipedia also has a list of independence results.

share|improve this answer
    
You can leave multiple links once you have 15 reputation. I added a link; I hope it's to the right place. –  Anton Geraschenko Oct 22 '09 at 21:45

"The real line is the only endless dense complete linear order in which every family of disjoint intervals is countable."

This statement generalizes the familar characterization of the real line (due to Cantor) as the unique endless dense complete linear order having a countable dense set. Souslin inquired whether this separability condition can be weaked to the condition on families of disjoint intervals. (Here, complete means that the order as the LUB property.)

This statement is known as Souslin's Hypothesis, and it is independent of ZFC. It is false under the combinatorical assertion known as Diamond, but follows from Martin's Axiom at Aleph_1. The proof that the statement is consistent, due to Solovay and Tennenbaum, is highly important in the history of set theory, since it required the development of iterated forcing, now a fundamental tool.

share|improve this answer

Sometimes ZFC is just not sufficient to prove statements which morally should be true. The axiom of projective determinacy is perhaps the best known instance of this. If you don't know what this is, consider the following example: take a closed set in R^3, project it in R^2, take the complement and project it into R. One cannot prove in ZFC that the resulting set is Lebesgue measurable (or has the property of Baire, or the perfect set property). However, this is an easy consequence of PD which in turn can be proved using large cardinals (Martin and Steel, "A Proof of Projective Determinacy", JAMS).

share|improve this answer
3  
Not sure if this is the right forum for this, but: do you think PD is "morally true" because it follows from large cardinal axioms, which themselves are "morally true"? Or does PD follow from some other set of ethical principles? Guess I'm somewhat of a libertine, myself... –  John Goodrick Oct 23 '09 at 17:59
2  
Maybe I didn't choose the right word. Anyway, for me, PD is a strong justification for large cardinals, not the other way round. But this is, of course, a philosophical rather than mathematical discussion. –  Todor Tsankov Oct 24 '09 at 8:12

Paul Erdős proved a funny statement about analytic functions to be equivalent to the continuum hypothesis. The same proof can also be found in Proofs from THE BOOK.

share|improve this answer

The assertion that the union of any Aleph_1 many measure zero sets is still measure zero. This is independent of ZFC. Of course, it implies the failure of the Continuum Hypothesis, but is not equivalent to this.

There are a huge variety of such statements in the field known as Cardinal Characteristics of the Continuum. For example, what is the additivity of the meager ideal (the ideal of all meager sets)? It is at least Aleph_1, but can be larger. What is the smallest size of a family of functions f:omega to omega such that every function is bounded by an element of the family? It can be Aleph_1, or larger independently. There are dozens of such examples.

share|improve this answer

In the ring of bounded operators on (complex, separable) Hilbert space, the ideal of compact operators is the sum of two properly smaller ideals. (I mean 2-sided ideals, in the algebraic sense, not topologically closed ideals.)

In the Stone-Cech compactification of a half-open interval minus the interval itself (call this space X), there exist two points such that the only compact, connected subset of X containing both points is X itself.

Both of these statements are true under CH (or various weaker assumptions) but not provable in ZFC. Lest anyone remind me that there should be only one statement per answer, I point out that, despite appearances, these two statements are provably equivalent. See an old paper of mine, "Near coherence of filters II," Trans. A.M.S. 300 (1987) 557-581, for the equivalence, and references there to older papers, including one with Gary Weiss and one with Saharon Shelah, for the CH result and the independence from ZFC.

share|improve this answer

Here's one (a corollary of some work I did with Keith Kearnes):

It is undecidable in ZFC whether there exists a commutative Noetherian domain of size aleph_{2} with a finite residue field.

share|improve this answer

For every function $f$ mapping the reals into the set of all countable subsets of the reals, there are real numbers $x$ and $y$ such that $x \notin f(y)$ and $y \notin f(x)$.

This innocent and reasonable statement is actually equivalent to the negation of the Continuum Hypothesis. The equivalence was first proved by Sierpiński, and is actually very easy to see.

If CH holds, let $\{x_\alpha: \alpha < \omega_1\}$ be an enumeration of the reals in type $\omega_1$, the function defined by $f(x_\alpha)=\{x_\beta: \beta \leq \alpha \}$ is a counterexample to the boxed statement or otherwise we'd have a pair of ordinals $\alpha, \beta < \omega_1$ such that both $\alpha < \beta$ and $\beta < \alpha$.

Suppose now that CH fails and let $f: \mathbb{R} \to [\mathbb{R}]^{\leq \aleph_0}$. Let $S$ be a set of reals of cardinality $\aleph_1$. Let $T=\bigcup \{f(x): x \in S \}$. The set $T$ has cardinality $\aleph_1$ and hence we can pick a real number $y \notin T$. Since $f(y)$ is countable we can pick a real number $z \in S \setminus f(y)$. We have both $z \notin f(y)$ and $y \notin f(z)$.

share|improve this answer
4  
Might as well call this statement by its name, Freiling's axiom of symmetry. –  Asaf Karagila May 9 '13 at 23:33

Of course, it follows from the negative solution to Hilbert's 10th problem (Putnam-Davis-Robinson-Matijasevic) that one can construct a specific diophantine equation P(x1,x2,...,xm)=0 for some m such that the solvability of this equation (over Z) is undecidable in ZFC. I actually think m, and the degree of P, can be made to be quite smallish.

It follows, of course, that the equation has no integer solutions (for if it had, this would have been easily demonstrable in ZFC). But ZFC is not capable of providing a proof of this fact (assuming that ZFC is consistent. If it's not then it can provide a proof of anything...)

share|improve this answer
    
This not right. The theorem of Matijasevic et al. states that there is a specific polynomial equation p(y, x_1, ..., x_n) such that the set of all integers a for which p(a, x_1, ..., x_n) has a solution where all the x_i's are integers is "undecidable," but here "undecidable" means uncomputable, i.e. you could never write a Java script to determine membership in this set. "Undecidable from ZFC" means that both the statement and its negation are logically consistent with ZFC. –  John Goodrick Oct 22 '09 at 23:39
1  
Greg Igusa says: That doesn't sound right to me. If the set A of a for which p(a, x_i) has a solution is undecidable, then there would have to be a specific integer a_0 for which the question "does p(a_0,x_i) have a solution" is independent of ZFC, else we could compute the set A by searching for proofs as to whether or not the polynomial has a solution. But this gives an example of a polynomial as in the original answer. –  Anton Geraschenko Oct 23 '09 at 0:30
2  
"Given a number a, search for some number n and some proof (from ZFC) that p(a, n) holds" is not a good algorithm for deciding whether or not (exists x) p(a, x) is true. If you do find such n and such a proof, then OK, you're done; but otherwise, you'll get stuck in an infinite loop. The set of a for which p(a,x) has a solution is always r.e., but not always recursive: en.wikipedia.org/wiki/Diophantine_set –  John Goodrick Oct 23 '09 at 1:16
2  
Since some of the references here are long, let me give a comment-sized statement: The solution of Hilbert's 10th problem also shows that there is a Diophantine equation E such that E has a solution if and only if ZFC is inconsistent (and this equivalence is provable in Peano Arithmetic). So those of us who think ZFC is consistent think E has no solutions but ZFC can't prove that. Those who think ZFC is inconsistent could make their case by finding a solution of E (but it would probably be easier just to exhibit a proof of a contradiction in ZFC). –  Andreas Blass Jul 4 '10 at 4:27
2  
Greg Igusa's argument above shows by contradiction the existence of a polynomial $p$ whose solvability is independent of ZFC, but does not by itself tell us how to get our hands on such a $p$. The missing ingredient is the result that one can computably translate arbitrary existential ($\Sigma^0_1$) statements into statements about solvability of Diophantine equations. This yields both the uncomputability (Matiyasevich's theorem), and the fact that a specific $p$ can be found (as in Andreas Blass' comment and Alon Amit's answer) since $\neg$Con(ZFC) is a $\Sigma^0_1$ statement. –  Bjørn Kjos-Hanssen Oct 19 '10 at 10:36

My favorite is the first problem I worked on, back in 1966 when I was an undergraduate. The question is: does every non separable Banach space have an uncountable biorthogonal system? Shelah constructed a counterexample under diamond; Kunen later gave a C(K) counterexample using CH. In 2005 Stevo Todorcevic gave a positive answer when mm > aleph_1. His paper "Biorthogonal Systems and Quotient spaces via Baire Category" appeared in Math. Annalen in the last couple of years.

share|improve this answer

One of my favorites has to do with products of spaces of countable cellularity:

"If X and Y are topological spaces with countable cellularity then their product X x Y has countable cellularity"

Is independent of ZFC. (The failing example being a Souslin line)

share|improve this answer
1  
What does "countable cellularity" mean? –  Qiaochu Yuan Mar 25 '11 at 20:44
    
That any collection of disjoint open subsets of a space is at most countable. –  Michael Blackmon Mar 29 '11 at 19:33

The statement, "Any two aleph-1-dense subsets of the reals are order isomorphic."

A subset X of R is called aleph-1-dense if between any two real numbers, there are exactly aleph-1 elements of X. On the one hand, Sierpinski used a diagonalization argument (working within ZFC) to construct kappa pairwise non-isomorphic suborderings of R each of density kappa, where kappa is the cardinality of R, so the Continuum Hypothesis implies that this statement fails. On the other hand, James Baumgartner used a clever forcing argument to build models of ZFC where the size of R is aleph-2 and any two aleph-1-dense suborderings of R are isomorphic.

See "All aleph_1 dense sets of reals can be isomorphic," James E. Baumgartner, Fundamenta Mathematicae v. LXXIX (1973), pp. 101-106.

share|improve this answer

Albin Jones has a draft paper on his web page, "Even more partitioning triples of countable ordinals", which has a survey of infinite Ramsey theory results stated in terms of ordinals.

Let $\omega$ be the first infinite ordinal and let $\omega_1$ be the first uncountable ordinal. Citing results of Todorcevic and Hajnal, Jones says that if you color pairs of elements of $\omega_1$ in blue and red, then it is independent of ZFC to decide whether there must be either a blue subset of type $\omega_1$ or a red subset of type $\omega+2$.

share|improve this answer

My favourite one(in fact it is equivalent to continuum hypothesys, proving equivalency is a very nice exercise,btw):

Real line could be represented as a countable union of linearly independent(over $\mathbb{Q}$) subsets.

share|improve this answer

Is every regular ($T_3$) topological space $X$ that is hereditarily separable (all subspaces are separable) Lindelöf (every open cover of $X$ has a countable subcover) ?

A counterexample is known as an S-space and Baumgartner showed there are models of ZFC without them. But under CH (and many other axioms) they do exist. Interestingly, in ZFC there does exist an L-space (a hereditarily Lindelöf space that is not separable), which was surprising to many topologists, who expected a certain duality to hold between S- and L-spaces. For a short intoduction see these slides.

share|improve this answer

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.