Sets, Functions & Relations

Sets say which objects are present. Relations say which tuples satisfy a condition. Functions are relations with an exact output obligation: for every input in their domain, there is one and only one output. Keeping those types visible turns many apparently different problems—database joins, graph edges, state transitions, lookup tables, and API mappings—into the same small collection of operations.

Sets: membership determines identity #

Extensionality is a proof method, not just a definition. To prove $A=B$, prove both inclusions:

$$A\subseteq B \quad\text{and}\quad B\subseteq A,$$

where $A\subseteq B$ means $\forall x\,(x\in A\Rightarrow x\in B)$. By contrast, $x\in A$ compares an object with a set; $A\subseteq B$ compares two sets. Confusing those two levels is one of the most common type errors in discrete mathematics.

A set-builder expression should be read relative to an already available universe or set:

$$\{x\in U:P(x)\}.$$

Writing an unrestricted “set of every object satisfying $P$” is not always legitimate. In particular, the attempted collection $R=\{x:x\notin x\}$ would imply $R\in R\leftrightarrow R\notin R$; this is Russell's paradox, not a set.

Operations are membership programs #

For $A,B\subseteq U$, every ordinary operation can be specified by the Boolean test used for membership.

This view makes the algebra checkable one element at a time. For example,

$$\begin{aligned} x\in (A\cap B)^c &\iff \neg(x\in A\land x\in B)\\ &\iff x\notin A\lor x\notin B\\ &\iff x\in A^c\cup B^c. \end{aligned}$$

Extensionality then gives $(A\cap B)^c=A^c\cup B^c$. The same method proves associativity, distributivity, absorption, and the second De Morgan law. It also prevents two frequent transcription errors:

$$A\setminus B=A\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c.$$

Families and the empty-family edge case #

For an indexed family $(A_i)_{i\in I}$ inside a fixed universe $U$,

$$x\in\bigcup_{i\in I}A_i \iff \exists i\in I\;(x\in A_i), \qquad x\in\bigcap_{i\in I}A_i \iff \forall i\in I\;(x\in A_i).$$

If $I=\varnothing$, the existential condition is false, so the union is $\varnothing$. The universal condition is vacuously true, so the intersection is $U$ relative to the declared universe. Without an ambient $U$, “the intersection of no sets is the set of everything” does not define a set in ordinary axiomatic set theory.

Why a finite power set has size $2^n$ #

Let $A$ have $n$ elements. A subset $S\subseteq A$ makes one independent binary decision for every $a\in A$: include it or exclude it. Equivalently, $S$ has a characteristic function

$$\chi_S:A\to\{0,1\},\qquad \chi_S(a)=1\iff a\in S.$$

This is a bijection between $\mathcal P(A)$ and all $n$-bit functions, so

$$|\mathcal P(A)|=2^n.$$

The edge case is informative: $\mathcal P(\varnothing)=\{\varnothing\}$, hence $2^0=1$.

Cartesian products make positions explicit #

An ordered pair $\langle a,b\rangle$ remembers which value is first. A particular set encoding, such as $\langle a,b\rangle=\{\{a\},\{a,b\}\}$, is useful in foundational reductions, but applications normally rely only on the invariant

$$\langle a,b\rangle=\langle c,d\rangle\iff a=c\land b=d.$$

The Cartesian product

$$A\times B=\{\langle a,b\rangle:a\in A\land b\in B\}$$

is typed: the first coordinate comes from $A$, the second from $B$. If $A$ and $B$ are finite, then

$$|A\times B|=|A|\,|B|,$$

because every one of the $|A|$ first-coordinate choices can be paired with every one of the $|B|$ second-coordinate choices. An $n$-tuple is an element of $A_1\times\cdots\times A_n$; do not silently identify it with an arbitrarily nested binary pair unless an encoding has been chosen.

Relations are sets of typed witnesses #

This representation turns a two-argument predicate into stored witnesses. It also exposes the types: “is a dependency of” may relate packages to packages, while “owns” may relate users to services. Composition is legal only when the middle types agree.

For $R\subseteq A\times B$:

$$\begin{aligned} \mathop{\mathrm{dom}}(R)&=\{a\in A:\exists b\in B\;aRb\},\\ \mathop{\mathrm{ran}}(R)&=\{b\in B:\exists a\in A\;aRb\},\\ R^{-1}&=\{\langle b,a\rangle:aRb\}. \end{aligned}$$

If $R\subseteq A\times B$ and $S\subseteq B\times C$, use the same order as function composition:

$$a\,(S\circ R)\,c \iff \exists b\in B\;(aRb\land bSc).$$

Read $S\circ R$ right to left: first follow $R$, then $S$.

Functions are total, single-valued relations #

As a relation, $\Gamma_f$ satisfies existence and uniqueness:

$$\forall a\in A\;\exists!b\in B\;(a,b)\in\Gamma_f.$$

A partial function $p:A\rightharpoonup B$ keeps uniqueness but drops existence for some inputs. Its actual domain is $\mathop{\mathrm{dom}}(p)\subseteq A$. A map that returns either a value or an explicit error can instead be modelled as a total function $A\to B+E$; that makes failure data part of the codomain rather than silently leaving the function undefined.

flowchart TD
  R["relation R ⊆ A × B"]
  P["partial function: at most one b per a"]
  F["total function f: A → B: exactly one b per a"]
  I["injective: each b has at most one preimage"]
  S["surjective: each b has at least one preimage"]
  J["bijective: each b has exactly one preimage"]
  R -->|"single-valued"| P
  P -->|"defined for every a"| F
  F --> I
  F --> S
  I --> J
  S --> J

The diagram is a constraint ladder. Moving downward adds obligations; it does not change the function's declared domain or codomain. In particular, surjectivity is not “the range is whatever happened to occur.” It is the assertion that the range equals the already declared codomain.

Images and preimages have different algebra #

For $S\subseteq A$ and $T\subseteq B$,

$$f[S]=\{f(a):a\in S\},\qquad f^{-1}[T]=\{a\in A:f(a)\in T\}.$$

The notation $f^{-1}[T]$ means preimage even when $f$ has no inverse function.

Preimages preserve all Boolean set operations because membership is tested pointwise:

$$f^{-1}[T_1\cup T_2]=f^{-1}[T_1]\cup f^{-1}[T_2], \quad f^{-1}[T_1\cap T_2]=f^{-1}[T_1]\cap f^{-1}[T_2], \quad f^{-1}[B\setminus T]=A\setminus f^{-1}[T].$$

Images always preserve unions, but only satisfy

$$f[S_1\cap S_2]\subseteq f[S_1]\cap f[S_2].$$

Equality can fail when $f$ is not injective. Let $f(x)=x^2$, $S_1=\{-1\}$, and $S_2=\{1\}$. Then $S_1\cap S_2=\varnothing$, but both images are $\{1\}$, so their image intersection is nonempty. Injectivity removes exactly this collision and restores equality.

Two identities are useful diagnostics:

$$S\subseteq f^{-1}[f[S]],\qquad f[f^{-1}[T]]\subseteq T.$$

The first is equality when $f$ is injective; the second is equality when every element of $T$ lies in the range of $f$.

Composition, identities, and inverses #

Given $f:A\to B$ and $g:B\to C$,

$$(g\circ f)(a)=g(f(a)).$$

Composition is associative because both parenthesizations evaluate to the same value:

$$((h\circ g)\circ f)(a)=h(g(f(a)))=(h\circ(g\circ f))(a).$$

The identity $\mathop{\mathrm{id}}_A(a)=a$ is neutral: $f\circ\mathop{\mathrm{id}}_A=f$ and $\mathop{\mathrm{id}}_B\circ f=f$. These are type-sensitive equations; $\mathop{\mathrm{id}}_A$ and $\mathop{\mathrm{id}}_B$ are usually different functions.

A map $\ell:B\to A$ is a left inverse when $\ell\circ f=\mathop{\mathrm{id}}_A$. A map $r:B\to A$ is a right inverse when $f\circ r=\mathop{\mathrm{id}}_B$.

• A left inverse forces injectivity: if $f(a_1)=f(a_2)$, apply $\ell$ to both sides.
• Conversely, an injective $f:A\to B$ has a left inverse when $A$ is nonempty: use the unique preimage on $f[A]$ and a fixed default $a_0\in A$ elsewhere. The exceptional injection $\varnothing\to B$ has a left inverse only if $B=\varnothing$.
• A right inverse forces surjectivity because $b=f(r(b))$ supplies a preimage.
• Constructing a right inverse for an arbitrary surjection requires choosing one preimage from every nonempty fiber. It is automatic for finite explicitly enumerable fibers; for arbitrary families, “every surjection splits” is a form of the Axiom of Choice.
• A two-sided inverse exists exactly for a bijection and is unique. Its value at $b$ is the unique $a$ with $f(a)=b$.

Relation powers and finite-path closure #

Let $R\subseteq A\times A$ be an endorelation and $I_A=\{(a,a):a\in A\}$. Define

$$R^0=I_A,\qquad R^{n+1}=R\circ R^n.$$

Then $(a,b)\in R^n$ means there is an $R$-path of exactly $n$ steps from $a$ to $b$. The two standard closures are

$$R^+=\bigcup_{n\ge 1}R^n, \qquad R^*=\bigcup_{n\ge 0}R^n=I_A\cup R^+.$$

• $R^+$ is the transitive closure: positive-length reachability.
• $R^*$ is the reflexive-transitive closure: reachability in zero or more steps.
• The reflexive closure alone is merely $I_A\cup R$; it is generally smaller than $R^*$.

The word “closure” includes a minimality claim. If $T$ is transitive and $R\subseteq T$, induction gives $R^n\subseteq T$ for every $n\ge1$, hence $R^+\subseteq T$. Therefore $R^+$ is not just transitive; it is the least transitive relation containing $R$. The same argument, adding reflexivity, proves the corresponding property of $R^*$. This path-based definition matches the formal TransGen and ReflTransGen constructions in Mathlib's relation library.

A worked model: users, services, and owners #

Let $U$ be users, $S$ services, $C\subseteq U\times S$ the “may call” relation, and $o:S\to U$ the owner function.

• $C[u]=\{s\in S:uCs\}$ is the set of services user $u$ may call.
• $C^{-1}[s]=\{u\in U:uCs\}$ is the caller set for service $s$.
• $o^{-1}[\{u\}]$ is the fiber of services owned by $u$.
• $o$ is surjective only if every declared user owns at least one service; it is injective only if no user owns two services.
• The relation $O=\{(s,o(s)):s\in S\}$ is functional from services to users. Its inverse relation need not be a function, because one user may own many services.

That last distinction is operationally important: reversing arrows in a data model does not automatically produce an inverse function. First inspect fiber cardinalities.

Diagnostic checklist #

When a discrete model feels ambiguous, ask these questions in order:

1. What are the carrier sets, and which universe makes complements meaningful?
2. Is each symbol membership, inclusion, a relation, or a function? Are its input/output types written down?
3. If it is called a function, is it total? If failures are possible, are they represented as partiality or explicit result values?
4. Is “onto” measured against a declared codomain or a retroactively chosen range?
5. Does a claimed inverse satisfy the correct left and right identity equations?
6. Does a closure include zero steps, positive steps, or only added identity pairs?
7. For any equality of sets or relations, what does an arbitrary element/pair have to satisfy on each side?

Most errors become short counterexamples once the carrier sets and quantifiers are explicit.