6.1: Cartesian Product
( \newcommand{\kernel}{\mathrm{null}\,}\)
We discussed unions and intersections in Section 3.3. The Cartesian product is another important set operation. Before introducing it, let us recall the notation for an ordered pair.
For any objects x and y, mathematicians use (x,y) to denote the ordered pair whose first coordinate is x and whose second coordinate is y. It is important to know that the order matters: (x,y) is usually not the same as (y,x). (That is why these are called ordered pairs. Notice that sets are not like this: sets are unordered, so {x,y} is always the same as {y,x}.) It is important to realize that: (x1,y1)=(x2,y2)⇔x1=x2 and y1=y2
A special case of the Cartesian product is familiar to all algebra students: recall that (6.1.3) R2={(x,y)∣x∈R,y∈R}
is the set of all ordered pairs of real numbers. This is the “coordinate plane” (or “xy-plane”) that is used to draw the graphs of functions.
The formula y=f(x) often appears in elementary algebra, and, in that subject, the variables x and y represent real numbers. However, advanced math courses allow x and y to be elements of any sets A and B, not just from R. Therefore, it is important to generalize the above example by replacing the two appearances of R in the right-hand side of Equation 6.1.3 with arbitrary sets A and B:
For any sets A and B, we let A×B={(a,b)∣a∈A,b∈B}.
This notation means, for all x, that x∈A×B iff ∃a∈A,∃b∈B,x=(a,b).
The set A×B is called the Cartesian product of A and B.
- R×R=R2.
- {1,2,3}×{a,b}={(1,a),(1, b),(2,a),(2, b),(3,a),(3, b)}.
- {a,b}×{1,2,3}={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}.
By comparing (2) and (3), we see that × is not commutative: A×B is usually not equal to B×A.
Specify each set by listing its elements.
- {a,i}×{n,t}=
- {Q,K}× {♣, ♦, ♥, ♠} =
- {1,2,3}×{3,4,5}=
We will prove in Theorem 9.1.18 that #(A×B)=#A⋅#B.
In other words: cardinality of a Cartesian product is the product of the cardinalities.
For now, let us just give an informal justification:
Suppose #A=m and #B=n. Then, by listing the elements of these sets, we may write A={a1,a2,a3,…,am} and B={b1,b2,b3,…,bn}.
The elements of A×B are: (a1,b1),(a1,b2),(a1,b3),⋯(a1,bn)(a2,b1),(a2,b2),(a2,b3),⋯(a2,bn),(a3,b1),(a3,b2),(a3,b3),⋯(a3,bn),⋮⋮⋮⋱⋮(am,b1),(am,b2),(am,b3),⋯(am,bn).
In this array,
- each row has exactly n elements, and
- there are m rows,
so the number of elements is the product mn=#A⋅#B.
Here are some examples of proofs involving Cartesian products.
If A and B are nonempty sets, and A×B=B×A, then A=B.
Solution
PROOF.
Assume A and B are nonempty sets, such that A×B=B×A. It suffices to show A⊂B and B⊂A. By symmetry, we need only show A⊂B.
Let a0 be an arbitrary element of A. Since B is nonempty, there exists some b0∈B. Then (a0,b0)∈A×B=B×A={(b,a)∣b∈B,a∈A},
so there exist b∈B and a∈A, such that (a0,b0)=(b,a). Therefore, a0=b (and b0=a, but we do not need that fact). Hence a0=b∈B.
If B is disjoint from C, then A×B is disjoint from A×C.
Solution
PROOF.
We prove the contrapositive: Assume A×B is not disjoint from A×C, and we will show B is not disjoint from C.
By assumption, the intersection of A×B and A×C is not empty, so we may choose some x∈(A×B)∩(A×C).
Then:
- Since x∈A×B, there exist a1∈A and b∈B, such that x=(a1,b).
- Since x∈A×C, there exist a2∈A and c∈C, such that x=(a2,c).
Hence (a1,b)=x=(a2,c), so b=c. Now b∈B and b=c∈C, so b∈B∩C. Therefore B∩C≠∅, so, as desired, B and C are not disjoint.
When reading the proof above, you may have noticed that the variable x (a single letter) was used to represent an ordered pair (a,b). There is nothing wrong with this, because the ordered pair is a single object, and a variable can represent any mathematical object at all, whether it is an element of a set, or an entire set, or a function, or an ordered pair, or something else.
Assume A, B, and C are sets. Prove A×(B∪C)=(A×B)∪(A×C).
Solution
PROOF.
(⊂) Given x∈(A×B)∪(A×C), we have x∈A×B or x∈A×C. By symmetry, we may assume x∈A×B, so x=(a,b) for some a∈A and b∈B. Note that b∈B∪C, so we have a∈A and b∈B∪C. Therefore x=(a,b)∈A×(B∪C)
Since x is an arbitrary element of (A×B)∪(A×C), this implies (A×B)∪(A×C)⊂A×(B∪C).
(⊂) Given (a,x)∈A×(B∪C),, we have a∈A, and either x∈B or x∈C. By symmetry, we may assume x∈B. Then (a,x)∈A×B⊂(A×B)∪(A×C), so (a,x)∈(A×B)∪(A×C). Since (a,x) is an arbitrary element of A×(B∪C), this implies A×(B∪C)⊂(A×B)∪(A×C).
- Suppose A, B, and C are sets.
- Show that if B⊂C, then A×B⊂A×C.
- Show that if A×B=A×C, and A≠∅, then B=C.
- Suppose A is a set.
- Show A×∅=∅.
- Show A×A=∅ if and only if A=∅.
- To say that × is distributive over ∪ means that, for all sets A, B, and C, we have A×(B∪C)=(A×B)∪(A×C) and (B∪C)×A=(B×A)∪(C×A).
The first equation was established in Example 6.1.11. Complete the proof that × is distributive over ∪ by proving the second equation. - Show that × is distributive over ∩. That is, for all sets A, B, and C, we have
- A×(B∩C)=(A×B)∩(A×C), and
- (B∩C)×A=(B×A)∩(C×A).