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