Sets, Functions, and Relations

A set is a collection of distinct objects. We write $x \in A$ to mean $x$ is an element of $A$. The empty set is $\emptyset$. Standard constructions: union $A \cup B$, intersection $A \cap B$, complement $A^c$, difference $A \setminus B$.

The Cartesian product of sets $A$ and $B$ is the set of all ordered pairs:

$A \times B = \{(a, b) : a \in A, \, b \in B\}$

More generally, $A_1 \times \cdots \times A_n$ is the set of $n$-tuples. The space $\mathbb{R}^d$ is $\mathbb{R} \times \cdots \times \mathbb{R}$ ($d$ times).

A function $f: A \to B$ assigns to each element $a \in A$ exactly one element $f(a) \in B$. The set $A$ is the domain, $B$ is the codomain. The image of $S \subseteq A$ is $f(S) = \{f(a) : a \in S\}$. The preimage of $T \subseteq B$ is $f^{-1}(T) = \{a \in A : f(a) \in T\}$.

A function $f: A \to B$ is:

• Injective (one-to-one): $f(a_1) = f(a_2) \implies a_1 = a_2$
• Surjective (onto): for every $b \in B$, there exists $a \in A$ with $f(a) = b$
• Bijective: both injective and surjective. A bijection has an inverse $f^{-1}: B \to A$.

A relation $\sim$ on a set $A$ is an equivalence relation if and only if it is:

1. Reflexive: $a \sim a$ for all $a \in A$
2. Symmetric: $a \sim b \implies b \sim a$
3. Transitive: $a \sim b$ and $b \sim c \implies a \sim c$

The equivalence class of $a$ is $[a] = \{b \in A : b \sim a\}$.

The quotient set $A / {\sim}$ is the set of all equivalence classes $\{[a] : a \in A\}$. The equivalence classes partition $A$ into disjoint, exhaustive subsets.

The power set of $A$, written $\mathcal{P}(A)$ or $2^A$, is the set of all subsets of $A$:

$\mathcal{P}(A) = \{S : S \subseteq A\}$

If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$. The power set always includes $\emptyset$ and $A$ itself. Power sets appear in measure theory when defining sigma-algebras: a sigma-algebra on $A$ is a subset of $\mathcal{P}(A)$ closed under complements and countable unions.

Two sets $A$ and $B$ have the same cardinality (written $|A| = |B|$) if and only if there exists a bijection $f: A \to B$. For finite sets, cardinality is the count of elements. For infinite sets, cardinality distinguishes countable sets (bijectable with $\mathbb{N}$) from uncountable ones (like $\mathbb{R}$). See cardinality and countability for a full treatment.

Given $f: A \to B$ and $g: B \to C$, the composition $g \circ f: A \to C$ is defined by $(g \circ f)(a) = g(f(a))$. Composition is associative: $h \circ (g \circ f) = (h \circ g) \circ f$. It is not commutative in general.

A function $f: A \to B$ has a left inverse $g: B \to A$ when $g \circ f = \text{id}_A$, and a right inverse $h: B \to A$ when $f \circ h = \text{id}_B$. A left inverse implies that $f$ is injective. Conversely, if $f$ is injective and $A$ is nonempty, choose one $a_0\in A$, invert $f$ on its image, and send every point of $B\setminus f(A)$ to $a_0$; no axiom of choice is needed. The empty-domain edge case matters: if $A=\emptyset$ and $B\neq\emptyset$, the unique map $A\to B$ is injective but cannot have a left inverse. A right inverse implies that $f$ is surjective; under the axiom of choice, every surjection has a right inverse obtained by choosing one point from each fiber (Halmos, 1960, Chapters 2-3).

A relation from $A$ to $B$ is a subset $R \subseteq A \times B$. We write $a \mathrel{R} b$ to mean $(a, b) \in R$. A function $f: A \to B$ is a special case: a relation where each $a \in A$ appears in exactly one pair.

A relation $\leq$ on a set $A$ is a partial order if and only if it is:

1. Reflexive: $a \leq a$ for all $a \in A$
2. Antisymmetric: $a \leq b$ and $b \leq a$ implies $a = b$
3. Transitive: $a \leq b$ and $b \leq c$ implies $a \leq c$

A set with a partial order is called a poset (partially ordered set). A total order is a partial order where every pair is comparable: for all $a, b$, either $a \leq b$ or $b \leq a$.