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 each of the following binary relations on $A =\{0,1,2,3\}$, draw a graph of the relation and state if it is reflexive, anti-reflexive, neither, symmetric, anti-symmetric, neither, transitive, order (total or partial) or equivalence.
- $R = \{(x,y) \in A \times A \mid x \leq y \}$
- $R = \{(x,y) \in A \times A \mid x+1 \mod 4 < y \}$
- $R = \{(x,y) \in A \times A \mid x+y \mod 4 \text{ is even }\}$
- $R = \{ (x,y) \in A \times A \mid |x-y|=1 \}$

- Give an example of a binary relation on $\mathbb{Z}$ having the following properties
- $R$ is reflexive, anti-symmetric and transitive, and not an equivalence.
- $R$ is anti-reflexive, anti-symmetric and not transitive.
- $R$ is symmetric and neither reflexive nor anti-reflexive.
- $R$ is an equivalence which is not equality (that is, there are pairs $(x,y) \in R$ where $x \neq y$).

- For each of the two following equivalence relations, describe the partition of the original set $A$ into equivalence classes according to that relation.
- $A_1= \{0,1,2,3,4,5,6,7,8,9\}$, $R = \{ (x,y) \mid |x-y| $ is even $\}$.
- $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.

For this part of the lab, you will be working in groups of three. In the first part of the exercise, 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.

- Let $A =\mathbb{R}$, and let triples $(x,y,z)$ of elements of $\mathbb{R}$ denote coordinates in 3-dimensional space. List the following in lexicographic order, from smallest to largest: (0,0,0), (1,-1,2), (-10,0,10), (0,-1,1), (1,-1,0),(-5,-10,-20).
- Let $A=\{+,*,$ ^$\}$, with $ + \leq * \leq$ ^. List all pairs of elements of $A$ in lexicographic order.

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^+$.
- 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, beige), (white,lightgray), (lightgray, gray),(beige, yellow), (gray, darkgray), (darkgray, black), and their symmetric counterparts (beige,white), (lightgray, white), etc. Draw the graph of SIMILAR and a graph of its transitive closure (make sure to include $(x,x)$ edges). Hint: since SIMILAR is a symmetric relation, you can draw a single undirected edge rather than two arrows for each pair of elements.

- Let $A=\{1,2,3,4\}$ with a total order relation $\leq$. Draw both the graph of $\leq$ on $A$ and its Hasse diagram.
- 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 \} $

- List elements of $A$ in lexicographic order (considering $a < b < c$), where when comparing a shorter string to a longer the shorter string is viewed as padded by blanks, with the blank smaller than any letter.
- Let $R = \{$(a,ab), (a,ac),(ab,abc), (bc,abc), (abc,a)$\}$. Draw a graph of $R$ and a graph of its transitive closure, and list all elements of the transitive closure.
- Draw a Hasse diagram of $R=\{(x,y) \mid $ x=y or x is a substring of y $\}$. That is, R= $\{(x,x) | x \in A \} \cup \{$ (a,ab), (a,ac), (a, abc), (ab,abc), (bc,abc) $\}$