5.2 Workshop 2 (Reading)

5.2.1 Preparatory Exercises (1 hour)

Task 5.10.

Find an example and a non-example for each of the following definitions.

Definition (Injective, injection).

A function $f:D\to C$ is said to be injective (or an injection) if $f(x_{1})=f(x_{2})$ implies $x_{1}=x_{2}$ for every $x_{1},x_{2}\in D$ .

Definition (Surjective, surjection).

A function $f:D\to C$ is said to be surjective (or a surjection) if, given any $y\in C$ , there is some $x\in D$ such that $f(x)=y$ .

Definition (Bijective, bijection).

A function is said to be bijective if it is both injective and surjective.

Task 5.11.

Consider the function $f:\mathbb{R}\rightarrow\mathbb{R}$ such that

f(x)=\begin{cases}x+1,\text{ if }x<0,\\ 2x+a,\text{ if }x\geqslant 0,\end{cases}

where $a$ is some real number.

Is $f$ injective? Is $f$ surjective?

Task 5.12.

Read the proofs of Claim A and Claim B (below).

1.

Highlight the key parts of the proofs. Are there any parts which you do not understand or are not convinced by?
2.

Compare the two proofs. What are the key differences between them?
3.

Consider $f$ in Claim A. Is $f$ bijective? Can you change the domain so that $f$ is no longer injective? Where does the proof break down?
4.

Consider $g$ in Claim B. Is $g$ bijective? Can you change the codomain so that $g$ is no longer surjective? Where does the proof break down?

Note: We define $\mathbb{N}_{0}=\mathbb{N}\cup\{0\}$ .

Claim A: The function $f\colon\mathbb{N}_{0}\rightarrow\mathbb{N}_{0}$ defined by $f(n)=n^{2}$ is injective.

Proof.

Let $m,n\in\mathbb{N}_{0}$ be such that $f(m)=f(n)$ . Then $m^{2}=n^{2}$ , and so

0=m^{2}-n^{2}=(m-n)(m+n).

If $m+n=0$ then $m=0$ and $n=0$ , so $m=n$ . Otherwise, $m-n=0$ , so $m=n$ . Thus $f$ is injective.

Claim B: The function $g\colon\mathbb{R}\rightarrow[-5,+\infty)$ defined by $g(x)=x^{2}+2x-4$ is surjective.

Proof.

Let $y\geq-5$ . We need to show there is some $x\in\mathbb{R}$ such that $g(x)=y$ . Observe that $g(x)=y\iff x^{2}+2x-4=y$ . By the quadratic formula, that means

x=\frac{-2\pm\sqrt{4+4(4+y)}}{2}

and since $y\geq-5$ , the square root is defined and this gives our value for $x$ . Thus, since we can find such an $x\in\mathbb{R}$ for every $y\in[-5,\infty)$ , this implies that $g$ is surjective.

5.2.2 B3 Reading Workshop Supplementary Material

For Task B3.2.1:

Theorem.

Let $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ be functions.

1.

If $f$ and $g$ are injective, so is $g\circ f$ .
2.

If $f$ and $g$ are surjective, so is $g\circ f$ .
3.

If $f$ and $g$ are bijective, so is $g\circ f$ .

Proof.

1.

Suppose $f$ and $g$ are injective. To show that $g\circ f$ is injective, we need to show that if $...$ (with $x,x^{\prime}\in X$ ), then $...$ .

So, suppose $x,x^{\prime}\in X$ satisfies $...$ . Then $g(f(x))=g(f(x^{\prime}))$ . Since $g$ is $...$ , this means $...$ . Since $f$ is $...$ this implies $...$ , as desired.

This completes the proof that $g\circ f$ is injective.
2.

Now suppose $f$ and $g$ are surjective. To show that $g\circ f$ is surjective, we need to show that for all $...$ , there is some $...$ such that $...$ .

Let $z\in Z$ . Since $g$ is $...$ , there is some $...$ such that $...$ . Since $f$ is $...$ , there is some $x\in X$ such that $...$ . Then

$...$

as desired.

This finishes the proof that $g\circ f$ is surjective.
3.

If $g$ and $f$ are bijective, then they are both injective and surjective, so by the previous two parts, $g\circ f$ is also both injective and surjective, hence $g\circ f$ is bijective.

For Task B3.2.2:

Theorem.

Let $X$ and $Y$ be finite sets and let $f:X\rightarrow Y$ be a function.

a)

If $f$ is injective, then $|X|\leq|Y|$ .
b)

If $f$ is surjective, then $|X|\geq|Y|$ .
c)

If $f$ is bijective, then $|X|=|Y|$ .

5.1.

Since $Y$ is finite, we can list its elements as $y_{1},\ldots,y_{m}$ where $m=|Y|$ .

5.2.

If $f$ is injective, then the elements $f(x_{1}),\ldots,f(x_{n})$ are distinct.

5.3.

Therefore there are exactly $m$ elements in the set $A=\{x_{1},\ldots,x_{m}\}$ .

5.4.

Since $X$ is finite, we can list its elements as $x_{1},\ldots,x_{n}$ where $n=|X|$ .

5.5.

Since this is a subset of $Y$ , the set $Y$ must have at least as many elements as $B$ , so $|Y|\geq n=|X|$ .

5.6.

If $f$ is surjective, then for each $i=1,\ldots,m$ , we can choose distinct $x_{i}\in X$ such that $f(x_{i})=y_{i}$ .

5.7.

Since this is a subset of $X$ , the set $X$ must have at least as many elements as $A$ , so $|X|\geq m=|Y|$ .

5.8.

This follows by combining results (a) and (b).

5.9.

Therefore there are exactly $n$ elements in the set $B=\{f(x_{1}),\ldots,f(x_{n}))\}$ .

For Task B3.2.3:

Definition (Countable and uncountable sets).

A set $S$ is said to be countable if it is finite or if there is a bijection from $\mathbb{N}$ to $S$ .

An infinite countable set is said to be countably infinite.

A set that is not countable is said to be uncountable.

Claim.

Consider the function $f:\mathbb{N}\to\mathbb{Z}$ which is defined by:

f(n)=\begin{cases}-\frac{n}{2}&\text{if $n$ is even,}\\ \frac{n-1}{2}&\text{if $n$ is odd.}\end{cases}

The function $f$ is bijective.

Proof.

For $f$ to be bijective, it needs to be both injective and surjective.

To show that $f$ is injective, we need to show that if $f(n)=f(n^{\prime})$ for $n,n^{\prime}\in\mathbb{N}$ , then $n=n^{\prime}$ .

So, suppose $n,n^{\prime}\in\mathbb{N}$ such that $f(n)=f(n^{\prime})$ . Then, $n$ is either even or odd. If $n$ is even, then $f(n)=-\frac{n}{2}=-\frac{n^{\prime}}{2}=f(n^{\prime})$ . Rearranging, we get $n=n^{\prime}$ as desired.

Alternatively, if $n$ is odd, then $f(n)=\frac{n-1}{2}=\frac{n^{\prime}-1}{2}=f(n^{\prime})$ . Again, rearranging gives $n=n^{\prime}$ .

This completes the proof that $f$ is injective.

To show that $f$ is surjective, we need to show that for all $m\in\mathbb{Z}$ , there is some $n\in\mathbb{N}$ such that $m=f(n)$ .

Let $m\in\mathbb{Z}$ . If $m$ is non-negative, then we can take $n=2m+1$ . Note that $n$ is an odd natural number so $f(n)=\frac{2m+1-1}{2}=m$ as desired.

On the other hand, if $m$ is negative, then we can set $n=-2m$ . Then $n$ is an even positive number and hence a natural number. We have $f(n)=-\frac{-2m}{2}=m$ .

Therefore $f$ is surjective.

As $f$ is both surjective and injective, it is bijective.

Corollary.

The set $\mathbb{Z}$ is countable.

For Task B3.2.4:

Theorem.

Let $S$ be any infinite set. The following are equivalent:

(i)

$S$ is countably infinite;
(ii)

there is a surjection from $\mathbb{N}$ to $S$ ;
(iii)

there is an injection from $S$ to $\mathbb{N}$ .

Proof.

•

(i) $\Rightarrow$ (ii): If $S$ is countably infinite then, by definition, there is a bijection from $\mathbb{N}$ to $S$ . Thus there is a surjection from $\mathbb{N}$ to $S$ .
•

(ii) $\Rightarrow$ (iii): Suppose $f:\mathbb{N}\to S$ is surjective. Then, for any $x\in S$ , the set $f^{-1}(\{x\})\subseteq\mathbb{N}$ is nonempty and so has a unique smallest element, call it $n_{x}$ . Then $g:S\to\mathbb{N}$ defined by $g(x)=n_{x}$ is injective.
•

(iii) $\Rightarrow$ (i): Suppose $h:S\to\mathbb{N}$ is injective. Then, since $S$ is an infinite set and no pair of elements in $S$ are mapped (under $h$ ) to the same natural number, $h(S)$ is an infinite subset of $\mathbb{N}$ and is therefore countable.

5.2.3 Workshop Tasks

Task 5.13 (5 mins).

(Warm Up)

1.
In your Preparatory Exercises, you were asked to consider the function $f:\mathbb{R}\rightarrow\mathbb{R}$ such that

$f(x)=\begin{cases}x+1,\text{ if }x<0,\\ 2x+a,\text{ if }x\geqslant 0,\end{cases}$

where $a$ is some real number.
1. (a)
  
  Did you think the function is injective or surjective (or both)? Share your thoughts with your group.
2. (b)
  
  Sketch the graph of $f$ . Can you think of a visual way to indicate when a function is injective, surjective or bijective?
2.

What key steps for proving injectivity and surjectivity did you highlight in the proofs of Claim A and Claim B in the Preparatory Exercises? Share them with your group.
3.

EXTENSION: Try to draft a proof of the claims you made for the function $f$ .

Task 5.14 (10 mins).

If we have a bijective function $f:D\to C$ , we can define a new function $f^{-1}:C\to D$ such that $f^{-1}(y)=x\iff f(x)=y$ and we call $f^{-1}$ the inverse of $f$ . This means that $f\circ f^{-1}$ and $f^{-1}\circ f$ are identity functions.

1.

If $f:D\to C$ is NOT bijective, is $f^{-1}:C\to D$ such that $f^{-1}(y)=x\iff f(x)=y$ a valid function?
2.

What is wrong with the following argument?

“Suppose $f:S\to T$ is a function with $A\subseteq S$ and $B\subseteq T$ . Since $f\circ f^{-1}$ and $f^{-1}\circ f$ are identity functions $id_{T}$ and $id_{S}$ by definition of the inverse function $f^{-1}$ , it follows that $f(f^{-1}(B))=id_{T}(B)=B\subseteq B$ and $f^{-1}(f(A))=id_{S}(A)=A\subseteq A$ by definition of the identity function. Hence, for all functions $f$ , we have $f(f^{-1}(B))\subseteq B$ and $f^{-1}(f(A))\subseteq A$ .”
3.

EXTENSION: Prove that $f\circ f^{-1}$ and $f^{-1}\circ f$ are identity functions.

Task 5.15 (10 mins).

(B3.2.1) In your supplementary material for this task, you’ve been given a sparse proof structure for the following theorem:

Theorem.

Let $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ be functions.

1.

If $f$ and $g$ are injective, so is $g\circ f$ .
2.

If $f$ and $g$ are surjective, so is $g\circ f$ .
3.

If $f$ and $g$ are bijective, so is $g\circ f$ .

1.

Complete the proof by filling in the gaps.
2.

EXTENSION: If $g\circ f$ is injective, is $f$ or $g$ injective? If $g\circ f$ is surjective, is $f$ or $g$ surjective?

Theorem.

Let $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ be functions.

1.

If $f$ and $g$ are injective, so is $g\circ f$ .
2.

If $f$ and $g$ are surjective, so is $g\circ f$ .
3.

If $f$ and $g$ are bijective, so is $g\circ f$ .

Proof.

1.

Suppose $f$ and $g$ are injective. To show that $g\circ f$ is injective, we need to show that if $...$ (with $x,x^{\prime}\in X$ ), then $...$ .

So, suppose $x,x^{\prime}\in X$ satisfies $...$ . Then $g(f(x))=g(f(x^{\prime}))$ . Since $g$ is $...$ , this means $...$ . Since $f$ is $...$ this implies $...$ , as desired.

This completes the proof that $g\circ f$ is injective.
2.

Now suppose $f$ and $g$ are surjective. To show that $g\circ f$ is surjective, we need to show that for all $...$ , there is some $...$ such that $...$ .

Let $z\in Z$ . Since $g$ is $...$ , there is some $...$ such that $...$ . Since $f$ is $...$ , there is some $x\in X$ such that $...$ . Then

$...$

as desired.

This finishes the proof that $g\circ f$ is surjective.
3.

If $g$ and $f$ are bijective, then they are both injective and surjective, so by the previous two parts, $g\circ f$ is also both injective and surjective, hence $g\circ f$ is bijective.

Task 5.16 (15 mins).

(B3.2.2) In your supplementary material for this task you’ve been given a theorem and its proof which has been split into blocks.

1.

Represent this theorem pictorially.
2.

Rearrange the blocks into a coherent proof of the theorem. Are there any steps you are not convinced by? Discuss these with your group.
3.

Compare each line of the proof of part (a) with the line in the proof of part (b) in the same position. In what ways are they similar? In what ways are they different and why?
4.

How do we know there exist distinct $x_{1},\ldots,x_{n}$ in block 5.15?
5.

If $Y$ is the image of $f$ , is it possible for $|X|<|Y|$ ?
6.

EXTENSION: Find counterexamples that show the converse of the statements in this theorem are not true in general.

Theorem.

Let $X$ and $Y$ be finite sets and let $f:X\rightarrow Y$ be a function.

a)

If $f$ is injective, then $|X|\leq|Y|$ .
b)

If $f$ is surjective, then $|X|\geq|Y|$ .
c)

If $f$ is bijective, then $|X|=|Y|$ .

5.10.

Since $Y$ is finite, we can list its elements as $y_{1},\ldots,y_{m}$ where $m=|Y|$ .

5.11.

If $f$ is injective, then the elements $f(x_{1}),\ldots,f(x_{n})$ are distinct.

5.12.

Therefore there are exactly $m$ elements in the set $A=\{x_{1},\ldots,x_{m}\}$ .

5.13.

Since $X$ is finite, we can list its elements as $x_{1},\ldots,x_{n}$ where $n=|X|$ .

5.14.

Since this is a subset of $Y$ , the set $Y$ must have at least as many elements as $B$ , so $|Y|\geq n=|X|$ .

5.15.

If $f$ is surjective, then for each $i=1,\ldots,m$ , we can choose distinct $x_{i}\in X$ such that $f(x_{i})=y_{i}$ .

5.16.

Since this is a subset of $X$ , the set $X$ must have at least as many elements as $A$ , so $|X|\geq m=|Y|$ .

5.17.

This follows by combining results (a) and (b).

5.18.

Therefore there are exactly $n$ elements in the set $B=\{f(x_{1}),\ldots,f(x_{n}))\}$ .

Definition (Countable and uncountable sets).

A set $S$ is said to be countable if it is finite or if there is a bijection from $\mathbb{N}$ to $S$ .

An infinite countable set is said to be countably infinite.

A set that is not countable is said to be uncountable.

Task 5.17 (15 mins).

(B3.2.3) In your supplementary notes, you’ve been given a claim, its proof and a corollary.

1.

Read the claim, proof and corollary. Identify the key steps of showing a function is bijective in the given proof.
2.

In the argument that $f$ is surjective, why do we consider the cases where $m$ is negative and non-negative instead of positive and negative?
3.

Write out the values of $f(1)$ , $f(2)$ , $f(3)$ , $f(4)$ , $f(5)$ and try to spot a pattern.
4.

Write a proof for the corollary.
5.

Think of an infinite subset $A$ of $\mathbb{N}$ . Find a bijective function from $A$ to $\mathbb{N}$ . What conclusions can you make from this?
6.

EXTENSION: Find other definitions or theorems which we can use to immediately conclude corollaries after another result.

Claim.

Consider the function $f:\mathbb{N}\to\mathbb{Z}$ which is defined by:

f(n)=\begin{cases}-\frac{n}{2}&\text{if $n$ is even,}\\ \frac{n-1}{2}&\text{if $n$ is odd.}\end{cases}

The function $f$ is bijective.

Proof.

For $f$ to be bijective, it needs to be both injective and surjective.

To show that $f$ is injective, we need to show that if $f(n)=f(n^{\prime})$ for $n,n^{\prime}\in\mathbb{N}$ , then $n=n^{\prime}$ .

Alternatively, if $n$ is odd, then $f(n)=\frac{n-1}{2}=\frac{n^{\prime}-1}{2}=f(n^{\prime})$ . Again, rearranging gives $n=n^{\prime}$ .

This completes the proof that $f$ is injective.

To show that $f$ is surjective, we need to show that for all $m\in\mathbb{Z}$ , there is some $n\in\mathbb{N}$ such that $m=f(n)$ .

Let $m\in\mathbb{Z}$ . If $m$ is non-negative, then we can take $n=2m+1$ . Note that $n$ is an odd natural number so $f(n)=\frac{2m+1-1}{2}=m$ as desired.

On the other hand, if $m$ is negative, then we can set $n=-2m$ . Then $n$ is an even positive number and hence a natural number. We have $f(n)=-\frac{-2m}{2}=m$ .

Therefore $f$ is surjective.

As $f$ is both surjective and injective, it is bijective.

Corollary.

The set $\mathbb{Z}$ is countable.

Task 5.18 (10 mins).

(B3.2.4) In your supplementary material, you were given a theorem and proof for this task.

1.

Read the given theorem and proof. Are there any steps that you’re not convinced by? Discuss them with your group.
2.

The proof never directly shows (ii) $\Rightarrow$ (i). Why can we still conclude that (i) and (ii) are equivalent?
3.

EXTENSION: Try proving the statements in this theorem in the other direction i.e. prove that (iii) $\Rightarrow$ (ii), (ii) $\Rightarrow$ (i) and (i) $\Rightarrow$ (iii).

Theorem.

Let $S$ be any infinite set. The following are equivalent:

(i)

$S$ is countably infinite;
(ii)

there is a surjection from $\mathbb{N}$ to $S$ ;
(iii)

there is an injection from $S$ to $\mathbb{N}$ .

Proof.

(i) $\Rightarrow$ (ii)

If $S$ is countably infinite then, by definition, there is a bijection $\mathbb{N}\to S$ .
(ii) $\Rightarrow$ (iii)

Suppose $f:\mathbb{N}\to S$ is surjective. Then, for any $x\in S$ , the set $f^{-1}(\{x\})\subseteq\mathbb{N}$ is nonempty and so has a unique smallest element, call it $n_{x}$ . Then $g:S\to\mathbb{N}$ defined by $g(x)=n_{x}$ is injective.
(iii) $\Rightarrow$ (i)

Suppose $h:S\to\mathbb{N}$ is injective. Then, since $S$ is an infinite set and no pair of elements in $S$ are mapped (under $h$ ) to the same natural number, $h(S)$ is an infinite subset of $\mathbb{N}$ and is therefore countable.