Introduction to Proofs
LPU Phagwara
August 16, 2022
Proof & Theorem
Definition
A proof is a valid arguement that establish the truth of a
mathematical statement.
Definition
A theorem is a statement that can be shown to be true. Less
important theorems are some times called propositions.
Introduction to Proofs
Types of Proof
Types of Proofs
Direct Proof Trival Proof
Proof by contraposition
Vaccous Proof
Proof by Contradiction
Introduction to Proofs
Direct Proof
Direct Proof of ∀x (P(x ) → Q(x ))
P(x) is assumed to be true
Use of Axioms, definitions, previously proved theorems
Conclusion Q(x ) is shown true
Introduction to Proofs
Example of Direct Proof
Theorem
If n is an odd integer then n2 is odd.
Proof.
Note that theorem is of type ∀n (P(n) → Q(n)), where
P(n) = n is an odd integer
Q(n) = n2 is an odd integer
Suppose P(n) is true. i.e. n is odd integer. Therefore
n = 2k + 1
Let us computer n2
n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
Introduction to Proofs
Example of Direct Proof
cont....
n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
= 2k ′ + 1 here k ′ = 2k 2 + 2k
This implies n2 is odd.
Introduction to Proofs
Proof by Contraposition Method
For proving p → q we will use the equivalence p → q ≡ ¬q → ¬p.
Proof by contraposition ∀x (P(x ) → Q(x ))
not Q(x) is assumed to be true
Use of Axioms, definitions, previously proved theorems
Conclusion not P(x ) is shown true
Introduction to Proofs
Example of Proof by Contraposition
Theorem
Prove that if n is an integer and n2 is an odd, then n is odd.
Proof.
Let us start giving a direct proof of this theorem
P(n) = n2 is an odd integer
Q(n) = n is an odd integer
Suppose P(n) is true. i.e. n2 is odd integer. Therefore
n2 = 2k + 1
q
Therefore n = (2k + 1)
This does not proves the conclusion and we are at dead end. So let
us try a proof by contraposition.
Introduction to Proofs
Example of proof by contraposition
Proof: Let us try to proof using contraposition method.
P(n) = n2 is an odd integer
Q(n) = n is an odd integer
Suppose Q(n) is not true. i.e. n is not an odd integer.
Therefore n is an even integer. Hence
n = 2k for some integer k.
Therefore n2 = (2k)2 = 4k 2 = 2(2k 2 ) = 2k ′
Here k ′ = 2k 2 is an integer. This gives n2 is even. So n2 is
not odd. i.e P(n) is not true.
∴ ∀n (¬Q(x ) → ¬P(x )) ≡ ∀n (P(x ) → Q(x ))
Introduction to Proofs
Vacous Proof
Definition
We can quickly prove that a conditional statement p → q is true
when we know that p is false, because p → q must be true when p
is false. Consequently, if we can show that p is false, then we have
a proof, called a vacous proof , of p → q.
Introduction to Proofs
Vacous Proof
Definition
We can quickly prove that a conditional statement p → q is true
when we know that p is false, because p → q must be true when p
is false. Consequently, if we can show that p is false, then we have
a proof, called a vacous proof , of p → q.
Example
Show that the proposition P(0) is true, where P(n) is “If n > 1,
then n2 > n” and domain consist of all integers.
Introduction to Proofs
Trivial Proof
Definition
We can quickly proof a conditional statement p → q if we prove
that q is true. The proof which uses the fact that q is true is
called trivial proof.
Introduction to Proofs
Trivial Proof
Definition
We can quickly proof a conditional statement p → q if we prove
that q is true. The proof which uses the fact that q is true is
called trivial proof.
Example
Let P(n) be “If a and b are positive integers with a ≥ b, then
an ≥ b n , where the domain consist of all positive integers. Show
that P(0) is true.
Introduction to Proofs
Proof by contradiction
Suppose we want to prove a statement p is true. Furthermore
suppose we have find a contradiction q such that ¬p → q is true.
Because q is false, but ¬p → q is true, we can conclude that ¬p is
false or in other words p is true.
Introduction to Proofs
Example of Proof by Contradiction
Theorem
√
Prove that if 2 is irrational.
Proof.
√
Let p be the proposition “ 2 is irrational.”
Suppose ¬p is true.
√ √
That is 2 is not an irrational number. So 2 is rational number.
√ a
∴ 2=
b
Where a, b are integers and we can take a and b having no
common factor. Squaring we have
a2
2=
b2
Introduction to Proofs
Example of a Proof by Contradiction
Cont..
a2 = 2b 2 ...(1)
This gives a2 is even. Therefore a is even and hence a = 2k. Put
this in (1) we get
4k 2 = 2b 2
2k 2 = b 2
This implies b 2 is also even number. This means both a and b are
even and has common factor 2. This is a contradiction.
Introduction to Proofs
Thank You for attention!
Introduction to Proofs
