14
$\begingroup$

I am curious as to whether there exists a mathematical object in any field that can be proven to exist but has no concrete examples? I.e., something completely non-constructive. The closest example I know of are ultrafilters, which only have one example that can be written down. MathOverflow user Harrison Brown mentioned to me that there are examples in Ramsey theory of objects that are proven to exist but have no known deterministic construction (but there might be), which is close to what I'm looking for. He also mentioned that the absolute Galois group of the rationals has only two elements that you can write down - the identity element and complex conjugation.

I am worried that this might be a terribly silly question, since typically there is a trivial example of an object, and a definition that specifically did not include the trivial case would be 'cheating' as far as I'm concerned. My motivation for this question is purely out of curiosity. Also, this is my first question on MO, so I probably need help with tags and such (I'm not terribly sure what this would belong to). I think that this should be a community wiki, but I do not have the reputation to make it so as far as I can tell.

$\endgroup$
13
  • 12
    $\begingroup$ Lots of things proved to exist by Zorn's lemma are non-constructive, like a basis for R as a Q-vector space, a transcendence basis for R as a field extension of Q, a well-ordering of R, a nontrivial non-archimedean absolute value on C, a field isomorphism between the algebraic closure of Q_p and C,... $\endgroup$
    – KConrad
    Apr 22, 2011 at 16:47
  • 4
    $\begingroup$ “No concrete examples” does not imply “non-constructive”. For example, in the game of hex the first player has a winning strategy, which can be constructed by marking the (finite) game graph. However, I don't think anyone has described a winning strategy for the game. en.wikipedia.org/wiki/Hex_%28board_game%29 $\endgroup$ Apr 22, 2011 at 17:46
  • 2
    $\begingroup$ @Qiaochu: Pretty sure the intention was that only the principal ultrafilters can be "explicitly" described. $\endgroup$ Apr 22, 2011 at 19:03
  • 2
    $\begingroup$ @Jon: You need to specify better what you mean by "concrete", or the question becomes too vague to be useful. $\endgroup$ Apr 22, 2011 at 19:04
  • 16
    $\begingroup$ This question is, at time of writing, likely to be closed. Since the comments section is already long, please bring discussion to tea.mathoverflow.net/discussion/1019 . And please vote up this comment so that it appears "above the fold". $\endgroup$ Apr 22, 2011 at 21:14

8 Answers 8

18
$\begingroup$

If I remember correctly, there is a theorem that asserts that all but possibly zero, one or two prime numbers generate infinitely many of the (cyclic) multiplicative groups $\mathbb{Z}/q\mathbb{Z}^{\times}$ where $q$ varies among the primes. Yet not even one such prime is known, not even $2$ or $3$. Thus, among $2,3$ and $5$, at least one of them has the property, but no one knows which do.

$\endgroup$
2
  • 4
    $\begingroup$ It is due to Heath-Brown: qjmath.oxfordjournals.org/content/37/1/27.full.pdf $\endgroup$
    – S. Carnahan
    May 11, 2011 at 4:28
  • 1
    $\begingroup$ But note also that each of the numbers $2$, $3$ and $5$ is concrete individually and can be given as explicitly as anything can be in mathematics. So this is not really a case where we prove something exists but there is no concrete example; rather, it is a case where among several concrete examples, we can prove that one of them has a certain property, but we don't know which one. $\endgroup$ May 11, 2011 at 12:21
14
$\begingroup$

You should look at Handbook of Analysis and its Foundations by Eric Schecter. Here is an excerpt from the preface:

Students and researchers need examples; it is a basic precept of pedagogy that every abstract idea should be accompanied by one or more concrete examples. Therefore, when I began writing this book (originally a conventional analysis book), I resolved to give examples of everything. However, as I searched through the literature, I was unable to find explicit examples of several important pathological objects, which I now call intangibles:

finitely additive probabilities that are not countably additive, elements of $(l_\infty)^*- l_1$(a customary corollary of the Hahn- Banach Theorem), universal nets that are not eventually constant, free ultrafilters (used very freely in nonstandard analysis!), well orderings for R, inequivalent complete norms on a vector space, etc. In analysis books it has been customary to prove the existence of these and other pathological objects without constructing any explicit examples, without explaining the omission of examples, and without even mentioning that anything has been omitted. Typically, the student does not consciously notice the omission, but is left with a vague uneasiness about these unillustrated objects that are so difficult to visualize.

I could not understand the dearth of examples until I accidentally ventured beyond the traditional confines of analysis. I was surprised to learn that the examples of these mysterious objects are omitted from the literature because they must be omitted: Although the objects exist, it can also be proved that explicit constructions do not exist. That may sound paradoxical, but it merely reflects a peculiarity in our language: The customary requirements for an "explicit construction" are more stringent than the customary requirements for an "existence proof." In an existence proof we are permitted to postulate arbitrary choices, but in an explicit construction we are expected to make choices in an algorithmic fashion. (To make this observation more precise requires some definitions, which are given in 14.76 and 14.77.)

Though existence without examples has puzzled some analysts, the relevant concepts have been a part of logic for many years. The nonconstructive nature of the Axiom of Choice was controversial when set theory was born about a century ago, but our understanding and acceptance of it has gradually grown. An account of its history is given by Moore [1982]. It is now easy to observe that nonconstructive techniques are used in many of the classical existence proofs for pathological objects of analysis. It can also be shown, though less easily, that many of those existence theorems cannot be proved by other, constructive techniques. Thus, the pathological objects in question are inherently unconstructible.

The paradox of existence without examples has become a part of the logicians' folklore, which is not easily accessible to nonlogicians. Most modern books and papers on logic are written in a specialized, technical language that is unfamiliar and nonintuitive to outsiders: Symbols are used where other mathematicians are accustomed to seeing words, and distinctions are made which other mathematicians are accustomed to blurring -- e.g., the distinction between first-order and higher-order languages. Moreover, those books and papers of logic generally do not focus on the intangibles of analysis.

On the other hand, analysis books and papers invoke nonconstructive principles like magical incantations, without much accompanying explanation and -- in some cases -- without much understanding. One recent analysis book asserts that analysts would gain little from questioning the Axiom of Choice. I disagree. The present work was motivated in part by my feeling that students deserve a more "honest" explanation of some of the non-examples of analysis -- especially of some of the consequences of the Hahn- Banach Theorem. When we cannot construct an explicit example, we should say so. The student who cannot visualize some object should be reassured that no one else can visualize it either. Because examples are so important in the learning process, the lack of examples should be discussed at least briefly when that lack is first encountered; it should not be postponed until some more advanced course or ignored altogether.

$\endgroup$
1
  • $\begingroup$ Very interesting! Definitely looks like something I will jack from the library. $\endgroup$ Apr 23, 2011 at 15:53
12
$\begingroup$

I think the meaning of the term "exist" needs to be clarified. All of the examples you describe except the Ramsey-theoretic one depend on axioms independent of ZF (e.g. the ultrafilter lemma). On the other hand, the probabilistic method can prove, in ZF, that plenty of objects exist (e.g. efficient sphere packings, families of graphs realizing bounds on the Ramsey numbers) for which we do not have efficient deterministic constructions. I assume this is what Harrison is referring to (the use of the probabilistic method in Ramsey theory).

$\endgroup$
3
  • $\begingroup$ I was going to mention error-correcting codes saturating the Shannon limit, but this answer implicitly covers that. $\endgroup$ Apr 22, 2011 at 21:10
  • $\begingroup$ "for which we do not have deterministic constructions" is an exaggeration. Whenever finite objects are concerned, one can always produce one by enumeration. You wouldn't say that we do not have a deterministic way of finding prime decompositions, would you? $\endgroup$ May 10, 2011 at 20:49
  • $\begingroup$ @Ori: sorry, I guess I meant "efficient deterministic constructions." $\endgroup$ May 10, 2011 at 23:48
10
$\begingroup$

In the game which is just like chess, except each player makes two moves in a row, the first player has a strategy that draws at least, but no explicit such strategy is known.

$\endgroup$
7
  • $\begingroup$ Do you have a reference for that? $\endgroup$ Apr 23, 2011 at 0:10
  • 16
    $\begingroup$ If the second player has a winning strategy, the first player starts by moving a knight and then undoing their move. More generally, this applies to any game in which "do nothing" is a legal move. $\endgroup$ Apr 23, 2011 at 0:16
  • $\begingroup$ Eric, I don't quite follow. White plays Nf3, Black plays, White plays Ng1, Black plays. Now Black has made <i>two</i> moves. $\endgroup$
    – Todd Trimble
    May 11, 2011 at 0:12
  • 1
    $\begingroup$ Todd, did you miss the part about each player making two moves in a row? White plays Nf3 and Ng1 before Black gets to do anything. $\endgroup$ May 11, 2011 at 0:37
  • 4
    $\begingroup$ Of course, if the best opening for the first player is to do nothing, effectively reversing roles, then the best follow-up for the second player is also to do nothing, reversing roles back. So two ideal players would just keep infinitely passing the buck back and forth; the game would stall out with no action. Which, yeah, in some sense is still a validation of this as a guaranteed non-loss strategy, but it's alas a possibility which is not very interesting. $\endgroup$ May 11, 2011 at 12:15
4
$\begingroup$

-The Robertson-Thomas-Seymour Graph Minor theorem says there exists of a polynomial time algorithm for determining if a graph has a heritable property P.

http://www.google.com/search?client=ubuntu&channel=fs&q=Graph+Minor+Theorem&ie=utf-8&oe=utf-8#q=Graph+Minor+Theorem+Algorithms&bav=on.2,or.r_gc.r_pw.&channel=fs&fp=f26a11cf684416b&hl=en

-Banach-Tarski decomposition of a ball into two balls of the same volume is another example.

-The proposition which is true but not provable in Godel's incompleteness theorem.

-The linear PDE which admits no solution (like in the last Chapter of John Fritz's book).

  • Pretty much any proof that uses the axiom of choice to construct something has this problem. I'll post more if I can come up with other examples. There are tons.

$\endgroup$
5
  • 1
    $\begingroup$ Taylor, the last comment you make is a bit delicate. In set theory there is what we call "canonical structures", whose existence needs the axiom of choice, but are 'explicit' infinitary objects, not dependent on any well-ordering or choice function used in their construction. $\endgroup$ Apr 22, 2011 at 19:31
  • 1
    $\begingroup$ "-The proposition which is true but not provable in Godel's incompleteness theorem." I'll just mention that for Peanos' axioms such a proposition had been found: for any infinite sequence of binary words (the words of symbols of 0 and 1) there are two of them, s.t. the first contains the second as a subword. $\endgroup$
    – zroslav
    Apr 22, 2011 at 19:37
  • 4
    $\begingroup$ Godel's proof provided a perfectly explicit construction of a statement (in a given formal system) which is true but unprovable in the system if the system is consistent. Godel's second incompleteness theorem shows that one such statement expresses the consistency of the system. $\endgroup$ Apr 22, 2011 at 19:39
  • $\begingroup$ What I think is a nicer example from the graph minor theorem, is that there "exists" a finite set of forbidden minors for toroidal graphs (or any family of graphs which is closed under minors). $\endgroup$ Apr 22, 2011 at 21:17
  • 1
    $\begingroup$ It's actually Fritz John. $\endgroup$ Apr 23, 2011 at 1:58
3
$\begingroup$

I think the best known example is the subset of the plane, s.t. its intersection with any line has exactly 2 points in it. This can be proven by the axiom of choice but there are no constructions of it.

$\endgroup$
3
  • 4
    $\begingroup$ In what sense is that a better than, say, a basis of $\mathbb R$ as a rational vector space? It's not like your set obviously exists! :) $\endgroup$ Apr 22, 2011 at 20:04
  • 1
    $\begingroup$ This sense is my own sense of beauty :) My set is the most argued to be existing. The existing of this set is the main reason for elementary geometers to beleive that the axiom of choice is not true :) $\endgroup$
    – zroslav
    Apr 22, 2011 at 22:45
  • 4
    $\begingroup$ I'm pretty confident that if/when those "elementary geometers" become algebraic geometers, though, they'll want their commutative rings to have lots of maximal ideals! :) $\endgroup$ Apr 23, 2011 at 0:13
3
$\begingroup$

Eigenvalues of the Laplacian $\Delta$ acting on $L^2 (G/ \Gamma)$, where $G = SL_2 (\mathbb{R})$ and $\Gamma = SL_2 (\mathbb{Z}) < G$ (one can consider more general groups $G$ and take any lattice $\Gamma$ in $G$), or the so called Maass forms. It is known, by Selberg's trace formula and other related results, that such eigenvalues do exist, and we even have theorems describing their asymptotic count, but not a single, concrete example of a Maass form is known, even for this specific choice of $G$ and $\Gamma$. Quoting from Goldfeld's "Automorphic forms and L-functions for the group GL(n,R)":

"Up to now no one has found a single example of a Maass form for $SL_2 (\mathbb{Z})$".

$\endgroup$
1
  • 6
    $\begingroup$ This quote must be interpreted carefully. Numerical values of these functions' Laplace eigenvalues and Hecke eigenvalues have been computed to over one hundred decimal places. Goldfeld is referring to the fact that they will never be constructed explicitly "from simpler functions", just as the solutions to any moderately complicated PDE will never be constructed explicitly in this way. $\endgroup$ Apr 23, 2011 at 2:02
1
$\begingroup$

A lot of existence proofs use arguments such as Cantor's diagonal argument, Baire category etc. Unlike the Zorn's lemma arguments, they can "in principle" yield examples. For instance, we could construct a transcendental number by enumerating the algebraic numbers and picking a number that differs from the nth algebraic number in the nth decimal digit. We can compute this number to as many digits as we want. Of course, this is not a transcendental number that anyone wants to know about.

$\endgroup$
4
  • $\begingroup$ You mean the Baire category theorem which assumes local compactness? Because the one assuming completeness sounds very constructive to me. $\endgroup$ Apr 22, 2011 at 23:55
  • $\begingroup$ Unfortunately for much of mathematical physics, Arzela-Ascoli is unconstructive. Maybe you meant that? $\endgroup$ Apr 22, 2011 at 23:57
  • 1
    $\begingroup$ Why is Arzela-Ascoli unconstructive? The proof gives a construction of the convergent subsequence of functions, once we know how to get a convergent subsequence for given argument. In any case, the point of my comment was that some existence proofs may appear to be unconstructive (such as proving existence of transcendental numbers based on uncountability), but in principle allow a construction. $\endgroup$ Apr 23, 2011 at 0:46
  • $\begingroup$ "once we know how to get a convergent subsequence for given argument" This. $\endgroup$ Apr 23, 2011 at 8:27

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