Mathematics Admissions Test (MAT) Logic, Proof and Mathematical Reasoning Syllabus

How is an even integer and an odd integer written algebraically for use in proofs?

An even integer is $2k$ and an odd integer is $2k+1$ for some integer $k$. These representations let you manipulate parity directly.

Outline a direct proof that the sum of two odd integers is even.

Let the odds be $2a+1$ and $2b+1$. Their sum is $2a+1+2b+1 = 2(a+b+1)$, which is $2 \times$ an integer, hence even.

Outline a direct proof that the product of two consecutive integers is even.

Take $n(n+1)$. One of $n,\ n+1$ is even (consecutive integers have opposite parity), so the product has a factor of $2$ and is even.

What is the general structure of a proof by contradiction?

Assume the statement is FALSE (assume $\lnot P$). Derive a logical contradiction (something false, like $1 = 0$). Conclude the assumption was wrong, so $P$ is true.

To prove $P \implies Q$ by contradiction, what do you assume at the start?

You assume $P$ is true AND $Q$ is false (i.e. $P \land \lnot Q$), then derive a contradiction.

Sketch the proof by contradiction that $\sqrt{2}$ is irrational.

Assume $\sqrt{2} = \frac{a}{b}$ in lowest terms. Then $a^{2} = 2b^{2}$, so $a$ is even, $a = 2c$, giving $b^{2} = 2c^{2}$, so $b$ is also even. Then $a,b$ share factor $2$, contradicting "lowest terms." Hence $\sqrt{2}$ is irrational.

Sketch Euclid's proof by contradiction that there are infinitely many primes.

Assume finitely many primes $p_{1},\dots,p_{n}$. Form $N = p_{1}p_{2}\cdots p_{n} + 1$. $N$ leaves remainder $1$ on division by each $p_{i}$, so it has a prime factor not in the list — a contradiction. Hence infinitely many primes.

How does proof by contradiction differ from proof by contrapositive?

Contrapositive proves $P \implies Q$ by directly proving $\lnot Q \implies \lnot P$. Contradiction assumes $P \land \lnot Q$ and seeks any contradiction. Contrapositive is a special, cleaner case when the contradiction is exactly $\lnot P$.

What is proof by exhaustion?

A method that splits the problem into a finite number of cases and verifies the statement in each case. It works only when the cases are finite and collectively cover all possibilities.

Use proof by exhaustion to show $n^{2} \equiv 0$ or $1 \pmod 4$ for every integer $n$.

Every integer is even or odd. If $n = 2k$, $n^{2} = 4k^{2} \equiv 0$. If $n = 2k+1$, $n^{2} = 4k^{2}+4k+1 \equiv 1$. The two cases exhaust all integers, so $n^{2} \equiv 0$ or $1 \pmod 4$.

What is the basic idea of proof by mathematical induction?

To prove $P(n)$ for all integers $n \geq n_{0}$: prove the base case $P(n_{0})$, then prove the inductive step that $P(k) \implies P(k+1)$. Together these give $P(n)$ for all $n \geq n_{0}$.

What two components must every induction proof contain?

A base case (verify the statement for the smallest value, often $n=1$) and an inductive step (assume $P(k)$, the inductive hypothesis, and prove $P(k+1)$).

State the formula for $\sum_{r=1}^{n} r$ that is commonly proved by induction.

$\displaystyle \sum_{r=1}^{n} r = \frac{n(n+1)}{2}$.

In an induction proof, what is the "inductive hypothesis"?

It is the assumption that the statement $P(k)$ holds for some particular integer $k$; you use it to deduce $P(k+1)$.

Why is the base case essential in induction (what goes wrong without it)?

Without a verified base case the inductive step only chains assumptions together with no starting truth, so the whole argument is unsupported — you could "prove" false statements like $P(k)\implies P(k+1)$ for a statement that is never actually true.

What is the formula $\sum_{r=1}^{n} r^{2}$ equal to?

$\displaystyle \sum_{r=1}^{n} r^{2} = \frac{n(n+1)(2n+1)}{6}$.

When given an unfamiliar definition in a MAT problem, what should you do first?

Read it precisely and test it on small/simple concrete cases to understand exactly what it does, rather than assuming it matches a familiar concept with a similar name.

If a problem defines an operation $a * b = a + b - ab$, how do you evaluate $2 * 3$?

Substitute directly into the definition: $2 * 3 = 2 + 3 - (2)(3) = 5 - 6 = -1$.

A problem defines $f$ to be "self-inverse" if $f(f(x)) = x$ for all $x$. How do you check whether a given $f$ satisfies this?

Compute the composition $f(f(x))$ by substituting $f(x)$ into $f$, simplify, and verify it equals $x$ for all $x$ in the domain.

When working with an unfamiliar definition, why is it useful to check edge/boundary cases?

Edge cases (e.g. $0$, $1$, negatives, equality boundaries) often reveal how the definition behaves, expose hidden constraints, and prevent false assumptions that the definition behaves "as expected."

In a MAT multiple-choice question, what is the elimination strategy?

Rule out answer options that are impossible — via counterexamples, parity/sign checks, limiting/boundary behaviour, or dimensional reasoning — narrowing to the correct choice without full computation.

How can substituting a convenient specific value help eliminate multiple-choice options?

If a stated identity/expression must hold for all values, plug in an easy value (e.g. $x=0$ or $x=1$); any option that gives the wrong result there can be eliminated immediately.

What is estimation used for in MAT-style problems?

To approximate a quantity's size or sign quickly so you can select or eliminate answer choices without exact calculation — e.g. bounding a value between two known numbers.

How can checking the sign or magnitude of an expression help eliminate options?

If reasoning shows the answer must be, say, positive and greater than $10$, any negative or small option is eliminated, often leaving a unique choice.

How does considering limiting behaviour (e.g. as $x \to 0$ or $x \to \infty$) help on multiple-choice questions?

Comparing how each candidate expression behaves in a limit against the required behaviour of the true answer eliminates options that grow, decay, or sign-change incorrectly.

In MAT long-answer questions, why is showing clear working important?

Marks are awarded for method and logical steps, not just the final answer; clear working lets the examiner follow and credit your reasoning even if the final answer has a slip.

What is a good structure for a MAT long-answer proof or solution?

State what you are proving/finding, set up notation and assumptions, proceed in clear logical steps with justification, and finish with a concluding statement that explicitly answers the question.

In a multi-part long-answer MAT question, how should later parts often be approached?

Later parts usually build on earlier ones — reuse results, definitions, or methods established earlier (the question is scaffolded), rather than starting each part from scratch.

What should a proof's final line do, and why does it matter for marks?

It should clearly state the conclusion (e.g. "hence the result follows" / restate what was proved), signalling the argument is complete; a missing or unjustified conclusion can lose the final method/accuracy marks.