Day 37 — Products & tuples

Day 37 — Products & tuples

Stage IV · concept day
Goal: Define Cartesian products and \(n\)-tuples; count \(|A\times B|=|A||B|\) (finite); see relations as subsets of products; contrast disjoint union with product; connect to records, schemas, and nested loops.

Why this matters

A pair \((user, role)\) lives in a product. Database rows are \(n\)-tuples; multiple loop indices range over products; graphs’ edge sets are subsets of \(V\times V\) (or unordered pairs). Relations and functions (Days 38–42) are specialized subsets of products.

Theory

Ordered pairs

An ordered pair \((a,b)\) satisfies \((a,b)=(c,d)\) iff \(a=c\) and \(b=d\).
Order matters: \((1,2)\neq(2,1)\).
(Set-theoretic encoding \((a,b)=\{\{a\},\{a,b\}\}\) is optional awareness.)

Cartesian product

\[A \times B = \{ (a,b) : a\in A,\; b\in B \}.\]

If \(A=\emptyset\) or \(B=\emptyset\) then \(A\times B=\emptyset\).

\(n\)-tuples and \(n\)-fold products

\[A_1 \times A_2 \times \cdots \times A_n = \{ (a_1,\ldots,a_n) : a_i\in A_i \}.\]

\[A^n = \underbrace{A\times\cdots\times A}_{n\text{ times}}.\]

Associativity up to canonical bijection: \((A\times B)\times C \cong A\times(B\times C)\) via \(((a,b),c)\mapsto(a,(b,c))\mapsto(a,b,c)\).

Finite counting

Theorem. If \(A,B\) finite, \(|A\times B| = |A|\cdot|B|\).

Proof. For each of \(|A|\) choices of first coordinate, \(|B|\) choices of second. \(\square\)

More generally \(|A_1\times\cdots\times A_n| = \prod_i |A_i|\).
\(|A^n| = |A|^n\).

Relations as subsets (preview)

A binary relation from \(A\) to \(B\) is any \(R \subseteq A\times B\).
We write \(a\,R\,b\) for \((a,b)\in R\). Day 38 studies properties on \(A\times A\).

Graphs (preview)

Directed graph: edge set \(E\subseteq V\times V\).
Undirected simple: edges as \(2\)-subsets, related but not identical to \(V\times V\).

Disjoint union vs product

Disjoint union (tagged sum):
\[A \sqcup B = (\{0\}\times A) \cup (\{1\}\times B).\]
Elements are either from \(A\) or from \(B\) (with tags).
\(|A\sqcup B| = |A|+|B|\) if we use this tagging (always disjoint).

Product: elements are both an \(A\) and a \(B\) coordinate.
\(|A\times B|=|A||B|\).

In programming: sum types / enums with payload ≈ disjoint union; structs with two fields ≈ product (Day 44).

Projections

\(\pi_1: A\times B \to A\), \(\pi_1(a,b)=a\); \(\pi_2(a,b)=b\).
Surjective if the other factor is nonempty.

Sections / fibers

For \(a\in A\), the fiber \(\{b : (a,b)\in R\}\) for \(R\subseteq A\times B\).

Nested loops

for a in A:
  for b in B:
    body

runs \(|A|\cdot|B|\) times—iteration over \(A\times B\).

Worked examples

Example 1 — Small product

\(A=\{1,2\}\), \(B=\{x,y,z\}\):
\(A\times B = \{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}\), size \(6\).

Example 2 — Noncommutativity

\(A\times B \neq B\times A\) in general as sets of pairs (different coordinate types/order), though equinumerous if finite.

Example 3 — Empty

\(\emptyset \times \{1,2\} = \emptyset\).

Example 4 — \(A^2\)

\(\{0,1\}^2 = \{(0,0),(0,1),(1,0),(1,1)\}\).

Example 5 — Relation

\(R = \{ (n,m)\in\mathbb{Z}^2 : n < m \} \subseteq \mathbb{Z}\times\mathbb{Z}\).

Example 6 — Count functions preview

Number of functions \(A\to B\) is \(|B|^{|A|}\) (Day 41–42)—each element of \(A\) picks an image in \(B\), product of choices.

Example 7 — Schema

Row type \(Users\times Roles\) vs relation \(Assigned \subseteq Users\times Roles\).

Example 8 — Disjoint union size

\(|\{a,b\} \sqcup \{b,c\}| = 4\) tagged, while \(|\{a,b\}\cup\{b,c\}|=3\).

Example 9 — Triple loop

\(|A\times B\times C|=|A||B||C|\).

Example 10 — Diagonal

\(\Delta_A = \{(a,a): a\in A\} \subseteq A\times A\) (equality relation).

Example 11 — Bijection reassociation

Map \(((a,b),c)\mapsto(a,b,c)\) is bijective between \((A\times B)\times C\) and \(A\times B\times C\).

Example 12 — Boolean cube

\(\{0,1\}^n\) has \(2^n\) points—bitstrings of length \(n\).

Example 13 — Grid

Pixel coordinates \(\{1,\ldots,W\}\times\{1,\ldots,H\}\).

Example 14 — Subset of product

\(\{ (x,y)\in\mathbb{R}^2 : x^2+y^2 = 1 \}\) unit circle—not a full product.

Exercises

1. List \(\{a,b\}\times\{1,2\}\).
   
2. Compute \(|\mathbb{Z}/5\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}|\) if \(|\mathbb{Z}/n\mathbb{Z}|=n\).
   
3. Prove \(A\times B = \emptyset \Leftrightarrow A=\emptyset \lor B=\emptyset\).
   
4. Show by counterexample \(A\times B = B\times A\) can fail.
   
5. How many elements in \(\{1,2,3\}^4\)?
   
6. Define \(R\subseteq\{1,2,3\}^2\) as \(\le\) on numbers; list pairs.
   
7. Prove \(|A\times B|=|A||B|\) for finite sets carefully (double count).
   
8. Give a bijection \((A\times B)\times C \to A\times(B\times C)\).
   
9. Express disjoint union of \(\{0,1\}\) and \(\{0,1\}\) as a \(4\)-element set of tagged pairs.
   
10. Count nested loop iterations: \(i\in A\), \(j\in B\), \(k\in C\).
    
11. Is \((A\cup B)\times C = (A\times C)\cup(B\times C)\)? Prove.
    
12. Is \((A\cap B)\times C = (A\times C)\cap(B\times C)\)? Prove.
    
13. Disprove \((A\times B)\cup(C\times D) = (A\cup C)\times(B\cup D)\) in general.
    
14. Describe \(\pi_1^{-1}(\{a\})\) as a subset of \(A\times B\).
    
15. CS: model HTTP request as product of method set and path set (simplified).
    
16. How many directed edges possible on vertex set \(V\) (allowing loops)? \(|V|^2\).
    
17. Without loops: \(|V|(|V|-1)\).
    
18. Define equality relation on \(A\) as a subset of \(A\times A\).
    
19. If \(|A|=n\), how many subsets does \(A\times A\) have?
    
20. Compare \(|A\sqcup A|\) and \(|A\times\{0,1\}|\)—bijection?
    
21. Prove if \(A\subseteq C\), \(B\subseteq D\) then \(A\times B \subseteq C\times D\).
    
22. Tuples: when is \((a,b,c)=(d,e,f)\)?
    
23. Bitmasks: identify \(\mathcal{P}([n])\) with \(\{0,1\}^n\) again.
    
24. Give a real schema with \(4\) attributes as a product of domains.
    
25. Explain in one paragraph product vs sum types for a “Result” value (preview Day 44).

CS connection

• Structs / records = products of field types.
  
• JOIN in databases multiplies row spaces (then filters).
  
• Nested loops iterate products.
  
• Configuration grids hyperparameter products.
  
• Pairing heap keys, coordinates, key-value stores.
  
• Graph adjacency as subset of \(V\times V\).

Common pitfalls

Pitfall	What to do instead
Treating pairs as sets \(\{a,b\}\)	Order and repetition differ
\(A\times B=B\times A\) as sets	Only equinumerous in general
Empty product mistakes	Any empty factor empties product
Confusing \(\cup\) of products with product of \(\cup\)	See Exercise 13
Counting undirected edges as \(|V|^2\)	Adjust for order and loops
Forgetting tags in disjoint union	Overlap collapses \(\cup\)

Checkpoint

• Define \(A\times B\) and \(A^n\)
  
• Count finite products
  
• Give relation as subset of product
  
• Contrast \(\sqcup\) and \(\times\)
  
• Prove one distributive law over \(\times\)
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — currying and exponential (awareness)

Maps \(A\times B\to C\) biject with maps \(A\to (B\to C)\) (currying) when working with pure total functions:
\[C^{A\times B} \cong (C^B)^A.\]
This is the set-theoretic root of “a function of two arguments is a function returning a function.” Day 44 types will echo this.

Counting recap

Object	Count (finite)
\(A\times B\)	\(\|A\|\|B\|\)
\(A^n\)	\(\|A\|^n\)
relations on \(A\)	\(2^{n^2}\) if \(\|A\|=n\)
functions \(A\to B\)	\(\|B\|^{\|A\|}\)
subsets of \(A\times B\)	\(2^{\|A\|\|B\|}\)

Distributivity laws (prove by element chase)

\[ \begin{align*} (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\times(B\cup C) &= (A\times B)\cup(A\times C). \end{align*} \]

More worked examples

Example 15 — Non-example of product
Unit circle \(\neq\) product of two nontrivial intervals in a simple way.

Example 16 — Database
SELECT * FROM A CROSS JOIN B has \(|A||B|\) rows before WHERE.

Example 17 — Identity
\(A\times\{*\}\cong A\) via \((a,*)\mapsto a\).

Example 18 — Tagging
\(A+A \cong A\times\{0,1\}\) as sets.

Additional exercises

26. Prove the three distributivity identities above.
    
27. Count binary relations from a \(3\)-set to a \(4\)-set.
    
28. Give a bijection \(A\times B\to B\times A\).
    
29. Show \((A\times B)\times(C\times D)\) equinumerous with \(A\times B\times C\times D\).
    
30. Model a key-value store state as a function \(K\to V\) vs relation \(K\times V\).

Extended practice workshop

Listing and counting

1. List \(\{0,1\}\times\{a,b,c\}\).
   
2. \(|\{1,\ldots,10\}^3|\).
   
3. \(|A\times B|\) if \(|A|=0\).
   
4. Number of subsets of \(A\times A\) for \(|A|=3\).
   
5. Number of binary relations on a \(4\)-set.

Algebra of products

6. Prove \((A\cup B)\times C=(A\times C)\cup(B\times C)\).
   
7. Prove \((A\cap B)\times C=(A\times C)\cap(B\times C)\).
   
8. Counterexample for \((A\times B)\cup(C\times D)=(A\cup C)\times(B\cup D)\).
   
9. Bijection \((A\times B)\times C\cong A\times B\times C\).
   
10. Bijection \(A\times B\cong B\times A\).

Relations preview

11. List \(\le\) on \(\{1,2,3\}\) as pairs.
    
12. Equality \(\Delta_A\) as a set.
    
13. “\(m\) divides \(n\)” on \(\{1,2,3,4\}\) as pairs.

Disjoint union

14. Write \(\{0,1\}\sqcup\{0,1\}\) as tagged pairs.
    
15. Compare \(|A\cup B|\) vs \(|A\sqcup B|\) when overlap.

CS scenarios

16. Nested loop counts as \(|A\times B\times C|\).
    
17. Grid coordinates.
    
18. Schema as product of domains.
    
19. Directed edges \(\subseteq V\times V\).
    
20. Key-value as function vs as relation \(\subseteq K\times V\).

Product vs sum card

	Product \(A\times B\)	Sum \(A\sqcup B\)
Element	both	either
Count	multiply	add
Code	struct	enum/variant

Synthesis

Cartesian products are how discrete math packages joint data: pairs, records, grid points, edges as ordered pairs. Counting multiplies; algebra distributes over \(\cup\)/\(\cap\) with care. Relations (tomorrow) are subsets of products—so every product identity you prove today pays rent immediately.

Mental model

• \(A\times B\): an element is a pair \((a,b)\) with both components.
  
• \(A\sqcup B\): an element is a tagged value from \(A\) or from \(B\) (disjoint union).
  
• \(A\to B\) (later): an element is a function—equivalently a special subset of \(A\times B\) (functional relation).

More worked examples

Example — Empty product.
\(A\times\emptyset=\emptyset\): there is no pair \((a,b)\) with \(b\in\emptyset\). Same for \(\emptyset\times B\). Counting: \(|A|\cdot 0=0\).

Example — Distributivity.
\((A\cup B)\times C = (A\times C)\cup(B\times C)\) by unfolding membership of pairs.
Fails for outer union of products: \((A\times B)\cup(C\times D)\) need not equal \((A\cup C)\times(B\cup D)\)—counterexample \(A=C=\{1\}\), \(B=\{x\}\), \(D=\{y\}\): right side contains \((1,y)\) and \((1,x)\) etc. in ways left may miss or… standard counterexample: \(A=\{1\},B=\{a\},C=\{2\},D=\{b\}\); \((1,b)\) is in the product of unions but not in either \(A\times B\) or \(C\times D\).

Example — Counting nested loops.
for a in A: for b in B: for c in C runs \(|A||B||C|\) iterations when loops are independent—literal \(|A\times B\times C|\).

Example — Bijection swap.
\(\varphi:A\times B\to B\times A\), \(\varphi(a,b)=(b,a)\) is bijective with inverse the same pattern. So \(|A\times B|=|B\times A|\) even though ordered pairs care about order.

Example — Relations as subsets.
On \(A=\{1,2,3\}\), the relation \(\le\) is the set of pairs \(\{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}\subseteq A\times A\). Number of all binary relations on \(A\): \(2^{|A|^2}=2^9=512\).

Extra exercises (synthesis)

31. Prove \(A\times(B\cap C)=(A\times B)\cap(A\times C)\).
    
32. Prove \(A\times(B\cup C)=(A\times B)\cup(A\times C)\).
    
33. Give a counterexample to \((A\times B)\cap(C\times D)=(A\cap C)\times(B\cap D)\) or prove it (it is true—prove).
    
34. Count \(|\{0,1\}^n|\) and interpret as bitstrings / subsets via characteristic vectors.
    
35. Model a directed multigraph without multi-edges as \(E\subseteq V\times V\). When would you want \(E\subseteq V\times V\times L\) (labeled edges)?
    
36. Compare \(|A\cup B|\) and \(|A\sqcup B|\) when \(A\cap B\neq\emptyset\).

Product algebra priority

Claim	Status
\((A\cup B)\times C=(A\times C)\cup(B\times C)\)	True
\((A\cap B)\times C=(A\times C)\cap(B\times C)\)	True
\((A\times B)\cup(C\times D)=(A\cup C)\times(B\cup D)\)	False in general
\(A\times\emptyset=\emptyset\)	True
\(|A\times B|=|A||B|\) (finite)	True

Tomorrow: properties of subsets of \(A\times A\) (and \(A\times B\))—reflexive, symmetric, transitive, and friends.

Tomorrow

Day 38 — Relations. Binary relations; digraph/matrix; reflexive/symmetric/transitive/antisymmetric; closures; composition.