3. Correspondences

1. Graphs and correspondences

is true.

If G is a graph, the relation $(x, y) \in G$ is expressed by saying that "$y$ corresponds to $x$ under G".

Let $\boldsymbol{R}\{x, y\}$ be a relation, where $x$ and $y$ are distinct letters. Let $\boldsymbol{G}$ be a letter, distinct from $x$ and $y$, which does not appear in $\boldsymbol{R}$. If the relation

is true, the relation $\boldsymbol{R}$ is said to have a graph (with respect to the letters $x$ and $y$). The graph $\boldsymbol{G}$ is then unique by virtue of the axiom of extent, and is called the graph of $\boldsymbol{R}$ with respect to $x$ and $y$.

¶ Let $Z$ be a letter, distinct from $x$ and $y$, which does not appear in $R$. If the relation

is true, then $R$ has a graph; we may take this graph to be the set of ordered pairs $z$ such that $z \in Z$ and $R \{ \mathrm{pr}_1 z,\ \mathrm{pr}_2 z \}$ ($z$ being a letter distinct from $x$, $y$, $Z$ which does not appear in $R$). This condition is satisfied if we know a term $T$, which does not contain either $x$ or $y$, such that $R \Rightarrow ((x,\ y) \in T)$ is true.

where G is a graph such that $\mathrm{pr}_1 \mathrm{G} \subset \mathrm{A}$ and $\mathrm{pr}_2 \mathrm{G} \subset \mathrm{B}$. G is said to be the graph of $\Gamma$, A is the source, and B the target of $\Gamma$.

If $(x,\ y) \in \mathrm{G}$, we say that "$y$ corresponds to $x$ in the correspondence $\Gamma$". For each $x \in \mathrm{pr}_1 \mathrm{G}$ the correspondence $\Gamma$ is said to be defined at $x$, and $\mathrm{pr}_1 \mathrm{G}$ is called the domain of $\Gamma$; each $y \in \mathrm{pr}_2 \mathrm{G}$ is said to be a value taken by $\Gamma$, and $\mathrm{pr}_2 \mathrm{G}$ is called the range of $\Gamma$.

If $R \{ x, y \}$ is a relation which has a graph $G$ (with respect to the letters $x$, $y$), and if $A$, $B$ are two sets such that $\mathrm{pr}_1 G \subset A$ and $\mathrm{pr}_2 G \subset B$, we say that $R$ is a relation between an element of $A$ and an element of $B$ (with respect to the letters $x$, $y$). The correspondence $\Gamma = (G, A, B)$ is said to be the correspondence between $A$ and $B$ defined by the relation $R$ (with respect to $x$ and $y$).

Let G be a graph and let X be a set. The relation

implies $(x, y) \in G$ and therefore has a graph $G'$. The second projection of $G'$ consists of all the objects which correspond under G to objects of X.

It follows immediately from C43 (Chapter I, § 5, no. 1) that the relation $y \in G\langle \{x\} \rangle$ is equivalent to $(x, y) \in G$. If G and $G'$ are two graphs, the relation $G \subset G'$ is thus equivalent to

If $\Gamma = (\mathrm{G}, \mathrm{A}, \mathrm{B})$ is a correspondence between A and B, then for every $x \in \mathrm{A}$ the section of G at $x$ is also called the section of $\Gamma$ at $x$ and is denoted by $\Gamma\langle\{x\}\rangle$ (or $\Gamma(x)$).

2. Inverse of a correspondence

Let G be a graph and $\mathrm{A} = \mathrm{pr}_1\mathrm{G}$, $\mathrm{B} = \mathrm{pr}_2\mathrm{G}$ its projections. The relation $(y, x) \in \mathrm{G}$ implies $(x, y) \in \mathrm{B} \times \mathrm{A}$; this relation therefore has a graph which consists of all ordered pairs $(x, y)$ such that $(y, x) \in \mathrm{G}$.

For every set X, $\overset{-1}{\mathrm{G}}\langle\mathrm{X}\rangle$ is called the inverse image of X under G.

¶ It is clear that the inverse of $\overset{-1}{\mathrm{G}}$ is G, and that

In particular, if X, Y are two sets, we have

A graph G is said to be symmetric if $\overset{-1}{\mathrm{G}} = \mathrm{G}$.

¶ Let $\Gamma = (\mathrm{G}, \mathrm{A}, \mathrm{B})$ be a correspondence between A and B. Since $\mathrm{pr}_1\overset{-1}{\mathrm{G}} \subset \mathrm{B}$ and $\mathrm{pr}_2\overset{-1}{\mathrm{G}} \subset \mathrm{A}$, the triple $(\overset{-1}{\mathrm{G}}, \mathrm{B}, \mathrm{A})$ is a correspondence between B and A, called the inverse of the correspondence $\Gamma$, and denoted by $\overset{-1}{\Gamma}$. For every subset Y of B, the image $\overset{-1}{\Gamma}\langle\mathrm{Y}\rangle$ of Y under $\overset{-1}{\Gamma}$ is also called the inverse image of Y under $\Gamma$. Clearly the inverse of $\overset{-1}{\Gamma}$ is $\Gamma$.

3. Composition of two correspondences

Let G, G′ be two graphs. Let A denote the set $\mathrm{pr}_1\mathrm{G}$ and let C denote the set $\mathrm{pr}_2\mathrm{G}'$. The relation $(\exists y)((x, y) \in \mathrm{G}$ and $(y, z) \in \mathrm{G}')$ implies that $(x, z) \in \mathrm{A} \times \mathrm{C}$, and therefore has a graph with respect to $x$ and $z$.

It follows immediately from Proposition 5 that if X is a subset of A we have $(\Gamma' \circ \Gamma)\langle \mathrm{X}\rangle = \Gamma'\langle \Gamma\langle \mathrm{X}\rangle\rangle$. Furthermore, since the target of $\overset{-1}{\Gamma'}$ is the same as the source of $\overset{-1}{\Gamma}$, the inverse of $\Gamma' \circ \Gamma$ is $\overset{-1}{\Gamma} \circ \overset{-1}{\Gamma'}$, by Proposition 3.

Clearly we have $\mathrm{pr}_1\Delta_\mathrm{A} = \mathrm{pr}_2\Delta_\mathrm{A} = \mathrm{A}$. The correspondence

is called the identity correspondence on A; it is its own inverse.

¶ If $\Gamma$ is a correspondence between A and B and if $\mathrm{I}_\mathrm{A}$, $\mathrm{I}_\mathrm{B}$ are the identity correspondences on A, B, respectively, then $\Gamma \circ \mathrm{I}_\mathrm{A} = \mathrm{I}_\mathrm{B} \circ \Gamma = \Gamma$.

4. Functions

If $f$ is a function, F its graph, and $x$ an element of the domain of $f$, the relation $y = f(x)$ is then equivalent to $(x, y) \in \mathrm{F}$ (Chapter I, § 5, no. 3, criterion C46).

5. Restrictions and extensions of functions

Two functions $f$ and $g$ are said to agree (or coincide) on a set E if E is contained in the domains of $f$ and $g$ and if $f(x)=g(x)$ for all $x\in E$. Two functions which have the same graph agree on their domain. To say that $f=g$ is to say that $f$ and $g$ have the same domain A and the same target B, and that they agree on A.

¶ Let $f=(F,A,B)$ and $g=(G,C,D)$ be two functions. To say that $F\subset G$ is to say that the domain A of $f$ is contained in the domain C of $g$ and that $g$ agrees with $f$ on A. If also $B\subset D$, then $g$ is said to be an extension of $f$ (more precisely, an extension of $f$ to C), and $g$ is said to extend $f$ (to C). When $g$ is called a family of elements of D, $f$ is said to be a subfamily of $g$.

¶ Let $f$ be a function and let A be a subset of the domain of $f$. It is immediate that the relation “$x\in A$ and $y=f(x)$” has a graph G with respect to $x$ and $y$, that this graph is functional, and that A is its domain; the function whose graph is G, which has the same target as $f$, is called the restriction of $f$ to $A$, and is sometimes denoted by $f|A$. A function is an extension of any of its restrictions. If two functions $f$, $g$ have the same target and agree on a set $E$, then their restrictions to $E$ are equal.

6. Definition of a function by means of a term

C54. Let $T$, $A$ be two terms and let $x$, $y$ be distinct letters. Suppose that $x$ does not appear in $A$ and that $y$ does not appear in either $T$ or $A$. Let $R$ be the relation “$x \in A$ and $y = T$”. The relation $R$ has a graph $F$ with respect to the letters $x$ and $y$. This graph is functional; its first projection is $A$, and its second projection is the set of objects of the form $T$ for $x \in A$ (§ 1, no. 6). For every $x \in A$ we have $F(x) = T$.

Let $B$ be the set of objects of the form $T$ for $x \in A$. Then

since the assembly denoted by $A \times B$ contains neither $x$ nor $y$, $R$ has a graph $F$ with respect to the letters $x$ and $y$ (no. 1). It is clear that the relation

implies $y = y'$, and hence $F$ is a functional graph. The remaining statements are evident.

¶ If $C$ is a set which contains the set $B$ of objects of the form $T$ for $x \in A$ (where $y$ does not appear in $C$), then the function $(F,A,C)$ is also denoted by the notation $x \to T$ ($x \in A$, $T \in C$); the corresponding assembly in formal mathematics contains neither $x$ nor $y$ and does not depend on the choice of the letter $y$ satisfying the above conditions. When the context is sufficiently explicit we shall permit ourselves the notations $x \to T(x \in A)$, $(T)_{x \in A}$, or $x \to T$, and sometimes simply $T$ or $(T)$. Thus we may speak of “the function $x^3$”, if the context indicates clearly that we mean the mapping $x \to x^3$ of the set of complex numbers into itself. \

Examples

7. Composition of two functions. Inverse function

Instead of saying that $f$ is surjective, we sometimes say that $f$ is a mapping of A onto B, or that it is a parametric representation of B by means of A (in which case A is called the set of parameters of the representation, and the elements of A are called parameters). If $f$ is bijective, we sometimes say that f puts A and B in one-to-one correspondence. A bijection of A onto A is called a permutation of A.

Examples

8. Retractions and sections

Instead of retraction (resp. section) the phrase left-inverse (resp. right-inverse) is sometimes used.

¶ If $f$ is injective (resp. surjective) and if $r$ (resp. $s$) is a retraction (resp. section) of $f$, then $f$ is a section (resp. retraction) of $r$ (resp. $s$). Hence a retraction is surjective and a section is injective.

¶ If $f$ is surjective and if $s$, $s'$ are two sections of $f$ such that $s(\mathrm{B}) = s'(\mathrm{B})$, then $s = s'$; for if $x \in \mathrm{B}$, there exists $y \in \mathrm{B}$ such that $s(x) = s'(y)$, and we have $x = f(s(x)) = f(s'(y)) = y$, so that $s(x) = s'(x)$ and consequently $s = s'$. Thus a section $s$ is uniquely determined by the set $s(\mathrm{B})$. By abuse of language, the set $s(\mathrm{B})$ is sometimes called a section of $f$.