Discrete Mathematics : Functions

Contents

• One-to-one functions
• Onto functions
• One-to-one correspondences
• Inverse functions
• Composition of functions
• Infinite sets

One-to-one functions

What is the difference between the two marriage functions?

Definition

Template

Proof: Direct proof.

• Suppose $x_1, x_2 \in X$ such that $f(x_1) = f(x_2)$.
• Show that $x_1 = x_2$.

Proof: Counterexample.

• Find $x_1, x_2 \in X$ such that $f(x_1) = f(x_2)$ but $x_1 \neq x_2$.

Example 1

Proof:
Direct proof. \begin{align*} & \text{Suppose } f(x_1) = f(x_2). \\ & \implies 4x_1 - 1 = 4x_2 - 1 \quad & \text{(Defn. of } f\text{)} \\ & \implies 4x_1 = 4x_2 \quad & \text{(Add 1 on both sides)} \\ & \implies x_1 = x_2 \quad & \text{(Divide by 4)} \\ \end{align*} Hence, $f$ is one-to-one.

Example 2

Proof (Invalid):
Direct proof. \begin{align*} & \text{Suppose } g(n_1) = g(n_2). \\ & \implies n_1^2 = n_2^2 \quad & \text{(Defn. of } g\text{)} \\ & \implies n_1 = n_2 \quad & \text{(Taking square root)} \\ \end{align*} Hence, $g$ is one-to-one.

Incorrect! What's wrong?

Proof:
Counterexample.

• Let $n_1 = -1$ and $n_2 = 1$.
  $g(n_1) = (-1)^2 = 1$ and $g(n_2) = 1^2 = 1$
  $\implies g(n_1) = g(n_2)$ but $n_1 \ne n_2$
• Hence, $g$ is not one-to-one.

Onto functions

What is the difference between the two marriage functions?

Definition

Template

Proof
Direct proof.

• Suppose $y$ is any element of $Y$.
• Show there exists $x \in X$ with $F(x) = y$.

Proof:
Counterexample.

• Find $y \in Y$ such that $y \ne F(x)$ for any $x \in X$.

Example 1

Proof:
Direct proof. \begin{align*} & \text{Let } y \in \mathbb{R}. \text{ Set } x = \frac{y+1}{4}. \text{ Then:} \\ & f\!\left(\frac{y+1}{4}\right) = 4 \cdot \frac{y+1}{4} - 1 = y \quad & \text{(Defn. of } f\text{, then simplify)} \end{align*} Hence, $f$ is onto.

Example 2

Proof (Invalid):
Direct proof. \begin{align*} & \text{Let } m \in \mathbb{Z}. \text{ Set } n = \frac{m+1}{4}. \text{ Then:} \\ & g\!\left(\frac{m+1}{4}\right) = 4 \cdot \frac{m+1}{4} - 1 = m \quad & \text{(Defn. of } g\text{, then simplify)} \end{align*} Hence, $g$ is onto.

Incorrect! What's wrong?

Proof:
Counterexample.

• Suppose $g(n) = 0$ for some $n \in \mathbb{Z}$: \begin{align*} 4n - 1 = 0 \implies n = \frac{1}{4} \quad & \text{(Defn. of } g\text{, then simplify)} \end{align*} But $\frac{1}{4} \notin \mathbb{Z}$, so $g(n) \ne 0$ for any integer $n$.
• Hence, $g$ is not onto.

One-to-one correspondences

What is the difference between the three marriage functions?

Example 1

Subset of $\{a,b,c,d\}$		4-tuple of $\{0,1\}$
$\{\ \}$	$\to$	$(0,0,0,0)$
$\{a\}$	$\to$	$(1,0,0,0)$
$\{b\}$	$\to$	$(0,1,0,0)$
$\{c\}$	$\to$	$(0,0,1,0)$
$\{d\}$	$\to$	$(0,0,0,1)$
$\{a,b\}$	$\to$	$(1,1,0,0)$
$\{a,c\}$	$\to$	$(1,0,1,0)$
$\{a,d\}$	$\to$	$(1,0,0,1)$
$\{b,c\}$	$\to$	$(0,1,1,0)$
$\{b,d\}$	$\to$	$(0,1,0,1)$
$\{c,d\}$	$\to$	$(0,0,1,1)$
$\{a,b,c\}$	$\to$	$(1,1,1,0)$
$\{a,b,d\}$	$\to$	$(1,1,0,1)$
$\{a,c,d\}$	$\to$	$(1,0,1,1)$
$\{b,c,d\}$	$\to$	$(0,1,1,1)$
$\{a,b,c,d\}$	$\to$	$(1,1,1,1)$

Example 2

Proof:
To show $F$ is a one-to-one correspondence, we show:

1. $F$ is one-to-one.
   Suppose $F(x_1,y_1) = F(x_2,y_2)$. \begin{align*} & \implies (x_1{+}y_1,\; x_1{-}y_1) = (x_2{+}y_2,\; x_2{-}y_2) \quad & \text{(Defn. of } F\text{)} \\ & \implies x_1{+}y_1 = x_2{+}y_2 \text{ and } x_1{-}y_1 = x_2{-}y_2 \quad & \text{(Equality of ordered pairs)} \\ & \implies x_1 = x_2 \text{ and } y_1 = y_2 \quad & \text{(Solving the two equations)} \\ & \implies (x_1, y_1) = (x_2, y_2) \quad & \text{(Equality of ordered pairs)} \\ \end{align*} Hence, $F$ is one-to-one.
2. $F$ is onto.
   Let $(u,v) \in \mathbb{R}{\times}\mathbb{R}$. Set $r = \frac{u+v}{2}$ and $s = \frac{u-v}{2}$. Then: $$F(r,s) = \left(\frac{u+v}{2}+\frac{u-v}{2},\;\frac{u+v}{2}-\frac{u-v}{2}\right) = (u,v).$$ Hence, $F$ is onto.

Inverse functions

What is the difference between the two marriage functions?

Definition

Example 1

Subset of $\{a,b,c,d\}$		4-tuple of $\{0,1\}$
$\{\ \}$	$\leftarrow$	$(0,0,0,0)$
$\{a\}$	$\leftarrow$	$(1,0,0,0)$
$\{b\}$	$\leftarrow$	$(0,1,0,0)$
$\{c\}$	$\leftarrow$	$(0,0,1,0)$
$\{d\}$	$\leftarrow$	$(0,0,0,1)$
$\{a,b\}$	$\leftarrow$	$(1,1,0,0)$
$\{a,c\}$	$\leftarrow$	$(1,0,1,0)$
$\{a,d\}$	$\leftarrow$	$(1,0,0,1)$
$\{b,c\}$	$\leftarrow$	$(0,1,1,0)$
$\{b,d\}$	$\leftarrow$	$(0,1,0,1)$
$\{c,d\}$	$\leftarrow$	$(0,0,1,1)$
$\{a,b,c\}$	$\leftarrow$	$(1,1,1,0)$
$\{a,b,d\}$	$\leftarrow$	$(1,1,0,1)$
$\{a,c,d\}$	$\leftarrow$	$(1,0,1,1)$
$\{b,c,d\}$	$\leftarrow$	$(0,1,1,1)$
$\{a,b,c,d\}$	$\leftarrow$	$(1,1,1,1)$

Example 2

Proof:
For any $y \in \mathbb{R}$, find $x$ such that $f(x) = y$: \begin{align*} & 4x - 1 = y \quad & \text{(Defn. of } f\text{)} \\ & \implies x = \frac{y+1}{4} \quad & \text{(Simplify)} \\ \end{align*} Hence, $f^{-1}(y) = \dfrac{y+1}{4}$.

Example 3

Proof:

• $F^{-1}$ is one-to-one. Suppose $F^{-1}(y_1) = F^{-1}(y_2) = x$. Then $y_1 = F(x) = y_2$.
• $F^{-1}$ is onto. For any $x \in X$, let $y = F(x) \in Y$. Then $F^{-1}(y) = x$.

Composition of functions

Definition

Example 1

Solution:

• $g \circ f$: $(g \circ f)(n) = g(n+1) = (n+1)^2$.
• $f \circ g$: $(f \circ g)(n) = f(n^2) = n^2 + 1$.
• $g \circ f \ne f \circ g$: e.g., $(g \circ f)(1) = 4$ but $(f \circ g)(1) = 2$.

Example 2

Solution:

• Range of $g \circ f = \{ y, z \}$.

Example 3

Solution:
$f \circ I_X = f$.

• $(f \circ I_X)(a) = f(I_X(a)) = f(a) = u$
• $(f \circ I_X)(b) = f(I_X(b)) = f(b) = v$
• $(f \circ I_X)(c) = f(I_X(c)) = f(c) = v$
• $(f \circ I_X)(d) = f(I_X(d)) = f(d) = u$

$I_Y \circ f = f$.

• $(I_Y \circ f)(a) = I_Y(f(a)) = I_Y(u) = u$
• $(I_Y \circ f)(b) = I_Y(f(b)) = I_Y(v) = v$
• $(I_Y \circ f)(c) = I_Y(f(c)) = I_Y(v) = v$
• $(I_Y \circ f)(d) = I_Y(f(d)) = I_Y(u) = u$

Proof:

• $f \circ I_X = f$: $(f \circ I_X)(x) = f(I_X(x)) = f(x)$.
• $I_Y \circ f = f$: $(I_Y \circ f)(x) = I_Y(f(x)) = f(x)$.

Example 4

Solution:
$f^{-1} \circ f = I_X$:

• $(f^{-1} \circ f)(a) = f^{-1}(z) = a = I_X(a)$
• $(f^{-1} \circ f)(b) = f^{-1}(x) = b = I_X(b)$
• $(f^{-1} \circ f)(c) = f^{-1}(y) = c = I_X(c)$

$f \circ f^{-1} = I_Y$:

• $(f \circ f^{-1})(x) = f(b) = x = I_Y(x)$
• $(f \circ f^{-1})(y) = f(c) = y = I_Y(y)$
• $(f \circ f^{-1})(z) = f(a) = z = I_Y(z)$

Proof:

• $f^{-1} \circ f = I_X$. Let $x \in X$. Suppose $f^{-1}(f(x)) = x'$. \begin{align*} & \implies f(x') = f(x) \quad & \text{(Defn. of inverse)} \\ & \implies x' = x \quad & \text{(}f \text{ is one-to-one)} \\ \end{align*} Hence $(f^{-1} \circ f)(x) = x$, so $f^{-1} \circ f = I_X$.
• $f \circ f^{-1} = I_Y$. Let $y \in Y$. Suppose $f(f^{-1}(y)) = y'$. \begin{align*} & \implies f^{-1}(y') = f^{-1}(y) \quad & \text{(Defn. of inverse)} \\ & \implies y' = y \quad & \text{(}f^{-1} \text{ is one-to-one)} \\ \end{align*} Hence $(f \circ f^{-1})(y) = y$, so $f \circ f^{-1} = I_Y$.

Example 5

Proof:
Direct proof. \begin{align*} & \text{Suppose } (g \circ f)(x_1) = (g \circ f)(x_2). \\ & \implies g(f(x_1)) = g(f(x_2)) && \text{(Defn. of composition)} \\ & \implies f(x_1) = f(x_2) && \text{(}g \text{ is one-to-one)} \\ & \implies x_1 = x_2 && \text{(}f \text{ is one-to-one)} \\ \end{align*} Hence, $g \circ f$ is one-to-one.

Example 6

Proof (Core idea):

Proof:

Direct proof.

• Let $z \in Z$. Since $g$ is onto, $\exists\, y \in Y$ with $g(y) = z$. Since $f$ is onto, $\exists\, x \in X$ with $f(x) = y$. Then $(g \circ f)(x) = g(f(x)) = g(y) = z$.
• Hence, $g \circ f$ is onto.

Infinite sets

Comparing set sizes

Solution:

• Remove one apple and one mango simultaneously. Repeat until a bag is empty.
• If both bags are empty, they have the same number of fruits.
• If one bag is empty and the other is not, the bag which is not empty has more number of fruits.

Comparing set sizes using one-to-one correspondences

• Two finite sets are of the same size if there is a one-to-one correspondence between them.

• Two finite sets are not of the same size if there is no one-to-one correspondence between them.

• A finite set is one that is empty or can be put into one-to-one correspondence with $\{1, 2, \ldots, n\}$ for some positive integer $n$.

• An infinite set is a nonempty set that cannot be put into one-to-one correspondence with $\{1, 2, \ldots, n\}$ for any positive integer $n$.

Cardinality

$A$ and $B$ have the same cardinality if and only if $A$ has the same cardinality as $B$ or $B$ has the same cardinality as $A$.

Properties: For all sets $A$, $B$, $C$:

• Reflexive: $A$ has the same cardinality as $A$.
• Symmetric: If $A$ has the same cardinality as $B$, then $B$ has the same cardinality as $A$.
• Transitive: If $A$ has the same cardinality as $B$ and $B$ has the same cardinality as $C$, then $A$ has the same cardinality as $C$.

$|\mathbb{Z}| = |\mathbb{Z}^{\text{even}}|$

• There is no one-to-one correspondence between the two sets.
• So, $|\mathbb{Z}| \ne |\mathbb{Z}^{\text{even}}|$.
• Incorrect! What's wrong?

• Failing to find a correspondence doesn't mean one doesn't exist.
• There is a one-to-one correspondence: $f(n) = 2n$.
• So, $|\mathbb{Z}| = |\mathbb{Z}^{\text{even}}|$.

Proof

• Define $f: \mathbb{Z} \to \mathbb{Z}^{\text{even}}$ by $f(n) = 2n$.
• $f$ is one-to-one:
  $f(n_1) = f(n_2) \implies 2n_1 = 2n_2 \implies n_1 = n_2.$
• $f$ is onto: for any $m \in \mathbb{Z}^{\text{even}}$, write $m = 2k$ ($k \in \mathbb{Z}$); then $f(k) = m$.

Take-home lesson

Countable sets

$\mathbb{N}$		$A$
$1$	$\to$	“First” element of $A$
$2$	$\to$	“Second” element of $A$
$3$	$\to$	“Third” element of $A$
$4$	$\to$	“Fourth” element of $A$
$5$	$\to$	“Fifth” element of $A$
$\vdots$		$\vdots$

$\mathbb{Z}$ is countable

Solution

$\mathbb{N}$		$\mathbb{Z}$
$1$	$\to$	$0$
$2$	$\to$	$1$
$3$	$\to$	$-1$
$4$	$\to$	$2$
$5$	$\to$	$-2$
$\vdots$		$\vdots$
$n$	$\to$	$f(n)$
$\vdots$		$\vdots$

• Define $f: \mathbb{N} \to \mathbb{Z}$ by: $$f(n) = \left. \begin{cases} \dfrac{n}{2} & \text{if } n \text{ is even},\\[6pt] -\!\left\lfloor\dfrac{n}{2}\right\rfloor & \text{if } n \text{ is odd}. \end{cases} \right\}$$
• $f$ is a one-to-one correspondence, so $\mathbb{Z}$ is countable.

$Q^{+}$ is countable

$\mathbb{N}$		$\mathbb{Q}^{+}$
		$\vdots$
$1$	$\to$	$\dfrac{1}{1}$
		$\vdots$
$2$	$\to$	$\dfrac{2}{1}$
		$\vdots$
$3$	$\to$	$\dfrac{3}{1}$
$\vdots$		$\vdots$

• This mapping misses most rationals — not a valid one-to-one correspondence.
• Incorrect! What's wrong?
• Failing to find a one-to-one correspondence does not mean one doesn't exist.

Solution

$\mathbb{N}$		$\mathbb{Q}^{+}$
$1$	$\to$	$1/1$
$2$	$\to$	$1/2$
$3$	$\to$	$2/1$
$4$	$\to$	$3/1$
$5$	$\to$	$1/3$
$6$	$\to$	$1/4$
$7$	$\to$	$2/3$
$8$	$\to$	$3/2$
$9$	$\to$	$4/1$
$10$	$\to$	$5/1$
$\vdots$		$\vdots$

• We exhibit a one-to-one correspondence $f: \mathbb{N} \to \mathbb{Q}^{+}$.
• $f$ is onto: every positive rational appears in the grid and every grid point is eventually reached.
• $f$ is one-to-one: skip already-counted rationals so no rational is counted twice.

$[0, 1]$ is uncountable

Solution

• We prove there is no one-to-one correspondence between $\mathbb{N}$ and $[0,1]$.
• We use proof by contradiction.
• Suppose $[0,1]$ is countable. List all elements:

  $\mathbb{N}$		$[0,1]$
  $1$	$\to$	$0.a_{11}\,a_{12}\,a_{13}\cdots$
  $2$	$\to$	$0.a_{21}\,a_{22}\,a_{23}\cdots$
  $3$	$\to$	$0.a_{31}\,a_{32}\,a_{33}\cdots$
  $\vdots$	$\vdots$	$\vdots$
  $n$	$\to$	$0.a_{n1}\,a_{n2}\,a_{n3}\cdots$
  $\vdots$	$\vdots$	$\vdots$

• We construct a real $d \in [0,1]$ not on this list.
• Suppose the list begins (diagonal entries boxed):

  

• Construct $d = 0.d_1 d_2 d_3\cdots$ where \begin{align*} d_n = \left. \begin{cases} 1 & \text{if } a_{nn} \ne 1,\\ 2 & \text{if } a_{nn} = 1. \end{cases} \right\} \end{align*} So we get $$d = 0.12112\ldots$$
• Observation: For each natural number $n$, the constructed real number $d$ differs in the $n$th decimal position from the $n$th number on the list.
• Therefore $d \notin$ the list, but $d \in [0,1]$ — contradiction!
• Hence $[0,1]$ is uncountable.

Take-home lesson

More theorems

$\mathbb{R}$ and $[0, 1]$ have the same size

Solution

• Let $S = \{ x \in \mathbb{R} \mid 0 < x < 1 \}$. Bend $S$ into a circle and project each point to $\mathbb{R}$, defining $F: S \to \mathbb{R}$.

We show $F$ is a one-to-one correspondence:

• $F$ is one-to-one: distinct points on the circle project to distinct points on the line.
• $F$ is onto: for any $y \in \mathbb{R}$, the line through $y$ and the circle's topmost point meets the circle at some $x$ with $F(x) = y$.

Set of bit strings is countable

Solution

• Define $f: \mathbb{N} \to \mathbb{B}$ by: $$f(n) = \left. \begin{cases} \epsilon & \text{if } n = 1, \\ \text{$k$-bit binary repr. of } n - 2^k & \text{if } n > 1,\; \lfloor \log n \rfloor = k. \end{cases} \right\}$$

  $\mathbb{N}$		$\mathbb{B}$
  $1$	$\to$	$\epsilon$
  $2$	$\to$	$0$
  $3$	$\to$	$1$
  $4$	$\to$	$00$
  $5$	$\to$	$01$
  $6$	$\to$	$10$
  $7$	$\to$	$11$
  $\vdots$		$\vdots$
  $n$	$\to$	$f(n)$
  $\vdots$		$\vdots$

• $f$ is a one-to-one correspondence, so $\mathbb{B}$ is countably infinite.
• More generally, the set of strings over any finite alphabet is countably infinite.

Set of computer programs is countable

Solution

• Each program is a finite string over a finite alphabet.
• [Encoding] Translate each program to a binary string via ASCII.
• Sort by length, then lexicographically within each length.
• Define $f: \mathbb{N} \to \mathbb{P}$ by $f(n) = n$-th program in this ordering.
• Programs encoding to bit strings of length $\le 5$:

  $\mathbb{N}$		$\mathbb{P}$
  $1$	$\to$	$01$
  $2$	$\to$	$11$
  $3$	$\to$	$0010$
  $4$	$\to$	$1010$
  $5$	$\to$	$1011$
  $6$	$\to$	$00010$
  $7$	$\to$	$00100$
  $8$	$\to$	$10111$
  $\vdots$		$\vdots$
  $n$	$\to$	$f(n)$
  $\vdots$		$\vdots$

• $f$ is a one-to-one correspondence, so $\mathbb{P}$ is countably infinite.

Set of all functions $\mathbb{N} \to \{0, 1\}$ is uncountable

Solution

• Let $\mathbb{S}$ = reals in $[0,1]$ of the form $0.a_1 a_2 a_3\cdots$ with $a_i \in \{0,1\}$ (omit sequences ending in all 1's for uniqueness).
• Map each $0.a_1 a_2 a_3\cdots \in \mathbb{S}$ to the function $g \in \mathbb{L}$ with $g(n) = a_n$. This gives a one-to-one correspondence between $\mathbb{S}$ and a subset of $\mathbb{L}$.

  $\mathbb{S}$		Subset of $\mathbb{L}$
  $0.a_1 a_2 a_3 \cdots a_n \cdots$	$\to$	$\mathbb{N}$ $\{0,1\}$ $1$ $\to$ $a_1$ $2$ $\to$ $a_2$ $3$ $\to$ $a_3$ $\vdots$ $\vdots$ $n$ $\to$ $a_n$ $\vdots$ $\vdots$

• Since $\mathbb{S} \subseteq [0,1]$ is uncountable, $\mathbb{L}$ is uncountable.

Take-home lesson