This subsection of the lecture is devoted to the presentation of an indirect method of checking the validity of formulas also called  "apagogic proofs". The idea consists in assuming the negation of original claim, deducing from this that one of the assumptions is a false or  an absurd result, and then conclude that the assumption must have been wrong. This type of proving is sometimes named  proving by reduction to nonsense or proving by contradiction. The examples presented below are based on this principle.
 

Example 6.5.1

We want to prove that this proposition is a tautology of the propositional calculus, i.e. irrespective of the valuation of the  component propositions the whole expression has always value 1.

Assume that it is not true, i.e. there exists an interpretation v of α, β, γthat ((( α ∧ β ) → γ) → ( α → ( β → γ )))(v) = 0. Because the implication  can take 0 value only in one case, therefore, it  must be

1. ((( α ∧ β) → γ ))(v) = 1 and
2. ( α → ( β → γ))(v) = 0

According to the implication's property and (2) we obtain

3. ( α)(v) = 1
4. ( β → γ)(v) = 0

It follows from (4) that ( β)(v) = 1 and ( γ)(v) = 0. Hence, with (3) we conclude ( α ∧ β)(v) = 1, and therefore (( α ∧ β) → γ)(v) = 0, what  contradicts (1).

Thus, our starting assumption is not true, i.e. the formula ((( α ∧ β) → γ ) → ( α → ( β → γ)))(v) = 1 always holds. ♦

The  scheme which was used in the example 6.5.1 is based on the fact that by the supposition of falsity of the proved proposition we conclude the property (1) and after a while we find out its contradiction. Because there is no interpretation in which it may be at the same time satisfied and non-satisfied, then the considered formula is a tautology, i.e. is valid for every valuation of its propositional variables.

A simplified version of our apagogic method of reasoning presented in the example 6.5.1 is shown on the figure 6.4.1. Each horizontal lines split next steps of the presented proof. As a result of the first four steps we obtain values of the formulas α, β and γ. These stages of reasoning can be characterised by the formula's deep-walk behaviour. In the fifth step we gather all obtained information and write it down into appropriate positions in the predecessor of the considered formula. Now, the  reverse process starts: beginning with the simple formulas up to a complex one. This leads to the step 7, where we spot a contradiction of obtained information: the same vertical column stores simultaneously 0 as well as 1 value.

Fig 6.5.1 An example of application of apagogic proving method.

Apagogic proofs are also presented in the following examples.

Example 6.5.2

If the function g : Y → X is the inverse of f: X → Y, then both f as well as g are one-to-one functions. We remember that the function g: Y → X is called an inverse to the function f : X → Y, iff Y = f(X) and X = g(Y) as well as g(f(x))=x for every x ∈ X.

We assume that f is not a different-value function. Let x₁ ≠ x₂ and f(x₁)=f(x₂). Because g is a function then for equal arguments it takes the same values, i.e. g(f(x₁)) =g(f(x₂)). Hence, according to the definition of a one-to-one function, we obtain x₁= g(f(x₁)) = g(f(x₂)) = x₂ which contradicts the previously established assumption that x₁ ≠ x₂.

If g is not a one-to-one function, then there are in the set Y two different elements y₁, y₂ such that g(y₁) = g(y₂). Then we obtain

(*)      f (g(y₁)) = f(g(y₂)).

Because g is the inverse to f thus Y = f(X), i.e. y₁, y₂ ∈ f(X). It follows that there exist such elements x₁, x₂ in X, then f(x₁) = y₁ as well as f(x₂) = y₂. Putting it to the equation (*) we obtain

f(g(f(x₁)) ) = f(g(f(x₂)) ). Using a property of the inverse function we have f(x₁) = f(x₂) , and therefore y₁=y₂. Contradiction. Thus, if only y₁ ≠ y₂ then g(y₁) ≠ g(y₂). That's why g is also a one-to-one function. ♦

Example 6.5.3

Now we want to prove that √ 2 is an irrational number. In order to do that we need to show that, if x² = 2, then x cannot be a rational number. Let us assume the opposite

1. x² = 2 and
2. x is a rational number.

According to (2) x = n/m for some arbitrary numbers n, m, where m ≠ 0. We may assume that n as well as m do not share common divisors other than 1 (in the opposite case it is enough to divide n and m by their greatest common divisor).

We obtain n²/m² = 2, that is n² = 2m². It follows from here that n² is an even number. As a consequence n must also be an even number (if n is odd, then for example n=2k+1 and n²= 4k²+ 4k+1 is also an odd number). Let n = 2k, then we obtain n² = 4k² = 2m². Hence 2k² = m², i.e. m is an even number. Contradiction with the assumption that n as well as m do not have common divisors. Thus, √ 2 is an irrational number.  ♦

The above-mentioned example of an apagogic proof  is based on the idea of reduction to a contradiction.

The proofs that use  of rules of transposition are also among apagogic proofs: instead of proving the implication ( α → β) we prove the proposition ( ¬ β → ¬ α).

Question 6.5.1 Prove that the formula ((( α → β) → α) → α) is a tautology of propositional calculus. In order to do that, use the method of reduction to a contradiction.

----- Check the answer -----

« previous section

next section  »