Cartesian Products

Math for CS · Axiom Academy

Ordered pairs, product sets, and the math behind databases Unlike sets, ordered pairs care about order: This means (1, 2) (2, 1) , unlike the set \ 1, 2\ = \ 2, 1\ . Example: Let A = \ 1, 2, 3\ and B = \ x, y\ . Then: A B = \ (1,x), (1,y), (2,x), (2,y), (3,x), (3,y)\ We can visualize this as a grid: This is a direct application of the multiplication principle in counting: m choices for the first component times n choices for the second. Example: |A| = 3 , |B| = 2 , so |A B| = 6 — which matches the 6 pairs we listed. In general, A B B A (unless A = B or one is empty). However, they always have the same cardinality: |A B| = |B A| = |A| |B| . The Cartesian product of a set with itself is written A^2 = A A . More generally, A^n = A A A ( n times) gives all n -tuples from A . A relational database table with columns C_1, C_2, , C_k is a subset of the Cartesian product of the domains of each column: Each row is an ordered tuple in . The most familiar Cartesian product is the one named after Descartes himself: Similarly, 3D space is ^3 = , and an n -dimensional feature vector in machine learning lives in ^n . A B is the set of all ordered pairs (a, b) |A B| = |A| |B| (multiplication principle) Order matters: A B B A in general Database tables are subsets of Cartesian products ^n is the n -fold Cartesian product of the reals

This is the written version of the interactive lesson above. See the full Math for CS course.