Functions and relations

- Lectures 17-19.

- Relation, binary, ternary, k-ary. Graph of a binary relation.
- Function, domain, codomain, range, preimage
- Function types: total, one-to-one, onto, bijection.
- Function composition and inverse
- Alphabet, language, $\{0,1\}^*$
- Binary relation properties: reflexive/anti-reflexive, symmetric/anti-symmetric, transitive
- Order (total and partial), equivalence

Solve each of the following exercises.

- For each of the following functions, identify domain, codomain and range. State whether the function is total, one-to-one, onto, bijection.
- $f\colon \mathbb{R} \to \mathbb{R}$, $f(x)=\lceil 2x \rceil$, where $\lceil z \rceil$ is the ceiling of $z$, that is, the smallest integer greater than or equal to $z$.
- Let universe $U=\{a,b,c,\dots,z\}$, and let $A\subseteq U$ be a set. Then $f_A\colon U \to \{0,1\}$ is defined as $f_A(x) =1$ if $x \in A$, and $f_A(x)=0$ if $x \notin A$ (this $f_A$ is called the
*characteristic function*of $A$). For this question, let $A$ be all vowels in $U$. How would your answer change if $A = \emptyset$? - $f \colon \{0,1\}^* \to \mathbb{N}$, where $f(x)=k$ if the length of string $x$ is $k$.

- Give two examples of functions, $f\colon \{1,2,3\} \to \{a,b,c\}$ and $g\colon \mathbb{Z} \to \mathbb{Z}$ such that $f$ and $g$ are both
- bijections
- one-to-one, but not onto (not necessarily total)
- neither one-to-one, nor onto

- For each of the following pairs, describe $f^{-1}$, $g^{-1}$, $f \circ g$ and $g \circ f$.
- $f \colon \mathbb{R} \to \mathbb{R}$, $f(x) = 2x$, and $g \colon \mathbb{R} \to \mathbb{R}$, $g(x)=x+10$.
- $f \colon \{0,1\}^* \to \{0,1\}^*$, $f(x)$ is reverse of $x$ (for example, $f(00111)=11100$; if $x=x_1 \dots x_k$ where $x_1,\dots, x_k \in \{0,1\}$, then $f(x)=x_k x_{k-1} \dots x_2 x_1$), and $g \colon \{0,1\}^*\to \{0,1\}^*$ is a circular shift to the right: that is, if $x=x_1\dots x_k$, then $g(x) = x_k x_1 x_2 \dots x_{k-1}$ (for example, $g(00111)=10011$). Hint: you can describe your answers by saying what happens on $x=x_1\dots x_k$.

For this part of the lab, you will be working in groups of three. In the first part of the exercise, you will create examples of relations and draw some of them on paper. Then, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

- $R = \{(x,y) \in A \times A \mid x \leq y \}$
- $R = \{ (x,y) \in A \times A \mid |x-y|=1 \}$
- $R = \{ (x,y) \in A \times A \mid x \equiv y \mod 2 \}$

- $R_1$: an example of an equivalence which is not equality (that is, there are pairs $(x,y) \in R_1$ where $x \neq y$).
- $R_2$: an example of a non-transitive, not reflexive and not anti-reflexive relation.
- $R_3$: an example of a partial order that is not a total order (draw the actual relation; you will then give this to your friend to draw Hasse diagram for it).

- $A_1= \{0,1,2,3,4,5,6,7,8,9\}$, $R = \{ (x,y) \mid where |x-y| $ is even $\}$. Here, $|x-y|=x-y$ when $x \geq y$, and $|x-y|=y-x$ when $x < y$.
- Each of the two relations $R_1$ drawn by your friends.
- $A_2 = A_1^*$ (that is, all strings made from $\{0,1,\dots, 9\}$). $R=\{(x,y) \mid$ x and y start with the same letter $\}$. Hint: $A_2$ also contains an empty string.

A * transitive closure * of a binary relation $R$ is the smallest transitive relation $R^+$ such that $R \subseteq R^+$. For example, $x < y$ (but not $x \leq y$) is a transitive closure of the relation $\{(x,y)| x+1=y\}$. A transitive closure of any $R$ can be computed by repeatedly adding pairs $(x,z)$ whenever $(x,y)$ and $(y,z)$ were either in $R$ or added earlier. A transitive closure of a transitive relation $R$ is $R$ itself. When relations are viewed as graphs, then there is an edge $(x,y)$ in $R^+$ if there is a way to get from $x$ to $y$ in the graph of $R$ by following a sequence of edges.

- Let $A = \{a,b,c\}$, and $R=\{(b,a), (a,b), (b,c)\}$. Draw a graph of $R$ and a graph of $R^+$, and list all pairs in $R^+$.
- Compute transitive closures of two relations $R_2$ drawn by your friends.
- Let $COLOURS=\{$white, beige, lightgray, gray, yellow, darkgray, black $\}$. Relation $SIMILAR(x,y)$ holds for a pair of similar (or the same) colours. So for any $x$, $(x,x) \in SIMILAR$. Additionally, the following pairs are similar: (white,lightgray), (lightgray, gray),(beige, yellow), (gray, darkgray), (darkgray, black), and their symmetric counterparts (lightgray,white), (gray, lightgray), etc. Draw the graph of SIMILAR and a graph of its transitive closure (make sure to include $(x,x)$ edges).

- Let $A=\{1,2,3,4\}$ with a total order relation $\leq$. Draw both the graph of $\leq$ on $A$ and its Hasse diagram.
- Draw Hasse diagrams of two relations $R_3$ drawn by your friends.
- Let $B = \{2,3,4,6,8,9,12\}$. Draw a Hasse diagram of the partial order relation $\{(x,y) \mid $ x divides y $\}$.

Let $A = \{abc, a, bc, ac, ab, bac \} $ (that is, $A \subset \{a,b,c\}^*)$.

- Let $R_1= \{ (ac,bc), (bc,ac), (bc, ab), (ab,bc), (ab, ac), (ac, ab), (abc,bac), (bac,abc), (abc,abc), (a,a), (bc,bc), (ac,ac), (ab,ab), (bac,bac) \} $. Draw a graph of $R_1$. In how many classes equivalence classes does $R_1$ partition $A$? List elements of each equivalence class. How would you describe this equivalence relation on $A$?
- Let $R_2 = \{$(a,ab), (a,ac),(ab,abc), (bc,abc), (abc,a), (ac, bac)$\}$. Draw a graph of $R_2$ and a graph of its transitive closure $R_2^+$. For each of $R_2$ and $R_2^+$, say if it is reflexive/anti-reflexive/neither, symmetric/anti-symmetric/neither, transitive/not transitive.
- Draw a Hasse diagram of $R_3=\{(x,y) \mid $ x=y or x is a substring of y $\}$. That is, R_3= $\{(x,x) | x \in A \} \cup \{$ (a,ab), (a,ac), (a, abc), (ab,abc), (bc,abc), (a, bac), (ac, bac) $\}$