Set Theory/Relations

Note on axioms used. In this section we rely only on the ZF axioms: Extensionality, Pairing, Separation (schema), Union, and Power Set. We do not use Replacement, Choice, or Regularity here. (Choice and Regularity will be introduced later and not used until those chapters.)

To define relations on sets we must have a concept of an ordered pair, as opposed to the unordered pairs the Axiom of Pairing gives. We want a coding that satisfies ${\displaystyle (a,b)=(c,d)\iff a=c\ \wedge \ b=d}$.

A standard definition is the Kuratowski pair ${\displaystyle (a,b)=\{\{a\},\{a,b\}\}.}$

Existence note. The sets ${\displaystyle \{a\}}$ and ${\displaystyle \{a,b\}}$ exist by Pairing, and then ${\displaystyle \{\{a\},\{a,b\}\}}$ exists by Pairing again; hence every ordered pair exists.

We extend to longer tuples by recursion: ${\displaystyle (a,b,c)=((a,b),c)}$, etc.

Using ordered pairs we define the Cartesian product and relations.

Definition (Cartesian product). For sets ${\displaystyle A,B}$, ${\displaystyle A\times B=\{(a,b)\mid a\in A\ \wedge \ b\in B\}.}$

Existence of ${\displaystyle A\times B}$. For any ${\displaystyle a\in A,b\in B}$, the Kuratowski pair ${\displaystyle (a,b)}$ is a subset of ${\displaystyle {\mathcal {P}}(A\cup B)}$, hence ${\displaystyle (a,b)\in {\mathcal {P}}({\mathcal {P}}(A\cup B))}$. Therefore ${\displaystyle A\times B\subseteq {\mathcal {P}}({\mathcal {P}}(A\cup B))}$, and by Separation on that ambient set with the formula “${\displaystyle \exists a\in A,\exists b\in B\ (u=(a,b))}$”, the subset ${\displaystyle A\times B}$ exists. (Axioms used: Pairing, Union, Power Set, Separation.)

Definition (relation). A (binary) relation is any set all of whose elements are ordered pairs. If ${\displaystyle R\subseteq A\times B}$ we say the source is ${\displaystyle A}$ and the target is ${\displaystyle B}$; we write ${\displaystyle (x,y)\in R}$ or ${\displaystyle x\ R\ y}$.

Domain, range, field. For a relation ${\displaystyle R}$ define ${\displaystyle \mathrm {dom} \ R=\{x:\exists y\ (x,y)\in R\},\quad \mathrm {ran} \ R=\{y:\exists x\ (x,y)\in R\},\quad \mathrm {field} R=\mathrm {dom} \ R\cup \mathrm {ran} \ R.}$

Existence of domain/range. Since ${\displaystyle R}$ is a set, so are ${\displaystyle \bigcup R}$ and ${\displaystyle \bigcup \bigcup R}$ (Union twice). Then ${\displaystyle \mathrm {dom} \ R,\mathrm {ran} \ R\subseteq \bigcup \bigcup R}$, and both are obtained by Separation inside ${\displaystyle \bigcup \bigcup R}$ using “${\displaystyle \exists y\ ((x,y)\in R)}$” and “${\displaystyle \exists x\ ((x,y)\in R)}$”. Hence the field is a set as well.

Converse. The (relational) converse of ${\displaystyle R\subseteq A\times B}$ is ${\displaystyle R^{T}=\{(y,x)\in B\times A\mid (x,y)\in R\}}$, a set by Separation on ${\displaystyle B\times A}$.

Image and preimage. For ${\displaystyle E\subseteq A}$, ${\displaystyle R[E]=\{y\in \mathrm {ran} \ R:\exists x\in E(x,y)\in R\}}$. For ${\displaystyle F\subseteq B}$, ${\displaystyle R^{T}[F]=\{x\in \mathrm {dom} \ R:\exists y\in F(x,y)\in R\}}$. Both exist by Separation (on ${\displaystyle \mathrm {ran} \ R}$ and ${\displaystyle \mathrm {dom} \ R}$ respectively).

Composition. If ${\displaystyle R\subseteq A\times B}$ and ${\displaystyle S\subseteq B\times C}$, their composition is ${\displaystyle S\circ R=\{(x,z)\in A\times C:\ \exists y\in B,((x,y)\in R\ \wedge \ (y,z)\in S)\}}$, a set by Separation on ${\displaystyle A\times C}$.

Benchmark relations.

1. Identity on ${\displaystyle A}$: ${\displaystyle I_{A}=\{(a,a):a\in A\}}$ (Separation on ${\displaystyle A\times A}$).

1. Universal relation on ${\displaystyle A}$: ${\displaystyle A\times A}$.

Elementary properties on a set ${\displaystyle X}$. A relation ${\displaystyle R\subseteq X\times X}$ is: reflexive if ${\displaystyle (\forall x\in X)\ xRx}$; symmetric if ${\displaystyle xRy\Rightarrow yRx}$; antisymmetric if ${\displaystyle (xRy\wedge yRx)\Rightarrow x=y}$; transitive if ${\displaystyle (xRy\wedge yRz)\Rightarrow xRz}$; total (on ${\displaystyle X}$) if ${\displaystyle \mathrm {dom} \ R=X}$.

Exercise. Show every relation from ${\displaystyle A}$ to ${\displaystyle B}$ is a subset of ${\displaystyle A\times B}$ and therefore a set (by Separation).

When ${\displaystyle A}$ and ${\displaystyle B}$ are different sets, the relation ${\displaystyle R\subseteq A\times B}$ is heterogeneous. Relations on a single set ${\displaystyle A}$ (i.e. ${\displaystyle R\subseteq A\times A}$) are homogeneous.

Let ${\displaystyle U}$ be a universe of discourse. By the Power Set axiom, ${\displaystyle {\mathcal {P}}(U)}$ exists. The membership relation ${\displaystyle x\in A}$ (with ${\displaystyle A\subseteq U}$) is a frequently used heterogeneous relation with domain ${\displaystyle U}$ and range ${\displaystyle {\mathcal {P}}(U)}$. Its converse is denoted ${\displaystyle A\ni x}$.

A relation ${\displaystyle f\subseteq X\times Y}$ is univalent (a partial function from ${\displaystyle X}$ to ${\displaystyle Y}$) if ${\displaystyle (x,y)\in f\ \wedge \ (x,z)\in f\ \Rightarrow \ y=z.}$ Equivalently (purely relationally), ${\displaystyle f\circ f^{T}\subseteq I_{Y}.}$

A function ${\displaystyle f:X\to Y}$ is a univalent relation with total domain, i.e. ${\displaystyle \mathrm {dom} \ f=X}$. Here ${\displaystyle X}$ is the domain and ${\displaystyle Y}$ the codomain.

For a function ${\displaystyle f:X\to Y}$ and ${\displaystyle A\subseteq X}$, the (direct) image is ${\displaystyle f(A)=\{y\in Y:\exists x\in A,\ f(x)=y\}}$. The range is ${\displaystyle f(X)}$. For ${\displaystyle B\subseteq Y}$, the preimage is ${\displaystyle f^{-1}(B)=\{x\in X:f(x)\in B\}}$. (Beware: ${\displaystyle f^{-1}}$ here denotes the preimage operator; an actual inverse function may not exist.)

Let ${\displaystyle {\mathcal {R}}={\mathcal {P}}(X\times Y)}$ be the set of all relations between ${\displaystyle X}$ and ${\displaystyle Y}$. Then ${\displaystyle Y^{X}=\{f\in {\mathcal {R}}:\ \mathrm {dom} \ f=X\ \wedge \ f\ {\text{is univalent}}\}}$ is a set by Separation on ${\displaystyle {\mathcal {R}}}$. Thus the collection of all functions ${\displaystyle X\to Y}$ is a set in ZF (no Replacement or Choice needed).

If ${\displaystyle f:X\to Y}$ and ${\displaystyle g:Y\to Z}$, then ${\displaystyle (g\circ f)(x)=g(f(x))}$, and ${\displaystyle g\circ f:X\to Z}$ is again a function. (Existence as a set follows from the relational composition above; univalence and totality are routine checks.)

A function ${\displaystyle f:X\to Y}$ is surjective if ${\displaystyle f(X)=Y}$. It is injective if ${\displaystyle f(x)=f(x')\Rightarrow x=x'}$; equivalently (relationally), ${\displaystyle f^{T}\circ f\subseteq I_{X}}$. A function is bijective if it is both.

For any function ${\displaystyle f:X\to Y}$, the converse relation ${\displaystyle f^{T}\subseteq Y\times X}$ always exists. It is a (total) function ${\displaystyle Y\to X}$ iff ${\displaystyle f}$ is bijective; in that case we write ${\displaystyle f^{-1}}$ for the inverse function.

Exercises.

• If a function has both a left inverse ${\displaystyle g}$ (${\displaystyle g\circ f=I_{X}}$) and a right inverse ${\displaystyle h}$ (${\displaystyle f\circ h=I_{Y}}$), show that ${\displaystyle g=h=f^{-1}}$.
• Prove that a function is invertible iff it is bijective.