Sets

Lessons

Senior 1 · Mathematics

Sets

5 lessons

Lesson 5 of 5

Relations and mappings

25 min

Pairs in which order matters

Three learners at a boarding school in Kigali come from different districts: Amani and Cedric are from Gasabo, and Bella is from Huye. The rule "comes from" pairs each learner with a district:

(\text{Amani},\ \text{Gasabo}),\quad (\text{Bella},\ \text{Huye}),\quad (\text{Cedric},\ \text{Gasabo}).

In each pair the learner comes first and the district second. Swap them and the pair no longer says "comes from". Pairs like these link the elements of one set to the elements of another; they are the building blocks of relations and mappings.

Definition

Ordered pair: two objects written in a fixed order, $(a, b)$ . The object $a$ is the first component and $b$ is the second component.

Rule: $(a, b) = (c, d)$ only when $a = c$ and $b = d$ . So $(2, 5) \neq (5, 2)$ , while the sets ${2, 5}$ and ${5, 2}$ are equal.

Definition

Cartesian product of $A$ and $B$ : the set of all ordered pairs whose first component is in $A$ and whose second component is in $B$ .

A \times B = \{(a, b) : a \in A \text{ and } b \in B\}

Read $A \times B$ as "A cross B".

Important

Rule: $n(A \times B) = n(A) \times n(B)$ .

Why: each of the $n (A)$ first components can be paired with each of the $n (B)$ second components, so the pairs form a table with $n (A)$ rows and $n (B)$ columns.

Worked example 1: a Cartesian product

$A = \{1, 2, 3\}$ and $B = \{x, y\}$ . List $A \times B$ and $B \times A$ .

Solution Build a table: rows for the elements of $A$ , columns for the elements of $B$ .

$\times$	$x$	$y$
1	$(1, x)$	$(1, y)$
2	$(2, x)$	$(2, y)$
3	$(3, x)$	$(3, y)$

A \times B = \{(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)\}

and $n(A \times B) = 3 \times 2 = 6$ , as the rule predicts.

$B \times A = \{(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)\}$ . It also has 6 pairs, but they are different pairs, so $A \times B \neq B \times A$ .

Relations

Definition

Relation from $A$ to $B$ : any subset $R$ of $A \times B$ . When $(a, b) \in R$ , we write $a \mathrel{R} b$ and say " $a$ is related to $b$ ".

Domain of $R$ : the set of first components of its pairs. Range of $R$ : the set of second components of its pairs.

Definition

Arrow diagram (papygram): a picture of a relation in which the two sets are drawn as ovals, with an arrow from $a$ to $b$ whenever $a \mathrel{R} b$ .

Worked example 2: "is a factor of"

$A = \{2, 3, 5\}$ , $B = \{4, 6, 9, 10, 15\}$ and $R$ is the relation "is a factor of" from $A$ to $B$ . List $R$ , draw its arrow diagram and state its domain and range.

Solution 2 divides 4, 6 and 10; 3 divides 6, 9 and 15; 5 divides 10 and 15. So

R = \{(2, 4), (2, 6), (2, 10), (3, 6), (3, 9), (3, 15), (5, 10), (5, 15)\}.

Each arrow is one ordered pair of R.

Domain $= \{2, 3, 5\}$ ; range $= \{4, 6, 9, 10, 15\}$ . $R$ has 8 of the $3 \times 5 = 15$ pairs in $A \times B$ .

Relations on one set: three properties

When a relation links a set $A$ to itself, we call it a relation on $A$ . Three properties describe how such a relation behaves.

Definition

Let $R$ be a relation on a set $A$ .

Reflexive: every element is related to itself: $a \mathrel{R} a$ for every $a \in A$ .
Symmetric: whenever $a \mathrel{R} b$ , also $b \mathrel{R} a$ .
Transitive: whenever $a \mathrel{R} b$ and $b \mathrel{R} c$ , also $a \mathrel{R} c$ .

An equivalence relation is a relation that is reflexive, symmetric and transitive.

Relation	Reflexive	Symmetric	Transitive
"is equal to", on numbers	yes	yes	yes
"is less than" ( $< \lt$ ), on numbers	no: $3 \lt 3$ is false	no: $2 \lt 5$ but not $5 \lt 2$	yes
"is a factor of", on $\{1, 2, 3, \ldots\}$	yes	no: 2 is a factor of 4, but 4 is not a factor of 2	yes
"differs by 1 from", on numbers	no	yes	no: 3 and 4 differ by 1, 4 and 5 differ by 1, but 3 and 5 differ by 2
"is in the same class as", on the learners of a school	yes	yes	yes

"Is equal to" and "is in the same class as" are equivalence relations. An equivalence relation sorts a set into groups (here, classes) that do not overlap.

Worked example 3: testing the three properties

On $A = \{1, 2, 3\}$ , let $R = \{(1, 1), (2, 2), (3, 3), (1, 3), (3, 1)\}$ and $S = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)\}$ . Is either an equivalence relation?

Solution

$R$ : reflexive, since $(1, 1), (2, 2), (3, 3) \in R$ . Symmetric, since the only pair with different components, $(1, 3)$ , comes with $(3, 1)$ . Transitive: $(1, 3)$ and $(3, 1)$ require $(1, 1)$ , which is in $R$ ; $(3, 1)$ and $(1, 3)$ require $(3, 3)$ , which is in $R$ ; chains that use a pair $(a, a)$ give nothing new. So $R$ is an equivalence relation.
$S$ : reflexive, but not symmetric, because $(1, 2) \in S$ and $(2, 1) \notin S$ . One failure is enough: $S$ is not an equivalence relation. (It is not transitive either: $(1, 2)$ and $(2, 3)$ are in $S$ , but $(1, 3)$ is not.)

Mappings

Definition

Mapping (function) from $A$ to $B$ : a relation in which every element of $A$ is related to exactly one element of $B$ .

Notation: $f : A \to B$ , and $f : x \mapsto f(x)$ or $f(x) = \ldots$ for the rule. $f (x)$ is called the image of $x$ .

Domain $= A$ ; codomain $= B$ ; range $= \{f(x) : x \in A\}$ , the set of images, which is a subset of $B$ .

Every relation between two finite sets is of one of four types. Only two of them are mappings.

The four types of relation. In a mapping, exactly one arrow leaves each element of the domain.

Worked example 4: domain, range and graph of a mapping

$f : x \mapsto 2x + 1$ has domain $\{0, 1, 2, 3\}$ . Find the range, write $f$ as a set of ordered pairs, say which type of relation it is, and draw its graph.

Solution $f (0) = 1$ , $f (1) = 3$ , $f (2) = 5$ , $f (3) = 7$ . So the range is $\{1, 3, 5, 7\}$ and

f = \{(0, 1), (1, 3), (2, 5), (3, 7)\}.

Different inputs give different images, so $f$ is one-to-one. Plot each pair as a point, with the input on the horizontal axis and the image on the vertical axis.

The graph of $f$ is four separate points. They are not joined, because the domain contains only 0, 1, 2 and 3.

Warning

Test a mapping from the domain side. Every element of the domain must have exactly one arrow leaving it: no element with no arrow, and no element with two. Elements of $B$ are free: one may receive several arrows (many-to-one) and another none at all.

Tip

In an ordered pair, think "input first, output second": $(x, f (x))$ . In a graph, the first component is read across and the second up, which is why $(2, 5)$ and $(5, 2)$ are different points.

Khan Academy: Relations and functions (7 min). Sal checks whether a relation is a function by asking whether any input has more than one output, the same test as the mapping rule in this lesson.

✦

Practice

The last two questions are harder.

$A = \{1, 2\}$ and $B = \{a, b, c\}$ . List $A \times B$ and find $n(A \times B)$ .
Find $x$ and $y$ if $(x + 1, 7) = (5, y - 2)$ .
On $A = \{1, 2, 3, 4\}$ , $R$ is the relation "is less than". List $R$ and give its domain and range.
Is $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ an equivalence relation on $\{1, 2, 3\}$ ? Check all three properties.
$A = \{1, 2, 3\}$ and $B = \{4, 5, 6\}$ . Which of these relations from $A$ to $B$ are mappings? (a) $\{(1, 4), (2, 4), (3, 6)\}$ (b) $\{(1, 4), (1, 5), (2, 6), (3, 6)\}$ (c) $\{(1, 5), (2, 6)\}$
$f : x \mapsto x^2 + 1$ has domain $\{0, 1, 2, 3\}$ . Find its range and say which type of relation it is.
$g$ maps each number in $\{1, 2, 3, 4, 5, 6\}$ to its remainder when divided by 3. Find the range of $g$ , draw its arrow diagram, and say which type of relation it is.

Show answersHide answers

$\{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)\}$ ; $n = 2 \times 3 = 6$ .
$x + 1 = 5$ , so $x = 4$ ; $7 = y - 2$ , so $y = 9$ .
$R = \{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}$ ; domain $\{1, 2, 3\}$ , range $\{2, 3, 4\}$ .
Yes. Reflexive: $(1, 1), (2, 2), (3, 3) \in R$ . Symmetric: $(1, 2)$ comes with $(2, 1)$ . Transitive: $(1, 2), (2, 1)$ need $(1, 1)$ ✓ and $(2, 1), (1, 2)$ need $(2, 2)$ ✓.
(a) A mapping (many-to-one). (b) Not a mapping: 1 has two images. (c) Not a mapping: 3 has no image.
$f(0) = 1,\ f(1) = 2,\ f(2) = 5,\ f(3) = 10$ : range $\{1, 2, 5, 10\}$ ; one-to-one.
$g(1) = 1,\ g(2) = 2,\ g(3) = 0,\ g(4) = 1,\ g(5) = 2,\ g(6) = 0$ : range $\{0, 1, 2\}$ ; many-to-one (for example 1 and 4 have the same image).

1Pairs in which order matters

2Relations

3Relations on one set: three properties

4Mappings

Pairs in which order matters

Relations

Relations on one set: three properties

Mappings