Introduction
Direct proof is the most straightforward proof technique: assume the premises are true and use logical reasoning to derive the conclusion. It’s the foundation of mathematical reasoning and formal logic.
Understanding direct proof is essential for:
- Mathematics: Proving theorems and lemmas
- Computer Science: Verifying algorithm correctness
- Philosophy: Constructing logical arguments
- Formal Verification: Proving software properties
- Critical Thinking: Building sound arguments
This comprehensive guide explores direct proof techniques, strategies, and applications.
What is Direct Proof?
Definition
A direct proof is a proof that:
- Assumes the premises are true
- Uses logical reasoning and known facts
- Derives the conclusion through a chain of valid inferences
Structure
Assume: Premises are true
Step 1: [Logical inference]
Step 2: [Logical inference]
...
Step n: [Logical inference]
Conclude: Therefore, the conclusion is true
Why Direct Proof Works
Direct proof works because:
- Validity: Each step follows logically from previous steps
- Soundness: If premises are true and reasoning is valid, conclusion must be true
- Transparency: The reasoning is explicit and verifiable
Basic Direct Proof Techniques
Technique 1: Modus Ponens Chain
Use modus ponens repeatedly to derive the conclusion.
Form:
Premise 1: p → q
Premise 2: q → r
Premise 3: p
─────────────────
Conclusion: r
Example: Prove that if x > 5, then x > 0
Premise 1: If x > 5, then x > 3
Premise 2: If x > 3, then x > 0
Premise 3: x > 5
─────────────────────────────
Step 1: x > 3 (from Premises 1 and 3, by Modus Ponens)
Step 2: x > 0 (from Premise 2 and Step 1, by Modus Ponens)
Conclusion: Therefore, x > 0
Technique 2: Universal Instantiation
Apply a universal statement to a specific case.
Form:
Premise 1: ∀x P(x)
Premise 2: a is in the domain
─────────────────────────────
Conclusion: P(a)
Example: Prove that Socrates is mortal
Premise 1: All humans are mortal (∀x (Human(x) → Mortal(x)))
Premise 2: Socrates is human (Human(Socrates))
─────────────────────────────────────────────
Step 1: Human(Socrates) → Mortal(Socrates) (from Premise 1, by Universal Instantiation)
Step 2: Mortal(Socrates) (from Premise 2 and Step 1, by Modus Ponens)
Conclusion: Therefore, Socrates is mortal
Technique 3: Conjunction Introduction
Combine multiple true statements.
Form:
Premise 1: p is true
Premise 2: q is true
─────────────────────
Conclusion: p ∧ q is true
Example: Prove that 2 is even and prime
Premise 1: 2 is even
Premise 2: 2 is prime
─────────────────────
Conclusion: 2 is even and prime
Technique 4: Disjunction Elimination
Use proof by cases.
Form:
Premise 1: p ∨ q
Premise 2: p → r
Premise 3: q → r
─────────────────
Conclusion: r
Example: Prove that |x| ≥ 0 for all real x
Premise 1: Either x ≥ 0 or x < 0
Premise 2: If x ≥ 0, then |x| = x ≥ 0
Premise 3: If x < 0, then |x| = -x > 0 ≥ 0
─────────────────────────────────────────────
Case 1: If x ≥ 0, then |x| ≥ 0
Case 2: If x < 0, then |x| ≥ 0
Conclusion: Therefore, |x| ≥ 0 for all real x
Mathematical Direct Proofs
Example 1: Prove an Algebraic Identity
Theorem: If n is an integer, then n² + n is even.
Proof:
Assume n is an integer.
Case 1: n is even
Then n = 2k for some integer k
n² + n = (2k)² + 2k = 4k² + 2k = 2(2k² + k)
Since 2k² + k is an integer, n² + n is even
Case 2: n is odd
Then n = 2k + 1 for some integer k
n² + n = (2k + 1)² + (2k + 1)
= 4k² + 4k + 1 + 2k + 1
= 4k² + 6k + 2
= 2(2k² + 3k + 1)
Since 2k² + 3k + 1 is an integer, n² + n is even
Therefore, n² + n is even for all integers n.
Example 2: Prove a Geometric Property
Theorem: The sum of angles in a triangle is 180°.
Proof:
Let ABC be a triangle.
Draw a line through A parallel to BC.
Let α = angle BAC, β = angle ABC, γ = angle ACB
By the parallel line property:
- The angle between AB and the parallel line equals β (alternate interior angles)
- The angle between AC and the parallel line equals γ (alternate interior angles)
The angles on one side of line BC sum to 180°:
α + β + γ = 180°
Therefore, the sum of angles in a triangle is 180°.
Example 3: Prove a Number Theory Result
Theorem: If a divides b and b divides c, then a divides c.
Proof:
Assume a divides b and b divides c.
By definition of divisibility:
- b = a·m for some integer m
- c = b·n for some integer n
Substituting:
c = b·n = (a·m)·n = a·(m·n)
Since m·n is an integer, a divides c.
Therefore, divisibility is transitive.
Logical Direct Proofs
Example 1: Prove a Logical Equivalence
Theorem: (p → q) ≡ (¬p ∨ q)
Proof:
We need to show that (p → q) and (¬p ∨ q) have the same truth value in all cases.
Case 1: p is true, q is true
p → q = T → T = T
¬p ∨ q = F ∨ T = T
Both are true ✓
Case 2: p is true, q is false
p → q = T → F = F
¬p ∨ q = F ∨ F = F
Both are false ✓
Case 3: p is false, q is true
p → q = F → T = T
¬p ∨ q = T ∨ T = T
Both are true ✓
Case 4: p is false, q is false
p → q = F → F = T
¬p ∨ q = T ∨ F = T
Both are true ✓
Therefore, (p → q) ≡ (¬p ∨ q).
Example 2: Prove a Logical Consequence
Theorem: From (p ∨ q) and ¬p, we can conclude q.
Proof:
Assume (p ∨ q) is true and ¬p is true.
Since (p ∨ q) is true, at least one of p or q is true.
Since ¬p is true, p is false.
Therefore, q must be true.
This is the disjunctive syllogism rule.
Example 3: Prove a Predicate Logic Statement
Theorem: ∀x (P(x) → Q(x)) and ∀x P(x) together imply ∀x Q(x).
Proof:
Assume ∀x (P(x) → Q(x)) and ∀x P(x).
Let a be an arbitrary element in the domain.
From ∀x (P(x) → Q(x)), we have P(a) → Q(a).
From ∀x P(x), we have P(a).
By Modus Ponens: Q(a).
Since a was arbitrary, ∀x Q(x).
Therefore, the conclusion follows.
Proof Strategies
Strategy 1: Work Backwards from the Conclusion
Start with what you want to prove and work backwards to the premises.
Example: Prove that if x² = 4, then x = 2 or x = -2
Goal: x = 2 or x = -2
What would make this true?
- If x² = 4, then (x - 2)(x + 2) = 0
- If (x - 2)(x + 2) = 0, then x - 2 = 0 or x + 2 = 0
- If x - 2 = 0 or x + 2 = 0, then x = 2 or x = -2
Working forward:
Assume x² = 4
Then x² - 4 = 0
Then (x - 2)(x + 2) = 0
Then x - 2 = 0 or x + 2 = 0
Then x = 2 or x = -2
Strategy 2: Use Definitions
Replace terms with their definitions to make the proof clearer.
Example: Prove that if n is even, then n² is even
Definition: n is even means n = 2k for some integer k
Assume n is even.
Then n = 2k for some integer k.
Then n² = (2k)² = 4k² = 2(2k²).
Since 2k² is an integer, n² is even.
Strategy 3: Use Known Results
Build on previously proven theorems and lemmas.
Example: Prove that if a divides b and a divides c, then a divides (b + c)
Lemma 1: If a divides b, then b = a·m for some integer m.
Lemma 2: If a divides b and a divides c, then a divides (b + c).
Proof:
Assume a divides b and a divides c.
By Lemma 1: b = a·m and c = a·n for integers m, n.
Then b + c = a·m + a·n = a(m + n).
Since m + n is an integer, a divides (b + c).
Strategy 4: Use Auxiliary Variables
Introduce new variables to simplify the proof.
Example: Prove that the product of two consecutive integers is even
Let n be an integer.
Let the two consecutive integers be n and n + 1.
Their product is n(n + 1).
Case 1: n is even
Then n = 2k, so n(n + 1) = 2k(n + 1) = 2(k(n + 1)), which is even.
Case 2: n is odd
Then n + 1 is even, so n + 1 = 2k, and n(n + 1) = n·2k = 2(nk), which is even.
Therefore, the product of two consecutive integers is always even.
Common Proof Patterns
Pattern 1: If-Then Proof
Goal: Prove p → q
Strategy: Assume p and derive q
Example: Prove that if x > 5, then x² > 25
Assume x > 5.
Then x > 5 > 0, so x is positive.
Multiplying both sides by x (positive): x² > 5x.
Since x > 5: 5x > 25.
Therefore: x² > 25.
Pattern 2: If-and-Only-If Proof
Goal: Prove p ↔ q
Strategy: Prove p → q and q → p
Example: Prove that n is even ↔ n² is even
(→) Assume n is even.
Then n = 2k, so n² = 4k² = 2(2k²), which is even.
(←) Assume n² is even.
Then n² = 2m for some integer m.
If n were odd, then n = 2k + 1, so n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd.
This contradicts n² being even.
Therefore, n must be even.
Therefore, n is even ↔ n² is even.
Pattern 3: Universal Statement Proof
Goal: Prove ∀x P(x)
Strategy: Let x be arbitrary and prove P(x)
Example: Prove that for all real numbers x, x² ≥ 0
Let x be an arbitrary real number.
Case 1: x ≥ 0
Then x² ≥ 0 (product of non-negative numbers)
Case 2: x < 0
Then x² = (-x)·(-x) where -x > 0
So x² > 0 ≥ 0
Therefore, for all real numbers x, x² ≥ 0.
Practice Problems
Problem 1: Prove an Algebraic Statement
Theorem: If a = b, then a + c = b + c.
Solution:
Assume a = b.
By the reflexive property of equality, c = c.
By the addition property of equality, if a = b, then a + c = b + c.
Therefore, a + c = b + c.
Problem 2: Prove a Logical Statement
Theorem: From p and (p → q), we can conclude q.
Solution:
Assume p is true and (p → q) is true.
By Modus Ponens, if p is true and (p → q) is true, then q is true.
Therefore, q is true.
Problem 3: Prove a Mathematical Statement
Theorem: The sum of two even numbers is even.
Solution:
Let m and n be even numbers.
Then m = 2a and n = 2b for some integers a and b.
m + n = 2a + 2b = 2(a + b).
Since a + b is an integer, m + n is even.
Therefore, the sum of two even numbers is even.
Problem 4: Prove a Geometric Statement
Theorem: If two angles are supplementary, their sum is 180°.
Solution:
Assume angles A and B are supplementary.
By definition, supplementary angles sum to 180°.
Therefore, A + B = 180°.
Related Resources and Tools
Online Learning Platforms
- Stanford Encyclopedia of Philosophy - Mathematical Proof - Academic treatment
- Khan Academy - Mathematical Proofs - Video tutorials
- Coursera - Introduction to Mathematical Thinking - University course
- MIT OpenCourseWare - Mathematics for Computer Science - Free materials
Interactive Tools
- Proof Checker - Fitch Proof Checker - Verify proofs
- Logic Simulator - LogicSim - Visual logic design
- Argument Mapper - Rationale - Map arguments visually
- Truth Table Generator - Stanford Tool - Create tables
Recommended Books
- “How to Prove It” by Daniel J. Velleman - Comprehensive proof guide
- “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook
- “A Concise Introduction to Logic” by Patrick J. Hurley - Accessible introduction
- “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook
Academic Journals
- Journal of Symbolic Logic - Leading journal on mathematical logic
- Studia Logica - International journal on logic and philosophy
- Logic and Logical Philosophy - Open access journal
Software Tools
- Prolog - Logic programming language
- Coq - Interactive theorem prover
- Isabelle - Generic proof assistant
- Z3 - SMT solver
Glossary of Key Terms
- Assumption: Statement assumed to be true at the start of a proof
- Conclusion: Statement to be proven
- Direct Proof: Proof that derives conclusion from premises
- Inference: Logical step from one statement to another
- Lemma: Auxiliary theorem used in a larger proof
- Modus Ponens: Rule allowing p and (p → q) to conclude q
- Premise: Statement used to support a conclusion
- Proof: Sequence of valid inferences from premises to conclusion
- Theorem: Statement proven to be true
- Validity: Property that conclusion follows from premises
Conclusion
Direct proof is the foundation of mathematical and logical reasoning. By mastering direct proof, you develop the ability to:
- Construct valid arguments
- Prove mathematical theorems
- Verify logical statements
- Build sound reasoning chains
- Communicate proofs clearly
The next article in this series will explore Proof by Contradiction, an alternative proof technique for cases where direct proof is difficult.
What type of direct proof do you find most interesting? Have you constructed direct proofs in mathematics or logic? Share your examples in the comments below!
Comments