MTH1020 · Analysis of Change
Logic & Proof: Foundations
Week 1 of Monash MTH1020 Analysis of Change opens the unit with the language of rigorous mathematics: what a proof is, conditional statements and their converse, contrapositive and negation, and the four standard proof techniques — direct, contrapositive, counterexample and contradiction. It layers in sets and divisibility, quantifiers, and the inequalities toolkit (x² ≥ 0, a² + b² ≥ 2ab and the AM–GM inequality). These skills are examined directly in the early mid-semester tests and, because Monash awards marks for mathematical communication, they set the standard for how every later solution must be written.
What this chapter covers
- 01What a proof is: logical certainty vs verifying examples; a single counterexample disproves a 'for all' statement
- 02Conditional statements P ⇒ Q; hypothesis and conclusion; direct proof (assume P, deduce Q)
- 03Negation and De Morgan's laws; negating quantifiers: not(∀x P) ≡ ∃x not P
- 04Converse (Q ⇒ P) vs contrapositive (not Q ⇒ not P); a statement is equivalent to its contrapositive
- 05Proof by contradiction: assume the negation, derive a contradiction (e.g. √2 and log₂(3) irrational)
- 06Sets (ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ), builder notation, intervals, and divisibility (m = kn), primes vs composites
- 07Universal (∀) and existential (∃) quantifiers; the Euler example n²+n+41 that fails at n = 40
- 08Inequalities: x² ≥ 0, a² + b² ≥ 2ab, and the AM–GM inequality (x+y)/2 ≥ √(xy), equality iff x = y
Proof by contradiction: √2 is irrational
- +1Set up the contradiction. Suppose, for contradiction, that √2 is rational. Then we can write √2 = a/b where a and b are integers with b ≠ 0, and the fraction is in lowest terms — a and b share no common factor greater than 1.
- +1Square and deduce a is even. Squaring gives 2 = a²/b², so a² = 2b². Hence a² is even, and since the square of an odd integer is odd, a itself must be even. Write a = 2c for some integer c.
- +1Substitute and deduce b is even. Then (2c)² = 2b², so 4c² = 2b², giving b² = 2c². Therefore b² is even, and by the same parity argument b is even.
- +1Reach the contradiction. Now a and b are both even, so they share the common factor 2 — contradicting the assumption that a/b was in lowest terms. The assumption that √2 is rational is therefore false, so √2 is irrational. □
Key terms
- Conditional statement (P ⇒ Q)
- An 'if P then Q' claim, where P is the hypothesis and Q the conclusion. A direct proof assumes P is true and deduces Q.
- Converse
- The converse of P ⇒ Q is Q ⇒ P. Its truth is independent of the original: a true statement can have a false converse.
- Contrapositive
- The contrapositive of P ⇒ Q is (not Q) ⇒ (not P). It is logically equivalent to the original, so proving it proves the statement.
- Proof by contradiction
- Assume the statement is false, derive a logical contradiction, and conclude the statement is true. Classic uses: √2 and log₂(3) are irrational.
- Counterexample
- A single instance where a universal ('for all') statement fails, which disproves it. Example: n²+n+41 is prime for many n but fails at n = 40.
- AM–GM inequality
- For non-negative reals, (x+y)/2 ≥ √(xy) — the arithmetic mean is at least the geometric mean — with equality if and only if x = y. It follows from (√x − √y)² ≥ 0.
Logic & Proof: Foundations FAQ
What's the difference between the converse and the contrapositive?
The converse of 'if P then Q' swaps the two parts to give 'if Q then P', and it need not have the same truth value — proving a statement tells you nothing about its converse. The contrapositive flips and negates both parts to give 'if not Q then not P', and it is logically equivalent to the original, which is why 'proof by contrapositive' is a valid strategy. A common Monash exam slip is to 'prove' a statement by accidentally proving its converse.
When should I use contradiction versus a direct proof?
Reach for a direct proof first: assume the hypothesis and deduce the conclusion in a chain of justified steps. Use contradiction when assuming the statement is false gives you something concrete to work with — irrationality proofs are the standard example, because 'suppose √2 = a/b in lowest terms' hands you an equation to manipulate. Contrapositive is best when 'not Q' is a friendlier starting point than P, as in 'if n² is even then n is even'.
How much of the mark is for the way I write the proof?
A significant fraction. Monash marks mathematical communication across every task, so full marks require full English sentences, defined variables, each step following logically from the last, and no ∀/∃/⇒ used as prose shorthand. A correct final answer with gaps in the reasoning or undefined symbols will drop communication marks — practise writing proofs the way the Monash Guidelines for Writing in Mathematics describe.
Can AI help me with proofs in MTH1020?
Yes, as a study aid. Sia can explain why a contrapositive is equivalent to the original, walk you through the structure of a contradiction proof, or check whether your negation of a quantified statement is correct — step by step, in the Monash write-up style. Use it to rehearse the method on your own applied-class questions; it does not complete graded assessment for you, and Monash academic-integrity rules apply.
Exam move
Build a personal 'proof toolkit' page: one worked template each for direct, contrapositive, counterexample and contradiction proofs, plus the negation rules for quantifiers and De Morgan's laws. Drill parity and divisibility statements (even/odd, m = kn) until the algebra is automatic, and always write the argument in full sentences with a named technique and a concluding line — that is exactly how Monash marks it. Keep the inequalities trio (x² ≥ 0, a² + b² ≥ 2ab, AM–GM) close, since they reappear as one-mark lemmas. This Week-1 material is tested early in MST1 and again in MST2 (Weeks 1–4), so rehearse it more than once. When a step won't click, ask Sia to re-explain that single line a different way.
Working through Logic & Proof: Foundations in MTH1020? Sia is AskSia’s AI Mathematics tutor — ask any MTH1020 Logic & Proof: Foundations question and get a clear, step-by-step explanation grounded in how MTH1020 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
