Discrete Mathematics Lecture 4 — Functions Continuation

University course in discrete mathematics for computer science and engineering.

Sep 12, 2021
Downloads ‐ HTML, Markdown, PDF
All Files ‐ Post Files

Function Compositing

Composition of functions is not commutative.

Ex.1: \(f, g : \mathbb{R} \rightarrow \mathbb{R}\)

\[ f(x) = 2x \] \[ g(x) = 3x \]

\[ (g \circ f)(x) = (f \circ g)(x) = f(g(x)) = f(3x) = 2(3x) = 6x \]

\[ (f \circ g)(x) = (g \circ f)(x) = x + (c_1 + c2) \begin{cases} & f(x) = x + c_1 \\ & g(x) = x + c_2 \\ \end{cases} \]

Basically if you multiply with a constant then order does not matter, same with if you just add a constant, then order does not matter. But


\[ f(x) = 2x \] \[ g(x) = x + 1 \]

\[ (f \circ g)(x) = f(g(x)) = 2(x + 1) = 2x + 2 \] \[ (g \circ f)(x) = g(fx)) = g(2x) = 2x + 1 \]

which are not the same thing, so as soon as you stray away from the first examples you see that the order does indeed matter.

You do not need that complicated functions for the order to matter.

Function Attributes

Proposition: Let A, B be finite sets and f : A -> B be a function. Then

  1. If \(|A| > |B|\), then the function \(f\) can not be injective (Pigeonhole principe).
    • Pigeonhole principe meaning that since \(A\) is larger than \(B\), then at least two \(A\)s must go to the same value in \(B\).
  2. If \(|A| < |B|\), then the function \(f\) can not be surjective.
  3. If \(|A| = |B|\), then the function is injective \(\Leftrightarrow\), \(f\) is surjective \(\Leftrightarrow\) \(f\) is bijective

Ex: Standard pigeonhole principe example. Lets say that you have \(5\) points in \(\mathbb{R}^2\) with integer coordinates, that is to said \(5\) points in \(\mathbb{Z}^2\).

You can say that all these points exist within the integer lattice.

img 1 (image of lattice with points)

Prove that there exists a pair so that their midpoint also has integer coordinates.

img 2 (image of lattice with points with some example of midpoints in the lattice and not in the lattice).

Solution: First, prove that the midpoint between \((x_1, y_1)\) and \((x_2, y_2)\) have the coordinate

\[ \left(\frac{x_1+x_2}{2}, \frac{y_1+y_2}{2}\right) \]

If \(a\) and \(b\) are integer, then \(\frac{a+b}{2}\) is also an integer if and only if \(a\) and \(b\) have the same parity. That is to say, both are even or that both are odd.

Then \(x_1\), \(x_2\) must have the same parity, and \(y_1\) and \(y_2\) must have a parity for the coordinate to have an integer value.

Let \(A\) be the set of the \(5\) given points.

Let \(B = {(u, u), (u, j), (j, u), (j, j)}\)

Let \(f : A \rightarrow B\) given by

\[ f((x, y)) = \begin{cases} (u, u), & \text{ if both } x \text{ and } y \text{ are odd}. \\ (u, j), & \text{ if } x \text{ is odd and } y \text{ is even}. \\ (j, u), & \text{ if } x \text{ is even and } y \text{ is odd}. \\ (j, j), & \text{ if both } x \text{ and } y \text{ are even}. \\ \end{cases} \]

The only thing that determines if the coordinate is an integer or not, is its parity.

Because \(|A| = 5 > 4 = |B|\) then \(f\) is not injective. Then there is \((x_1, y_1) \neq (x_2, y_2)\) so that

\[ f((x, y)) = f((x_2, y_2)) \]

Then their midpoint

\[ \left(\frac{x_1+x_2}{2}, \frac{y_1+y_2}{2}\right) \]

will have integer coordinates.

(end of proof).

The last proposition only dealed with finite sets, what can we do with infinite sets? Can you say that one infinite set is larger than another?

What you need is a term called cardinality.

Def: Let \(A\), \(B\) be two sets. \(A\) and \(B\) is said to have the same cardinality if there exists a bijection \(f : A \rightarrow B\).

What this means is that there is a correspondence between each element in these two sets.

Note: \(f^{-1}\) is a bijection from \(B\) till \(A\). In other terms, the order does not matter, they still have the same cardinality.

A set \(X\) is said to be countably infinite if it has the same cardinality as \(\mathbb{Z}_+ = N \setminus {0} = \{1, 2, 3, ...\}\).

If \(X\) is infinite and no such bijection exists (cannot be countably infinite), then X is said to be uncountable.


  1. \(\mathbb{N}\) is countable

Proof: We must provide a bijection \(f : \mathbb{Z}_+ \rightarrow N\).

The “easiest” example \(f(x) = x - 1\).

1 2 3 4 ...
0 1 2 3 ...
  1. \(\mathbb{Z}\) is countable.

En bijection \(f : \mathbb{Z}_+ \rightarrow \mathbb{Z}\) can be described as, \(0, 1, -1, 2, -2, 3, -3\).


\[ f(1) = 0 \] \[ f(2n) = n \forall n \in \mathbb{Z}_+ \] \[ f(2n + 1) = -n \forall n \in \mathbb{Z}_+ \]

  1. \(\mathbb{Q}\) is countable.


Note first that there exists an injection

\[ f : \mathbb{Q} \rightarrow \mathbb{Z} \times \mathbb{Z} \]

same as

\[ f : \frac{a}{b} \rightarrow (a, b) \]

this is not a surjection because of the value \(0\) and that

\[ \frac{2}{3} \rightarrow (2, 3) \]

\[ \frac{4}{6} \rightarrow (2, 3) \]

because they are the same

But you regard \(\mathbb{Q}\) as a infinite subset of \(\mathbb{Z} \times \mathbb{Z}\).

Also, we already know that Z is countable. So there exists a bijection between

\[ \mathbb{Z} \times \mathbb{Z} \text{ to } \mathbb{Z}_+ \times \mathbb{Z}_+ \]

Therfore you have a component wise bijection between these two.

So we can now instead prove tha \(\mathbb{Z}_+ \times \mathbb{Z}_+\) is countable by describing a bijection from \(\mathbb{Z}_+ \text{ to } \mathbb{Z}_+ \times \mathbb{Z}_+\).

(1, 1) (1, 2) (1, 3) (1, 4), ...
(2, 1) (2, 2) (2, 3) (2, 4), ...
(3, 1) (3, 2) (3, 3) (3, 4), ...
(4, 1) (4, 2) (4, 3) (4, 4), ...
.      .      .      .
.      .      .      .
.      .      .      .

(The cartesian product)

img 3 (zigzag of the cartesian product)

The point is that with this is that you now see the bijection between \(\mathbb{Z}_+ to \mathbb{Z}_+ \times \mathbb{Z}_+\) then do a bijection to \(\mathbb{Z} \times \mathbb{Z}\) which is a subset of \(\mathbb{Q}\).

(add big part here with img explaining number set density ect).

Cantors Clause: R is uncountable.

Proof: The argument is called Cantors diagonalization.

Assume that there exists a bijection

\[ f : \mathbb{Z}_+ \rightarrow \mathbb{R} \]

which means that you can make a infinite list of all real numbers. That is to say all possible decimal series.

r1 2.314689 ...
r2 3.129683 ...
t3 0.12 ooo ...
r4 16.3181733333333333

What you can here is draw a diagonal line in the list


We can now find a number which cannot be described within this list.

which constructs a new number, which is fundamentally different in construction from the other numbers in the list.

Cantors clause describes the intution that the real numbers have higher cardinality compared to the natural numbers.

See more: Halting Problem. Gödels ofullständighets clause.

Binary Operations

Def: Let \(A\) be a set. A binary operation on \(A\) is a function from \(A \times A\) to \(A\).

Notation: \(f : A \times A \rightarrow A\).

you can write that your input is

\[ (a_1, a_2) \mapsto f((a_1, a_2)) \]

Normal ways to write this \((a_1, a_2) \mapsto a_1 * a_2\), “\(a_1\) times \(a_2\)”.

4 Different Terms

  1. A binary operation * on a set A is said to be commutative if

\[ \forall a_1, a_2 \in A : a_1 * a_2 = a_2 * a_1 \]

  1. * is said to be associative if

\[ \forall a_1, a_2, a_3 \in A : (a_1 * a_2) * a_3 = a_1 * (a_2 * a_3) \]

  1. Let * be a binary operation on \(A\). An element \(e\) in \(A\) is said to be an identity element for * if

\[ \forall a \in A : a * e = e * a = a \]

  1. Let * be a binary operation on a set A that has an identity element e. Let now a in A. An element b in A is said to be an inverse to a if

\[ a * b = b * a = e \]

Ex.1: \(A = \mathbb{Z}_+\)

There are two natural examples on binary operations. \(+\) and \(\times\).

\[ \mathbb{Z}_+ \times \mathbb{Z}_+ \rightarrow \mathbb{Z}_+ \]

\[ \begin{align} (a, b) & \mapsto a + b \\ & \mapsto a \times b \end{align} \]

\(+\) \(\times\)
Commutative true true
Associative true true
Identity false true (1)
Inverse false (has no ident) true (just 1)

Ex.1+: \(A = \mathbb{Z}\)

Now you have an identity for addition, \(0\). And every \(a\) in \(A\) has a additive inverse, that is \(-a\).

Terminology: \((\mathbb{Z}, +)\) is a commutative / abelsk group.

The word group meaning that you have a associate binary operation with an identity and every element has an identity.

This is the easiest example of a group.