Loav · VCE Specialist Mathematics · Units 3 & 4
S34-P01 · Discrete mathematics · Logic and proof
1. A proof starts by deciding what is claimed
A conjecture is a statement whose truth is being investigated. A proof explains why it follows from definitions, assumptions and established results. This is stronger than checking examples: a statement about every integer has infinitely many cases, and no finite list of successful substitutions covers them all. Examples help you notice a pattern and test whether a proposed claim is plausible. The argument must then explain why another permitted case cannot behave differently.
Always state the universe of values. “If x² = 9, then x = 3” is false over the real numbers because x = −3 is a counterexample. It becomes true when x is restricted to positive real numbers. A counterexample must satisfy every assumption and fail the conclusion. Choosing an excluded value does not disprove a statement. Conversely, changing the domain after finding a counterexample changes the claim; it does not repair the original proof.
Definitions turn words into usable algebra. An integer n is even when n = 2k for some integer k, and odd when n = 2k + 1 for some integer k. For integers a and b, a divides b, written a ∣ b, when b = ak for an integer k. The existence and type of k matter. Writing 6 = 4 × 1.5 does not show that 4 divides 6.
2. Implication, equivalence and the direction of a condition
Write P ⇒ Q for “if P, then Q”. P is the hypothesis; Q is the conclusion. The implication rules out a case in which P is true but Q is false. It does not claim that P must occur. For example, if an integer is divisible by 12, it is divisible by 3. Divisibility by 12 is sufficient for divisibility by 3: it guarantees it. Divisibility by 3 is necessary for divisibility by 12: it must be present whenever the stronger condition holds.
The converse exchanges the statements: Q ⇒ P. It requires its own justification. The converse of the preceding example is false, because 3 is divisible by 3 but not by 12. Do not reverse an arrow just because both statements contain the same quantities. In solving equations, squaring can create precisely this problem: x = 2 implies x² = 4, but x² = 4 allows another value.
An equivalence P ⇔ Q means both P ⇒ Q and Q ⇒ P. The phrase “if and only if” therefore requires two directions, or a chain of genuinely reversible steps. Calling a condition “necessary and sufficient” says exactly the same thing. In an inequality proof, multiplying by an unknown-sign expression is not automatically reversible without considering its sign. A reliable proof labels the direction being established and checks any restrictions used in reversing a calculation.
3. Quantifiers tell you how much must be proved
The universal quantifier ∀ means “for every”; the existential quantifier ∃ means “there is at least one”. To prove a universal statement, take an arbitrary permitted object and reason without adding special assumptions. To prove an existential statement, one valid construction can be enough. Thus an example can prove existence, while a counterexample can disprove universality. These jobs are different even though both may involve one number.
Negation reverses the quantifier and negates the condition. The negation of “for every real x, f(x) ≥ 0” is “there exists a real x for which f(x) < 0”. It is not “f(x) is negative for every x”. The negation of “there exists an integer n with property R” is “every integer n fails R”. For inequalities, the negation of x < 5 is x ≥ 5, including the boundary.
Order matters when quantifiers are nested. “For every real x there exists a real y with y > x” is true: choose y = x + 1 after x is given. “There exists a real y greater than every real x” is false: whichever y is proposed, take x = y + 1. When negating a nested statement, reverse each quantifier in its original order. State clearly whether a chosen quantity is allowed to depend on an earlier one.
4. Choose a route that exposes the structure
A direct proof starts with the hypothesis and develops justified consequences until the conclusion is obtained. A proof by cases splits the domain into exhaustive possibilities, proves the claim in each, and then reunites them. For integer parity, “even or odd” is exhaustive; “positive or negative” is not exhaustive for all integers because it omits zero. Check the split before doing the algebra.
The contrapositive of P ⇒ Q is not Q ⇒ not P. It is logically equivalent to the original implication. This route is useful when the negation of the conclusion has a simple form, such as oddness. A proof by contradiction assumes the original hypotheses and the negation of the desired conclusion, then obtains a contradiction with a definition, a hypothesis or an established fact. Name the contradiction rather than finishing with “impossible” without explanation.
Exploration may work backwards from the desired conclusion to discover a useful identity. The final proof must still show that its steps follow in a valid direction. Starting with the very inequality being proved and manipulating it into a true statement does not establish the inequality unless every step was equivalent. A safer presentation begins with a known non-negative quantity and derives the target.
Worked example 1: a direct divisibility proof
Prove that if integers a and b satisfy 7 ∣ a and 7 ∣ b, then 7 ∣ (3a − 2b). By definition, write a = 7r and b = 7s for integers r and s. Then 3a − 2b = 21r − 14s = 7(3r − 2s). Because integers are closed under multiplication and subtraction, 3r − 2s is an integer. The expression is therefore divisible by 7.
The closure sentence supplies the final logical link. A factor of 7 alone is not enough if the remaining factor might be non-integral. The converse is false: a = 2 and b = 3 give 3a − 2b = 0, which is divisible by 7, although neither a nor b is. This also reminds us that zero is a multiple of every nonzero integer.
Worked example 2: use a contrapositive to prove parity
Prove that, for an integer n, if n² + 2n is odd, then n is odd. The contrapositive says: if n is even, then n² + 2n is even. Suppose n = 2k for an integer k. Then n² + 2n = 4k² + 4k = 2(2k² + 2k), which is even because the bracket is an integer. The contrapositive is true, so the original implication is true.
To establish “if and only if”, prove the other direction too. If n = 2k + 1, then n² + 2n = 4k² + 8k + 3 = 2(2k² + 4k + 1) + 1, which is odd. These two arguments together show that n² + 2n is odd exactly when n is odd. Neither conclusion relies on testing a list of integers.
Worked example 3: a short graph-theory contradiction
A finite undirected network has vertices joined by edges, with no loops. Prove that the number of vertices of odd degree is even. The degree of a vertex counts the edges incident to it. Adding all degrees counts each edge twice, once at each endpoint. Thus the total degree is twice the number of edges and is even.
Assume for contradiction that there are an odd number of odd-degree vertices. The sum of their degrees is then odd, while the remaining even degrees sum to an even number. The total would be odd, contradicting the earlier even total. Therefore the number of odd-degree vertices must be even. This proof uses a counting observation and parity; it does not assume that the network is connected. A diagram may suggest the result, but the double-counting explanation proves it for every permitted network.
5. Inequalities, checking and assessment habits
For real a and b, (a − b)² ≥ 0 implies a² + b² ≥ 2ab. Equality holds exactly when a = b. This short proof explains both the inequality and its equality condition. When dividing an inequality by a negative quantity, reverse its direction; when dividing by a variable quantity, establish its sign first. Squaring both sides is order-preserving only under suitable sign conditions, such as both sides being non-negative.
Technology can test a conjecture, find a counterexample or expand an identity. A symbolic expansion of (a − b)² helps check algebra, but a decimal search cannot certify a universal real inequality. If a search returns no counterexample, report the searched domain and resolution. It has supplied evidence, not a proof. In an assessment, explicitly state the domain, the arbitrary starting object, the method and the concluding claim. When asked to use a particular method, use it even if another method looks shorter.
Practise, then check
Give reasons in sentences as well as algebra. In each disproof, verify that your counterexample satisfies the hypothesis.
- For integers n, consider “8 ∣ n implies 4 ∣ n”. Identify a sufficient condition and a necessary condition, and decide whether the converse holds.
- Negate: “For every real x there exists a real y such that y² > x.” Decide whether the original statement is true.
- Prove by cases that n(n + 1) is even for every integer n.
- Prove that a² + b² ≥ −2ab for all real a and b, and state when equality occurs.
- A student claims: “If a product of two integers is even, both integers are even.” Disprove the claim and state a true replacement.
- Prove by contradiction that no greatest integer exists.
- A proposed undirected network has exactly five vertices of odd degree. Explain why no such network can exist. What changes if it has six?
Reasoned answers
- Divisibility by 8 is sufficient for divisibility by 4, and divisibility by 4 is necessary for divisibility by 8. If n = 8k, then n = 4(2k), with 2k an integer. The converse is false: n = 4 is divisible by 4 but not by 8. Necessity alone does not guarantee the stronger condition.
- The negation is: “There exists a real x such that for every real y, y² ≤ x.” The original is true. Given any real x, choose y = √(|x| + 1); then y² = |x| + 1 > x. The chosen y may depend on x, as permitted by the quantifier order.
- If n = 2k, then n(n + 1) = 2k(2k + 1), an even integer. If n = 2k + 1, then n(n + 1) = (2k + 1)2(k + 1), also even. Every integer is in one of these cases, including negative integers and zero, so the proof covers the full domain.
- Start with (a + b)² ≥ 0. Expanding gives a² + 2ab + b² ≥ 0, hence a² + b² ≥ −2ab. Equality holds precisely when (a + b)² = 0, or a = −b. No positivity assumption on a or b was needed.
- Take 2 and 3: their product is 6, which is even, but 3 is odd. A true replacement is that at least one factor is even. If both factors were odd, writing them as 2r + 1 and 2s + 1 would give product 2(2rs + r + s) + 1, which is odd. This proves the replacement by contrapositive.
- Suppose a greatest integer N exists. The number N + 1 is also an integer and is greater than N. This contradicts the assumption that N is greatest. Therefore no greatest integer exists. The contradiction depends on the closure of integers under adding 1, rather than on a large numerical example.
- Five odd-degree vertices would make the total degree odd, contradicting the fact that each edge contributes 2. Six passes this necessary parity test, but the test alone does not verify an otherwise specified degree sequence. Existence is possible: three separate edges give six degree-one vertices. This construction proves existence for at least one such network.
Curriculum and sources
VCE Specialist Mathematics Units 3 and 4. Scope follows the VCAA Mathematics Study Design 2023–2027, Specialist Mathematics Areas of Study 1 and 3 as applicable, and the current Specialist Mathematics FAQ. Unit 2 complex-number foundations are retained where required. Curriculum checked 15 October 2026. Teaching reference: Cambridge Senior Mathematics VCE Specialist Mathematics 3&4, second edition (2023), sections 2A–2C, pp. 66–81. All explanations, examples, practice questions and diagrams are original. Independent teaching material; not a VCAA publication.
