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 \{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.
Group exercises
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.
Topic 1: Lexicographic order
Let $A$ be a set with a (partial or total) order relation $\leq$ on its elements. A lexicographic order
R of $k$-tuples of elements of $A$ is defined as follows. If $(a_1, \dots, a_k)$ and $(b_1, \dots, b_k)$ are $k$-tuples of elements of $A$, then $R(a_1 \dots a_k, b_1 \dots b_k)$ holds if either for every $i$, $a_i=b_i$, or at the smallest $i$ such that $a_i \neq b_i$, $a_i < b_i$. If $A = \{0,1\}$, with order $0 \leq 1$, and $k=2$, then $00$ is the smallest element in the lexicographic order of pairs of elements of $A$, followed by $01$, followed by $10$, with $11$ being the largest. ( A dictionary order is an example of a lexicographic order if we consider all words to be padded by blanks, with a blank being the smallest letter in the alphabet -- in general, lexicographic order is defined over strings with an alphabet $A$, rather than just $k$-tuples of elements of $A$. )
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.
Topic 2: Transitive closure
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.
Topic 3: Hasse diagrams
Let $R$ be partial order on $A$. A graph of $R$ would contain a loop on every vertex (because $R$ is reflexive), and potentially a lot of edges because of transitivity. For example, let $A=\mathcal{P}(\{1,2,3\})$, and consider a partial order relation $R=\{(B,C) \in A \times A \mid B \subseteq C\}$. Then the graph of $R$ would have edges $(\emptyset,\{1\})$, $(\emptyset, \{1,2\})$, $(\emptyset,\{1,2,3\})$, $(\{1\}, \{1,2\})$, $(\{1\},\{1,2,3\})$ and so on, making a messy picture.
A Hasse diagram is a way to draw a cleaner graph corresponding to the same partial order, by eliminating all edges implied by other edges using reflexivity and transitivity. That is, in a Hasse diagram, we do not draw loops, and only draw an edge $(a,b)$ if there are no edges $(a,c)$ and $(c,b)$ already in the diagram. Also, we draw smaller elements below larger elements, and skip arrows. For example, a Hasse diagram of the subset relation on $A=\mathcal{P}(\{1,2,3\})$ is as follows.
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 $\}$.
Review after the group activity
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) $\}$