Language and methods of proof
Use the language of logic precisely: implication, converse, contrapositive, negation and equivalence; apply quantifiers (, ); construct and evaluate counterexamples; identify valid argument forms.
Worked examples
Identifying the contrapositive and converse
Straightforward
Problem
Given the statement "If it is raining (), then the ground is wet ()," write the converse, contrapositive, and inverse of the statement, and determine which of the four statements are true.
1
State the original implication in the form .
Original: "If it is raining, then the ground is wet."
2
State the converse .
Converse: "If the ground is wet, then it is raining."
3
State the contrapositive .
Contrapositive: "If the ground is not wet, then it is not raining."
4
State the inverse .
Inverse: "If it is not raining, then the ground is not wet."
5
Determine which statements are true.
The original and contrapositive are both true, and are logically equivalent. The converse and inverse are both false, since the ground could be wet for another reason (e.g. someone watered the garden).
Answer
The original and contrapositive are true and logically equivalent; the converse and inverse are false.
Proof by contrapositive
Moderate
Problem
Prove that if is odd, then is odd.
1
Recognise that a direct proof is awkward, and instead prove the contrapositive.
Contrapositive: "If is even, then is even."
2
Assume is even and write it in that form.
Assume is even. Then for some integer .
3
Compute and show it is even.
. Since is an integer, is even.
4
Conclude using the equivalence of a statement and its contrapositive.
We have proved the contrapositive. Therefore, by logical equivalence, if is odd then is odd.
Answer
If is odd, then is odd, proved via the equivalent contrapositive.
Disproving a universal statement with a counterexample
Challenging
Problem
Disprove the statement: "For all positive integers , the number is prime."
1
Recall how to disprove a universally quantified statement.
The statement is is prime. Its negation is is not prime, so a single counterexample is sufficient to disprove it.
2
Test a value of likely to break the pattern.
Try : .
3
Show the resulting value is not prime.
, which is not prime. So is a counterexample.
Answer
disproves the statement, since is not prime.
Practise
Q1·Straightforward
What is the contrapositive of the statement "If is even, then is even"?
Explanation
The statement has the form where : " is even" and : " is even".
The contrapositive is :
- : " is odd"
- : " is odd"
So the contrapositive is **"If is odd, then is odd."**
Note: the contrapositive is logically equivalent to the original statement. Option (b) is the inverse (), which is not equivalent. Option (a) is the converse (), also not equivalent.
The contrapositive is :
- : " is odd"
- : " is odd"
So the contrapositive is **"If is odd, then is odd."**
Note: the contrapositive is logically equivalent to the original statement. Option (b) is the inverse (), which is not equivalent. Option (a) is the converse (), also not equivalent.
Q2·Straightforward
What is the negation of the statement "There exists an integer such that "?
Explanation
The statement has the form where : "".
The negation is .
is .
So the negation is **"For all integers , ."**
This is in fact a true statement (squares are always non-negative), which is consistent with the original statement being false.
The negation is .
is .
So the negation is **"For all integers , ."**
This is in fact a true statement (squares are always non-negative), which is consistent with the original statement being false.
Q3·Straightforward
Which of the following is the converse of "If is divisible by 6, then is divisible by 2"?
Explanation
The statement has the form where:
- : " is divisible by 6"
- : " is divisible by 2"
The converse is : **"If is divisible by 2, then is divisible by 6."**
Note that the original statement is **true** (every multiple of 6 is a multiple of 2), but the converse is **false** — for example, is divisible by 2 but not by 6. The converse of a true statement is not necessarily true.
Option (c) is the contrapositive (which is true and equivalent to the original). Option (b) is the inverse.
- : " is divisible by 6"
- : " is divisible by 2"
The converse is : **"If is divisible by 2, then is divisible by 6."**
Note that the original statement is **true** (every multiple of 6 is a multiple of 2), but the converse is **false** — for example, is divisible by 2 but not by 6. The converse of a true statement is not necessarily true.
Option (c) is the contrapositive (which is true and equivalent to the original). Option (b) is the inverse.
Q4·Straightforward
The statement "For all real numbers , " is false. Which of the following values of is a counterexample?
Explanation
Check each option:
- : ✓ (not a counterexample)
- : ✓ (not a counterexample)
- : , and , so is **false** ✓ — this is a counterexample
- : ✓ (not a counterexample)
The counterexample is . Note that and also work (equality holds at those points), but are not listed.
- : ✓ (not a counterexample)
- : ✓ (not a counterexample)
- : , and , so is **false** ✓ — this is a counterexample
- : ✓ (not a counterexample)
The counterexample is . Note that and also work (equality holds at those points), but are not listed.
Q5·Moderate
Which of the following logical argument forms is valid?
Explanation
**Option (c) is valid.** This is called *modus tollens*: from and , we conclude . This is equivalent to applying the contrapositive ().
**Option (a)** — Affirming the consequent: just because is true doesn't mean was the cause. Invalid.
Example: "If it rains, the ground is wet; the ground is wet; therefore it rained." The ground could be wet for other reasons.
**Option (b)** — Denying the antecedent: being false says nothing about . Invalid.
**Option (d)** — Also invalid: a false gives no information about either way.
**Option (a)** — Affirming the consequent: just because is true doesn't mean was the cause. Invalid.
Example: "If it rains, the ground is wet; the ground is wet; therefore it rained." The ground could be wet for other reasons.
**Option (b)** — Denying the antecedent: being false says nothing about . Invalid.
**Option (d)** — Also invalid: a false gives no information about either way.
Q6·Moderate
Which of the following is logically equivalent to the statement ?
Explanation
The statement is logically equivalent to its contrapositive , which is **option (d)**.
You can verify this with a truth table:
You can verify this with a truth table:
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
The columns are identical.
- Option (a) is the converse — not equivalent.
- Option (b) is the inverse — equivalent to the converse, but not to the original.
- Option (c) is neither converse nor contrapositive.
- Option (a) is the converse — not equivalent.
- Option (b) is the inverse — equivalent to the converse, but not to the original.
- Option (c) is neither converse nor contrapositive.
Q7·Moderate
Disprove the following statement by finding a counterexample:
"If is divisible by 4, then is divisible by 4."
"If is divisible by 4, then is divisible by 4."
✎ Work this one through on paper — proofs are self-assessed.
Worked proof
**Claim:** The statement is false.
**Counterexample:** Let .
- , and , so is divisible by 4. ✓
- , and , so is **not** divisible by 4. ✗
Since satisfies the hypothesis ( divisible by 4) but not the conclusion ( divisible by 4), the statement is disproved.
**Contrast with a true statement:** "If is divisible by 4 and is prime, then ." — here the extra condition forces .
**Counterexample:** Let .
- , and , so is divisible by 4. ✓
- , and , so is **not** divisible by 4. ✗
Since satisfies the hypothesis ( divisible by 4) but not the conclusion ( divisible by 4), the statement is disproved.
**Contrast with a true statement:** "If is divisible by 4 and is prime, then ." — here the extra condition forces .
Q8·Moderate
Prove by the contrapositive method:
"If is even, then is even."
Clearly state the contrapositive and prove it directly.
"If is even, then is even."
Clearly state the contrapositive and prove it directly.
✎ Work this one through on paper — proofs are self-assessed.
Worked proof
**Contrapositive:** "If is odd, then is odd."
This is logically equivalent to the original statement, so proving it suffices.
**Proof of the contrapositive:**
Assume is odd. Then for some integer .
Squaring:
Since is an integer, is of the form (with ), which is odd.
**Conclusion:** We have shown that if is odd then is odd. By contrapositive, if is even then is even.
This is logically equivalent to the original statement, so proving it suffices.
**Proof of the contrapositive:**
Assume is odd. Then for some integer .
Squaring:
Since is an integer, is of the form (with ), which is odd.
**Conclusion:** We have shown that if is odd then is odd. By contrapositive, if is even then is even.
Q9·Moderate
The statement "For all real numbers , " is false. Which of the following is the best counterexample?
Explanation
** is the counterexample.**
, and is false.
All other listed values give :
- ✓
- ✓
- ✓
The correct statement would be "For all real numbers , " — adding the condition makes it true.
, and is false.
All other listed values give :
- ✓
- ✓
- ✓
The correct statement would be "For all real numbers , " — adding the condition makes it true.
Q10·Challenging
Prove by the contrapositive method:
"For all integers , if is divisible by 3, then is divisible by 3."
Consider all possible remainders when is divided by 3.
"For all integers , if is divisible by 3, then is divisible by 3."
Consider all possible remainders when is divided by 3.
✎ Work this one through on paper — proofs are self-assessed.
Worked proof
**Contrapositive:** "If is not divisible by 3, then is not divisible by 3."
**Proof of the contrapositive:**
Assume is not divisible by 3. Then the remainder when is divided by 3 is either 1 or 2.
**Case 1:** for some integer .
The remainder when is divided by 3 is 1, so is not divisible by 3.
**Case 2:** for some integer .
The remainder when is divided by 3 is 1, so is not divisible by 3.
In both cases, is not divisible by 3.
**Conclusion:** By contrapositive, if is divisible by 3 then is divisible by 3.
**Application:** This result is used in the proof that is irrational.
**Proof of the contrapositive:**
Assume is not divisible by 3. Then the remainder when is divided by 3 is either 1 or 2.
**Case 1:** for some integer .
The remainder when is divided by 3 is 1, so is not divisible by 3.
**Case 2:** for some integer .
The remainder when is divided by 3 is 1, so is not divisible by 3.
In both cases, is not divisible by 3.
**Conclusion:** By contrapositive, if is divisible by 3 then is divisible by 3.
**Application:** This result is used in the proof that is irrational.
Q11·Challenging
Prove that the product of two odd integers is odd.
✎ Work this one through on paper — proofs are self-assessed.
Worked proof
**Proof:**
Let and be odd integers. Then and for some integers and .
Compute the product:
Let , which is an integer. Then .
Since is of the form , it is odd.
**Conclusion:** The product of two odd integers is odd.
**Remark:** Combining this with the fact that the product of two even integers is even (trivial), and that even odd = even, we can describe the parity of any product.
Let and be odd integers. Then and for some integers and .
Compute the product:
Let , which is an integer. Then .
Since is of the form , it is odd.
**Conclusion:** The product of two odd integers is odd.
**Remark:** Combining this with the fact that the product of two even integers is even (trivial), and that even odd = even, we can describe the parity of any product.
Q12·Challenging
Consider the statement: "There exists a real number such that ."
(a) Write the negation of this statement.
(b) Determine whether the original statement is true or false, and justify your answer.
(a) Write the negation of this statement.
(b) Determine whether the original statement is true or false, and justify your answer.
✎ Work this one through on paper — proofs are self-assessed.
Worked proof
**(a) Negation:**
The statement has the form .
Its negation is: **"For all real numbers , ."**
Equivalently: "There is no real number satisfying ."
**(b) Truth value:**
The original statement is **false**.
**Justification:** For all real numbers , we have (a square is always non-negative). Therefore , so for any real .
This means the negation ("for all real , ") is **true**, confirming the original existential statement is false.
**Remark:** The equation does have solutions in the complex numbers (), but not in the reals.
The statement has the form .
Its negation is: **"For all real numbers , ."**
Equivalently: "There is no real number satisfying ."
**(b) Truth value:**
The original statement is **false**.
**Justification:** For all real numbers , we have (a square is always non-negative). Therefore , so for any real .
This means the negation ("for all real , ") is **true**, confirming the original existential statement is false.
**Remark:** The equation does have solutions in the complex numbers (), but not in the reals.
Open Math
Language and methods of proof
Proof · MEX-12-01
Name:
Date:
Q1Straightforward
What is the contrapositive of the statement "If is even, then is even"?
- A.If is even, then is even.
- B.If is odd, then is odd.
- C.If is odd, then is odd.
- D.If is even, then is odd.
Q2Straightforward
What is the negation of the statement "There exists an integer such that "?
- A.There exists an integer such that .
- B.For all integers , .
- C.For all integers , .
- D.There exists an integer such that .
Q3Straightforward
Which of the following is the converse of "If is divisible by 6, then is divisible by 2"?
- A.If is divisible by 2, then is divisible by 6.
- B.If is not divisible by 6, then is not divisible by 2.
- C.If is not divisible by 2, then is not divisible by 6.
- D.If is divisible by 3, then is divisible by 6.
Q4Straightforward
The statement "For all real numbers , " is false. Which of the following values of is a counterexample?
- A.
- B.
- C.
- D.
Q5Moderate
Which of the following logical argument forms is valid?
- A.; is true; therefore is true.
- B.; is false; therefore is false.
- C.; is false; therefore is false.
- D.; is false; therefore is true.
Q6Moderate
Which of the following is logically equivalent to the statement ?
- A.
- B.
- C.
- D.
Q7Moderate
Disprove the following statement by finding a counterexample:
"If is divisible by 4, then is divisible by 4."
"If is divisible by 4, then is divisible by 4."
Q8Moderate
Prove by the contrapositive method:
"If is even, then is even."
Clearly state the contrapositive and prove it directly.
"If is even, then is even."
Clearly state the contrapositive and prove it directly.
Q9Moderate
The statement "For all real numbers , " is false. Which of the following is the best counterexample?
- A.
- B.
- C.
- D.
Q10Challenging
Prove by the contrapositive method:
"For all integers , if is divisible by 3, then is divisible by 3."
Consider all possible remainders when is divided by 3.
"For all integers , if is divisible by 3, then is divisible by 3."
Consider all possible remainders when is divided by 3.
Q11Challenging
Prove that the product of two odd integers is odd.
Q12Challenging
Consider the statement: "There exists a real number such that ."
(a) Write the negation of this statement.
(b) Determine whether the original statement is true or false, and justify your answer.
(a) Write the negation of this statement.
(b) Determine whether the original statement is true or false, and justify your answer.
Worked solutions and answers at openmath.au/year-12/extension-2/the-nature-of-proof/language-and-methods-of-proof