Skip to content
February 26, 2014 / porton

How proof by contradiction differs of direct proof

This my post is about mathematical logic, but first I will explain the story about people who asked or answer this question.

A famous mathematician Timoty Gowers asked this question: What is the difference between direct proofs and proofs by contradiction.

We, people, are capable of doing irrational things and to be discouraged.

I wrote an unthoughtful comment at Timoty Gowers’s blog. And this has caused Gowers to be discouraged and don’t continue to search an answer for his question. Yes, all of us, even Fields medalists such as Gowers are capable for doing irrational things.

On the other hand the irrational thing which I have done, was that I simply posted that somehow stupid comment despite of knowing that there are more about this (as described below). Note however that at the time of posting that comment I have not yet formulated the below exactly.

The trouble with my comment is that it applies only to the standard axiomatic theory of first order predicate logic. My comment is wrong for the way mathematics is usually written and is communicated. And this way differs of the customary formal predicate logic.

In customary informal mathematics the words “for all” and “exists” are not exact equivalent of {\forall} and {\exists} from first order predicate logic. The main difference is that we can have more than one proposition under a quantifier.

Examples:

For all {x \in \mathbb{R}} we have {e^x > 0} and therefore {e^x > - 1.}

In the standard first order predicate logic this would be written as two separate formulas:

{\forall x \in \mathbb{R} : e^x > 0}; {\forall x \in \mathbb{R} : e^x > - 1}.

Have you noticed that in the informal mathematics we usually require {x \in \mathbb{R}} only once and don’t write it twice as in the above formal formula?

Certainly we can invent a formalistic for this, like:

{\forall x \in \mathbb{R} : ( e^x > 0 ; e^x > - 1)}.

Here we have multiple propositions under an universal quantifier.

It can be considered formally:

{\forall x \in U : ( P_0 ( x) ; \ldots ; P_n ( x))} is a shorthand for {\forall x \in U : P_0 ( x) ; \ldots ; \forall x \in U : P_n ( x)}.

Now an example about existence quantifiers:

There exists {n \in \mathbb{N}} such that {n > 2} and therefore {n^2 > 4}.

To formalize this, consider {\exists n \in \mathbb{N} : n > 2} as a definition. After this formula we have {n} defined and it must confirm to the proposition {n > 2}.

This could be written formally as:

{( \exists n \in \mathbb{N} : n > 2) ; n^2 > 4}.

In customary logic this could be expanded to

{( \exists n \in \mathbb{N} : n > 2) ; ( \exists n \in \mathbb{N} : n^2 > 4)}.

To formalize this after the {\exists} definition we could introduce a new constant symbol ({n} in our example) and a new theorem ({n > 2} in our example). I leave as an exercise to describe the mapping from my formalistic (where {\exists} denotes not just existence but also a definition) to the reader.

Now to the claimed topic of this post, the difference of proof by contradiction and a direct proof:

Suppose now we want to prove a proposition {\forall x \in U : R ( x)}.

Proof by contradiction:

Suppose {\neg \forall x \in U : R ( x)}. Then {\exists x \in U : \neg R ( x)}.

After this we can have a sequence {( \exists x \in U : \neg R ( x)) ; P_0 ; \ldots ; P_n ; 0} of propositions using this {x}.

Or we can prove it directly: Then we would have a sequence

{P_0 ; \ldots ; P_n ; \forall x \in U: ( Q_0 ( x) ; \ldots ; Q_n ( x) ; R ( x))}.

The choice of direct proof or proof by contradiction should depend on which of these two sequences of formulas is simpler.

Now suppose we want to prove a proposition {\exists x \in U : R ( x)}.

Proof by contradiction:

Suppose {\neg \exists x \in U : R ( x)}. Then {\forall x \in U : \neg R ( x)}.

Then we would have a sequence of propositions

{\forall x \in U : ( \neg R ( x) ; P_0 ; \ldots ; P_n ; 0)}.

Or we can prove it directly: Then we would have a sequence

{(\exists x \in U: P_0 ( x)) ; P_1(x) \ldots ; P_n ( x) ; R ( x)}.

The choice of direct proof or proof by contradiction should depend on which of these two sequences of formulas is simpler.

I leave open the following topic of discussion:

Show examples that sometimes a direct proof and sometimes a proof by contradiction is shorter.

Remark: All I have written here is about classic logic. I don’t deal with intuitionistic logic.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: