Tuesday, August 5, 2008

Nonconstructive proofs

What is the simplest method to prove a statement? Well, this depends on the statement you want to proof. If, for example the statement you want to prove is: "There exists a positive number large than 2 on the real line", you can just choose a number, for example 3, and show that according to the order axioms it is large than 2. Thus, you will have an example that you constructed.

However, it is not that always that simple. Even when you are asked to show that something exists, sometimes it turns out that to proof this existence you will not need to actually construct anything. An example of this is the theorem: "Not all numbers real numbers are rational". While it is possible to proof this by simple construction, there is another way to show this which doesn't require any construction, but only three theorems from Set Theory:
1. R is uncountable
2. Q is countable
3. For any two sets A-countable, B-uncountable, B\A- is uncountable.

The statement than follows immediately, and even in a stronger version - instead of showing that there are irrational numbers we showed that "most" of the real numbers are irrational. However, we don't get a concrete number from this proof. The fact that such proves are possible was a cause to a rather major disagreement between mathematicians in the past. Now it is a well excepted.

In the example above, I showed a statement which can be proved by construction and without construction. But are there statements that cannot be proved by construction, but can be proved without construction? It turns out that there are such statements. Lets prove that: "There exists an irrational number which when raised to an irrational power will be rational".
It sound hard, but it is surprisingly easy. Lets look on the number:

If the number is rational, the statement is proven, because the square root of two is irrational. If it is not rational, lets look on:


Since 2 is rational, we are done.

The problem is that we have don't know if is rational or not, and therefore we don't have a construction. But we know for sure that the statement is true.

No comments: