10.3 Proof by Contraposition
3 min read•august 12, 2024
Proof by contraposition is a powerful technique in mathematical reasoning. It allows us to prove an implication by proving its logically equivalent statement. This method is especially useful when the original statement is difficult to prove directly.
In this section, we'll learn how to construct and apply contrapositive proofs. We'll explore examples that demonstrate the effectiveness of this technique in both mathematical and real-world contexts. Understanding contraposition enhances our ability to tackle complex logical statements and proofs.
Logical Statements and Their Negations
Types of Logical Statements
Top images from around the web for Types of Logical Statements
.svg.png&w=640&q=75)
Logical reasoning - Wikipedia View original
Is this image relevant?
Logical reasoning - Wikipedia View original
Is this image relevant?
1 of 1
Top images from around the web for Types of Logical Statements
Logical reasoning - Wikipedia View original
Is this image relevant?
Logical reasoning - Wikipedia View original
Is this image relevant?
1 of 1
- Implication consists of two parts: hypothesis (p) and conclusion (q), expressed as "" or p → q
- Converse reverses the order of the original implication, written as "if q, then p" or q → p
- Inverse negates both the hypothesis and conclusion of the original implication, expressed as "if not p, then not q" or ~p → ~q
- contradicts the original statement, written as "not (if p, then q)" or ~(p → q)
Negation Process and Equivalence
- Negating an implication transforms it into a conjunction: ~(p → q) ≡ p ∧ ~q
- Negating a universal statement changes it to an existential statement: ~(x P(x)) ≡ x ~P(x)
- Negating an existential statement changes it to a universal statement: ~(∃x P(x)) ≡ ∀x ~P(x)
- Double negation cancels out: ~~p ≡ p
Applications and Examples
- Implication: "If it rains, then the ground is wet" (Rain → Wet Ground)
- Converse: "If the ground is wet, then it rained" (Wet Ground → Rain)
- Inverse: "If it doesn't rain, then the ground is not wet" (~Rain → ~Wet Ground)
- Negation: "It rains and the ground is not wet" (Rain ∧ ~Wet Ground)
- Universal statement negation: "Not all birds can fly" negates to "There exists a bird that cannot fly"
- Existential statement negation: "There is no largest prime number" negates to "All numbers are not the largest prime"
Proof by Contraposition
Understanding Contraposition
- Contrapositive reverses and negates both parts of an implication: (p → q) ≡ (~q → ~p)
- Logical equivalence between an implication and its contrapositive forms the basis for proof by contraposition
- Contrapositive maintains the truth value of the original implication, unlike converse or inverse
Constructing Proofs by Contraposition
- Start with the implication to be proved: p → q
- Form the contrapositive: ~q → ~p
- Prove the contrapositive using methods
- Conclude that the original implication is true based on the logical equivalence
Applications and Examples
- Original statement: "If a number is even, then it is divisible by 2"
- Contrapositive: "If a number is not divisible by 2, then it is not even"
- Mathematical example: Prove that if n² is odd, then n is odd
- Contrapositive: If n is not odd (even), then n² is not odd (even)
- Proof: Let n be even, so n = 2k for some integer k
- Then n² = (2k)² = 4k² = 2(2k²), which is even
- Therefore, the contrapositive is true, so the original statement is true
- Real-world example: "If a student graduates, then they have completed all required courses"
- Contrapositive: "If a student has not completed all required courses, then they will not graduate"
Key Terms to Review (14)
∀: The symbol '∀' represents the universal quantifier in mathematical logic, which asserts that a certain property or statement holds true for all elements within a specified set. This symbol is essential for expressing general statements about entire collections of objects and is commonly used in conjunction with predicates to form logical expressions.
∃: The symbol ∃ represents the existential quantifier in mathematical logic, indicating that there exists at least one element in a given set that satisfies a particular property or condition. This concept is crucial for constructing statements and proofs in mathematics, as it allows for the expression of the existence of solutions or counterexamples within various contexts.
Assuming the converse: Assuming the converse involves considering the opposite direction of a conditional statement. In logical reasoning, if we have a statement of the form 'If A, then B' (A → B), the converse is 'If B, then A' (B → A). This method is often used in proofs to explore implications and relationships between statements.
Contrapositive: The contrapositive of a conditional statement reverses and negates both the hypothesis and the conclusion. It takes a statement of the form 'If P, then Q' and turns it into 'If not Q, then not P.' This logical transformation is crucial for understanding implications and constructing proofs, especially when demonstrating the truth of statements through alternative methods.
Direct Proof: A direct proof is a method of demonstrating the truth of a mathematical statement by using logical reasoning and established facts, leading directly from assumptions to the conclusion. This technique is foundational in mathematics, as it allows for clear and straightforward verification of statements using definitions, axioms, and previously proven theorems.
If not q, then not p: The phrase 'if not q, then not p' represents the contrapositive of a conditional statement 'if p, then q'. It means that if the conclusion q is false, then the premise p must also be false. This logical equivalence is fundamental in proofs and reasoning, as proving the contrapositive can be a powerful way to establish the truth of the original statement.
If p, then q: The phrase 'if p, then q' is a fundamental concept in logic and mathematics that represents a conditional statement. It indicates that if the proposition p (the antecedent) is true, then the proposition q (the consequent) must also be true. This relationship is crucial for understanding implications and reasoning in proofs, especially when discussing validity and logical deductions.
If-Then Statements: If-then statements are conditional statements that express a relationship between two propositions, where one proposition (the hypothesis) leads to another (the conclusion). These statements can be expressed in the form 'If P, then Q', indicating that if the condition P is true, then the result Q must also be true. They are crucial in mathematical reasoning and proofs, particularly in establishing logical connections and implications between various concepts.
Indirect proof: An indirect proof is a method of demonstrating the truth of a statement by assuming the opposite of what you want to prove and showing that this assumption leads to a contradiction. This technique is powerful because if the assumption of falsehood results in an illogical outcome, it confirms the original statement's validity. It connects closely with the concepts of proof by contraposition and proof by contradiction, both of which rely on this logical structure to establish the truth of propositions.
Law of Excluded Middle: The law of excluded middle is a fundamental principle in classical logic stating that for any proposition, either that proposition is true or its negation is true. This binary perspective is crucial in reasoning, particularly in constructing arguments and proofs, as it allows one to assert the truth value of statements unequivocally. In mathematical proofs, this law supports strategies that establish the validity of a statement by confirming that it cannot simultaneously be false.
Logical implication: Logical implication is a fundamental concept in propositional logic that describes a relationship between two statements, where the truth of one statement guarantees the truth of another. In other words, if statement A implies statement B, then whenever A is true, B must also be true. This idea is crucial for understanding how arguments are constructed and validated, particularly when using techniques like proof by contraposition.
Modus Ponens: Modus Ponens is a fundamental rule of inference in propositional logic that states if a conditional statement is true and its antecedent is true, then the consequent must also be true. This principle is essential for drawing valid conclusions from established premises, making it a key component in constructing logical arguments and proofs.
Negation: Negation is the logical operation that takes a statement and transforms it into its opposite, asserting that the statement is not true. This fundamental concept is crucial for understanding logical connectives and helps form the basis for more complex reasoning techniques. By negating a statement, we can explore implications, contradictions, and construct valid arguments in mathematical proofs and logical reasoning.
Neglecting edge cases: Neglecting edge cases refers to the oversight of unusual or extreme scenarios that could potentially invalidate a proof or solution in mathematics. This is critical because failing to consider these cases can lead to incomplete arguments and false conclusions, especially when establishing the validity of a statement through various proof techniques.