Cartesian product

The Cartesian product of two sets is the set of all possible ordered pairs made up of one element from each set. In set-builder notation, the Cartesian product \(A \times B\) of two sets \(A\) and \(B\) is defined as:

$$A \times B = \set{ (a, b) : a \in A \land b \in B }$$

Intuitively, the Cartesian product here can be viewed as the set of all combinations of \(a\) and \(b\) where \(a\) is an element of \(A\) and \(b\) is an element of \(B.\)

For finite sets, the cardinality of their Cartesian product is the product of their individual cardinalities. This is expressed through the following equation: \(|A \times B| = |A| * |B|\), which is really just the rule of product.

⚠ Recognize that \(A \times B \neq B \times A.\) This is because the roles of the first and second elements have been swapped, and for ordered pairs, that matters. Therefore, while \(A \times B\) and \(B \times A\) have the same combinations, they do not have the same ordered pairs, making them different sets.
Contents

Cartesian products of several sets

When dealing with more than \(2\) sets at once, the definition of the Cartesian product can be generalized for \(n\) sets.

For sets \(A_1, ..., A_n\), their Cartesian product is as follows: $$A_1 \times ... \times A_n = \set{ (a_1, ..., a_n) : \bigwedge_{i=1}^{n} a_i \in A_i}$$

This can be read as "the set of all \(n\)-tuples whose \(i\)th element is an element of the \(i\)th set." Therefore, the Cartesian product of \(n\) sets is the set of all ordered \(n\)-tuples made up of one element from each set.

Cartesian product of a set with itself

The Cartesian product of a set \(A\) with itself is typically abbreviated as \(A^n\), defined as:

$$A^n = \underbrace{A \times A \times ... \times A}_{n \, \text{times}}$$

If \(A\) consists of only characters, you can instead write the elements of \(A^n\) as strings rather than as ordered \(n\)-tuples, which means you can forgo the use of parentheses and commas. Take \(\set{0, 1}^3\) for example, the set of all \(3\)-bit binary strings:

$$\set{0, 1}^3 = \set{ 000, 001, 010, 011, 100, 101, 110, 111 }$$
⚠ Notably, the two-dimensional plane as we know it is the collection of all ordered pairs \((x, y)\) such that \((x, y) \in \mathbb{R}^2.\)
Logic & Proofs
Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form
Set Theory
Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof
Functions
Function • Floor function • Ceiling function • Inverse function
Algorithms
Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm
Relations
Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class
Number Theory
Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm
Induction
Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition
Combinatorics
Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle
Graph Theory
Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm
Recursion
Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort