Mathematical Quantifiers :
In our daily conversations we use some words such as some, all, every, each, at least, there
exists, etc. These are named as quantifiers because each indicates quantity.
Examples;
All insects have four legs.
Some turtles live in the water.
Every triangle has three sides.
Ex: Find the truth value of each proposition.
a. Some apples are green.
b. Every number is prime.
c. All months have 30 days.
d. Some prime numbers are odd.
Open sentence: Statements containing one or more variable that become propositions
when the value of the variable is substituted are called open sentence.
Let P be an open proposition which contains one variable. If P becomes true when the term
x is substituted for the variable, then P can be denoted by P(x) or P x
𝑃𝑥: 𝑥 + 6 > 5, 𝑥 is a real number
𝑃𝑥: is ……(T/F) when x is replaced by 1
𝑃𝑥: is ……(T/F) when x is replaced by -10
Ex: Complete the following table.
Using words Using Symbol
Square of some real numbers is positive.
∀𝑥 ∈ 𝑍, 𝑥 + 1 ≥ 2
4 more than twice of a number is less than six for all natural numbers.
∃𝑥 ∈ 𝑁, 3𝑥 − 1 ≤ 0
All integers are positive.
∀𝑥 ∈ 𝑅, √𝑥 ∈ 𝑅
For some rational numbers, its square root is also a rational number.
Ex: Discuss whether the following propositions are true or false. Also write them again by using
words.
a. ∃𝑥 ∈ 𝑍, 𝑥 2 < 18
b. ∀𝑥 ∈ 𝑅, (𝑥 − 1)2 > 0
c. ∃𝑥 ∈ 𝑅, 𝑥 2 < 𝑥
𝑥
d. ∀𝑥 ∈ 𝑅, = 1
𝑥
Negation of Quantifiers
Ex: Find the truth value and negate each of the following sentences
1. ∀𝑥 ∈ 𝑅 ; 𝑥 2 ≥ 0
2. ∀𝑥 ∈ 𝑍, 2𝑥 + 4 = 6
3. (∃𝑥 ∈ 𝑅 ; 𝑥 > 3) ∧ (∀𝑥 ∈ 𝑅 ; 𝑥 2 + 1 ≤ 6)
4. ∀𝑥 ∈ 𝑁, ∃𝑦 ∈ 𝑍, 𝑦 2 + 2𝑥 ≥ 0
5. [(∃𝑥 ∈ 𝑅, 2𝑥 + 3 = 0) ∨ (∀𝑥 ∈ 𝑅, 𝑥 2 ≥ 𝑥 )] ⇒ (∀𝑥 ∈ 𝑅, 𝑥 2 − 𝑥 = 0)
Axiom, Theorem, Proof
Axiom is a proposition that is accepted as true without proof. An axiom is also called a postulate.
Some examples : 0 is a Natural Number. Two parallel lines never intersect each other. A straight
line may be drawn between any two points.
Theorem is a statement whose truth can be proved on the basis of a given set of axioms or
assumptions.
In general, theorems are in the form of 𝑝 ⇒ 𝑞.
The first part of the theorem is known as hypothesis and the second part known as conclusion.
Types of Proof
Direct Proof: We use it to prove statements in the form of 𝑝 ⇒ 𝑞
Direct proof has the following steps:
Assume the statement 𝑝 is true. Use what we know about 𝑝 and other facts as necessary to deduce
that another statement 𝑞 is true, that shows 𝑝 ⇒ 𝑞.
Ex: Prove that ”the sum of two odd integers is an even number”
Ex: Prove that if k is an odd integer then 𝑘 3 + 𝑘 2 − 𝑘 − 1 is divisible by 8.
Ex: Prove that (𝑎 + 𝑏)2 −(𝑎 − 𝑏)2 = 4𝑎𝑏.
Mathematical Induction: Given a propositional function P(n) defined for integers n, and a fixed
integer a.
If these two conditions are true
1. 𝑃(𝑎) is true.
2. If 𝑃(𝑘) is true for some integer 𝑘 ≥ 𝑎, then 𝑃(𝑘 + 1) is also true.
then the 𝑃(𝑛) is true for all integers 𝑛 ≥ 𝑎.
Ex: Use mathematical induction to prove the following theorem for all integers 𝒏 ≥ 𝟏 (Gauss Sum)
𝑛(𝑛 + 1)
1 + 2 + 3 + ⋯+ 𝑛 =
2
Ex: Use mathematical induction to prove the following theorem.
𝟏 𝟏 𝟏 𝟏 𝒏
+ + +⋯+ =
𝟏×𝟐 𝟐×𝟑 𝟑×𝟒 𝒏 × (𝒏 + 𝟏) 𝒏 + 𝟏
Proof by Contrapositive: In logic we learned that 𝑝 ⇒ 𝑞 ≡ 𝑞′ ⇒ 𝑝′ . Therefore instead of proving
𝑝 ⇒ 𝑞 if we find that 𝑞′ ⇒ 𝑝′ is true, since there is an equivalence between them, we can conclude
that 𝑝 ⇒ 𝑞 is true.
Ex: Prove that if 𝑥 2 is even then 𝑥 is even for all integers.
Proof by contradiction (also known as indirect proof or the method of reductio ad absurdum) is a
common proof technique that is based on a very simple principle: something that leads to a
contradiction can not be true, and if so, the opposite must be true.
Ex: Prove that there is no largest number.
Counter Example: 2 is a counter example for the hypothesis: “All prime numbers are odd numbers".
