Are there any mathematical objects that exist but have no concrete examples? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-21T15:21:59Z http://mathoverflow.net/feeds/question/62635 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples Are there any mathematical objects that exist but have no concrete examples? Jon Paprocki 2011-04-22T16:37:44Z 2011-05-10T23:48:22Z <p>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 <a href="http://en.wikipedia.org/wiki/Ultrafilter" rel="nofollow">ultrafilters</a>, 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.</p> <p>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.</p> http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples/62646#62646 Answer by Qiaochu Yuan for Are there any mathematical objects that exist but have no concrete examples? Qiaochu Yuan 2011-04-22T18:14:59Z 2011-05-10T23:48:22Z <p>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 <a href="http://en.wikipedia.org/wiki/Probabilistic_method" rel="nofollow">probabilistic method</a> can prove, <em>in ZF</em>, 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). </p> http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples/62652#62652 Answer by Taylor Dupuy for Are there any mathematical objects that exist but have no concrete examples? Taylor Dupuy 2011-04-22T19:24:25Z 2011-04-22T19:24:25Z <p>-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. </p> <p><a href="http://www.google.com/search?client=ubuntu&amp;channel=fs&amp;q=Graph+Minor+Theorem&amp;ie=utf-8&amp;oe=utf-8#q=Graph+Minor+Theorem+Algorithms&amp;bav=on.2,or.r_gc.r_pw.&amp;channel=fs&amp;fp=f26a11cf684416b&amp;hl=en" rel="nofollow">http://www.google.com/search?client=ubuntu&amp;channel=fs&amp;q=Graph+Minor+Theorem&amp;ie=utf-8&amp;oe=utf-8#q=Graph+Minor+Theorem+Algorithms&amp;bav=on.2,or.r_gc.r_pw.&amp;channel=fs&amp;fp=f26a11cf684416b&amp;hl=en</a></p> <p>-Banach-Tarski decomposition of a ball into two balls of the same volume is another example.</p> <p>-The proposition which is true but not provable in Godel's incompleteness theorem.</p> <p>-The linear PDE which admits no solution (like in the last Chapter of John Fritz's book).</p> <ul> <li><p>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.</p></li> </ul> http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples/62653#62653 Answer by zroslav for Are there any mathematical objects that exist but have no concrete examples? zroslav 2011-04-22T19:32:57Z 2011-04-22T19:32:57Z <p>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.</p> http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples/62676#62676 Answer by Michael Renardy for Are there any mathematical objects that exist but have no concrete examples? Michael Renardy 2011-04-22T22:52:57Z 2011-04-22T22:52:57Z <p>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.</p> http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples/62678#62678 Answer by Olivier Bégassat for Are there any mathematical objects that exist but have no concrete examples? Olivier Bégassat 2011-04-22T23:47:43Z 2011-04-22T23:47:43Z <p>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.</p> http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples/62680#62680 Answer by Igor Rivin for Are there any mathematical objects that exist but have no concrete examples? Igor Rivin 2011-04-23T00:02:24Z 2011-04-23T00:02:24Z <p>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.</p> http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples/62684#62684 Answer by Mark Schwarzmann for Are there any mathematical objects that exist but have no concrete examples? Mark Schwarzmann 2011-04-23T00:50:47Z 2011-04-23T00:50:47Z <p>Eigenvalues of the Laplacian $\Delta$ acting on $L^2 (G/ \Gamma)$, where $G = SL_2 (\mathbb{R})$ and $\Gamma = SL_2 (\mathbb{Z}) &lt; 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)":</p> <p>"Up to now no one has found a single example of a Maass form for $SL_2 (\mathbb{Z})$".</p> http://mathoverflow.net/questions/62635/are-there-any-mathematical-objects-that-exist-but-have-no-concrete-examples/62693#62693 Answer by Justin Hilburn for Are there any mathematical objects that exist but have no concrete examples? Justin Hilburn 2011-04-23T01:42:56Z 2011-04-23T01:52:26Z <p>You should look at <a href="http://www.math.vanderbilt.edu/~schectex/ccc/" rel="nofollow">Handbook of Analysis and its Foundations</a> by Eric Schecter. Here is an excerpt from the preface:</p> <p>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:</p> <p>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.</p> <p>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.)</p> <p>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.</p> <p>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.</p> <p>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.</p>