Ordered pairs, products and relations

Order matters

On a map, the point $(3, 5)$ is not the point $(5, 3)$. A seat in a cinema is "row $4$, seat $7$", and it is not "row $7$, seat $4$". When the order matters, we write the two items as an ordered pair $(a, b)$.

Two ordered pairs are equal only when both places match:

For example, if $(x + 1, 3) = (4, y - 2)$, then $x + 1 = 4$ and $3 = y - 2$, so $x = 3$ and $y = 5$.

The Cartesian product

The Cartesian product of two sets $A$ and $B$ is the set of all ordered pairs with the first element from $A$ and the second from $B$:

If $A = \{1, 2\}$ and $B = \{x, y, z\}$, then

There are $2 \times 3 = 6$ pairs. In general, $n(A \times B) = n(A) \times n(B)$. Also $A \times B \neq B \times A$ unless $A = B$, because $(1, x)$ is not $(x, 1)$.

The product $\mathbb{R} \times \mathbb{R}$ is the set of all pairs of real numbers. These are exactly the points of the coordinate plane, which is why the plane is written $\mathbb{R}^2$.

Count the crossings: there are always $m \times n$. A relation picks any collection of them, so there are $2^{mn}$ relations.

Relations

A relation $R$ from a set $A$ to a set $B$ is any subset of $A \times B$. We write $(a, b) \in R$, or $a\,R\,b$, and we say that "$a$ is related to $b$".

In an arrow diagram, we draw an arrow from $a$ to $b$ for every pair $(a, b)$ in $R$. Here $R = \{(1, x), (1, y), (2, z)\}$. The element $1$ has two arrows, and the element $3$ has none. A relation allows both.

Three sets belong to a relation from $A$ to $B$:

• the domain, the set of all first elements: here $\{1, 2\}$;
• the codomain, the whole set $B$: here $\{x, y, z\}$;
• the range, the set of the second elements that actually occur: here $\{x, y, z\}$.

The domain is a subset of $A$, and the range is a subset of the codomain.

A relation by a rule. Let $A = \{1, 2, 3, 4\}$ and let $R = \{(x, y) : y = x + 2\}$ from $A$ to $\mathbb{N}$. Then $R = \{(1,3), (2,4), (3,5), (4,6)\}$. The domain is $\{1, 2, 3, 4\}$ and the range is $\{3, 4, 5, 6\}$.

How many relations? A relation is a subset of $A \times B$, and this product has $n(A)\,n(B)$ elements. So the number of relations from $A$ to $B$ is

For $A = \{1, 2\}$ and $B = \{x, y, z\}$ it is $2^6 = 64$.

Relations on one set

A relation from $A$ to $A$ is called a relation on $A$. Three properties are important.

• Reflexive: every $a$ is related to itself, $(a, a) \in R$.
• Symmetric: if $(a, b) \in R$ then $(b, a) \in R$.
• Transitive: if $(a, b) \in R$ and $(b, c) \in R$ then $(a, c) \in R$.

A relation with all three properties is an equivalence relation. It sorts the elements into groups that do not overlap.

Example. On $\mathbb{Z}$, let $a\,R\,b$ mean that $a - b$ is divisible by $3$. It is reflexive, since $a - a = 0$. It is symmetric, since if $3$ divides $a - b$ it also divides $b - a$. It is transitive, since if $3$ divides $a - b$ and $b - c$ then it divides their sum, $a - c$. So $R$ is an equivalence relation. It puts two numbers in the same group when they leave the same remainder after division by $3$.

Counterexample. "$a$ is less than $b$" on $\mathbb{N}$ is transitive, but it is not reflexive (since $a < a$ is false) and not symmetric.

Practise with new numbers

Try it in Python

This program makes the Cartesian product of $\{1, 2\}$ and $\{x, y, z\}$, finds one relation in it, and counts all the relations.

Remember these

• An ordered pair $(a, b)$ has a first and a second element, and $(a, b) = (c, d)$ only if $a = c$ and $b = d$.
• $A \times B$ is the set of all pairs. $n(A \times B) = n(A)\,n(B)$.
• A relation from $A$ to $B$ is any subset of $A \times B$. There are $2^{n(A)n(B)}$ of them.
• Domain: first elements. Codomain: the whole of $B$. Range: the second elements that occur.
• An equivalence relation is reflexive, symmetric and transitive.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. If $(a + 2, 5) = (7, b - 1)$, find $a$ and $b$.

2. $A$ has $3$ elements and $B$ has $4$. How many elements does $A \times B$ have, and how many relations are there from $A$ to $B$?

3. Is the relation "$a$ is a brother of $b$" reflexive?

4. On $\mathbb{N}$, is the relation "$a$ divides $b$" symmetric?