Logic, Sets, Definitions & Proofs
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.
- Read and negate statements with $\forall$ and $\exists$.
- State the converse and contrapositive and distinguish necessary from sufficient.
- Choose a proof method: direct, contrapositive, contradiction, induction.
- Prove set equality and write a clean proof from definitions.
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.
How to learn this unit
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.
What a complete proof contains
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.
- Start cleanly. "Let $x\in A$ be arbitrary" for a set inclusion, or "Assume $P$" for an implication.
- Unpack definitions. Replace "even," "one-to-one," "subset," or "divides" by the exact definition before doing algebra.
- Track direction. In a biconditional, label the forward and reverse directions. In a contrapositive proof, state the contrapositive first.
- Close the loop. End by explicitly naming the conclusion: "therefore $x\in B$," "therefore $n$ is even," or "therefore $f$ is one-to-one."
Statements and quantifiers
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.
Negation
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$."
Implication, converse, contrapositive
$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 |
The proof methods
Four tools cover almost everything in MAT137.
- Direct. Assume $P$, deduce $Q$.
- Contrapositive. To prove $P\Rightarrow Q$, prove $\neg Q\Rightarrow\neg P$.
- Contradiction. Assume the statement is false, derive an impossibility.
- Induction. For statements about all $n\in\mathbb{N}$.
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.
Definitions and biconditionals
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.
Induction
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}$.
Sets and notation
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.
Practice
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\}$?
Answer
Let $f$ have domain $D$. Write the formal definition of "$f$ is one-to-one," then write its negation.
Answer
Negate: "If a student in this class has a brother, then they also have a sister."
Answer
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.
Answer
Prove that $f(x)=3x+2$, with domain $\mathbb{R}$, is one-to-one.
Solution
Prove that $f(x)=x^2$, with domain $\mathbb{R}$, is not one-to-one.
Solution
Prove: if $f$ is strictly increasing on $D$, then $f$ is one-to-one on $D$.
Solution
$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$.
Answer
Expanded topic checklist
Course coverage. This unit is part of the complete MAT137 topic map. It should cover the following items before you move on:
- Language. Translate English claims into quantified statements and identify the variables, domains, hypotheses, and conclusions.
- Proof forms. Use direct proof, contrapositive, contradiction, cases, and induction as separate tools rather than interchangeable rituals.
- Sets. Work fluently with subsets, unions, intersections, complements, Cartesian products, and set-builder notation.
- Induction. Treat induction as a proof about all natural numbers: base case, induction hypothesis, induction step, and conclusion.
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.
Deep practice extensions
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$."
Guide
Prove by induction that $1+3+5+\cdots+(2n-1)=n^2$ for every $n\ge1$.
Guide
Prove $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ by element chasing.
Guide
Disprove the statement: if $A\cup B=A\cup C$, then $B=C$.