Sets, Logic, and Functions

Analysis proves every claim from a small list of assumptions about the real numbers. Before the numbers comes the language the proofs are written in: sets, the logical connectives that combine statements about them, and functions that move between them. A sloppy grip on for all versus there exists, or on what it means for two sets to have the same size, produces proofs that look right and are wrong.

Statements, quantifiers, and proof grammar

A statement is a sentence that is either true or false. Analysis strings statements together with the connectives and, or, not, and implies, and quantifies them over sets. Two quantifiers appear in nearly every definition:

• Universal, written $\forall$: $\forall x\in S,P(x)$ asserts $P(x)$ holds for every $x$ in $S$.
• Existential, written $\exists$: $\exists x\in S,P(x)$ asserts $P(x)$ holds for at least one $x$ in $S$.

Order matters. The statement $\forall x\exists yP(x,y)$ lets $y$ depend on $x$; the statement $\exists y\forall xP(x,y)$ demands a single $y$ that works for all $x$ at once. The gap between these two — a $y$ that may vary with $x$ versus one $y$ serving every $x$ at once — is the same gap between pointwise and uniform properties that runs through the whole subject (continuity versus uniform continuity, pointwise versus uniform convergence), so read quantifier order carefully from the start.

Negation flips quantifiers and passes to the inside:

To disprove every $x$ has property $P$, exhibit one $x$ without it; that single $x$ is a counterexample. The negation of an implication $P⟹Q$ is $P\text{ and }\neg Q$: a case where the hypothesis holds but the conclusion fails.

Three proof patterns

Most proofs in these notes are one of three shapes.

• Direct proof. To show $P⟹Q$, assume $P$ and derive $Q$ by valid steps.
• Contrapositive. The implication $P⟹Q$ is logically identical to $\neg Q⟹\neg P$. Proving the contrapositive proves the original. This is often easier: to show if $xy>0$ then $x,y$ have the same sign, assume they have opposite signs and derive $xy\le 0$.
• Contradiction. To show $P$, assume $\neg P$ and derive an impossibility. The proof that $\sqrt{2}$ is not rational — assume $\sqrt{2}=m/n$ in lowest terms, deduce that $m$ and $n$ are both even — is the archetype; it appears in full in the proof that $\sqrt{2}$ exists in $\mathbb{R}$.

Sets and their operations

A set is an unordered collection of distinct objects, its elements. We write $x\in A$ for membership and $x\notin A$ for its negation. Sets are equal, $A=B$, when they have exactly the same elements, which in practice is proved by showing $A\subset B$ and $B\subset A$ — every element of each lies in the other. The set with no elements is the empty set $\varnothing$. The standard number systems are

with $\mathbb{N}\subset \mathbb{Z}\subset \mathbb{Q}\subset \mathbb{R}$. The three binary operations on sets are union, intersection, and difference.¹

Unions and intersections extend to arbitrary families. Given a set $A_{\lambda }$ for each $\lambda$ in an index set $I$,

The two operations trade places under complement, De Morgan's laws, stated here in their general form:¹

The proof is the model for every equality of sets argument: take an $x$ in the left side, show it lies in the right; then reverse. Take $x\in A\setminus (B\cup C)$. Then $x\in A$ and $x\notin B\cup C$, so $x$ is in neither $B$ nor $C$. Hence $x\in A\setminus B$ and $x\in A\setminus C$, that is $x\in (A\setminus B)\cap (A\setminus C)$. The reverse inclusion runs the same steps backward. Switching the order of unions and intersections across an infinite family generally requires proof.

Induction and well-ordering

Statements indexed by a natural number are proved by induction, which rests on a single order property of $\mathbb{N}$ we take as an axiom.

From well-ordering the induction principle follows.

Let $S$ be the set of $n$ for which $P(n)$ fails, and suppose $S\ne \varnothing$. By well-ordering $S$ has a least element $m$. The basis gives $m>1$, so $m-1\in \mathbb{N}$, and $m-1\notin S$ because $m$ is least — hence $P(m-1)$ holds. The induction step then forces $P(m)$, contradicting $m\in S$. So $S$ is empty.¹

For example, $2^{n-1}\le n!$ for all $n\in \mathbb{N}$. The basis $n=1$ reads $1\le 1$. Assuming $2^{n-1}\le n!$, multiply by $2$ and use $2\le n+1$:

which is $P(n+1)$. A convenient variant, strong induction, assumes $P(k)$ for all $k\le n$ in the induction step; it is equivalent to the ordinary form.

Functions

Informally a function $f:A\to B$ assigns to each $x\in A$ a single $y\in B$. To make this precise we first form ordered pairs.

The set $A$ is the domain, $B$ the codomain, and the range is $R(f)=\{f(x):x\in A\}\subset B$. The range can be a proper subset of the codomain. A function is best pictured as a table of assignments rather than a formula: many functions have no formula at all, and a single function can be written by several different formulas.

Inverse images are the better-behaved of the two: they commute with all three set operations,

Direct images do not: in general $f(C\cap D)\subset f(C)\cap f(D)$, and the inclusion can be strict. This asymmetry is why the topological definition of continuity, developed in continuous functions, is phrased with inverse images of open sets rather than direct images.

Injective, surjective, bijective

When $f$ is a bijection, the inverse image of each single element $\{y\}$ is one point, so $f^{-1}$ is itself a function $B\to A$, the inverse function. For example $f(x)=x^3$ on $\mathbb{R}$ is a bijection with $f^{-1}(x)=x^{1/3}$.

Composition chains functions: for $f:A\to B$ and $g:B\to C$, the composition $g\circ f:A\to C$ is $(g\circ f)(x)=g(f(x))$. Compositions of injections are injective and of surjections are surjective, so compositions of bijections are bijections.

Relations and equivalence classes

A binary relation on $A$ is any subset $R\subset A\times A$; we write $aRb$ for $(a,b)\in R$. The comparisons $<$, $=$, and $\subset$ are all relations. Three properties single out the relations that behave like equality.

An equivalence relation partitions $A$: the equivalence class of $a$ is $[a]=\{x\in A:aRx\}$, and every element lies in exactly one class, with $aRb\leftrightarrow [a]=[b]$. This construction builds number systems. The rationals are equivalence classes of pairs $(a,b)\in \mathbb{Z}\times \mathbb{N}$ under $(a,b)\sim (c,d)\leftrightarrow ad=bc$, and the class of $(a,b)$ is written $a/b$, so $1/2$ and $2/4$ denote the same rational.

Cardinality

Counting a finite set is pairing its elements with $\{1,2,\dots ,n\}$. A bijection is the right generalization of that pairing to any size.

Having the same cardinality is an equivalence relation: the identity gives reflexivity, the inverse of a bijection gives symmetry, and composition gives transitivity. A set is finite if $|A|=n$ for some $n$ (or $A=\varnothing$), and infinite otherwise. The Cantor–Bernstein–Schröder theorem, which we use but do not prove, says $|A|\le |B|$ and $|B|\le |A|$ together give $|A|=|B|$ — cardinalities can be compared like numbers.¹

Infinite sets split into two grades.

Countably infinite means listable: a bijection $\mathbb{N}\to A$ is precisely an enumeration $a_1,a_2,a_3,\dots$ that hits every element once. Several sets that look too large to list are in fact countable.

• Even numbers. $f(n)=2n$ is a bijection from $\mathbb{N}$ onto the even naturals, so a proper subset has the same cardinality as the whole. This cannot happen for finite sets, and in fact characterizes infinite ones.
• Pairs. $\mathbb{N}\times \mathbb{N}$ is countable. List the pairs by anti-diagonals: first the pair summing to $2$, then those summing to $3$, and so on, giving $(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),\dots$
• Rationals. $\mathbb{Q}$ is countable. Apply the same zig-zag to the positive fractions $p/q$, skip any already listed in lower terms, then interleave $0$ and the negatives.

The anti-diagonal order is an explicit bijection, not just a picture.

Countability is preserved downward: a subset of a countable set is countable, and (taking the contrapositive) any set containing an uncountable set is uncountable. Not every infinite set is countable, however.

Cantor's theorem

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$. For a finite set of size $n$ it has size $2^n$, strictly larger than $n$. Cantor's theorem extends the strict inequality to infinite sets, and its proof is the diagonal argument that recurs throughout analysis and logic.¹

The name diagonal is clearest when $A=\mathbb{N}$. A subset of $\mathbb{N}$ is the same data as an infinite binary string — its indicator, with a $1$ in position $k$ when $k$ is in the subset. A claimed enumeration of all such strings is an infinite table; the set $B$ is obtained by flipping each diagonal entry, producing a string that disagrees with row $n$ in column $n$, hence a subset on no row of the table.

In particular $\mathcal{P}(\mathbb{N})$ is uncountable, so uncountable sets exist. Iterating, $\mathbb{N},\mathcal{P}(\mathbb{N}),\mathcal{P}(\mathcal{P}(\mathbb{N})),\dots$ is a strictly increasing tower of infinities. The set $\mathbb{R}$ has the same cardinality as $\mathcal{P}(\mathbb{N})$, so it too is uncountable — a fact we prove directly, twice, once by nested intervals and once by a decimal diagonal, in intervals and uncountability.

Quantifier order carries the most weight: the supremum, the limit, continuity, and integrability are each a fixed arrangement of $\forall$ and $\exists$, and reading that arrangement correctly is most of understanding them.