The Cartesian Product

Return to Course Outline

Previous Lecture

Misc

Problem set on set proofs (and a little bit about Cartesian products).

Questions?

Cartesian Products

Section 5.4.

Basic Idea

Let A = { red, green, blue, 1 }

Let B = { 0, 1 }

Find A × B. A × B = { (red,0), (green,0), (blue,0), (1,0), (red,1), (green,1), (blue,1), (1,1) }. Each element of A paired with each element of B.

Which of A × B, B × A, A × A, B × B, or none could the following come from:

• The pair (blue, 1)? A × B or A × A. Blue can only come from A, but 1 could come from either A or B.
• How about (blue,green)? A × A
• How about (0,red)? B × A. Notice that the order of arguments to Cartesian product makes a big difference in the pairs produced.
• How about (green,2)? None, neither set contains 2.

What is ∅ × A? ∅ × A = A × ∅ = ∅ because the empty set has no elements from which to form pairs.

Algebraic Relations

Prove part 3 of theorem 5.25 (i.e., if A, B, and C are subsets of some universal set, then (A ∩ B) × C = (A × C) ∩ (B × C)).

Proof: We prove that (A ∩ B) × C = (A × C) ∩ (B × C) by proving that each side of the equality is a subset of the other.

We start by showing that if the pair (u,v) is in (A ∩ B) × C then (u,v) is also in (A × C) ∩ (B × C). Assume (u,v) is in (A ∩ B) × C. Thus u is in (A ∩ B) and v is in C. Furthermore, since u is in (A ∩ B), u is in A and u is in B. Now, with u in A and v in C, (u,v) is in A × C, Similarly, since u is in B, (u,v) is also in B × C. Since (u,v) is in both A × C and B × C, it is in (A × C) ∩ (B × C).

For the other direction, we show that if (u,v) is in (A × C) ∩ (B × C) then (u,v) is in (A ∩ B) × C. So assume (u,v) is in (A × C) ∩ (B × C). From the definition of intersection, (u,v) is in A × C and (u,v) is in B × C, so u is in A and v is in C, and u is in B and v is in C. Since u is in A and in B, it is in A ∩ B. This and the fact that v is in C mean that (u,v) is in (A ∩ B) × C.

Since (A ∩ B) × C is a subset of (A × C) ∩ (B × C) and vice versa, we have shown that if A, B, and C are subsets of some universal set, then (A ∩ B) × C = (A × C) ∩ (B × C). QED.

Extensions

If A, B, and C are sets, does it make sense to talk about A × B × C, i.e., a Cartesian product of more than 2 sets? What do the elements of such a cross product look like?

It does make sense, and produces ordered triples. Similarly Cartesian products of 4 or more sets produce ordered 4- or more tuples.

Technically, A × B × C = (A × B) × C.

For the sake of illustration, suppose A = { a, ... }, B = { b, ... }, and C = { c, ... }. Then elements of A × B × C are actually pairs whose first members are pairs, e.g., pairs such as ((a,b),c). But this gets notationally simplified to (a,b,c).

Key Points

Cartesian products are where ordered pairs come from.

Proof techniques for sets adapted to Cartesian products.

Next

Indexed families of sets.

Read section 5.5.

Next Lecture