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

FactNote
(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.

Q2. Show by example that , using A = {1,2}, B = {3,4}, C = {5,6}.

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