Before any calculus, MAT137 teaches the language: how to read a precise statement, how quantifiers work, and how to prove things. This is the foundation every later unit is written in — invest here.
Mathematics is the one field that claims certainty. A proof is how a result becomes true forever — not just "true in every case we checked." Precise language and quantifiers exist so a statement cannot be quietly reinterpreted when that would be convenient.
This is the logic that runs computers: Boolean algebra in every circuit, the conditions in every program, database queries, type systems, and the formal verification that proves aircraft and chip designs correct. Theorem provers and AI reasoning run on it too.
Boole turned logic into algebra in 1854; Cantor built a theory of infinite sets so radical that Hilbert called it "a paradise." Then Russell found a paradox — the set of all sets that do not contain themselves — that broke it, and in 1931 Gödel proved that every consistent, effectively axiomatized formal system rich enough to express arithmetic contains statements it can neither prove nor disprove. The field's biggest open question, P vs NP — is finding an answer as easy as checking one? — carries a one-million-dollar prize.
The goal is not to memorize symbols. The goal is to translate between English, formal logic, and proof structure without changing the meaning. For each new statement, do three passes: identify the quantifiers, identify the main implication or equation, then decide what a proof would need to start with and what it must end by showing.
A proof should make the logical source of every line visible. MAT137 proofs do not need to be long, but they do need to say what is arbitrary, what is assumed, what definition is being used, and where the conclusion has been reached.
A statement is a sentence that is either true or false. Most interesting statements use quantifiers: "for all" ($\forall$) and "there exists" ($\exists$).
$\forall x\in S,\ P(x)$ means $P(x)$ is true for every $x$ in $S$. $\exists x\in S,\ P(x)$ means $P(x)$ is true for at least one $x$ in $S$.
Order matters. $\forall x\,\exists y$ and $\exists y\,\forall x$ usually say different things. "For every $x$ there is a $y$ with $y>x$" is true for $\mathbb{R}$; "there is a $y$ greater than every $x$" is false.
To negate a quantified statement, flip each quantifier and negate the inside.
$\neg(\forall x,\,P(x))\equiv \exists x,\,\neg P(x)$ and $\neg(\exists x,\,P(x))\equiv \forall x,\,\neg P(x).$
Negate: "for every $\varepsilon>0$ there exists $n\in\mathbb{N}$ with $\tfrac1n<\varepsilon$."
$P\Rightarrow Q$ ("if $P$ then $Q$") is false only when $P$ is true and $Q$ is false. Its contrapositive is $\neg Q\Rightarrow\neg P$; its converse is $Q\Rightarrow P$.
An implication and its contrapositive are always logically equivalent — that is what makes proof by contrapositive valid. The converse is a different claim and may be false. In $P\Rightarrow Q$, $P$ is sufficient for $Q$, while $Q$ is necessary for $P$.
| $P$ | $Q$ | $P\Rightarrow Q$ | $\neg Q\Rightarrow\neg P$ |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
Four tools cover almost everything in MAT137.
Start from the logical shape of the claim, then choose the route that gives you useful information to work with.
Claim: for every integer $n$, if $n^2$ is even then $n$ is even.
Claim: $\sqrt2$ is irrational.
A definition usually has two directions. Saying "$n$ is even if and only if there exists $k\in\mathbb Z$ such that $n=2k$" means both implications hold. You may unfold a definition during a proof, but you may not replace a theorem by an informal picture of what it ought to mean.
$P\Longleftrightarrow Q$ means $(P\Rightarrow Q)\land(Q\Rightarrow P)$. To prove it, clearly prove both directions.
For integers $m,n$, if $m$ and $n$ are even, then $m+n$ is even.
If $P(1)$ holds, and $P(k)\Rightarrow P(k+1)$ for every $k\in\mathbb N$, then $P(n)$ holds for all $n\in\mathbb{N}$. If the claim starts at another integer $n_0$, use $P(n_0)$ as the base case.
Prove $1+2+\cdots+n=\dfrac{n(n+1)}{2}$.
Set-builder $\{x\in S: P(x)\}$, union $\cup$, intersection $\cap$, subset $\subseteq$, and the number systems $\mathbb{N}\subset\mathbb{Z}\subset \mathbb{Q}\subset\mathbb{R}$. Absolute value $|x|$ and the triangle inequality $|a+b|\le|a|+|b|$ appear constantly from Unit 2 on.
To prove $A=B$, prove both inclusions: take an arbitrary $x\in A$ and show $x\in B$; then take an arbitrary $x\in B$ and show $x\in A$.
For complements relative to a universe $U$, $(A\cup B)^c=A^c\cap B^c$.
• Proving the converse by accident. Check direction.
• Forgetting that a single counterexample kills a $\forall$ statement, while one
example proves an $\exists$ statement.
• Assuming the conclusion somewhere in the proof; every step must follow from
hypotheses, definitions, or earlier results.
• In induction, skipping the base case or not actually using the hypothesis in
the step.
Problems adapted from the MAT137 question bank by Alfonso Gracia-Saz, used under CC BY-SA 4.0. Write full solutions before opening the answer.
Write the set $E$ of even integers in set-builder notation. Is it $\{n\in\mathbb{Z}:\forall a\in\mathbb{Z},\,n=2a\}$ or $\{n\in\mathbb{Z}:\exists a\in\mathbb{Z}\text{ s.t. }n=2a\}$?
Let $f$ have domain $D$. Write the formal definition of "$f$ is one-to-one," then write its negation.
Negate: "If a student in this class has a brother, then they also have a sister."
Which are equivalent to "Every Canadian man likes hockey"? (a) If a man is Canadian, he likes hockey. (b) If a man likes hockey, he is Canadian. (c) If a man does not like hockey, he is not Canadian.
Prove that $f(x)=3x+2$, with domain $\mathbb{R}$, is one-to-one.
Prove that $f(x)=x^2$, with domain $\mathbb{R}$, is not one-to-one.
Prove: if $f$ is strictly increasing on $D$, then $f$ is one-to-one on $D$.
$S_n$ depends on an integer $n\ge1$. Which guarantee $S_n$ for all $n\ge1$? (a) $S_3$ and $\forall n\ge1,\,S_n\Rightarrow S_{n+1}$. (b) $S_1$ and $\forall n\ge1,\,S_n\Rightarrow S_{n+1}$. (c) $S_1$ and $\forall n\ge1,\,S_{n+1}\Rightarrow S_n$.
Course coverage. This unit is part of the complete MAT137 topic map. It should cover the following items before you move on:
Use the Alfonso Gracia-Saz MAT137 materials as the primary local spine, with the current UofT single-variable calculus topic split as the completeness check. The added items are original study prompts, not copied textbook exercises.
The proof spine is: parse the claim, choose the proof form, state the assumptions explicitly, and close the quantifiers in the same order they were opened.
Use these after the main practice set. They are designed to force definition-level reasoning, theorem selection, and mixed application rather than routine calculation only.
Negate: "For every $\epsilon>0$ there is $\delta>0$ such that if $0<|x-a|<\delta$, then $|f(x)-L|<\epsilon$."
Prove by induction that $1+3+5+\cdots+(2n-1)=n^2$ for every $n\ge1$.
Prove $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ by element chasing.
Disprove the statement: if $A\cup B=A\cup C$, then $B=C$.