---
title: Sets, Logic, and Functions
module: Foundations and the Real Number System
moduleNumber: 1
lessonNumber: 1
order: 101
summary: >
  The working language of analysis: quantifiers and the proof patterns
  (contrapositive, contradiction, induction), sets and their operations,
  relations and equivalence classes, and functions with their images, injections,
  surjections, and bijections. Cardinality is measured by bijection, and Cantor's
  theorem that no set surjects onto its power set forces uncountable sets to exist.
topics: [Foundations and the Real Number System]
sources:
  - book: Lebl
    ref: "Introduction — §0.3 Basic set theory (induction, functions, relations, cardinality, Cantor's theorem)"
  - book: Rosenlicht
    ref: "Ch. 1 — Notions from set theory"
draft: false
---

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 y\, P(x,y)$ lets $y$ depend on $x$; the
statement $\exists y\, \forall x\, P(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](/real-analysis/continuity/uniform-continuity), pointwise versus
[uniform convergence](/real-analysis/function-sequences/pointwise-uniform-convergence)),
so read quantifier order carefully from the start.

Negation flips quantifiers and passes to the inside:

$$
\neg\bigl(\forall x \in S,\ P(x)\bigr) \iff \exists x \in S,\ \neg P(x),
\qquad
\neg\bigl(\exists x \in S,\ P(x)\bigr) \iff \forall x \in S,\ \neg P(x).
$$

To disprove "every $x$ has property $P$," exhibit one $x$ without it; that single $x$ is a
**counterexample**. The negation of an implication $P \implies 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 \implies Q$, assume $P$ and derive $Q$ by valid steps.
- **Contrapositive.** The implication $P \implies Q$ is logically identical to
  $\neg Q \implies \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 $\sqrt2 = m/n$ in lowest terms, deduce that $m$ and $n$
  are both even — is the archetype; it appears in full in the proof that
  [$\sqrt2$ exists in $\mathbb{R}$](/real-analysis/foundations/ordered-fields-completeness).

> **Definition (Contrapositive).** The contrapositive of $P \implies Q$ is
> $\neg Q \implies \neg P$. The two implications are equivalent: each is true in exactly the
> same circumstances. The **converse** $Q \implies P$ is a different statement and need not
> hold.

## 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** $\emptyset$. The standard number systems are

$$
\mathbb{N} = \{1,2,3,\dots\}, \quad
\mathbb{Z} = \{\dots,-1,0,1,\dots\}, \quad
\mathbb{Q} = \{\tfrac{p}{q} : p \in \mathbb{Z},\ q \in \mathbb{N}\}, \quad
\mathbb{R},
$$

with $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$. The three binary
operations on sets are union, intersection, and difference.[^lebl-set]

> **Definition (Set operations).** For sets $A$ and $B$,
> $$
> A \cup B = \{x : x \in A \text{ or } x \in B\}, \qquad
> A \cap B = \{x : x \in A \text{ and } x \in B\},
> $$
> $$
> A \setminus B = \{x : x \in A \text{ and } x \notin B\}.
> $$
> When $A$ is a fixed universe, $B^c = A \setminus B$ is the **complement** of $B$. Sets with
> $A \cap B = \emptyset$ are **disjoint**.

$$
% caption: Union, intersection, and difference of two sets; the shaded region is
% the result of each operation.
\begin{tikzpicture}[scale=1.0, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
% panel 1: union
\begin{scope}
  \begin{scope}
    \clip (-0.35,0) circle (0.85);
    \fill[acc!14] (0.35,0) circle (0.85);
  \end{scope}
  \fill[acc!14] (-0.35,0) circle (0.85);
  \fill[acc!14] (0.35,0) circle (0.85);
  \draw[black] (-0.35,0) circle (0.85);
  \draw[black] (0.35,0) circle (0.85);
  \node at (-0.65,0) {$A$};
  \node at (0.65,0) {$B$};
  \node[anchor=north] at (0,-1.05) {union};
\end{scope}
% panel 2: intersection
\begin{scope}[xshift=3.4cm]
  \begin{scope}
    \clip (-0.35,0) circle (0.85);
    \fill[acc!22] (0.35,0) circle (0.85);
  \end{scope}
  \draw[black] (-0.35,0) circle (0.85);
  \draw[black] (0.35,0) circle (0.85);
  \node at (-0.65,0) {$A$};
  \node at (0.65,0) {$B$};
  \node[anchor=north] at (0,-1.05) {intersection};
\end{scope}
% panel 3: difference
\begin{scope}[xshift=6.8cm]
  \begin{scope}
    \clip (0.35,0) circle (0.85);
    \fill[white] (-0.35,0) circle (0.85);
  \end{scope}
  \begin{scope}
    \clip (-0.35,0) circle (0.85);
    \fill[acc!16] (-0.35,0) circle (0.85);
    \fill[white] (0.35,0) circle (0.85);
  \end{scope}
  \draw[black] (-0.35,0) circle (0.85);
  \draw[black] (0.35,0) circle (0.85);
  \node at (-0.65,0) {$A$};
  \node at (0.65,0) {$B$};
  \node[anchor=north] at (0,-1.05) {set minus};
\end{scope}
\end{tikzpicture}
$$

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

$$
\bigcup_{\lambda \in I} A_\lambda = \{x : x \in A_\lambda \text{ for some } \lambda\},
\qquad
\bigcap_{\lambda \in I} A_\lambda = \{x : x \in A_\lambda \text{ for all } \lambda\}.
$$

The two operations trade places under complement, **De Morgan's laws**, stated here in
their general form:[^lebl-set]

> **Theorem (De Morgan).** For sets $A, B, C$,
> $$
> A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C), \qquad
> A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C).
> $$

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.

> **Axiom (Well-ordering of $\mathbb{N}$).** Every nonempty subset of $\mathbb{N}$ has a
> least element.

From well-ordering the induction principle follows.

> **Theorem (Principle of induction).** Let $P(n)$ be a statement about $n \in \mathbb{N}$.
> If $P(1)$ is true (the basis) and $P(n) \implies P(n+1)$ for every $n$ (the induction step),
> then $P(n)$ is true for all $n \in \mathbb{N}$.

Let $S$ be the set of $n$ for which $P(n)$
fails, and suppose $S \ne \emptyset$. 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.[^lebl-set]

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$:

$$
2^{n} \;=\; 2 \cdot 2^{n-1} \;\le\; 2 \cdot n! \;\le\; (n+1)\, n! \;=\; (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.

> **Definition (Cartesian product).** For sets $A$ and $B$, the Cartesian product is
> $A \times B = \{(x,y) : x \in A,\ y \in B\}$. A **function** $f : A \to B$ is a subset
> $f \subset A \times B$ such that for each $x \in A$ there is exactly one $y \in B$ with
> $(x,y) \in f$; we write $f(x) = y$. That subset is the **graph** of $f$.

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.

> **Definition (Image and inverse image).** For $f : A \to B$, a subset $C \subset A$, and a
> subset $D \subset B$,
> $$
> f(C) = \{f(x) : x \in C\}, \qquad f^{-1}(D) = \{x \in A : f(x) \in D\}.
> $$
> $f(C)$ is the (direct) **image** of $C$; $f^{-1}(D)$ is the **inverse image** of $D$.

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

$$
f^{-1}(C \cup D) = f^{-1}(C) \cup f^{-1}(D), \quad
f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D), \quad
f^{-1}(C^c) = \bigl(f^{-1}(C)\bigr)^c.
$$

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](/real-analysis/continuity/continuous-functions), is phrased with
inverse images of open sets rather than direct images.

### Injective, surjective, bijective

> **Definition (Injection, surjection, bijection).** A function $f : A \to B$ is
> - **injective** (one-to-one) if $f(x_1) = f(x_2)$ implies $x_1 = x_2$;
> - **surjective** (onto) if $f(A) = B$, i.e. every $y \in B$ equals $f(x)$ for some $x$;
> - **bijective** if it is both injective and surjective.

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

$$
% caption: Three functions between finite sets: injective (no target hit twice),
% surjective (every target hit), and bijective (a perfect pairing).
\begin{tikzpicture}[scale=1.0, font=\footnotesize,
  dot/.style={circle, fill=black, inner sep=1.3pt}]
\definecolor{acc}{HTML}{4A6FA5}
% panel 1: injective (not surjective): 3 -> 4
\begin{scope}
  \foreach \i/\y in {1/0,2/0.9,3/1.8} \node[dot] (l\i) at (0,\y) {};
  \foreach \i/\y in {1/-0.45,2/0.45,3/1.35,4/2.25} \node[dot] (r\i) at (1.6,\y) {};
  \draw[->, acc] (l1) -- (r1);
  \draw[->, acc] (l2) -- (r2);
  \draw[->, acc] (l3) -- (r3);
  \node[anchor=north] at (0.8,-0.85) {injective};
\end{scope}
% panel 2: surjective (not injective): 4 -> 3
\begin{scope}[xshift=4.3cm]
  \foreach \i/\y in {1/-0.45,2/0.45,3/1.35,4/2.25} \node[dot] (a\i) at (0,\y) {};
  \foreach \i/\y in {1/0,2/0.9,3/1.8} \node[dot] (b\i) at (1.6,\y) {};
  \draw[->, acc] (a1) -- (b1);
  \draw[->, acc] (a2) -- (b1);
  \draw[->, acc] (a3) -- (b2);
  \draw[->, acc] (a4) -- (b3);
  \node[anchor=north] at (0.8,-0.85) {surjective};
\end{scope}
% panel 3: bijective
\begin{scope}[xshift=8.6cm]
  \foreach \i/\y in {1/0,2/0.9,3/1.8} \node[dot] (c\i) at (0,\y) {};
  \foreach \i/\y in {1/0,2/0.9,3/1.8} \node[dot] (d\i) at (1.6,\y) {};
  \draw[->, acc] (c1) -- (d1);
  \draw[->, acc] (c2) -- (d2);
  \draw[->, acc] (c3) -- (d3);
  \node[anchor=north] at (0.8,-0.85) {bijective};
\end{scope}
\end{tikzpicture}
$$

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 $a\, R\, b$ for
$(a,b) \in R$. The comparisons $<$, $=$, and $\subset$ are all relations. Three properties
single out the relations that behave like equality.

> **Definition (Equivalence relation).** A relation $R$ on $A$ is
> - **reflexive** if $a\,R\,a$ for all $a$;
> - **symmetric** if $a\,R\,b$ implies $b\,R\,a$;
> - **transitive** if $a\,R\,b$ and $b\,R\,c$ imply $a\,R\,c$.
>
> A relation with all three is an **equivalence relation**.

An equivalence relation partitions $A$: the **equivalence class** of $a$ is
$[a] = \{x \in A : a\,R\,x\}$, and every element lies in exactly one class, with
$a\,R\,b \iff [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) \iff 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.

> **Definition (Same cardinality).** Sets $A$ and $B$ have the **same cardinality**, written
> $|A| = |B|$, when there exists a bijection $f : A \to B$. We write $|A| \le |B|$ when an
> injection $A \to B$ exists, and $|A| < |B|$ when $|A| \le |B|$ but $|A| \ne |B|$.

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 = \emptyset$), 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.[^lebl-set]

Infinite sets split into two grades.

> **Definition (Countable).** A set $A$ is **countably infinite** if $|A| = |\mathbb{N}|$, and
> **countable** if it is finite or countably infinite. A set that is not countable is
> **uncountable**. The cardinality of $\mathbb{N}$ is written $\aleph_0$.

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.

$$
% caption: The anti-diagonal enumeration of the pairs, which lists every element
% of the grid exactly once and so counts a two-dimensional set with one index.
\begin{tikzpicture}[scale=1.0, font=\footnotesize,
  gp/.style={draw, minimum width=9mm, minimum height=6mm, inner sep=1pt}]
\definecolor{acc}{HTML}{4A6FA5}
\foreach \r/\rl in {0/1,1/2,2/3,3/4} {
  \foreach \c/\cl in {0/1,1/2,2/3,3/4} {
    \node[gp] (n\r\c) at (\c*1.35, -\r*0.95) {(\rl,\cl)};
  }
}
% anti-diagonal enumeration: sum 2, then sum 3, then sum 4, ...
\draw[->, acc, thick] (n00) -- (n01);
\draw[->, acc, thick] (n01) .. controls (0.55,-0.75) .. (n10);
\draw[->, acc, thick] (n10) .. controls (1.9,-0.95) .. (n02);
\draw[->, acc, thick] (n02) .. controls (2.0,-1.15) .. (n11);
\draw[->, acc, thick] (n11) .. controls (1.0,-1.55) .. (n20);
\draw[->, acc, thick] (n20) .. controls (3.1,-1.9) .. (n03);
\node[anchor=west, text=acc] at (4.9,-0.95) {follow the arrows};
\node[anchor=west, text=acc] at (4.9,-1.75) {to list every pair};
\end{tikzpicture}
$$

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

> **Worked example.** The map $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$,
> $$
> f(m, n) = \frac{(m + n - 2)(m + n - 1)}{2} + m,
> $$
> is a bijection. Each pair $(m, n)$ lies on the anti-diagonal of constant sum $s = m + n$.
> The diagonals with smaller sum $2, 3, \dots, s - 1$ hold $1, 2, \dots, s - 2$ pairs, totalling
> $\frac{(s-2)(s-1)}{2}$; within its own diagonal the pair is the $m$-th, ordered by increasing
> first coordinate. Adding these gives $f$. Checking the first few values recovers the listed
> order: $f(1,1) = 1$, $f(1,2) = 2$, $f(2,1) = 3$, $f(1,3) = 4$, $f(2,2) = 5$, $f(3,1) = 6$.
> Every diagonal is exhausted before the next begins, so $f$ hits each natural exactly once:
> it is a bijection, and $\mathbb{N} \times \mathbb{N}$ is countable.

> **Worked example.** $\mathbb{Z}$ is countable. The map $g : \mathbb{N} \to \mathbb{Z}$,
> $$
> g(n) = \begin{cases} n/2 & \text{if } n \text{ is even}, \\ -(n-1)/2 & \text{if } n \text{ is odd}, \end{cases}
> $$
> enumerates $\mathbb{Z}$ as $0, 1, -1, 2, -2, 3, -3, \dots$ The even inputs cover the positive
> integers, the odd inputs cover $0$ and the negatives, and no integer is hit twice, so $g$ is a
> bijection $\mathbb{N} \to \mathbb{Z}$.

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.[^lebl-set]

> **Theorem (Cantor).** For every set $A$, $|A| < |\mathcal{P}(A)|$. In particular there is no
> surjection $A \to \mathcal{P}(A)$.

> **Proof.** The map $x \mapsto \{x\}$ is an injection $A \to \mathcal{P}(A)$, so
> $|A| \le |\mathcal{P}(A)|$. It remains to rule out a surjection. Let $g : A \to \mathcal{P}(A)$
> be any function; each $g(x)$ is a subset of $A$. Define the **diagonal set**
>
> $$
> B = \{x \in A : x \notin g(x)\}.
> $$
>
> Suppose $B = g(x_0)$ for some $x_0$. If $x_0 \in B$, then by the definition of $B$ we have
> $x_0 \notin g(x_0) = B$, a contradiction; if $x_0 \notin B$, then $x_0 \in g(x_0) = B$, again a
> contradiction. So $B$ is in the range of no $g$, and $g$ is not surjective. $\blacksquare$

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.

$$
% caption: The diagonal argument on binary strings: read the boxed diagonal, swap
% every bit, and the resulting string differs from every row of the list.
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
\definecolor{red}{HTML}{C0392B}
% rows of a claimed list of binary strings
\foreach \row/\r/\rl in {%
  {1,0,1,1,0}/0/1, {0,1,1,0,1}/1/2, {1,1,0,0,1}/2/3, {0,0,1,1,0}/3/4, {1,0,0,1,1}/4/5} {
  \node[anchor=east] at (-0.5,-\r*0.7) {$s_{\rl}$};
  \foreach \bit [count=\c from 0] in \row {
    \node at (\c*0.7,-\r*0.7) {\bit};
  }
}
% highlight the diagonal
\foreach \d in {0,1,2,3,4} {
  \draw[red, thick] (\d*0.7,-\d*0.7) circle (0.24);
}
\node[anchor=west, text=red] at (4.1,-1.05) {diagonal: 1 1 0 1 1};
\node[anchor=west, text=acc] at (4.1,-1.75) {swap the bits: 0 0 1 0 0};
\node[anchor=west, text=acc] at (4.1,-2.45) {on no row of the list};
\end{tikzpicture}
$$

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](/real-analysis/foundations/intervals-uncountability).

| Set | Cardinality | Countable? |
| --- | --- | --- |
| $\{1,\dots,n\}$ | $n$ | finite |
| $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ | $\aleph_0$ | countably infinite |
| $\mathbb{N} \times \mathbb{N}$ | $\aleph_0$ | countably infinite |
| $\mathcal{P}(\mathbb{N})$, $\mathbb{R}$ | $> \aleph_0$ | uncountable |

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.

[^lebl-set]: **Lebl**, _Basic Analysis I_, §0.3 — Basic set theory: set operations and De Morgan's laws, the well-ordering property and the principle of induction, functions with their images and inverse images, injections/surjections/bijections, cardinality and countability, and Cantor's theorem on the power set with the diagonal argument.