9
$\begingroup$

There exist constructive and non-constructive proofs.

Sometimes, for a mathematical statement, we can have both non-constructive and a constructive proof.

However, are there statements for which there is only a non-constructive proof? (The fact that there maybe a construction of the required object but we don't know it yet doesn't count here).

Phrased differently, are there statements (that claim existence of objects) that are essentially non-constructive?

  • 3
    How about anything that we know cannot be proved in ZF, that is, requires some version of the Axiom of Choice, possibly weaker than full AC? Then there is a huge number of statements, important in standard mathematics, that only have a non-constructive proof. Hahn-Banach, existence of a non-principal ultrafilter on $\mathbb{N}$, existence of a basis for a general vector space, and so on and so on.2011-10-17
  • 0
    Could anyone give a simpler example? Moreover, what ensures that there does not exist a constructive proof for a statement?2011-10-17
  • 4
    To ensure that there is no "constructive proof", one usually constructs a model of ZF in which the statement is not true. You have not told us what is your background, so it is very difficult to know what you consider simple!2011-10-17
  • 0
    @Mariano, I think you are confusing [constructible](http://en.wikipedia.org/wiki/Constructible_universe) with [constructive](http://en.wikipedia.org/wiki/Constructivism_%28mathematics%29) (also see [SEP](http://plato.stanford.edu/entries/mathematics-constructive/)).2011-11-12

4 Answers 4

8

There exist real numbers that don't have names. You can prove this, but you can't construct such a real number, because by the very act of constructing it, you would be giving it a name.

  • 0
    If you look at constructive set theory you could probably construct the real numbers out of them. You don't really need the law of excluded middle to get to the statement you just said i.e. not all real numbers are describable.2011-10-17
  • 0
    This is just a disguised version of *computable* numbers, isn't it?2011-10-17
  • 0
    Actually, the set of computable numbers isn't the same as the set of nameable numbers. For example chaitin constant isn't computable, but you can define i.e. name it.2011-10-17
  • 0
    I actually don't think you can prove this, but I suppose it depends upon what you mean by "nameable." If a real is nameable if, say, it uniquely satisfies some formula in the language of set theory, then it is consistent that every real number is nameable.2011-10-18
  • 0
    @ccc, I'm not sure if you are responding to me or to simplicity. In any event, "names" are finite strings of symbols from a finite alphabet and are thus countably infinite, whereas reals are an uncountable infinity, hence, there are reals without names.2011-10-18
  • 0
    If this is a tacit agreement with how I defined nameable, then you are using the word "countable" two different ways. The reals are uncountable within a fixed set-theoretic universe, whereas they may be countable from the meta-universe perspective you are using to count the formulas. You may argue that the formulas may be encoded as sets in the universe, but then the map which sends a formula to the real it defines is not a set by Tarski's undefinability of truth. This is a subtle issue that is often overlooked.2011-10-18
  • 0
    @ccc, I am using "countable" the same way Cantor used it when he proved that the rationals are countable but the reals are not. Cantor and I don't know from "meta-universe perspectives," we just know there are more numbers than there are names for them.2011-10-18
  • 0
    I am sorry I am not making myself clear. Maybe this exposition at Mathoverflow will do the job better: http://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numbe/44129#44129 The point is that there are fine set-theoretic issues surrounding the notion of "definability." For example, how do you even know the nameable numbers form a set? There is no set-theoretic function that maps a name to the number it names, so the standard tools of cardinal analysis aren't accessible. So you cannot conclude that there is a non-nameable real.2011-10-18
  • 0
    I think I know that the real numbers form a set, and I think I know that the ones that have names form a subset of that set, and I think I know that any subset of a set is a set, so I think I know that the numbers that have names form a set. But I'll have a look at the link, thanks.2011-10-18
  • 1
    The reals certainly are a set, but claiming that the nameable numbers form a subset is begging the question. It sounds like you're invoking the axiom of comprehension to state that the reals with a name form a set, but this axiom only applies to collections of the form $\{x \in X : \phi(x)\}$ where $X$ is a known set and $\phi$ is a formula in the language of set theory. There is no such formula that captures the notion of nameable. I'm sorry for fussing about this, but there are limitations to the accuracy of informal set theory: this particular argument can't be formalized.2011-10-18
  • 0
    Gerry, one last comment (sorry for this extended monologue). You are perhaps thinking of superficially similar cardinality arguments to establish the existence of transcendental or noncomputable real numbers. But these arguments are critically different because the notions of algebraicity and computability are formalizable via formulas in set theory. The notion of "nameability" isn't, else you would quickly run into self-referential paradoxes: "let $\alpha$ be the least ordinal which isn't nameable."2011-10-18
7

The existence of a basis for $\mathbb R$ as a vector space over $\mathbb Q$ is a consequence of the axiom of choice but it has no constructive proof.

  • 0
    Can you point somewhere that proves it has no construction?2011-10-17
  • 0
    @Henrique, sorry I don't have a reference, except for the fact that such a basis is uncountable and the set of constructive numbers is countable. See for instance http://math.stackexchange.com/questions/58036/are-some-real-numbers-uncomputable/58043#58043.2011-10-17
  • 2
    @Henrique Tyrrell: The existence of a basis for an arbitrary vector space implies the axiom of choice, but I believe not much is known (in the sense of what version of the axiom must follow) in the specific case of the reals over the rational number field. See the following: http://www.math.lsa.umich.edu/~ablass/bases-AC.pdf and http://mathoverflow.net/questions/68950 and http://mathoverflow.net/questions/460632011-10-17
  • 2
    A basis for the reals over the rationals creates a set without the property of Baire, so you need strictly more than Dependent Choice to prove its existence. Pinning it down exactly might require a bit more work, but it definitely requires an uncountable choice principle.2011-10-18
2

There are various flavors of constructive mathematics. Depending on what you mean exactly there might be different answers. But more importantly you would like to find a statement that makes sense from constructive view-point (and has the same sense from classical viewpoint) that is provable classically but not constructively. For example, if you think about real numbers, you cannot simply talk about arbitrary subsets of real numbers since the are not well-defined constructively. In fact you cannot talk about the set of real numbers as an object like we do in classical mathematics. Moreover different definitions of real numbers are not constructively equivalent.

The example given by Gerry is not true constructively simple because they don't believe in existence of those numbers. Similar problems are involved in lhf's answer.

The simplest example that one can give of a statement that cannot be proven constructively is the principle of excluded middle for arbitrary complex formulas.

0

Two canonical examples: the axiom of choice and the law of excluded middle are both assertions that are provable in a classical setting, but they aren't provable constructively.