Cartesian Product

Context: FIT1058_MOC · builds sets of ordered tuples · cardinality multiplies · underlies $A^k$ in Sets of Strings

Quick Revision

• 🎯 Objective: $A\times B$ = all ordered pairs, first from $A$, second from $B$ ➔ order matters.
• 📦 Core Components: ordered pair $(a,b)$ ➔ $|A\times B|=|A||B|$ ➔ $n$-tuples.
• ⚡ Key Constraint: not commutative ($A\times B\ne B\times A$); multiplicative growth, not exponential.

📝 Core

1. The Product (Ordered Tuples)

• Ordered pair ➔ $(a,b)$, order matters ($(a,b)\ne (b,a)$ unless $a=b$).
• Definition ➔ $A\times B=\{(a,b):a\in A,b\in B\}$.
• Contrast a set ➔ tuples are ordered; set elements are not.

2. Cardinality Multiplies

• Product rule ➔ $|A\times B|=|A|\cdot |B|$ (independent choices).
• $n$ factors ➔ length-$n$ tuples, $|A_1\times \cdots \times A_n|={\prod }_i|A_i|$.

3. Geometry & Strings

• Spaces ➔ $\mathbb{R}\times \mathbb{R}$ = plane, ${\mathbb{R}}^3$ = 3-D space.
• Strings ➔ length-$k$ string over $A$ = element of $A^k$, so $|A^k|=|A{|}^k$ (Sets of Strings).

Key identities:

$|A\times B|=|A|\cdot |B|,|A_1\times \cdots \times A_n|={\prod }_{i=1}^n|A_i|$ $A\times B\ne B\times A\text{ (in general)},|A^k|=|A{|}^k$

⚖️ Core Decision Matrix

Constructor	Size	Growth
$A\times B$	$|A||B|$	multiplicative
$A^k$	$|A{|}^k$	polynomial in $|A|$
Power Set $\mathcal{P}(A)$	$2^{|A|}$	exponential

When It Flips: the two principal set constructors grow very differently — Cartesian product multiplies sizes, the power set exponentiates. Product is not commutative but its cardinality is order-independent.

📊 Exam Execution Trace

Manual Execution Trace

$A=\{1,2\}$, $B=\{x,y\}$:

Step / State	Quantity	Result
0 (Init)	—	—
1	$A\times B$	$\{(1,x),(1,y),(2,x),(2,y)\}$
2	$|A\times B|$	$2\cdot 2=4$
3	$B\times A$	$\{(x,1),(x,2),(y,1),(y,2)\}\ne A\times B$

⚠️ Common Mistakes

• 💡 Not commutative ➔ $(a,b)$ and $(b,a)$ are different tuples; $A\times B$ and $B\times A$ have equal size but differ as sets.

🧠 Active Recall

Why is $|A\times B|=|A|\cdot |B|$, and why are the elements ordered pairs?

• Hint: Independent choice + role.

Answer

• Short answer: $|A|$ choices for the first component, $|B|$ for the second ⟹ product; components have distinct roles.
• Why: Ordered ➔ $(a,b)\ne (b,a)$; a set would ignore that order.

How does a length- $k$ string over $A$ relate to a Cartesian product, and its count?

• Hint: String = tuple.

Answer

• Short answer: A length-$k$ string is a $k$-tuple in $A^k=A\times \cdots \times A$.
• Why: Product rule ➔ $|A^k|=|A{|}^k$.