# What is the most useful non-existing object of your field?

When many proofs by contradiction end with "we have built an object with such, such and such properties, which does not exist", it seems relevant to give this object a name, even though (in fact because) it does not exist. The most striking example in my field of research is the following.

Definition : A random variable $X$ is said to be uniform in $\mathbb{Z}$ if it is $\mathbb{Z}$-valued and has the same distribution as $X+1$.

Theorem : No random variable is uniform in $\mathbb{Z}$.

What are the non-existing objects you have come across?

• – Emil Jeřábek supports Monica Sep 28 '14 at 22:05
• I'm not sure why this question is being so heavily downvoted; it's certainly on the really soft end, but I think it can lead to some interesting answers. +1 (if only to counteract said downvotes). – Noah Schweber Sep 28 '14 at 22:21
• Since the phrase "proof by contradiction" was invoked, I'll recall the distinction between "proof of negation" and "proof by contradiction", as explained by Andrej Bauer here: math.andrej.com/2010/03/29/…. For proofs of negation, one supposes a proposition $\phi$ is true and derives a contradiction; therefore $\phi$ is false. A proof by contradiction supposes $\phi$ is false and derives a contradiction; therefore $\phi$ is true. Intuitionists accept proofs of negation, but not proof by contradiction! – Todd Trimble Sep 28 '14 at 23:59
• There is a related question on matheducators.se. – Ben Barber Sep 29 '14 at 6:36
• @RickyDemer: A similar phenomenon occurs when one comes up with a list of nice properties for an object to have, then proves that no object can simultaneously have all of them. It is then often very interesting to search for ways to weaken the conditions to get an object that does exist. As a familiar example, there does not exist a countably additive, translation invariant, set function $\mu : \mathcal{P}(\mathbb{R}) \to [0,\infty]$ with $\mu([0,1]) = 1$. Lebesgue had the brilliant idea to fix this by defining $\mu$ only on an appropriate subset of $\mathcal{P}(\mathbb{R})$. – Nate Eldredge Sep 29 '14 at 7:08

The elliptic curve attached to a nontrivial solution of $x^n+y^n=z^n,\quad n>2$.

• This is about the only example I've seen so far that actually has been given a special name (see the opening paragraph of the OP): it's called the Frey curve. (Edit: well, now there are others, such as Reinhardt cardinal.) – Todd Trimble Sep 29 '14 at 7:08
• There are no non-zero weight $2$ cuspforms for $\Gamma_0(2)$. There are also no elliptic curves over $\Bbb Q$ with a rational $4p$-isogeny for $p \geq 5$. Both of these play a role here. – Jamie Weigandt Sep 29 '14 at 23:19
• I'm not a mathematician, but doesn't it have to be specified (as in Fermat's theorem) that $n, x, y, z \in \mathbb{N}_1$? Or are there no non-integer solutions? – l0b0 Sep 30 '14 at 7:05
• @l0b0 If one were being fully formal, then yes, that would have to be specified. But in a context of people talking who can follow the reference implied by the technical terms "the elliptic curve attached to...", it's tacitly understood; it goes without saying. :-) – Todd Trimble Sep 30 '14 at 14:37
• @ToddTrimble In fairness, it should be noted that Hellegouarch defined these curves associated to Fermat solutions and used them to prove some interesting things relating Fermat solutions to rational torsion points on elliptic curves. I believe that this was before Frey started looking at them. Not to take anything away from Frey, who made the key observation that these curves provide a link between Fermat and the modularity conjecture. Anyway, although it makes for a longer name, these non-existent curves might better called Frey-Hellegouarch curves. – Joe Silverman Oct 1 '14 at 13:58

An infinite strictly decreasing sequence of positive integers.

Silly as it might seem, it is the clue for a technique called Fermat descent and which is still nowadays of crucial importance in arithmetic/diophantine geometry. Fermat's idea was to take an integer solution in positive integers $(a_1,b_1,\dots,c_1)$ to some diophantine equation he had in mind, and then to massage it in order to create another solution $(a_2,b_2,\dots,c_2)$ still in positive integers but with $a_2<a_1,b_2<b_1,\dots c_2<c_1$: due to the non-existence quoted above, this was a contradiction and he won in proving the diophantine equation in his hands had no solution at all (in positive integers, it might sometime had "the trivial one", namely $(0,\dots,0)$). Although only vaguely reminiscent of this technique, the much more sophisticated "étale descent" owes its name to Fermat's.

• Surely that should be a strictly descending infinite sequence? – user253751 Oct 1 '14 at 3:14
• Ah, yes, that is what I meant... – Filippo Alberto Edoardo Oct 1 '14 at 12:24

A very well-known example, whose importance in set theory and the foundations of mathematics can't be easily overstated, would be Russell's set of the sets which don't contain themselves.

• This is interesting, since it puts the cart before the horse: this set does exist in Frege's set-theory, which Russell used to prove it inconsistent. Russell's set-theory was specifically defined to exclude such objects. Hence the theory is derived from the object's existence, rather than vice versa :) – Warbo Sep 29 '14 at 12:56
• One can also argue that this one does exist, perfectly happily: it’s just a class that isn’t a set. – Peter LeFanu Lumsdaine Sep 29 '14 at 20:12
• @PeterLeFanuLumsdaine yes, but it's worth pointing out that relative to 19th century set theory, classes are part of hierarchical set theory, which I believe is what Frege tried to rigorize. (Or was it Russell. I'm rusty.) – djechlin Sep 30 '14 at 17:35
• This is sometimes called the Russell set, or Russell class. Its so dangerous, even NFU blocks it. – goblin Sep 30 '14 at 19:47
• It is not even an object in your area, because it can't even be defined. – shuhalo Oct 1 '14 at 13:01

A polynomial-time algorithm for SAT (satisfiability), the problem of whether a boolean logical formula has a setting of its variables that makes it true.

(It's not quite in the letter of the question because we do not know that it does not exist.)

Primarily, we show that problems are NP-hard by reducing SAT (or another NP-hard problem) to those problems in polynomial time. The argument is thus that, if we have a polytime algorithm for those problems, then this constructs a polytime algorithm for SAT. Since we do not believe this mythical creature exists, we do not think those problems can be solved efficiently. (not sure if all mathematicians are already aware of this or whether the summary is useful.)

If we had this polynomial-time algorithm for SAT, then we could prove theorems quickly and automatically, we could break cryptosystems, we could improve massively in all sorts of scheduling, routing, resource allocation, and other optimization problems -- in short, "useful" would be an understatement.

(Let me add -- what's really "useful" is the converse: if this object does not exist, then we know that these sorts of tasks cannot be accomplished.)

• In a similar vein, we might consider an algorithm for the halting problem. – Steve Huntsman Sep 29 '14 at 3:29

The path integral!

I realize that it's not in the spirit of the question, but it's too good not to mention.

• Neither is $\mathbb{F}_1$, but if we are liberal and admit such chimerical entities, then both are worthy of mention! – Todd Trimble Sep 29 '14 at 16:30
• Definitely too good not to mention! – Peter Samuelson Sep 29 '14 at 17:04
• Hm, in what sense does it not exist? – Ruslan Oct 3 '14 at 4:06
• The sense in which it does not exist is that it has never been defined mathematically. Here, it's important to distinguish "define" and "compute". Physicists know how to compute (some) path integrals, but they don't know how to define them. Mathematicians, on the other hand, refuse to deal with concepts that havn't been defined. I should point out that there is mathematical work whose goal is to define path integrals (e.g. Glimm & Jaffee's book) but a lot of the path integrals considered by physicists fall outside the scope of that book. That being said, I'm really not an expert on all that. – André Henriques Oct 3 '14 at 20:32
• I think this answer is not really in the spirit of the question. The question says many proofs by contradiction end with "we have built an object with such, such and such properties, which does not exist". Otherwise, besides $\mathbb{F}_{1}$, I think motives would definitely deserve a place in this list. Both $\mathbb{F}_{1}$ and motives (and also path integrals, as far as I can see) are really important guidelines, that help us develop theory, even though we do not know whether they exist. We surely hope they do exist. But such objects is not what this question is about… – jmc Dec 31 '14 at 12:33

A number which is less than 1 and greater than 1.

EDIT: Since my attempt at provocation was understandably taken as mere frivolity, or rudeness for its own sake, let me risk self-advertising by pointing to some examples: the argument just before the statement of Corollary 4.9 in arxiv.org/abs/0801.3415; or Lemma 3.6 in arxiv.org/abs/0811.4432; or Lemma 3.2 in arxiv.org/abs/0906.2253

• Integers (strictly) between 0 and 1 form the basis of transcendental number theory. – NAME_IN_CAPS Sep 28 '14 at 23:04
• I should perhaps explain that behind my frivolous phrasing is a serious point: see the argument just before the statement of Corollary 4.9 in arxiv.org/abs/0801.3415 , or Lemma 3.6 in arxiv.org/abs/0811.4432 , or Lemma 3.2 in arxiv.org/abs/0906.2253 – Yemon Choi Sep 28 '14 at 23:09
• Yemon, your follow-up definitely improves your answer. Answers should provide some context, rather than being baldly obviously nonexistent items. – Todd Trimble Sep 28 '14 at 23:15
• I use the non-existence of a number that is both positive and negative much more often then the non-existence of a number that is less than and greater than $1$. However, the non-existence of a number that is both positive and negative follows easily: Let $x$ fulfill i) $x<1$ and ii) $x>1$. Then for $y = x-1$ we have by i) that $y<0$ and by ii) that $y>0$ and hence, $y$ has the desired properties. Since $x$ does not exist, $y$ also does not exist either. – Dirk Sep 29 '14 at 17:40
• +1 I was going to post this myself (or rather an integer between 0 and 1) if you hadn't beaten me to it. See my answer to this MO question: mathoverflow.net/questions/129364/… – Timothy Chow Sep 29 '14 at 20:07

Three examples that come to my mind (not from my field)

• The free complete lattice on three generators. On a first sight, it seems harmful to construct this structure by transfinite induction, that is "from below", as an increasing union of sets each labeled by some ordinal, starting from $\{a,b,c\}$. The problem is that one would need all ordinals: in other words, the free complete lattice on three generators is a proper class (for a proof, see e.g. P.T.Johnstone's Stone Spaces, ch I ).

• Non-commutative finite fields. These have a lot of useful and interesting properties, the most relevant of which, after Wedderburn's theorem, is possibly non-existence.

• I really like your way of counting (-; – jmc Sep 29 '14 at 8:05
• The third example does not exist, which is exactly what we're looking for! – Toby Bartels Sep 29 '14 at 9:19
• So, naively, I would guess that the free Boolean algebra on 3 generators has 8 elements, and is thus complete. Am I wrong? – André Henriques Sep 29 '14 at 10:21
• @AndréHenriques: Actually, it has $2^8$ elements. But you are correct that free complete Boolean algebras on finite sets exist (and are the same as free Boolean algebras). Free complete Boolean algebras on infinite sets do not exist. – Eric Wofsey Sep 29 '14 at 11:14
• Maybe it should be added that free suplattices on any set exist, and suplattices admit arbitrary infs (so are complete). Here, the morphisms of $\mathbf{SupLat}$ preserve just sups. Similarly, the free inf-lattice exists on any set, and this admits arbitrary sups. It's when we require morphisms of the category to preserve both arbitrary sups and infs that free objects do not exist (on sets of cardinaility greater than 2). – Todd Trimble Sep 29 '14 at 12:38

Generic filters, in forcing. As long as $\mathbb{P}$ is not trivial, no truly generic filters through $\mathbb{P}$ exist, yet we use "them" all the time.

Okay, one's mileage might vary with this answer depending on philosphy: for example, if we're working in something like a set-theoretic multiverse, then we can say that generic filters always exist, in an appropriate sense; in the opposite direction, one could argue that - insofar as what we are using forcing for is producing independence results - we only really use filters which are generic with respect to some countable model, which certainly exist. And a multiverse-type approach can subsume this perspective, if we view every universe as potentially countable; when I'm thinking seriously about the philosophy of set theory, this is certainly the point of view I adopt. But when I'm actually doing set theory, I naively assume that (1) there is a "real" set-theoretic universe $V$, and (2) generic filters over $V$ "exist," so in that sense I'm using nonexistent objects.

Not quite in my field, but: Reinhardt cardinals.

• We don't know that they don't exist yet! They might exist in $\lnot\sf AC$ worlds. – Asaf Karagila Sep 29 '14 at 15:19
• My world is an AC world. – Emil Jeřábek supports Monica Sep 29 '14 at 15:49
• You only have one world? Poor guy, do you need a few? I have spares. :-) – Asaf Karagila Sep 29 '14 at 15:50
• Nah, thank you, but so far I’m content to live in the world that is given to me. Anyway, the question asks for “non-existing objects you have come across”, not objects non-existing in every imaginable world. – Emil Jeřábek supports Monica Sep 29 '14 at 17:10
• The world is his choice, isn't it? – Hagen von Eitzen Oct 6 '14 at 15:16

The program $H$ which computes the function $$h(P,x)=\begin{cases} 1 & \text{If program P will terminate on input x}\\ 0 & \text{otherwise} \end{cases}$$

This function (and the program that computes it) forms the basis of the most common proof of the impossibility of a solution solving the Halting Problem..

Thus it forms the basis of many proofs of in-computability, by showing that if some function $g$ (computed by a Program $G$), then $g$ would have the properties of $h$ and thus the would not be computable (and thus $G$ does not exist)

These impossible programs are known as "halting oracles"; in fact, there's a whole hierarchy of them! h above only solves the program halting-problem. Since the oracle can't be a program, it can't solve its own halting problem. We can define an oracle h2 to solve the program-halting-oracle-halting-problem, but then we need another oracle h3 to solve the program-halting-oracle-halting-oracle-halting-problem, and so on.

• Incidentally, while a software solution cannot exist, we cannot yet exclude a hardware based solution involving exotic material. (Incidentally the laws of physics have a condition: a potential paradox is not an error. If you actually fed in the forbidden input that would cause the paradox, something will intervene and change the output.) – Joshua Sep 30 '14 at 20:43
• These impossible programs are known as "halting oracles"; in fact, there's a whole hierarchy of them! h above only solves the program halting-problem. Since the oracle can't be a program, it can't solve its own halting problem. We can define an oracle h2 to solve the program-halting-oracle-halting-problem, but then we need another oracle h3 to solve the program-halting-oracle-halting-oracle-halting-problem, and so on. – Warbo Oct 1 '14 at 21:04
• @Warbo: That is interesting. As this is community wiki, feel free to edit it into the answer – Lyndon White Oct 1 '14 at 23:56

In intuitionistic mathematics, a non-constant function from $\mathbb R$ to $\{ 0 , 1 \}$.

Many classical theorems can be proved to fail intuitionistically by showing that they imply this or something much like it. (Probably the most common thing is to show that the classical theorem implies the theorem $$\forall \, x , y \in \mathbb R , \; x = y \; \vee \; x \ne y \text ,$$ which doesn't look like the existence of a thing; but this is equivalent to the existence, for each real number $x$, of a function $f$ from $\mathbb R$ to $\{ 0 , 1 \}$ such that $f ( y ) = 1$ iff $x = y$.)

More generally, in constructive mathematics, we don't usually assume that such functions don't exist, but we also understand that we can't prove that they do. So this still demonstrates that classical theorems can't be proved constructively (at least, not without being modified).

In a more neutral framework, we might speak of a non-constant continuous function from $\mathbb R$ to $\{ 0 , 1 \}$, or of a non-constant computable function from $\mathbb R$ to $\{ 0 , 1 \}$.

A field $F$ with algebraic closure of degree $3$ over $F$.

Useful because: It is the first restriction on the structure of absolute Galois groups of fields: they have no torsion except for involutions. This result, due to Artin and Schreier was the starting point of much of modern Galois theory.

• Why is this useful? – user9072 Oct 4 '14 at 20:05
• Because it is the first restriction on the structure of absolute Galois groups of fields: they have no torsion except for involutions. This result, due to Artin and Schreier was the starting point of much of modern Galois theory. – user59047 Oct 5 '14 at 11:32
• Thanks for the elaboration. I upvoted now. The downvote was not mine. – user9072 Oct 5 '14 at 12:17

Another "not quite my field" example, plus it is not known yet if this is an answer to your question: Siegel zeros.

It is not my field, but I would like to mention this example anyway since when I learned it some time ago I was very impressed. In quantum field theory, in particular in quantum electrodynamics, one assumes existence of the whole theory, namely operator valued functions on $\mathbb{R}^{3+1}$ which should satisfy various properties, e.g. equivariance under the Poincare group, equal time commutation relations, existence of in and out states. However existence of such objects is not proven in physically interesting situations, e.g. for quantum electrodynamics in 4d. For me, as a mathematician, it was quite shocking and took a long time to realize that such advanced and non-trivial objects are only believed to exist, and were not constructed even in any non-rigorous sense. Moreover as far as I heard, now it is believed that some of these theories even should not exist (!), but they worked well so far since they are expected to be good approximations to more sophisticated (probably) existing theories.

• Can you elaborate on this issue you raised on QFT? – Alan Feb 7 '15 at 13:33

The complex number $i$, which does not exist in the field of real numbers. (Please note the pun)

• @downvoter if you don't like the joke, it's enough just not to laugh. – Ryan Reich Sep 29 '14 at 12:46
• Interesting choice; the same could be said of -1! – Warbo Sep 29 '14 at 13:00
• @Warbo: might as well go all-in and say 0 ;-) – Steve Jessop Sep 30 '14 at 8:25
• Neither $-1$ nor 0 works, as they are contained in every field. – Ryan Reich Sep 30 '14 at 12:46
• I didn't catch the pun at first; I think that you edited it to make it more obvious. But at a very elementary level, i, −1, and 0 are all legitimate examples of what the question is asking for, even though only the first of these fits the pun. – Toby Bartels Sep 30 '14 at 17:08

How about an infinite (strictly) descending sequence in a well-founded relation? It does not have a special name because it does not exist for trivial reasons. But it fits the description, there are tons of proofs where people construct infinite descending sequences of natural numbers, ordinals etc.

Non-trivial approximate subrings of ${\bf R}$ or of ${\bf F}_p$.

The existence of such objects is ruled out by a number of "sum-product theorems", a typical one of which asserts that given a subset $A$ of ${\bf F}_p$ that is not extremely large or extremely small, either the sum set $A+A$ or the product set $A \cdot A$ has to be significantly larger than $A$.

On the other hand, one can improve upon the "trivial bound" in many arguments in arithmetic combinatorics or combinatorial geometry by analysing a putative configuration that attains this trivial bound and showing that it ultimately must arise from an approximate subring. Some early examples of this are in

Bourgain, Jean; Katz, N.; Tao, Terence C., A sum-product estimate in finite fields, and applications, Geom. Funct. Anal. 14, No. 1, 27-57 (2004). ZBL1145.11306.

There are now dozens of other places where this sort of argument appears. (Analogous arguments also appear in other fields, e.g. using the "group configuration theorem" from model theory, or the "group chunk theorem" in algebraic geometry.)

The core model. To a large extent, inner model theory (my area of set theory) is about building the core model K which then under any reasonable hypothesis is shown to not exist.

Not my field per se either, and maybe this is more pedestrian than some of the other examples offered thus far, but it seems that a lot of arguments involving Riemann surfaces rely on the fact that if $M$ is a compact Riemann surface of genus $g>0$, there is no meromorphic function on $M$ with a single, simple pole.

• In a similar vein, one could think of a non-constant holomorphic function from $\mathbb{C}$ to the unit disc. (But this sounds to me more like a contradiction than "we have built a natural object that turns out not to exist", probably because of the "non-constant" condition that is phrased negatively. I do not have this feeling for the random variable that is uniform in $\mathbb{Z}$. I willingly admit that this is highly subjective.) – user56097 Sep 29 '14 at 4:07

Approximation-preserving reductions between optimization problems in the same complexity class.

This may require a bit of explanation. My trade is developing polynomial approximation algorithms for various computational problems that are known to be NP-hard. Most of these problems polynomially reduce to each other; if the reductions could be extended to the corresponding approximation algorithms I (as well as numerous other mathematicians and software engineers) would be out of business.

However, one of the consequences of PCP theorem is that, provided that $NP\neq P$, the existence of a polynomial reduction between problems does not imply the existence of a polynomial reduction between the corresponding approximation problems.

A variety of algebras of a fixed type (e.g. groups, rings, Lie algebras, semigroups) that contains only finitely based subvarieties is called a Specht variety. It is known, as early as the 1980s, that maximal Specht varieties of semigroups do not exist. But some maximal Specht varieties of monoids were recently discovered; this is quite surprising given how close semigroups and monoids are.

• Are maximal Specht varieties of semigroups useful? – Noah Schweber Sep 28 '14 at 23:24
• @Noah: One way it can be helpful (at least to me) is in the investigation of (non-)finitely based semigroups. (The maximal Specht varieties of monoids helped a lot in my work on varieties of monoids.) – E W H Lee Sep 28 '14 at 23:31

In the study of NF(U) set theory, the (graphs of the) singleton function restricted to the universe or the ordinals. The absence of these sets is how NF avoids Cantor's paradox and Burali-Forti, and often the simplest disproof of some property comes from showing that the property would entail the existence of these functions.

Proper unramified extensions of $\mathbf{Q}$ (Hermite-Minkowski).

Analogously: Non-trivial Abelian schemes over $\mathrm{Spec}\,\mathbf{Z}$ and other small rings of integers of number fields (Fontaine).

Infinitely many rational points on curves of genus $>1$ over number fields (Faltings, Vojta, Bombieri).

The Fundamental Theorem of Hopf Modules: Every Hopf module over a Hopf algebra is trivial.

Several of the classical proofs of major results in Hopf algebras involve constructing/defining a Hopf module such that the theorem desired holds precisely when this Hopf module is trivial. So the non-existence of a non-trivial such object is quite important.

The concept of Hopf module has of course been generalized (in many different ways), though their triviality is no longer guaranteed in such broader contexts.

Modular cusp forms of weight 2 for $\mathrm{SL}_2(\mathbb Z)$ or $\Gamma_0(2)$. Their non existence is a key ingredient for the non existence of the elliptic curve $y^2=x(x-a^p)(x+b^p)$, where $a^p+b^p=c^p$ is a counterexample to FLT and other similar diophantine equations.

Great question! Gromov's proof of the nonexistence of compact exact Lagrangian submanifolds $L \subset \mathbb{R}^{2n}$ (as well as few other non-existence results proved there). Gromov'es work in general could be mentioned as the starting of modern symplectic geometry - but the result itself showed that Lagrangian submanifolds exhibit special intersection \ non-existence properties (toghether with the Lagrangian Arnold conjectures, and other results from that time) paving the way to ideas such as Lagrangian Floer homology, Fukaya categories, etc...

This isn't a precise 'proof by contradiction' answer (although there are potentially ways to make it so, using descriptive set theory techniques), but more a matter of guiding philosophy.

In the class of second-countable locally compact groups, there is a general dearth of 'universal' objects (e.g. a group in the class such that all groups in the class appear as closed subgroups) and embedding theorems (analogous statements to things like 'every countable group embeds in a 2-generator group'). This is in contrast both to the more special classes of countable groups and second-countable compact groups, and also to the more general class of Polish groups.

By itself, this is inconvenient: we can't hope to prove many general results about locally compact groups by first passing to our favourite universal object and then analysing its structure in detail. But what is being hinted at here is that any given (second-countable) locally compact group is in some sense 'much smaller' than the class as a whole. This gives the possibility to prove some surprisingly strong finiteness properties, once one puts the appropriate caveats around compact groups and discrete groups. This sense that any individual group in the class is small has long been known for connected locally compact groups (modulo a compact normal subgroup, such a group is a finite-dimensional Lie group; especially once you pass to the associated Lie algebra, having finite dimension is obviously a very powerful finiteness property); we are now beginning to understand it also for totally disconnected locally compact groups.

$\newcommand{\R}{\mathbb{R}}$ Related to the original example of the OP: In Bayesian statistics, "non-informative prior distributions", there is even a paper with that in the title! http://www.uv.es/~bernardo/Dialogue.pdf

For example, in the spirit of the OQ, a noninformative prior on $\R$ can be defined as the distribution of a random variable $X$ such that $X+c$ has the same distribution as $X$. No such random variable exists, but if we calculate formally, the constant density function $f(x)=1$ fits the bill, even if it is not a probability density function, its integral being $\infty$.

An onto endomorphism $\phi$ of a finitely generated hopfian semigroup $S$ for which there would exist a cofinite proper subsemigroup $T$ with $\phi(T)=S$.

The mere statement and the idea of proof reminisces from far away of Poincare Recurrence Theorem, though this story is purely combinatorial and uses very delicate rewriting procedure!