Cartesian Products and Ordered Pairs

Pairs Keep Track of Order

A Cartesian product gathers pairs whose first and second entries come from specified sets. The order of the entries matters: a pair records which entry came from which set. This makes Cartesian products useful for organizing data with two coordinates, and later for describing relations, functions, and spaces with coordinates.

We first make precise what an ordered pair means. One standard set-theoretic definition is the Kuratowski definition $(a,b)=\{\{a\},\{a,b\}\}$. Even when $a=b$, this expression is a set: in that case $(a,a)=\{\{a\}\}$. The important feature of the definition is that the two coordinates can be recovered uniquely.

Theorem (Uniqueness of coordinates): For any $a,b,c,d$, $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$.

Proof. If $a=c$ and $b=d$, substituting these equalities into the Kuratowski definition gives $\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$, so $(a,b)=(c,d)$. Conversely, suppose $(a,b)=(c,d)$. The union of the members of $(a,b)$ is $\{a,b\}$, and the intersection of its members is $\{a\}$. These statements also hold when $a=b$, since then the pair has the single member $\{a\}$. Equality of the two ordered pairs therefore gives $\{a\}=\{c\}$, hence $a=c$, and $\{a,b\}=\{c,d\}$. Substituting $c=a$, we have $\{a,b\}=\{a,d\}$. If $b=a$, the left side is $\{a\}$, so $d=a=b$. If $b\ne a$, then $b\in\{a,d\}$ and $b\ne a$, so $b=d$. Thus both coordinates agree. $\square$

This result justifies checking pairs coordinate by coordinate. For example, $(1,2)\ne(2,1)$, because equality would require $1=2$. An ordered pair is not an unordered two-element set.

Definition and Membership Test

Definition: For sets $A$ and $B$, their Cartesian product is the set $$ A\times B=\{(a,b):a\in A\text{ and }b\in B\}. $$ Thus $(x,y)\in A\times B$ if and only if $x\in A$ and $y\in B$.

The order of the factors corresponds to the order of the coordinates. In $A\times B$, the first coordinate must come from $A$, and the second from $B$. If the factors are subsets of larger sets $X$ and $Y$, then $A\times B$ is a subset of $X\times Y$: each pair in the first product meets the membership conditions for the second.

Worked Example: Listing a Finite Product

Let $A=\{1,3\}$ and $B=\{r,s\}$. List $A\times B$, then decide whether $(3,r)$ and $(r,3)$ belong to it.

For first coordinate $1$, the allowed second coordinates are $r$ and $s$, giving $(1,r)$ and $(1,s)$. For first coordinate $3$, they give $(3,r)$ and $(3,s)$. Therefore $$ A\times B=\{(1,r),(1,s),(3,r),(3,s)\}. $$ To test $(3,r)$, check $3\in A$ and $r\in B$; both hold, so $(3,r)\in A\times B$. To test $(r,3)$, the first coordinate would have to be in $A$, but $r\notin A$; also $3\notin B$. Thus $(r,3)\notin A\times B$.

Check: the displayed list has exactly the pairs obtained by combining each of the two choices from $A$ with each of the two choices from $B$. Each listed pair meets both membership conditions, and any pair in the product must appear by those conditions.

Products and Set Operations

Coordinatewise membership gives exact rules for how products interact with unions and intersections. The same argument works whether or not the sets involved are finite.

Proposition: For any sets $A,C,B,D$, $$ (A\cup C)\times B=(A\times B)\cup(C\times B) $$ and $$ (A\cap C)\times(B\cap D)=(A\times B)\cap(C\times D). $$

Proof. To prove the union identity, take any ordered pair $(x,y)$. It belongs to $(A\cup C)\times B$ exactly when $x\in A\cup C$ and $y\in B$. The first condition means $x\in A$ or $x\in C$, so the pair belongs to $A\times B$ or to $C\times B$. That is exactly membership in $(A\times B)\cup(C\times B)$. Since the two sets have the same members, they are equal.

For the intersection identity, $(x,y)\in(A\cap C)\times(B\cap D)$ exactly when $x\in A$, $x\in C$, $y\in B$, and $y\in D$. These four conditions hold exactly when $(x,y)\in A\times B$ and $(x,y)\in C\times D$, which is membership in $(A\times B)\cap(C\times D)$. Thus the sets are equal. $\square$

Applying the union identity to each coordinate gives $(A\cup C)\times(B\cup D)=(A\times B)\cup(A\times D)\cup(C\times B)\cup(C\times D)$. Each term represents one possible choice of which set supplies each coordinate.

Worked Example: Expanding a Product of Unions

Let $A=\{1,2\}$, $C=\{2,3\}$, $B=\{p\}$, and $D=\{q\}$. Compute both sides of $(A\cup C)\times(B\cup D)=(A\times B)\cup(A\times D)\cup(C\times B)\cup(C\times D)$.

First, $A\cup C=\{1,2,3\}$ and $B\cup D=\{p,q\}$. Hence the left side is $$ \{(1,p),(1,q),(2,p),(2,q),(3,p),(3,q)\}. $$ The four products on the right are $A\times B=\{(1,p),(2,p)\}$, $A\times D=\{(1,q),(2,q)\}$, $C\times B=\{(2,p),(3,p)\}$, and $C\times D=\{(2,q),(3,q)\}$. Their union is therefore $\{(1,p),(1,q),(2,p),(2,q),(3,p),(3,q)\}$, the same set as the left side.

Check: every pair in the left side has first coordinate $1$, $2$, or $3$, and second coordinate $p$ or $q$. The four products on the right cover these choices; the pairs with first coordinate $2$ occur twice among the four products but appear only once in their union.

Comparing Products by Inclusion

If each factor of one product is contained in the corresponding factor of another, then the product is contained as well. The converse needs attention to empty factors: if a product has no pairs, it is contained in every set, no matter what its factors are.

Theorem: For sets $A,B,C,D$, $$ A\times B\subseteq C\times D $$ if and only if either $A=\varnothing$, or $B=\varnothing$, or both $A\subseteq C$ and $B\subseteq D$.

Proof. Suppose first that $A=\varnothing$ or $B=\varnothing$. Then there is no pair with first coordinate in $A$ and second coordinate in $B$, so $A\times B=\varnothing$, which is a subset of $C\times D$. If instead $A\subseteq C$ and $B\subseteq D$, every $(a,b)\in A\times B$ has $a\in C$ and $b\in D$; hence it belongs to $C\times D$.

For the converse, suppose $A\times B\subseteq C\times D$, and suppose neither $A$ nor $B$ is empty. Choose $a_0\in A$ and $b_0\in B$. For any $a\in A$, $(a,b_0)\in A\times B$, so $(a,b_0)\in C\times D$, which gives $a\in C$. Thus $A\subseteq C$. For any $b\in B$, $(a_0,b)\in A\times B\subseteq C\times D$, which gives $b\in D$. Thus $B\subseteq D$. These cases establish the equivalence, including the possibility that a factor is empty. $\square$

Worked Example: Comparing Two Products

Let $A=\{1,2\}$, $B=\{u\}$, $C=\{1,2,3\}$, and $D=\{u,v\}$. Compare $A\times B$ and $C\times D$.

The first product is $A\times B=\{(1,u),(2,u)\}$. The second is $C\times D=\{(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)\}$. The factor comparisons are $A\subseteq C$, since $1,2\in C$, and $B\subseteq D$, since $u\in D$. Thus the theorem gives $A\times B\subseteq C\times D$. Directly, both pairs in $A\times B$, namely $(1,u)$ and $(2,u)$, appear in the second product.

The inclusion is strict: $(3,u)\in C\times D$, because $3\in C$ and $u\in D$, but $3\notin A$, so $(3,u)\notin A\times B$. This direct check agrees with $A\ne C$ and $B\ne D$.

Empty Factors and Equality

Definition: The empty set, written $\varnothing$, has no elements. For any sets $A$ and $B$, $A\times B=\varnothing$ if and only if $A=\varnothing$ or $B=\varnothing$.

If either factor is empty, no ordered pair can satisfy both membership conditions. Conversely, if both factors are nonempty, choose $a\in A$ and $b\in B$; then $(a,b)\in A\times B$, so the product is not empty.

There is a related equality rule. If all four sets $A,B,C,D$ are nonempty, then $A\times B=C\times D$ if and only if $A=C$ and $B=D$. Indeed, equality gives both product inclusions, and the inclusion theorem yields $A\subseteq C$, $B\subseteq D$, $C\subseteq A$, and $D\subseteq B$. The reverse direction follows from substituting equal factors. Without nonemptiness, equality of products need not identify the factors: for example, $\varnothing\times\{0\}=\{1\}\times\varnothing=\varnothing$, although the corresponding first factors differ and the second factors differ.

Worked Example: Products with an Empty Factor

Let $E=\varnothing$, $F=\{a,b\}$, and $G=\{7\}$. Compute $E\times F$, $G\times E$, and $F\times G$.

For $E\times F$, a pair would need a first coordinate in $E$, but $E$ has no elements. Therefore $E\times F=\varnothing$. For $G\times E$, a pair would need a second coordinate in $E$, so $G\times E=\varnothing$. In contrast, $F\times G=\{(a,7),(b,7)\}$: the first coordinate can be $a$ or $b$, and the second coordinate must be $7$.

Check: the last product is nonempty because $a\in F$ and $7\in G$, so $(a,7)\in F\times G$. The first two products have an empty factor and therefore have no possible pair. This confirms that an empty product requires at least one empty factor, not that every factor must be empty.

A Common Pitfall

Wrong calculation: One might treat a pair as unordered and write $\{1,2\}\times\{1\}=\{\{1,2\}\}$. This is incorrect: the product contains ordered pairs, not sets formed by collecting coordinates. The correct calculation is $\{1,2\}\times\{1\}=\{(1,1),(2,1)\}$. In particular, $(1,2)$ is not in this product because its second coordinate $2$ is not in $\{1\}$.

A second common error is to infer $A\subseteq C$ and $B\subseteq D$ from $A\times B\subseteq C\times D$ without checking that the first product is nonempty. For instance, $\varnothing\times\{0\}\subseteq\{1\}\times\{0\}$ holds because the left side is empty, but $\{0\}\not\subseteq\{0\}$ is not the issue; rather, choosing another example, $\varnothing\times\{0\}\subseteq\{1\}\times\varnothing$ also holds while $\{0\}\nsubseteq\varnothing$. The inclusion theorem handles this case by explicitly allowing an empty factor.

Check Your Understanding

Use the coordinate membership rule in each question, and check whether any factor is empty before applying an inclusion criterion.

List $\{a,b\}\times\{1,2\}$ and decide whether $(2,a)$ belongs to it.
For arbitrary sets $A,B,C$, prove $A\times(B\cup C)=(A\times B)\cup(A\times C)$.
Give nonempty sets $A,B,C,D$ for which $A\times B\subsetneq C\times D$.
Can $A\times B$ be empty when both $A$ and $B$ are nonempty? Justify your answer.
Find distinct pairs of factors whose Cartesian products are equal because both products are empty.