Table of Contents
In a previous post we studied sets: we learned to define them, relate them through inclusion and equality, and operate on them (union, intersection, difference, complement). Now, before tackling topics such as relations and functions in future posts, we need two essential building blocks: ordered pairs and the Cartesian product.
Why? Because sets, on their own, cannot handle one fundamental concept: order.
Why sets are not enough
Recall that a set is determined solely by its elements, regardless of the order in which they are written or how many times they are listed. This is a direct consequence of the Axiom of Extensionality:
\[ \{3, 5\} = \{5, 3\} \]
Axiom of Extensionality. Two sets are equal if and only if they have exactly the same elements. The order in which they are written and any repetitions are irrelevant: \( \{1, 2, 3\} = \{3, 1, 2\} = \{1, 1, 2, 3\} \). The only thing that defines a set is which elements it contains.
That works fine when all we care about is which elements are present, but it becomes a serious limitation whenever order matters.
Example. Consider these everyday situations:
| Situation | Pair 1 | Pair 2 | Are they the same? |
|---|---|---|---|
| Coordinates on a map | (latitude, longitude) | (longitude, latitude) | ✗ — they lead to different places |
| Temperature (min, max) | (5°C, 30°C) = “from 5 to 30 degrees” | (30°C, 5°C) = “from 30 to 5 degrees” | ✗ — different ranges |
| Family relation | (Juan, María) = “Juan is María’s son” | (María, Juan) = “María is Juan’s daughter” | ✗ — different relations |
In all these cases, swapping the order changes the meaning. But if we use ordinary sets:
\[ \{\text{Juan}, \text{María}\} = \{\text{María}, \text{Juan}\} \]
The set cannot tell who comes first! We need a mathematical structure where order is an essential part of the object’s identity. That structure is the ordered pair.
Ordered pair
Intuitive concept
An ordered pair is a way of pairing two elements where position counts — which one comes first and which comes second. It is written using parentheses:
\[ (a, b) \]
where:
- \( a \) is the first component (or first coordinate)
- \( b \) is the second component (or second coordinate)
Key difference from sets:
Set \( \{a, b\} \) Ordered pair \( (a, b) \) Does order matter? No: \( \{a, b\} = \{b, a\} \) Yes: \( (a, b) \neq (b, a) \) (if \( a \neq b \)) Are repeated elements allowed? No: \( \{a, a\} = \{a\} \) Yes: \( (a, a) \) has two components Notation Braces \( \{\ \} \) Parentheses \( (\ ) \)
Examples:
- \( (2, 5) \) — first component: 2, second component: 5.
- \( (5, 2) \) — first component: 5, second component: 2.
- \( (2, 5) \neq (5, 2) \) because the components sit in different positions.
- \( (3, 3) \) — both components are equal, but the pair still has two distinct “slots.”
- \( ((1, 3), 4) \) — an ordered pair whose first component is another ordered pair \( (1, 3) \) and whose second component is \( 4 \).
Fundamental property (equality of ordered pairs)
The defining characteristic of an ordered pair is its equality criterion:
Definition. Two ordered pairs are equal if and only if their corresponding components are equal:
\[ (a, b) = (c, d) \iff a = c \wedge b = d \]
In other words, equality is checked position by position: first components must match, and second components must match — if either fails, the pairs are different.
Connection with logic: Notice that equality of pairs uses a conjunction (\( \wedge \)): both equalities are required at once. If either one fails, the pairs are different.
Example 1. Find the values of \( x \) and \( y \) such that:
\[ (x + 1,\ y – 2) = (3,\ 7) \]
By the fundamental property:
\[ (x + 1,\ y – 2) = (3,\ 7) \iff \begin{cases} x + 1 = 3 \\ y – 2 = 7 \end{cases} \iff \begin{cases} x = 2 \\ y = 9 \end{cases} \]
Example 2. Find \( x \) and \( y \) such that:
\[ (x^2,\ 9y – 1) = (6y – x,\ x^3) \]
Applying the fundamental property:
\[ x^2 = 6y – x \implies x^2 + x = 6y \implies x(x + 1) = 6y \quad \cdots(1) \]
\[ 9y – 1 = x^3 \implies x^3 + 1 = 9y \implies (x+1)(x^2 – x + 1) = 9y \quad \cdots(2) \]
Dividing (1) by (2): \( \dfrac{x}{x^2 – x + 1} = \dfrac{6}{9} = \dfrac{2}{3} \)
\[ 3x = 2(x^2 – x + 1) \implies 2x^2 – 5x + 2 = 0 \implies x_1 = 2 \text{ or } x_2 = \tfrac{1}{2} \]
Substituting into (1): \( y_1 = 1 \) or \( y_2 = \tfrac{1}{8} \)
\[ \therefore S = \{(2, 1),\ (\tfrac{1}{2}, \tfrac{1}{8})\} \]
Formal definition: the Kuratowski construction
So far we have used ordered pairs intuitively. But in axiomatic set theory (ZFC), the only objects that exist are sets. The challenge is: how do we encode “order” using only sets, where order is by definition irrelevant?
Note. ZFC (Zermelo-Fraenkel with the Axiom of Choice) is the formal set theory that, through its 9 axioms, corrects the paradoxes of naïve set theory (such as Russell’s Paradox) — mentioned, though not developed in depth, together with those axioms in the post The Origins of Set Theory. Within ZFC, every mathematical concept — including the ordered pair — must be constructed exclusively from sets and the membership relation (\( \in \)).
In 1921, the Polish mathematician Kazimierz Kuratowski proposed an elegant solution:
Kuratowski’s definition. The ordered pair \( (a, b) \) is defined as:
\[ (a, b) = \{\{a\}, \{a, b\}\} \]
At first glance this looks artificial, but the idea is ingenious: the element \( a \) appears in both subsets (in \( \{a\} \) and in \( \{a, b\} \)), while \( b \) appears only in the subset with the larger cardinality (\( \{a, b\} \), when \( a \neq b \)). This internal asymmetry encodes the order.
Example. If \( a = 1 \) and \( b = 2 \):
\[ (1, 2) = \{\{1\}, \{1, 2\}\} \] \[ (2, 1) = \{\{2\}, \{2, 1\}\} = \{\{2\}, \{1, 2\}\} \]
Clearly \( \{\{1\}, \{1, 2\}\} \neq \{\{2\}, \{1, 2\}\} \) because \( \{1\} \neq \{2\} \). ✓
Historical note. Before Kuratowski, other mathematicians proposed alternative definitions:
Author Year Definition Remark Norbert Wiener 1914 \( (a,b) = \{\{\{a\}, \emptyset\}, \{\{b\}\}\} \) Correct but complex Felix Hausdorff 1914 \( (a,b) = \{\{a, 1\}, \{b, 2\}\} \) Requires 1 and 2 to be defined first — risk of circularity Kuratowski 1921 \( (a,b) = \{\{a\}, \{a, b\}\} \) Current standard — elegant and minimal Kuratowski’s definition prevailed for its simplicity: it uses only the Pairing Axiom and requires no prior concepts such as the natural numbers.
Existence of the ordered pair in ZFC
Why can we be sure that \( \{\{a\}, \{a, b\}\} \) is a legitimate set? Because its existence follows directly from the axioms of ZFC:
- Pairing Axiom (first use): This axiom says that given any two objects, there exists the set containing both of them. Applying it to \( a \) and \( a \), we get \( \{a, a\} = \{a\} \) (a singleton). Applying it to \( a \) and \( b \), we get \( \{a, b\} \) (the unordered pair).
- Pairing Axiom (second use): Now we apply the same axiom to the sets just created: taking \( \{a\} \) and \( \{a, b\} \) as the two objects, the axiom guarantees the existence of \( \{\{a\}, \{a, b\}\} \) — which is precisely Kuratowski’s ordered pair.
We can also locate the ordered pair within the hierarchy of sets:
- Since \( a \in A \) and \( b \in B \), both belong to \( A \cup B \).
- Then the sets \( \{a\} \) and \( \{a, b\} \) are subsets of \( A \cup B \).
- Being subsets of \( A \cup B \), they are elements of its power set: \( \{a\} \in \mathcal{P}(A \cup B) \) and \( \{a, b\} \in \mathcal{P}(A \cup B) \).
- Therefore, the pair \( (a, b) = \{\{a\}, \{a, b\}\} \), being a set whose elements live in \( \mathcal{P}(A \cup B) \), is in turn a subset of \( \mathcal{P}(A \cup B) \), and hence an element of \( \mathcal{P}(\mathcal{P}(A \cup B)) \).
In summary:
\[ (a, b) \in \mathcal{P}(\mathcal{P}(A \cup B)) \]
Concrete example. If \( A = \{1\} \) and \( B = \{2\} \):
- \( A \cup B = \{1, 2\} \)
- \( \mathcal{P}(A \cup B) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\} \)
- Notice that \( \{1\} \) and \( \{1, 2\} \) are both in there ✓
- \( (1, 2) = \{\{1\}, \{1, 2\}\} \in \mathcal{P}(\mathcal{P}(A \cup B)) \) ✓
This confirms that the ordered pair is a legitimate set within the ZFC hierarchy.
Reminder. \( \mathcal{P}(X) \) is the power set of \( X \): the set of all subsets of \( X \). If you need to review this concept, see the post on families of sets.
Proof of the fundamental property using Kuratowski
The real test that Kuratowski’s definition works is that it allows us to prove the fundamental property \( (a, b) = (c, d) \iff a = c \wedge b = d \). The more important direction — the one that justifies the entire construction — is showing that if two Kuratowski pairs are equal, their components must coincide.
Direction \( (\Rightarrow) \): Suppose \( (a, b) = (c, d) \). By Kuratowski’s definition, this means:
\[ \{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\} \]
We must show that \( a = c \) and \( b = d \). We analyze two cases:
Case 1: \( a = b \). Then \( \{a, b\} = \{a, a\} = \{a\} \), so the left-hand side simplifies:
\[ \{\{a\}, \{a\}\} = \{\{a\}\} = \{\{c\}, \{c, d\}\} \]
For a one-element set to equal another, the other must also have exactly one element. This forces \( \{c\} = \{c, d\} \), which happens only when \( c = d \). Also, since \( \{a\} = \{c\} \), we conclude \( a = c \). By transitivity: \( b = a = c = d \). ✓
Case 2: \( a \neq b \). Then \( \{a\} \) has one element and \( \{a, b\} \) has two, so \( \{a\} \neq \{a, b\} \) and the left-hand side has two distinct elements. We reason as follows:
- \( \{a\} \) is an element of \( \{\{c\}, \{c, d\}\} \), so either \( \{a\} = \{c\} \) or \( \{a\} = \{c, d\} \).
- If \( \{a\} = \{c, d\} \), then \( c = d = a \), and the right-hand side reduces to \( \{\{a\}\} \) (one element), but the left-hand side has two distinct elements — contradiction.
- Therefore \( \{a\} = \{c\} \), giving \( a = c \).
- It remains that \( \{a, b\} = \{c, d\} = \{a, d\} \). Since \( b \neq a \), the element different from \( a \) in both sets must coincide: \( b = d \). ✓
In both cases we conclude: \( a = c \wedge b = d \). ∎
Direction \( (\Leftarrow) \): This direction is immediate. If \( a = c \) and \( b = d \), substituting directly shows \( \{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\} \), i.e., \( (a, b) = (c, d) \). ✓
Reflection. In everyday mathematical practice, nobody thinks of an ordered pair as \( \{\{a\}, \{a, b\}\} \). We use \( (a, b) \) intuitively. Kuratowski’s definition is a technical foundation that guarantees the concept is consistent within ZFC — a “construction trick” that, once verified, we can set aside and work directly with the fundamental property.
Cartesian product
One major application is plotting graphs in the Cartesian plane. We are now ready to build a very important concept: the Cartesian product. This operation takes two sets and produces a new set made up of all possible ordered-pair combinations between them.
Definition
Given two sets \( A \) and \( B \), the Cartesian product of \( A \) and \( B \) is the set of all ordered pairs \( (a, b) \) such that \( a \in A \) and \( b \in B \):
\[ A \times B = \{(a, b) \mid a \in A \wedge b \in B\} \]
Read as “\( A \) cross \( B \)” or “\( A \) times \( B \).”
That is, \( (a, b) \in A \times B \) if and only if \( a \in A \) and \( b \in B \).
Conversely, \( (a, b) \notin A \times B \) if and only if \( a \notin A \) or \( b \notin B \).
Connection with logic: Notice that membership in the Cartesian product uses a conjunction “and”: both coordinates must satisfy their condition. By contrast, the negation becomes a disjunction “or”: it is enough for one coordinate to fail.
Is \( A \times B \) a legitimate set in ZFC? Yes. We already showed that every pair \( (a, b) \) lives inside \( \mathcal{P}(\mathcal{P}(A \cup B)) \). So \( A \times B \) is obtained by filtering that large set down to just the elements that are ordered pairs with \( a \in A \) and \( b \in B \). This “filtering” is exactly what the Axiom of Separation (also called the Axiom of Restricted Comprehension) allows:
Note. The Axiom of Separation says that, given an already-existing set \( C \) and a property \( P(x) \), we can form the subset of elements of \( C \) satisfying \( P \). Unlike naïve comprehension (which caused Russell’s Paradox), here we always start from a pre-existing set — never from the entire universe.
Applying this axiom with \( C = \mathcal{P}(\mathcal{P}(A \cup B)) \) and the property “being a pair \( (a, b) \) with \( a \in A \) and \( b \in B \)”:
\[ A \times B = \{x \in \mathcal{P}(\mathcal{P}(A \cup B)) \mid \exists, a \in A,\ \exists, b \in B : x = (a, b)\} \]
That is, \( A \times B \) is not created “from nothing” — it is extracted as a subset of a set we already know exists.
When \( A = B \), the product \( A \times A \) is abbreviated as \( A^2 \).
Examples
Example 1. Let \( A = \{1, 2\} \) and \( B = \{a, b, c\} \). Find \( A \times B \) and \( B \times A \).
\[ A \times B = \{(1, a),\ (1, b),\ (1, c),\ (2, a),\ (2, b),\ (2, c)\} \] \[ B \times A = \{(a, 1),\ (a, 2),\ (b, 1),\ (b, 2),\ (c, 1),\ (c, 2)\} \]
Notice that \( A \times B \neq B \times A \): the pairs \( (1, a) \) and \( (a, 1) \) are distinct objects.
Example 2. Let \( A = \{-1, 0, 1\} \) and \( B = \{1, 2\} \). Find \( (A – B) \times (A \cap B) \).
First: \( A – B = \{-1, 0\} \) and \( A \cap B = \{1\} \).
\[ (A – B) \times (A \cap B) = \{-1, 0\} \times \{1\} = \{(-1, 1),\ (0, 1)\} \]
Cardinality of the Cartesian product
For finite sets, the number of elements in the Cartesian product is simply the product of the number of elements in each set:
\[ n(A \times B) = n(A) \cdot n(B) \]
Why? For each of the \( n(A) \) possible first components, there are \( n(B) \) choices for the second. By the multiplication principle of combinatorics, the total is \( n(A) \cdot n(B) \).
Example. If \( A = \{1, 2\} \) and \( B = \{a, b, c\} \):
\[ n(A \times B) = 2 \cdot 3 = 6 \quad \checkmark \]
Note on infinite sets. The cardinality of products of infinite sets has surprising behavior. For example, \( \mathbb{N} \times \mathbb{N} \) has the same cardinality as \( \mathbb{N} \) (both are countable: \( \aleph_0 \)), and \( \mathbb{R} \times \mathbb{R} \) has the same cardinality as \( \mathbb{R} \). The “plane” has exactly as many points as the “line”!
Graphical representations of the Cartesian product
There are four main ways to visualize a Cartesian product, each highlighting a different aspect.
Tree diagram
A tree diagram shows the Cartesian product as a branching process: from each element of the first set, branches extend to every element of the second set.
Example. \( A = \{1, 2\} \), \( B = \{a, b, c\} \):1abc→ (1, a)→ (1, b)→ (1, c)2abc→ (2, a)→ (2, b)→ (2, c):
Pedagogical advantage: The tree diagram makes it visually clear why \( n(A \times B) = n(A) \cdot n(B) \): each branch at the first level spawns as many sub-branches as there are elements in \( B \).
Double-entry table
We arrange the elements of \( A \) along the rows and those of \( B \) along the columns. Each cell contains the corresponding ordered pair:
| \( A \times B \) | a | b | c |
|---|---|---|---|
| 1 | \( (1, a) \) | \( (1, b) \) | \( (1, c) \) |
| 2 | \( (2, a) \) | \( (2, b) \) | \( (2, c) \) |
Pedagogical advantage: The table is exhaustive — it makes it impossible to forget any pair. It also prepares the student for the concept of a matrix, which is fundamental in linear algebra.
Arrow diagram (sagittal diagram)
Two ovals are drawn (as in a Venn diagram): one for \( A \) and one for \( B \). Arrows are then drawn from each element of \( A \) to each element of \( B \):
In the complete Cartesian product, every element of \( A \) sends an arrow to every element of \( B \). When we study binary relations, we will see that a relation is a subset of these arrows — not necessarily all of them.
Pedagogical advantage: The arrow diagram is direct preparation for understanding functions and relations: the concepts of domain, codomain, and image are visualized naturally.
Cartesian plane representation
When \( A \) and \( B \) are subsets of the real numbers, the Cartesian product can be represented as points in a plane. The elements of \( A \) are placed on the horizontal axis (abscissas) and those of \( B \) on the vertical axis (ordinates).
Example. If \( A = \{1, 2, 3, 4\} \) and \( B = \{1, 2\} \), then \( A \times B \) produces 8 points in the plane, since \( n(A \times B) = 4 \times 2 = 8 \).
The Cartesian plane \( \mathbb{R}^2 \). When \( A = B = \mathbb{R} \) (the real numbers), the product \( \mathbb{R} \times \mathbb{R} = \mathbb{R}^2 \) yields the complete Cartesian plane — the two-dimensional space where functions, equations, and geometric figures are graphed. René Descartes (17th century) was the one who unified geometry and algebra using this representation, which is why the product bears his name: Cartesian.
Summary of representations
| Representation | Best for… | Prepares for… |
|---|---|---|
| Tree diagram | Seeing the combinatorial logic (branching) | Multiplication principle, probability |
| Double-entry table | Ensuring exhaustiveness (no pair left out) | Matrices, linear algebra |
| Arrow diagram | Visualizing connections between sets | Relations, functions, domain/image |
| Cartesian plane | Numerical sets, geometry | Graphing functions, calculus |
Diagonal of a set
Given a set \( A \), the diagonal of \( A \times A \) is the subset formed by all pairs whose two components are equal:
\[ D(A) = \{(a, b) \in A \times A \mid a = b\} = \{(a, a) \mid a \in A\} \]
Example. If \( A = \{1, 2, 3\} \):
\[ A^2 = \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\} \] \[ D(A) = \{(1,1), (2,2), (3,3)\} \]
It is called the “diagonal” because, when these pairs are plotted in the Cartesian plane, the points of \( D(A) \) form a line at 45 degrees running from corner to corner — like the diagonal of a square.
Properties of the Cartesian product
The Cartesian product shares the “\( \times \)” symbol with multiplication of numbers, but its algebraic behavior is very different. In this section we study the properties it satisfies — and those it does not.
Non-commutativity
Unlike multiplication of numbers (\( 3 \times 5 = 5 \times 3 \)), the Cartesian product is not commutative:
\[ A \neq B \implies A \times B \neq B \times A \]
Why? Because the pairs in \( A \times B \) have the form \( (a, b) \), while those in \( B \times A \) have the form \( (b, a) \). Since \( (a, b) \neq (b, a) \) when \( a \neq b \), the two sets are different.
Exceptions. The equality \( A \times B = B \times A \) holds in only two cases:
- \( A = B \) (trivially, it is the same product)
- \( A = \emptyset \) or \( B = \emptyset \) (both sides give \( \emptyset \))
The empty set as an absorbing element
The empty set “absorbs” any Cartesian product:
\[ A \times \emptyset = \emptyset \times A = \emptyset \]
Proof. For a pair \( (a, b) \in A \times \emptyset \) to exist, both conditions must hold: \( a \in A \) and \( b \in \emptyset \). But the empty set has no elements, so no such \( b \) exists. Regardless of whether \( a \in A \), there is no \( b \) available to form the pair. Therefore the product is empty. ∎
Analogy. If you have a wardrobe with 5 shirts but 0 pairs of trousers, you can put together \( 5 \times 0 = 0 \) outfits. No matter how many shirts you have: without trousers, no combination is possible.
Distributive properties
The Cartesian product distributes over union, intersection, and difference. These properties are fundamental tools for manipulating expressions involving Cartesian products.
| Operation | Distributive property |
|---|---|
| Union | \( A \times (B \cup C) = (A \times B) \cup (A \times C) \) |
| Intersection | \( A \times (B \cap C) = (A \times B) \cap (A \times C) \) |
| Difference | \( A \times (B – C) = (A \times B) – (A \times C) \) |
These properties also hold when distributing from the left:
\[ (A \cup B) \times C = (A \times C) \cup (B \times C) \] \[ (A \cap B) \times C = (A \times C) \cap (B \times C) \] \[ (A – B) \times C = (A \times C) – (B \times C) \]
In the proofs below we make use of propositional logic properties studied in a previous post.
Proof of distributivity over union
\( A \times (B \cup C) = (A \times B) \cup (A \times C) \)
Like every set equality, this is proved by double inclusion.
(a) \( A \times (B \cup C) \subseteq (A \times B) \cup (A \times C) \):
- Let \( (x, y) \in A \times (B \cup C) \) — hypothesis
- \( \implies x \in A \wedge y \in (B \cup C) \) — def. of Cartesian product
- \( \implies x \in A \wedge (y \in B \vee y \in C) \) — def. of \( \cup \)
- \( \implies (x \in A \wedge y \in B) \vee (x \in A \wedge y \in C) \) — distributivity of \( \wedge \) over \( \vee \)
- \( \implies (x, y) \in (A \times B) \vee (x, y) \in (A \times C) \) — def. of Cartesian product
- \( \implies (x, y) \in (A \times B) \cup (A \times C) \) — def. of \( \cup \)
- \( \therefore A \times (B \cup C) \subseteq (A \times B) \cup (A \times C) \) — from (1) and (6)
(b) \( (A \times B) \cup (A \times C) \subseteq A \times (B \cup C) \):
- Let \( (x, y) \in (A \times B) \cup (A \times C) \) — hypothesis
- \( \implies (x, y) \in (A \times B) \vee (x, y) \in (A \times C) \) — def. of \( \cup \)
- \( \implies (x \in A \wedge y \in B) \vee (x \in A \wedge y \in C) \) — def. of Cartesian product
- \( \implies x \in A \wedge (y \in B \vee y \in C) \) — factoring \( \wedge \) over \( \vee \)
- \( \implies x \in A \wedge y \in (B \cup C) \) — def. of \( \cup \)
- \( \implies (x, y) \in A \times (B \cup C) \) — def. of Cartesian product
- \( \therefore (A \times B) \cup (A \times C) \subseteq A \times (B \cup C) \) — from (1) and (6)
From (a) and (b): \( A \times (B \cup C) = (A \times B) \cup (A \times C) \). ∎
Proof of distributivity over intersection
\( (A \cap B) \times C = (A \times C) \cap (B \times C) \)
(a) \( (A \cap B) \times C \subseteq (A \times C) \cap (B \times C) \):
- Let \( (x, y) \in (A \cap B) \times C \) — hypothesis
- \( \implies x \in (A \cap B) \wedge y \in C \) — def. of Cartesian product
- \( \implies (x \in A \wedge x \in B) \wedge y \in C \) — def. of \( \cap \)
- \( \implies (x \in A \wedge y \in C) \wedge (x \in B \wedge y \in C) \) — regrouping (\( \wedge \) is associative and commutative)
- \( \implies (x, y) \in (A \times C) \wedge (x, y) \in (B \times C) \) — def. of Cartesian product
- \( \implies (x, y) \in (A \times C) \cap (B \times C) \) — def. of \( \cap \)
- \( \therefore (A \cap B) \times C \subseteq (A \times C) \cap (B \times C) \) — from (1) and (6)
(b) \( (A \times C) \cap (B \times C) \subseteq (A \cap B) \times C \):
- Let \( (x, y) \in (A \times C) \cap (B \times C) \) — hypothesis
- \( \implies (x, y) \in (A \times C) \wedge (x, y) \in (B \times C) \) — def. of \( \cap \)
- \( \implies (x \in A \wedge y \in C) \wedge (x \in B \wedge y \in C) \) — def. of Cartesian product
- \( \implies (x \in A \wedge x \in B) \wedge y \in C \) — regrouping
- \( \implies x \in (A \cap B) \wedge y \in C \) — def. of \( \cap \)
- \( \implies (x, y) \in (A \cap B) \times C \) — def. of Cartesian product
- \( \therefore (A \times C) \cap (B \times C) \subseteq (A \cap B) \times C \) — from (1) and (6)
From (a) and (b): \( (A \cap B) \times C = (A \times C) \cap (B \times C) \). ∎
Proof of distributivity over difference
\( A \times (B – C) = (A \times B) – (A \times C) \)
- \( (x, y) \in A \times (B – C) \)
- \( \iff x \in A \wedge y \in (B – C) \) — def. of Cartesian product
- \( \iff x \in A \wedge (y \in B \wedge y \notin C) \) — def. of difference
- \( \iff (x \in A \wedge y \in B) \wedge (y \notin C) \) — regrouping
- \( \iff (x \in A \wedge y \in B) \wedge \neg(x \in A \wedge y \in C) \) — since \( x \in A \) already holds, \( y \notin C \) negates the second condition
- \( \iff (x, y) \in (A \times B) \wedge (x, y) \notin (A \times C) \) — def. of Cartesian product
- \( \iff (x, y) \in (A \times B) – (A \times C) \) — def. of difference
Since every step is a biconditional (\( \iff \)), the equality is proved. ∎
Observation. The proofs of the distributive properties always follow the same pattern:
- Expand the definition of the Cartesian product
- Apply the definition of the set operation (\( \cup \), \( \cap \), \( – \))
- Use the logical laws (distributivity, De Morgan, etc.)
- Reassemble the definition of the Cartesian product
Non-associativity
The Cartesian product is not associative in the strict sense:
\[ (A \times B) \times C \neq A \times (B \times C) \]
Why? Because elements on each side have a different structure:
| Product | Form of elements | Example with \( a \in A, b \in B, c \in C \) |
|---|---|---|
| \( (A \times B) \times C \) | \( ((a, b), c) \) | \( ((1, 2), 3) \) |
| \( A \times (B \times C) \) | \( (a, (b, c)) \) | \( (1, (2, 3)) \) |
The pair \( ((1, 2), 3) \) is a pair whose first component is another pair, while \( (1, (2, 3)) \) has a pair as its second component. They are distinct objects.
In practice. Although formally \( (A \times B) \times C \neq A \times (B \times C) \), there is a natural correspondence (bijection) between the two sets:
\[ ((a, b), c) \longleftrightarrow (a, (b, c)) \longleftrightarrow (a, b, c) \]
For this reason, in practice we drop the inner parentheses and simply write \( A \times B \times C \) with elements \( (a, b, c) \), called ordered triples.
Monotonicity (preservation of inclusion)
If one set is contained in another, the Cartesian product preserves that relationship:
\[ A \subseteq B \implies A \times C \subseteq B \times C \]
Proof.
- Suppose \( A \subseteq B \), i.e., \( \forall x [x \in A \implies x \in B] \) — hypothesis
- Let \( (x, y) \in A \times C \) — auxiliary hypothesis
- \( \implies x \in A \wedge y \in C \) — def. of Cartesian product
- \( \implies x \in B \wedge y \in C \) — from (1) and (3), since \( x \in A \implies x \in B \)
- \( \implies (x, y) \in B \times C \) — def. of Cartesian product
- \( \therefore A \times C \subseteq B \times C \) — from (2) and (5) ∎
Generalization. If \( A \subseteq C \) and \( B \subseteq D \), then \( A \times B \subseteq C \times D \).
Further notable properties
| Property | Statement |
|---|---|
| Cancellation | \( A \times C = B \times C \) and \( C \neq \emptyset \implies A = B \) |
| Cross-intersection | \( (A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D) \) |
| Cross-union (inclusion) | \( (A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D) \) |
| Complement (inclusion) | \( A’ \times B’ \subseteq (A \times B)’ \) |
Note. In the cross-union, the inclusion is strict (\( \subseteq \), not \( = \)). The right-hand side contains “mixed” pairs such as \( (a, d) \) with \( a \in A \) and \( d \in D \), which do not necessarily belong to \( A \times B \) or to \( C \times D \).
Summary of properties
| Property | Does it hold for the Cartesian product? |
|---|---|
| Commutativity | ✗ (unless \( A = B \) or empty) |
| Associativity | ✗ (unless up to isomorphism) |
| Absorbing element (\( \emptyset \)) | ✓ |
| Distributivity over \( \cup \) | ✓ |
| Distributivity over \( \cap \) | ✓ |
| Distributivity over \( – \) | ✓ |
| Monotonicity (\( \subseteq \)) | ✓ |
Generalization: \( n \)-tuples and \( n \)-ary products
The ordered pair captures the idea of “two elements in a defined order.” But many situations call for sequences of three, four, or more ordered elements:
- A point in space: \( (x, y, z) \) — ordered triple
- A record in a database: (name, age, city, email) — 4-tuple
- A vector in \( n \) dimensions: \( (x_1, x_2, \ldots, x_n) \) — \( n \)-tuple
The ordered \( n \)-tuple
An \( n \)-tuple \( (x_1, x_2, \ldots, x_n) \) is a finite sequence of \( n \) elements in which:
- Order is essential: \( (1, 2, 3) \neq (3, 2, 1) \)
- Repetitions are allowed: \( (1, 1, 1) \) is a valid 3-tuple
- The length \( n \) is part of the identity: \( (1, 2) \neq (1, 2, 0) \)
Equality of \( n \)-tuples. Two \( n \)-tuples are equal if and only if they have the same length and agree component by component:
\[ (x_1, \ldots, x_n) = (y_1, \ldots, y_n) \iff x_1 = y_1 \wedge x_2 = y_2 \wedge \cdots \wedge x_n = y_n \]
| Name | Notation | Length | Example |
|---|---|---|---|
| Ordered pair | \( (a, b) \) | 2 | \( (3, 7) \) |
| Ordered triple | \( (a, b, c) \) | 3 | \( (1, 0, -2) \) |
| 4-tuple | \( (a, b, c, d) \) | 4 | \( (N, S, E, W) \) |
| \( n \)-tuple | \( (x_1, \ldots, x_n) \) | \( n \) | \( (x_1, x_2, \ldots, x_{100}) \) |
Two ways to define the \( n \)-tuple
There are two approaches to formalizing the \( n \)-tuple within set theory.
Recursive definition (nested pairs)
Kuratowski’s ordered pair is reused, chaining pairs one inside another:
\[ (a, b, c) = ((a, b), c) \] \[ (a, b, c, d) = (((a, b), c), d) \] \[ (x_1, x_2, \ldots, x_n) = ((x_1, \ldots, x_{n-1}), x_n) \]
Each \( n \)-tuple is built as an ordered pair whose first component is the preceding \( (n-1) \)-tuple. It is like a set of Russian dolls (matryoshkas): each layer wraps around the one inside it.
Advantage: Simple and direct — only the definition of ordered pair is needed. Disadvantage: To access the first element of a 100-tuple, you have to “unpack” 99 levels of nesting.
Index-function definition
An \( n \)-tuple is defined as a function from the index set \( \{1, 2, \ldots, n\} \) to the elements of the tuple: each index \( i \) is assigned exactly one value \( x_i \):
\[ 1 \mapsto x_1, \quad 2 \mapsto x_2, \quad \ldots, \quad n \mapsto x_n \]
That is, the tuple \( (x_1, x_2, x_3) \) is the correspondence that assigns \( 1 \mapsto x_1 \), \( 2 \mapsto x_2 \), \( 3 \mapsto x_3 \). Each position has a unique assigned value.
Advantage: Direct access to any component (no unpacking needed). Generalizes naturally to infinite families. Disadvantage: This correspondence is, strictly speaking, what we will later define formally as a function — a concept we have not yet developed.
In practice, both definitions produce the same behavior and are used interchangeably.
\( n \)-ary Cartesian product
The Cartesian product extends naturally to more than two sets:
\[ A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \ldots, a_n) \mid a_1 \in A_1 \wedge a_2 \in A_2 \wedge \cdots \wedge a_n \in A_n\} \]
This can also be written using product notation:
\[ \prod_{i=1}^{n} A_i = A_1 \times A_2 \times \cdots \times A_n \]
When all sets are equal (\( A_1 = A_2 = \cdots = A_n = A \)), we write:
\[ A^n = \underbrace{A \times A \times \cdots \times A}_{n \text{ times}} \]
The cardinality formula extends naturally:
\[ n(A_1 \times A_2 \times \cdots \times A_n) = n(A_1) \cdot n(A_2) \cdots n(A_n) \]
The spaces \( \mathbb{R}^n \): from the plane to hyperspace
The most important instance of the \( n \)-ary Cartesian product arises when \( A = \mathbb{R} \) (the real numbers):
| Space | Definition | Geometric interpretation |
|---|---|---|
| \( \mathbb{R}^1 = \mathbb{R} \) | The number line | Line (1 dimension) |
| \( \mathbb{R}^2 = \mathbb{R} \times \mathbb{R} \) | Pairs \( (x, y) \) | Cartesian plane (2 dimensions) |
| \( \mathbb{R}^3 = \mathbb{R} \times \mathbb{R} \times \mathbb{R} \) | Triples \( (x, y, z) \) | Three-dimensional space (3 dimensions) |
| \( \mathbb{R}^n \) | \( n \)-tuples \( (x_1, \ldots, x_n) \) | \( n \)-dimensional space |
Example. The space \( \mathbb{R}^3 \) is where we live: every point is identified by a triple \( (x, y, z) \) indicating length, width, and height. Newton formulated his laws of mechanics in this space, and Einstein extended it to \( \mathbb{R}^4 \) by incorporating time as a fourth coordinate.
Beyond geometry. Although we cannot “visualize” \( \mathbb{R}^{100} \), the concept is perfectly rigorous and has concrete applications: in data science, each record in a database with 100 numerical fields is a point in \( \mathbb{R}^{100} \). Artificial intelligence algorithms routinely operate in spaces of thousands of dimensions.
Chapter summary. We started from a fundamental limitation of sets — their inability to represent order — and built step by step the tools that resolve it:
- The ordered pair \( (a, b) \): two elements with a defined position
- The Kuratowski definition \( \{\{a\}, \{a, b\}\} \): formal grounding in ZFC
- The Cartesian product \( A \times B \): the space of all combinations
- The algebraic properties: distributivity, monotonicity, non-commutativity
- The \( n \)-tuple and \( \mathbb{R}^n \): generalization to multiple dimensions
With these tools in hand, we are ready to define binary relations and, from them, functions — the most important concept in all of modern mathematics.
What’s coming next
With ordered pairs and the Cartesian product at our disposal, we have the tools needed to tackle the following topics in the next post:
- Binary relations — subsets of the Cartesian product that connect elements of one set to another.
- Properties of relations — reflexivity, symmetry, transitivity, and others.
- Equivalence relations — relations that group “similar” elements into classes.
- Order relations — relations that arrange elements in hierarchies.
- Functions — a special type of relation where each element has exactly one image.
See you in the next post!