SET 06 · Cartesian Product
Ordered pairs
— order matters: (different points on a graph). .
Sets vs tuples
but . but is a valid pair.
Definition
Example: A = {1, 2}, B = {a, b, c} → A×B = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)}
Key facts
| Fact | Note |
|---|---|
| (in general) | {1,2}×{3,4} has (1,3); {3,4}×{1,2} has (3,1) |
| {a,b}×{p,q,r} → 6 pairs | |
| no first (or second) coordinate to pick | |
| or or |
n-ary products
— ordered triples. .
Airlines (slides)
A = {Ind, AA}, B = C = {Mum, Hyd} A×B×C = {(Ind,Mum,Mum), (Ind,Mum,Hyd), (Ind,Hyd,Mum), (Ind,Hyd,Hyd), (AA,Mum,Mum), (AA,Mum,Hyd), (AA,Hyd,Mum), (AA,Hyd,Hyd)} — 2·2·2 = 8.
A × B × C ≠ (A × B) × C
- has elements like — a triple.
- has elements like — a pair whose first item is a pair.
Same count, different objects ⇒ strictly not equal (though there’s a natural one-to-one correspondence).
Solved problems (slides) — try first
Q1. A = {DS, Algo} (courses), B = {Mark, Allen} (professors). Find A×B.
👁 Show answer
{(DS, Mark), (DS, Allen), (Algo, Mark), (Algo, Allen)}
Q2. Show by example that , using A = {1,2}, B = {3,4}, C = {5,6}.
👁 Show answer
A×B×C = {(1,3,5), (1,3,6), (1,4,5), (1,4,6), (2,3,5), (2,3,6), (2,4,5), (2,4,6)} (A×B)×C = {((1,3),5), ((1,3),6), ((1,4),5), ((1,4),6), ((2,3),5), ((2,3),6), ((2,4),5), ((2,4),6)} Elements are triples vs nested pairs ⇒ not equal.
Why this matters next
A relation from A to B is just a subset of A×B ⇒ number of relations = . → Relations
Prev ← SET 05 Power Set and Cardinality · Next → SET 07 Set Operations