11
$\begingroup$

I'm giving a talk on constructive mathematics, and I'd like some snappy examples of weird things that happen in non-constructive math.

For example, it would be great if there were some theorem claiming $\neg \forall x. \neg P(x)$, where no $x$ satisfying $P(x)$ were known or knowable.

But other examples are welcome as well.

  • 0
    A standard example is the Intermediate Value Theorem, with $P(x)$ being "$f(x)=0$". But that one is not "weird"... Banach-Tarski is a pretty weird example.2012-02-15
  • 0
    @ArturoMagidin, the IVT has a constructive version based on nested intervals.2012-02-15
  • 0
    related to http://math.stackexchange.com/questions/73400/are-there-essentially-non-constructive-statements2012-02-15
  • 0
    @lhf: The IVT ultimately relies on the supremum property; the proofs of which that I can think of right now are all by contradiction and non-constructive2012-02-15
  • 1
    @ArturoMagidin, I meant the [bisection algorithm](http://en.wikipedia.org/wiki/Bisection_method). Of course, the nested-interval property is equivalent to the existence of supremum and so in this sense is non-constructive. The IVT is also equivalent to both.2012-02-15
  • 0
    @luqui: If you Google the *Probabilistic Method*, you will see that this is a technique for proving the existence of certain types of combinatorial objects, say special graphs, by showing that that positive fraction of large enough graphs has the required property. Quite often, no explicit example is known.2012-02-16

6 Answers 6