What is a contrapositive? A quiz on modus ponens, counterexamples and proof

Chapter: Direct Deduction A logical proof is essentially a navigation through facts to reach a destination that was not initially obvious. In a direct deduction, we move in a single, straight line from things we already know to a new conclusion. A direct proof is the most basic form of this journey, where we never use contradictions or 'what if' scenarios. The most common rule used in direct deduction is called Modus Ponens, which means 'the way that affirms'. In the statement 'If P, then Q', the part P is called the antecedent, which is the condition that comes before. The part Q is called the consequent, which is the logical result that follows if the condition is met. Notice that the logic only flows from the antecedent to the consequent, not the other way around. No. Having four sides is the consequent. You cannot prove the antecedent (it is a square) just because the consequent is true. Most arguments are more than one step long; they form a chain of reasoning. In a chain, the consequent of the first step becomes the antecedent for the next step. This property is known as transitivity: if A leads to B and B leads to C, then A leads to C. Consider a computer: If you press 'Save', the software sends data. If the software sends data, the hard drive spins. By direct deduction, we can conclude that pressing 'Save' causes the hard drive to spin. The entire proof collapses. A direct deduction requires every single link to be perfectly valid to guarantee the truth of the conclusion. Direct deduction is the art of stacking these Modus Ponens steps to build an unshakeable wall of logic. Yes. If your starting premises are false, even perfect logic will lead to a false conclusion. Logic only guarantees that *if* the start is true, the end is true. While it seems simple, formalizing it allows us to check extremely complex arguments where the 'obvious' truth might be hidden. It also prevents us from making mistakes like reversing the logic. An argument is valid if the conclusion follows from the premises. A direct proof is a specific way of presenting that argument as a forward-moving sequence of steps. Theoretically, no. Some mathematical proofs involve thousands of steps. However, longer chains are harder to verify and have more 'links' where a mistake could hide. In formal direct deduction, rules must be 100% true. If a rule has exceptions, it is not a valid tool for a strict logical proof, as it cannot guarantee the truth of the conclusion. Chapter: Indirect Paths Sometimes, proving that a statement is true by building it from scratch feels like climbing a vertical wall without any equipment. In your previous look at Direct Deduction, you learned to move from point A to point B using a clear, forward-moving chain of logic. But what happens when you want to prove that something does not exist, or that a certain path is impossible to take? To solve this, we rely on a fundamental rule of logic called the Law of Excluded Middle. Because of this law, if we can 100% prove that a statement cannot be false, it must, by default, be true. The light must be on. Since there is no third state between 'on' and 'off' in this logic, ruling out 'off' leaves only 'on' as the truth. This strategy is known as Proof by Contradiction, or more traditionally, Reductio ad absurdum. Instead of proving a statement directly, you assume the opposite is true and follow that logic until it breaks. Let's look at a concrete example: proving there is no smallest positive fraction. If we try to prove this directly, we'd have to check every possible fraction, which is impossible because there are infinitely many. Instead, we use the indirect path. We start by assuming the opposite: 'There IS a smallest positive fraction.' Let's call this supposed smallest fraction x. Now, we apply a simple rule: if we divide any positive number by 2, we get a smaller positive number. Our assumption that a 'smallest fraction' exists led us to nonsense. Because that assumption is now proven to be impossible, the opposite must be true: there is no smallest positive fraction. Structuring these proofs requires careful setup of your initial assumption. If you want to prove 'All cats are mammals,' your indirect proof must begin with: 'Assume there exists at least one cat that is not a mammal.' You then search for a fact about mammals that this 'non-mammal cat' would violate, creating the necessary glitch in the logic. The Law of Excluded Middle ensures that this 'survival of the fittest' approach to truth actually works. By mastering the Reductio ad absurdum, you gain a powerful tool for tackling complex problems where a direct approach is blocked. In the next chapters, we will see how this 'backward' thinking helps us prove even more elusive mathematical truths. Not at all! You aren't claiming the lie is true; you are exploring the *consequences* of that lie to show they are impossible. It is a perfectly valid logical tool used by mathematicians for thousands of years. Not necessarily. It might just mean you haven't found the right chain of logic yet. Failing to find a contradiction doesn't prove the assumption is true; it just means the proof is incomplete. Technically yes, but it's often 'overkill'. If a direct proof is available, it's usually clearer and more informative. Contradiction is best saved for when the direct path is blocked or overly complicated. No. A counter-example disproves a general claim by showing one case where it fails. Reductio ad absurdum *proves* a claim by showing its opposite is impossible. They are related but serve opposite goals. In formal logic and math, yes. In everyday conversation, things can be 'gray' or 'somewhat true.' But for the architecture of proof, we assume a strict binary to ensure our conclusions are absolute. Chapter: Proving the Negative Proving a statement directly is often like walking straight through a thick forest; the path is blocked by messy calculations or complex variables. Consider the goal of proving that if the square of an integer, $n^2$, is even, then the integer $n$ itself must also be even. Dealing with square roots in a proof about integers is frustrating because roots often result in irrational numbers. Yes. We can prove that 'If $n$ is NOT even (odd), then $n^2$ is NOT even (odd)'. This is the contrapositive. In our example, the antecedent ($P$) is '$n^2$ is even' and the consequent ($Q$) is '$n$ is even'. The negation of a statement simply asserts the opposite of the original claim. But why are we allowed to swap them? In logic, two statements are logically equivalent if they always share the same truth value. Because they are equivalent, proving the contrapositive is mathematically identical to proving the original statement. This is the essence of proof by contraposition: if the direct path is blocked, we take the equivalent 'backwards' path. Let's return to our original challenge: proving that if $n^2$ is even, then $n$ is even. Our new goal is to prove: If $n$ is odd, then $n^2$ is odd. We have successfully shown that if $n$ is odd, then $n^2$ is odd. Because this contrapositive is true, the original statement—if $n^2$ is even, then $n$ is even—is also proven. This technique is not limited to parity; it works for any logical statement involving sets or categories. The contrapositive of 'If $x \\in \\mathbb{N}$, then $x \\in \\mathbb{Z}$' is 'If $x \\notin \\mathbb{Z}$, then $x \\notin \\mathbb{N}$'. No. Since all natural numbers are integers, failing to be an integer automatically disqualifies it from being a natural number. Proof by contraposition is a powerful tool in the Architecture of Proof because it allows us to choose the most convenient starting point. By understanding that $P \\rightarrow Q$ and $\\neg Q \\rightarrow \\neg P$ are the same, we gain a second perspective on every conditional claim. No, though they are related. In a contrapositive proof, you prove a specific equivalent statement (If not Q, then not P). In a proof by contradiction, you assume the entire statement is false and show that this assumption leads to an impossible result (a contradiction). Sometimes both the direct path and the contrapositive path are difficult. In those cases, mathematicians might try other techniques like induction or proof by contradiction. The contrapositive is just one tool in the toolbox, not a universal solution. Yes, but you have to be careful. An 'if and only if' statement ($P \\leftrightarrow Q$) is actually two statements: $P \\rightarrow Q$ and $Q \\rightarrow P$. You can use the contrapositive to prove either or both of those individual directions. The name comes from Latin roots meaning 'placed against'. You are positioning the negations against the original terms and swapping their places. Every conditional (if-then) statement has a contrapositive. If a statement doesn't have an 'if' and a 'then' structure, you can't form a contrapositive in the standard way. Chapter: The Domino Effect When we look at the first few natural numbers, patterns often emerge that seem too perfect to be a coincidence. It appears that the sum of the first $n$ odd numbers is always $n^2$, but we have only checked four cases. There are an infinite number of natural numbers, so checking them one by one is impossible. No. In mathematics, a pattern can hold for millions of cases and then fail at the next one. We need a formal proof. To solve this, we use a technique called mathematical induction, which handles infinite lists through logic rather than manual counting. Mathematical induction relies on a specific two-part structure to ensure a statement is true for every number in a sequence. The base case is the foundation of the proof, where we verify the statement for the smallest value in our set. Without a base case, we might prove a 'bridge' between numbers that doesn't actually start anywhere. Now that we know the pattern starts correctly, we need to prove that it propagates forward. This brings us to the inductive step, which is a conditional argument: if it works for $k$, then it works for $k+1$. In our example, the inductive hypothesis is assuming that the sum of the first $k$ odd numbers equals $k^2$. To reach our goal, we add the next odd number to both sides of that assumption. Because we showed that truth 'travels' from $k$ to $k+1$, the base case we proved earlier now triggers a chain reaction. Let's pause to consider a failure. If we had the inductive step but the base case was false, the whole proof would be worthless. The proof fails. You have only proven specific cases, not a general rule for all numbers. Mathematical induction transforms an infinite problem into a finite one with just two requirements: a start and a connection. This method is the standard tool for proving properties about sets of numbers that never end. Yes, but you have to adjust your base case and the direction of your step. For example, if you want to prove something for all integers less than or equal to -1, your base case would be -1, and your inductive step would prove that if it works for $k$, it works for $k-1$. Then your inductive step will be impossible to prove. The inductive step requires showing that the truth *always* passes from $k$ to $k+1$. If it fails at 5, then the link between 4 and 5 must be broken, and your algebraic proof will fail. No, there are other methods like direct deduction or proof by contradiction. However, induction is specifically 'built' for natural numbers and sequences, making it the most natural choice for those types of problems. It's not cheating because we aren't saying it *is* true; we are saying *if* it is true. We are testing the strength of the connection. By assuming $P(k)$, we are just seeing where that assumption leads. If it leads to $P(k+1)$, we've proven the connection exists. Yes! You can use induction on any 'countable' set. For example, you can prove that any polygon with $n$ sides has a sum of interior angles equal to $(n-2) \\times 180^{\\circ}$. The base case would be a triangle ($n=3$), and the inductive step would involve adding one more vertex.

From the Knowverse course text.

Chapter: The Domino Effect When we deal with the set of natural numbers, we face a list that never ends, which makes traditional step-by-step checking impossible. A natural number is any positive whole number in the set $\{1, 2, 3, ...\}$. Suppose we have a claim that works for $n=1$, $n=2$, and $n=3$. We might be tempted to say it works for every number. However, in mathematics, checking a few cases is not a proof. We need a way to reach every number in the infinite list without checking them one by one. No. Because the list of natural numbers is infinite, the computer will always have more numbers left to check, no matter how much time passes. Mathematical induction is the technique designed to solve this problem by creating a logical chain reaction. Instead of proving every case separately, we prove that the truth of one case guarantees the truth of the next one. The base case is our starting point. It is usually the proof that the statement holds for $n=1$. Let's use a specific example: the sum of the first $n$ integers is equal to $\\frac{n(n+1)}{2}$. Even though the base case is often simple, the entire proof fails without it. It provides the initial 'truth' that we will carry forward. Now we move to the inductive step. This is where we build a bridge from any number $k$ to the next number $k+1$. First, we make an assumption called the inductive hypothesis. We assume the statement is true for some arbitrary number $k$. We don't know if it's true for $k$ yet, but we say: "Suppose it is true for $k$." To prove the goal, we start with the sum of the first $k+1$ numbers: $(1 + 2 + ... + k) + (k+1)$. Now we simplify the expression: $\\frac{k(k+1)}{2} + (k+1)$. By showing that $P(k)$ leads to $P(k+1)$, we have completed the inductive step. Mathematical induction works because it combines a specific fact (the base case) with a universal rule (the inductive step). Yes, but you have to adjust your base case. If you want to prove something for all integers $\\ge -5$, your base case would be $n = -5$. The inductive step would still show that if it works for $k$, it works for $k+1$ (e.g., $-5 \\to -4 \\to -3 ...$). No. If the statement is false for $n=4$, you will find that the inductive step fails. Specifically, you will be unable to prove that $P(3) \\implies P(4)$ using logical deduction, even if $P(1) \\implies P(2)$ seemed to work. In common language, 'induction' often means guessing a rule from examples. In mathematics, 'Mathematical Induction' is actually a rigorous deductive method. It's named induction because it moves from specific instances to a general rule, but it does so with 100% logical certainty. Yes. In standard induction, we only assume the statement is true for $k$. In Strong Induction, we assume the statement is true for *all* numbers from the base case up to $k$. This gives us more tools to prove the $k+1$ case and is useful for complex problems like prime factorization. Generally, no. Induction relies on 'discrete' steps (where there is a clear 'next' number). Real numbers are 'dense,' meaning between any two numbers, there are infinitely many more. For those, mathematicians use different techniques like 'Transfinite Induction' or properties of the real number line. Chapter: Direct Deduction A logical proof is essentially a navigation through facts to reach a destination that was not initially obvious. In a direct deduction, we move in a single, straight line from things we already know to a new conclusion. A direct proof is the most basic form of this journey, where we never use contradictions or 'what if' scenarios. The most common rule used in direct deduction is called Modus Ponens, which means 'the way that affirms'. In the statement 'If P, then Q', the part P is called the antecedent, which is the condition that comes before. The part Q is called the consequent, which is the logical result that follows if the condition is met. Notice that the logic only flows from the antecedent to the consequent, not the other way around. No. Having four sides is the consequent. You cannot prove the antecedent (it is a square) just because the consequent is true. Most arguments are more than one step long; they form a chain of reasoning. In a chain, the consequent of the first step becomes the antecedent for the next step. This property is known as transitivity: if A leads to B and B leads to C, then A leads to C. Consider a computer: If you press 'Save', the software sends data. If the software sends data, the hard drive spins. By direct deduction, we can conclude that pressing 'Save' causes the hard drive to spin. The entire proof collapses. A direct deduction requires every single link to be perfectly valid to guarantee the truth of the conclusion. Direct deduction is the art of stacking these Modus Ponens steps to build an unshakeable wall of logic. Yes. If your starting premises are false, even perfect logic will lead to a false conclusion. Logic only guarantees that *if* the start is true, the end is true. While it seems simple, formalizing it allows us to check extremely complex arguments where the 'obvious' truth might be hidden. It also prevents us from making mistakes like reversing the logic. An argument is valid if the conclusion follows from the premises. A direct proof is a specific way of presenting that argument as a forward-moving sequence of steps. Theoretically, no. Some mathematical proofs involve thousands of steps. However, longer chains are harder to verify and have more 'links' where a mistake could hide. In formal direct deduction, rules must be 100% true. If a rule has exceptions, it is not a valid tool for a strict logical proof, as it cannot guarantee the truth of the conclusion. Chapter: Indirect Paths Sometimes, proving that a statement is true by building it from scratch feels like climbing a vertical wall without any equipment. In your previous look at Direct Deduction, you learned to move from point A to point B using a clear, forward-moving chain of logic. But what happens when you want to prove that something does not exist, or that a certain path is impossible to take? To solve this, we rely on a fundamental rule of logic called the Law of Excluded Middle. Because of this law, if we can 100% prove that a statement cannot be false, it must, by default, be true. The light must be on. Since there is no third state between 'on' and 'off' in this logic, ruling out 'off' leaves only 'on' as the truth. This strategy is known as Proof by Contradiction, or more traditionally, Reductio ad absurdum. Instead of proving a statement directly, you assume the opposite is true and follow that logic until it breaks. Let's look at a concrete example: proving there is no smallest positive fraction. If we try to prove this directly, we'd have to check every possible fraction, which is impossible because there are infinitely many. Instead, we use the indirect path. We start by assuming the opposite: 'There IS a smallest positive fraction.' Let's call this supposed smallest fraction x. Now, we apply a simple rule: if we divide any positive number by 2, we get a smaller positive number. Our assumption that a 'smallest fraction' exists led us to nonsense. Because that assumption is now proven to be impossible, the opposite must be true: there is no smallest positive fraction. Structuring these proofs requires careful setup of your initial assumption. If you want to prove 'All cats are mammals,' your indirect proof must begin with: 'Assume there exists at least one cat that is not a mammal.' You then search for a fact about mammals that this 'non-mammal cat' would violate, creating the necessary glitch in the logic. The Law of Excluded Middle ensures that this 'survival of the fittest' approach to truth actually works. By mastering the Reductio ad absurdum, you gain a powerful tool for tackling complex problems where a direct approach is blocked. In the next chapters, we will see how this 'backward' thinking helps us prove even more elusive mathematical truths. Not at all! You aren't claiming the lie is true; you are exploring the *consequences* of that lie to show they are impossible. It is a perfectly valid logical tool used by mathematicians for thousands of years. Not necessarily. It might just mean you haven't found the right chain of logic yet. Failing to find a contradiction doesn't prove the assumption is true; it just means the proof is incomplete. Technically yes, but it's often 'overkill'. If a direct proof is available, it's usually clearer and more informative. Contradiction is best saved for when the direct path is blocked or overly complicated. No. A counter-example disproves a general claim by showing one case where it fails. Reductio ad absurdum *proves* a claim by showing its opposite is impossible. They are related but serve opposite goals. In formal logic and math, yes. In everyday conversation, things can be 'gray' or 'somewhat true.' But for the architecture of proof, we assume a strict binary to ensure our conclusions are absolute. Chapter: Proving the Negative Proving a statement directly is often like walking straight through a thick forest; the path is blocked by messy calculations or complex variables. Consider the goal of proving that if the square of an integer, $n^2$, is even, then the integer $n$ itself must also be even. Dealing with square roots in a proof about integers is frustrating because roots often result in irrational numbers. Yes. We can prove that 'If $n$ is NOT even (odd), then $n^2$ is NOT even (odd)'. This is the contrapositive. In our example, the antecedent ($P$) is '$n^2$ is even' and the consequent ($Q$) is '$n$ is even'. The negation of a statement simply asserts the opposite of the original claim. But why are we allowed to swap them? In logic, two statements are logically equivalent if they always share the same truth value. Because they are equivalent, proving the contrapositive is mathematically identical to proving the original statement. This is the essence of proof by contraposition: if the direct path is blocked, we take the equivalent 'backwards' path. Let's return to our original challenge: proving that if $n^2$ is even, then $n$ is even. Our new goal is to prove: If $n$ is odd, then $n^2$ is odd. We have successfully shown that if $n$ is odd, then $n^2$ is odd. Because this contrapositive is true, the original statement—if $n^2$ is even, then $n$ is even—is also proven. This technique is not limited to parity; it works for any logical statement involving sets or categories. The contrapositive of 'If $x \\in \\mathbb{N}$, then $x \\in \\mathbb{Z}$' is 'If $x \\notin \\mathbb{Z}$, then $x \\notin \\mathbb{N}$'. No. Since all natural numbers are integers, failing to be an integer automatically disqualifies it from being a natural number. Proof by contraposition is a powerful tool in the Architecture of Proof because it allows us to choose the most convenient starting point. By understanding that $P \\rightarrow Q$ and $\\neg Q \\rightarrow \\neg P$ are the same, we gain a second perspective on every conditional claim. No, though they are related. In a contrapositive proof, you prove a specific equivalent statement (If not Q, then not P). In a proof by contradiction, you assume the entire statement is false and show that this assumption leads to an impossible result (a contradiction). Sometimes both the direct path and the contrapositive path are difficult. In those cases, mathematicians might try other techniques like induction or proof by contradiction. The contrapositive is just one tool in the toolbox, not a universal solution. Yes, but you have to be careful. An 'if and only if' statement ($P \\leftrightarrow Q$) is actually two statements: $P \\rightarrow Q$ and $Q \\rightarrow P$. You can use the contrapositive to prove either or both of those individual directions. The name comes from Latin roots meaning 'placed against'. You are positioning the negations against the original terms and swapping their places. Every conditional (if-then) statement has a contrapositive. If a statement doesn't have an 'if' and a 'then' structure, you can't form a contrapositive in the standard way. Chapter: The Domino Effect When we look at the first few natural numbers, patterns often emerge that seem too perfect to be a coincidence. It appears that the sum of the first $n$ odd numbers is always $n^2$, but we have only checked four cases. There are an infinite number of natural numbers, so checking them one by one is impossible. No. In mathematics, a pattern can hold for millions of cases and then fail at the next one. We need a formal proof. To solve this, we use a technique called mathematical induction, which handles infinite lists through logic rather than manual counting. Mathematical induction relies on a specific two-part structure to ensure a statement is true for every number in a sequence. The base case is the foundation of the proof, where we verify the statement for the smallest value in our set. Without a base case, we might prove a 'bridge' between numbers that doesn't actually start anywhere. Now that we know the pattern starts correctly, we need to prove that it propagates forward. This brings us to the inductive step, which is a conditional argument: if it works for $k$, then it works for $k+1$. In our example, the inductive hypothesis is assuming that the sum of the first $k$ odd numbers equals $k^2$. To reach our goal, we add the next odd number to both sides of that assumption. Because we showed that truth 'travels' from $k$ to $k+1$, the base case we proved earlier now triggers a chain reaction. Let's pause to consider a failure. If we had the inductive step but the base case was false, the whole proof would be worthless. The proof fails. You have only proven specific cases, not a general rule for all numbers. Mathematical induction transforms an infinite problem into a finite one with just two requirements: a start and a connection. This method is the standard tool for proving properties about sets of numbers that never end. Yes, but you have to adjust your base case and the direction of your step. For example, if you want to prove something for all integers less than or equal to -1, your base case would be -1, and your inductive step would prove that if it works for $k$, it works for $k-1$. Then your inductive step will be impossible to prove. The inductive step requires showing that the truth *always* passes from $k$ to $k+1$. If it fails at 5, then the link between 4 and 5 must be broken, and your algebraic proof will fail. No, there are other methods like direct deduction or proof by contradiction. However, induction is specifically 'built' for natural numbers and sequences, making it the most natural choice for those types of problems. It's not cheating because we aren't saying it *is* true; we are saying *if* it is true. We are testing the strength of the connection. By assuming $P(k)$, we are just seeing where that assumption leads. If it leads to $P(k+1)$, we've proven the connection exists. Yes! You can use induction on any 'countable' set. For example, you can prove that any polygon with $n$ sides has a sum of interior angles equal to $(n-2) \\times 180^{\\circ}$. The base case would be a triangle ($n=3$), and the inductive step would involve adding one more vertex. Chapter: Finding a Flaw Suppose you start connecting points on a circle and counting the separate regions created inside the shape. With 2 points, you get 2 regions. With 3 points, you get 4. With 4 points, you get 8. The pattern seems obvious. Most people guess 32, but the actual answer is 31. When you add the 6th point, the 'doubling' rule instantly shatters. You find only 31 regions, not 32. This specific case—the 6th point—is what mathematicians call a counterexample. A counterexample is a single, specific instance that proves a general statement is false. To understand why one example is so powerful, we need to look at the structure of universal statements. A universal statement claims that something is true for *every* member of a group, like 'All birds fly'. If you say 'All humans are over 5 feet tall', I don't need to measure everyone. I only need to find one person who isn't. This highlights a vital limit in mathematics: you cannot prove a universal statement just by listing 'true' examples. Consider the claim: 'For any number $n$, $n^2 + n + 41$ is a prime number'. Even though you had 40 successful examples, they did not constitute a proof. In mathematics, a single counterexample outweighs a billion 'true' instances. This is why mathematicians are obsessed with rigor. We don't just look for patterns; we look for the one case that might break them. No. Counterexamples are strictly a tool for disproof. To prove a statement is true, you need a general logical argument that covers every possible case, not just a single example. In mathematics, it doesn't matter how rare the case is. If it exists, the general claim is false. For example, the number 2 is the only even prime, but that one 'weird' case is enough to disprove the claim that 'All primes are odd'. Good places to start are boundary cases or 'extreme' values. For numbers, try 0, 1, negative numbers, or very large numbers. For shapes, try 'degenerate' cases like a circle with zero radius or a triangle where all points are on a line. Not at all! Often, finding a counterexample helps mathematicians refine a claim. Instead of saying 'All prime numbers are odd,' we change it to 'All prime numbers *greater than 2* are odd.' The counterexample helps us find the true boundaries of a rule. In everyday language, we say 'the exception proves the rule.' In math, there are no exceptions. A single 'exception' is a counterexample that invalidates the rule entirely. Math is an all-or-nothing system.

From the Knowverse course text.