1
Tuples are ordered and sets are not
(1, 2) ≠ (2, 1) while {1, 2} = {2, 1}. Tuples also allow repetition: (1, 1) is a perfectly good pair.
Lesson · Sets, Relations, and Functions · Sets
Cartesian Products and Tuples
A tuple has order and allows repetition, which a set does not. The Cartesian product collects every ordered pair, has size |A| · |B|, and is where relations and functions will live.
(a, b) = (c, d) ⟺ a = c and b = d order matters
A × B = {(a, b) : a ∈ A, b ∈ B}
|A × B| = |A| · |B|
A × B ≠ B × A in general
Ordered, unlike a set
Core ideas
What this lesson establishes
Sets forget order. Tuples remember it, and everything from relations to graphs needs that memory.
2
The product multiplies sizes
|A × B| = |A| · |B|, because each of |A| first coordinates can be paired with each of |B| second ones. This is Combinatorics and Counting's product rule.
3
The product is not commutative
A × B and B × A contain different pairs unless A = B or one is empty. There is a natural bijection between them, which is a weaker statement.
The material
Products and tuples
The definitions, the size formula, and where products get used.
Definition · Ordered pair
An ordered pair (a, b) satisfies (a, b) = (c, d) exactly when a = c and b = d. More generally an n-tuple (a₁, …, aₙ) is equal to another exactly when they agree coordinate by coordinate.
Definition · Cartesian product
A × B = {(a, b) : a ∈ A and b ∈ B}. The n-fold product A₁ × ⋯ × Aₙ is the set of n-tuples with aᵢ ∈ Aᵢ, and Aⁿ abbreviates A × ⋯ × A with n factors.
Theorem · The size of a product
For finite sets, |A × B| = |A| · |B|, and |A₁ × ⋯ × Aₙ| is the product of the sizes.
Each pair is formed by choosing a first coordinate (|A| ways) and then a second (|B| ways, independently of the first). Distinct choices give distinct pairs, by the definition of pair equality, and every pair arises this way. So the count is |A| · |B|.
□
If either factor is empty the product is empty: there is no pair to form. A × ∅ = ∅ for every A, which the size formula also predicts.
Example · A small product
{1, 2} × {a, b, c} has 2 · 3 = 6 elements: (1,a), (1,b), (1,c), (2,a), (2,b), (2,c). Note {a,b,c} × {1,2} contains (a,1), a different object from (1,a).
Where products are used
- Relations (“Binary Relations”) are subsets of A × B. "x is less than y" is the set of pairs where that holds.
- Functions (“Functions”) are relations with an extra condition, so they too are sets of pairs.
- The plane is ℝ × ℝ, written ℝ². Coordinate geometry is the observation that points are ordered pairs.
- Bit strings of length n are elements of {0, 1}ⁿ, and there are 2ⁿ of them — the same count as the subsets of an n-element set, for the same reason.
That last coincidence is worth pausing on. A subset of an n-element set is exactly a choice of in-or-out for each element, which is exactly a bit string of length n. The bijection between P(A) and {0,1}ⁿ is why both are counted by 2ⁿ. It is a preview of “Injective, Surjective, Bijective”, which names such a pairing a bijection, and of “Cardinality and Countability”, which makes it the definition of size.
Definition · Cardinality of a product of a set with itself
|Aⁿ| = |A|ⁿ. With |A| = 2 this gives 2ⁿ; with |A| = 26 and n = 4 it gives the number of four-letter strings, 456 976.
Interactive
The four counting rules
Enumerated while enumeration is possible
Method
Working with products
Coordinates first, then count.
1
Fix which set supplies which coordinate
A × B takes its first coordinate from A. Reversing this silently produces a different set.
2
Count by multiplying
|A × B × C| = |A| · |B| · |C|. Independent choices multiply; this is the product rule Combinatorics and Counting states in general.
3
Enumerate systematically when listing
Vary the last coordinate fastest, exactly as truth table rows do. The pattern makes a missing tuple visible.
4
Remember that a subset of a product is a relation
This is the whole content of “Binary Relations”: any set of pairs is a relation, and any relation is a set of pairs.
Products
Score 0 / 0Choose the answer you can justify.
Counting with a product
How many strings of length 4 use letters from {a, b, c}?
A string of length 4 is an element of {a,b,c}⁴.
|{a,b,c}⁴| = 3⁴ = 81
How many use no repeated letter?
first 3 choices
second 2 choices (one used)
third 1 choice
fourth 0 choices ⟹ 0 such strings
Length 4 from a 3-letter alphabet must repeat: pigeonhole (“The Pigeonhole Principle”).
The second count is the pigeonhole principle arriving early, and by arithmetic rather than by argument: four positions, three letters, so some letter is used twice. “The Pigeonhole Principle” states it in general.
Common mistakes
1
Treating A × B and B × A as the same setThey contain different objects. There is a natural bijection between them, which is a statement about size, not about equality.
2
Adding sizes instead of multiplying|A × B| is a product because the choices are made together, not alternatively. “The Sum and Product Rules” in Combinatorics and Counting draws the line between the two rules.
3
Writing {a, b} when order mattersIf swapping the entries changes the meaning, you need a tuple. Using a set throws away exactly the information you were relying on.
Check your understanding
✓
Finish when you can say why 2ⁿ counts both subsets and bit strings.
Describe the bijection explicitly: given a subset, produce its bit string; given a bit string, produce its subset. That construction is what “Injective, Surjective, Bijective” calls a bijection, what “Cardinality and Countability” turns into the definition of same size, and what Combinatorics and Counting uses constantly.
Note: Formally an ordered pair can be defined purely in terms of sets, as (a, b) = {{a}, {a, b}} — Kuratowski's definition — which does satisfy the equality property. Nothing on this path needs it; it is worth knowing that order is not an extra primitive.