Define Cartesian product

The Cartesian product of two sets A and B, written A × B, is the set of all ordered pairs whose first element is from A and second from B:

A × B = { (a, b) : a ∈ A and b ∈ B }

Example. A = {1, 2}, B = {x, y, z}:

A × B = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}

Properties

• Pairs are ordered: (a, b) ≠ (b, a) unless a = b.
• |A × B| = |A|·|B| for finite sets (here 2·3 = 6).
• In general A × B ≠ B × A (it is equal only if A = B or one of them is empty).
• A × ∅ = ∅.
• It extends to n sets: A₁ × A₂ × ... × Aₙ is the set of ordered n-tuples. Aⁿ = A × A × ... × A (n times).

Use in this subject. A relation from A to B is a subset of A × B. A function f : A → B is a special kind of relation, so it is also a subset of A × B. The transition function of a DFA is δ : Q × Σ → Q, whose domain is a Cartesian product.