Mathematical Proof/Functions

Introduction

In the previous chapter, we have discussed the concept of relations. 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 every element in $A$ is related to exactly one (or an unique) element of $B$.

You should have encountered the concept of functions 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

Definition. (Functions) Let $A$ and $B$ be sets. A function or mapping from set $A$ to set $B$, written $f:A\to B$, is a relation from set $A$ to set $B$ such that for every element $a\in A$, there exists a unique $b\in B$ such that $(a,b)\in f$.

Remark.

• The notation "$(a,b)\in f$" may seem weird at the first place. However, when we think about what $f$ represents here, it becomes more natural: since $f$ is a relation from set $A$ to set $B$, it is indeed a subset of $A\times B$. So, it makes sense to say $(a,b)$ is an element of $f$.

• However, it is much more common to write $f(a)=b$ instead (and you should have seen this notation before).

• Since $f$ is a relation, we can apply the terminologies to functions: the set $A$ is the domain of function $f$, denoted by $\operatorname {dom} f$.
• We also have some more terminologies for functions: The set $B$ is called the codomain of $f$, $b=f(a)$ is the image of $a$ under $f$. Also, $a$ is referred to as the pre-image of $b$ under $f$. Furthermore, we say that $f$ maps $a$ into $b$.

• From the definition, every element $a\in A$ has an unique (or exactly one) image.

• When the set $A$ is empty, then the only function (and also the only relation) from set $A$ to $B$ is the empty set. When set $A$ is nonempty while the set $B$ is empty, since the only relation from set $A$ to $B$ is also the empty set, but such relation does not satisfy the requirements to be a function (there does not exist $b\in B$ such that $(a,b)\in f$ for every $a\in A$).

Exercise. Write down the meaning of "$f$ is not a function from $A$ to $B$", i.e., the negation of the definition above. (Hint: first split the unique existential quantifier into two the existence part and uniqueness part.)

Solution

First, we express the meaning of "$f$ is a function from $A$ to $B$" using logical notations: $${\big (}\forall a\in A,\exists b\in B,f(a)=b{\big )}{\text{ and }}{\big (}\forall a\in A,\forall b,c\in B,{\text{if }}f(a)=b{\text{ and }}f(a)=c,{\text{ then }}b=c{\big )}.$$ Then, the meaning of "$f$ is not a function from $A$ to $B$" is: $${\big (}\exists a\in A,\forall b\in B,f(a)\neq b{\big )}{\text{ or }}{\big (}\exists a\in A,\exists b,c\in B,f(a)=b{\text{ and }}f(a)=c{\text{ and }}b\neq c{\big )}.$$ (LHS means the existential requirement is violated, and RHS means the uniqueness requirement is violated.) In other words, the meaning is "there exists some $a\in A$ with no image, OR there exists some $a\in A$ with more than one image".

Example. Let $A=\{1,2,3\}$ and $B=\{a,b\}$. Then, $$f=\{(1,a),(2,a),(3,b)\}$$ defines a function. Graphically, it looks like

  A               B
*----*          *----*
|1*  #
|    |  #       |    |
|    |       #  |    |
|    |          |#   |
|2* # # # # # #  # *a|
|    |          |    |
|3* # # # # # #  # *b|
|    |          |    |
*----*          *----*

Here, $a$ is the image of 1 and 2 under $f$. In other words, 1 and 2 are the pre-images of $a$. Similarly, $b$ is the image of 3 under $f$ and 3 is the pre-image of $b$ under $f$.

Example. Let $A=\{a,b,c,d\}$ and $B=\{1,2,3,4,5,6\}$. Then, $f=\{(a,1),(a,2),(b,3),(c,4),(d,5)\}$ is not a function from $A$ to $B$ since $a$ has two images: 1 and 2. Also, $f=\{(a,1),(b,3)\}$ is not a function from $A$ to $B$ since $c$ and $d$ have no image.

Example. It is quite common to refer, say, "$f(x)=x^{2}$" to as a "function". But, when we look at the definition of function, such saying actually has some issues, strictly speaking:

1. What are the domain and codomain?
2. $f(x)$ is just an image of a real number $x$ under $f$. The function $f$ itself should be a set.

For the first question, usually the domain and codomain are taken to be $\mathbb {R}$. But for some functions, $f(x)$ becomes undefined for some values of real number $x$. In this case, it is common to set the domain as $\{x:f(x){\text{ is a real number}}\}$, which is referred to as the natural domain.

For the second question, the actual function $f$ is indeed the set $$f=\{(x,x^{2}):x\in \mathbb {R} \}.$$ This set of point in the plane is the graph of $f$ (a parabola). However, it is acceptable to have such saying for convenience.

Exercise. A commonly encountered function is the exponential function, which is defined by $g(x)=e^{x}$. Another one is the natural logarithm function defined by $h(x)=\ln x$.

(a) Find the domain and codomain of the functions $g$ and $h$.

(b) Express the functions $g$ and $h$ using sets.

Solution

(a) The domain and codomain of $g$ are both $\mathbb {R}$. The domain of $h$ is $(0,\infty )$ (when $x$ is less than or equal to zero, $\ln x$ is undefined), and the codomain of $h$ is $\mathbb {R}$.

(b) $g=\{(x,e^{x}):x\in \mathbb {R} \}$ and $h=\{(x,\ln x):x\in (0,\infty )\}$.

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 range of a function (same as the definition for a relation).

Definition. (Range of function) The range of a function $f$, denoted by $\operatorname {ran} f$, is $$\operatorname {ran} f=\{b\in B:b=f(x){\text{ for some }}x\in A\}=\{f(x):x\in A\}\subseteq B.$$

Remark.

• Comparing the definitions of range and codomain, we can notice that for the range, it includes all elements in the codomain that have at least one pre-image. On the other hand, the codomain is the set that contains everything into which every element $a\in A$ can be possibly mapped.
• When the range and the codomain of a function $f$ turn out to be the same, we call such function $f$ to be surjective. We will discuss more properties for a function later.

• We can observe that we can actually manually set (or restrict) the codomain of function to be its range. So, even if a given function is not surjective, we can make it surjective by changing its codomain manually.

Example. Let $A=\{1,2\}$ and $B=\{3,4,5\}$. Define the function $f$ by $$f=\{(1,3),(2,4)\}.$$ Then, $\operatorname {ran} f=\{3,4\}.$

Exercise. Let $A$ and $B$ be sets, and $b$ be a fixed element of $B$. Then, the function $f:A\to B$ defined by $f(a)=b$ for every $a\in A$ is called the constant function from $A$ to $B$.

(a) What is the range of constant function?

(b) What is the codomain of constant function?

(c) Can the range of constant function equal its codomain?

(d) What is/are the pre-image(s) of $b$?

Solution

(a) The range is $\{b\}$.

(b) The codomain is the set $B$.

(c) Yes, if $B=\{b\}$.

(d) The pre-images of $b$ are all elements of $A$.

Example. (Identity function) Let $A$ be a set. Then the function $id_{A}$ defined by $id_{A}(a)=a$ for every $a\in A$ is called the identity function of $A$. Every $a\in A$ is the image of itself. The domain, codomain, and range of $id_{A}$ are all $A$.

Remark.

• This function is quite important in the section about inverse functions.

Example. Consider the function $f:\mathbb {R} \to \mathbb {R}$ defined by $f(x)=e^{x}$. Find the range of the function $f$, $\operatorname {ran} f$, and prove your answer.

The range of the function $f$ is $\operatorname {ran} f=(0,\infty )$.

Proof. To prove that $\operatorname {ran} f=(0,\infty )$, we will prove (i) $\operatorname {ran} f\subseteq [0,\infty )$; (ii) $[0,\infty )\subseteq \operatorname {ran} f$.

Firstly, for $\operatorname {ran} f\subseteq (0,\infty )$: for every $y$, $${\begin{aligned}y\in \operatorname {ran} f&\implies y=e^{x}{\text{ for some }}x\in \mathbb {R} \\&\implies y>0&({\text{we do not have the reverse implication for this step}})\\&\implies y\in (0,\infty ).\end{aligned}}$$ On the other hand, for $(0,\infty )\subseteq \operatorname {ran} f$: for every $y\in (0,\infty )$, we choose $x=\ln y\in \mathbb {R}$. Then, $f(x)=e^{x}=e^{\ln y}=y$. So, by definition, we have $y\in \operatorname {ran} f$.

$\Box$

Exercise. Consider the function $f:\mathbb {R} \to \mathbb {R}$ defined by $f(x)=x^{2}$. Find $\operatorname {ran} f$, and prove your answer.

Solution

We have $\operatorname {ran} f=[0,\infty )$.

Proof. First, for every $y$, $${\begin{aligned}y\in \operatorname {ran} f&\implies y=x^{2}{\text{ for some }}x\in \mathbb {R} \\&\implies y\geq 0\\&\implies y\in [0,\infty ).\end{aligned}}$$ This shows that $\operatorname {ran} f\subseteq [0,\infty )$.

On the other hand, for every $y\in [0,\infty )$, we choose $x={\sqrt {y}}\in \mathbb {R}$. Then, $f(x)=x^{2}=\left({\sqrt {y}}\right)^{2}=y$ . So, we have $y\in \operatorname {ran} f$. This shows that $[0,\infty )\subseteq \operatorname {ran} f$, and we are done.

$\Box$

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 equality of functions:

Definition. (Equality of functions) Let $A$ and $B$ be sets, and let $f:A\to B$ and $g:A\to B$ be two functions from $A$ to $B$ (notice that their domains and codomains have to be the same). Then, the functions $f$ and $g$ are said to be equal, written $f=g$, if $f(a)=g(a)$ for every $a\in A$.

Exercise. Write down the meaning for two functions $f$ and $g$ to be not equal.

Solution

($f$ and $g$ have different domain) or ($f$ and $g$ have different codomain) or (there exists $a\in A$ such that $f(a)\neq g(a)$).

Example. Consider the functions $f:\mathbb {R} \to \mathbb {R}$ and $g:\mathbb {R} \to (0,\infty )$ defined by $f(x)=e^{x}$ and $g(x)=e^{x}$. Although their "formulas" are the same, they are not equal since their codomains are different.

Exercise. Consider the functions $f$ and $g$ defined by $f(x)=x$ and $g(x)={\frac {x^{2}}{x}}$. Are the functions $f$ and $g$ equal? Why?

Solution

No.

Notice hat $g(x)$ is undefined when $x=0$ (and defined for every other real number $x$), while $f(x)$ is defined for every real number $x$. Thus, the domain of $f$ is $\mathbb {R}$ and the domain of $g$ is $\mathbb {R} \setminus \{0\}$. So, $f$ and $g$ are not equal.

Injective, surjective and bijective functions

In this section, we will discuss some important properties that a function may possess, namely injectivity, surjectivity, and bijectivity.

Definition. (Injective function) A function $f:A\to B$ is injective or one-to-one if for every $x,y\in A$, $f(x)=f(y)\implies x=y$, or equivalently (contrapositive), for every $x,y\in A$, $x\neq y\implies f(x)\neq f(y)$.

Remark.

• The definition tells us that an injective function from $A$ to $B$ maps distinct elements of $A$ into distinct elements of $B$.
• To prove that a function is injective, it is common to use a direct proof: for every $x,y\in A$, assume $f(x)=f(y)$, and then proceed to prove that $x=y$.

Exercise. Write down the meaning of "a function $f:A\to B$ is not injective".

Solution

There exist $x,y\in A$ such that $f(x)=f(y)$ and $x\neq y$.

Example. A function $f:\mathbb {R} \to \mathbb {R}$ is defined by $f(x)=2x+5$. Prove that $f$ is injective.

Proof. For every $x,y\in \mathbb {R}$, $$f(x)=f(y)\implies 2x+5=2y+5\implies 2x=2y\implies x=y.$$ Thus, $f$ is injective.

$\Box$

Example. A function $f:\mathbb {R} \to \mathbb {R}$ is defined by $f(x)=x^{2}$. Prove or disprove that $f$ is injective.

Disproof. Since $f(-1)=f(1)=1$, $f$ is not injective.

$\Box$

Exercise. A function $g:[0,\infty )\to \mathbb {R}$ is defined by $g(x)=x^{2}$. Prove that $g$ is injective.

Proof

Proof. For every $x,y\in [0,\infty )$, $$g(x)=g(y)\implies x^{2}=y^{2}\implies {\sqrt {x^{2}}}={\sqrt {y^{2}}}\implies |x|=|y|\implies x=y.$$

$\Box$

Remark.

• It suggests that the domain of a function is important when we determine whether a function is injective. We should not just look at the formula of the function.

Example. A function $f:\mathbb {R} \to \mathbb {R}$ is defined by $f(x)=x^{2}-3x+5$. Prove or disprove that $f$ is injective.

This time, it is not immediately clear that whether this function is injective or not. So, we may first try to prove that $f$ is injective, and see what we get: for every $x,y\in \mathbb {R}$, $$f(x)=f(y)\implies x^{2}-3x+5=y^{2}-3y+5\implies x(x-3)=y(y-3).$$ Notice that for the last equation to imply $x=y$, we need $x\neq 3$ and $y\neq 3$. However, $x$ and $y$ can take any real values. Hence, this suggests us to consider $f(3)$ and disprove that $f$ is injective. Another observation is that when $x=3$, then $x(x-3)=0$. But to make it equal zero, we can also take $x=0$. Thus, this gives us a counterexample for disproving that $f$ is injective:

Disproof. Since $f(0)=f(3)=5$, $f$ is not injective.

$\Box$

Exercise. A function $f:[-1,1]\to [0,1]$ is defined by $f(x)={\sqrt {1-x^{2}}}$. Prove or disprove that $f$ is injective.

Solution

Disproof. Since $f(-1)=f(1)=0$, $f$ is not injective.

$\Box$

Remark.

• The graph of this function is a semicircle located above the $x$-axis.

Definition. (Surjective function) A function $f:A\to B$ is surjective or onto if for every $y\in B$, there exists $x\in A$ such that $f(x)=y$.

Remark.

• The definition tells us that $f$ is surjective if every element of the codomain $B$ is the image of some element of $A$. In other words, $\operatorname {ran} f=B$.

Exercise. Write down the meaning of "$f:A\to B$ is not surjective".

Solution

There exists $y\in B$ such that for every $x\in A$, $f(x)\neq y$.

In other words, some element of the codomain $B$ is not the image of every element of $A$. In other words, $\operatorname {ran} f\neq B$ (since $\operatorname {ran} f\subseteq B$ by definition, we may also write this as $\operatorname {ran} f\subset B$).

Example. A function $f:\mathbb {R} \to \mathbb {R}$ is defined by $f(x)=2x+5$. Prove that $f$ is surjective.

To prove that $f$ is surjective, we need to prove that for every $y\in \mathbb {R}$, there exists $x\in \mathbb {R}$ such that $f(x)=y$, i.e., $y=2x+5$. To show this, we can see that the choices of $x\in \mathbb {R}$ to satisfy the requirement for different values of $y$ are different. Indeed, the choice of $x$ depend on the value of $y\in \mathbb {R}$. But it is not hard to choose such $x\in \mathbb {R}$ with a given value of $y\in \mathbb {R}$: we can just rearrange the above equation to make $x$ to be the subject of the equation: $$x={\frac {y-5}{2}}\in \mathbb {R}$$

Proof. For every $y\in \mathbb {R}$, choose $x={\frac {y-5}{2}}\in \mathbb {R}$. Then, $$f(x)=f\left({\frac {y-5}{2}}\right)=2\left({\frac {y-5}{2}}\right)+5=y-5+5=y.$$

$\Box$

Example. Prove or disprove that the function $f:\mathbb {R} \to \mathbb {R}$ defined by $f(x)=x^{2}$ is surjective.

Disproof. Take $y=-1$. Then, there is no $x\in \mathbb {R}$ such that $$x^{2}=f(x)=-1$$ since $x^{2}=-1$ has no real solution. Hence, $f$ is not surjective.

$\Box$

Exercise. Prove that the function $g:\mathbb {R} \to [0,\infty )$ defined by $g(x)=x^{2}$ is surjective.

Proof

Proof. For every $y\in [0,\infty )$, choose $x={\sqrt {y}}\in \mathbb {R}$ (it is possible to choose such real number $x$ since $y\in [0,\infty )$). Then, $$f(x)=f\left({\sqrt {y}}\right)=\left({\sqrt {y}}\right)^{2}=y$$

$\Box$

Remark.

• It suggests that the codomain of a function is important when we determine whether a function is surjective. So, again, we should not just look at the formula of the function.

Definition. (Bijective function) A function $f:A\to B$ is bijective or one-to-one correspondence if it is both injective and surjective.

Remark.

• We should be aware that "one-to-one correspondence" (which means bijective) is different from "one-to-one" (which means injective).
• In other words, $f$ is bijective if for every $y\in B$, there exists a unique $x\in A$ such that $f(x)=y$ (the existence part corresponds to the surjectivity, and the uniqueness part corresponds to the injectivity).

• However, we usually still prove the bijectivity by proving the injectivity and surjectivity separately, similar to the case for proving "there exists a unique ..." where we prove the existence part and uniqueness part separately.

Exercise. Write down the meaning of "$f:A\to B$ is not bijective".

Solution

$f$ is not injective or $f$ is not surjective.

Example. We have proved the function $f:\mathbb {R} \to \mathbb {R}$ defined by $f(x)=2x+5$ is both injective and surjective. Hence, it is bijective.

Example. We have proved the function $g_{1}:[0,\infty )\to \mathbb {R}$ defined by $g_{1}(x)=x^{2}$ is injective and the function $g_{2}:\mathbb {R} \to [0,\infty )$ defined by $g_{2}(x)=x^{2}$ is surjective. Then, with basically the same proof, we can prove that the function $g_{3}:[0,\infty \to [0,\infty )$ defined by $g_{3}(x)=x^{2}$ is both injective or surjective, and hence bijective.

Example. Prove that the function $f:\mathbb {R} \setminus \{1\}\to \mathbb {R} \setminus \{3\}$ defined by $f(x)={\frac {3x+1}{x-1}}$ is bijective.

For proving the surjective part, we need to make $x$ as the subject for the equaton $y={\frac {3x+1}{x-1}}$: $$y={\frac {3x+1}{x-1}}\iff xy-y=3x+1\iff (y-3)x=y+1\iff x={\frac {y+1}{y-3}}.$$

Proof.

Injective: For every $x,y\in \mathbb {R} \setminus \{1\}$, $$f(x)=f(y)\implies {\frac {3x+1}{x-1}}={\frac {3y+1}{y-1}}\implies 3x+1=3y+1\implies 3x=3y\implies x=y.$$ Surjective: For every $y\in \mathbb {R} \setminus \{3\}$, choose $x={\frac {y+1}{y-3}}$. We then need to show that $x\in \mathbb {R} \setminus \{1\}$. Since $x\in \mathbb {R}$ ($y\neq 3$, so $x$ is defined), it suffices to show that $x\neq 1$. Let us prove it by contradiction:

Assume to the contrary that $x=1$. Then, ${\frac {y+1}{y-3}}=1\implies y+1=y-3\implies 1=-3$. So we arrive at a contradiction.

Then, we have $$f(x)=f\left({\frac {y+1}{y-3}}\right)={\frac {3\left({\frac {y+1}{y-3}}\right)+1}{{\frac {y+1}{y-3}}-1}}={\frac {3y+3+y-3}{y+1-y+3}}={\frac {4y}{4}}=y.$$

$\Box$

Exercise. Let $A$ be a set. Prove that the identity function $id_{A}:A\to A$ is bijective.

Proof

Proof.

Injective: For every $x,y\in A$, $id_{A}(x)=id_{A}(y)\implies x=y$.

Surjective: For every $y\in A$, choose $x=y\in A$. Then, $id_{A}(x)=id_{A}(y)=y$.

$\Box$

Exercise. A function $f:\mathbb {Z} \times \mathbb {Z} \to \mathbb {Z} \times \mathbb {Z}$ is defined by $$f(m,n)=(n,m).$$ Prove or disprove that $f$ is bijective.

Solution

Proof.

Injective: For every $(m_{1},n_{1}),(m_{2},n_{2})\in \mathbb {Z} \times \mathbb {Z}$, $$f(m_{1},n_{1})=f(m_{2},n_{2})\implies (n_{1},m_{1})=(n_{2},m_{2})\implies n_{1}=n_{2}{\text{ and }}m_{1}=m_{2}\implies (m_{1},n_{1})=(m_{2},n_{2}).$$

Surjective: For every $(x,y)\in \mathbb {Z} \times \mathbb {Z}$, choose $(y,x)\in \mathbb {Z} \times \mathbb {Z}$. Then, $$f(y,x)=(x,y).$$

$\Box$

Exercise. Consider a function $f:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ defined by $f(m,n)=m+n$, and another function $g:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ defined by $g(m,n)=mn$.

(a) Prove or disprove that $f$ is (i) injective; (ii) surjective.

(b) Prove or disprove that $g$ is (i) injective; (ii) surjective.

Solution

(a) (i)

Disproof. Since $f(1,2)=f(2,1)=3$, $f$ is not injective.

$\Box$

(ii)

Disproof. Take $y=1$. Then, for every $(m,n)\in \mathbb {N} \times \mathbb {N}$, $m+n\neq y=1$.

$\Box$

(b) (i)

Disproof. Since $f(1,2)=f(2,1)=2$, $f$ is not injective.

$\Box$

(ii)

Proof. For every $y\in \mathbb {N}$, choose $(m,n)=(1,y)\in \mathbb {N} \times \mathbb {N}$. Then, $f(m,n)=1(y)=y$.

$\Box$

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 composition:

Definition. (Composition) Let $f:A\to B$ and $g:B\to C$ be two functions, where $A,B$ and $C$ are nonempty sets. Then, the composition of $f$ and $g$, denoted by $g\circ f$ (read "g-circle-f"), is the function from $A$ to $C$ defined by $$(g\circ f)(a)=g(f(a)){\text{ for every }}a\in A.$$

Remark.

• We can see that the composition $g\circ f$ is obtained by first applying $f$ and then applying $g$.

Example. Let $A=\{1,2,3\},B=\{a,b,c,d\}$ and $C=\{4,5\}$. Consider the functions $f:A\to B$ and $g:B\to C$ defined by $$f=\{(1,a),(2,b),(3,b)\}{\text{ and }}g=\{((a,4),(b,5),(c,5),(d,5)\}.$$ Then, we have $(g\circ f)(1)=4,(g\circ f)(2)=5$ and $(g\circ f)(3)=5$. So, the function $g\circ f:A\to C$ is given by $$g\circ f=\{(1,4),(2,5),(3,5)\}.$$ However, $f\circ g$ is undefined, since the codomain of $g$ ($C$) is different from the domain of $f$ ($A$).

Remark.

• To make both $g\circ f$ and $f\circ g$ defined, we need to have $f:A\to B$ and $g:B\to A$, that is, the domain (codomain) of $f$ must be equal to the codomain (domain) of $g$.
• In this case, $g\circ f$ is a function from $B$ to $B$, and $f\circ g$ is a function from $A$ to $A$. So, in order for them to be possibly equal, we need to further have $A=B$.

• But, even if $A=B$, it is still possible that $f\circ g\neq g\circ f$. Consider the following example.

Example. Let $A=\{1,2\}$. Consider the functions $f:A\to A$ and $g:A\to A$ defined by $$f=\{(1,2),(2,2)\}{\text{ and }}g=\{(1,1),(2,1)\}.$$ Then, $g\circ f=\{(1,1),(2,1)\}$ and $f\circ g=\{(1,2),(2,2)\}$. Since, for example, $(g\circ f)(1)=1\neq 2=(f\circ g)(1)$, it follows that $g\circ f\neq f\circ g$.

Remark.

• This example shows that the composition of functions is not commutative. That is, after changing the order of the composition, the result may be different.

Although the composition of functions is not commutative, it is associative.

Theorem. (Associativity of the composition of functions) For every nonempty set $A,B,C,D$, and for every function $f:A\to B,g:B\to C$ and $h:C\to D$, we have $$h\circ (g\circ f)=(h\circ g)\circ f.$$

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$, $${\big (}h\circ (g\circ f){\big )}(a)=h{\big (}(g\circ f)(a){\big )}=h{\big (}g(f(a)){\big )}.$$ (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, $${\big (}(h\circ g)(f(a)){\big )}=h{\big (}g(f(a)){\big )}.$$

$\Box$

Example. Let $A=\{1,2,3\},B=\{a,b,c,d\},C=\{4,5\}$ and $D=\{\alpha ,\beta ,\gamma \}$. Consider the functions $f:A\to B$, $g:B\to C$ and $h:C\to D$ defined by $$f=\{(1,a),(2,b),(3,b)\},g=\{((a,4),(b,5),(c,5),(d,5)\}{\text{ and }}h=\{(4,\beta ),(5,\gamma )\}.$$ Recall that we have shown that $g\circ f=\{(1,4),(2,5),(3,5)\}$. We can further show that $h\circ g=\{(a,\beta ),(b,\gamma ),(c,\gamma ),(d,\gamma )\}$. Thus, $h\circ (g\circ f):A\to D$ and $(h\circ g)\circ f:A\to D$ are given by $$h\circ (g\circ f)=(h\circ g)\circ f=\{(1,\beta ),(2,\gamma ),(3,\gamma )\}.$$

Now, let us study some results that are related to the composition, injectivity, surjectivity, and bijectivity.

Proposition. For every nonempty set $A,B,C$ and for every function $f:A\to B$ and $g:B\to C$,

(a) if $f$ and $g$ are injective, then $g\circ f$ is injective.

(b) if $f$ and $g$ are surjective, then $g\circ f$ is surjective.

Proof. For (a), assume that $f$ and $g$ are injective. Then, for every $x,y\in A$ $${\begin{aligned}g\circ f(x)=g\circ f(y)&\implies g(f(x))=g(f(y))\\&\implies f(x)=f(y)&(g{\text{ is injective}})\\&\implies x=y.&(f{\text{ is injective}})\\\end{aligned}}$$ 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 this $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).$$

$\Box$

Corollary. For every nonempty set $A,B,C$ and for every function $f:A\to B$ and $g:B\to C$, if $f:A\to B$ and $g:B\to C$ are bijective, then $g\circ f$ is bijective.

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

$\Box$

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

Proposition. For every nonempty set $A,B,C$ and for every function $f:A\to B$ and $g:B\to C$,

(a) if $g\circ f$ is injective, then $f$ is injective.

(b) if $g\circ f$ is surjective, then $g$ is surjective.

Proof. For (a), assume that $g\circ f$ is injective. Then, for every $x,y\in A$, $${\begin{aligned}f(x)=f(y)&\implies g(f(x))=g(f(y))&({\text{definition of function}})\\&\implies x=y.&(g\circ f{\text{ is injective}})\\\end{aligned}}$$ 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$.

$\Box$

Remark.

• It follows that if $g\circ f$ is bijective, then $f$ is injective and $g$ is surjective.
• For (a), with the assumption, $f$ may or may not be surjective. Also, for (b), $g$ may or may not be injective.

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

Exercise. Disprove that for every nonempty set $A,B,C$ and for every function $f:A\to B$ and $g:B\to C$,

(a) if $g\circ f$ is injective, then $g$ is injective.

(b) if $g\circ f$ is surjective, then $f$ is surjective.

Solution

(a)

Disproof. Take $A=\{1,2\},B=\{1,2,3\},C=\{1,2\}$, and take the functions $f:A\to B$ and $g:B\to C$ defined by $f=\{(1,1),(2,2)\},g=\{(1,1),(2,2),(3,1)\}$.

Then, the function $g\circ f:A\to C$ is given by $g\circ f=\{(1,1),(2,2)\}$, which is injective, since for every $x,y\in A$, $(g\circ f)(x)=(g\circ f)(y)\implies x=y$. However, the function $g$ is not injective since $g(1)=g(3)=1$.

$\Box$

(b)

Disproof. Take $A=\{1,2\},B=\{1,2,3\},C=\{1,2\}$, and take the functions $f:A\to B$ and $g:B\to C$ defined by $f=\{(1,1),(2,2)\},g=\{(1,1),(2,2),(3,1)\}$.

Then, the function $g\circ f:A\to C$ is given by $g\circ f=\{(1,1),(2,2)\}$, which is surjective, since for every $c\in C$, there exists $a\in A$ such that $(g\circ f)(a)=c$. However, the function $f$ is not surjective, since, for example, take $c=3$. Then, for every $a\in A$, $f(a)\neq c=3$.

$\Box$

Example. Consider two arbitrary functions $f:\mathbb {R} \to \mathbb {R}$ and $g:\mathbb {R} \to \mathbb {R}$ such that the function $g\circ f:\mathbb {R} \to \mathbb {R}$ is given by $$g\circ f(x)=x^{3}.$$ What properties do the functions $f$ and $g$ possess?

Solution. First, we claim that $g\circ f$ is bijective.

Proof.

Injective: for every $x,y\in \mathbb {R}$, $(g\circ f)(x)=(g\circ f)(y)=x^{3}=y^{3}\implies x=y$.

Surjective: for every $y\in \mathbb {R}$, choose $x=y^{1/3}\in \mathbb {R}$. Then, $(g\circ f)(x)=(y^{1/3})^{3}=y$.

$\Box$

Then, we can conclude that $f$ is injective and $g$ is surjective by the above proposition.

Exercise. Consider the function $f:\mathbb {R} \to \mathbb {R}$ satisfying $(f\circ f)(x)=x$ for every $x\in \mathbb {R}$. Prove or disprove that $f$ is (i) injective; (ii) surjective.

Solution

(i) and (ii):

Proof. First, notice that $f\circ f=id_{\mathbb {R} }$, and we have proved that $id_{\mathbb {R} }$ is bijective. So, by the above proposition, $f$ is injective and surjective.

$\Box$

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 inverse relation $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 function $f:A\to B$ always a function from $B$ to $A$ itself? The answer is, indeed, no. Consider the following example.

Example. Let $A=\{1,2,3\}$ and $B=\{a,b\}$. Consider the function $f:A\to B$ defined by $$f=\{(1,a),(2,a),(3,b)\}.$$ Then, the inverse relation (we are not calling it inverse function) of $f$, denoted by $f^{-1}$, is $$f^{-1}=\{(a,1),(a,2),(b,3)\}.$$ We can then see that this inverse relation $f^{-1}$ is not a function from $B$ to $A$, since the element $a\in B$ has two images: 1 and 2.

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 inverse function of $f$:

Definition. (Inverse function) Let $A$ and $B$ be sets, and let $f:A\to B$ be a function. The inverse function of the function $f$ is the inverse relation of $f$, denoted by $f^{-1}$, provided that $f^{-1}$ is a function from $B$ to $A$.

Remark.

• Since given a relation from $A$ to $B$, it has a unique (or exactly one) inverse relation from $B$ to $A$ (according to the definition), it follows that the inverse function of a function $f$, if exists, is unique.

We are then interested in knowing under what conditions the inverse relation $f^{-1}$ is a function from $B$ to $A$, so that the inverse function exists.

First, in order for $f^{-1}$ to be a function from $B$ to $A$, we must have $\operatorname {dom} f^{-1}=B$. So, we need to ensure that every 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 $\operatorname {ran} f=B$, i.e., $f$ needs to be surjective.

Of course, we also need to ensure that there is a unique 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 at most 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 image.

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 necessary and sufficient condition for the existence of the inverse function:

Theorem. Let $f:A\to B$ be a function. Then its inverse relation $f^{-1}$ is a function from $B$ to $A$ (i.e., the inverse function of $f$ exists) if and only if the function $f$ is bijective.

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 {\color {darkgreen}A}$, first assume $z=f(x)=f(y){\color {blue}\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 ${\color {blue}B}$ to ${\color {darkgreen}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')\in f^{-1}$, in addition to $(b,a)\in f^{-1}$. So, we have $(a,b),(a',b)\in f$, i.e., $f(a)=f(a')=b$. Since $f$ is injective, we have $a=a'$.

$\Box$

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.

Theorem. If the function $f:A\to B$ is bijective, then its inverse function $f^{-1}:B\to A$ is also bijective.

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'\in B$, first assume $a=f^{-1}(b)=f^{-1}(b')$. Then, $(b,a),(b',a)\in f^{-1}$. Thus, $(a,b),(a,b')\in f$. It follows that $b=b'$ 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)$.

$\Box$

Remark.

• Notice that in the proof, we do not make use of the bijectivity of $f$ to prove the injectivity and surjectivity of $f^{-1}$. Indeed, we just use the definition of function to prove them. The bijectivity of $f$ serves only one purpose: ensuring that the inverse function exists.

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=id_{A}{\text{ and }}f\circ f^{-1}=id_{B}.$$ It turns out that these two definitions of inverse function are indeed (logically) equivalent. Consider the following theorem.

Theorem. Let $f:A\to B$ and $g:B\to A$ be two functions such that $f\circ g=id_{A}$ and $g\circ f=id_{B}$. Then, $f$ is bijective and $g$ equals the inverse function of $f$, $f^{-1}$.

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

Injective: For every $x,y\in A$, $${\begin{aligned}f(x)=f(y)&\implies g(f(x))=g(f(y))&(g{\text{ is a function}})\\&\implies (g\circ f)(x)=(g\circ f)(y)\\&\implies id_{A}(x)=id_{A}(y)&({\text{assumption}})\\&\implies x=y.\end{aligned}}$$ Surjective: For every $y\in B$, choose $x=g(y)\in A$. Then, $$f(x)=f(g(y))=id_{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))=id_{A}(a)=a=f^{-1}(b).$$

$\Box$

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}=id_{A}$ and $f^{-1}\circ f=id_{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=id_{A}$ and $g\circ f=id_{B}$ is unique, since the inverse function is unique.

Exercise. Let $f:A\to B$ be a function. Prove that if $f$ is bijective, and thus its inverse function $f^{-1}$ exists, then we have $f\circ f^{-1}=id_{A}$ and $f^{-1}\circ f=id_{B}$.

Proof. First, since $f^{-1}$ is a function from $B$ to $A$, it follows that $f\circ f^{-1}$ is a function from $A$ to $A$, and $f^{-1}\circ f$ is a function from $B$ to $B$.

Then, for every $a\in A$, there exists a unique $b\in B$ such that $f(a)=b$, and hence $a=f^{-1}(b)$. So, $$(f^{-1}\circ f)(a)=f^{-1}(f(a))=f^{-1}(b)=a.$$ Also, for every $b\in B$, $$(f\circ f^{-1})(b)=f(f^{-1}(b))=f(a)=b.$$

$\Box$

Here, we will introduce an approach to find a formula for the inverse function. But this approach does not always work.

Example. Recall that we have proved that the function $f:\mathbb {R} \setminus \{1\}\to \mathbb {R} \setminus \{3\}$ defined by $f(x)={\frac {3x+1}{x-1}}$ is bijective. So, its inverse function $f^{-1}$ exists. Determine the inverse function $f^{-1}$.

Solution. We have for every $x\in \mathbb {R} \setminus \{3\}$, $(f\circ f^{-1})(x)=x$. Hence, $$x=(f\circ f^{-1})(x)=f(f^{-1}(x))={\frac {3f^{-1}(x)+1}{f^{-1}(x)-1}}\implies xf^{-1}(x)-x=3f^{-1}(x)+1\implies f^{-1}(x)={\frac {x+1}{x-3}}.$$ Thus, the inverse function $f^{-1}:\mathbb {R} \setminus \{3\}\to \mathbb {R} \setminus \{1\}$ is given by $$f^{-1}(x)={\frac {x+1}{x-3}}.$$

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:\mathbb {R} \to (0,\infty )$ defined by $f(x)=e^{x}$ is bijective, but its inverse function $f^{-1}:(0,\infty )\to \mathbb {R}$ 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.

Exercise. Consider the function $f:[0,1]\to [0,1]$ defined by $$f(x)={\sqrt {1-x^{2}}}.$$ (a) Prove that $f$ is bijective.

(b) Determine the formula for inverse function, $f^{-1}(x)$.

Solution

(a)

Proof.

Injective: For every $x,y\in [0,1]$, $${\begin{aligned}f(x)=f(y)&\implies {\sqrt {1-x^{2}}}={\sqrt {1-y^{2}}}\\&\implies 1-x^{2}=1-y^{2}\\&\implies x^{2}=y^{2}\\&\implies x=y.&(x,y\geq 0)\end{aligned}}$$ Surjective: For every $y\in [0,1]$, choose $x={\sqrt {1-y^{2}}}\in [0,1]$. Then, $$f(x)=f\left({\sqrt {1-y^{2}}}\right)={\sqrt {1-\left({\sqrt {1-y^{2}}}\right)^{2}}}={\sqrt {1-(1-y^{2})}}={\sqrt {y^{2}}}=|y|=y.$$

$\Box$

(b) Since $f(f^{-1}(x))=x$ for every $x\in [0,1]$, we have $$x={\sqrt {1-(f^{-1}(x))^{2}}}\implies x^{2}=1-(f^{-1}(x))^{2}\implies f^{-1}(x)=\pm {\sqrt {1-x^{2}}}.$$ But the codomain of the inverse function $f^{-1}$ is $[0,1]$. So we should choose the positive square root as the formula, i.e., $$f^{-1}(x)={\sqrt {1-x^{2}}}.$$

Remark.

• It turns out that, in this case the function $f$ is equal to its inverse function $f^{-1}$.

Image sets and preimage sets

The concepts discussed in this section are the generalizations of the concepts of image and pre-image.

Definition. (Image (set) and preimage (set)) Let $A$ and $B$ be sets, and let $f:A\to B$ be a function.

(a) Suppose $X\subseteq A$. The image (set) of $X$ is the set $$f(X)=\{y\in B:y=f(x){\text{ for some }}x\in X\}\subseteq B.$$ (b) Suppose $Y\subseteq B$. The preimage (set) of $Y$ is the set $$f^{-1}(Y)=\{x\in A:f(x)\in Y\}\subseteq A.$$

Remark.

• Notice that the "$f^{-1}$" used in the notation for the preimage set is not referring to the inverse function. The preimage set $f^{-1}(Y)$ of $Y$ still makes sense even if the function $f$ is not bijective. However, the inverse function $f^{-1}$ does not exist if the function $f$ is not bijective.
• In other words, the image set contains the image of every element $x\in X$. So, it is a set of images, and hence the name.
• On the other hand, the preimage set contains the pre-images of every element $y\in Y$. That is, the preimage set $f^{-1}(Y)$ is the set of elements in $A$ mapped into $Y$ by $f$.
• Special case: suppose $a\in A$ and $b\in B$. Then, the image set of $\{a\}$ is the set containing image of $a$ under $f$: $\{f(a)\}$, and the preimage of set $\{b\}$ is the set containing the preimages (if any) of $b$ under $f$.

Graphically, the image set looks like:

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

The preimage set looks like

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

Example. Let $A=\{1,2,3,4,5,6,7\}$ and $B=\{a,b,c,d,e\}$. Consider the function $f:A\to B$ defined by $$f=\{(1,a),(2,a),(3,b),(4,b),(5,d),(6,d),(7,a)\}.$$ Then,

• $f(\{1,3\})=\{a,b\}$
• $f^{-1}(\{a,b\})=\{1,2,3,4\}$
• $f(\{1,2,3,4\})=\{a,b\}$
• $f(\{1,2,3,4,5,6,7\})=\{a,b,d\}$
• $f^{-1}(\{c\})=\varnothing$
• $f^{-1}(\{a,c,d,e\})=\{1,2,5,6,7\}$
• $f(\{1,2,5,6,7\})=\{a,d\}$

Remark.

• Notice that $f$ is not bijective, but it is still meaningful to consider the preimage sets of $f$. For instance, we have $f^{-1}(\{a\})=\{1,2\}$, but "$f^{-1}(a)$" has no meaning since $f^{-1}$ does not exist at all.
• We can observe that $f(\{1,3\})=\{a,b\}$ but $f^{-1}(\{a,b\})=\{1,2,3,4\}$. So, $f^{-1}(f(X))\neq X$ in general. Also, we can notice that after "applying" the image set and then preimage set on a set $X$, it seems that we may get some set that is larger than $X$.
• On the other hand, we can see that $f^{-1}(\{a,c,d,e\})=\{1,2,5,6,7\}$ but $f(\{1,2,5,6,7\})=\{a,d\}$. So, $f(f^{-1}(Y))\neq Y$ in general. Also, it seems that we get some set that is smaller than $X$.
• Such kind of results turns out to be true in general (see the following theorem).

Exercise. Consider a function $f:A\to B$. Find (a) $f(A)$; (b) $f^{-1}(B)$; (c) $f(\varnothing )$; (d) $f^{-1}(\varnothing )$.

Solution

(a) $f(A)=\{y\in B:y=f(x){\text{ for some }}x\in A\}=\operatorname {ran} f$.

(b) $f^{-1}(B)=\{x\in A:\underbrace {f(x)\in B} _{\text{always true}}\}=A$.

(c) $f(\varnothing )=\{y\in B:\underbrace {y=f(x){\text{ for some }}x\in \varnothing } _{\text{always false}}\}=\varnothing$.

(d) $f^{-1}(\varnothing )=\{x\in A:\underbrace {f(x)\in \varnothing } _{\text{always false}}\}=\varnothing$.

Proposition. Let $A$ and $B$ be sets, and let $f:A\to B$ be a function. Then,

(a) $X\subseteq f^{-1}(f(X))$ for every subset $X\subseteq A$.

(b) $f(f^{-1}(Y))\subseteq Y$ for every subset $Y\subseteq B$.

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\implies f(x)\in f(X)\implies 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$.

$\Box$

Exercise. Propose an additional assumption on the function $f$ so that (a) $X=f^{-1}(f(X))$ under this assumption; (b) $Y=f(f^{-1}(Y))$ under this assumption. Then, prove them. (Hint: the assumption is either "$f$ is injective" or "$f$ is surjective". Construct some simple examples of injective/surjective functions to make your choice.)

Solution

(a) The assumption is "$f$ is injective".

Proof. It suffices to show that $f^{-1}(f(X))\subseteq X$, since another subset inclusion is immediate by the proposition above. For every $x$, $${\begin{aligned}x\in f^{-1}(f(X))&\implies f(x)\in f(X)\\&\implies f(x)=f(x'){\text{ for some }}x'\in X\\&\implies x=x'&({\text{injective}}).\end{aligned}}$$

$\Box$

(b) The assumption is "$f$ is surjective".

Proof. It suffices to show that $Y\subseteq f^{-1}(f(Y))$. For every $y$, assume $y\in Y$. Then, since $f$ is surjective, $y=f(x)$ for some $x\in A$. This means $x\in f^{-1}(Y)$ since $f(x)\in Y$. Combining this with the previous equation, we have $y=f(x)$ for some $x\in f^{-1}(Y)$. Thus, $y\in f(f^{-1}(Y))$ by the definition of image set.

$\Box$

Exercise. Prove or disprove that (a) if $x\in X$, then $f(x)\in f(X)$; (b) if $f(x)\in f(X)$, then $x\in X$.

Solution

(a)

Proof. Assume $x\in X$. Then by definition of image set, $f(x)\in f(X)$.

$\Box$

(b)

Disproof. Take $A=\{1,2\}$, $B=\{1\}$, and the function $f:A\to B$ defined by $f=\{(1,1),(2,1)\}$. Then, take $x=2$ and $X=\{1\}$. After that, we have $f(x)=1\in \{1\}=f(X)$, but $x=2\notin \{1\}=X$.

$\Box$

Cardinalities of sets

Recall that a set is $S$ finite 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 infinite sets undefined. But, it turns out that we can define cardinalities of infinite sets in a more complicated way, using bijective functions.

It may now seem that we can write something like $|S|=\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 finite sets.

Example. Let $A=\{a,b,c\}$ and $B=\{1,2,3\}$. We can then clearly observe that $|A|=|B|=3$, just by counting the number of elements contained by each of them. Alternatively, we can pair off the elements of $A$ and $B$ in this way: $${\begin{array}{c|ccc}A&a&b&c\\&\updownarrow &\updownarrow &\updownarrow \\B&1&2&3\\\end{array}}$$ More precisely, such pairing defines a bijective function $f:A\to B$ given by $$f=\{(a,1),(b,2),(c,3)\}.$$

This example suggests that for two finite (nonempty) sets $A$ and $B$, they have the same cardinality if there exists a bijective function from $A$ to $B$ (or from $B$ to $A$. One such function is given by the inverse function of the bijective function from $A$ to $B$.) This leads us to the following definition:

Definition. Two (finite or infinite) sets $A$ and $B$ have the same cardinality (or are numerically equivalent), written $|A|=|B|$, if $A$ and $B$ are both empty, or there exists a bijective function from $A$ to $B$.

Remark.

• If two sets have different cardinalities, then we write $|A|\neq |B|$. Having different cardinalities means ($A$ is nonempty or $B$ is nonempty) and (for every function from $A$ to $B$, the function is not bijective). (The latter one, in other words, means there does not exist bijective function from $A$ to $B$.)
• It does not matter for the bijective function to be from $A$ to $B$, or from $B$ to $A$. Since existence of one of them implies the existence of another one, by considering the inverse function.
• For finite sets (including empty set), this definition is a bit redundant since we can simply count the number of elements in a finite set. But for infinite sets, this definition is the basis for comparing their cardinalities or "sizes".
• From this definition, we also know that a finite set and an infinite set cannot have the same cardinality, since there must not exist a bijective function from from a finite set to an infinite set (one can show this using proof by contradiction).

Example. Let $E$ be the set of all even integers, i.e., $E=\{2x:x\in \mathbb {Z} \}$. Prove that $\mathbb {Z}$ and $E$ are numerically equivalent.

Proof. Define a function $f:\mathbb {Z} \to E$ by $f(x)=2x$. Now, it remains to prove that it is bijective.

Injective: For every $x,y\in \mathbb {Z}$, $f(x)=f(y)\implies 2x=2y\implies x=y$.

Surjective: For every $y\in E$, choose $x={\frac {y}{2}}\in \mathbb {Z}$. Then, $f(x)=2(y/2)=y$.

$\Box$

Exercise. Let $O$ be the set of all odd integers.

(a) Prove that $\mathbb {Z}$ and $O$ are numerically equivalent.

(b) Prove that $E$ and $O$ are numerically equivalent.

Solution

(a)

Proof. Define a function $f:\mathbb {Z} \to O$ by $f(x)=2x+1$. Now, it remains to prove that it is bijective.

Injective: For every $x,y\in \mathbb {Z}$, $f(x)=f(y)\implies 2x+1=2y+1\implies x=y$.

Surjective: For every $y\in O$, choose $x={\frac {y-1}{2}}\in \mathbb {Z}$. Then, $f(x)=2\left({\frac {y-1}{2}}\right)+1=y-1+1=y$.

$\Box$

(b)

Proof. Define a function $f:E\to O$ by $f(x)=x+1$. Now, it remains to prove that it is bijective.

Injective: For every $x,y\in \mathbb {Z}$, $f(x)=f(y)\implies x+1=y+1\implies x=y$.

Surjective: For every $y\in O$, choose $x=y-1\in E$. Then, $f(x)=y-1+1=y$.

$\Box$

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 infinite sets.

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

Theorem. For every set $A,B,C$,

• (reflexivity) $A$ is numerically equivalent to $A$.
• (symmetry) If $A$ is numerically equivalent to $B$, then $B$ is numerically equivalent to $A$.
• (transitivity) If $A$ is numerically equivalent to $B$, and $B$ is numerically equivalent to $C$, then $A$ is numerically equivalent to $C$.

Proof.

Reflexivity:

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

Case 2: $A$ is nonempty. Then, consider the identity function $id_{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 not 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$ and $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.

$\Box$

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:

Definition. (Denumerable sets) A set $A$ is denumerable if $A$ is numerically equivalent to $\mathbb {N}$, i.e., there exists a bijective function $f:\mathbb {N} \to A$.

Remark.

• Again, the bijective function can be from $A$ to $\mathbb {N}$, and it does not matter.
• By the reflexivity of numerical equivalence, $\mathbb {N}$ itself is denumerable.
• Since $\mathbb {N}$ is an infinite set, to be numerically equivalent to it, the set $A$ must be infinite. That is, being an infinite set is a necessary (but not sufficient) condition for it to be denumerable.
• The existence of such bijective function $f:\mathbb {N} \to A$ allows us to list out the denumerable set $A$ as an infinite list $f(1),f(2),f(3),\dotsc$. Thus, we can list out the elements of $A$ as $a_{1},a_{2},a_{3},\dotsc$, i.e., $A$ can be expressed as $\{a_{1},a_{2},a_{3},\dotsc \}$.

• Conversely, assuming $a_{i}\neq a_{j}$ for every $i\neq j$ (to ensure injectivity), then we can define a function $f:\mathbb {N} \to A$ by $f(n)=a_{n}$, which is bijective, based on the above infinite list.

• The cardinality of $\mathbb {N}$ is denoted by $|\mathbb {N} |$, or $\aleph _{0}$ (read "aleph-zero" or "aleph-naught"). So, the cardinality of every denumerable set is $\aleph _{0}$.

Using this definition, we can further define another property of a set:

Definition. (Countable sets) A set $A$ is countable if it is either finite or denumerable. A set that is not countable is uncountable.

Remark.

• Intuitively, we can still "count" the elements in a denumerable set. Also, we can clearly count the elements in a finite set. Hence, we call them as countable sets.
• From this definition, we know that countably infinite sets are exactly the same as denumerable sets. In some other places, the term "countably infinite sets" is used instead of "denumerable sets".
• Also, from this definition, we know that a set that is uncountable is necessarily infinite.

Example. Prove that the set $\mathbb {Z}$ is denumerable.

To prove this, we need to construct a bijective function $f:\mathbb {N} \to \mathbb {Z}$. So, we should have a one-to-one corresponding pairing between positive integers and integers.

Idea: we can label the integers as an infinite "queue": $${\begin{array}{ccccccc}{\text{Label}}&5&3&1&2&4\\\hline \cdots &-2&-1&0&1&2&\cdots \end{array}}$$ From this, we get an infinite "queue" of integers: $0,1,-1,2,-2,\dotsc$.

Proof. The following pairing suggests a way to construct a bijective function $f:\mathbb {N} \to \mathbb {Z}$: $${\begin{array}{c|cccccc}\mathbb {N} &1&2&3&4&5&\cdots \\&\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow \\\mathbb {Z} &0&1&-1&2&-2&\cdots \\\end{array}}$$ More precisely, we can define the function $f:\mathbb {N} \to \mathbb {Z}$ by $$f(n)={\begin{cases}{\frac {n}{2}},&{\text{ if }}n{\text{ is even}};\\{\frac {1-n}{2}},&{\text{ if }}n{\text{ is odd}}.\end{cases}}$$ Then, it remains to prove that this function is bijective.

Injective: For every $m,n\in \mathbb {N}$,

Case 1: $m$ and $n$ are both even. Then, $f(m)=f(n)\implies {\frac {m}{2}}={\frac {n}{2}}\implies m=n$.

Case 2: $m$ and $n$ are both odd. Then, $f(m)=f(n)\implies {\frac {1-m}{2}}={\frac {1-n}{2}}\implies 1-m=1-n\implies m=n$.

Case 3: $m$ and $n$ have different parities. Then, it is impossible to have $f(m)=f(n)$, since $f(m)$ is nonnegative, while $f(n)$ is negative. The result follows.

Surjective: For every $y\in \mathbb {Z}$,

Case 1: $y$ is nonnegative. Then, choose $n=2y\in \mathbb {N}$, which is even. So, we have $f(n)={\frac {2y}{2}}=y$.

Case 2: $y$ is negative. Then, choose $n=1-2y\in \mathbb {N}$, which is odd. So, we have $f(n)={\frac {1-(1-2y)}{2}}={\frac {2y}{2}}=y$.

$\Box$

Remark.

• The function above can also be defined using a single formula:

$$f(n)={\frac {1+(-1)^{n}(2n-1)}{4}}.$$

• This result is again quite weird, since $\mathbb {N} \subset \mathbb {Z}$, but $|\mathbb {N} |=|\mathbb {Z} |$.
• By the transitivity and symmetry of numerical equivalence, the set of all even integers and the set of all odd integers are also denumerable.

Exercise. Let $S_{3}$ be the set of all multiples of 3. Prove or disprove that $S_{3}$ is denumerable.

Solution

Proof. Let us first prove that $\mathbb {Z}$ is numerically equivalent to $S_{3}$. Define the function $f:\mathbb {Z} \to S_{3}$ by $f(n)=3n$. We now prove that $f$ is bijective:

Injective: For every $m,n\in \mathbb {Z}$, $f(m)=f(n)\implies 3m=3n\implies m=n$.

Surjective: For every $y\in S_{3}$, choose $n={\frac {y}{3}}\in \mathbb {Z}$. Then, $f(n)=3(y/3)=y$.

Then, since $\mathbb {Z}$ is numerically equivalent to $\mathbb {N}$, it follows that $S_{3}$ is numerically equivalent to $\mathbb {N}$. Thus, $S_{3}$ is denumerable.

$\Box$

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.

Example.

(a) Prove that the set of all positive rational numbers, $\mathbb {Q} ^{+}$ is denumerable.

(b) Hence, prove that the set of all rational numbers, $\mathbb {Q}$ is denumerable.

Solution.

(a) First, consider the following diagram:

This diagram arranges all rational numbers in an infinite array. Then, we obtain an infinite list of all rational numbers, following the arrows in the diagram: $${\frac {1}{1}},{\frac {2}{1}},{\frac {1}{2}},{\frac {1}{3}},{\color {red}{\frac {2}{2}}},{\frac {3}{1}},{\frac {4}{1}},\dotsc$$

Proof. Using the above infinite list, we can then define a bijective function $f:\mathbb {N} \to \mathbb {Q} ^{+}$: $$f(1)={\frac {1}{1}},f(2)={\frac {2}{1}},f(3)={\frac {1}{2}},f(4)={\frac {1}{3}},{\cancel {f(5)={\color {red}{\frac {2}{2}}},}}f(5)={\frac {3}{1}},\dotsc$$ In other words, the one-to-one corresponding pairing is $${\begin{array}{c|ccccccc}\mathbb {N} &1&2&3&4&5&6&\cdots \\&\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow \\\mathbb {Q} ^{+}&{\frac {1}{1}}&{\frac {2}{1}}&{\frac {1}{2}}&{\frac {1}{3}}&{\frac {3}{1}}&{\frac {4}{1}}&\cdots \end{array}}$$ In particular, we skip ${\color {red}{\frac {2}{2}}}$ for the function, since this number is the same as ${\frac {1}{1}}$. So, to ensure the injectivity of the function $f$, we need to skip such repeated rational number. (The red numbers in the above diagram are the repeated rational numbers, and we have to skip them all in the definition of the function.) Such function $f$ is bijective (since for every $n\in \mathbb {N}$, there exists a unique $y\in \mathbb {Q} ^{+}$ such that $f(n)=y$), and so $\mathbb {Q} ^{+}$ is denumerable.

$\Box$

(b)

Proof. Since $\mathbb {Q} ^{+}$ is denumerable, we are allowed to write $\mathbb {Q} ^{+}=\{q_{1},q_{2},q_{3},\dotsc \}$. Similarly, we can write the set of all negative rational numbers as $\mathbb {Q} ^{-}=\{-q_{1},-q_{2},-q_{3},\dotsc \}$. Hence, we can write the set of all rational numbers as $$\mathbb {Q} =\mathbb {Q} ^{+}\cup \{0\}\cup \mathbb {Q} ^{-}=\{q_{1},q_{2},q_{3},\dotsc \}\cup \{0\}\cup \{-q_{1},-q_{2},-q_{3},\dotsc \}=\{0,q_{1},-q_{1},q_{2},-q_{2},\dotsc \}.$$ More precisely, we can define a function $f:\mathbb {N} \to \mathbb {Q}$ by $$f(1)=0,f(2)=q_{1},f(3)=-q_{1},f(4)=q_{2},f(5)=-q_{2},\dotsc$$ (similar to the function for proving that $\mathbb {Z}$ is denumerable) In other words, the one-to-one corresponding pairing is $${\begin{array}{c|cccccc}\mathbb {N} &1&2&3&4&5&\cdots \\&\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow \\\mathbb {Q} &0&q_{1}&-q_{1}&q_{2}&-q_{2}&\cdots \end{array}}$$ This function $f$ can be proved to be bijective (very similar proof as in the proof for $\mathbb {Z}$ is denumerable, but we now consider the indexes of "$q$"), and hence $\mathbb {Q}$ is denumerable.

$\Box$

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, $\mathbb {R}$. In other words, there does not exist a bijective function from $\mathbb {N}$ to $\mathbb {R}$. Since $\mathbb {R}$ is uncountable, this suggests that the "size" of $\mathbb {R}$ is different from the "size" of $\mathbb {N}$, i.e., there are different sizes of infinity (in some sense).

Example.

(a) Let $a,b\in \mathbb {R}$ with $b>a$. Construct a bijective function $f:(0,1)\to (a,b)$

(b) Using the bijective function in (a), prove that $|(a,b)|=|(c,d)|$ for every $a,b,c,d\in \mathbb {R}$ with $b>a$ and $d>c$.

(c) Prove that the open interval $(0,1)$ is uncountable.

(d) Prove that $|(a,b)|=|\mathbb {R} |$ for every $a,b\in \mathbb {R}$ with $b>a$. (Hint: You can use without proof the fact that the tangent function $\tan :(-\pi /2,\pi /2)\to \mathbb {R}$ is bijective.)

Solution.

(a) Define a function $f:(0,1)\to (a,b)$ by $$f(x)=a+(b-a)x.$$ Now, we prove that $f$ is bijective.

Proof.

Injective: For every $x,y\in (0,1)$, $$f(x)=f(y)\implies a+(b-a)x=a+(b-a)y\implies (b-a)x=(b-a)y\implies x=y$$.

Surjective: For every $y\in (a,b)$, choose $x={\frac {y-a}{b-a}}\in (0,1)$. Then, $$f(x)=a+(b-a)\cdot {\frac {y-a}{b-a}}=a+y-a=y.$$

$\Box$

(b)

Proof. By (a), we can construct a bijective function $f:(0,1)\to (a,b)$, and also a bijective function $g:(0,1)\to (c,d)$. These mean $|(0,1)|=|(a,b)|$ and $|(0,1)|=|(c,d)|$. Then, by the symmetry and transitivity of numerical equivalence, we have $|(a,b)|=|(c,d)|$.

$\Box$

(c) One can use the Cantor's diagonal argument to prove it.

(d)

Proof. Since the tangent function $\tan :(-\pi /2,\pi /2)\in \mathbb {R}$ is bijective, we have $|(-\pi /2,\pi /2)|=|\mathbb {R} |$. Also, from part (b), we have for every $a,b\in \mathbb {R}$ with $b>a$, $|(a,b)|=|(-\pi /2,\pi /2)|$. The result then follows from the transitivity of numerical equivalence.

$\Box$

Remark.

• Part (d) says in particular $|(0,1)|=|\mathbb {R} |$. So, this implies that $\mathbb {R}$ is uncountable, since if it is countable (i.e., denumerable in this case) and $|(0,1)|=|\mathbb {R} |$, then it means $(0,1)$ is denumerable, causing a contradiction.

The following results may be useful for comparing denumerable or uncountable sets.

Proposition. Every infinite subset of a denumerable set is denumerable.

Example. Let $P$ be the set of all prime numbers. Prove that $P$ is denumerable.

Proof. Recall that we have proved there are infinitely many prime numbers. Then, since $P$ is an infinite subset of $\mathbb {N}$ (which is denumerable), it follows that $P$ is denumerable.

$\Box$

Exercise. Prove that the set $S=\{2^{n}:n\in \mathbb {Z} \}=\left\{\dotsc ,{\frac {1}{8}},{\frac {1}{4}},{\frac {1}{2}},1,2,4,8,\dotsc \right\}$ is denumerable.

Proof

Proof. Since the set $S$ is an infinite subset of $\mathbb {Q}$, and $\mathbb {Q}$ is denumerable, it follows that $S$ is denumerable.

$\Box$

Example. Prove that for every finite subset $S$ of $\mathbb {N}$, $|\mathbb {N} \setminus S|=|\mathbb {N} |$. (This means that no matter we "take away" how many elements from $\mathbb {N}$, as long as the number of elements taken away is finite, then the cardinality is not affected.)

Proof. First, we have $\mathbb {N} \setminus S\subseteq \mathbb {N}$, and $\mathbb {N}$ is denumerable. So, it remains to prove that $\mathbb {N} \setminus S$ is infinite. We prove it by contradiction.

Assume to the contrary that $\mathbb {N} \setminus S$ is finite. Since $S$ is also finite, we have $$S\cup (\mathbb {N} \setminus S)=\mathbb {N}$$ is finite, contradicting to the fact that $\mathbb {N}$ is infinite.

$\Box$

Proposition. Let $A$ and $B$ be sets such that $A\subseteq B$. If $A$ is uncountable, then $B$ is uncountable.

Remark.

• Using this result, we can give an alternative proof that $\mathbb {R}$ is uncountable (we have $(0,1)$ is uncountable and $(0,1)\subseteq \mathbb {R}$).

Example. Prove that $[a,b]$ is uncountable for every $a,b\in \mathbb {R}$ with $b>a$.

Proof. Since $(a,b)\subseteq [a,b]$ and $(a,b)$ is uncountable, we conclude that $[a,b]$ is uncountable.

$\Box$

Remark.

• Notice that this just says that $[a,b]$ is uncountable. It does not imply that $|[a,b]|=|(a,b)|$. As we will see, two uncountable sets may have different cardinalities.

Proposition. If $A$ and $B$ be denumerable sets, then $A\times B$ is denumerable.

Proposition. If $A$ and $B$ are denumerable sets, then $A\cup B$ is denumerable.

Exercise. Prove or disprove that if $A$ and $B$ are denumerable sets, then $A\cap B$ is denumerable.

Solution

Disproof. Take $A$ to be the set of all even numbers and $B$ to be the set of all odd numbers. Then, $A\cap B=\varnothing$, which is not denumerable.

$\Box$

Example.

• $\mathbb {N} \times \mathbb {N}$ is denumerable.
• $\mathbb {Q} \times \mathbb {Z}$ is denumerable.

Exercise. Prove or disprove each of the following statements:

(a) For every nonempty set $A,B$, $|A\times B|=|B\times A|$.

(b) The set of all irrational numbers, $\mathbb {I}$ is uncountable. (Hint: use proof by contradiction)

(c) Every infinite subset of $\mathbb {I}$ is uncountable.

(d) For every set $A,B,C$, if $A\subseteq B\subseteq C$, and $A,C$ are denumerable, then $B$ is denumerable.

(e) $\{{\sqrt {2}}\}\times \mathbb {Q}$ is uncountable.

(f) The set $S=\{(x,y)\in \mathbb {Z} \times \mathbb {R} :x+y=1\}$ is denumerable.

Solution

(a)

Proof. Define a function $f:A\times B\to B\times A$ by $$f(a,b)=(b,a).$$ It now remains to prove that $f$ is bijective.

Injective: For every $(a_{1},b_{1}),(a_{2},b_{2})\in A\times B$, $$f(a_{1},b_{1})=f(a_{2},b_{2})\implies (b_{1},a_{1})=(b_{2},a_{2})\implies b_{1}=b_{2}{\text{ and }}a_{1}=a_{2}\implies (a_{1},b_{1})=(a_{2},b_{2}).$$ Surjective: For every $(x,y)\in B\times A$, choose $(a,b)=(y,x)\in A\times B$. Then, $$f(a,b)=(b,a)=(x,y).$$

$\Box$

(b)

Proof. Assume to the contrary that $\mathbb {I}$ is countable. Since $\mathbb {I}$ is infinite, this means $\mathbb {I}$ is denumerable. Also, since $\mathbb {Q}$ is denumerable, it follows that $$\mathbb {I} \cup \mathbb {Q} =\mathbb {R}$$ is denumerable, contradicting to the fact that $\mathbb {R}$ is uncountable.

$\Box$

(c)

Disproof. Consider the set $S=\{k+{\sqrt {2}}:k\in \mathbb {N} \}\subseteq \mathbb {I}$. Then, define the function $f:\mathbb {N} \to S$ by $$f(n)=n+{\sqrt {2}}.$$ It remains to prove that $f$ is bijective.

Injective: For every $m,n\in \mathbb {N}$, $f(m)=f(n)\implies m+{\sqrt {2}}=n+{\sqrt {2}}\implies m=n$.

Surjective: For every $y\in S$, choose $n=y-{\sqrt {2}}\in \mathbb {N}$. Then, $f(n)=y-{\sqrt {2}}+{\sqrt {2}}=y$.

$\Box$

(d)

Proof. Assume $A\subseteq B\subseteq C$ and $A,C$ are denumerable. Since $B\subseteq C$ and $C$ is denumerable, it remains to prove that $B$ is infinite. But since $A$ is denumerable, and hence infinite, and also $A\subseteq B$, $B$ must be infinite. We are done.

$\Box$

(e)

Disproof. Let $S$ be the set $\{{\sqrt {2}}\}\times \mathbb {Q}$. Define a function $f:\mathbb {Q} \to S$ by $$f(q)=({\sqrt {2}},q).$$ It now remains to prove that $f$ is bijective.

Injective: For every $q_{1},q_{2}\in \mathbb {Q}$, $f(q_{1})=f(q_{2})\implies ({\sqrt {2}},q_{1})=({\sqrt {2}},q_{2})\implies q_{1}=q_{2}$.

Surjective: For every $(x,y)\in S$, choose $q=y\in \mathbb {Q}$. Then, $f(q)=({\sqrt {2}},y)=(x,y)$ ($x$ must be ${\sqrt {2}}$).

$\Box$

(f)

Proof. For every $x\in \mathbb {Z}$, the only real number $y$ such that $x+y=1$ is $y=1-x$. Thus, we can express the set $S$ as $$S=\{(x,1-x)\in \mathbb {Z} \times \mathbb {R} :x\in \mathbb {Z} \}.$$ Then, we can define a function $f:S\to \mathbb {Z}$ by $$f(x,y)=x.$$ It now remains to prove that $f$ is bijective.

Injective: For every $(x_{1},y_{1}),(x_{2},y_{2})\in S$, $f(x_{1},y_{1})=f(x_{2},y_{2})\implies x_{1}=x_{2}\implies (x_{1},1-x_{1})=(x_{2},1-x_{2})\implies (x_{1},y_{1})=(x_{2},y_{2})$.

Surjective: For every $z\in \mathbb {Z}$, choose $(x,y)=(z,1-z)\in S$. Then, $f(x,y)=z$.

$\Box$