Cartesian Products and Representing Relations

Hello! Last lesson, you counted elements that belonged to at least one of several sets. Now we will make a different kind of set: one whose elements are ordered pairs. This lets us describe not just which objects exist, but which objects are connected. You will construct a Cartesian product, select pairs to form a relation, and show that relation in three ways: as a list of pairs, a mapping diagram, and a directed graph.

---

Every possible pairing: the Cartesian product

Suppose $A=\{p,q\}$ and $B=\{1,2,3\}$. If the first entry must come from $A$ and the second from $B$, the complete set of possibilities is

$$A\times B=\{(p,1),(p,2),(p,3),(q,1),(q,2),(q,3)\}.$$

This is the Cartesian product:

$$A\times B=\{(a,b)\mid a\in A\text{ and }b\in B\}.$$

Unlike an ordinary two-element set, an ordered pair has a designated first and second entry. In general, $(p,1)\ne (1,p)$. Two ordered pairs are equal only when their corresponding entries are equal.

Watch the opening of Khan Academy India’s Cartesian product of sets for the construction and counting idea. The brief final segment shows why reversing the two sets matters.

The grid below is a way to check that none of the possibilities has been missed. Each row fixes one first entry; each column fixes one second entry.

For finite sets, each of the $|A|$ first entries can be paired with each of the $|B|$ second entries. Therefore,

$$|A\times B|=|A||B|.$$

This is a count of possible pairs, not a claim that the sets themselves have been merged. Also, $A\times B$ and $B\times A$ have the same number of pairs but generally contain different pairs. If either set is empty, no complete pair can be made, so its product with the other set is empty.

---

A relation selects some of those pairs

A Cartesian product includes every permitted pairing. A relation from $A$ to $B$ selects whichever of those pairs satisfy a stated condition. Formally, a relation $R$ from $A$ to $B$ is a subset of $A\times B$. When the first and second entries both come from a set $S$, we call it a relation on $S$, with $R\subseteq S\times S$.

Read the definition in Relations and Functions, the Class 11 mathematics exemplar. Stop at its note about arrow diagrams; the subsequent material on functions belongs to a later lesson.

Take $S=\{1,2,3\}$, and let $R$ mean “the first number is a factor of the second.” Testing the nine pairs in $S\times S$ gives

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

For example, $(1,3)\in R$ because $1$ is a factor of $3$, while $(2,3)\notin R$. We can also write $1R3$ to say that $1$ is related to $3$. Notice the distinction between the allowed pairs in $S\times S$ and the selected pairs in $R$: a pair can belong to the product without satisfying the relation.

A reliable way to construct a finite relation is to keep the first entry fixed, check every possible second entry, and then move to the next first entry. The product tells you how many candidate pairs there are—nine here—so it provides an immediate check on whether your list could be complete.

---

A mapping diagram keeps the two roles visible

The same five pairs can be drawn with two copies of $S$: one copy for possible first entries and one for possible second entries. Draw an arrow from the left-hand $a$ to the right-hand $b$ exactly when $(a,b)\in R$.

Watch the mapping-diagram portion of What is a FUNCTION? Using Mapping Diagrams from The Magic Of Math. Use it for the change of representation; the video’s later test for functions is not needed yet.

Here is the mapping diagram for our factor relation:

The arrow from the left-hand $1$ to the right-hand $3$ represents $(1,3)$. There is no arrow from the left-hand $3$ to the right-hand $1$, because $(3,1)\notin R$. A relation is allowed to have several arrows leaving one element, or none; do not add or remove arrows to make the picture look more balanced.

Although both columns happen to contain $S$, they represent different positions in a pair. For a relation from different sets $A$ and $B$, place the elements of $A$ on the left and those of $B$ on the right in the same way.

---

A directed graph uses one copy of the set

When a relation is on $S$, we can instead draw each element of $S$ just once. An arrow from vertex $a$ to vertex $b$ again means $(a,b)\in R$. This is a directed graph, or digraph, of the relation.

Read the diagram discussion in Mathematics LibreTexts’ 6.1: Relations. It explains why a two-column picture is convenient, and why a one-copy directed graph is particularly appropriate when both entries come from the same set.

Our five-pair relation becomes:

An arrow returning to the same vertex is a loop. The loop at $2$, for example, records $(2,2)\in R$. An arrow from $1$ to $2$ does not also supply an arrow from $2$ to $1$: direction records the order of the pair.

Be careful with the word graph. Plotting $(1,2)$ as a point on coordinate axes is another possible picture of a numerical relation. In the directed graph above, $1$ and $2$ are vertices, and $(1,2)$ is represented by an arrow between them. Those pictures encode the same pair in different ways.

---

Choosing and checking a representation

Suppose $A=\{1,2,3\}$, $B=\{2,4\}$, and a pair belongs to $T$ when its first entry is smaller than its second. The six candidates in $A\times B$ can be checked by first entry. The selected pairs are

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

A mapping diagram would have arrows from $1$ to both $2$ and $4$, from $2$ to $4$, and from $3$ to $4$. It would not have an arrow from $2$ to $2$: “smaller than” does not include equality. Because this relation goes from $A$ to a different set $B$, the two-column mapping diagram keeps its roles clearer than a one-set digraph.

Use the representation that answers the question most directly. A roster of pairs makes membership easy to check; a mapping diagram shows which first entries connect to which second entries; and a directed graph displays the connections of a relation on one set without duplicating its elements. In every case, you can recover the relation by recording one ordered pair per arrow.

---

The central distinction is all possible pairs versus selected pairs: $A\times B$ contains every ordered pair with the prescribed entry order, while a relation $R\subseteq A\times B$ contains only pairs meeting its condition. Mapping diagrams and directed graphs change how you display those pairs, not which pairs belong.

Next, you will use directed graphs and ordered pairs to test structural properties of relations, such as whether every element is related to itself and whether reversing an arrow preserves the relation.