Does the existence of a mathematical object imply that it is possible to construct the object?

Question

In mathematics the existence of a mathematical object is often proved by contradiction without showing how to construct the object.

Does the existence of the object imply that it is at least possible to construct the object?

Or are there mathematical objects that do exist but are impossible to construct?

Answer 1

Really the answer to this question will come down to the way we define the terms "existence" (and "construct"). Going philosophical for a moment, one may argue that constructibility is a priori required for existence, and so ; this, broadly speaking, is part of the impetus for intuitionism and constructivism, and related to the impetus for (ultra)finitism.$^1$ Incidentally, at least to some degree we can produce formal systems which capture this point of view (although the philosophical stance should really be understood as preceding the formal systems which try to reflect them; I believe this was a point Brouwer and others made strenuously in the early history of intuitionism).

A less philosophical take would be to interpret "existence" as simply "provable existence relative to some fixed theory" (say, ZFC, or ZFC + large cardinals). In this case it's clear what "exists" means, and the remaining weasel word is "construct." Computability theory can give us some results which may be relevant, depending on how we interpret this word: there are lots of objects we can define in a complicated way but provably have no "concrete" definitions:

• The halting problem is not computable.

• Kleene's $\mathcal{O}$ - or, the set of indices for computable well-orderings - is not hyperarithmetic.

• A much deeper example: while we know that for all Turing degrees ${\bf a}$ there is a degree strictly between ${\bf a}$ and ${\bf a'}$ which is c.e. in $\bf a$, we can also show that there is no "uniform" way to produce such a degree in a precise sense.

Going further up the ladder, ideas from inner model theory and descriptive set theory become relevant. For example:

• We can show in ZFC that there is a (Hamel) basis for $\mathbb{R}$ as a vector space over $\mathbb{Q}$; however, we can also show that no such basis is "nicely definable," in various precise senses (and we get stronger results along these lines as we add large cardinal axioms to ZFC). For example, no such basis can be Borel.

• Other examples of the same flavor: a nontrivial ultrafilter on $\mathbb{N}$; a well-ordering of $\mathbb{R}$; a Vitali (or Bernstein or Luzin) set, or indeed any non-measurable set (or set without the property of Baire, or without the perfect set property); ...

• On the other side of the aisle, the theory ZFC + a measurable cardinal proves that there is a set of natural numbers which is not "constructible" in a precise set-theoretic sense (basically, can be built just from "definable transfinite recursion" starting with the emptyset). Now the connection between $L$-flavored constructibility and the informal notion of a mathematical construction is tenuous at best, but this does in my opinion say that a measurable cardinal yields a hard-to-construct set of naturals in a precise sense.

---

$^1$I don't actually hold these stances except very rarely, and so I'm really not the best person to comment on their motivations; please take this sentence with a grain of salt.

Answer 2

There exists a Hamel basis for the vector space $\Bbb{R}$ over $\Bbb{Q}$, but nobody has seen one so far. It is the axiom of choice which ensures existence.

Answer 3

I am not sure if "constructible" in this context is related, but I think this example also counts.

Not all the regular polygons are constructible. The Gauss–Wantzel theorem stated that,

A regular $n$-gon is constructible with compass and straightedge iff

• $n$ is a Fermat prime (A prime in form of $2^{2^m}+1$)
• $n=2^k$
• $n$ is the product of a power of $2$ and distinct Fermat primes.

So, for instance, regular heptagon ($7$-gon) exists but it is not constructible.

Answer 4

As others already said, it dependes on your notion of constructible.

Can you construct infinite objects? I think most people agree that you can construct any natural or integer or rational number. But the whole set is infinite. Can you construct it? On the other hand, most real numbers are "infinite" themselves. Can you construct $\sqrt{2}$? What about $\pi$ or $e$?

Things get complicated. Once you have a precise definition for $\pi$, you can trivialy construct it with this steps:

1. Take $\pi$.
2. Done.

Is that satisfactory?

Constructive Mathematics (see also links therein) attempt(s) to answer your question. Unfortunately, once you deviate from traditional mathematics, you face the reality of it: a human endeavour. I.e. multiple interpretations, different logics, proof systems, axioms sets, notations... So there are also multiple approaches to constructive mathematics...

Answer 5

It may be worth mentioning that Errett Bishop developed his version of constructive mathematics precisely because of his disillusionment with his earlier research in complex analysis which he felt involved objects that don't admit any construction. His last work in classical mathematics was the article

Bishop, Errett. Differentiable manifolds in complex Euclidean space. Duke Math. J. 32 1965 1–21

which was and continues to be influential. After 1965, he published about a dozen articles, all dealing with constructive mathematics.

Answer 6

Taking yet another definition of the terms, a 6 dimensional surface trivially exists, but I'm not sure what one would construct it from in the real world, so the object exists but cannot be (physically and real-world) constructed

Answer 7

I come from computer science and would like to define "construct" like this:

A real decimal number is constructible if you can write a program that prints out digits of the number forever. A decimal point must be printed at some time. The program must be of finite fixed size but can use more and more memory without limit as further digits are computed.

Given this definition, it is possible to describe a number that exists, but is impossible to construct.

This is related to the Halting Problem. Like in any version of the HP, we assign a number to each possible computer program in a certain language. The Halting Problem Theorem then states that there is no finite program that can decide whether another program will halt or get caught in an infinite loop.

In this version, we then asks for the real number between $0$ and $1$ where digit number $n$ after the decimal point is $1$ if program number $n$ halts and $0$ otherwise.

Any given program $n$ will either halt, or it will not. This means the number is well defined and exists.

However, writing an actual program to compute it would violate the HPT, so that is impossible.

Answer 8

Another sort of an example: there is a positive real $x\approx 1.16730397826142$ where $x^5-x-1=0$. The Intermediate Value Theorem proves that there is one. But it can't be constructed: we do not have the mathematical language to express it.