Skip to content

The Cartesian Product: Ordered Pairs, Grids and Relations

A × B is the set of ordered pairs (a, b) with a in A and b in B. Worked examples, why |A × B| = |A| · |B|, why order matters, and how relations use it.

By Published 4 min read

Reign Creative LLC makes Discrete Math: Study & Quiz, which this article links to, so we have a commercial interest in it. How we write and check articles.

AI-assisted article. Drafted with AI tools from the sources cited below and checked by automated tests and an AI editorial review. No person has reviewed it yet. How we write and check articles.

Key takeaways

  • A × B is the set of all ordered pairs (a, b) whose first entry comes from A and second entry from B.
  • For finite sets, |A × B| = |A| · |B|, which is the multiplication principle of counting in set form.
  • Order matters: (1, 2) ≠ (2, 1), so A × B and B × A are usually different sets.
  • A × ∅ = ∅ for any set A, because there is no second entry to choose.
  • A relation from A to B is any subset of A × B, and a function is a relation with exactly one pair for each element of A.

Union and intersection combine sets into new sets of the same kind of element. The Cartesian product does something different: it builds a set of pairs, one entry from each set. It is the construction behind coordinates, tables, relations and functions, and it is the set-theory version of the multiplication principle of counting.

Ordered pairs from two sets

For sets A and B, the Cartesian product is

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

the set of all ordered pairs whose first entry is from A and second entry from B. Levin's Discrete Mathematics: An Open Introduction points out that this is nothing new to anyone who has graphed a function: the Cartesian plane is the set of all ordered pairs of real numbers, ℝ × ℝ.

Example. Let A = {1, 2, 3} and B = {x, y}. Then

A × B = {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)}.

Arranged as a grid, with A down the side and B across the top, every cell is one pair:

x y
1 (1, x) (1, y)
2 (2, x) (2, y)
3 (3, x) (3, y)

Counting the pairs

The grid has 3 rows and 2 columns, so 6 cells. In general, for finite sets,

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

Applied Discrete Structures states this rule after an example with A = {1, 2, 3} and B = {4, 5}, noting that it is a good reason for the × symbol. It is the multiplication principle in disguise: choosing a pair means making one choice from A and then one independent choice from B. Two dice, for instance, have {1, …, 6} × {1, …, 6} as their outcomes, 36 ordered pairs in all, which is where the familiar 36 in dice probability comes from.

Products of more sets work the same way. A × B × C is the set of ordered triples (a, b, c), and has |A| · |B| · |C| elements. When all the sets are equal, exponents are used: A² = A × A, A³ = A × A × A, and so on. The set {0, 1}ⁿ is the set of all bit strings of length n, which has 2ⁿ elements, the same count as the power set of an n-element set.

Order matters

An ordered pair is not a set. {1, 2} = {2, 1}, but (1, 2) ≠ (2, 1). Two ordered pairs are equal only when their first entries match and their second entries match.

So A × B and B × A are usually different. With A = {1, 2, 3} and B = {x, y}, A × B contains (1, x) while B × A contains (x, 1), and the two sets share no elements at all. They do have the same size, |A| · |B| = |B| · |A|.

Two edge cases are worth knowing:

  • A × ∅ = ∅. There is no element of ∅ to use as the second entry, so no pairs can be formed. This matches |A| · 0 = 0.
  • A × B = B × A exactly when A = B, or when A or B is empty.

How the product interacts with other operations

Cartesian products distribute over union and intersection:

  • A × (B ∪ C) = (A × B) ∪ (A × C)
  • A × (B ∩ C) = (A × B) ∩ (A × C)

Each is proved by the element-chasing method from the set operations guide: take an arbitrary pair (a, b) and follow the definitions. The product does not distribute the other way around, and (A × B) ∪ (C × D) is generally not a product of two sets at all.

Relations and functions are subsets of products

This is where the Cartesian product does its main work in a discrete math course.

A relation from A to B is any subset of A × B. If A is a set of students and B a set of courses, the relation "is enrolled in" is the set of pairs (student, course) where that student takes that course. A relation on a single set A is a subset of A × A; "is less than" on {1, 2, 3} is {(1, 2), (1, 3), (2, 3)}. The guide to relation properties checks such sets for reflexivity, symmetry and transitivity.

A function f from A to B is a relation in which every a ∈ A appears as a first entry exactly once. Its graph, {(a, f(a)) : a ∈ A}, is a subset of A × B, which is precisely what you draw when you plot a function. Whether a function is one-to-one or onto is a question about how those pairs use B, the subject of injective, surjective and bijective functions.

Where you see it outside mathematics

  • Grids and coordinates. A chessboard's squares are {a, …, h} × {1, …, 8}, 64 ordered pairs.
  • Every combination of options. Three sizes and four colours give 12 product variants, the same count as in permutations versus combinations problems that use the multiplication rule.

Exercises on products of sets

  1. List {a, b} × {1, 2, 3} and {1, 2, 3} × {a, b}. How many pairs are in each, and how many do they share?
  2. How many elements does {0, 1}³ × {x, y} have? (8 · 2 = 16.)
  3. Prove A × (B ∩ C) = (A × B) ∩ (A × C) by element chasing.
  4. Find sets A and B with A × B = B × A and A ≠ B. (One of them must be empty.)

Sets and the functions built from them belong to the sets, functions and countability unit of Discrete Math: Study & Quiz, the fourth in its sequence. It is part of our education app collection, and the discrete math hub lists the rest of the set-theory guides.

Good to know

Frequently asked questions

What is the Cartesian product of two sets?
The set of all ordered pairs whose first entry is from the first set and second entry from the second. For A = {1, 2, 3} and B = {x, y}, A × B = {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)}.
How many elements does A × B have?
|A| times |B| when both are finite. Each of the |A| choices for the first entry can be paired with each of the |B| choices for the second, so a 3-element set and a 2-element set give 6 ordered pairs.
Is A × B equal to B × A?
Usually not. (1, x) is in A × B, but B × A contains (x, 1) instead, and an ordered pair is different from its reverse. The two products have the same number of elements, and they are equal only when A = B or one of the sets is empty.
What is a Cartesian product used for?
It describes every combination of choices: coordinates in the plane (ℝ × ℝ), outcomes of rolling two dice, the squares of a grid such as a chessboard, and pairs of related objects. Relations and functions are defined as subsets of Cartesian products.

Sources

  1. Cartesian Products and Power Sets (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
  2. Sets (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
  3. Cartesian Product (opens in a new tab)Wolfram MathWorld — accessed

About the author

— The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.

We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.

No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.

Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.

Keep reading