What is a Relation?

Connecting Elements

You’ve seen functions. A function connects each input to exactly one output.

But what if we want more flexibility?

A person can be friends with many people
A number can divide many other numbers
A city can be connected to several other cities

This is where relations come in.

What is a Relation?

Remember Cartesian products? If you have sets $A$ and $B$ , then $A \times B$ is all ordered pairs $(a, b)$ .

A relation from $A$ to $B$ is a subset of $A \times B$ .

That’s it. Pick some pairs from $A \times B$ , and you have a relation.

Example: Let $A = \{1, 2, 3\}$ and $B = \{a, b\}$ .

The Cartesian product $A \times B$ has all 6 pairs:

$\{(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)\}$

A relation is any subset of this. For instance:

$R = \{(1, a), (2, b), (3, a)\}$

This relation connects 1 to a, 2 to b, and 3 to a.

Relations on a Single Set

Most often, we study relations from a set to itself.

A binary relation on $A$ is a subset of $A \times A$ .

These are the interesting ones. They describe how elements of a set relate to each other.

Examples

“Less than” on $\{1, 2, 3\}$ :

Which pairs $(a, b)$ satisfy $a < b$ ?

$\{(1, 2), (1, 3), (2, 3)\}$

“Divides” on $\{1, 2, 3, 4, 6\}$ :

Which pairs $(a, b)$ satisfy ” $a$ divides $b$ “?

$a$	divides…
1	1, 2, 3, 4, 6
2	2, 4, 6
3	3, 6
4	4
6	6

So the relation is:

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

“Equality” on any set:

The pairs where both elements are the same:

$\{(a, a) \mid a \in A\}$

On $\{1, 2, 3\}$ , this is $\{(1,1), (2,2), (3,3)\}$ .

Notation

If $R$ is a relation and $(a, b) \in R$ , we write:

$a \mathrel{R} b$

This reads: ” $a$ is related to $b$ ” or ” $a$ R $b$ “.

Examples:

Relation	Notation	Meaning
Less than	$3 < 5$	$(3, 5)$ is in the “less than” relation
Divides	$2 \mid 6$	$(2, 6)$ is in the “divides” relation
Equality	$4 = 4$	$(4, 4)$ is in the “equals” relation

You’ve been using relations all along. Now you know what they really are.

Relations vs Functions

A function is a special kind of relation.

	Relation	Function
Each input can connect to…	Any number of outputs	Exactly one output
$(1, a)$ and $(1, b)$ both in $R$ ?	Allowed	Not allowed

Every function is a relation. But not every relation is a function.

Example: “Is a parent of”

Alice is a parent of Bob
Alice is a parent of Carol

The pairs $(Alice, Bob)$ and $(Alice, Carol)$ are both in the relation.

This is not a function, since Alice maps to two people.

But it’s a perfectly valid relation.

Why Relations Matter

Relations let us describe:

Orderings: less than, divides, subset of
Equivalences: same age as, congruent to, equivalent to
Connections: is friends with, is adjacent to, links to

The next step is understanding what properties a relation can have.