Relations

A relation is just a precise way of saying "$x$ is linked to $y$". Once we have the Cartesian product $A \times B$, every relation is simply a subset , a chosen list of pairs that we call related. This single idea unifies geometry, algebra, and (later) calculus.

Definitions

Let $A$ and $B$ be non-empty sets. A relation $R$ from $A$ to $B$ is a subset of $A \times B$. We write $a\,R\,b \quad\text{or}\quad (a, b) \in R$ to mean "$a$ is related to $b$" under $R$. A relation from $A$ to itself is called a relation on $A$.

The domain of $R$ is the set of first coordinates that actually appear: $\text{Dom}(R) = \{a \in A : \exists b \in B,\ (a, b) \in R\}.$

The range of $R$ is the set of second coordinates that actually appear: $\text{Range}(R) = \{b \in B : \exists a \in A,\ (a, b) \in R\}.$

The codomain of $R$ is the entire set $B$. Note range $\subseteq$ codomain, but they need not be equal.

Three ways to describe a relation

A relation can be given in three equivalent ways.

1. Roster form. List the pairs. $R = \{(1, 2), (1, 3), (2, 4)\}$.

2. Set-builder form. Use a rule. $R = \{(x, y) \in A \times B : x + y = 5\}$.

3. Arrow diagram. Draw the sets $A$ and $B$ as ovals of dots and connect $a \to b$ when $(a, b) \in R$. Helpful for visualising small relations.

Any single relation can be reformulated freely between these three.

Counting relations

How many relations are there from $A$ to $B$ when both are finite? A relation is any subset of $A \times B$, and $|A \times B| = |A| \cdot |B|$. The number of subsets of a finite set with $k$ elements is $2^k$. Hence $\text{Number of relations from } A \text{ to } B = 2^{|A| \cdot |B|}.$

For $|A| = 2, |B| = 3$ this is $2^6 = 64$ , already too many to enumerate by hand for casual problems.

A first taste of "kinds of relations"

You will study these formally in Class XII, but the vocabulary is worth meeting now. A relation $R$ on $A$ is called:

• Reflexive if $a\,R\,a$ for every $a \in A$.
• Symmetric if $a\,R\,b \Rightarrow b\,R\,a$.
• Transitive if $a\,R\,b$ and $b\,R\,c$ together imply $a\,R\,c$.

The equality relation $=$ has all three properties; the relation "is a brother of" is not reflexive but (loosely) symmetric, and the relation "is less than or equal to" is reflexive and transitive but not symmetric.

Worked examples

Example 1. Let $A = \{1, 2, 3, 4\}$, $B = \{1, 4, 9, 16\}$. Define $R = \{(x, y) \in A \times B : y = x^2\}$. List the pairs, domain, range, codomain.

For each $x \in A$, check if $x^2 \in B$:

• $x = 1$: $1 \in B$, pair $(1, 1)$.
• $x = 2$: $4 \in B$, pair $(2, 4)$.
• $x = 3$: $9 \in B$, pair $(3, 9)$.
• $x = 4$: $16 \in B$, pair $(4, 16)$.

$R = \{(1, 1), (2, 4), (3, 9), (4, 16)\}$.

$\text{Dom}(R) = \{1, 2, 3, 4\}$, $\text{Range}(R) = \{1, 4, 9, 16\}$, $\text{Codomain} = B = \{1, 4, 9, 16\}$.

Example 2. Let $A = \{1, 2, 3, 4, 5\}$. Define $R = \{(x, y) : y = x + 2,\ x, y \in A\}$. List $R$ and find its domain and range.

For each $x \in A$ check if $x + 2 \in A$. $x = 1: 3 \in A$. $x = 2: 4 \in A$. $x = 3: 5 \in A$. $x = 4: 6 \notin A$. $x = 5: 7 \notin A$. So $R = \{(1, 3), (2, 4), (3, 5)\}$.

Domain $= \{1, 2, 3\}$, Range $= \{3, 4, 5\}$.

Example 3. How many relations are there from a $3$-element set $A$ to a $2$-element set $B$?

$2^{|A| \cdot |B|} = 2^6 = 64$.

Example 4. The relation $R$ on $\mathbb{R}$ is defined by $x\,R\,y \iff x + y = 0$. Describe $R$ as a set of ordered pairs and as a graph.

$R = \{(x, -x) : x \in \mathbb{R}\}$. The graph is the line $y = -x$ in the Cartesian plane.

Example 5 (harder). Let $A = \{1, 2, 3, 4, 6\}$ and define $R$ on $A$ by $x\,R\,y \iff x \text{ divides } y$. List $R$, find Dom and Range, and decide if $R$ is reflexive, symmetric, transitive.

For each pair $(x, y)$ with $x | y$ and both in $A$:

• $1$: divides $1, 2, 3, 4, 6$ , pairs $(1,1), (1,2), (1,3), (1,4), (1,6)$.
• $2$: divides $2, 4, 6$ , $(2,2), (2,4), (2,6)$.
• $3$: divides $3, 6$ , $(3,3), (3,6)$.
• $4$: divides $4$ , $(4,4)$.
• $6$: divides $6$ , $(6,6)$.

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

Domain $=$ Range $= A$ (since each element divides itself).

Reflexive: yes, $(a, a) \in R$ for all $a$. Symmetric: no, e.g. $(1, 2) \in R$ but $(2, 1) \notin R$. Transitive: yes ($a | b$ and $b | c$ imply $a | c$).

Try it yourself

1. Let $A = \{1, 2, 3\}$, $B = \{4, 5, 6\}$. Write $R = \{(x, y) : x + y = 7\}$ in roster form. Find Dom, Range, Codomain.
2. Find the number of relations from a set of $5$ elements to itself.
3. Define $R$ on $\mathbb{Z}$ by $x\,R\,y \iff x - y$ is divisible by $3$. Is $R$ reflexive? Symmetric? Transitive?
4. Let $A = \{1, 2, 3, 4\}$. Write $R = \{(x, y) : y = 2x\}$ in roster form.
5. Let $A = \{-2, -1, 0, 1, 2\}$. Write $R = \{(x, y) : y = |x|, y \in A\}$ in roster form.
6. Find Dom and Range of $R = \{(x, x^3) : x \in \{1, 2, 3, 4\}\}$.
7. Draw the arrow diagram of $R = \{(1, a), (2, a), (3, b)\}$ from $\{1, 2, 3\}$ to $\{a, b, c\}$.
8. Express the relation "$x + 2y = 8$, $x, y \in \mathbb{N}$" in roster form.
9. Find the relation $R$ on $\{1, 2, 3, 4, 5, 6\}$ given by $x\,R\,y \iff y = x + 1$.
10. Decide if "is a friend of" (on people) is reflexive, symmetric, transitive.
11. If $A$ has $4$ elements, how many relations on $A$ are reflexive? (Hint: each "diagonal" pair must be in; each off-diagonal pair is free.)
12. The relation $R$ on $\mathbb{N}$ is $a\,R\,b \iff a \le b$. Is it reflexive, symmetric, transitive?

Pitfalls / Tricks

• Range vs codomain. The codomain is what you declare the output set to be; the range is what actually appears. Always answer the question literally , many MCQs distinguish these.
• A relation from $A$ to $B$ that lists $(a, b)$ does not imply $b\,R\,a$. Ordered pairs in a relation are directed.
• An empty subset of $A \times B$ is a relation too (the empty relation).
• Insight. Every equation linking two variables , say $x^2 + y^2 = 1$ , defines a relation on $\mathbb{R}$. The graph of the equation is the relation viewed as a subset of $\mathbb{R}^2$.