Cartesian Products of Sets

Definition

Given two non-empty sets $P$ and $Q$, the Cartesian product $P \times Q$ is the set of all ordered pairs $(p, q)$ where $p$ belongs to $P$ and $q$ belongs to $Q$. In symbols:

If either $P$ or $Q$ is the empty set $\phi$, then $P \times Q$ is also the empty set: $P \times Q = \phi$.

Intuition

Think of a menu: if $P$ is a set of 2 drinks (tea, coffee) and $Q$ is a set of 3 snacks (biscuit, cake, sandwich), then $P \times Q$ lists every possible drink–snack combination. You get $2 \times 3 = 6$ distinct combos, each written as an ordered pair like (tea, biscuit). The order is fixed — (tea, biscuit) is different from (biscuit, tea), which wouldn't even be in the set because biscuit isn't a drink.

Tiny Concrete Example …

Fig 2.1 is a visual representation of the Cartesian product of two small sets. The grid has two columns, labelled red and blue at the bottom, and three rows, labelled b, c, s up the left side. At each of the six intersections — where a column and a row meet — there is a dot. The slate frame around the grid gives it the look of a lattice or a coordinate system.

The physical idea is straightforward: every possible pairing of a colour from the set $A = \{\text{red}, \text{blue}\}$ with an object from the set $B = \{b, c, s\}$ (bag, coat, shirt) is represented by exactly one dot. The dot at the intersection of the red column and the b row, for instance, corresponds to the ordered pair (red, b). The grid makes it obvious that there are $2 \times 3 = 6$ such pairs, and that the order matters — (red, b) is a different dot from (b, red), which would require a different grid entirely.

This figure is the textbook’s concrete introduction to the definition of the Cartesian product. The key formula it leads to is:

Here $A$ and $B$ are any two non-empty sets. The symbol $\times$ is read “cross” — it does not mean multiplication of numbers, but the formation of all ordered pairs. The notation $(a, b)$ is an ordered pair: the first element comes from $A$, the second from $B$. Because the pair is ordered, $(a, b)$ is different from $(b, a)$ unless $a = b$.

From the grid, the textbook immediately extracts a counting rule: if $n(A) = p$ and $n(B) = q$, then the number of elements in $A \times B$ is $pq$. In the figure, $p = 2$ and $q = 3$, so $n(A \times B) = 6$. This is not a coincidence — it is a direct consequence of the fact that each of the $p$ choices for the first coordinate can be paired with each of the $q$ choices for the second, giving a rectangular array of dots. …

Fig 2.2 is a visual representation of the Cartesian product $A \times B$, where $A = \{\text{DL}, \text{MP}, \text{KA}\}$ and $B = \{01, 02, 03\}$. The figure is a 3×3 grid. Along the bottom (horizontal axis) are the three column labels: DL, MP, KA — these are the elements of set $A$, the states. Along the left side (vertical axis) are the three row labels: 01, 02, 03, listed from bottom to top — these are the elements of set $B$, the licence plate codes. At each of the nine intersections of a row and a column, an indigo dot is placed. The entire grid is enclosed by slate-coloured frame lines.

The physical idea is straightforward: every possible ordered pair (state, code) is represented by exactly one point in this grid. The dot at the intersection of the row labelled 02 and the column labelled MP, for example, corresponds to the ordered pair (MP, 02). Because the grid has 3 rows and 3 columns, there are $3 \times 3 = 9$ such dots, matching the 9 ordered pairs listed in the textbook.

The key formula this figure illustrates is the cardinality of a Cartesian product:

Here $n(A)$ is the number of elements in set $A$, and $n(B)$ is the number of elements in set $B$. In this case, $n(A) = 3$ and $n(B) = 3$, so $n(A \times B) = 3 \times 3 = 9$.

The figure also drives home a crucial point about ordered pairs: the pair (DL, 01) is not the same as (01, DL). In the grid, (DL, 01) is the dot at the intersection of column DL and row 01. The pair (01, DL) would require a different grid — one where the set of first elements is $\{01, 02, 03\}$ and the set of second elements is $\{\text{DL}, \text{MP}, \text{KA}\}$ — and would occupy a different position. The grid layout makes this order-dependence visually obvious: the row and column labels are not interchangeable.

Fig. 2.3 is a visual representation of the Cartesian product $A \times B$ for the specific sets $A = \{a_1, a_2\}$ and $B = \{b_1, b_2, b_3, b_4\}$. The figure is a simple grid: a 2‑column by 4‑row lattice. The two columns are labelled at the bottom with $a_1$ and $a_2$ (the elements of $A$). The four rows are labelled on the left with $b_1, b_2, b_3, b_4$, listed from bottom to top. At each of the $2 \times 4 = 8$ intersections of a column and a row, a dot is placed. Each dot corresponds to exactly one ordered pair: the column gives the first coordinate (from $A$), and the row gives the second coordinate (from $B$).

The physical idea is that the Cartesian product $A \times B$ can be thought of as a grid of points — a lattice — in a plane. If $A$ and $B$ are subsets of the real numbers, then each ordered pair $(a_i, b_j)$ is the coordinate of a point in the plane. The figure makes it clear that the pair $(a_1, b_2)$ is a different point from $(a_2, b_1)$; the order matters. The grid layout also makes it obvious that the total number of ordered pairs is the product of the number of elements in $A$ and the number in $B$.

Here $n(A) = 2$, $n(B) = 4$, so $n(A \times B) = 2 \times 4 = 8$. This is the central counting formula the textbook develops with this figure. The figure itself is a concrete, visual proof of that formula: you can count the dots.