Log inSign up
DISCRETE MATH β€’ SETS, RELATIONS, AND FUNCTIONS

Cartesian products and power sets

Two fundamental constructions that generate new sets from existing ones, underpinning relations, functions, and combinatorics.

SECTION 1

Historical Context & Motivation

The idea of pairing elements from two collections and systematically enumerating all subsets of a given collection arose long before the formal language of set theory existed. Ancient combinatorial thinking in Indian and Chinese mathematics considered arrangements and selections of objects, but it was the development of coordinate geometry and later the axiomatization of sets that gave these ideas their modern, rigorous form. The Cartesian product takes its name from RenΓ© Descartes, whose coordinate system relies on pairing real numbers to identify points in the plane, while the power set emerged from Georg Cantor's groundbreaking investigations into infinite cardinalities. Together, these two constructions form the backbone of how modern mathematics builds relations, functions, probability spaces, and topological structures from elementary sets.

1637
Descartes' La GΓ©omΓ©trie
RenΓ© Descartes publishes his method of representing geometric points as ordered pairs of numbers, implicitly defining the concept of a Cartesian product of the real line with itself.
1874
Cantor Founds Set Theory
Georg Cantor introduces the notion of sets as foundational mathematical objects and begins studying their cardinalities, leading to the formal concept of subsets and power sets.
1891
Cantor's Diagonal Argument
Cantor proves that the power set of any set has strictly greater cardinality than the set itself, establishing the power set as a tool for constructing larger infinities.
1908
Zermelo's Axiomatization
Ernst Zermelo introduces the Axiom of Power Set in his axioms for set theory, guaranteeing that the collection of all subsets of any set is itself a set.
1930s
Modern Formalization
The Zermelo–Fraenkel axioms (ZF) solidify the Cartesian product and power set as standard constructions, and Kuratowski's definition of ordered pairs provides a purely set-theoretic foundation for products.

The central question these constructions address is deceptively simple: given one or more sets, how can we systematically generate every possible pairing of their elements and every possible sub-collection? Answering this question rigorously unlocks the formal definitions of relations, functions, and probability measures, and reveals deep truths about the nature of infinity itself.

SECTION 2

Core Definitions & Principles

Before diving into computations and proofs, it is essential to lay down the precise definitions that govern Cartesian products and power sets. Both constructions start from one or more existing sets and produce a new set whose elements are structured in a well-defined way. The Cartesian product pairs elements together, preserving order, while the power set collects all possible subsets, treating each subset as a single element of the resulting set. These definitions are not arbitrary; they encode the combinatorial structure that makes relations, functions, and cardinality arguments possible.

1

Ordered Pair

An ordered pair (a, b) is a pair of elements in which the first component a and the second component b are distinguished. Crucially, (a, b) β‰  (b, a) unless a = b, unlike unordered sets where {a, b} = {b, a}.
2

Cartesian Product

The Cartesian product A Γ— B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. It captures every possible pairing of an element from A with an element from B.
3

Power Set

The power set 𝒫(A) is the set of all subsets of A, including the empty set βˆ… and A itself. Every element of 𝒫(A) is a set.
4

Cardinality Connection

If |A| = m and |B| = n, then |A Γ— B| = m Γ— n. If |A| = n, then |𝒫(A)| = 2ⁿ. These formulas reflect the multiplicative and exponential nature of the two constructions.
5

Empty Set Behavior

A Γ— βˆ… = βˆ… for any set A, because no ordered pairs can be formed. Meanwhile, 𝒫(βˆ…) = {βˆ…}, a set containing exactly one element β€” the empty set itself.
✦ KEY TAKEAWAY
Think of the Cartesian product like a restaurant menu: if you can choose one appetizer from set A and one entrΓ©e from set B, then A Γ— B is the set of all possible meal combinations. The power set, on the other hand, is like a buffet where for each dish you make a binary choice β€” take it or leave it. With n dishes, you have 2ⁿ possible plate configurations, including the empty plate.
SECTION 3

Visual Explanation

Visualizing the Cartesian product as a grid and the power set as a lattice of subsets makes the combinatorial structure of each construction immediately apparent. The following diagram illustrates the Cartesian product A Γ— B where A = {1, 2, 3} and B = {x, y}. Each dot in the grid represents one ordered pair, and the total number of dots equals |A| Γ— |B| = 6.

The grid layout shows every ordered pair in A Γ— B. Each row corresponds to an element of B and each column to an element of A. The six colored dots represent the six elements of the Cartesian product.

Notice how the grid structure makes the multiplication principle visually self-evident: for each of the three choices along the horizontal axis (elements of A), there are exactly two choices along the vertical axis (elements of B), yielding 3 Γ— 2 = 6 ordered pairs in total. This grid interpretation extends naturally to higher dimensions β€” A Γ— B Γ— C would be a three-dimensional lattice of ordered triples β€” though such constructions are harder to draw on a flat page. The key insight is that order matters in each tuple: the pair (1, x) occupies a different cell than (x, 1) would if we reversed the factors.

SECTION 4

Mathematical Framework

The formal definitions of the Cartesian product and power set rely on set-builder notation and, at a foundational level, on the axioms of Zermelo–Fraenkel set theory. Understanding these definitions precisely is essential for proving properties about relations, functions, and cardinalities.

CARTESIAN PRODUCT
A Γ— B = { (a, b) | a ∈ A ∧ b ∈ B }
A and B are sets. Each element of A Γ— B is an ordered pair (a, b). The Kuratowski definition encodes (a, b) as {{a}, {a, b}}, ensuring (a, b) = (c, d) if and only if a = c and b = d.
CARDINALITY OF CARTESIAN PRODUCT
|A Γ— B| = |A| Γ— |B|
For finite sets, the cardinality of the product equals the arithmetic product of the individual cardinalities. This follows directly from the multiplication principle in combinatorics.
POWER SET
𝒫(A) = { S | S βŠ† A }
The power set 𝒫(A) contains every subset S of A, including the empty set βˆ… and A itself. Each element of 𝒫(A) is a set, not an element of A.
CARDINALITY OF POWER SET
|𝒫(A)| = 2^|A|
Each element of A is either included or excluded from a given subset, yielding 2 independent binary choices. By the multiplication principle, the total number of subsets is 2ⁿ where n = |A|. This result holds for finite A and generalizes via Cantor's theorem to show that 𝒫(A) always has strictly greater cardinality than A, even for infinite sets.

Several algebraic properties connect the Cartesian product to other set operations. The product distributes over union: A Γ— (B βˆͺ C) = (A Γ— B) βˆͺ (A Γ— C), and similarly over intersection: A Γ— (B ∩ C) = (A Γ— B) ∩ (A Γ— C). However, the Cartesian product is not commutative in general β€” A Γ— B β‰  B Γ— A unless A = B or one of them is empty β€” because the ordered pairs (a, b) and (b, a) are distinct objects. Likewise, it is not associative in the strict sense: (A Γ— B) Γ— C β‰  A Γ— (B Γ— C) because ((a, b), c) and (a, (b, c)) are different ordered pairs, though there is a natural bijection between them, so we often abuse notation and write A Γ— B Γ— C for the set of ordered triples.

πŸ”— Connection to Functions
A function f: A β†’ B is formally a subset of A Γ— B satisfying the property that for each a ∈ A there exists exactly one b ∈ B such that (a, b) ∈ f. Equivalently, the set of all functions from A to B can be identified with the set Bᴬ, which has cardinality |B|^|A|. When B = {0, 1}, the set of all functions from A to {0, 1} is in bijection with 𝒫(A) β€” each function encodes a characteristic function of a subset β€” which gives another proof that |𝒫(A)| = 2^|A|.
SECTION 5

Power Set Lattice & Detailed Breakdown

The power set of a finite set has a rich internal structure best visualized as a Hasse diagram, which is a type of lattice diagram where subsets are arranged by inclusion. The empty set sits at the bottom, the full set at the top, and an edge connects two subsets whenever one is obtained from the other by adding exactly one element. This lattice is isomorphic to the Boolean lattice Bβ‚™, and it appears throughout combinatorics, logic, and computer science. The following diagram shows 𝒫({a, b, c}), which contains 2Β³ = 8 subsets.

The Hasse diagram of 𝒫({a, b, c}) shows 8 subsets arranged in four levels by cardinality. Edges connect each subset to its immediate supersets (those formed by adding one element). The number of subsets at each level follows the binomial coefficients C(3, k).

The lattice structure reveals a beautiful symmetry: the number of subsets of size k in an n-element set is the binomial coefficient C(n, k), and these coefficients sum to 2ⁿ by the binomial theorem: 2ⁿ = Ξ£ C(n, k) for k = 0 to n. This connection between the power set cardinality and the binomial theorem is one of the most elegant bridges between set theory and algebra. Furthermore, the lattice (𝒫(A), βŠ†) is a Boolean algebra under the operations of union, intersection, and complement, making it a cornerstone example in both order theory and logic.

Growth of the power set: each additional element doubles the number of subsets.
Set A|A||𝒫(A)|Subsets Listed
βˆ…01{ βˆ… }
{a}12{ βˆ…, {a} }
{a, b}24{ βˆ…, {a}, {b}, {a, b} }
{a, b, c}38{ βˆ…, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }
{a, b, c, d}41616 subsets (too many to list compactly)
SECTION 6

Worked Example

Let us work through a comprehensive example that exercises both the Cartesian product and the power set. Let A = {1, 2} and B = {a, b, c}. We will compute A Γ— B, B Γ— A, 𝒫(A), and 𝒫(A Γ— B) step by step.

Computing Cartesian Products and Power Sets
1
Step 1 β€” Compute A Γ— BFor each element of A, pair it with every element of B. From a = 1: (1, a), (1, b), (1, c). From a = 2: (2, a), (2, b), (2, c). We expect |A| Γ— |B| = 2 Γ— 3 = 6 ordered pairs.
A Γ— B = { (1, a), (1, b), (1, c), (2, a), (2, b), (2, c) }
2
Step 2 β€” Compute B Γ— ANow reverse the factors. For each element of B, pair it with every element of A. This yields pairs like (a, 1) and (a, 2), which are distinct from (1, a) and (2, a) because order matters. We still get |B| Γ— |A| = 3 Γ— 2 = 6 pairs, but they are different pairs.
B Γ— A = { (a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2) } β‰  A Γ— B
3
Step 3 β€” Compute 𝒫(A)Enumerate all subsets of A = {1, 2}. For each element, decide independently whether to include or exclude it. With 2 elements we expect 2Β² = 4 subsets: the empty set, two singletons, and the full set.
𝒫(A) = { βˆ…, {1}, {2}, {1, 2} }
4
Step 4 β€” Determine |𝒫(A Γ— B)|The set A Γ— B has 6 elements (computed in Step 1). The power set of a 6-element set has 2⁢ = 64 elements. Listing all 64 subsets is impractical, but the cardinality follows directly from the formula. Each of the 6 ordered pairs is independently included or excluded.
|𝒫(A Γ— B)| = 2⁢ = 64
5
Step 5 β€” Verify a Key PropertyCheck the distributive property: A Γ— (B ∩ C) = (A Γ— B) ∩ (A Γ— C). Let C = {b, c, d}. Then B ∩ C = {b, c}. The left side gives A Γ— {b, c} = {(1,b), (1,c), (2,b), (2,c)}. For the right side, A Γ— C = {(1,b), (1,c), (1,d), (2,b), (2,c), (2,d)}, and (A Γ— B) ∩ (A Γ— C) picks out only pairs present in both: {(1,b), (1,c), (2,b), (2,c)}, confirming equality.
A Γ— (B ∩ C) = (A Γ— B) ∩ (A Γ— C) = { (1,b), (1,c), (2,b), (2,c) } βœ“
SECTION 7

Properties, Pitfalls, and Comparisons

Students often confuse the Cartesian product with set intersection or union, and confuse elements of a power set with elements of the original set. Understanding the precise algebraic properties of each construction β€” and where the common mistakes arise β€” is essential for working confidently with these objects.

Comparison of key properties of Cartesian products and power sets.
PropertyCartesian Product (A Γ— B)Power Set (𝒫(A))
Elements areOrdered pairs (a, b)Sets (subsets of A)
Cardinality|A| Γ— |B| (multiplicative)2^|A| (exponential)
Commutative?No. A Γ— B β‰  B Γ— A in generalN/A (unary operation)
Associative?Not strictly, but naturally isomorphicN/A (unary operation)
Distributes over βˆͺ?Yes: A Γ— (B βˆͺ C) = (A Γ— B) βˆͺ (A Γ— C)𝒫(A βˆͺ B) β‰  𝒫(A) βˆͺ 𝒫(B) in general
Empty set behaviorA Γ— βˆ… = βˆ…π’«(βˆ…) = {βˆ…}, with |𝒫(βˆ…)| = 1
⚠️ Common Mistake
Students frequently write statements like "2 ∈ 𝒫({1, 2, 3})" β€” but this is false. The elements of the power set are sets, not individual elements. The correct statement is {2} ∈ 𝒫({1, 2, 3}), and also 2 ∈ {1, 2, 3}. Confusing the membership relation (∈) with the subset relation (βŠ†) is the single most common error in power set problems.
✦ KEY TAKEAWAY
The Cartesian product and the power set represent two fundamentally different ways of generating combinatorial complexity. The product grows multiplicatively, combining elements across sets, while the power set grows exponentially, enumerating all possible selections within a single set. In database theory, the Cartesian product corresponds to the cross-join of two tables, while the power set corresponds to enumerating all possible query filters on a table's rows.
SECTION 8

Connections to Advanced Theory

The Cartesian product and power set are not merely computational tools for finite sets; they are gateways to some of the deepest ideas in mathematics. Cantor's theorem β€” that there is no surjection from A onto 𝒫(A) β€” implies that the hierarchy of infinite cardinalities never terminates. The Cartesian product, meanwhile, generalizes to infinite products that underpin topology (the product topology), measure theory (product Οƒ-algebras), and functional analysis (sequence spaces as ℝℕ). Understanding these finite constructions thoroughly prepares you for these powerful generalizations.

How the finite constructions in this lesson generalize to advanced mathematics.
Concept in This LessonAdvanced GeneralizationWhere It Appears
A Γ— B (binary product)∏ᡒ Aα΅’ (arbitrary indexed product)Topology, measure theory, Tychonoff's theorem
𝒫(A) with |𝒫(A)| = 2^|A|Cantor's theorem: |A| < |𝒫(A)| for all ACardinal arithmetic, continuum hypothesis
Subsets as characteristic functionsMeasurable sets, indicator functionsProbability theory, Lebesgue integration
Functions as subsets of A Γ— BMorphisms in category theoryAbstract algebra, homological algebra
Power set lattice (𝒫(A), βŠ†)Boolean algebras, Οƒ-algebrasLogic, automata theory, formal verification

In your upcoming study of relations and functions, you will see the Cartesian product repeatedly: a binary relation on A and B is simply a subset R βŠ† A Γ— B, and a function is a relation satisfying an additional uniqueness condition. The power set appears whenever you study event spaces in probability (the set of all possible events is 𝒫(Ξ©) for the sample space Ξ©) or when you define topologies (a topology on X is a particular subcollection of 𝒫(X) closed under unions and finite intersections). Mastering these basic constructions now will make these advanced structures feel natural rather than mysterious.

SECTION 9

Practice Problems

PROBLEM 1 β€” CONCEPTUAL
Explain why A Γ— B β‰  B Γ— A in general, even though |A Γ— B| = |B Γ— A|. Under what conditions does A Γ— B = B Γ— A?
PROBLEM 2 β€” BASIC CALCULATION
Let C = {x, y, z} and D = {1, 2}. List all elements of C Γ— D and compute |𝒫(D)|. Then list the elements of 𝒫(D).
PROBLEM 3 β€” INTERMEDIATE
Let A = {1, 2, 3} and B = {2, 3, 4}. Compute (A ∩ B) Γ— (A βˆͺ B). Then verify that (A ∩ B) Γ— (A βˆͺ B) = (A Γ— (A βˆͺ B)) ∩ (B Γ— (A βˆͺ B)).
PROBLEM 4 β€” APPLIED
A database has a table Students with 500 rows and a table Courses with 80 rows. A cross-join computes the Cartesian product of the two tables. If the system then filters this cross-join to keep only valid enrollments, and there are 2,400 actual enrollment records, what percentage of the full Cartesian product represents actual enrollments? Also, if an administrator wants to define a set of possible course bundles (subsets of Courses), how many possible bundles exist?
PROBLEM 5 β€” CRITICAL THINKING
Prove that for any finite set A with |A| = n, the number of elements in 𝒫(𝒫(A)) is 2^(2ⁿ). Then compute |𝒫(𝒫({a, b}))| and explain why iterating the power set operator grows so rapidly.
SUMMARY

Summary & Review

The Cartesian product A Γ— B constructs the set of all ordered pairs (a, b) with a ∈ A and b ∈ B, yielding a set of cardinality |A| Γ— |B|. This construction is not commutative β€” A Γ— B β‰  B Γ— A in general β€” and it distributes over union and intersection. The Cartesian product provides the formal foundation for relations and functions, both of which are defined as subsets of a Cartesian product.

The power set 𝒫(A) collects every subset of A into a single set, always including βˆ… and A itself. Its cardinality is 2ⁿ, reflecting the binary include-or-exclude choice for each of the n elements. The Hasse diagram reveals that the power set forms a Boolean lattice under subset inclusion, and Cantor's theorem guarantees that the power set of any set β€” finite or infinite β€” has strictly greater cardinality than the original set. Together, these two constructions are indispensable building blocks for discrete mathematics, combinatorics, and the foundations of analysis.

Varsity Tutors β€’ Discrete Math β€’ Cartesian products and power sets