Chapter 1 : Logic and Proofs
2. Proofs
In this section we introduce the notion of a proof and describe methods for constructing
proofs. A proof is a valid argument that establishes the truth of a mathematical statement.
A proof can use the hypotheses of the theorem, if any, axioms assumed to be true, and
previously proven.
2.1. Direct proofs
A direct proof of a conditional statement 𝑃 ⟹ 𝑄 is constructed when the first step is the
assumption that 𝑃 is true; subsequent steps are constructed using rules of inference, with
the final step showing that 𝑄 must also be true. A direct proof shows that a conditional
statement 𝑃 ⟹ 𝑄 is true by showing that if 𝑃 is true, then 𝑄 must also be true, so that the
combination 𝑃 true and 𝑄 false never occurs.
Example
Let 𝑥 ∈ ℝ, prove that :
|𝑥| < 1 ⟹ 0 < 𝑥 2 + 5 < 6
Solution
We have |𝑥| < 1 ⟹ −1 < 𝑥 < 1
then 0 ≤ 𝑥 2 < 1
Finally 5 ≤ 𝑥 2 + 5 < 6
We deduce that |𝑥| < 1 ⟹ 0 < 𝑥 2 + 5 < 6 is true.
2.2. Proof with counter-example
we stated that to show that a statement of the form ′′∀𝑥 ∈ 𝐸, 𝑃(𝑥)′′ is false, we need only
find a counterexample, that is, an example 𝑥 for which 𝑃(𝑥) is false. When presented with
a statement of the form ′′∀𝑥 ∈ 𝐸, 𝑃(𝑥)′′ , which we believe to be false or which has resisted
all proof attempts, we look for a counterexample.
Example
Let 𝑃:′′ ∀𝑛 ∈ ℕ, 2𝑛 = 2𝑛 ′′
The proposition 𝑃 is it true ?
9
Chapter 1 : Logic and Proofs
Solution
The 𝑃:′′ ∀𝑛 ∈ ℕ, 2𝑛 = 2𝑛 ′′ is false. Just take 𝑛 = 0, we obtain the proposition ′′2 × 0 = 20 ′′
that it is false.
2.3. Proofs with contradiction
Suppose we want to prove that a statement 𝑃 is true. Furthermore, suppose that we can
find a contradiction 𝑄 such that 𝑃̅ ⟹ 𝑄 is true. Because 𝑄 is false, but 𝑃̅ ⟹ 𝑄 is true, we
can conclude that 𝑃̅ is false, which means that P is true.
Example
Let 𝑎, 𝑏 ∈ ℝ+ , prove that :
𝑎 𝑏
= ⟹𝑎=𝑏
1+𝑏 1+𝑎
Solution
We suppose that 𝑃 is false, then 𝑃̅ is true.
We have :
𝑎 𝑏
𝑃̅: ′′ = 𝑒𝑡 𝑎 ≠ 𝑏′′
1+𝑏 1+𝑎
𝑎 𝑏
= ⟹ 𝑎 (1 + 𝑎) = 𝑏 (1 + 𝑏) ⟹ 𝑎 + 𝑎2 = 𝑏 + 𝑏 2
1+𝑏 1+𝑎
⟹ 𝑎2 − 𝑏 2 = 𝑏 − 𝑎 ⟹ (𝑎 − 𝑏)(𝑎 + 𝑏) = −(𝑎 − 𝑏)
but 𝑎 ≠ 𝑏 then 𝑎 − 𝑏 ≠ 0.
So
−(𝑎 − 𝑏)
𝑎+𝑏 = = −1
𝑎−𝑏
‘’Contradiction because 𝑎 ≥ 0 𝑎𝑛𝑑 𝑏 ≥ 0 (The sum of two positive numbers is positive)’’
then 𝑃̅ is false.
2.4. Proof by contraposition
An extremely useful type of indirect proof is known as proof by contraposition. Proofs by
contraposition make use of the fact that the conditional statement 𝑃 ⟹ 𝑄 is equivalent to
its contrapositive, 𝑄̅ ⟹ 𝑃̅. This means that the conditional statement 𝑃 ⟹ 𝑄 can be proved
by showing that its contrapositive 𝑄̅ ⟹ 𝑃̅ is true.
10
Chapter 1 : Logic and Proofs
Example
Let 𝑛 ∈ ℕ, prove that :
𝑛2 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟 ⟹ 𝑛 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟
Solution :
Let 𝑃 and 𝑄 be two propositions. We have ′′𝑃 ⟹ 𝑄′′ ⟺ ′′𝑄̅ ⟹ 𝑃̅ ′′.
Then :′′ 𝑛2 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟 ⟹ 𝑛 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟′′ ⟺′′ 𝑛 𝑖𝑠 𝑜𝑑𝑑 ⟹ 𝑛2 𝑖𝑠 𝑜𝑑𝑑′′.
𝑛 𝑖𝑠 𝑜𝑑𝑑 ⟹ ∃𝑘 ∈ ℕ ∕ 𝑛 = 2𝑘 + 1.
then 𝑛2 = (2𝑘 + 1)2 = 4𝑘 2 + 4𝑘 + 1
= 2(2𝑘 2 + 2𝑘 ) + 1
just take 𝑘 ′ = 2𝑘 2 + 2𝑘 ∈ ℕ, and we obtain 𝑛2 = 2𝑘 ′ + 1.
then 𝑛2 is odd.
The proposition ′′𝑛 𝑖𝑠 𝑜𝑑𝑑 ⟹ 𝑛2 𝑖𝑠 𝑜𝑑𝑑′′ is true, then the proposition
′′𝑛2 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟 ⟹ 𝑛 𝑎𝑛 𝑒𝑣𝑒𝑛 𝑛𝑢𝑚𝑏𝑒𝑟′′ is true.
11