Relations, Functions, and Quotients

Let $R$ be a set every element of which is an ordered pair. Then the classes

$\{a:\mathrm{\exists }b(a,b)\in R\}\text{and}\{b:\mathrm{\exists }a(a,b)\in R\}$

are sets, and both are included in $\bigcup \bigcup R$.

A relation is a set $R$ every element of which is an ordered pair (The Kuratowski ordered pair $(a,b):=\{\{a\},\{a,b\}\}$). We write $aRb$ for $(a,b)\in R$.

By If every element of $R$ is an ordered pair, then $\{a:\mathrm{\exists }b(a,b)\in R\}$ and $\{b:\mathrm{\exists }a(a,b)\in R\}$ are sets, both included in $\bigcup \bigcup R$ the following two classes are sets, so the notation is legitimate:

$\mathrm{dom}R:=\{a:\mathrm{\exists }b(a,b)\in R\},\mathrm{ran}R:=\{b:\mathrm{\exists }a(a,b)\in R\},$

the domain and the range of $R$. The field of $R$ is $\mathrm{fld}R:=\mathrm{dom}R\cup \mathrm{ran}R$ (The union $\bigcup x$ of a set, and the binary union $a\cup b:=\bigcup \{a,b\}$).

$R$ is a relation from $A$ to $B$ when $R\subseteq A\times B$ (The Cartesian product $A\times B:=\{z\in \mathcal{P}(\mathcal{P}(A\cup B)):\mathrm{\exists }a\in A\mathrm{\exists }b\in Bz=(a,b)\}$, Subset $x\subseteq y$, proper subset $x⊊y$, and the separation notation $\{z\in x:\phi (z)\}$), and a relation on $A$ when $R\subseteq A\times A$.

• Domain and range are intrinsic; the sets $A$ and $B$ are not. A relation determines its own domain and range, but it is a relation from $A$ to $B$ for many different $A$ and $B$: any $A$ containing $\mathrm{dom}R$ and any $B$ containing $\mathrm{ran}R$ will do. That is the content of Every relation $R$ satisfies $R\subseteq \mathrm{dom}R\times \mathrm{ran}R$, and $R$ is a relation from $A$ to $B$ if and only if $\mathrm{dom}R\subseteq A$ and $\mathrm{ran}R\subseteq B$, and it is the same distinction that makes a codomain part of the declaration $f:A\to B$ rather than of the set $f$ in A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain.

• The empty set is a relation. It has no elements, so the requirement that every element be an ordered pair holds vacuously, and $\mathrm{dom}\mathrm{\varnothing }=\mathrm{ran}\mathrm{\varnothing }=\mathrm{\varnothing }$. It is a relation on every set.

Let $R$ be a relation and let $A$ and $B$ be sets. Then

• (i) $R\subseteq \mathrm{dom}R\times \mathrm{ran}R$;
• (ii) $R\subseteq A\times B$ if and only if $\mathrm{dom}R\subseteq A$ and $\mathrm{ran}R\subseteq B$.

Let $R$ and $S$ be relations and $A$ a set. Then each of

$\{(b,a):(a,b)\in R\},\{(a,c):\mathrm{\exists }b((a,b)\in R\wedge (b,c)\in S)\},\{(a,b)\in R:a\in A\}$

is a set; the first is included in $\mathrm{ran}R\times \mathrm{dom}R$, the second in $\mathrm{dom}R\times \mathrm{ran}S$, and the third in $R$.

Let $R$ and $S$ be relations (Relation, $\mathrm{dom}R$, $\mathrm{ran}R$, $\mathrm{fld}R$, and the specialisations "relation from $A$ to $B$" and "relation on $A$") and let $A$ be a set. By For relations $R$ and $S$ and a set $A$, the collections $\{(b,a):(a,b)\in R\}$, $\{(a,c):\mathrm{\exists }b((a,b)\in R\wedge (b,c)\in S)\}$ and $\{(a,b)\in R:a\in A\}$ are sets the three collections below are sets, and each is again a relation, since each of its elements is an ordered pair (The Kuratowski ordered pair $(a,b):=\{\{a\},\{a,b\}\}$):

• the inverse $R^{-1}:=\{(b,a):(a,b)\in R\}$;
• the composite $S\circ R:=\{(a,c):\mathrm{\exists }b((a,b)\in R\wedge (b,c)\in S)\}$;
• the restriction $R\upharpoonright A:=\{(a,b)\in R:a\in A\}$.

Membership in each is exactly as written: $(b,a)\in R^{-1}$ holds if and only if $(a,b)\in R$; $(a,c)\in S\circ R$ holds if and only if $(a,b)\in R$ and $(b,c)\in S$ for some $b$; and $(a,b)\in R\upharpoonright A$ holds if and only if $(a,b)\in R$ and $a\in A$.

• The order in $S\circ R$. $S\circ R$ applies $R$ first and $S$ second. This is the convention that makes the composite of functions read $(g\circ f)(x)=g(f(x))$, and it is the one the rest of the library uses. The opposite convention exists in the literature and would reverse every composite written here.

• Restriction cuts the domain, not the range. $R\upharpoonright A$ keeps the pairs of $R$ whose first coordinate lies in $A$ and discards the rest; $A$ need not be included in $\mathrm{dom}R$, and $\mathrm{dom}(R\upharpoonright A)=\mathrm{dom}R\cap A$.

Let $R$ be a relation (Relation, $\mathrm{dom}R$, $\mathrm{ran}R$, $\mathrm{fld}R$, and the specialisations "relation from $A$ to $B$" and "relation on $A$") and let $A$ and $B$ be sets. The image of $A$ under $R$ and the preimage of $B$ under $R$ are

$R[A]:=\{b\in \mathrm{ran}R:\mathrm{\exists }a(a\in A\wedge (a,b)\in R)\},R^{-1}[B]:=\{a\in \mathrm{dom}R:\mathrm{\exists }b(b\in B\wedge (a,b)\in R)\},$

sets by The Axiom Schema of Separation: for each formula $\phi$, $\mathrm{\forall }\bar{p}\mathrm{\forall }x\mathrm{\exists }y\mathrm{\forall }z(z\in y\leftrightarrow (z\in x\wedge \phi (z,\bar{p})))$ applied inside $\mathrm{ran}R$ and $\mathrm{dom}R$ respectively. Thus $b\in R[A]$ holds if and only if $(a,b)\in R$ for some $a\in A$, and $a\in R^{-1}[B]$ holds if and only if $(a,b)\in R$ for some $b\in B$ (The Kuratowski ordered pair $(a,b):=\{\{a\},\{a,b\}\}$).

The notation is consistent: applying the first clause to the inverse relation $R^{-1}$ of The inverse relation $R^{-1}$, the composite $S\circ R$, and the restriction $R\upharpoonright A$ gives $R^{-1}[B]=\{a\in \mathrm{ran}(R^{-1}):\mathrm{\exists }b(b\in B\wedge (b,a)\in R^{-1})\}$, which has exactly the elements just described, since $(b,a)\in R^{-1}$ says $(a,b)\in R$ and $\mathrm{ran}(R^{-1})=\mathrm{dom}R$.

• The bracket is not an application. $R[A]$ is the set of things related to something in $A$; it is written with square brackets precisely so that it is never confused with a value $R(a)$, which for a general relation does not exist. Even for a function, $f[S]$ and $f(S)$ mean different things, and only the bracket form is used here.

• Image and range. Taking $A:=\mathrm{dom}R$ gives $R[\mathrm{dom}R]=\mathrm{ran}R$, and taking $A:=\mathrm{\varnothing }$ gives $R[\mathrm{\varnothing }]=\mathrm{\varnothing }$, since no $a$ lies in $\mathrm{\varnothing }$.

Let $A$ be a set. The identity relation and the membership relation on $A$ are

${\mathrm{\Delta }}_A:=\{(a,b)\in A\times A:a=b\},{\in }_A:=\{(a,b)\in A\times A:a\in b\},$

sets by The Axiom Schema of Separation: for each formula $\phi$, $\mathrm{\forall }\bar{p}\mathrm{\forall }x\mathrm{\exists }y\mathrm{\forall }z(z\in y\leftrightarrow (z\in x\wedge \phi (z,\bar{p})))$ applied inside $A\times A$ (The Cartesian product $A\times B:=\{z\in \mathcal{P}(\mathcal{P}(A\cup B)):\mathrm{\exists }a\in A\mathrm{\exists }b\in Bz=(a,b)\}$), and relations on $A$ in the sense of Relation, $\mathrm{dom}R$, $\mathrm{ran}R$, $\mathrm{fld}R$, and the specialisations "relation from $A$ to $B$" and "relation on $A$". Thus $(a,b)\in {\mathrm{\Delta }}_A$ holds if and only if $a=b$ and $a\in A$, and $(a,b)\in {\in }_A$ holds if and only if $a\in b$ and both lie in $A$ (The Kuratowski ordered pair $(a,b):=\{\{a\},\{a,b\}\}$).

• ${\mathrm{\Delta }}_A$ carries the set $A$ with it. ${\mathrm{\Delta }}_A$ and ${\mathrm{\Delta }}_B$ are different relations when $A\mathrm{\ne }B$, because $\mathrm{dom}{\mathrm{\Delta }}_A=\mathrm{ran}{\mathrm{\Delta }}_A=A$. That is what makes ${\mathrm{\Delta }}_A$ usable as a neutral element for composition on the left and on the right, with the correct set in each position.

• The membership relation is the one Foundation constrains. ${\in }_A$ is set membership restricted to $A$, so Under Foundation, $x\mathrm{\notin }x$ for every set $x$, there are no sets with $x\in y\in x$, and there are no sets with $x\in y\in z\in x$ says that it has no cycle of length one, two or three.

Let $R$, $S$, $T$ be relations and let $A$, $B$ be sets. Then

• (i) $T\circ (S\circ R)=(T\circ S)\circ R$;
• (ii) $(S\circ R{)}^{-1}=R^{-1}\circ S^{-1}$;
• (iii) $(R^{-1}{)}^{-1}=R$;
• (iv) $\mathrm{dom}(R^{-1})=\mathrm{ran}R$ and $\mathrm{ran}(R^{-1})=\mathrm{dom}R$;
• (v) if $R$ is a relation from $A$ to $B$, then ${\mathrm{\Delta }}_B\circ R=R$ and $R\circ {\mathrm{\Delta }}_A=R$.

Let $R$ and $S$ be relations and $A$, $B$ sets. Then

• (i) $R[A\cup B]=R[A]\cup R[B]$;
• (ii) $R[A\cap B]\subseteq R[A]\cap R[B]$;
• (iii) $R[A]\setminus R[B]\subseteq R[A\setminus B]$;
• (iv) if $A\subseteq B$ then $R[A]\subseteq R[B]$;
• (v) $(S\circ R)[A]=S[R[A]]$.

Let $A$ be a set and let $R$ be a relation on $A$, that is $R\subseteq A\times A$ (Relation, $\mathrm{dom}R$, $\mathrm{ran}R$, $\mathrm{fld}R$, and the specialisations "relation from $A$ to $B$" and "relation on $A$", The Cartesian product $A\times B:=\{z\in \mathcal{P}(\mathcal{P}(A\cup B)):\mathrm{\exists }a\in A\mathrm{\exists }b\in Bz=(a,b)\}$). Then $R$ is:

• reflexive on $A$ when $(a,a)\in R$ for every $a\in A$;
• irreflexive when $(a,a)\mathrm{\notin }R$ for every $a\in A$;
• symmetric when $(a,b)\in R$ implies $(b,a)\in R$, for all $a,b\in A$;
• asymmetric when $(a,b)\in R$ implies $(b,a)\mathrm{\notin }R$, for all $a,b\in A$;
• antisymmetric when $(a,b)\in R$ and $(b,a)\in R$ imply $a=b$, for all $a,b\in A$;
• transitive when $(a,b)\in R$ and $(b,c)\in R$ imply $(a,c)\in R$, for all $a,b,c\in A$;
• connex on $A$ when, for all $a,b\in A$, $(a,b)\in R$ or $(b,a)\in R$.