11.1 Quick review and some even Exercises

I will use $\mathbb{Z}_n$ as shorthand for the set $\{0,1,2,\ldots,n-1\}$, the first $n$ non-negative integers.

A binary relation (or simply relation) is a set of ordered pairs.

$\{(1,2), (1,3), (2,3)\}$

If the set is a subset of $A \times A$ then we may say the relation is "on $A$".

If the set is a subset of $A \times B$ then we may say the relation is "from $A$ to $B$".

Ex: $R = \{(1,2), (1,3), (2,3)\}$ is a relation on $\mathbb{Z}_4$ because $R \subseteq \mathbb{Z}_4 \times \mathbb{Z}_4$.

Ex: $R = \{(1,2), (1,3), (2,3)\}$ is a relation from $\mathbb{Z}_4$ to $\mathbb{Z}_5$ because $R \subseteq \mathbb{Z}_4 \times \mathbb{Z}_5$.

!!! Review subset and cartesian-product if these examples don't make sense to you.

$(1,2) \in R$ is a statement that 1 and 2 are related in the relation $R$. It is often written $1R2$ as shorthand.

Because $1R2$ is a statement, it is either true or false. For the $R$ above, it is true.

Some relations are familiar: The "less than" relation on $\mathbb{Z}$, for example.

$\{ (x,y) \in \mathbb{Z} \times \mathbb{Z}: \mbox{$x$ is less than $y$} \}$

But, relations don't have to be familiar or intuitive as the relation $R$ above showed.

Exercise 2: Let $A = \{1,2,3,4,5,6\}$. Write out the relation $R$ that expresses $|$ (divides) on $A$.

In other words, list the set of all $(x,y) \in A \times A$ where $x|y$. (Recall $x|y$ is true if $y$ is an integer multiple of $x$.)

$(3,6)$ is in there because $6 = 3 \cdot k$ for some integer $k$.

$(6,3)$ is not in there because $3 \neq 6 \cdot k$ for any integer $k$.

Methodically, I'd do this in my head using this pseudocode.

   for x = 1...6
      for y = 1...6
         if (y mod x == 0)  // y a multiple of x means y/x has no remainder
            print (x,y)

Because relations are sets of ordered pairs, be sure to write a set of ordered pairs

Solution 2: $R = \{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)\}$.

Exercise 4: Here is a diagram for a relation $R$ on a set $A$. Write the sets $A$ and $R$.

We can assume they want to know the smallest set $A$ for which $R$ is on, so that's just the labels on the dots.

In an arrow diagram, every arrow represents an ordered pair $(x,y)$ where $x$ is the source and $y$ the destination.

Solution 4: $A = \{0,1,2,3,4,5\}$. (Notice this is $\mathbb{Z}_6$ in the notation given above.) $R = \{(0,0),(0,4),(1,1),(1,3),(1,5),(2,2),(2,4),(3,3),(3,1),(4,4),(4,0),(4,2),(5,5),(5,1)\}$.

Exercise 6: Congruence modulo 5 is a relation on the set $A = \mathbb{Z}$. In this relation $xRy$ means $x \equiv y$ (mod 5). Write out the set $R$ in set-builder notation.

The problem says that $(x,y) \in R$ if the open senetence "$x \equiv y$ (mod 5)" is true. Since set builder notation uses an open sentence after the ":", it is straghtforward to write.

Note: $x \equiv y$ (mod 5) is a statement saying that when you apply "mod 5" to $x$ and $y$ they're equal.

Solution 6: $R = \{(x,y) \in \mathbb{Z} \times \mathbb{Z}: x \bmod 5 = y \bmod 5 \}$.

Exercise 8: Let $A= \{1,2,3,4,5,6\}$. Observe that $\varnothing \subseteq A \times A$, so $R=\varnothing$ is a relation on $A$. Draw a diagram for this relation.

To draw a diagram for a realtion on $A$: (It's a little different for digrams from $A$ to $B$.)

xxxxxxxxxx
   for lbl in A
      Draw dot labeled with lbl's value
   for (x,y) in R
      Draw arrow from x to y

Solution 8: There should be a labeled dot for each element of $A$, and since there are no ordered pairs, there should be no arrows.