Discrete Mathematics Lecture 3 — Functions

University course in discrete mathematics for computer science and engineering.

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

Continuation of Predicates

This will show how to use predicates with quantifier symbols with logic and set theory combined together

Ex: Let \(u=\mathbb{N}=\{0, 1, 2 ... \}\) and let \(P(x, y, z)\) be our predicate

\[ P(x, y, z) : x^2 + y^2 \leq z^2 \]

And let us try to evaluate the truth of the below.

  1. \(\forall x \forall y \exists z P(x, y, z)\)
  2. \(\forall x \forall z \exists y P(x, y, z)\)
  3. \(\exists x \exists y \forall z P(x, y, z)\)
  4. \(\exists x \exists z \forall y P(x, y, z)\)

Lets start with the first predicate.

  1. \(\forall x \forall y \exists z P(x, y, z)\)

Is this true or false?

It is true regardless of what you pick as \(x\), \(y\), you can always find an integer \(z\) so that \(z^2 \geq x^2 + y^2\).

  1. \(\forall x \forall z \exists y P(x, y, z)\)

It is false if \(x > z\) then there no \(y\) so that \(x^2 + y^2 <= z^2\).

  1. \(\exists x \exists y \forall z P(x, y, z)\)

It is true, you can pick \(x = 0\) and \(y = 0\) then it will be true for all \(z\) in \(\mathbb{N}\), you have to be careful here because we are counting with that \(\mathbb{N}\) begins with \(0\).

  1. \(\exists x \exists z \forall y P(x, y, z)\)

It is false because regardless of what you pick for \(x\) and \(z\) will crumble for large enough \(y\).

To write text statements to contain quantfiers instead

Ex.1: write the following argument symbolically and decide if the argument is valid or not

hypothesis one: everyone drinks that drinks alchohol gets liver problems hypothesis two: the members in the nykterhetsrörelsen do not drink alchohol and none of them get liver problem

our universe here is the set of all people. \(u = \text{all people}\)

there are actually three underlying predicates

we write down 3 predicates

\[ D(x) : x \text{ drinks alchohol} \]

\[ L(x) : x \text{ gets liver problems} \]

\[ N(x) : x \text{ is a member of the movement} \]

The first hypothesis can be written as

\[ \forall x D(x) \Rightarrow L(x) \]

can also be written

\[ \forall x : \neg D(x) \lor L(x) \]

The second hypothesis can be written as

\[ \forall x : N(x) \Rightarrow \neg D(x) \]

\[ \forall x : N(x) \Rightarrow \neg L(x) \]

can also be written

\[ \neg \exists x : N(x) \land L(x) \]

is the argument valid or not, again this is not asking wether or not it is true or not, this you have to find out through a scientific study. Regardless the argument is invalid because of the following case


this image shows the case where the conclusion

\[ \forall x N(x) \Rightarrow \neg L(x) \]

is false, therefore the argument is not valid.

Ex.2: Vissa hackers also have normal jobs. Some computer science students work in paralell with their studies. conclusion some computer science students are hackers.

writing this with quantifiers ect.

\[ u = \text{all people} \]

\[ D(x) : x \text{ is a CSE student} \] \[ H(x) : x \text{ is a hacker} \] \[ J(x) : x \text{ has a normal job} \]

\[ \begin{align*} & \exists x : H(x) \land J(x) \\ & \exists x : D(x) \land J(x) \\ \hline & \exists x : D(x) \land H(x) \end{align*} \]


therefore the argument is invalid

Interval notation

Intervall notation for intervals of real numbers

  • \([a, b]\), \(\{x \in R \mid a \leq x \leq b \}\) img 1
  • \((a, b)\), \(\{x \in R \mid a < x < b \}\) img 2
  • \([a, b)\) img 3
  • \((a, b)\) img 4
  • \([a, \infty)\) img 5
  • \(\{ x \in R \mid x \geq a \}\)
  • \((a, \infty)\) img 6
  • \((-\infty, a]\), \(\{x \in R \mid x \leq a \}\)
  • \((-\infty, a)\)

… add more later

Ex: \(A = (2, 4]\), \(B = [3, inf)\)

write the following sets with intervall notation

  • \(A u B = (2, inf)\)
  • \(A \cap B = [3, 4]\)
  • \(A \setminus B = (2, 3)\)



\[ f : X \rightarrow Y \]

\(X\) is called the functions domain and \(Y\) is called the codomain.

from highschool you are most used to functions that

\[ f : \mathbb{R} \rightarrow \mathbb{R} \]

but in higher maths and especially in discrete mathematics you are interested in functions that go between sets other than \(R\).

Ex.1: \(X = \text{the set of everyone in this course}\).

\[ Y = [0, 65] \cap \frac{\mathbb{N}}{10} \]

what is meant with \(\frac{\mathbb{N}}{10}\) is

\[ \frac{\mathbb{N}}{10} = \left\{\frac{\mathbb{N}}{10} \mid n \in \mathbb{N}\right\} \]

so a function could be

\[ f(x) = \text{ how many marks x you can get on the test} \]

So this means that the points have an intervall of \(0.1\) between them, meaning that the points are not integers but numbers with a difference of \(0.1\) between them.

Ex.2: Let \(u\) be a universe and \(P(x)\) a predicate on \(u\). Then you can connect a function to these. You usually also call this function \(P\) but you have to be careful because predicates are also \(P\).

\[ P : u \rightarrow {0, 1} \] \[ P(x) = \begin{cases} 0, & \text{ if the predicate } P(x) \text{ is false} \\ 1, & \text{ if the predicate } P(x) \text{ is true} \\ \end{cases} \]

\(P\) is a so called Boolean function. A Boolean function is a function for which its co-domain is the set \(\{0, 1\}\).

Note: Let \(f X \rightarrow Y\) be a function. The value set (change) to \(f\) is the set of all the possible output values. If we were to write this formally

\[ f(X) = \{y \in Y \mid \exists x \in X \text{ where } y(x) = y \} \]

\[ f(X) \subseteq Y \]

More About Functions

Let \(f : X \rightarrow Y\) be a function

  • \(f\) is said to be injective if \(\forall x_1, x_2 \in X : f(x_1) = f(x_2) \Rightarrow (x_1=x_2)\)
    • contra positive \(x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)\)
  • \(f\) is said to be surjective if \(f(X) = Y, \forall Y \in Y : \exists x \in X \text{ so that } f(x) = y\).
  • \(f\) is said to be bijective it is injective and surjective.

Ex: \(f : X \rightarrow \mathbb{R}\)

\[ f(x) = \frac{1}{|x|} \]

what is the correct domain \(X\)?

\[ X = \mathbb{R} \setminus \{0\} \]

is \(f\) injective? It is not injective because \(f(-x) = f(x), \forall x \neq 0\).

\(f\) would be injective if you limited the domain to \((0, \infty)\) or \((-\infty, 0)\).

is \(f\) surjective? It is not surjective, \(f(R \setminus \{0\}) = (0, \infty)\).

you can make it surjective by limiting its codomain as

\[ f : (0, \infty) \rightarrow (0, \infty) \]

Let \(f : X \rightarrow Y\) be a injective function.

The inverse to the function \(f\), is written as \(f^{-1}\), this means the inverse function NOT \(\frac{1}{f}\) which is the function from \(f(X)\) to \(X\) which is given by \(f^{-1}(y) = x\) when \(f(x) = y\).

this only works when you have a injective function because you will have two functions which go to the same y value.


Ex: \(f : (0, \infty) \rightarrow (0, \infty)\)

\[ f(x) = \frac{1}{x} \]

\[ f^{-1}(y) = \frac{1}{y} \]

this is a special case where

\[ f=f^{-1} \]

Function Compositing

\[ f : X \rightarrow Y \] \[ g : Y \rightarrow Z \]

\(f\)s codomain is \(g\)s domain

this is so called composite function

this can also be written as

\[ g \circ f \]

which is read like “\(g\) after \(f\)”.

\[ g \circ f : X \rightarrow Z \]

\[ (g \circ f)(x) = g(f(x)) \]

the composition of function is not commutative, meaning that the order of how you compose them together matters.

Important Note: If \(X=Y=Z\) then \(g \circ f\) and \(f \circ g\) makes sense.

but in most cases \(g \circ f \neq f \circ g\) (composition of functions is not commutative).