Types of Relations and Functions — Worked Solutions

Ques­tion 1: Prop­er­ties of three rela­tions#

The prob­lem#

On $\{1, 2, 3, 4\}$, decide which prop­er­ties hold:
$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)\}$.

Under­stand­ing the prob­lem#

For each rela­tion check three prop­er­ties on the set $A = \{1, 2, 3, 4\}$:

• reflex­ive: all four pairs $(1,1), (2,2), (3,3), (4,4)$ are present;
• sym­met­ric: when­ever $(a, b)$ is present, so is $(b, a)$;
• tran­si­tive: when­ever $(a, b)$ and $(b, c)$ are present, so is $(a, c)$.

The idea#

Test each prop­erty pair by pair. To show a prop­erty fails, one miss­ing pair is enough.

Step-by-step solu­tion#

Rela­tion $R_1$

Step 1. Reflex­ive: $(1,1), (2,2), (3,3), (4,4)$ are all in $R_1$. ✓

Step 2. Sym­met­ric: the only non-diag­o­nal pairs are $(1, 3)$ and $(3, 1)$, and each has its reverse. ✓

Step 3. Tran­si­tive: the chains are $(1,3),(3,1) \Rightarrow (1,1)$ ✓; $(3,1),(1,3) \Rightarrow (3,3)$ ✓; any chain through a diag­o­nal pair like $(1,1),(1,3)$ gives back $(1,3)$ ✓.

Step 4. All three hold, so $R_1$ is an equiv­a­lence rela­tion.

Rela­tion $R_2$

Step 1. Reflex­ive? $(1, 1) \notin R_2$. ✗

Step 2. Sym­met­ric: $(1, 2)$ and $(2, 1)$ are both present. ✓

Step 3. Tran­si­tive? $(1, 2)$ and $(2, 1)$ are present, so $(1, 1)$ would have to be, but it is not. ✗

Rela­tion $R_3$

Step 1. Reflex­ive? $(1, 1) \notin R_3$. ✗

Step 2. Sym­met­ric? $(1, 2) \in R_3$ but $(2, 1) \notin R_3$. ✗

Step 3. Tran­si­tive: the only chain is $(1, 2), (2, 3)$, which needs $(1, 3)$, and it is present. No other pair $(b, c)$ starts where another pair ends. ✓

Check­ing the answer#

A brute-force check of all pairs by com­puter gives: $R_1$ (reflex­ive, sym­met­ric, tran­si­tive); $R_2$ (sym­met­ric only); $R_3$ (tran­si­tive only). ✓

Answer#

$R_1$ is an equiv­a­lence rela­tion; $R_2$ is sym­met­ric only; $R_3$ is tran­si­tive only.

Com­mon mis­take to avoid#

Think­ing $R_2$ is tran­si­tive because "there is noth­ing to chain". The chain $(1, 2), (2, 1)$ demands $(1, 1)$.

Ques­tion 2: Con­gru­ence mod­ulo 5#

The prob­lem#

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]$.

Under­stand­ing the prob­lem#

You must prove all three prop­er­ties for every inte­ger, not just check exam­ples. Then list the class of $2$: all inte­gers related to $2$.

The idea#

Fol­low Exam­ple 1 of the les­son, which does the same for $4$. Write "mul­ti­ple of $5$" as $5k$ with $k$ an inte­ger.

Step-by-step solu­tion#

Step 1. Reflex­ive. For any inte­ger $a$, $a - a = 0 = 5 \times 0$, a mul­ti­ple of $5$. So $(a, a) \in R$.

Step 2. Sym­met­ric. Sup­pose $(a, b) \in R$, so $a - b = 5k$. Then

$$b - a = -5k = 5(-k),$$

a mul­ti­ple of $5$. So $(b, a) \in R$.

Step 3. Tran­si­tive. Sup­pose $a - b = 5k$ and $b - c = 5m$. Add them.

$$a - c = (a - b) + (b - c) = 5k + 5m = 5(k + m)$$

So $(a, c) \in R$.

Step 4. All three hold, so $R$ is an equiv­a­lence rela­tion.

Step 5. The class of $2$: all $x$ with $x - 2 = 5k$, that is $x = 5k + 2$.

$$[2] = \{\ldots, -8, -3, 2, 7, 12, \ldots\}$$

Check­ing the answer#

$12 - 2 = 10$ ✓ and $-3 - 2 = -5$ ✓, both mul­ti­ples of $5$. Each ele­ment of $[2]$ leaves remain­der $2$ on divi­sion by $5$.

Answer#

$R$ is reflex­ive, sym­met­ric and tran­si­tive, hence an equiv­a­lence rela­tion; $[2] = \{5k + 2 : k \in \mathbf{Z}\} = \{\ldots, -8, -3, 2, 7, 12, \ldots\}$.

Ques­tion 3: Sim­i­lar­ity of tri­an­gles#

The prob­lem#

On the set of all tri­an­gles, show that "is sim­i­lar to" is an equiv­a­lence rela­tion.

Under­stand­ing the prob­lem#

Say $T_1 \, R \, T_2$ when tri­an­gle $T_1$ is sim­i­lar to tri­an­gle $T_2$, mean­ing their cor­re­spond­ing angles are equal (equiv­a­lently, cor­re­spond­ing sides are in the same ratio). You must prove the three prop­er­ties.

The idea#

Use the angle descrip­tion of sim­i­lar­ity: two tri­an­gles are sim­i­lar when their angles can be matched so that cor­re­spond­ing angles are equal. Equal­ity of num­bers is reflex­ive, sym­met­ric and tran­si­tive, and that car­ries over.

Step-by-step solu­tion#

Step 1. Reflex­ive. Any tri­an­gle $T$ has the same angles as itself (match each angle with itself), so $T$ is sim­i­lar to $T$.

Step 2. Sym­met­ric. If $T_1$ is sim­i­lar to $T_2$, the angles of $T_1$ equal the cor­re­spond­ing angles of $T_2$. Read­ing the same cor­re­spon­dence back­wards, the angles of $T_2$ equal those of $T_1$, so $T_2$ is sim­i­lar to $T_1$.

Step 3. Tran­si­tive. If $T_1 \sim T_2$ and $T_2 \sim T_3$, each angle of $T_1$ equals the match­ing angle of $T_2$, which equals the match­ing angle of $T_3$. So the angles of $T_1$ equal those of $T_3$, and $T_1 \sim T_3$.

Step 4. Hence sim­i­lar­ity is an equiv­a­lence rela­tion.

Check­ing the answer#

The same argu­ment works with side ratios: if the ratio is $k$ from $T_1$ to $T_2$ and $m$ from $T_2$ to $T_3$, it is $km$ from $T_1$ to $T_3$, and $\displaystyle \tfrac{1}{k}$ from $T_2$ back to $T_1$.

Answer#

Sim­i­lar­ity is reflex­ive, sym­met­ric and tran­si­tive, so it is an equiv­a­lence rela­tion on tri­an­gles.

Ques­tion 4: "Divides" on the nat­ural num­bers#

The prob­lem#

On $\mathbf{N}$, is $R = \{(a, b) : a \text{ divides } b\}$ reflex­ive, sym­met­ric, tran­si­tive?

Under­stand­ing the prob­lem#

"$a$ divides $b$" means $b = ak$ for some nat­ural num­ber $k$. Check each prop­erty; for a fail­ure give a spe­cific counter-exam­ple.

The idea#

Write divis­i­bil­ity as mul­ti­pli­ca­tion and test each prop­erty.

Step-by-step solu­tion#

Step 1. Reflex­ive. $a = a \times 1$, so $a$ divides $a$ for every $a$. ✓

Step 2. Sym­met­ric? Counter-exam­ple: $2$ divides $4$, but $4$ does not divide $2$. So $(2, 4) \in R$ but $(4, 2) \notin R$. ✗

Step 3. Tran­si­tive. If $a \mid b$ and $b \mid c$, then $b = ak$ and $c = bm$. So

$$c = (ak)m = a(km),$$

and $a \mid c$. ✓

Check­ing the answer#

Exam­ple of tran­si­tiv­ity: $2 \mid 6$ and $6 \mid 18$, and indeed $2 \mid 18$.

Answer#

$R$ is reflex­ive and tran­si­tive, but not sym­met­ric.

Ques­tion 5: Sym­met­ric and tran­si­tive but not reflex­ive#

The prob­lem#

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.

Under­stand­ing the prob­lem#

You must build one rela­tion that has two prop­er­ties and lacks the third. It fails to be reflex­ive if at least one of $(1,1), (2,2), (3,3)$ is miss­ing.

The idea#

Leave out one ele­ment entirely: relate $1$ and $2$ only to them­selves and never men­tion $3$. Then there are no pairs that could break sym­me­try or tran­si­tiv­ity.

Step-by-step solu­tion#

Step 1. Take $R = \{(1, 1), (2, 2)\}$.

Step 2. Not reflex­ive: $(3, 3) \notin R$.

Step 3. Sym­met­ric: each pair $(a, a)$ is its own reverse.

Step 4. Tran­si­tive: the only chains are $(1,1),(1,1) \Rightarrow (1,1)$ and $(2,2),(2,2) \Rightarrow (2,2)$, both present.

Check­ing the answer#

A com­puter check of the three prop­er­ties gives (not reflex­ive, sym­met­ric, tran­si­tive). ✓ Other answers are pos­si­ble, for exam­ple $\{(1,1),(1,2),(2,1),(2,2)\}$.

Answer#

$R = \{(1, 1), (2, 2)\}$ is sym­met­ric and tran­si­tive but not reflex­ive, since $(3, 3) \notin R$.

Ques­tion 6: Equiv­a­lence classes mod­ulo 3#

The prob­lem#

On $A = \{1, 2, \ldots, 12\}$, $R = \{(a, b) : 3 \mid a - b\}$. List the equiv­a­lence classes.

Under­stand­ing the prob­lem#

Two num­bers are related when their dif­fer­ence is a mul­ti­ple of $3$, that is, when they leave the same remain­der on divi­sion by $3$. Each class col­lects all num­bers with the same remain­der.

The idea#

Sort $1$ to $12$ by remain­der on divi­sion by $3$: remain­der $1$, $2$ or $0$.

Step-by-step solu­tion#

Step 1. Remain­der $1$: $1, 4, 7, 10$.

Step 2. Remain­der $2$: $2, 5, 8, 11$.

Step 3. Remain­der $0$: $3, 6, 9, 12$.

Step 4. These three sets are the classes $[1]$, $[2]$ and $[3]$.

Check­ing the answer#

The classes are dis­joint and together con­tain all $12$ ele­ments ($4 + 4 + 4 = 12$), as equiv­a­lence classes must.

Answer#

$\{1, 4, 7, 10\}$, $\{2, 5, 8, 11\}$, $\{3, 6, 9, 12\}$.

Ques­tion 7: One-one and onto for four func­tions#

The prob­lem#

Decide whether each is one-one and whether it is onto: (a) $f : \mathbf{R} \to \mathbf{R}$, $f(x) = 5 - 2x$; (b) $f : \mathbf{R} \to \mathbf{R}$, $f(x) = \lvert x \rvert$; (c) $f : \mathbf{N} \to \mathbf{N}$, $f(n) = n + 3$; (d) $f : \mathbf{R} \to \mathbf{R}$, $f(x) = x^3$.

Under­stand­ing the prob­lem#

One-one: $f(x_1) = f(x_2)$ forces $x_1 = x_2$. Onto: every ele­ment $y$ of the codomain equals $f(x)$ for some $x$ in the domain. Pay atten­tion to the domain and codomain given.

The idea#

For one-one, start from $f(x_1) = f(x_2)$ and try to reach $x_1 = x_2$. For onto, take any $y$ and solve $f(x) = y$ for $x$, check­ing that $x$ lies in the domain. Use a counter-exam­ple when a prop­erty fails.

Step-by-step solu­tion#

Part (a)

Step 1. One-one: $5 - 2x_1 = 5 - 2x_2 \Rightarrow -2x_1 = -2x_2 \Rightarrow x_1 = x_2$. ✓

Step 2. Onto: given $y \in \mathbf{R}$, solve $5 - 2x = y$ to get $\displaystyle x = \frac{5 - y}{2}$, a real num­ber. Then $\displaystyle f\left(\frac{5 - y}{2}\right) = 5 - (5 - y) = y$. ✓

Step 3. So $f$ is bijec­tive.

Part (b)

Step 1. One-one? $f(2) = 2 = f(-2)$ but $2 \ne -2$. ✗

Step 2. Onto? $\lvert x \rvert \ge 0$, so a neg­a­tive num­ber such as $-1$ has no preim­age. ✗

Part (c)

Step 1. One-one: $n_1 + 3 = n_2 + 3 \Rightarrow n_1 = n_2$. ✓

Step 2. Onto? The small­est out­put is $f(1) = 4$. So $1$, $2$ and $3$ are never out­puts (their preim­ages would be $-2, -1, 0$, not nat­ural num­bers). ✗

Part (d)

Step 1. One-one: if $x_1^3 = x_2^3$, then tak­ing the real cube root of both sides gives $x_1 = x_2$ (every real num­ber has exactly one real cube root). ✓

Step 2. Onto: given $y \in \mathbf{R}$, take $x = \sqrt[3]{y}$; then $x^3 = y$. ✓

Step 3. So $f$ is bijec­tive.

Check­ing the answer#

Graph­i­cally, (a) and (d) pass the hor­i­zon­tal-line test and cover every height; (b) has a V shape, fail­ing both; (c) shifts every nat­ural num­ber up by $3$, never reach­ing $1, 2, 3$.

Answer#

(a) bijec­tive; (b) nei­ther one-one nor onto; (c) one-one but not onto ($1, 2, 3$ are missed); (d) bijec­tive.

Ques­tion 8: Prov­ing a bijec­tion#

The prob­lem#

Show that $f : \mathbf{R} - \{2\} \to \mathbf{R} - \{1\}$, $\displaystyle f(x) = \frac{x - 1}{x - 2}$ is a bijec­tion.

Under­stand­ing the prob­lem#

You must show $f$ is both one-one and onto. The domain leaves out $2$ (where the denom­i­na­tor is zero) and the codomain leaves out $1$; you will see why $1$ is excluded.

The idea#

One-one: set $f(x_1) = f(x_2)$, cross-mul­ti­ply and sim­plify. Onto: solve $\displaystyle \frac{x - 1}{x - 2} = y$ for $x$ and check that the $x$ found is allowed.

Step-by-step solu­tion#

Step 1. One-one. Sup­pose $f(x_1) = f(x_2)$.

$$\displaystyle \frac{x_1 - 1}{x_1 - 2} = \frac{x_2 - 1}{x_2 - 2}$$

Step 2. Cross-mul­ti­ply and expand.

$$\begin{aligned} (x_1 - 1)(x_2 - 2) &= (x_2 - 1)(x_1 - 2) \\ x_1x_2 - 2x_1 - x_2 + 2 &= x_1x_2 - 2x_2 - x_1 + 2 \end{aligned}$$

Step 3. Can­cel $x_1x_2$ and $2$ from both sides and col­lect.

$$-2x_1 - x_2 = -2x_2 - x_1 \quad\Longrightarrow\quad -x_1 = -x_2 \quad\Longrightarrow\quad x_1 = x_2$$

So $f$ is one-one.

Step 4. Onto. Take any $y \ne 1$ and solve $f(x) = y$.

$$\displaystyle \begin{aligned} x - 1 &= y(x - 2) \\ x - 1 &= xy - 2y \\ x - xy &= 1 - 2y \\ x(1 - y) &= 1 - 2y \\ x &= \frac{1 - 2y}{1 - y} = \frac{2y - 1}{y - 1} \end{aligned}$$

This divi­sion is allowed because $y \ne 1$.

Step 5. Check that this $x$ is in the domain, i.e. $x \ne 2$. If $\displaystyle \frac{2y - 1}{y - 1} = 2$, then $2y - 1 = 2y - 2$, i.e. $-1 = -2$, impos­si­ble. So $x \ne 2$.

Step 6. Check that it works.

$$\displaystyle f(x) = \frac{\frac{2y - 1}{y - 1} - 1}{\frac{2y - 1}{y - 1} - 2} = \frac{\frac{y}{y - 1}}{\frac{1}{y - 1}} = y$$

So $f$ is onto, and hence a bijec­tion.

Check­ing the answer#

Test $y = 3$: $\displaystyle x = \frac{5}{2}$, and $\displaystyle f\left(\frac{5}{2}\right) = \frac{3/2}{1/2} = 3$. ✓ Also $f(x) = 1$ would need $x - 1 = x - 2$, impos­si­ble, which is why $1$ is removed from the codomain.

Answer#

$f(x_1) = f(x_2) \Rightarrow x_1 = x_2$, and every $y \ne 1$ equals $\displaystyle f\left(\frac{2y - 1}{y - 1}\right)$ with $\displaystyle \frac{2y - 1}{y - 1} \ne 2$; so $f$ is a bijec­tion.

Ques­tion 9: Count­ing one-one and onto func­tions#

The prob­lem#

How many one-one func­tions are there from $\{a, b\}$ to $\{1, 2, 3\}$? How many onto func­tions from $\{1, 2, 3\}$ to $\{a, b\}$?

Under­stand­ing the prob­lem#

A func­tion assigns one out­put to each input. For one-one, $a$ and $b$ must get dif­fer­ent out­puts. For onto, both $a$ and $b$ must be used as out­puts at least once.

The idea#

Count one-one func­tions by the mul­ti­pli­ca­tion prin­ci­ple. Count onto func­tions by count­ing all func­tions and sub­tract­ing those that miss an out­put.

Step-by-step solu­tion#

Step 1. One-one from $\{a, b\}$ to $\{1, 2, 3\}$: $a$ has $3$ choices; $b$ must be dif­fer­ent, so $2$ choices.

$$3 \times 2 = 6$$

Step 2. All func­tions from $\{1, 2, 3\}$ to $\{a, b\}$: each of the $3$ inputs has $2$ choices.

$$2^3 = 8$$

Step 3. Func­tions that are not onto use only one out­put: all to $a$, or all to $b$. That is $2$ func­tions.

Step 4. Onto func­tions.

$$8 - 2 = 6$$

Check­ing the answer#

List­ing by com­puter: $6$ one-one func­tions and $6$ onto func­tions. ✓

Answer#

$6$ one-one func­tions and $6$ onto func­tions.

Ques­tion 10: The signum func­tion#

The prob­lem#

Is the signum func­tion one-one? Is it onto $\mathbf{R}$?

Under­stand­ing the prob­lem#

The signum func­tion $f : \mathbf{R} \to \mathbf{R}$ is

$$f(x) = \begin{cases} 1, & x > 0 \\ 0, & x = 0 \\ -1, & x < 0. \end{cases}$$

The idea#

For one-one, look for two dif­fer­ent inputs with the same out­put. For onto, look at the range and com­pare it with the codomain $\mathbf{R}$.

Step-by-step solu­tion#

Step 1. One-one? $f(1) = 1 = f(2)$, but $1 \ne 2$. So it is not one-one.

Step 2. Onto? The only out­puts are $-1$, $0$ and $1$. So the range is $\{-1, 0, 1\}$, not all of $\mathbf{R}$; for exam­ple, $5$ has no preim­age.

Check­ing the answer#

The graph is three flat pieces; a hor­i­zon­tal line at height $1$ meets it infi­nitely often, and a line at height $5$ never meets it.

Answer#

No, it is not one-one; and no, it is not onto $\mathbf{R}$, since its range is $\{-1, 0, 1\}$.