Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 38 Β· Relations and Functions

Ordered Pairs and Cartesian Products

Learn ordered pairs, how a pair can be built from sets alone, the Cartesian product A Γ— B, its size, and how to compute it in Python.

Sets have no order, but many things in math do: the point (2, 5) is not the point (5, 2). To talk about relations and functions we need ordered pairs and the set of all of them, the Cartesian product. This is the foundation for the whole chapter.

Ordered pairs

An ordered pair (a, b) has a first component a and a second component b. The defining property is:

Text
(a, b) = (c, d)  if and only if  a = c and b = d

Compare with sets: {1, 2} = {2, 1}, but (1, 2) β‰  (2, 1). Also (3, 3) is allowed, while {3, 3} = {3} has only one element.

Building pairs from sets (optional but beautiful)

Set theory aims to build everything from sets alone, so is there a way to define (a, b) using only sets? Yes. Kazimierz Kuratowski proposed

Text
(a, b) = { {a}, {a, b} }

Let us see why it works. The element tells you which object is first (it is the only singleton in the pair when a β‰  b), and {a, b} adds the second. If a = b the set collapses to {{a}}. One can prove that this definition satisfies the property above, so it is a legitimate model. After that proof nobody thinks about the construction again: we use (a, b) as a primitive idea. It matters because it shows that no new "pair" concept is needed beyond sets.

Python Kuratowski pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Cartesian product

The Cartesian product of sets A and B is the set of all ordered pairs with first component from A and second from B:

Text
A Γ— B = { (a, b) : a ∈ A and b ∈ B }

Example. If A = {1, 2} and B = {x, y, z}, then

Text
A Γ— B = { (1,x), (1,y), (1,z), (2,x), (2,y), (2,z) }

Think of a table with the elements of A as rows and those of B as columns; each cell is one pair.

x y z
1 (1,x) (1,y) (1,z)
2 (2,x) (2,y) (2,z)

Key facts:

  • Size: |A Γ— B| = |A| Β· |B|. Here, 2 Β· 3 = 6.
  • Not commutative: A Γ— B β‰  B Γ— A in general, because (1, x) is a different object from (x, 1). They are equal only if A = B or one of the sets is empty.
  • Empty factor: A Γ— βˆ… = βˆ…, because there is no pair to form.
  • Distributes over union and intersection: A Γ— (B βˆͺ C) = (A Γ— B) βˆͺ (A Γ— C) and A Γ— (B ∩ C) = (A Γ— B) ∩ (A Γ— C).

The best known example is the plane: ℝ Γ— ℝ, also written ℝ², is the set of points (x, y) with x, y ∈ ℝ. This is why a point on a graph is called an "ordered pair of coordinates", and why the system is named after RenΓ© Descartes (Cartesius in Latin).

Python Cartesian product and its size

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Products of more sets, and powers

Longer tuples work the same way. A Γ— B Γ— C is the set of ordered triples (a, b, c), with size |A| Β· |B| Β· |C|. The product of a set with itself is a power: AΒ² = A Γ— A, AΒ³ = A Γ— A Γ— A. A set of binary words of length 8 is {0, 1}⁸, with 2⁸ = 256 elements, one for each byte.

Subsets of a Cartesian product

A subset of A Γ— B is just a set of pairs picked from the table. The next lesson shows that this is exactly what a relation is. For instance, from A = {1, 2, 3} and B = {1, 2, 3}, the set {(1, 1), (1, 2), (2, 3)} is a subset of A Γ— B. Because |A Γ— B| = 9, there are 2⁹ = 512 subsets, each a different way of connecting elements of A to elements of B.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. Which statement is true about ordered pairs?

    This is the defining property of ordered pairs. The pair (3, 3) is allowed.
  2. 2. If |A| = 4 and |B| = 5, how many elements does A Γ— B have?

    |A Γ— B| = |A| Β· |B| = 20.
  3. 3. When is A Γ— B = B Γ— A?

    If A = B the two products are literally the same. If A is empty or B is empty, both products are empty.
  4. 4. How many subsets does {1, 2} Γ— {1, 2, 3} have?

    The product has 2 Β· 3 = 6 elements, so it has 2^6 = 64 subsets.

Summary

  • An ordered pair (a, b) records order: (a, b) = (c, d) iff a = c and b = d.
  • Kuratowski showed (a, b) = {{a}, {a, b}} works, so pairs are definable from sets.
  • A Γ— B is the set of all pairs with first component in A and second in B; |A Γ— B| = |A| Β· |B|.
  • A Γ— B β‰  B Γ— A in general; ℝ Γ— ℝ is the plane.
  • A subset of A Γ— B is a relation from A to B (next lesson).

Next: Relations