Functions and Relations

You can read the LaTeX document online (for the latest updated chapters) from the link: https://pdf.gaomj.cn/?file=get.php?f=set-theory

Functions and Relations In this chapter some fundamental and widely used concepts are introduced. As in Chapter 1, we first discuss them without axiomatic formalisation, and then justify the definitions and verify the properties using axiomatic methods. We will encounter the axiom of choice in this chapter.

Contents
Contents
 1.  Functions
 2.  Relations
   2.1.  Ordered Pairs
   2.2.  Relations and Equivalences
   2.3.  Equivalences and Mappings
 3.  * Functions as Relations
 4.  Axiom of Choice: A First View

1. Functions Informally, a function f:X\to Y is a rule f that assigns to each element x\in X a unique element y\in Y, denoted by y=f(x)\in Y. The set X is called the domain of f, and the set of values consisting of all f(x) for x\in X is called the range or image of f.

In mathematics, functions can also be named as maps, mappings, etc. In different areas it is customary to use different names.

Now we continue to define some useful concepts related to functions. Let f:X\to Y be a mapping.

1. The image of a set A\subseteq X under f is the set
   \[
   f(A):=\{y\in Y\mid \exists x\, [(x\in A)\wedge (y=f(x))]\}.
   \]
2. The inverse image or pre-image of a set B\subseteq Y under f is the set
   \[
   f^{-1}(B):=\{x\in X\mid f(x)\in B\}.
   \]
3. The mapping f is injective, or one-to-one, or is an injection if for any x _ 1,x _ 2\in X,
   \[(f(x _ 1)=f(x _ 2))\Rightarrow (x _ 1=x _ 2).\]
4. The mapping f is surjective, or onto, or is a surjection if for any y\in Y, there exists at least one x\in X such that f(x)=y, i.e., f(X)=Y.
   
5. The mapping f is bijective, or is a bijection if it is both injective and surjective. In this case it is called a one-to-one correspondence.
   
6. If f is a bijection, for each y\in Y there exists one and only one x\in X such that f(x)=y. A mapping f^{-1}:Y\to X then defined by y\mapsto x if f(x)=y is the inverse mapping of f.
   
7. Let A\subset X. The restriction of f to A is the mapping f| _ A:A\to Y defined by f| _ A(x):=f(x) for all x\in A.
   
8. Let A\supseteq X. An extension of f is a mapping g:A\to Y if g| _ X=f.
   
9. Let g:Y\to Z be another mapping. The composition of f and g is the mapping g\circ f:X\to Z defined by (g\circ f)(x):=g(f(x)) for all x\in X.

We have the following elementary properties of inverse mappings and compositions. They will be discussed in detail in Section 3.

In the above propositions, we have used the notion of identity mapping \operatorname{Id}:X\to X defined by \operatorname{Id}(x):=x for all x\in X.

2. Relations The notion of a function has been informally described. It is natural and easy to understand. However it is not satisfactory from the axiomatic point of view and sort of like a circular definition: To define a function is to define a correspondence but a correspondence is undefined unless we define it as a function. Therefore we shall consider the definitions in the language of set theory.

2.1. Ordered Pairs An unordered pair can be defined as a pair set \{a, b\} due to the property \{a,b\}=\{b,a\}.

Now we want another notion (a,b) consisting of a,b such that (a,b)\neq (b,a) generally, i.e., an ordered pair. A possible candidate is \{a, \{b\}\}. However, the problem is that it does not encode the information uniquely. For example, a=b=\{\varnothing\} gives \{a,\{b\}\}=\{\{\varnothing\},\{\{\varnothing\}\}\}, while a=\{\{\varnothing\}\} and b=\varnothing gives the same result. Therefore, a good definition should have the property that (a,b)=(c,d) implies a=c and b=d.

There are several possible definitions with this property. We adopt the following one that is commonly used today.

We just need to prove the "\Rightarrow" part. Suppose (a,b)=(c,d), i.e., \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}. Then \{a\}=\{c\} or \{a\}=\{c,d\}. If \{a\}=\{c,d\}, then c=d=a. Hence either \{a,b\}=\{c\} or \{a,b\}=\{c,d\} leads to a=b=c=d. In this case the theorem holds. If \{a\}=\{c\}, then a=c. In this case:

1. If \{a,b\}=\{c\} we again obtain a=b=c=d.
   
2. If \{a,b\}=\{c,d\}, then b=c or b=d, both imply (a=c \wedge b=d). □

.
Now we can have the following definition.

Of course from the axiomatic point of view, this definition is not legal until we verify A\times B is a set.

By definition of ordered pairs, the elements of (a,b), i.e. \{a\} and \{a,b\}, are subsets of A\cup B if a\in A and b\in B. Alternatively, we can say they are elements of the power set \mathcal{P}(A\cup B). Thus, (a,b) itself, is an subset of \mathcal P\mathcal{P}(A\cup B). By subset axioms,
\[\{x\in\mathcal P\mathcal P(A\cup B)\mid \exists a\exists b\, (a\in A\wedge b\in B\wedge x=(a,b))\}\]is a set, which is exactly A\times B.

2.2. Relations and Equivalences A relation is nothing more than a set of ordered pairs.

We must check both A,B are sets: (a,b)=\{\{a\},\{a,b\}\}\in\mathcal R\Rightarrow\{a,b\}\in\bigcup\mathcal R\Rightarrow a,b\in\bigcup\bigcup\mathcal R. Thus we can apply the pair axiom.

Suppose now we want a partition of a set A into several disjoint subsets. This naturally leads to a relation on A. If a relation \mathcal R on A is defined such that for any a,b\in A, a\mathcal R b means a and b belong to the same subset, then it can be seen that \mathcal{R} has the following properties:

1. \mathcal R is reflexive, i.e., \forall a\in A\, (a\mathcal R a).
   
2. \mathcal{R} is symmetric, i.e., \forall a,b\in A\, (a\mathcal R b \Rightarrow b\mathcal R a).
   
3. \mathcal{R} is transitive, i.e., \forall a,b,c\in A\, [(a\mathcal R b \wedge b\mathcal R c)\Rightarrow (a\mathcal R c)].

Any relation satisfying these three properties is called an equivalence relation.

Given a relation \mathcal R which is symmetric and transitive, with domain X and range Y, we have
\[ \mathcal R\subseteq X\times Y\subseteq (X\cup Y)\times (X\cup Y).\]

If x\in X, then there is some y\in Y such that x\mathcal R y, and by symmetry y\mathcal R x. We conclude that x\mathcal R x by transitivity. Similarly, for any y\in Y, we have y\mathcal R y. Therefore \mathcal R is reflexive on X\cup Y. We have proved the following theorem.

This theorem deserves special caution. Consider the \leqslant relation on the set of complex numbers \mathbb C, which is both symmetric and transitive with domain \mathbb R, the set of real numbers, and range \mathbb R. However, it is not reflexive on \mathbb C since for an imaginary number the inequality relation is not defined.

Since [a] is a subset of the range of \mathcal R, it is a set by subset axioms. The following proposition is easy to verify.

We have known the second part of the theorem holds. For the first part, each equivalence class of A is nonempty since x\in[x] for any x\in A, and is a subset of A. The union of all equivalence classes is A, so it suffices to show that the equivalence classes are disjoint. This is true by the previous proposition. □
.

For an equivalence relation on A, we can define the quotient set as the set of all equivalence classes: A/\mathcal R := \{[a] \mid a\in A\}. There is a natural surjection
\begin{align*}
\pi : A & \to A/\mathcal R,\\
a & \mapsto [a].
\end{align*}

For example, the set of integers has a partition {[0],[1]}, containing respectively all the even integers and odd integers. For an odd number n, \pi(n)=[1]; for an even number m, \pi(m)=[0].

2.3. Equivalences and Mappings Let f:X\to Y be a mapping. Then f gives us an equivalence relation on X defined by a\sim b if f(a)=f(b). There is an injection \widehat{f}:{(X{/}\sim)}\to Y defined by \widehat{f}([a])=f(a). We have
\[
f=\widehat{f}\circ \pi.
\]
Now given an equivalence relation and a mapping f:A\to A, we ask: Is there a mapping defined on the qiotient set, i.e., \widehat{f}:{A/\sim}\to {A/\sim}, such that for any a\in A,
\[\widehat{f}([a])=[f(a)]?\]

This is not true generally. For example, let A=\{a,b,c,d\} and the equivalence be determined by the partition \{1,2\}\cup\{3,4\}. Then it is a necessary condition that [f(1)]=[f(2)] and [f(3)]=[f(4)], i.e., the mapping preserves the equivalence. We have the following general theorems. They are easy to prove with the help of Propsition 12.

3. * Functions as Relations

We now return to the axiomatic formalisation of functions, i.e., mappings. To define a function is equivalent to define a set of ordered pairs (x,y), but we need one more condition: Given any x\in X, there is a unique y\in Y such that (x,y) is in this set.

It is customary to use the letter f to denote such a functional relation \mathcal R, and we write f(x) to mean the unique y such that x\mathcal{R}y.

A quick observation is that if two mappings f,g have the same domain and f(x)=g(x) for all x in this domain then f=g.

By subset axioms, it is easily established that the sets in the definitions of Section 1 exist. Moreover, the inverse of a mapping has its gerneralized form.

This definition does not require that f be a bijection, nor does it imply that f^{-1} is a mapping. It can be seen that the domain and image of f^{-1} are respectively the image and domain of f, and that f^{-1} is a mapping if and only if f is "injective" while f is a mapping if and only if f^{-1} is "injective". (We have not defined the notion of "injective" relation but it can be easily understood as the gerneralized version of injective mappings.)

Now we can define the composition of two mappings or two relations.

Proof. It is easy to verify g\circ f is a mapping. Suppose x(g\circ f)z _ 1 and x(g\circ f)z _ 2. Then there exist y _ 1,y _ 2 such that xfy _ 1\wedge y _ 1gz _ 1 and xfy _ 2\wedge y _ 2gz _ 2. Since f is a mapping, y _ 1=y _ 2, and therefore since g is a mapping, z _ 1=z _ 2. Hence g\circ f is a mapping.

Next, if x is in the domain of g\circ f and (g\circ f)(x)=z, then there is a y such that xfy\wedge ygz. But xf(f(x)) and f(x)g[g(f(x))], so x(g\circ f)[g(f(x))]. Thus, due to the fact that g\circ f is a mapping, (g\circ f)(x)=g(f(x)).

If x\in X such that f(x)\in Y', then by the fact that x(g\circ f)[g(f(x))], x is in the domain of g\circ f.□
.

We now verify the (generalized) propositions in Section 1, which are stated here again.

Proof. First, suppose f is a relation with domain X and range Y. Then f^{-1} is a relation with domain Y and range X, so (f^{-1})^{-1} is a relation with domain X and range Y. Since (f^{-1})^{-1} and f have the same domain, and xfy\Leftrightarrow yf^{-1}x\Leftrightarrow x(f^{-1})^{-1}y for all x\in X and y\in Y, we conclude that (f^{-1})^{-1}=f.

The associativity of compositions: both sides of equality have a common domain, and are mappings. Moreover, they both take value h(g(f(x))) for any x in the domain.

If g is the inverse bijection of the bijection f:X _ 1\to Y _ 1, then g\circ f is a mapping with domain \{x\in X _ 1\mid f(x)\in X _ 2=Y _ 1\}=X _ 1, and (g\circ f)(x)=g(f(x))=x. Therefore g\circ f=\operatorname{Id} _ {X _ 1}, and similarly f\circ g=\operatorname{Id} _ {X _ 2}.

Suppose g\circ f=\operatorname{Id} _ {X _ 1}. We have for any x\in X _ 1 there is a y\in Y _ 1 such that f(x)=y, y\in X _ 2 and g(y)=x. Therefore Y _ 1\subseteq X _ 2 and X _ 1\subseteq Y _ 2. Similarly Y _ 2\subseteq X _ 1 and X _ 2\subseteq Y _ 1 if we suppose further f\circ g=\operatorname{Id} _ {X _ 2}. Hence X _ 1=Y _ 2 and Y _ 1=X _ 2.

Recall the definition of f^{-1} is \{(y,x)\mid y=f(x)\}. Since g(y)=x for x\in X _ 1, it holds that g\subseteq f^{-1}, and by f(x)gx we know f^{-1}\subseteq g. Thus g=f^{-1}.

Since g(f(X _ 1))=X _ 1=Y _ 2, g is surjective. It is also injective because f is a mapping if and only if f^{-1}=g is injective. Hence g is a bijection, and the same argument applies to f.

We finally shows (g\circ f)^{-1}=f^{-1}\circ g^{-1}. We have
\begin{align*}
& z(g\circ f)^{-1}x \Leftrightarrow x(g\circ f)z \Leftrightarrow \exists y\, (xfy\wedge ygz)\\
\Leftrightarrow{} & \exists y\, (zg^{-1}y\wedge yf^{-1}x)
\Leftrightarrow{} z(f^{-1}\circ g^{-1})x.
\end{align*}

The propositions are proved.□

4. Axiom of Choice: A First View

Given a mapping f, the inverse is not necessarily a mapping. In such a case can we always find a mapping that behaves like the normal inverse mapping?

Suppose f(x)=y for some x,y. We want a mapping g such that g(y)=x. A natural requirement is that for this y there is only one x such that f(x)=y, i.e., f is injective.

Suppose f(x _ 1)=f(x _ 2)=y. Then x _ 1=g(f(x _ 1))=g(y)=g(f(x _ 2))=x _ 2, so f injective. Conversely, Suppose f is injective. We have known in this case f^{-1} is a mapping, which is almost what we want. We have to define the value of it on Y\setminus f(X), which can be done by assigning to all of them f(x) for some x\in X. Since X is nonempty, this is always possible.

Such a mapping g is called a left inverse of f. We naturally ask whether it holds that there exists a right inverse h:Y\to X such that f\circ h=\operatorname{Id} _ Y if and only if f is surjective.

If the right inverse h of f exists, then for any y\in Y, y=f(h(y))=f(x) where x=h(y). Hence f is surjective.

Conversely we now suppose f is surjective. Let y _ 1\in Y and X _ 1=f^{-1}(y _ 1)\neq\varnothing. Then there exists x _ 1\in X _ 1 such that f(x _ 1)=y _ 1. We obtain an ordered pair (y _ 1, x _ 1). Now we choose a new y _ 2\in Y, and choose x _ 2 similarly. We obtain an ordered pair (y _ 2,x _ 2), and then form a pair set \{(y _ 1,x _ 1),(y _ 2,x _ 2)\}. Continue this process, in which an ordered pair and a pair set are formed, until the elements of Y are exausted. The final set \{(y _ 1,x _ 1),\dots,(y _ n,x _ n)\} is the mapping we seek.

Appearently this construction break down when the elements of Y cannot be exhausted. It turns out that although for any y\in Y there exists at least one x this is not by itself enough to allow for the construction of a mapping h:y\mapsto x. A new axiom is needed if we want to proceed.

The axiom of choice assures us of the existence of such a mapping. A specific form of this axiom is now stated.

7. Axiom of Choice, I. For any relation \mathcal R with domain X, there is a mapping f on X such that f\subseteq \mathcal R.

We can now prove the "if" part. By axiom of choice and the surjectivity of f, there exists a mapping h on Y such that h\subseteq f^{-1}. For any y\in Y we have yf^{-1}h(y)\Rightarrow h(y)fy\Rightarrow f(h(y))=y.□

Sets as Exponents

Consider two sets X,Y. We can form a set consisting of mappings f:X\to Y. A mapping from X into Y is a subset of X\times Y, and therefore an element of \mathcal P(X\times Y). By subset axioms, we can form such a set, denoted by Y^X, i.e.,
\[ Y^X:=\{f\mid f:X\to Y\}. \]
A common example is the set \{0,1\}^A for some set A, the set of all mappings f:A\to\{0,1\}. It is usually denoted by 2^A as well.