Building Pairs from Sets
Suppose a café offers two drink sizes,
\[ S=\{\text{small},\text{large}\}, \]and three drink types,
\[ D=\{\text{coffee},\text{tea},\text{cocoa}\}. \]A customer can combine one size with one drink type.
For example,
\[ (\text{small},\text{coffee}) \]represents one possible choice.
If we list every possible pairing of a size with a drink, we obtain a new set:
\[ \{ (\text{small},\text{coffee}), (\text{small},\text{tea}), (\text{small},\text{cocoa}), (\text{large},\text{coffee}), (\text{large},\text{tea}), (\text{large},\text{cocoa}) \}. \]This set of all possible ordered pairings is called a Cartesian product.
Ordered Pairs
An ordered pair is written
\[ (a,b). \]The first entry is called the first component, and the second entry is called the second component.
The word ordered matters.
In general,
\[ (a,b)\neq(b,a). \]For example,
\[ (2,5)\neq(5,2). \]The same two numbers appear, but their positions are different.
Equality of Ordered Pairs
Two ordered pairs are equal exactly when their corresponding components are equal:
\[ (a,b)=(c,d) \]if and only if
\[ a=c \quad\text{and}\quad b=d. \]For example,
\[ (x,7)=(3,7) \]requires
\[ x=3. \]Ordered pairs therefore preserve positional information that ordinary sets do not.
The Cartesian Product
Let \(A\) and \(B\) be sets.
The Cartesian product of \(A\) and \(B\), written
\[ A\times B, \]is the set of all ordered pairs whose first component comes from \(A\) and whose second component comes from \(B\).
In set-builder notation,
\[ \boxed{ A\times B = \{(a,b)\mid a\in A,\ b\in B\} } \]So if
\[ A=\{1,2\} \]and
\[ B=\{x,y,z\}, \]then
\[ A\times B = \{ (1,x),(1,y),(1,z), (2,x),(2,y),(2,z) \}. \]Every element of \(A\) is paired with every element of \(B\).
Why Order Matters
Cartesian products usually change when we reverse the order of the sets.
Using
\[ A=\{1,2\} \]and
\[ B=\{x,y\}, \]we have
\[ A\times B = \{ (1,x),(1,y),(2,x),(2,y) \}. \]But
\[ B\times A = \{ (x,1),(x,2),(y,1),(y,2) \}. \]Therefore, in general,
\[ \boxed{A\times B\neq B\times A}. \]The two sets may have the same number of elements, but their ordered pairs are different mathematical objects.
When Could They Be Equal?
If \(A=B\), then reversing the factors does not change the product:
\[ A\times A=A\times A. \]For different sets, however, equality is not something we should assume.
Listing a Cartesian Product
A reliable way to build a finite Cartesian product is to work systematically.
Let
\[ A=\{a,b,c\} \]and
\[ B=\{1,2\}. \]Start with the first element of \(A\), \(a\), and pair it with every element of \(B\):
\[ (a,1),(a,2). \]Then do the same with \(b\):
\[ (b,1),(b,2). \]Then with \(c\):
\[ (c,1),(c,2). \]So
\[ A\times B = \{ (a,1),(a,2), (b,1),(b,2), (c,1),(c,2) \}. \]This row-by-row method helps prevent missing pairs.
Cardinality of a Cartesian Product
Suppose \(A\) and \(B\) are finite sets.
If \(A\) has \(m\) elements and \(B\) has \(n\) elements, then each of the \(m\) elements of \(A\) can be paired with each of the \(n\) elements of \(B\).
Therefore,
\[ \boxed{|A\times B|=|A|\cdot|B|}. \]Example
If
\[ |A|=4 \]and
\[ |B|=7, \]then
\[ |A\times B| = 4\cdot7 = 28. \]We can know the number of ordered pairs without listing them all.
The Multiplication Principle Appears Again
This formula is an example of the same multiplication principle used in counting:
If one decision has \(m\) possibilities and a second independent decision has \(n\) possibilities, then there are
\[ mn \]possible ordered combinations.
Cartesian products give that counting principle a set-theoretic form.
Products of a Set with Itself
A particularly important case is
\[ A\times A. \]This contains all ordered pairs whose two components both come from \(A\).
For example, if
\[ A=\{1,2,3\}, \]then
\[ A\times A = \{ (1,1),(1,2),(1,3), (2,1),(2,2),(2,3), (3,1),(3,2),(3,3) \}. \]Because
\[ |A|=3, \]we have
\[ |A\times A|=3^2=9. \]The notation
\[ A^2 \]is sometimes used as shorthand for
\[ A\times A. \]This idea becomes especially useful when we study coordinate systems.
The Coordinate Plane
The familiar Cartesian coordinate plane is itself a Cartesian product.
Every point in the plane is an ordered pair
\[ (x,y) \]of real numbers.
Therefore, the entire real coordinate plane can be written as
\[ \mathbb{R}\times\mathbb{R}. \]More compactly,
\[ \mathbb{R}^2. \]So when we graph the point
\[ (3,-2), \]we are selecting one element of
\[ \mathbb{R}^2. \]A Curve Is a Set of Ordered Pairs
Consider the line
\[ y=2x+1. \]Its graph can be described as the set
\[ L= \{(x,y)\in\mathbb{R}^2\mid y=2x+1\}. \]This is a subset of the Cartesian plane:
\[ L\subseteq\mathbb{R}^2. \]This gives us a powerful connection:
\[ \boxed{ \text{graph} = \text{set of ordered pairs} } \]The geometric picture and the set-theoretic description are two views of the same object.
Relations as Subsets of Cartesian Products
Cartesian products provide the universe of possible pairings between two sets.
A relation chooses some of those possible pairs.
Suppose
\[ A=\{1,2,3\} \]and
\[ B=\{a,b\}. \]Then
\[ A\times B = \{ (1,a),(1,b), (2,a),(2,b), (3,a),(3,b) \}. \]Now suppose we choose
\[ R=\{(1,a),(2,a),(3,b)\}. \]Because every ordered pair in \(R\) comes from \(A\times B\),
\[ R\subseteq A\times B. \]That is exactly how a relation from \(A\) to \(B\) will be defined.
So the progression is:
\[ \boxed{ \text{sets} \longrightarrow \text{Cartesian product} \longrightarrow \text{relations} \longrightarrow \text{functions} } \]This is why Cartesian products appear immediately before relations in the development of set theory.
Products of More Than Two Sets
The same idea can be extended beyond pairs.
If we have sets \(A\), \(B\), and \(C\), then
\[ A\times B\times C \]consists of ordered triples
\[ (a,b,c) \]with
\[ a\in A, \qquad b\in B, \qquad c\in C. \]For finite sets,
\[ |A\times B\times C| = |A||B||C|. \]Three-Dimensional Space
Every point in ordinary three-dimensional coordinate space has the form
\[ (x,y,z). \]Thus three-dimensional real space is
\[ \mathbb{R}^3 = \mathbb{R}\times\mathbb{R}\times\mathbb{R}. \]The Cartesian-product idea therefore scales naturally from lists of choices to geometry in higher dimensions.
Practical Applications
Product Configurations
Suppose a manufacturer offers
\[ C=\{\text{black},\text{white},\text{silver}\} \]for color and
\[ S=\{\text{small},\text{medium},\text{large}\} \]for size.
Every possible color-size configuration belongs to
\[ C\times S. \]There are
\[ 3\cdot3=9 \]possible configurations.
Scheduling
Suppose
\[ D=\{\text{Monday},\text{Tuesday},\text{Wednesday}\} \]and
\[ T=\{9{:}00,10{:}00,11{:}00\}. \]The set
\[ D\times T \]contains every possible day-time appointment slot.
Database Relationships
If \(E\) is a set of employees and \(P\) is a set of projects, then
\[ E\times P \]contains every possible employee-project assignment.
The actual assignments form a subset of that Cartesian product.
Computer Graphics
Pixels can be located by ordered pairs such as
\[ (x,y). \]A rectangular screen can therefore be modeled using a Cartesian product of horizontal and vertical coordinate sets.
Tables and Spreadsheets
If \(R\) is the set of row positions and \(C\) the set of column positions, then every cell location can be represented by an ordered pair
\[ (r,c)\in R\times C. \]The Cartesian product is the mathematical structure behind the grid.
Worked Examples
Example 1: Listing a Product
Let
\[ A=\{1,2\} \]and
\[ B=\{a,b,c\}. \]Then
\[ A\times B = \{ (1,a),(1,b),(1,c), (2,a),(2,b),(2,c) \}. \]Example 2: Reversing the Order
Using the same sets,
\[ B\times A = \{ (a,1),(a,2), (b,1),(b,2), (c,1),(c,2) \}. \]Although both products contain six elements,
\[ A\times B\neq B\times A. \]Example 3: Cardinality without Listing
Suppose
\[ |X|=8 \]and
\[ |Y|=5. \]Then
\[ |X\times Y| = 8\cdot5 = 40. \]Example 4: Testing Membership
Let
\[ A=\{1,2,3\} \]and
\[ B=\{x,y\}. \]Is
\[ (2,y)\in A\times B? \]Yes. The first component satisfies
\[ 2\in A \]and the second satisfies
\[ y\in B. \]Therefore,
\[ (2,y)\in A\times B. \]But
\[ (y,2)\notin A\times B \]because \(y\notin A\).
Example 5: Coordinate Membership
Let
\[ R= \{(x,y)\in\mathbb{R}^2\mid y=x^2\}. \]Is \((3,9)\in R\)?
Test the condition:
\[ 9=3^2. \]This is true, so
\[ (3,9)\in R. \]Is \((3,8)\in R\)?
\[ 8\neq3^2, \]so
\[ (3,8)\notin R. \]Example 6: Three Factors
Suppose a meal consists of one entrée, one side, and one drink. There are \(4\) entrées, \(3\) sides, and \(5\) drinks.
The set of all meals can be modeled by
\[ E\times S\times D. \]Its cardinality is
\[ 4\cdot3\cdot5=60. \]Therefore there are
\[ \boxed{60} \]possible ordered meal combinations.
Common Errors
1. Forgetting That Ordered Pairs Have Positions
In general,
\[ (a,b)\neq(b,a). \]Changing the order changes the ordered pair.
2. Assuming \(A\times B=B\times A\)
Cartesian products are generally not commutative.
\[ A\times B\neq B\times A. \]3. Missing Some Pairings
Every element of the first set must be paired with every element of the second set.
A systematic row-by-row listing method helps avoid omissions.
4. Multiplying the Elements Instead of the Cardinalities
If
\[ A=\{2,4\} \]and
\[ B=\{3,5\}, \]the Cartesian product is not
\[ \{6,10,12,20\}. \]It contains ordered pairs:
\[ A\times B = \{(2,3),(2,5),(4,3),(4,5)\}. \]5. Confusing \((a,b)\) with \(\{a,b\}\)
An ordered pair preserves position:
\[ (a,b). \]A set does not:
\[ \{a,b\}=\{b,a\}. \]These are different kinds of mathematical objects.
6. Forgetting the Empty-Set Case
If either factor is empty, there are no possible ordered pairs.
\[ A\times\varnothing=\varnothing \]and
\[ \varnothing\times B=\varnothing. \]This also agrees with cardinality:
\[ |A|\cdot0=0. \]Practice
Listing Products
Let
\[ A=\{1,2\} \]and
\[ B=\{r,s\}. \]Find:
- \(A\times B\)
- \(B\times A\)
Check Answers
- \[ A\times B = \{(1,r),(1,s),(2,r),(2,s)\}. \]
- \[ B\times A = \{(r,1),(r,2),(s,1),(s,2)\}. \]
Membership Practice
Let
\[ X=\{a,b,c\} \]and
\[ Y=\{1,2\}. \]Determine whether each statement is true or false.
- \((a,1)\in X\times Y\)
- \((1,a)\in X\times Y\)
- \((c,2)\in X\times Y\)
- \((b,3)\in X\times Y\)
Check Answers
- True.
- False.
- True.
- False, because \(3\notin Y\).
Cardinality Practice
Suppose
\[ |A|=6 \]and
\[ |B|=9. \]Find
\[ |A\times B|. \]Check Answer
\[ |A\times B| = |A||B| = 6\cdot9 = 54. \]Therefore,
\[ \boxed{54}. \]Coordinate Practice
Let
\[ L= \{(x,y)\in\mathbb{R}^2\mid y=3x-1\}. \]Determine whether each point belongs to \(L\).
- \((2,5)\)
- \((0,-1)\)
- \((3,7)\)
Check Answers
- \[ 5=3(2)-1, \] so \[ (2,5)\in L. \]
- \[ -1=3(0)-1, \] so \[ (0,-1)\in L. \]
- \[ 7\neq3(3)-1=8, \] so \[ (3,7)\notin L. \]
The Deeper Idea
A Cartesian product creates a space of possibilities.
If \(A\) contains possible first choices and \(B\) contains possible second choices, then
\[ A\times B \]contains every possible ordered combination.
From there, mathematics can select particular pairs:
\[ R\subseteq A\times B. \]That selected subset becomes a relation.
A function will later impose an additional rule: each allowed input must be paired with exactly one output.
So Cartesian products are not an isolated topic. They establish the space in which relations and functions live.
\[ \boxed{ \text{possible pairings} \longrightarrow \text{relations} \longrightarrow \text{functions} } \]The same construction also gives us coordinate planes, higher-dimensional spaces, tables, grids, configurations, and many practical counting models.
Summary
- An ordered pair is written \[ (a,b). \]
- Order matters: \[ (a,b)\neq(b,a) \] in general.
- Two ordered pairs are equal exactly when corresponding components are equal.
- The Cartesian product of sets \(A\) and \(B\) is \[ A\times B = \{(a,b)\mid a\in A,\ b\in B\}. \]
- Every element of \(A\) is paired with every element of \(B\).
- In general, \[ A\times B\neq B\times A. \]
- For finite sets, \[ |A\times B| = |A||B|. \]
- The product \[ A\times A \] is sometimes written \[ A^2. \]
- The real coordinate plane is \[ \mathbb{R}^2 = \mathbb{R}\times\mathbb{R}. \]
- A relation from \(A\) to \(B\) is a subset of \[ A\times B. \]
- Cartesian products can be extended to ordered triples and higher-dimensional tuples.
Cartesian products turn separate sets into structured combinations. Once we can build the full set of possible ordered pairs, we are ready to study which pairings actually occur. That next step is the theory of relations.
Sets, Relations, and Functions
- Previous: Finite and Infinite Sets and Cardinality
- Sets, Relations, and Functions — return to the lesson directory.