Mathematical Proof/Functions

Introduction

In the previous chapter, we have discussed the concept of Template:Colored em. There are not much restrictions on the relations. For instance, for a relation from set $A$ to set $B$, every element of $A$ can be related to no elements of $B$, exactly one element of $B$, or multiple elements of $B$. In this chapter, we will focus on a particular type of relations from set $A$ to set $B$ where Template:Colored em element in $A$ is related to Template:Colored em (or a Template:Colored em) element of $B$.

You should have encountered the concept of Template:Colored em before, e.g. a function defined by $f(x)=x^2$ gives you a value of $f(x)$ for every given value of $x$. The functions you have encountered are likely to be in the above form, i.e. in the form of an equation. Also, the value of $x$ and $f(x)$ are likely to be real numbers.

But we can generalize such ideas to more general situations where $x$ and $f(x)$ are not necessarily real numbers (e.g., they can be elements of certain sets), and the functions need not be expressed by a formula like above. As a result, the concept and definition of functions discussed here may seem foreign to you, and look quite different from what you have previously learnt about functions.

Definitions

Template:Colored definition Template:Colored remark Template:Colored exercise Template:Colored example Template:Colored example Template:Colored example Template:Colored exercise We should be aware that the codomain of a function is not necessarily the same as the range of a function. The following is the definition of the Template:Colored em of a function (same as the definition for a relation). Template:Colored definition Template:Colored remark Template:Colored example Template:Colored exercise Template:Colored example Template:Colored remark Template:Colored example Template:Colored exercise Since the domain and codomain, in addition to the "way" of the mapping, all affect the "behaviour" and properties of a function, it is natural to incorporate all these features into the definition of Template:Colored em of functions: Template:Colored definition Template:Colored exercise Template:Colored example Template:Colored exercise

Injective, surjective and bijective functions

In this section, we will discuss some important properties that a function may possess, namely injectivity, surjectivity, and bijectivity. Template:Colored definition Template:Colored remark Template:Colored exercise Template:Colored example Template:Colored example Template:Colored example Template:Colored exercise Template:Colored definition Template:Colored remark Template:Colored exercise Template:Colored example Template:Colored example Template:Colored definition Template:Colored remark Template:Colored exercise Template:Colored example Template:Colored example Template:Colored example Template:Colored exercise Template:Colored exercise Template:Colored exercise

Composition of functions

Let $A,B$ and $C$ be nonempty sets, and let $f:A\to B$ and $g:B\to C$ be two functions. In this section, we are going to discuss a way to create a new function from "combining" the two functions $f$ and $g$, called their Template:Colored em: Template:Colored definition Template:Colored remark Template:Colored example Template:Colored remark Template:Colored example Template:Colored remark Although the composition of functions is not commutative, it is Template:Colored em. Template:Colored theorem

Proof. First, since $g\circ f$ is a function from $A$ to $C$, it follows that $h\circ (g\circ f)$ is a function from $A$ to $D$. Similarly, since $h\circ g$ is a function from $B\to D$, it follows that $(h\circ g)\circ f$ is function from $A$ to $D$.

It now remains to prove that both functions map every element $a\in A$ into the same image in $D$. For every $a\in A$, $$(h\circ (g\circ f))(a)=h((g\circ f)(a))=h(g(f(a))).$$ (a bracket for $g\circ f$ means "grouping" $g$ and $f$ first, that is, we regard $g\circ f$ as a function first. To understand this more easily, one may write $f_1$ instead of "$g\circ f$" above.)

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

$◻$

Template:Colored example Now, let us study some results that are related to the composition, injectivity, surjectivity, and bijectivity. Template:Colored proposition

Proof. For (a), assume that $f$ and $g$ are injective. Then, for every $x,y\in A$ $$\begin{array}{cc}g\circ f(x)=g\circ f(y)& ⟹g(f(x))=g(f(y))\\ & ⟹f(x)=f(y)& (g\text{ is injective})\\ & ⟹x=y.& (f\text{ is injective})\\ \end{array}$$ For (b), assume that $f$ and $g$ are injective. Then, for every $c\in C$, since $g$ is surjective, there exists $b\in B$ such that $g(b)=c$. For Template:Colored em $b\in B$, there must also exist $a\in A$ such that $f(a)=b$ since $f$ is surjective. It follows that for every $c\in C$, there exists $a\in A$ such that $$c=g(b)=g(f(a))=(g\circ f)(a).$$

$◻$

Proof. Assume that $f$ and $g$ are bijective, i.e., are injective Template:Colored em surjective. It follows by the above proposition that $g\circ f$ is injective Template:Colored em surjective, i.e., is bijective.

$◻$

After knowing such results, it is natural to question that whether the Template:Colored em of the above proposition holds. Indeed, the converse does not hold, and we have the following results: Template:Colored proposition

Proof. For (a), assume that $g\circ f$ is injective. Then, for every $x,y\in A$, $$\begin{array}{ccc}f(x)=f(y)& ⟹g(f(x))=g(f(y))& (\text{definition of function})\\ & ⟹x=y.& (g\circ f\text{ is injective})\\ \end{array}$$ For (b), assume that $g\circ f$ is surjective. Then, for every $c\in C$, there exists $a\in A$ such that $g(f(a))=c$. So, we now can show that $g$ is surjective: for every $c\in C$, we can choose $f(a)\in B$, and then we have $g(f(a))=c$.

$◻$

Template:Colored remark To summarize the results, we have the following table:

Summary

$g\circ f$ (given)	$f$	$g$
injective	injective	injective/not injective
surjective	surjective	surjective/not surjective
bijective	injective	surjective

Inverse functions

Recall that a function $f:A\to B$ is a special relation from set $A$ to set $B$ satisfying some requirements. Also, recall that given a relation from $A$ to $B$, the Template:Colored em $R^{-1}$ is defined to be $$R^{-1}=\{(b,a):(a,b)\in R\}\subseteq B\times A.$$ We know that the inverse relation is always a relation itself. However, is the inverse relation of a Template:Colored em $f:A\to B$ always a Template:Colored em from $B$ to $A$ itself? The answer is, indeed, no. Consider the following example. Template:Colored example Of course, when the inverse relation of a function $f:A\to B$ turns out to be also a function from $B$ to $A$, it is natural to define it as the Template:Colored em of $f$: Template:Colored definition Template:Colored remark We are then interested in knowing under what conditions the inverse relation $f^{-1}$ is a function from $B$ to $A$, so that the Template:Colored em.

First, in order for $f^{-1}$ to be a function from $B$ to $A$, we must have $\mathrm{dom}{f}^{-1}=B$. So, we need to ensure that Template:Colored em element of $B$ is related to some elements in $A$, so that when we "reverse" the ordered pairs in $f$ to get $f^{-1}$, there is at least one image for every $b\in B$. This means $\mathrm{ran}f=B$, i.e., $f$ needs to be surjective.

Of course, we also need to ensure that there is a Template:Colored em image for every $b\in B$. Under the condition that $f$ is surjective, there is at least one image for every $b\in B$ already. So, it remains to ensure that there is Template:Colored em one image for every $b\in B$.

To ensure this, we need the function $f$ to be injective, since, if $f$ is injective, then every element of $B$ has at most one pre-image. So, when we "reverse" the ordered pairs in $f$ to get $f^{-1}$, every element of $B$ has at most one Template:Colored em.

From this discussion, we know that if $f^{-1}$ is a function from $B$ to $A$, then $f$ has to be injective and surjective, i.e. bijective. This shows that the bijectivity of $f$ is the necessary condition for the existence of the inverse function. Is it also the sufficient condition? It turns out that the bijectivity of $f$ is actually the Template:Colored em condition for the existence of the inverse function: Template:Colored theorem

Proof.

"$\Rightarrow$" direction: Assume that $f^{-1}$ is a function from $B$ to $A$. Then, we will proceed to prove that $f$ is injective and surjective:

Injective: For every $x,y\in A$, first assume $z=f(x)=f(y)\in B$. Then, $(x,z),(y,z)\in f$. By definition of inverse relation, we have $(z,x),(z,y)\in f^{-1}$. Since $f^{-1}$ is a function from $B$ to $A$, we have by definition $x=y$.

Surjective: For every $b\in B$, since $f^{-1}$ is a function from $B$ to $A$, there exists a unique $a\in A$ such that $(b,a)\in f^{-1}$. This means by definition of inverse relation that $(a,b)\in f$, i.e., $f(a)=b$ .

"$\Leftarrow$" direction: Assume that $f$ is bijective. Then, we will proceed to prove that $f^{-1}$ is a function from $B$ to $A$. That is, we need to ensure that for every element $b\in B$, there exists a unique $a\in A$ such that $(b,a)\in f^{-1}$.

Existence: For every $b\in B$, since $f$ is surjective, there exists $a\in A$ such that $f(a)=b$, i.e. $(a,b)\in f$. Hence, $(b,a)\in f^{-1}$. This shows that for every $b\in B$, there exists $a\in A$ such that $(b,a)\in f^{-1}$.

Uniqueness: Assume $(b,a^{\prime })\in f^{-1}$, in addition to $(b,a)\in f^{-1}$. So, we have $(a,b),(a^{\prime },b)\in f$, i.e., $f(a)=f(a^{\prime })=b$. Since $f$ is injective, we have $a=a^{\prime }$.

$◻$

Hence, from this theorem, we know that it is only meaningful to talk about inverse function of $f$ when $f$ is bijective. If $f$ is not bijective, then its inverse function does not exist at all, and it is meaningless to talk about it. The following theorem further suggests that the inverse function must also be bijective. Template:Colored theorem

Proof. Assume that $f:A\to B$ is bijective. Then, $f^{-1}$ is a function from $B$ to $A$. Then, we will show that it is injective and surjective.

Injective: For every $b,b^{\prime }\in B$, first assume $a=f^{-1}(b)=f^{-1}(b^{\prime })$. Then, $(b,a),(b^{\prime },a)\in f^{-1}$. Thus, $(a,b),(a,b^{\prime })\in f$. It follows that $b=b^{\prime }$ since $f$ is a function.

Surjective: For every $a\in A$, since $f$ is a function, there exists a unique $b\in B$ such that $f(a)=b$, i.e., $(a,b)\in f$, and hence $(b,a)\in f^{-1}$, i.e., $f^{-1}(b)$.

$◻$

Template:Colored remark Another common definition of inverse function is that the inverse function of $f$, denoted by $f^{-1}$, is a function satisfying $$f^{-1}\circ f=i{d}_A\text{ and }f\circ f^{-1}=i{d}_B.$$ It turns out that these two definitions of inverse function are indeed (logically) equivalent. Consider the following theorem. Template:Colored theorem

Proof. Let us first prove that $f$ is bijective.

Injective: For every $x,y\in A$, $$\begin{array}{ccc}f(x)=f(y)& ⟹g(f(x))=g(f(y))& (g\text{ is a function})\\ & ⟹(g\circ f)(x)=(g\circ f)(y)\\ & ⟹i{d}_A(x)=i{d}_A(y)& (\text{assumption})\\ & ⟹x=y.\end{array}$$ Surjective: For every $y\in B$, choose $x=g(y)\in A$. Then, $$f(x)=f(g(y))=i{d}_B(y)=y.$$

Now, let us prove that $g=f^{-1}$. Since $f$ is bijective, the inverse function $f^{-1}$ exists. Then, since the domain and codomain of the inverse function $f^{-1}$ is $B$ and $A$ respectively by definition, $g$ and $f^{-1}$ have the same domain and codomain. It now remains to show that $g(b)=f^{-1}(b)$ for every $b\in B$. Since $f$ is surjective, for every $b\in B$, there exists $a\in A$ such that $f(a)=b$. This means $a=f^{-1}(b)$. Now, we have for every $b\in B$, $$g(b)=g(f(a))=i{d}_A(a)=a=f^{-1}(b).$$

$◻$

The converse of the above theorem is also true. More precisely, if $f$ is bijective, and thus its inverse function $f^{-1}$ exists, then we have $f\circ f^{-1}=i{d}_A$ and $f^{-1}\circ f=i{d}_B$. (Details are left to the following exercise.) Hence, the two definitions are actually logically equivalent, in the sense that

• by the above theorem, the conditions in the alternative definition imply the conditions in our definition.
• by the above remark, the conditions in our definition imply the conditions in the alternative definition.

It then follows that the function $g$ satisfying $f\circ g=i{d}_A$ and $g\circ f=i{d}_B$ is unique, since the inverse function is unique. Template:Colored exercise Here, we will introduce an approach to find a formula for the inverse function. But this approach does not Template:Colored em work. Template:Colored example In this approach, we use some algebraic manipulation to find the inverse function. However, such method is not always possible. For instance, the function $f:ℝ\to (0,\mathrm{\infty })$ defined by $f(x)=e^x$ is bijective, but its inverse function $f^{-1}:(0,\mathrm{\infty })\to ℝ$ is given by (indeed, defined to be) $f^{-1}(x)=\ln x$. In this case, such inverse function cannot be obtained by such algebraic manipulation. Template:Colored exercise

Image sets and preimage sets

The concepts discussed in this section are the generalizations of the concepts of Template:Colored em and Template:Colored em. Template:Colored definition Template:Colored remark Graphically, the image set looks like:

   A              B
*------*       *------*
|      |       |      |
|  . X |       | f(X) |
|.###. |       |  .   |
|.###.--------->.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

The preimage set looks like

   A              B
*------*       *------*
|f-1(Y)|       |      |
|  .   |       |  Y   |
|.###. |       |  .   |
|.###.<---------.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

Proof. (a) For every subset $X\subseteq A$, we have $f^{-1}(f(X))=\{x\in A:f(x)\in f(X)\}$. So, for every $x$, $$x\in X⟹f(x)\in f(X)⟹x\in f^{-1}(f(X)).$$ (b) For every subset $Y\subseteq B$, we have $f(f^{-1}(Y))=\{y\in B:y=f(x)\text{ for some }x\in f^{-1}(Y)\}$. So, for every $y$, assume $y\in f(f^{-1}(Y))$. Then, $y=f(x)$ for some $x\in f^{-1}(Y)$. But $x\in f^{-1}(Y)$ means $f(x)\in Y$. So, we have $y=f(x)\in Y$.

$◻$

Cardinalities of sets

Recall that a set is $S$ Template:Colored em if it contains a finite number of elements, i.e., $S=\varnothing$ or $|S|=n$ for some $n\in \mathbb{N}$. On the other hand, a set is infinite if it is not finite. Previously, we have studied cardinalities of finite sets, and we have left cardinalities of Template:Colored em sets undefined. But, it turns out that we can define cardinalities of infinite sets in a more complicated way, using Template:Colored em.

It may now seem that we can write something like $|S|=\mathrm{\infty }$ for an infinite set $S$. But it turns out that this is not quite meaningful, and as we shall see, infinite sets can have different cardinalities, or different "sizes". That is, there are different sizes of infinity! (in some sense).

To motivate the definition for the cardinalities of infinite sets, let us first consider a simple example of Template:Colored em sets. Template:Colored example This example suggests that for two finite (nonempty) sets $A$ and $B$, they have the Template:Colored em if there exists a bijective function from $A$ to $B$ (or from $B$ to $A$. One such function is given by the Template:Colored em of the bijective function from $A$ to $B$.) This leads us to the following definition: Template:Colored definition Template:Colored remark Template:Colored example The result in this example may seem strange and counter-intuitive, since $\mathbb{Z}$ seems to be twice as large as $E$, and $E$ is a proper subset of $\mathbb{Z}$, but they turn out to have the same cardinality. Such phenomenon is actually quite common when we deal with the cardinalities of Template:Colored em.

Fortunately, the numerical equivalence has some nice properties: reflexivity, symmetry and transitivity: Template:Colored theorem

Proof.

Reflexivity:

Case 1: $A$ is empty. Then, $|A|=|A|=0$.

Case 2: $A$ is nonempty. Then, consider the identity function $i{d}_A:A\to A$. We have shown that it is bijective.

Symmetry:

Case 1: $A$ and $B$ are both empty. Then, $B$ must be numerically equivalent to $A$.

Case 2: One of $A,B$ is empty, and another is nonempty. Then, $A$ must Template:Colored em be numerically equivalent to $B$, and the result follows.

Case 3: Both $A$ and $B$ are nonempty. Then, assume $A$ is numerically equivalent to $B$. This means there exists a bijective function $f:A\to B$. Now, consider its inverse function $f^{-1}:B\to A$, which is bijective. So, $B$ is numerically equivalent to $A$.

Transitivity:

Case 1: $A,B,C$ are empty. Then, $A$ must be numerically equivalent to $C$.

Case 2: Some of $A,B,C$ are empty, and some are nonempty. Then, it is impossible for $A$ to be numerically equivalent to $B$ Template:Colored em $B$ to be numerically equivalent to $C$. The result follows.

Case 3: $A,B,C$ are nonempty. Then, assume $A$ is numerically equivalent to $B$ and $B$ is numerically equivalent to $C$. Then, there exist bijective functions $f:A\to B$ and $g:B\to C$. Thus, their composition $g\circ f:A\to C$ is bijective. Hence, $A$ and $C$ are numerically equivalent.

$◻$

Now, let us focus on the set $\mathbb{N}$, and consider the (infinite) sets having the same cardinality as $\mathbb{N}$. We give a special name for such sets: Template:Colored definition Template:Colored remark Using this definition, we can further define another property of a set: Template:Colored definition Template:Colored remark Template:Colored example Template:Colored remark Template:Colored exercise We now know that $\mathbb{N}$ and $\mathbb{Z}$ have the same cardinality. It is then natural to consider the set of all rational numbers, $\mathbb{Q}$. It appears that $\mathbb{Q}$ is much larger than $\mathbb{Z}$, so it may seem that $\mathbb{Q}$ should no longer be denumerable, and be uncountable. But it turns out that $\mathbb{Q}$ is also denumerable. Template:Colored example So, we have proved that $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|$. It turns out that even if $\mathbb{Q}$ seems much larger than $\mathbb{N}$ and $\mathbb{Z}$, it still has the same cardinality as them. A natural question then arises: is there any uncountable set at all? The answer is yes, and the best known example is the set of all real numbers, $ℝ$. In other words, there does not exist a bijective function from $\mathbb{N}$ to $ℝ$. Since $ℝ$ is uncountable, this suggests that the "size" of $ℝ$ is different from the "size" of $\mathbb{N}$, i.e., there are different sizes of infinity (in some sense). Template:Colored example Template:Colored remark The following results may be useful for comparing denumerable or uncountable sets. Template:Colored proposition Template:Colored example Template:Colored exercise Template:Colored example Template:Colored proposition Template:Colored remark Template:Colored example Template:Colored remark Template:Colored proposition Template:Colored proposition Template:Colored exercise Template:Colored example Template:Colored exercise Template:Nav Template:BookCat