Types of Relations and Functions

Why this mat­ters#

Think about how "equals" behaves. Every­thing equals itself, it works in both direc­tions, and you can chain it along. Some rela­tions behave in exactly the same way, and when they do, they sort a set neatly into groups that never over­lap. In this chap­ter we name these prop­er­ties (reflex­ive, sym­met­ric, tran­si­tive), meet equiv­a­lence rela­tions and their classes, and then sort func­tions into one-one, onto, or both.

Types of rela­tions#

A rela­tion $R$ on a set $A$ is sim­ply a sub­set of $A \times A$. We call it

• empty if $R = \varnothing$, uni­ver­sal if $R = A \times A$;
• reflex­ive if $(a, a) \in R$ for every $a \in A$;
• sym­met­ric if $(a, b) \in R \Rightarrow (b, a) \in R$;
• tran­si­tive if $(a, b), (b, c) \in R \Rightarrow (a, c) \in R$.

When a rela­tion has all three of the last prop­er­ties, we call it an equiv­a­lence rela­tion.

Equiv­a­lence classes#

Given an equiv­a­lence rela­tion, the class of $a$ is $[a] = \{x : (x, a) \in R\}$, the set of every­thing related to it. Here is the lovely part: any two classes are either exactly the same or com­pletely sep­a­rate, and together they fill the whole set. Exam­ple 1 has four classes: $[0]$ (mul­ti­ples of $4$), $[1]$, $[2]$, $[3]$.

Types of func­tions#

Now to func­tions. We say $f : A \to B$ is

• one-one (injec­tive) if $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$, so dif­fer­ent inputs always give dif­fer­ent out­puts;
• onto (sur­jec­tive) if every $b \in B$ is $f(a)$ for some $a$, so the range is the whole of $B$;
• bijec­tive if it is both.

A handy short­cut: for finite sets with $n(A) = n(B)$, one-one and onto mean the same thing, so check­ing one is enough.

Prac­tice#

1. On $\{1, 2, 3, 4\}$, work out which prop­er­ties each rela­tion has: $R_1 = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 1)\}$; $R_2 = \{(1, 2), (2, 1)\}$; $R_3 = \{(1, 2), (2, 3), (1, 3)\}$.
2. Show that $R = \{(a, b) : a - b \text{ is a multiple of } 5\}$ on $\mathbf{Z}$ is an equiv­a­lence rela­tion. Describe $[2]$.
3. On the set of all tri­an­gles, show that "is sim­i­lar to" is an equiv­a­lence rela­tion.
4. On $\mathbf{N}$, is $R = \{(a, b) : a \text{ divides } b\}$ reflex­ive? Sym­met­ric? Tran­si­tive?
5. Give an exam­ple of a rela­tion on $\{1, 2, 3\}$ that is sym­met­ric and tran­si­tive but not reflex­ive.
6. On $A = \{1, 2, \ldots, 12\}$, $R = \{(a, b) : 3 \mid a - b\}$. List the equiv­a­lence classes.
7. Decide one-one / onto: $f : \mathbf{R} \to \mathbf{R}$, $f(x) = 5 - 2x$; $f : \mathbf{R} \to \mathbf{R}$, $f(x) = \lvert x \rvert$; $f : \mathbf{N} \to \mathbf{N}$, $f(n) = n + 3$; $f : \mathbf{R} \to \mathbf{R}$, $f(x) = x^3$.
8. Show that $f : \mathbf{R} - \{2\} \to \mathbf{R} - \{1\}$, $\displaystyle f(x) = \tfrac{x - 1}{x - 2}$ is a bijec­tion.
9. How many one-one func­tions are there from $\{a, b\}$ to $\{1, 2, 3\}$? Onto func­tions from $\{1, 2, 3\}$ to $\{a, b\}$?
10. Is the signum func­tion one-one? Onto $\mathbf{R}$?

Answers#