Lecture 2: Proof Methods

ISE Block 1.2 Maths · Week 1

Proofs

Direct proof and evidence

• Implication: “if \(P\), then \(Q\)” is broken only when \(P\) is true and \(Q\) is false
• Direct proof: assume \(P\); reach \(Q\) by justified steps
• Arbitrary element: “Let \(n\) be an integer” does not specify its value. The proof must work for any integer \(n\)
• Evidence is not proof: 40 passing tests established 40 cases, not the universal claim; one counterexample refuted it

• TIMING: 2-3 minutes. Retrieval, not reteaching.
• The tested cases were established; only the infinite claim was not. “Checking every case” later today builds on this.
• PROMPT: which claims from the lab did you refute, and with what witness? Every true claim on the sheet had a direct proof.
• LISTEN FOR: “I tried more numbers” offered as a proof.
• The first bullet is load-bearing: the contrapositive and contradiction both lean on it.

Universal claims

• Question: can we prove that no fraction squares to exactly 2?
  • infinitely many fractions to rule out: testing can only refute
• If we can: no float’s exact value squares to exactly 2 either, however many digits it carries, because every float is a fraction
• Commit now: in Python, is math.sqrt(2) * math.sqrt(2) == 2 True or False?

• TIMING: 2 minutes.
• PROMPT: everyone commits. Keep the answer for “Floats and the square root of 2”.
• Today’s plan, said aloud: four more methods, then how to review a proof. Which method fits depends on the claim and on which assumption gives something useful to work with. Both directions are needed because an “iff” is two claims, not because a direct proof failed.

The contrapositive

Negating a statement

Statement	Its negation	Careful
\(x > 0\)	\(x \leq 0\)	not \(x < 0\): at \(x = 0\), both \(x > 0\) and \(x < 0\) are false
\(n \geq 5\)	\(n < 5\)	the boundary 5 changes side
there is no largest \(n\)	some \(n\) is largest
integer \(n\) is even	\(n\) is odd	uses the fact below

• Negation: \(\NOT(Q)\), read “not \(Q\)”, is true exactly when \(Q\) is false
  • to write it, ask: what does it look like when \(Q\) fails?
• Fact assumed (not proved here): every integer is even or odd, and not both
  • so for an integer, “not even” is “odd” and “not odd” is “even”

• TIMING: 3 minutes.
• PROMPT: negate “x > 0” before revealing the row. Expect “x < 0”.
• Taught first so the converse and contrapositive table can use NOT(Q).
• “and”, “or”: Friday; “for every”: next week.
• The fact is the Division Theorem with divisor 2 (MCS Theorem 8.1.4, p. 245), in week 4. SAY: assumed today, proved in week 4.

Converse and contrapositive

Start from an implication \(P \IMPLIES Q\), “if \(P\), then \(Q\)”.

Name	Statement	Read aloud
converse	\(Q \IMPLIES P\)	if \(Q\), then \(P\)
contrapositive	\(\NOT(Q) \IMPLIES \NOT(P)\)	if not \(Q\), then not \(P\)

• Example: “if it rains, I bring an umbrella”
  • converse: “if I bring an umbrella, it rains”
  • contrapositive: “if I don’t bring an umbrella, it doesn’t rain”

• TIMING: 3 minutes.
• PROMPT: which of the two says the same thing as the original? Commit before the next slide.
• Friday shows the other ways to write NOT(Q).

\(P\): it rains. \(Q\): I bring an umbrella.

	umbrella	no umbrella
rain	nothing broken	\(P \IMPLIES Q\) and \(\NOT(Q) \IMPLIES \NOT(P)\) broken
no rain	\(Q \IMPLIES P\) broken	nothing broken

• When is each one broken? an implication fails exactly when its “if” part holds and its “then” part fails
  • the contrapositive’s “if” is “no umbrella” and its “then” is “no rain”: it fails at rain, no umbrella, the same cell as \(P \IMPLIES Q\)

• TIMING: 3 minutes. This grid is new, not inherited from L1. First ask where the original promise is broken, then ask about the contrapositive.
• EMPHASIS: read the contrapositive’s cell slowly: “not Q true” is “Q false”; “not P false” is “P true”.

• An implication and its contrapositive are broken in exactly the same situation, so they are equivalent.
  • proving either one proves the other
• The converse is a separate claim: it fails in a different situation. It needs its own proof

• TIMING: 1 minute.

TRY: “if \(n\) is a multiple of 4, then \(n\) is even”. Write the converse and the contrapositive. Which must be true?

• Converse: “if \(n\) is even, then \(n\) is a multiple of 4”: false at \(n = 2\)
• Contrapositive: “if \(n\) is not even, then \(n\) is not a multiple of 4”: true, like the original

• TIMING: 3 minutes: 1 alone, 1 with a neighbour, 1 debrief.
• LISTEN FOR: the negation put on only one side; the converse and contrapositive swapped.

Proof by contrapositive

• Rational: a real number \(r\) is rational \(\defeq\) \(r\) equals a quotient of integers, \(m/n\) for some \(m, n \in \Int\) with \(n \neq 0\)
  • \(\Rat\) is the set of all rational numbers; \(\Rat \subset \Real\)
  • a real number that is not rational is irrational; \(\Real \setminus \Rat\)
• Theorem: for every real \(r \geq 0\), if \(r\) is irrational, then \(\sqrt{r}\) is irrational
• Direct attempt: “\(r\) is irrational” gives no fraction to manipulate
• Contrapositive: if \(\sqrt{r}\) is rational, then \(r\) is rational
  • we can write \(\sqrt r = m/n\) and square both sides

• TIMING: 2 minutes.
• \(n \neq 0\): without it \(m/n\) means nothing. MCS (p. 13) leaves it out.
• \(r \geq 0\) so that \(\sqrt{r}\) is a real number.
• SOURCE: MCS Theorem 1.5.2, p. 14.

Theorem: for every real \(r \geq 0\), if \(r\) is irrational, then \(\sqrt{r}\) is irrational.

Proof (we prove the contrapositive: if \(\sqrt{r}\) is rational, then \(r\) is rational). Let \(r \geq 0\) be real.

1. Assume \(\sqrt{r}\) is rational. ← the contrapositive’s hypothesis
2. By the definition of rational, \(\sqrt{r} = m/n\) for some integers \(m\) and \(n\) with \(n \neq 0\). ← unpack
3. Squaring both sides gives \(r = m^2/n^2\). ← compute
4. Since \(m^2\) and \(n^2\) are integers and \(n^2 \neq 0\), their quotient \(r\) is rational. \(\qedmark\) ← conclude

• Conclusion: the contrapositive holds, hence so does the theorem

• TIMING: 3 minutes.
• EMPHASIS: the first words announce the method, so the reader knows why line 1 assumes what it does.

If and only if

Two implications in one statement

\[ P \IFF Q \]

• Read aloud: “\(P\) if and only if \(Q\)”, often written “iff”
• Meaning: both \(P \IMPLIES Q\) and \(Q \IMPLIES P\) hold
  • one direction is the converse of the other
• Convention: in a mathematical definition, “if” often specifies both directions; an ordinary implication specifies only one
  • defining even by \(n = 2k\) for some integer \(k\) lets us use the condition in both directions

• TIMING: 2 minutes.

TRY: for a real number \(x\), which is true?

1. \(x = 2\) if and only if \(x^2 = 4\)
2. \(x^2 = 4\) if and only if \(x = 2\) or \(x = -2\)

• 1 is false: “if \(x = 2\), then \(x^2 = 4\)” holds, but “if \(x^2 = 4\), then \(x = 2\)” fails at \(x = -2\)
• 2 is true: \(x^2 = 4\) gives \((x - 2)(x + 2) = 0\), hence \(x = 2\) or \(x = -2\). Both values square to 4
• one failing direction makes an iff false

• TIMING: 3 minutes.
• PROMPT: hands up for each before the reveal.
• LISTEN FOR: “it’s true because 2 squared is 4”: one direction offered as both.

Both directions

• Method: to prove \(P \IFF Q\), prove \(P \IMPLIES Q\), then prove \(Q \IMPLIES P\)
  • say which direction each part proves
  • each direction may use its own method: direct, or the contrapositive
• Converse assumed (a named flaw): proving \(Q \IMPLIES P\) when the claim is \(P \IMPLIES Q\)
  • a valid proof of the converse proves nothing about the claim
  • the converse may be false: “if even, then a multiple of 4”

• TIMING: 2 minutes.
• Friday’s lab (lab 02) uses this flaw name. Bogus proof 2, later today, is an instance.

Even numbers and their squares

• Lemma: for every integer \(n\), \(n\) is even if and only if \(n^2\) is even
• Forward, “\(n\) even implies \(n^2\) even”: direct
• Backward, “\(n^2\) even implies \(n\) even”: by the contrapositive
  • starting with \(n^2 = 2k\) gives no useful expression for \(n\)
  • contrapositive: “\(n\) not even” gives \(n = 2k + 1\), which we can square
• Uses: the even-or-odd fact

• TIMING: 2 minutes.
• PROMPT: before revealing the backward plan, ask why the natural direct attempt stalls. Try \(n^2 = 2k\): what is \(n\)?
• The square-root-of-2 proof needs the backward direction; say so now.
• SOURCE: MCS Problem 1.10(a), p. 24, asks for the backward direction for nonnegative \(n\); we do both, for every integer.

Proof. Let \(n\) be an integer. We prove each direction.

• Forward (direct): assume \(n\) is even, so \(n = 2k\) for some integer \(k\)
  • then \(n^2 = 4k^2 = 2(2k^2)\), and \(2k^2\) is an integer, so \(n^2\) is even
• Backward (contrapositive): we prove “if \(n\) is not even, then \(n^2\) is not even”
  • \(n\) is not even, so \(n\) is odd (the fact): \(n = 2k + 1\) for some integer \(k\)
  • then \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\), and \(2k^2 + 2k\) is an integer, so \(n^2\) is odd
  • so \(n^2\) is not even (the fact: not both) \(\qedmark\)

• Shown: for every integer \(n\), \(n\) is even iff \(n^2\) is even

• TIMING: 5 minutes.
• Point at where each hypothesis is used: “\(n\) is even” at the first unpack; “\(n\) is not even” turned into “odd” by the fact.

Proof by cases

Splitting a proof into cases

• When: separate cases give us useful assumptions, such as even or odd
  • \(n\) even gives \(n = 2k\); \(n\) odd gives \(n = 2k + 1\)
• Method: cover every possible case and prove the claim in each
• Duty: show the cases cover every possibility
  • “\(n\) even” and “\(n\) odd” cover every integer: the fact
  • cases “\(Q\)” and “not \(Q\)” always cover everything; any other split needs a reason

• TIMING: 2 minutes.
• OPTIONAL, for a keen student: MCS §1.7, pp. 15-16, proves that any six people include three who have all met or three who have never met, by cases inside cases. Enrichment only; not taught.

A parity argument

Claim: for every integer \(n\), \(n^2 + n\) is even.

Proof (by cases). Let \(n\) be an integer. It is even or odd (the fact), so two cases cover it.

• Case 1: \(n\) is even, so \(n = 2k\) for some integer \(k\)
  • \(n^2 + n = 4k^2 + 2k = 2(2k^2 + k)\), with \(2k^2 + k\) an integer: even

• Case 2 — try it: \(n\) is odd, so \(n = 2k + 1\) for some integer \(k\). Show that \(n^2 + n\) is even.

• Odd case: \(n^2 + n = n(n + 1) = (2k + 1)(2k + 2) = 2(2k + 1)(k + 1)\); \((2k + 1)(k + 1)\) is an integer

• In every case \(n^2 + n\) is even, so it is even for every integer \(n\). \(\qedmark\)

• TIMING: 5 minutes.
• PROMPT: Reveal case 1, then give one minute to write the odd case before revealing the factorisation.
• Each case’s hypothesis is used at its unpacking line.

A proof with a missing case

Claim: for every integer \(n\), \(n^2 \geq n\).

“Proof” (by cases).

• Case \(n > 0\): \(n \geq 1\). Multiplying by \(n > 0\) gives \(n^2 \geq n\).
• Case \(n < 0\): then \(n^2 \geq 0 > n\). \(\qedmark\)

\(n\)	\(\ldots\)	\(-2\)	\(-1\)	\(0\)	\(1\)	\(2\)	\(\ldots\)
case	\(n < 0\)	\(n < 0\)	\(n < 0\)	none	\(n > 0\)	\(n > 0\)	\(n > 0\)

• Gap: \(n = 0\) is in neither case
• Lesson: the claim is true; the proof is still invalid
• A missing case (a named flaw): a case split that leaves a gap
• Repair: add “case \(n = 0\): \(0^2 = 0 \geq 0\)”. Every integer is negative, zero or positive, so the three cases are exhaustive

• TIMING: 3 minutes.
• PROMPT: find the gap before it is named.
• LISTEN FOR: “but it’s true anyway”.
• Friday’s lab (lab 02) uses this flaw name.

Checking every case

• Rule: a claim about finitely many cases is proved by checking every one of them
  • the check must reach every case, and must test the claim as stated
  • with a program, read the code to confirm both: True alone shows neither
• Read it: for every integer \(n\) from 1 to 10, \(n^3 - n\) is a multiple of 6
• Run it:

print(all((n**3 - n) % 6 == 0 for n in range(1, 11)))

True

• Infinite claim: the same line is only evidence for “every natural number \(n\)”, like the forty tests of \(n^2 + n + 41\)

• TIMING: 4 minutes.
• PROMPT: read range(1, 11) aloud. Does it reach 10? This is “reaches every case”.
• The infinite claim is in fact true; running cases cannot show it.
• BREAK here (~53 minutes of content).
• SOURCE: the rule is this major’s. MCS’s nearest support: “mechanically checkable proofs of enormous length or complexity” (§1.9, p. 17).

Proof by contradiction

Assuming the opposite

• Proof by contradiction of a claim \(C\)
  1. say that you are arguing by contradiction
  2. suppose \(C\) is false
  3. deduce something known to be false
  4. conclude that \(C\) is true
• Contradiction: a statement known to be false, such as \(1 = 0\), or a statement together with its negation
• Why it works: steps 2-3 prove “if \(C\) is false, then something false holds”
  • an implication with a false “then” part holds only when its “if” part is false
  • so “\(C\) is false” is false: \(C\) is true
• Fits: claims that something never happens or does not exist

• TIMING: 4 minutes.
• PROMPT: “if C is false, then 1 = 0” has been proved. Can C be false? Use the working meaning of an implication.
• MCS also calls this “indirect proof” (p. 16). Say “proof by contradiction”.

Rationals in lowest terms

• Lowest terms: for positive integers \(n\) and \(d\), \(n/d\) is in lowest terms when no integer greater than 1 divides both
  • \(6/4\) is not: 2 divides both; \(3/2\) is, and \(6/4 = 3/2\)
• Fact assumed (not proved here): every positive rational can be written in lowest terms
  • why plausible: cancel a common factor; the numerator shrinks each time, and a positive integer cannot shrink forever
• Why it matters: the proof that \(\sqrt{2}\) is irrational shows that 2 divides both \(n\) and \(d\)
  • for \(6/4\) that is no contradiction; for a fraction in lowest terms, it is

• TIMING: 3 minutes.
• MCS says “no common prime factors” (§2.1, p. 27): an equivalent condition. Week 3 proves the fact by well ordering.

The square root of 2

Theorem: \(\sqrt{2}\) is irrational.

• Why contradiction? Assuming \(\sqrt{2}\) is rational gives us a fraction to work with
• Plan: suppose \(\sqrt{2} = n/d\) in lowest terms; show that \(n\) and \(d\) are both even; that clashes with lowest terms
• Tools: the lemma (\(n\) even iff \(n^2\) even); lowest terms

• TIMING: 2 minutes.
• \(n\) is now the numerator, as in MCS; earlier it was a denominator.

Proof. We argue by contradiction. Suppose \(\sqrt{2}\) is rational.

1. \(\sqrt{2} > 0\), so \(\sqrt{2} = n/d\) for positive integers \(n\) and \(d\), in lowest terms. ← assumed rational; written in lowest terms
2. Squaring and multiplying by \(d^2\) gives \(n^2 = 2d^2\). Since \(d^2\) is an integer, \(n^2\) is even. ← compute
3. By the lemma, \(n\) is even: \(n = 2c\) for some integer \(c\). ← the lemma
4. Substitute \(n = 2c\): \(4c^2 = 2d^2\), hence \(d^2 = 2c^2\). As \(c^2\) is an integer, \(d^2\) is even. By the lemma, \(d\) is even. ← compute; use the lemma again
5. So 2 divides both \(n\) and \(d\), and \(n/d\) is not in lowest terms. This contradicts step 1. ← the contradiction

• So the supposition is false: \(\sqrt{2}\) is irrational. \(\qedmark\)
• Consequence: no rational \(q\) satisfies \(q^2 = 2\); otherwise \(|q| = \sqrt{2}\) would be rational

• TIMING: 6 minutes.
• PROMPT: TRY. Reveal step 3, then stop: how do we get “\(d\) is even”? One minute, then step 4.
• LISTEN FOR: “\(n^2\) even, so \(n\) even” asserted without the lemma.
• Steps 3-4 use the lemma’s backward direction; step 1 the lowest-terms fact.

Mathematical numbers and computer numbers

Maths	In Python	The difference
Integers \(\Int\)	int	Python integers can grow as memory allows; many languages use fixed-width integers that can overflow
Real numbers \(\Real\)	float	A finite-precision float stores only certain values, not an arbitrary real number

• A number is not its representation. Most real numbers cannot be stored as floats.
• In particular, no float represents \(\sqrt{2}\) exactly.

• TIMING: 2 minutes. Briefly contrast Python’s arbitrary-precision int with fixed-width machine integers (e.g. 32-bit); neither int type includes fractions.
• Most everyday Python floats use binary64. Exclude infinity and NaN when calling float values rational. No excursion into the IEEE standard or numerical analysis.

Floats and the square root of 2

• Stored value: every float except inf and nan is \(m \cdot 2^e\) for integers \(m\) and \(e\) (IEEE Standard for Floating-Point Arithmetic, n.d.), so it is rational
  • e.g. \(0.75 = 3 \cdot 2^{-2}\)
  • Fraction(x) is that exact value
• Exact square: by the theorem, the stored value never squares to exactly 2 as a real number
• Rounded square: x * x rounds the mathematical product to a float. That result may be 2.0
• ==: compares stored numeric values without a tolerance

• TIMING: 3 minutes. Back to the opening commitment.
• Read \(m \cdot 2^e\) as “m times 2 to the e”; \(e\) may be negative.

• Predict: will x * x == 2 and Fraction(x) ** 2 == 2 give the same answer?

import math
from fractions import Fraction

x = math.sqrt(2)
print(x * x == 2)  # rounded product, compared with 2
print(Fraction(x) ** 2 == 2)  # exact rational arithmetic

False
False

• Fraction(x) is the exact rational value the float stores.

r = math.sqrt(11)
print(r * r == 11)  # rounded product, compared with 11
print(Fraction(r) ** 2 == 11)  # exact

True
False

• For 11, rounding lands on 11.0; for 2 it misses 2.0
  • no theorem decides this: rounding is a property of float arithmetic
• What the theorem predicts: the exact line for 2 is False for every float
• For 11: the exact line is False too, but that rests on a known fact not proved here: \(\sqrt{11}\) is irrational
  • this proof does not cover it: it needs a lemma about multiples of 11, not our lemma about 2
• == on floats: compares stored values; it does not reverse rounding

• TIMING: 2 minutes.
• Outputs assume IEEE 754 binary64 (correctly rounded sqrt and ×), as on every common platform; Python doesn’t guarantee binary64.
• MCS Problem 1.12, p. 24, asks how far the root-2 proof generalises.
• IF ASKED: “11 divides n^2, so 11 divides n” needs prime factorisation, not two parity cases. Don’t prove it here.

• No finite float represents \(\sqrt{2}\) exactly. Rounded arithmetic may nevertheless produce 2.0.
• Proof versus testing: the theorem rules out an exact rational square of 2 for every rational input
• Engineering: choose the comparison from the specification
  • approximate equality wanted: compare within a tolerance chosen for the scale and the accuracy required
  • equality of stored values wanted: == compares stored results exactly; it does not undo earlier rounding

• TIMING: 1 minute.
• Emphasise the distinction between the exact stored number and rounded arithmetic.

Good proofs in practice

The review checklist

• Valid: what a reviewer must confirm
  • right claim: it proves the claim as stated, or an equivalent form such as its contrapositive, and not the converse
  • every step justified: by a definition, an allowed fact, a proved result or an earlier line, never by the claim itself
  • cases cover everything: the proof says why
• Clear: this major’s conventions while you learn
  • method named when it helps the reader
  • use of hypotheses clear from the argument
  • conclusion stated at the end
  • written in sentences: explain why the equations follow
• an unused hypothesis is a warning sign, not by itself a flaw

• TIMING: 3 minutes.
• Friday’s lab uses this checklist, worded this way.
• EMPHASIS: a proof can break a “clear” convention and still be valid; a proof that fails a “valid” check proves nothing.
• An unused hypothesis often means the converse or a different claim was proved: bogus proof 2 is an example.
• SOURCE: “A proof is an essay, not a calculation”, MCS §1.9, p. 18.

Spotting a bogus proof

Three “proofs” of true claims. For each: which check fails?

1. Claim: the sum of two odd integers is even. “Proof”: let \(m\) and \(n\) be odd. Odd plus odd is even, so \(m + n\) is even. \(\qedmark\)
2. Claim: for every integer \(n\), if \(n^2\) is even, then \(n\) is even. “Proof”: let \(n\) be even, \(n = 2k\). Then \(n^2 = 2(2k^2)\) is even. \(\qedmark\)
3. Claim: \(n^3 - n\) is even for every integer \(n\). “Proof” (by cases). Case \(n\) even: \(n = 2k\), so \(n^3 - n = 2(4k^3 - k)\), which is even. \(\qedmark\)

• TIMING: 4 minutes: two alone, two in pairs.
• LISTEN FOR: “the answer is right, so the proof is fine”.

	Flaw	Check that fails
1	circular reasoning: “odd plus odd is even” is the claim, used as a step	every step justified
2	converse assumed: it proves “\(n\) even implies \(n^2\) even”	right claim (clue: “\(n^2\) even” is never used)
3	a missing case: \(n\) odd is never treated	cases cover everything

• Circular reasoning (a named flaw): a step assumes the claim being proved
• all three claims are true: a true conclusion does not make a proof valid
• “clearly” and “obviously” mark the step to check first

• TIMING: 3 minutes.
• Repairs: 1 needs the definitions (this morning’s model proof); 2 is the backward direction of the lemma; 3 needs case 2, \(n = 2k + 1\).
• Friday’s lab (lab 02) uses all three flaw names.

Consolidation

Your turn: one contradiction proof

Prove: there is no largest natural number.

• say which method you use
• say what you suppose
• derive a contradiction and identify it
• swap with a neighbour and review against the checklist

Proof. We argue by contradiction. Suppose there is a largest natural number \(m\). Then \(m + 1\) is a natural number, since adding 1 to a natural number gives a natural number, and \(m + 1 > m\), which contradicts \(m\) being the largest. So there is no largest natural number. \(\qedmark\)

• TIMING: 6 minutes: four writing, two swapping and checking.
• LISTEN FOR: a supposition written but never contradicted; “infinity” used as a number.
• WHY \(m + 1 \in \Nat\): \(m\) is a natural number, and adding 1 to a natural number gives a natural number.
• WHY it contradicts: “largest” means \(m \geq k\) for every natural \(k\); take \(k = m + 1\), and \(m + 1 > m\) since \(1 > 0\).

Contradiction or contrapositive?

• Contrapositive: to prove \(P \IMPLIES Q\), assume \(\NOT(Q)\) and derive \(\NOT(P)\)
• Contradiction: assume the claim is false and derive an impossibility
• Either method may work. If \(P\) is used only to reach the final contradiction, the contrapositive is usually shorter.

• TIMING: 1 minute. Brief spoken comparison, not a separate exercise.
• EXAMPLE, if asked: the root-r theorem by contradiction: suppose \(r\) irrational and \(\sqrt{r} = m/n\); then \(r = m^2/n^2\) is rational, contradicting the supposition. Where was “\(r\) irrational” used? Only at the end: the contrapositive version is cleaner.
• Friday’s truth table checks that NOT(P IMPLIES Q) is P AND NOT(Q).

Choosing a method

Method	Start by	Tends to fit
direct	assuming \(P\)	unpacking \(P\) leads towards \(Q\)
contrapositive	assuming \(\NOT(Q)\)	\(\NOT(Q)\) gives more to unpack than \(P\)
both directions	proving each implication	an “if and only if”
cases	splitting the possibilities	the objects split naturally: even or odd, sign
contradiction	supposing the claim false	“there is no …”, “never”

• TIMING: 1 minute. This is the synthesis: point at today’s example for each row.

For an integer \(n\), which method would you try first, and why?

1. \(n\) is odd iff \(n + 1\) is even
2. \(n^2 + 3n\) is even

• (a) both directions: it is an “iff”
• (b) cases, \(n\) even or odd; or directly, as \((n^2 + n) + 2n\), reusing “\(n^2 + n\) is even”

• TIMING: 3 minutes. Commit first, then discuss.
• More than one method can work: (b) has two good answers.

Exit question

“For every integer \(n\): if \(n^2\) is odd, then \(n\) is odd.”

• Which method would you use?
• Write its first line.

• e.g. “We prove the contrapositive: if \(n\) is not odd, then \(n^2\) is not odd”; by the even-or-odd fact, that is “if \(n\) is even, then \(n^2\) is even”

• TIMING: 4 minutes. On paper or a quick poll. Record the share choosing a workable method and the share able to write the first line, for the week 1 pace review. Not marked.
• Workable: contrapositive (the lemma’s forward direction) or contradiction. The natural direct attempt (\(n^2 = 2k + 1\), so \(n\) = ?) stalls.

Conclusion

Learning outcomes

You should now be able to:

• state the converse and contrapositive of an implication; identify the equivalent statement
• negate a simple statement correctly
• prove a claim by contrapositive
• prove an “if and only if” as two implications
• split a proof into cases that cover every possibility
• prove a claim by contradiction, such as \(\sqrt{2}\) being irrational
• choose a proof method; check for missing cases and unjustified steps

Recommended reading

• MCS §1.5.2 to §1.9 (pp. 14–19): the contrapositive, if and only if, proof by cases, proof by contradiction and good proofs in practice
  • the book is free from MIT OpenCourseWare
• Read actively: before each proof, cover it and try the first two lines yourself

References

IEEE Standard for Floating-Point Arithmetic. n.d. IEEE. https://doi.org/10.1109/ieeestd.2019.8766229.

Questions?

eoin@eoin.ai · eoin.p.o.brien@ul.ie

• Leave this up while the room empties: the addresses stay on the projector for anyone who wanted to ask and did not want to ask in front of everyone.