Are there examples of statements that have been proven whose consistency proofs came before their proofs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:55:23Z http://mathoverflow.net/feeds/question/71201 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71201/are-there-examples-of-statements-that-have-been-proven-whose-consistency-proofs-c Are there examples of statements that have been proven whose consistency proofs came before their proofs? Chris Jerdonek 2011-07-25T08:08:00Z 2011-07-28T04:42:12Z <p>I'm wondering if there are examples of statements that have been proven whose consistency proofs came before the proofs of the statements themselves.</p> <p>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.</p> <p>Background:</p> <p>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.</p> <p>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).</p> <p>For statements that can be proven then, are there cases where their consistency proofs are easier or came before the proofs themselves?</p> <p><b>Update:</b></p> <p>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.</p> http://mathoverflow.net/questions/71201/are-there-examples-of-statements-that-have-been-proven-whose-consistency-proofs-c/71207#71207 Answer by Joel David Hamkins for Are there examples of statements that have been proven whose consistency proofs came before their proofs? Joel David Hamkins 2011-07-25T10:03:36Z 2011-07-25T11:49:57Z <p>One of the main applications of <a href="http://en.wikipedia.org/wiki/PCF_theory" rel="nofollow">Shelah's pcf theory</a> is the celebrated theorem that if $\aleph_\omega$ is a strong limit, then $2^{\aleph_\omega}\lt\aleph_{\omega_4}$. </p> <p>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.</p> <p>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. </p> http://mathoverflow.net/questions/71201/are-there-examples-of-statements-that-have-been-proven-whose-consistency-proofs-c/71213#71213 Answer by Juris Steprans for Are there examples of statements that have been proven whose consistency proofs came before their proofs? Juris Steprans 2011-07-25T11:45:11Z 2011-07-25T11:56:25Z <p>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 $α&lt;\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.</p> <p>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.</p> http://mathoverflow.net/questions/71201/are-there-examples-of-statements-that-have-been-proven-whose-consistency-proofs-c/71258#71258 Answer by Ali Enayat for Are there examples of statements that have been proven whose consistency proofs came before their proofs? Ali Enayat 2011-07-25T20:28:35Z 2011-07-25T20:45:09Z <p>Here are my favorite examples of statements whose consistency was established and cheished before their proof.</p> <p><strong>1.</strong> The <a href="http://arxiv.org/PS_cache/math/pdf/9204/9204203v1.pdf" rel="nofollow">Keisler-Shelah isomorphism theorem</a> 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).</p> <p><strong>2.</strong> Several algebraic results (normal forms, divison algorithms, etc) concerning the "left-distributive algebras of one generator" were first established by Richard Laver by <strong>assuming (very) large cardinals</strong> (known as <strong>(I3)</strong> in the literature). Later Patrick Dehornoy eliminated the large cardinal assumption in these results by giving a representation in the braid group. </p> <p>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 <a href="http://arxiv.org/PS_cache/math/pdf/9204/9204203v1.pdf" rel="nofollow">old paper of Laver</a> about this topic; there is by now a large literature on the subject.</p> <p><strong>3.</strong> 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 <a href="http://en.wikipedia.org/wiki/Absoluteness#Shoenfield.27s_absoluteness_theorem" rel="nofollow">Shoenfield absoluteness theorem</a> that shows that all sorts of consistency results can be translated into $ZFC$-proofs.</p> http://mathoverflow.net/questions/71201/are-there-examples-of-statements-that-have-been-proven-whose-consistency-proofs-c/71267#71267 Answer by Michael Blackmon for Are there examples of statements that have been proven whose consistency proofs came before their proofs? Michael Blackmon 2011-07-25T22:27:58Z 2011-07-25T22:27:58Z <p>Considering all the answers so far, I thought I might as well add one with a more topological flavor to it</p> <ol> <li><p>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 <a href="http://www.math.cornell.edu/~justin/Ftp/Lspace.pdf" rel="nofollow">here</a></p></li> <li><p>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.)</p></li> <li><p>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 <a href="http://mathoverflow.net/questions/53711/cn-and-forcing-reading-a-recent-paper-by-kunen/53728#53728" rel="nofollow">see this answer</a></p></li> </ol> http://mathoverflow.net/questions/71201/are-there-examples-of-statements-that-have-been-proven-whose-consistency-proofs-c/71269#71269 Answer by Asaf Karagila for Are there examples of statements that have been proven whose consistency proofs came before their proofs? Asaf Karagila 2011-07-25T22:58:51Z 2011-07-25T22:58:51Z <p>A very good example, I believe, is A. Blass' theorem that AC holds if and only if every vector space has a basis.</p> <p>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 <em>proves</em> such a vector space exists.</p> <p>There are probably some other similar examples of equivalent assertions of AC of similar nature.</p>