# Discrete Mathematics Lecture 3 — Functions

University course in discrete mathematics for computer science and engineering.

Sep 4, 2021
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)$$

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

img1

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*}

img2

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)$$

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)$$

# Functions

Notation:

$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$

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.

(img)

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).