Logic, Sets & Proof
Analysis begins with airtight reasoning. This unit is the proof language — quantifiers, implications, induction, and the inequalities of absolute value — on which every later theorem about the real numbers rests. Do not rush it: an ε–δ proof is nothing but quantifiers handled correctly.
- Read and negate statements with $\forall$ and $\exists$, including nested ones.
- State the converse and contrapositive and use contradiction correctly.
- Prove statements by induction and strong induction.
- Prove and use the triangle inequality and its reverse form.
In analysis "obvious" is not allowed. Statements must be proved from axioms, because intuition about infinity and limits is famously unreliable — exactly where 18th-century calculus kept going wrong.
This is the logic that runs computers and the basis of proof assistants like Lean and Coq, now used to verify major theorems and safety-critical software line by line.
The 19th-century drive for rigour came precisely because calculus had been caught being sloppy. Boole, Cantor, Russell, and Gödel turned reasoning itself into an object of study; Gödel's 1931 theorems showed every consistent, effectively axiomatized system rich enough for arithmetic has true statements it cannot prove.
Quantifiers and negation
$\forall x\in S,\ P(x)$ means $P(x)$ holds for every $x$ in $S$. $\exists x\in S,\ P(x)$ means $P(x)$ holds for at least one $x$ in $S$.
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)$. For nested quantifiers, work from the outside in.
Order matters. $\forall x\,\exists y$ and $\exists y\,\forall x$ usually mean different things: "everyone has a mother" is not "someone is everyone's mother." Mastering this is the whole game in ε–δ arguments, where the statement has three alternating quantifiers.
Negate: "for every $\varepsilon>0$ there is $n\in\mathbb{N}$ with $\tfrac1n<\varepsilon$."
Implication, converse, contrapositive
$P\Rightarrow Q$ is false only when $P$ is true and $Q$ is false. Its contrapositive is $\neg Q\Rightarrow\neg P$ (always equivalent to the original); its converse is $Q\Rightarrow P$ (a different claim).
Proof methods
Direct (assume $P$, deduce $Q$), contrapositive (prove $\neg Q\Rightarrow\neg P$ instead), contradiction (assume the statement fails, derive an impossibility), and induction (for statements about all $n\in\mathbb{N}$).
Claim: if $n^2$ is even then $n$ is even.
Claim: $\sqrt2$ is irrational.
Induction and strong 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}$. Strong induction lets the step assume $P(1),\dots,P(k)$ all at once; the two principles are equivalent.
$1+2+\cdots+n=\dfrac{n(n+1)}{2}$.
Every integer $n\ge2$ is a product of primes.
Absolute value — the workhorse of analysis
Nearly every estimate in this course is a chain of absolute-value inequalities. Learn these two cold.
For all real $a,b$: $|a+b|\le|a|+|b|$, and (reverse form) $\big||a|-|b|\big|\le|a-b|$.
• Proving the converse by accident — check the direction before writing.
• One counterexample kills a $\forall$ statement; one example proves an
$\exists$ statement — never mix these up.
• In a contradiction proof, negate the whole statement, quantifiers
included.
• In induction, never skip the base case, and make sure the step actually uses
the hypothesis.
Practice
Original problems written for this guide in the style of Spivak's exercises. Write a full solution before opening the answer.
Prove: if $x^2$ is irrational then $x$ is irrational.
Solution
Negate: "$\exists M\ \forall n,\ a_n\le M$." What does the negation say about the sequence?
Answer
Prove $n<2^n$ for all $n\in\mathbb{N}$.
Solution
Prove $(1+x)^n\ge1+nx$ for every $x\ge-1$ and $n\in\mathbb{N}$.
Solution
Prove $|a+b+c|\le|a|+|b|+|c|$ for all real $a,b,c$.
Solution
Prove that if $r$ is rational and $x$ is irrational, then $r+x$ is irrational.
Solution
Which is true over $\mathbb{R}$: $\forall x\,\exists y\,(y>x)$ or $\exists y\,\forall x\,(y>x)$? Prove one and disprove the other.
Answer
$S_n$ is a statement for each $n\ge1$. Which sets of facts guarantee $S_n$ for all $n\ge1$? (a) $S_5$ and $S_k\Rightarrow S_{k+1}$ for all $k$. (b) $S_1$ and $S_k\Rightarrow S_{k+1}$ for all $k$. (c) $S_1$ and $S_{k+1}\Rightarrow S_k$ for all $k$.
Answer
Expanded topic checklist
Course coverage. This unit is part of the complete MAT158H1 topic map. It should cover the following items before you move on:
- Logic. Handle quantifiers, negations, implications, and proof by contradiction cleanly.
- Sets and functions. Use images, preimages, injective/surjective language, and set operations.
- Proof discipline. Separate assumptions, claims, and conclusions so later analysis proofs are readable.
- Counterexamples. Disprove false universal statements with minimal examples.
Use the current UofT MAT158H1 calendar topics as the coverage spine, and pair lecture notes with a Spivak-style proof-calculus text for extra reading. The exact assigned textbook should still be checked against the instructor syllabus.
Analysis proofs are mostly careful quantifier management: choose epsilon, produce delta or N, then verify every implication in order.
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.
Explain why "for every $\epsilon$ there exists $N$" is different from "there exists $N$ for every $\epsilon$."
Guide
Prove: if $n^2$ is even, then $n$ is even.
Guide
Show $f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$.
Guide
Disprove: every injective function is surjective.