A proof is a convincing argument, given the assumptions, that something is true in that the conclusion stated follows from the assumptions.

The English word "proof" comes, through French, from the Latin word "probo" ≈ "to approve, permit, test, inspect, examine, demonstrate, prove, show". A related word is the English word "probe".

Mathematical proofs are formal. Proofs in other areas are less formal, and might be better stated as "showing convincingly" rather than "proving".

People (e.g., lawyers) will often say that an argument used "proves" their case. In reality, the argument may "show convincingly" (with high probability) their case.

• Some problems may require a demonstration that something can be done.
• Some problems may require a proof that something cannot be done.

[survey of square miles]

Matthew uses the more abstract word for "examination (to deceive)" as an intellectual exercise (in deception) with associated play on words.

Luke uses the more literal word for "trying out", "testing out", etc., with corresponding loss of the play on word meaning. How does one "test out" the face of the sky?

A contradiction is something that is inconsistent with assumptions up to the point when the contradiction is reached.

To prove a proposition p by proof by contradiction,

• The proposition p must be either true or false.
• Assume p to be false (i.e., not true).
• Show a contradiction (that is, p cannot be false).
• The conclusion is that the original assumption p must be true.

This is the method used by the logic programming language Prolog.

More: Prolog: Logical variables

There are many names for a proof by contradiction.

• Proof by contradiction
• Latin: "reductio ad absurdum" ≈ "reduction to absurdity" abbreviated as RAA (Reductio ad absurdum)
• Latin: "argumentum ad absurdum" ≈ "argument to absurdity"
• Apapogical argument
• Indirect proof
• Proof by assuming the opposite
• Reductio ad impossible
• Greek: "ἡ εἰς τὸ ἀδύνατον ἀπόδειξις" ≈ "demonstration of (into) the impossible" as outlined by Aristotle which is similar, but not identical, to what is usually called a proof by contradiction. It is restricted to certain types of syllogisms.

The English word "apagogic" means "proving indirectly" by showing the impossibility of the contrary. The word comes from the English word "apagoge" which comes from the ancient Greek word "απαγωγή" ≈ "leading away (from)".

Here are some well-known examples.

• Euclid: Infinity of primes.
• Pythagoras: Irrationality of the square root of 2.
• Turing: Halting Problem.

There are many others.

More: Alan Turing: halting problem

• It is desired to prove proposition P.
• Assume that P is false, that is not P.
• Show that not P implies false.
• This shows that assuming not P leads to a contradiction so that P must be true.

An original argument in formal terms goes back to Aristotle, described here. A few centuries earlier, Xenophanes of Colophon describes the argument in a poem. After Aristotle, Euclid and Archimedes both use the technique. Socrates and Plato, before Aristotle, use the technique in dialectical (discussion) format. The Sorites paradox is related to this technique.

Aristotle calls this "demonstration" "into" the "impossible".

• The Latin word "per" ≈ "through, by means of".

It is not clear if Aristotle wants the following compared.

• "Sophistic" "refutations". Latin: "sophismata refutandi" ≈ "sophistic refutations".
• "Demonstration" "into" the "impossible". Latin: "demonstratio ad impossibile" ≈ "demonstration to the impossible".

You are given an 8 by 8 grid. You are completely fill the grid with bricks, each 2 by 1, or prove (show) that it cannot be done. No overlapping bricks. All bricks used must be on the grid. This is easy to prove (show) by demonstration.
Aristotle's explanation of "demonstration" "into" the "impossible" can be difficult to explain and understand using his logic system and proof rules of syllogisms. The fill the grid problem will be used to explain the essence of Aristotle's method.

Aside: I started using this problem as part of the problem solving part of introductory computer science courses in the late 1980's.

You are now given an 8 by 8 grid two opposite corners removed. You are to either completely fill the grid with bricks, each 2 by 1, or prove (show) that it cannot be done. No overlapping bricks. All bricks used must be on the grid.
Proving that something cannot be done is "impossible" using Aristotle's method of syllogisms. Thus, one must "go away (from)" "into" the "impossible" by going outside the system of syllogisms by assuming it can be done and then finding a contradiction.

• Assume or agree that the bricks can fill the grid.
• Find a contradiction. If found, there is agreement that it cannot be done.

Aside: The Greek word for "agree" (going both ways) is the word often translated as "confess" (going one way) in the GNT (Greek New Testament).

You are now given a 7 by 7 grid with two opposite corners removed. You are to either completely fill the grid with bricks, each 2 by 1, or prove (show) that it cannot be done. No overlapping bricks. All bricks used must be on the grid.
One can use the same method for this problem.

• Assume or agree that the bricks can fill the grid.
• Find a contradiction. If found, there is agreement that it cannot be done.

Hint: The contradiction in this problem is not the same contradiction as the previous problem.

Aristotle developed syllogisms as a way to use logic to show that certain propositions were true. This system does not work well, in general, for showing that propositions are false. Here is an outline of the method described by Aristotle.

We can show that syllogism A: p1 and p2 is true. This is a obstensive proof.

We agree that syllogism B: p1 and p3 is false but cannot prove it.

We negate p3 and show that syllogism C: p1 and (not p3) is true and, thus, has contradictions. This is an obstensive proof.

We conclude, using "proof" "into" the "impossible" that syllogism B is false. The name "proof" "into" the "impossible" appears to come from step B - the step that is to be proven false and is "impossible" to prove using syllogisms. Steps A and C are normal syllogisms.

Thus, the solution goes "away from" B as "into the impossible" and thus, towards C.

Note that since the result is mechanically obtained from the expression or formula of the syllogism, they can be considered as one entity.


Note that the problem solution requires that the expression (not p3) be simplified before solving the syllogism.

The translator (top), Hugh Tredennick (1939), takes liberties both with the word order and the meanings of some words. This may be because of not fully understanding the technical and logical argument being made by Aristotle.

[published logarithmic tables of the 1800's]

• "ἀναιρέω" ≈ "take away, cancel, answer" translated as "refute"
• "ἀπάγουσα" ≈ "leads away from" translated as "reducing" or "reduction".
• "εἰς" ≈ "into" sometimes translated as "per" (Latin tradition).
• "ὁμολογούμενον" ≈ "agreed (on)" translated as "admitted" and often translated as "confessed".
• "ψεῦδος" ≈ "falsehood" and the prefix of English words starting with "pseudo".

An expression (that expresses a value) reduces from a combined form to a simpler form.

• 2+3 reduces 5 (the reduced value).
• 5 does not reduce to 2+3 (a combined form with parts). In functional programming languages (and programming language theory) one can abstract 5 to 2+3 (and many similar values). Deciding on which abstraction to use is important for a given problem being solved.

Paraphrase using table: Proof B, "into" the "impossible", is different from proof A (and C) in that B asserts what it claims to refute/cancel by "leading away from" "into" that assumed fallacy or false result (B, which cannot be proven using syllogisms). Both A and C admit (agree to) two (valid) syllogism requirements (p1, p2,not p3). (B does not).

What is "impossible" here? What is "impossible" is solving B as a syllogism. Thus, one must "lead away from" "into" the "impossible" (that is, B), and (instead) to C, which can be solved as a syllogism.

One idea:

In a constructive/obstensive proof, one reduces A to B. Thus, the expression (that expresses a value) reduces from 2+3 to 5 (the reduced value) and not from 5 to 2+3.

In a demonstration proof "into" the "impossible" one goes away from "into" B thus towards showing that A cannot be true.

This is the follow-on part by Aristotle (not needed here).

Hypothesis testing in statistics is similar to proof by contradiction in mathematics.

... more to be added ...