This section covers methods to prove quantified statements involving universal ("\u2200") and existential ("\u2203") quantifiers.
Definition: A universal statement is of the form "\u2200x \in S, P(x)" and asserts that property P holds for all elements x in the set S.
Proving Universal Statements
Method 2.3.1: To prove "\u2200x \in S, P(x)" directly:
Let x be an arbitrary element in domain S.
Prove that P(x) is true using appropriate proof techniques based on the logical form of P(x).
Since x is arbitrary, conclude "\u2200x \in S, P(x)" is true.
Example 2.3.2: Prove that for every odd integer x, x² = 8k + 1 for some k in Z.
Let x be an arbitrary odd integer. Odd integers can be represented as:
Case 1: x = 4m + 1 → x² = 16m² + 8m + 1 = 8(2m² + m) + 1.
Case 2: x = 4m + 3 → x² = 16m² + 24m + 9 = 8(2m² + 3m + 1) + 1.
Exercise 2.3.3: Prove that for all rational numbers x and y, x + y² is a rational number.
Exercise 2.3.4: Prove that if a | b and a | c, then a | (bx + cy) for all integers x and y.
Set Definitions
If A is a subset of B (A ⊆ B), then every element of A is also an element of B.
A and B are equal (A = B) if A ⊆ B and B ⊆ A.
Method 2.3.4: To prove set relations:
A ⊆ B ↔ "\u2200 x, x ∈ A → x ∈ B."
A = B ↔ "\u2200 x, x ∈ A → x ∈ B ∧ x ∈ B → x ∈ A."
Example 2.3.5: Proof examples of set relationships:
Prove if A ⊆ B and B ⊆ C, then A ⊆ C.
Prove A ⊆ B if and only if A ∪ B = B.
Example 2.3.7: Prove a | b if and only if bZ ⊆ aZ.
(1) If a | b, show bZ is a subset of aZ.
(2) If bZ ⊆ aZ, show a | b.
Method 2.3.9: To prove a universal statement by contradiction:
Assume that the statement is false.
Find an element t in S such that ¬P(t).
Show this leads to a contradiction.
Example 2.3.10: Prove for all x in (0, π/2), sin x + cos x > 1 using contradiction.
It is possible to express universal statements without using "for all" explicitly.
Example 2.3.11: Prove the sum of a rational number and an irrational number is irrational.
Existence Statements: Of the form "There exists x such that P(x)" is true if the truth set of P(x) is non-empty.
Method 2.3.13: To prove “\u2203 x \in S such that P(x)":
Display an element a in S that makes P(a) true (constructive proof) or prove it by contradiction.
Example 2.3.14: Prove:
Exist integers m and n such that 2m + 7n = 1.
There exists a positive integer n such that n² > 2n.
Unique Existential Quantifier Method 2.3.19: To prove “\u2203! x \in S such that P(x)":
Proves existence of x such that P(x).
Show P(y) ∧ P(z) → (y = z).
Example 2.3.20: Prove every nonzero real number has a unique multiplicative inverse.
Exercise 2.3.21: Prove the equation x⁵ + 2x - 5 = 0 has a unique real solution between x = 1 and x = 2.