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

I'm wondering if there are examples of statements that have been proven whose consistency proofs came before the proofs of the statements themselves.

More informally, I'm wondering how promising in general is the approach of attempting a consistency proof for a statement when faced with a statement that seems true but difficult to prove.

Background:

If a statement is provable from a set of axioms, then that statement is obviously consistent (assuming the set of axioms is consistent). So provability is stronger than consistency. This might lead one to think that constructing a consistency proof for a statement should be strictly easier than constructing a proof.

Yet consistency proofs (at least oft-cited ones, for example those by Godel and Cohen about the Continuum Hypothesis) seem to require a high level of sophistication (though this might be a byproduct of the fact that consistency proofs like these are for the special class of statements that cannot be proven).

For statements that can be proven then, are there cases where their consistency proofs are easier or came before the proofs themselves?

Update:

Thanks a lot, everyone, for the great answers so far. The number and existence of these examples is interesting to me, as well as the fact that they all rely on the same technique of first proving something using an additional axiom (an approach first suggested by Michael Greinecker). That hadn't occurred to me. I wonder if there are other approaches.

share|improve this question
5  
Yes. Sometimes it is easier to prove something first using additional axioms that are known to be consistent. Such a proof can be interpreted as a consistency proof for the system without the additional axiom. I don't have an example at hand, but there are several results that have been first shown using the continuum hypothesis and then shown to hold in general. –  Michael Greinecker Jul 25 '11 at 9:05
4  
Martin's Borel determinacy paper appeared in 1975, but his analytic determinacy one appeared in 1970. The latter proved analytic determinacy assuming the existence of a measurable cardinal. Ref: Martin, Donald A. (1975). "Borel determinacy". Annals of Mathematics. Second Series 102 (2): 363–371 Martin, Donald A., Measurable cardinals and analytic games, Fund. Math. 66 (1970), 287-291 –  Tanmay Inamdar Jul 25 '11 at 9:18
    
Although I suspect that this might not be exactly what you want... –  Tanmay Inamdar Jul 25 '11 at 9:19
add comment

8 Answers

up vote 18 down vote accepted

Here are my favorite examples of statements whose consistency was established and cheished before their proof.

1. The Keisler-Shelah isomorphism theorem stating that two elementarily equivalent structures have isomorphic ultrapowers (proved using in $ZFC+GCH$ by Keisler in 1964, and in $ZFC$ by Shelah in 1971).

2. Several algebraic results (normal forms, divison algorithms, etc) concerning the "left-distributive algebras of one generator" were first established by Richard Laver by assuming (very) large cardinals (known as (I3) in the literature). Later Patrick Dehornoy eliminated the large cardinal assumption in these results by giving a representation in the braid group.

By the way, a left distributive algebra is a set with one binary operation * satisfying the left distributive law $a*(b*c)=(a*b)*(a*c)$; the operation of conjugation in a group is an example. Here is an old paper of Laver about this topic; there is by now a large literature on the subject.

3. In some cases, the consistency proof of a statement $S$ can be combined with some absoluteness argument to yield a proof of $S$ (this was hinted at in the second example cited by Steprans). There are all sorts of absoluteness theorems in logic; the standard tool of the trade is the Shoenfield absoluteness theorem that shows that all sorts of consistency results can be translated into $ZFC$-proofs.

share|improve this answer
1  
There are a large number of results having the type of (2), namely, where a statement is first known from a very large cardinal, and then established from a much weaker large cardinal, which is then proved optimal. –  Joel David Hamkins Jul 25 '11 at 20:35
    
Abstract link for the Laver paper: arxiv.org/abs/math/9204203v1 –  Harry Altman Jul 19 '13 at 15:58
add comment

One of the main applications of Shelah's pcf theory is the celebrated theorem that if $\aleph_\omega$ is a strong limit, then $2^{\aleph_\omega}\lt\aleph_{\omega_4}$.

The conclusion of the theorem, however, is an immediate consequence of the generalized continuum hypothesis, and so the consistency of this statement was known long before Shelah made his proof. The surprising aspect of the theorem is precisely the fact that it is provable without any assumption on the continuum function.

There are likely many other examples of statements that were first proved from a GCH assumption (or which are trivial under GCH), but for which later this assumption was removed. And indeed, in these cases the later more general arguments are also often more difficult, as you suggest.

share|improve this answer
    
Thanks, Andreas! –  Joel David Hamkins Jul 25 '11 at 11:48
7  
@Joel: while I admire the technical depth of Shelah's theorem, I find it misleading to cite it as an example of a statement whose consistency was known before its proof because I doubt that the inequality $2^{\aleph_{\omega}} < \aleph_{\omega_4}$ was ever written down in any mathematical work prior to the appearance of Shelah's theorem. –  Ali Enayat Jul 25 '11 at 19:50
1  
This makes me wonder if there are also examples of statements that were proved first by assuming the negation of GCH (or better yet, as you say, trivial under the assumption). This could also be asked for the other examples provided. –  Chris Jerdonek Jul 25 '11 at 20:07
    
Ali, I think you are right. –  Joel David Hamkins Jul 25 '11 at 20:26
    
Joel, I unselected your answer based on Ali's comment above and the fact that you agree with it. Thanks for your feedback! –  Chris Jerdonek Jul 28 '11 at 4:44
add comment

A very good example, I believe, is A. Blass' theorem that AC holds if and only if every vector space has a basis.

It was well established that the existence of a vector space without a basis is consistent with the negation of AC, by Lauchli, 1963. Only 21 years later it was proved that ZF+not AC proves such a vector space exists.

There are probably some other similar examples of equivalent assertions of AC of similar nature.

share|improve this answer
1  
Well, to be fair I'm not certain Lauchli proved the consistency with ZF, but rather with ZFA. It was not until 1966 that the Jech-Sochor theorem was published to transfer this principle to a model of ZF. –  Asaf Karagila Jul 25 '11 at 23:27
add comment

Baumgartner and Hajnal showed that if $\Phi$ is an order type with the partition property $\Phi\rightarrow (\omega)_\omega^1$ then $\Phi\rightarrow(\alpha)_k^2$ for all $α<\omega_1$ and $k$. This provided the solution to problems of Erdős and Hajnal [Axiomatic set theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967), pp. 17--48, Amer. Math. Soc., Providence, R.I., 1971; MR0280381 (43 #6101)]. They proved this by first using Martin's Axiom and then appealing to absoluteness. Galvin later provided a purely combinatorial proof. See Baumgartner, J.; Hajnal, A. "A proof (involving Martin's axiom) of a partition relation." Fund. Math. 78 (1973), no. 3, 193.

A similar example is provided by Farah, Hrušák, and Martínez Ranero in " A countable dense homogeneous set of reals of size $\aleph_1$" Fund. Math. 186 (2005), no. 1, 71–77. They construct a $\lambda$ set that is homogeneous in the sense that any two countable dense sets can be mapped to each other assuming CH and then obtain the result by appealing to Keisler's absoluteness for the logic of countable sentences.

share|improve this answer
    
Juris, can you clarify the line of reasoning provided in your second example? When you say they "then obtain the result by appealing to [a result of Keisler]," is that in a second proof that does not assume CH? And is that done as a second proof within the same paper, or in a separate paper? –  Chris Jerdonek Jul 25 '11 at 18:13
    
Chris, that is done in the same paper and the result of Keisler does not require CH. –  Juris Steprans Jul 25 '11 at 19:50
add comment

Considering all the answers so far, I thought I might as well add one with a more topological flavor to it

  1. The existence of an L-space was known to be consistent for years (See The Handbook of Set-Theoretic Topology, Chapter 7, pg. 295). It was only recently that a ZFC construction was given here

  2. Some of the existence proofs for certain types of embeddings, and automorphisms between Boolean algebras have this flair to them, (See "The fourth head of $\beta\mathbb{N}$" by Ilijas Farah, in Open Problems in Topology II. pg 139.)

  3. Certain types of gnarly questions about coverings of $\mathbb{R}$ involving the forward and inverse images of $\aleph_1$ many continuous functions, have had some success with this see this answer

share|improve this answer
add comment

Todorcevic proved in ZFC that the two-element subsets of $\omega_1$ can be partitioned into $\aleph_1$ classes so that every uncountable subset of $\omega_1$ contains pairs from every class; in symbols, $\aleph_1\not\to[\aleph_1]_{\aleph_1}^2$. The straightforward proof of the same from CH was known to Erdős, Hajnal, and Rado many years earlier.

share|improve this answer
add comment

Before the existence of a nontrivial surjection $f:\mathcal P(\omega)\to\mathcal P(\omega)$ satisfying $f(X)\supseteq X$ and $f(X\cup Y)=f(X)\cup f(Y)$ was proved in ZFC, it was proved under various additional hypotheses such as CH.

share|improve this answer
add comment

Inasmuch as the negation of a large cardinal axiom is automatically known to be consistent, theorems such as "there are no Moschovakis cardinals" were known to be consistent before they were proven outright. Unfortunately I don't recall the definition of a Moschovakis cardinal--some combinatorial property related to determinacy?--and I couldn't find anything by startpaging or duckduckgoing.

share|improve this answer
    
Perhaps you can take the example from other users on this thread and just post all your examples into one answer? –  Asaf Karagila Jul 19 '13 at 23:30
1  
@AsafKaragila I'd gladly follow their examples if I knew that they are doing it right. In another list-type question I read the instruction: "As usual, please limit yourself to one counterexample per answer." –  user33772 Jul 20 '13 at 0:36
    
I can't find any record of something called a "Moschovakis cardinal;" perhaps you mean "Reinhardt cardinal?" (en.wikipedia.org/wiki/Reinhardt_cardinal) –  Noah S Jul 20 '13 at 6:18
    
@NoahS Seems like Moschovakis cardinals have gone down the memory hole. I read about them in an unpublished "Survey of Recent Results in Set Theory" sometime in the late sixties. I probably still have a copy somewhere, but it would be hopeless to try and find it. –  user33772 Jul 20 '13 at 7:19
    
Pity, they sound interesting. I've posted a question about this; hopefully, we'll get some answers! –  Noah S Jul 20 '13 at 7:48
show 5 more comments

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.