35
$\begingroup$

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.

$\endgroup$
3
  • 7
    $\begingroup$ 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. $\endgroup$ Jul 25, 2011 at 9:05
  • 5
    $\begingroup$ 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 $\endgroup$
    – tci
    Jul 25, 2011 at 9:18
  • $\begingroup$ Although I suspect that this might not be exactly what you want... $\endgroup$
    – tci
    Jul 25, 2011 at 9:19

9 Answers 9

27
$\begingroup$

Here are my favorite examples of statements whose consistency was established and cherished 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.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Jul 25, 2011 at 20:35
  • $\begingroup$ Abstract link for the Laver paper: arxiv.org/abs/math/9204203v1 $\endgroup$ Jul 19, 2013 at 15:58
27
$\begingroup$

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.

$\endgroup$
4
  • 12
    $\begingroup$ @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. $\endgroup$
    – Ali Enayat
    Jul 25, 2011 at 19:50
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 25, 2011 at 20:07
  • $\begingroup$ Ali, I think you are right. $\endgroup$ Jul 25, 2011 at 20:26
  • $\begingroup$ Joel, I unselected your answer based on Ali's comment above and the fact that you agree with it. Thanks for your feedback! $\endgroup$ Jul 28, 2011 at 4:44
14
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Jul 25, 2011 at 23:27
9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Jul 25, 2011 at 18:13
  • $\begingroup$ Chris, that is done in the same paper and the result of Keisler does not require CH. $\endgroup$ Jul 25, 2011 at 19:50
7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

Let $c(X)$ denote the cellularity of the topological space $X$, that is the supremum of the cardinalities of its families of pairwise disjoint non-empty open subsets.

In the early 60's Kurepa asked:

Is there a compact Hausdorff space $X$ such that $c(X)<c(X^2)$?

and noted that if $\mathbb{L}$ is a Suslin Line then $c(\mathbb{L})=\aleph_0<c(\mathbb{L}^2)$.

So the consistency of a positive answer to Kurepa's question has been known since the first constructions of Suslin trees using forcing by Jech and Tennenbaum in the late 60s. Later Galvin was able to get a compact CCC space whose square is not CCC from the Continuum Hypothesis.

And while the existence of a CCC space whose square is not CCC is independent from ZFC (an arbitrary product of CCC spaces is CCC under $MA_{\omega_1}$ for example), in the mid 80s Todorcevic surprised everyone by constructing a compact space $X$ such that $c(X)<c(X^2)$ in ZFC.

http://archive.numdam.org/article/CM_1986__57_3_357_0.pdf

Todorcevic's paper contained many other ZFC constructions of objects whose consistency had been previously known, including higher cardinal generalizations of $S$-spaces and $L$-spaces.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Perhaps you can take the example from other users on this thread and just post all your examples into one answer? $\endgroup$
    – Asaf Karagila
    Jul 19, 2013 at 23:30
  • 2
    $\begingroup$ @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." $\endgroup$
    – user33772
    Jul 20, 2013 at 0:36
  • $\begingroup$ I can't find any record of something called a "Moschovakis cardinal;" perhaps you mean "Reinhardt cardinal?" (en.wikipedia.org/wiki/Reinhardt_cardinal) $\endgroup$ Jul 20, 2013 at 6:18
  • $\begingroup$ @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. $\endgroup$
    – user33772
    Jul 20, 2013 at 7:19
  • $\begingroup$ Pity, they sound interesting. I've posted a question about this; hopefully, we'll get some answers! $\endgroup$ Jul 20, 2013 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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