| ← | Table of contents | → |
In propositional logic, ¬P → P ≡ P. What that means is that, in order to prove claim P, you can always add ¬P to the fact bank. But be careful to negate the entire claim, not just part of the claim. Quantifiers are part of the claim. For example, if the claim is ∀xP(x), then the negation of the claim is ¬(∀xP(x)), which is equivalent to ∃x¬(P(x)). Even if quantifiers are implicit in the claim, be sure to pay attention to them.
In propositional logic, ¬P → false ≡ P too. That means that, after adding ¬P to the fact bank, you only need to prove something that is obviously false — a contradiction — to conclude that P is true.
Definition. A number x is rational if there exist integers a and b, where b ≠ 0, so that x = a/b. For example, 1/3, 2/10 and 10/3 are all rational numbers.
Lemma 1. If x is rational then there exist integers r and s (s ≠ 0) so that x = r/s, where at least one of r and s is not even.
Proof. Let x be an arbitrary rational number. According to the definition of a rational number, there exist a and b so that x = a/b. If both a and b are even, then divide them both by 2. For example, if a = 4 and b = 14, so x = 4/14, then x = 2/7. Keep dividing by 2 until one of them is not even.
Theorem. √2 not rational.
Proof. We can safely add the negation of what we want to prove to the fact bank. Here it is.
(1) √2 is rational.
Now we can apply Lemma 1. Since √2 is rational (by (1) from the fact bank),
(2) there exists integers r and s, where s ≠ 0 and r and s are not both even, such that √2 = r/s.Since we know that such integers r and s exist, we can choose two such values, which we continue to call r and s. So, for this particular pair of numbers r and s,
(3) √2 = r/s.
(4) s ≠ 0.
(5) r and s are not both even.
Squaring both sides of equation (3) yields
Since 2s2 is clearly even, r2 must also be even (the two are the same value, by (7)). So r cannot be odd since the square of an odd number is odd.
(6) 2 = r2/s2 (7) 2s2 = r2 (from (6), by algebra)
(8) r is even.But the square of an even number is divisible by 4. So, from (9),
(9) s is odd (since, by (5), r and s are not both even).
(10) r2 is divisible by 4.By equation (7),
(11) 2s2 is divisible by 4.
Since s is odd (fact (9)),
(12) s2 is odd.If n is an odd number then 2n is divisible by 2, but not by 4. (Dividing 2n by 2 gives odd number n. You cannot divide by 2 again.) So
(13) 2s2 is not divisible by 4.But facts (11) and (13) contradict one another. They cannot both be true. Since P ∧ ¬P ≡ false, we have proved a contradiction. That is all there is. The contradiction is enough to conclude that the theorem must be true.
♦
Definition. The arithmetic mean of two numbers x and y is (x+y)/2.
Definition. The geometric mean of two nonnegetive numbers x and y is √xy.
Theorem. If x and y are two different positive real numbers, then the arithemetic mean of x and y is larger than the geometric mean of x and y.
Proof. Let's start by using definitions to restate the theorem. Notice that we must be clear that we are restating what we want to prove; we are not adding anything to the fact bank yet. Also, let's make it explicit that the theorem is to be proved for every x and y that satisfy the requirements of being different and positive.
Equivalent claim. For every x and y, if x > 0, y > 0 and x ≠ y then (x+y)/2 > √xy.
By contradiction, we can add the negation of the claim to the fact bank.
(1) There exist x and y, where x > 0, y > 0 and x ≠ y, so that (x+y)/2 ≤ √xy.To use an existential fact, we grab two values (continue to call them x and y) where
(2) x > 0Starting at fact (5), let's apply some algebra to get new facts. First, since x and y are both positive, both sides of inequality (5) are positive. So squaring both sides preserves the inequality, giving
(3) y > 0
(4) x ≠ y
(5) (x+y)/2 ≤ √xy
But, since x ≠ y (fact (4)), and the square of any nonzero number is positive,
(6) (x+y)2/4 ≤ xy. (7) (x+y)2 ≤ 4xy (by algebra, from (6)). (8) x2 + 2xy + y2 ≤ 4xy (by algebra, from (7)). (9) x2 − 2xy + y2 ≤ 0 (by algebra, from (8)). (10) (x−y)2 ≤ 0 (by algebra, from (9)).
(11) x − y ≠ 0.Facts (10) and (12) are contradictory. So the theorem must be true.
(12) (x − y)2 > 0.
♦