Unit 01 · Analysis 1A

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.

By the end you can

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.

Why it matters & where it comes from

Why it exists

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.

In the real world

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.

Story & open questions

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

Definition Quantifiers

$\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$.

Rule Negation

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.

Example Negating an analysis statement

Negate: "for every $\varepsilon>0$ there is $n\in\mathbb{N}$ with $\tfrac1n<\varepsilon$."

Flip $\forall\varepsilon$ to $\exists\varepsilon$, flip $\exists n$ to $\forall n$, negate the inequality:

"there exists $\varepsilon>0$ such that for every $n\in\mathbb{N}$, $\tfrac1n\ge\varepsilon$."

Implication, converse, contrapositive

Definition

$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).

Why is a false hypothesis allowed? An implication only promises what happens when $P$ holds. If $P$ is false there is no broken promise, so $P\Rightarrow Q$ counts as true. This convention is what makes statements like "every element of the empty set is purple" true — and harmless.

Proof methods

The toolkit

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}$).

Example Contrapositive

Claim: if $n^2$ is even then $n$ is even.

Contrapositive: $n$ odd $\Rightarrow n^2$ odd. Write $n=2k+1$; then $n^2=2(2k^2+2k)+1$ is odd. ∎

Example Contradiction

Claim: $\sqrt2$ is irrational.

Suppose $\sqrt2=p/q$ in lowest terms. Then $p^2=2q^2$, so $p^2$ is even, so $p$ is even (previous example); write $p=2r$.

Then $q^2=2r^2$ makes $q$ even too — contradicting "lowest terms." So no such fraction exists. ∎

Induction and strong induction

Principle 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.

Example

$1+2+\cdots+n=\dfrac{n(n+1)}{2}$.

Base: $n=1$ gives $1=\tfrac{1\cdot2}{2}$. ✓

Step: assuming it for $k$, add $k+1$: $\tfrac{k(k+1)}{2}+(k+1)=\tfrac{(k+1)(k+2)}{2}$. ✓

Example Strong induction

Every integer $n\ge2$ is a product of primes.

If $n$ is prime, done. Otherwise $n=ab$ with $2\le a,b<n$; by the strong hypothesis each of $a,b$ is a product of primes, so $n$ is too. ∎

Absolute value — the workhorse of analysis

Nearly every estimate in this course is a chain of absolute-value inequalities. Learn these two cold.

Theorem Triangle inequality

For all real $a,b$: $|a+b|\le|a|+|b|$, and (reverse form) $\big||a|-|b|\big|\le|a-b|$.

Proof

From $-|a|\le a\le|a|$ and $-|b|\le b\le|b|$, add: $-(|a|+|b|)\le a+b\le|a|+|b|$, which is exactly $|a+b|\le|a|+|b|$.

Reverse form: $|a|=|(a-b)+b|\le|a-b|+|b|$ gives $|a|-|b|\le|a-b|$; swapping $a,b$ gives the other direction. ∎

How it gets used The classic move: to show $|f(x)-L|$ is small, insert a helpful middle term, $|f(x)-L|\le|f(x)-m|+|m-L|$, and make each piece less than $\varepsilon/2$. You will use this "add and subtract" trick in nearly every unit.

Common pitfalls

• 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.

Practice 1 · Contrapositive

Prove: if $x^2$ is irrational then $x$ is irrational.

Solution

Contrapositive: if $x$ is rational, $x=p/q$, then $x^2=p^2/q^2$ is rational. ∎

Practice 2 · Negation

Negate: "$\exists M\ \forall n,\ a_n\le M$." What does the negation say about the sequence?

Answer

"$\forall M\ \exists n,\ a_n>M$" — the sequence is unbounded above.

Practice 3 · Induction

Prove $n<2^n$ for all $n\in\mathbb{N}$.

Solution

Base: $1<2$. Step: if $k<2^k$ then $k+1<2^k+1\le2^k+2^k=2^{k+1}$. ∎

Practice 4 · Bernoulli's inequality

Prove $(1+x)^n\ge1+nx$ for every $x\ge-1$ and $n\in\mathbb{N}$.

Solution

Base $n=1$ is equality. Step: since $1+x\ge0$, $(1+x)^{k+1}\ge(1+kx)(1+x)=1+(k+1)x+kx^2\ge1+(k+1)x$. ∎

Practice 5 · Triangle inequality

Prove $|a+b+c|\le|a|+|b|+|c|$ for all real $a,b,c$.

Solution

Apply the triangle inequality twice: $|a+b+c|\le|a+b|+|c|\le|a|+|b|+|c|$.

Practice 6 · Irrational sums

Prove that if $r$ is rational and $x$ is irrational, then $r+x$ is irrational.

Solution

If $r+x=s$ were rational, then $x=s-r$ would be a difference of rationals, hence rational — a contradiction.

Practice 7 · Quantifier order

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

The first: given $x$, take $y=x+1$. The second is false: any candidate $y$ fails at $x=y$, since $y>y$ is impossible.

Practice 8 · Broken induction

$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

Only (b). (a) proves the claim only from $n=5$ on; (c) propagates downward from $S_1$ and says nothing above $1$.

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.

Textbook/source alignment

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.

Core theorem map

Analysis proofs are mostly careful quantifier management: choose epsilon, produce delta or N, then verify every implication in order.

Study routine. Rewrite each definition in words, symbols, and a negated form; all three versions appear in tests.

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.

Extension 1 · Quantifier order

Explain why "for every $\epsilon$ there exists $N$" is different from "there exists $N$ for every $\epsilon$."

Guide

The first lets $N$ depend on the tolerance; the second asks one $N$ to work for all tolerances, usually impossible for convergence definitions.

Extension 2 · Contrapositive

Prove: if $n^2$ is even, then $n$ is even.

Guide

Use contrapositive. If $n$ is odd, $n=2k+1$, so $n^2=4k^2+4k+1$ is odd.

Extension 3 · Preimage

Show $f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$.

Guide

An element $x$ is in the left side iff $f(x)\in A\cap B$, iff $f(x)\in A$ and $f(x)\in B$, iff $x$ is in both preimages.

Extension 4 · Counterexample

Disprove: every injective function is surjective.

Guide

The function $f:\mathbb{N}\to\mathbb{N}$ by $f(n)=n+1$ is injective but misses $1$.

← IndexAll chapters Unit 02 →Real numbers & least upper bounds