From Sets of Objects to Sets of Pairs
The previous tutorial, “Proving Set Identities,” used membership conditions to understand and compare sets. We now use the same idea to construct a new set from two given sets. Rather than collecting individual objects from one set, we collect pairs of objects, with one entry selected from each set.
An ordered pair written \((a,b)\) has a first entry \(a\) and a second entry \(b\). The order matters: in general, \((a,b)\) and \((b,a)\) are different ordered pairs. We use the standard convention that two ordered pairs are equal exactly when their corresponding entries agree: $$ (a,b)=(c,d)\quad\Longleftrightarrow\quad a=c\text{ and }b=d. $$ The next tutorial examines ordered pairs more closely. For now, this convention lets us read membership in a Cartesian product precisely.
Definition (Cartesian Product). Let \(A\) and \(B\) be sets. Their Cartesian product, written \(A\times B\), is the set of all ordered pairs whose first entry belongs to \(A\) and whose second entry belongs to \(B\): $$ A\times B=\{(a,b):a\in A\text{ and }b\in B\}. $$
Equivalently, for an ordered pair \((x,y)\), $$ (x,y)\in A\times B \quad\Longleftrightarrow\quad x\in A\text{ and }y\in B. $$ This equivalence is the main test for product membership. Both requirements must hold: the first coordinate is checked against the first factor, and the second coordinate against the second factor.
Listing a Product and Respecting the Order
When both factors are finite, list every possible choice for the first entry alongside every possible choice for the second. Each choice of a first entry must be paired with each choice of a second entry. Repetitions do not arise from different listings of the same pair, since a set contains each of its elements only once.
Worked Example: Listing Every Pair
Let \(A=\{r,s\}\) and \(B=\{2,5,7\}\). The first entry must be either \(r\) or \(s\), and the second entry must be one of \(2,5,7\). Pairing each first entry with all three second entries gives $$ A\times B = \{(r,2),(r,5),(r,7),(s,2),(s,5),(s,7)\}. $$ For instance, \((s,5)\in A\times B\) because \(s\in A\) and \(5\in B\). But \((2,s)\notin A\times B\): its first coordinate \(2\) does not belong to \(A\), and its second coordinate \(s\) does not belong to \(B\). Reversing the entries does not preserve membership automatically.
The factors do not usually commute. Even if the same objects appear in both factors, changing their positions can change the collection of ordered pairs. There are special cases in which the two products are equal, but equality is not automatic.
Worked Example: Reversing the Factors
Let \(A=\{u,v\}\) and \(B=\{v,w\}\), where \(u,v,w\) are distinct objects. Then $$ A\times B=\{(u,v),(u,w),(v,v),(v,w)\} $$ while $$ B\times A=\{(v,u),(v,v),(w,u),(w,v)\}. $$ The pair \((u,v)\) belongs to \(A\times B\), because \(u\in A\) and \(v\in B\). It does not belong to \(B\times A\), because its first coordinate \(u\) is not in \(B\). Thus \(A\times B\ne B\times A\) for these sets.
Membership and Set Operations
The definition turns product membership into two simultaneous membership conditions. This connects Cartesian products to the union and intersection rules already established in this course. A product with a union in one coordinate separates into a union of products; a product with an intersection in one coordinate separates into an intersection of products.
Theorem (Products and Unions and Intersections). Let \(A,B,C\) be sets. Then $$ A\times(B\cup C)=(A\times B)\cup(A\times C) $$ and $$ A\times(B\cap C)=(A\times B)\cap(A\times C). $$
Proof. Let \((x,y)\) be any ordered pair. By the definition of Cartesian product and the membership characterization of a union, $$ \begin{aligned} (x,y)\in A\times(B\cup C) &\Longleftrightarrow x\in A\text{ and }y\in B\cup C\\ &\Longleftrightarrow x\in A\text{ and }(y\in B\text{ or }y\in C)\\ &\Longleftrightarrow (x\in A\text{ and }y\in B) \text{ or }(x\in A\text{ and }y\in C)\\ &\Longleftrightarrow (x,y)\in(A\times B)\cup(A\times C). \end{aligned} $$ The equivalence holds for every ordered pair, so the two sets have the same elements and are equal.
For the intersection identity, again take an arbitrary ordered pair \((x,y)\). Then $$ \begin{aligned} (x,y)\in A\times(B\cap C) &\Longleftrightarrow x\in A\text{ and }y\in B\cap C\\ &\Longleftrightarrow x\in A\text{ and }y\in B\text{ and }y\in C\\ &\Longleftrightarrow (x\in A\text{ and }y\in B) \text{ and }(x\in A\text{ and }y\in C)\\ &\Longleftrightarrow (x,y)\in(A\times B)\cap(A\times C). \end{aligned} $$ Here the repeated condition \(x\in A\) is equivalent to requiring it in both product memberships. Since membership agrees for every ordered pair, equality follows. \(\square\)
The same reasoning applies when the union or intersection is in the first coordinate. For example, $$ (A\cup B)\times C=(A\times C)\cup(B\times C). $$ In each case, translate product membership into coordinate conditions and then use the membership definition for the relevant set operation.
Worked Example: Using a Product Identity
Let \(A=\{1,3\}\), \(B=\{a,b\}\), and \(C=\{b,c\}\). Then \(B\cup C=\{a,b,c\}\), so $$ A\times(B\cup C) = \{(1,a),(1,b),(1,c),(3,a),(3,b),(3,c)\}. $$ On the other side, $$ A\times B=\{(1,a),(1,b),(3,a),(3,b)\} $$ and $$ A\times C=\{(1,b),(1,c),(3,b),(3,c)\}. $$ Their union is $$ (A\times B)\cup(A\times C) = \{(1,a),(1,b),(1,c),(3,a),(3,b),(3,c)\}. $$ The two sides agree, as the theorem predicts. The example also shows why a pair such as \((3,c)\) is included: its second entry belongs to \(C\), even though it does not belong to \(B\).
Products and Subset Inclusion
Inclusion between factors gives inclusion between products. If \(A\subseteq C\) and \(B\subseteq D\), then each first coordinate allowed by \(A\) is also allowed by \(C\), and each second coordinate allowed by \(B\) is also allowed by \(D\). The converse requires care: an empty factor can make a product empty, in which case product inclusion may reveal nothing about the other factor.
Theorem (Subset Inclusion for Cartesian Products). Let \(A,B,C,D\) be sets, and suppose \(A\ne\varnothing\) and \(B\ne\varnothing\). Then $$ A\times B\subseteq C\times D \quad\Longleftrightarrow\quad A\subseteq C\text{ and }B\subseteq D. $$
Proof. First suppose \(A\times B\subseteq C\times D\). We prove \(A\subseteq C\). Let \(a\in A\) be arbitrary. Since \(B\ne\varnothing\), choose \(b\in B\). Then \((a,b)\in A\times B\), so the assumed inclusion gives \((a,b)\in C\times D\). By the definition of product membership, \(a\in C\). Since \(a\) was arbitrary, \(A\subseteq C\).
We also prove \(B\subseteq D\). Let \(b\in B\) be arbitrary. Since \(A\ne\varnothing\), choose \(a\in A\). Then \((a,b)\in A\times B\), and hence \((a,b)\in C\times D\). Product membership gives \(b\in D\). Thus \(B\subseteq D\).
Conversely, suppose \(A\subseteq C\) and \(B\subseteq D\). Let \((a,b)\in A\times B\). By definition, \(a\in A\) and \(b\in B\). The assumed inclusions imply \(a\in C\) and \(b\in D\). Therefore \((a,b)\in C\times D\), proving \(A\times B\subseteq C\times D\). Both directions establish the claimed equivalence. \(\square\)
The nonempty hypotheses in the reverse direction are essential. If \(A=\varnothing\), then \(A\times B=\varnothing\) regardless of \(B\). The empty product is a subset of every set, even if \(B\) is not a subset of \(D\). Thus an inclusion between products does not always let us infer inclusion between both factors.
Worked Example: Checking Product Inclusion
Let \(A=\{p,q\}\), \(B=\{1,2\}\), \(C=\{p,q,r\}\), and \(D=\{0,1,2,3\}\). We have \(A\subseteq C\) and \(B\subseteq D\), so the subset theorem gives \(A\times B\subseteq C\times D\). For a direct check, $$ A\times B=\{(p,1),(p,2),(q,1),(q,2)\}. $$ Every listed pair also belongs to \(C\times D\), since its first coordinate is in \(C\) and its second coordinate is in \(D\). Conversely, the theorem does not say that \(C\times D\subseteq A\times B\); for example, \((r,0)\in C\times D\) but \((r,0)\notin A\times B\).
Empty Factors and Common Misreadings
If either factor is empty, there is no way to form an ordered pair satisfying both coordinate requirements. Consequently, $$ A\times\varnothing=\varnothing \qquad\text{and}\qquad \varnothing\times A=\varnothing $$ for every set \(A\). To verify the first equality, an element of \(A\times\varnothing\) would have to be a pair \((a,b)\) with \(b\in\varnothing\), which is impossible. The second follows because its first coordinate would have to belong to \(\varnothing\).
A frequent error is to treat \(A\times B\) as though it were a set of the elements of \(A\) and \(B\) mixed together. It is instead a set of ordered pairs. For example, if \(A=\{p\}\) and \(B=\{7\}\), then \(A\times B=\{(p,7)\}\), not \(\{p,7\}\). Another common error is to reverse the coordinate roles or assume \(A\times B=B\times A\). The definition fixes which factor supplies each coordinate.
| Expression | Membership requirement | What it describes |
|---|---|---|
| \(A\cup B\) | \(x\in A\) or \(x\in B\) | Objects belonging to at least one set |
| \(A\cap B\) | \(x\in A\) and \(x\in B\) | Objects common to both sets |
| \(A\times B\) | \(x\in A\) and \(y\in B\) | Ordered pairs with specified coordinate roles |
Check Your Understanding
- State the definition of \(A\times B\) and the membership test for a pair \((x,y)\).
- If \(A=\{m,n\}\) and \(B=\{0,4\}\), list every element of \(A\times B\).
- Give a reason that \(A\times B\) and \(B\times A\) need not be equal.
- Write the identity for \(A\times(B\cup C)\) and explain how membership in its left side is tested.
- In the product subset theorem, why are \(A\ne\varnothing\) and \(B\ne\varnothing\) needed to infer both factor inclusions?
- What is \(A\times\varnothing\), and why does this hold for every set \(A\)?