The Cartesian product¶

Level: 101 · for anyone who has written a pair of coordinates

One line: A × B is every ordered pair with its first entry from A and its second from B — so the pair (2, 5) is not the pair (5, 2), A × B is not B × A, and (1, 1) counts.

The definition¶

ℝ² = ℝ × ℝ = {(x, y) | x, y ∈ ℝ}. Read it slowly: the set of all objects of the form (x, y), where x is a real number and y is a real number. That is the coordinate plane, and every point in it is one ordered pair.

Symbol by symbol:

Piece	Say it	What it means
ℝ	"R", or "the reals"	the set of all real numbers, such as −5, 0, 1/3, √2 and π
ℝ²	"R two"	a short name, defined by the rest of the line; the ² counts copies of ℝ, as 3² = 3 × 3 counts copies of 3
=	"is"	here, "is by definition": the line gives one set three names
×	"cross"	the Cartesian product, defined just below
{ … \| … }	"the set of all … such that …"	set-builder notation: the shape of a member left of the bar, the condition it must meet right of it; some books write a colon instead of the bar
(x, y)	"the pair x, y"	an ordered pair: a first entry and a second entry, each in its own place
x, y ∈ ℝ	"x and y are in ℝ"	∈ means "is a member of", and the comma is short for "x ∈ ℝ and y ∈ ℝ", each chosen freely, so x = y is allowed

Replace ℝ with any two sets and the same recipe defines the Cartesian product:

A × B = {(a, b) | a ∈ A, b ∈ B}

The × is not multiplication of numbers. It is an operation on sets, and its output is a set of pairs. To be a member of A × B, an object has to pass two checks: it is a pair, and its first entry comes from A while its second comes from B. The number 5 fails the first check. The triple (1, 2, 3) fails it too; that one lives in ℝ³. The pair (2, i) fails the second, because i is not real.

What the program prints¶

Verified output of cartesian_product.py — regenerated by tools/run_examples.py, never hand-typed.

1. A PAIR IS ORDERED; A SET IS NOT
   (2, 5) == (5, 2)   is False
   {2, 5} == {5, 2}   is True
   (3, 3) has 2 entries;  {3, 3} has 1 member
   Two pairs are equal exactly when both entries match in order.

2. THE PRODUCT, FROM THE DEFINITION
   P = {a, b}   Q = {1, 2, 3}
   P x Q is every (p, q) with p in P and q in Q, laid out as a grid:
   rows are members of P, columns are members of Q.
     P x Q =  (a, 1)   (a, 2)   (a, 3)
              (b, 1)   (b, 2)   (b, 3)
   |P| x |Q| = 2 x 3 = 6;  the grid has 6 cells.

3. SWAP THE FACTORS AND YOU GET A DIFFERENT SET
     Q x P =  (1, a)   (1, b)
              (2, a)   (2, b)
              (3, a)   (3, b)
   P x Q == Q x P            is False
   members they share:       []
   ('a', 1) in P x Q         is True
   ('a', 1) in Q x P         is False
   'a' is not in Q, so it cannot be a first entry of a Q x P pair.
   Same size, and not one member in common. The product is not
   commutative: which set feeds which slot is part of the definition.

4. A SET TIMES ITSELF, AND THE PAIRS WITH A REPEATED ENTRY
   S = {0, 1}
     S x S =  (0, 0)   (0, 1)
              (1, 0)   (1, 1)
   (0, 0) in S x S           is True
   (1, 1) in S x S           is True
   |S x S| = 4, not 2. Dropping the repeats is the usual
   mistake: nothing in the definition says the two entries differ.

5. THE COUNT IS ALWAYS THE PRODUCT OF THE SIZES
     |A|  |B|  |A x B|  |A| x |B|
       0    0        0          0
       0    1        0          0
       0    3        0          0
       0    5        0          0
       1    0        0          0
       1    1        1          1
       1    3        3          3
       1    5        5          5
       2    0        0          0
       2    1        2          2
       2    3        6          6
       2    5       10         10
       3    0        0          0
       3    1        3          3
       3    3        9          9
       3    5       15         15
   Including the empty set: a product with an empty factor is empty,
   because there is nothing to put in that slot.

6. THE SAME THING PYTHON CALLS itertools.product
   set(product(P, Q)) == P x Q   is True
   The library and the definition agree, pair for pair.

A pair is not a set¶

Section 1 asks Python the question directly. (2, 5) == (5, 2) is False; {2, 5} == {5, 2} is True. A set only knows who its members are. A pair also knows which came first, and that is the whole difference. The rule for equality of pairs is

(a, b) = (c, d) exactly when a = c and b = d,

and everything else on this page follows from it. If (2, 5) were equal to (5, 2), the rule would force 2 = 5.

The same rule says a pair can repeat its entry. (3, 3) has two entries, both equal to 3; the set {3, 3} collapses to {3} and has one member. Section 4 checks the consequence: (1, 1) is a member of {0, 1} × {0, 1}, and the product has 4 members, not 2. Leaving out the repeated pairs is the most common mistake in listing a product, and nothing in the definition licenses it.

(If you have seen a pair defined as the set {{a}, {a, b}}, that is the Kuratowski construction, and its only purpose is to show that a pair can be built out of sets. The one-element inner set marks which entry is first. In practice nobody unpacks it; the equality rule above is all that is ever used.)

Which set feeds which slot¶

Section 2 lays out P × Q for P = {a, b} and Q = {1, 2, 3} as a grid: one row per member of P, one column per member of Q, one pair per cell. The grid is worth keeping in your head, because it makes the count obvious. Two rows of three cells is six pairs, and in general

|A × B| = |A| · |B|.

Section 5 checks that on every combination of sizes from 0 to 3 against 0 to 5, including the empty set. A × ∅ is empty for a reason the grid shows: no columns, so no cells.

Section 3 swaps the factors. Q × P is the transposed grid, three rows of two, and it has the same six-cell count. But compare the members. (a, 1) is in P × Q. Is it in Q × P? Its first entry would have to come from Q, and a is not in Q. In fact the two sets share no member at all: the program takes their intersection and gets the empty set.

That is what it means to say the Cartesian product is not commutative. It is not a technicality about notation. The definition names a first set and a second set, and the pairs it produces carry that order in them. A × B = B × A holds only when A = B, or when one of them is empty and both products are the empty set.

Back to the plane¶

With finite sets the product can be listed. ℝ × ℝ cannot, because ℝ itself cannot be listed. Countable sets is the page on what listed means and which sets allow it. ℝ² is no smaller than ℝ, since the pairs (x, 0) alone are a copy of the line.

That copy is the x-axis, and it is worth being precise about it. Is ℝ a subset of ℝ²? Strictly, no: 3 is a real number and 3 is not a pair, so 3 ∉ ℝ². What is true is that the map x ↦ (x, 0) puts ℝ inside ℝ² as the x-axis, and everyone speaks as if the two were the same. That is an identification, not equality of sets. The same distinction separates a member of ℝ² from a subset of it: the point (1, 0) is a member; the unit circle {(x, y) | x² + y² = 1} is a subset, a set of points, and never a single element.

Run it yourself¶

From the root of your clone of this repository:

python3 04_Sets/cartesian_product/examples/cartesian_product.py

Auf Deutsch: Stichwörter¶

A × B ist die Menge der geordneten Paare; die Reihenfolge wird aus Mengen gebaut, die keine kennen, und |A × B| = |A|·|B| ist ein Gitter.

Stichwörter: kartesisches Produkt, geordnetes Paar (Kuratowski), Koordinatenebene ℝ², Gitter, Tupel, Zählregel.