Discrete Mathematics and Proof

Cartesian product

A point in the plane needs two numbers in a fixed order, and so does a crepe order of one batter and one filling. What single set holds every such pair at once?

You need

Writing sets: roster, rule and the empty setAlgebra 1

Unlocks

Relations and their properties: reflexive, symmetric, antisymmetric, transitiveDiscrete Mathematics and Proof

Where you are 15 in Sets

Logic, proof and discrete math6

Sets15

▴ 2 above Writing sets: roster, rule and the empty set Cardinality of a finite set

Cartesian product

One-to-one, onto and bijective functions Power set ▾ Show all 15 (8 more)

Why this exists

A point of the plane is two numbers playing different parts: (3, 1) and (1, 3) are different points (Ordered pairs and the first quadrant). A crepe order at Nayeli’s stand is also two things, a batter and a filling. The Cartesian product gathers every such pair into one set. The plane is a product, a relation is a subset of one, and counting choices made in stages (The fundamental counting principle) is counting a product.

Definition

Ordered pair. An ordered pair (a, b) is two objects in a fixed order: a is the first coordinate, b the second coordinate. Everything about pairs used here comes from one rule:

(a, b) = (c, d) \iff a = c \text{ and } b = d

So (1, 2) \neq (2, 1), and (3, 3) is a genuine pair whose coordinates happen to agree.

Why a set of two will not do. Since \{1, 2\} = \{2, 1\}, a set loses order, and since \{3, 3\} = \{3\}, a repeated entry collapses (Writing sets: roster, rule and the empty set). An ordered pair is a new kind of object. It can be built from sets (one standard choice is \{\{a\}, \{a, b\}\}), but nothing here depends on how, only on the rule above.

Cartesian product. For sets A and B, the Cartesian product is the set of all ordered pairs with first coordinate in A and second coordinate in B:

A \times B = \{(a, b) : a \in A,\ b \in B\}

It is read “A cross B”. We write A^2 = A \times A; it holds every pair of members of A, including each (a, a), and both (a, b) and (b, a).

More factors. Two ordered triples (a, b, c) are equal when all three coordinates agree, and A \times B \times C = \{(a, b, c) : a \in A,\ b \in B,\ c \in C\}. Likewise A_1 \times \cdots \times A_n is the set of lists (a_1, \ldots, a_n) with each a_i \in A_i, and A^n is the product of n copies of A. A member of A^n is a string of length n in the alphabet A: the triple (c, a, b) \in \{a, b, c\}^3 is the word cab.

Intuition

Put the members of A along a horizontal line and those of B up a vertical one. The pair (a, b) is the crossing of the column over a with the row beside b, so A \times B is a full grid of dots.

Figure 1\{1, 2, 3, 4\} \times \{1, 2, 3\} as a grid: four columns of three dots, 12 pairs. The pairs (3, 1) and (1, 3) are different dots.

Figure 1 shows two facts at once. There is one column per member of A and one dot in each column per member of B, so 4 \cdot 3 = 12 pairs. And order matters: (3, 1) and (1, 3) are different dots.

With all real numbers as factors the grid fills in: \mathbb{R} \times \mathbb{R} = \mathbb{R}^2 is the coordinate plane (The coordinate plane). A product of two intervals is a rectangle. The rectangle R of Figure 2 is

\begin{aligned} [1, 5] \times [2, 3] = \{(x, y) :{}& 1 \le x \le 5, \\ & 2 \le y \le 3\} \end{aligned}

A product always has this full-rectangle shape, every column of A against every row of B, so a diagonal line or a circle is a set of pairs but not a product.

Figure 2R = [1, 5] \times [2, 3] and S = [2, 3] \times [1, 5]. Swapping the factors reflects a rectangle in the line y = x.

Results

Equality of pairs. (a, b) = (c, d) exactly when a = c and b = d.

Size of a product. For finite sets,

\lvert A \times B\rvert = \lvert A\rvert \cdot \lvert B\rvert

and \lvert A_1 \times \cdots \times A_n\rvert = \lvert A_1\rvert \cdots \lvert A_n\rvert, so \lvert A^n\rvert = \lvert A\rvert^n.

An empty factor. A \times \varnothing = \varnothing \times A = \varnothing. Conversely, if A \times B = \varnothing, then A = \varnothing or B = \varnothing.

Order of the factors. A \times B = B \times A exactly when A = B, or A = \varnothing, or B = \varnothing.

Product over union and intersection. For all sets A, B, C,

A \times (B \cup C) = (A \times B) \cup (A \times C)

A \times (B \cap C) = (A \times B) \cap (A \times C)

and the same with the shared set on the right, such as (A \cup B) \times C = (A \times C) \cup (B \times C).

Intersection of two products.

(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)

Union of two products. Only an inclusion holds (Exercise 16), and the sides can differ (Example 6), because the right side lets x come from A while y comes from D:

(A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D)

Why it is true

Size. Sort the pairs into rows by first coordinate. For fixed a \in A, the pairs (a, b) with b \in B are \lvert B\rvert different pairs, since their second coordinates differ. Pairs with different first coordinates are unequal, so the rows do not overlap and every pair is in exactly one row: \lvert A\rvert rows of \lvert B\rvert. This is the multiplication principle, and the product is the set it counts. For n factors, match (a_1, \ldots, a_n) with ((a_1, \ldots, a_{n-1}), a_n) and apply the two-factor count n - 1 times.

An empty factor. A member of A \times \varnothing would need a second coordinate in \varnothing, and there is none. For the converse, take the contrapositive: if a \in A and b \in B, then (a, b) \in A \times B.

Order of the factors.

Proof. If A = B, the products are the same set; if A or B is empty, both are \varnothing. Now suppose A \times B = B \times A with neither set empty. Let x \in A, and choose some y \in B. Then (x, y) \in A \times B = B \times A, so the first coordinate x lies in B. Hence A \subseteq B. Exchanging the roles of A and B gives B \subseteq A, so A = B by double inclusion (Subsets, proper subsets and equal sets). \square

Product over union.

Proof. Every member of either side is an ordered pair, so follow an arbitrary pair (x, y). It lies in A \times (B \cup C) exactly when

x \in A \land (y \in B \lor y \in C)

By the distributive law of \land over \lor (the logic behind the distributive laws for sets) this is equivalent to

\begin{aligned} &(x \in A \land y \in B) \\ \lor {}&(x \in A \land y \in C) \end{aligned}

which says (x, y) \in A \times B or (x, y) \in A \times C, that is, (x, y) \in (A \times B) \cup (A \times C). Every step runs both ways, so each side is a subset of the other. \square

The intersection version is the same argument with \land for \lor (Exercise 11).

Intersection of two products.

Proof. A pair (x, y) is in the left side exactly when x \in A, y \in B, x \in C and y \in D. Regrouping and reordering these four conditions (the associative and commutative laws of \land) gives x \in A \cap C and y \in B \cap D. \square

Worked examples

Example 1

Every crepe order

Nayeli’s crepe stand has three batters, plain p, cocoa c and buckwheat w, so B = \{p, c, w\}, and two fillings, apple a and ham h, so F = \{a, h\}. List B \times F, count it, and decide whether B \times F = F \times B.

Solution

Pair each batter with each filling, one batter at a time:

\begin{aligned} B \times F = \{&(p, a), (p, h), (c, a), \\ &(c, h), (w, a), (w, h)\} \end{aligned}

That is 3 \cdot 2 = 6 pairs, one per crepe. F \times B also has six pairs, such as (a, p), but the two sets share no member: a pair in both would have its first coordinate in B and in F, and B \cap F = \varnothing. Same crepes, different sets, so a menu must fix which coordinate comes first.

Example 2

An equation between pairs

Find all real x and y with (x + y, x - y) = (7, 1). Then find all real x and y with \{x + y, x - y\} = \{7, 1\}.

Solution

Equal pairs have equal coordinates, so x + y = 7 and x - y = 1. Adding gives 2x = 8, so x = 4, and then y = 3 from the first equation. Check: (4 + 3, 4 - 3) = (7, 1). One solution.

For the sets, the two members of \{x + y, x - y\} must be 7 and 1 in some order (both 7 would give \{7\} \neq \{7, 1\}). Either x + y = 7 and x - y = 1, giving (4, 3) again, or x + y = 1 and x - y = 7, giving x = 4 and y = -3. The extra solution is exactly what a set throws away: which entry came first.

Example 3

Strings of a fixed length

List the members of \{a, b\}^3 as strings and count them. Then count the four-digit codes made from the digits 0 to 9, and those whose first digit is not 0.

Solution

A member of \{a, b\}^3 is a triple, written as a three-letter word. By first letter, then second, then third: aaa, aab, aba, abb, baa, bab, bba, bbb. That is 2^3 = 8, as \lvert A^n\rvert = \lvert A\rvert^n predicts. A four-digit code is a member of D^4 with D = \{0, 1, \ldots, 9\}, so there are 10^4 = 10{,}000 codes. Those not starting with 0 form \{1, \ldots, 9\} \times D \times D \times D, with 9 \cdot 10 \cdot 10 \cdot 10 = 9{,}000 members.

Example 4

Rectangles in the plane

Let R = [1, 5] \times [2, 3] and S = [2, 3] \times [1, 5], as in Figure 2. Which of (4, 3), (3, 4) and (2, 2) lie in R, and which in S? Describe R \cap S, and decide whether R = S.

Solution

A point is in a product when each coordinate lies in its own factor. (4, 3) is in R, since 4 \in [1, 5] and 3 \in [2, 3], but not in S, since 4 \notin [2, 3]. (3, 4) is not in R, since 4 \notin [2, 3], but is in S. (2, 2) lies in both. By the intersection rule,

\begin{aligned} R \cap S &= ([1, 5] \cap [2, 3]) \times ([2, 3] \cap [1, 5]) \\ &= [2, 3] \times [2, 3] \end{aligned}

the central square. (4, 3) shows R \neq S, though both have area 4 \cdot 1 = 4.

Example 5

Counting an overlap

Let A = \{1, 2, 3, 4, 5\} and B = \{2, 4, 6, 8\}. Find \lvert A \times B\rvert, \lvert (A \times B) \cap (B \times A)\rvert and \lvert (A \times B) \cup (B \times A)\rvert.

Solution

By the size rule, \lvert A \times B\rvert = 5 \cdot 4 = 20, and \lvert B \times A\rvert = 20 too. The intersection rule gives

\begin{aligned} (A \times B) \cap (B \times A) &= (A \cap B) \times (B \cap A) \\ &= \{2, 4\} \times \{2, 4\} \end{aligned}

the four pairs (2, 2), (2, 4), (4, 2), (4, 4). Counting the union by subtracting the overlap once gives 20 + 20 - 4 = 36. The products do differ: (1, 6) \in A \times B, but (1, 6) \notin B \times A as 1 \notin B.

Example 6

A union of products that is not a product

Let A = B = \{1, 2\} and C = D = \{2, 3\}. Compare (A \times B) \cup (C \times D) with (A \cup C) \times (B \cup D).

Solution

Each of A \times B and C \times D has 2 \cdot 2 = 4 pairs. They overlap in (A \cap C) \times (B \cap D) = \{2\} \times \{2\}, the one pair (2, 2), so the union has 4 + 4 - 1 = 7 pairs. On the other side A \cup C = B \cup D = \{1, 2, 3\}, so the product has 3 \cdot 3 = 9 pairs.

Figure 3The union of the two products is the seven solid points. The product (A \cup C) \times (B \cup D) is all nine.

The missing pairs are (1, 3) and (3, 1): in (1, 3) the first coordinate is in A but the second only in D, so the pair is in neither square. The union is a proper subset of the product.

Example 7

Not every set of pairs is a product

Let A = \{1, 2, 3\}. Show that E = \{(1, 1), (2, 2), (3, 3)\}, a subset of A \times A, is not C \times D for any sets C and D.

Solution

Proof. Suppose, for a contradiction (Proof by contradiction), that E = C \times D. From (1, 1) \in C \times D we get 1 \in C, and from (2, 2) \in C \times D we get 2 \in D. Then (1, 2) \in C \times D = E. But every member of E has equal coordinates, so (1, 2) \notin E. This contradiction shows no such C and D exist. \square

E is the diagonal of the grid: a product cannot hold two corners of a rectangle without the other two.

Boundaries

The count needs finite sets. The product is defined for any sets, but \lvert A \times B\rvert = \lvert A\rvert \cdot \lvert B\rvert is about finite ones. Whether \mathbb{Z} \times \mathbb{Z} is “the same size” as \mathbb{Z} is a question for Countable sets.

Order and grouping matter. A \times B \neq B \times A unless A = B or one is empty. And (A \times B) \times C has members ((a, b), c) and A \times B \times C has triples (a, b, c); they match one for one and are usually identified, but they are not equal sets.

Multiplying counts products only, not sets like those of Examples 6 and 7.

The same brackets mean two things. (2, 5) may be a pair or an open interval. In (2, 5) \in \mathbb{R}^2 it is a pair; in (2, 5) \times \{0\} it is an interval.

Where this goes next

A relation from A to B is any subset of A \times B; the sets of pairs of Relations and functions are cut from a product. Relations and their properties: reflexive, symmetric, antisymmetric, transitive sorts subsets of A \times A by properties such as symmetry, and One-to-one, onto and bijective functions studies functions, relations with exactly one pair in each column of the grid. A relation on A is a member of the Power set of A \times A. Identities like those above are proved by following one element through the definitions.

Exercises

Listing and counting

Let P = \{0, 5\} and Q = \{r, s, t\}. List P \times Q and Q \times P.
List the members of \{-1, 1\}^2, and then those whose two coordinates add to 0.
If \lvert A\rvert = 7 and \lvert B\rvert = 9, find \lvert A \times B\rvert, \lvert B \times B\rvert and \lvert A \times B \times A\rvert.
Nayeli’s stand now offers three batters, five fillings and two sizes, small and large. An order is a triple (batter, filling, size). How many orders are there, and how many use plain batter in the large size?
List \{\varnothing\} \times \{1, 2\} and \varnothing \times \{1, 2\}, and count each.

Equal pairs and strings

Find x and y with (2x - 1, y + 4) = (5, -2).
Find all real x and y with (x^2, y) = (9, x).
How many strings of length 6 can be written in the alphabet \{a, b, c\}? How many of them begin with a?

Products in the plane

Let T = [-2, 1] \times [1, 4]. Which of (1, 4), (4, 1) and (0, 0) lie in T? What is its area?
Write ([0, 4] \times [1, 3]) \cap ([2, 6] \times [0, 2]) as a product of two intervals, and find its area.

Identities and counterexamples

Prove that A \times (B \cap C) = (A \times B) \cap (A \times C) for all sets A, B, C.
Let A = \{1\}, B = \{5\}, C = \{2\} and D = \{6\}. List (A \times B) \cup (C \times D) and (A \cup C) \times (B \cup D). Which pairs are in the second but not the first?
Prove that if A = C, then (A \times B) \cup (C \times D) = (A \cup C) \times (B \cup D).
Let A = \{1, 2, 3\} and B = \{1, 2\}. Is A \times B = B \times A? Give a pair that settles it.

Reasoning

Prove that if A \times A = B \times B, then A = B.
Prove that (A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D) for all sets.
Explain why no finite sets have \lvert A \times B\rvert = 7 with both \lvert A\rvert > 1 and \lvert B\rvert > 1. Then list every pair of sizes (\lvert A\rvert, \lvert B\rvert) with \lvert A \times B\rvert = 12.
Let A and B be nonempty. Prove that if A \times B \subseteq C \times D, then A \subseteq C and B \subseteq D. Why is “nonempty” needed?

Answers

P \times Q = \{(0, r), (0, s), (0, t), (5, r), (5, s), (5, t)\} and Q \times P = \{(r, 0), (r, 5), (s, 0), (s, 5), (t, 0), (t, 5)\}.
\{(-1, -1), (-1, 1), (1, -1), (1, 1)\}. The coordinates add to 0 in (-1, 1) and (1, -1).
7 \cdot 9 = 63, 9 \cdot 9 = 81 and 7 \cdot 9 \cdot 7 = 441. So 63, 81 and 441.
3 \cdot 5 \cdot 2 = 30 orders. Fixing batter and size leaves one order per filling: 5.
\{\varnothing\} \times \{1, 2\} = \{(\varnothing, 1), (\varnothing, 2)\}, with 2 members, since \{\varnothing\} has one member. But \varnothing \times \{1, 2\} = \varnothing, with 0.
2x - 1 = 5 gives x = 3, and y + 4 = -2 gives y = -6.
x^2 = 9 and y = x, so the solutions are (3, 3) and (-3, -3).
The strings form \{a, b, c\}^6: 3^6 = 729. Fixing the first letter leaves five places: 3^5 = 243.
(1, 4) \in T, since 1 \in [-2, 1] and 4 \in [1, 4]. (4, 1) \notin T, as 4 \notin [-2, 1]; (0, 0) \notin T, as 0 \notin [1, 4]. Area 3 \cdot 3 = 9.
([0, 4] \cap [2, 6]) \times ([1, 3] \cap [0, 2]) = [2, 4] \times [1, 2], area 2 \cdot 1 = 2.
Proof. (x, y) \in A \times (B \cap C) iff x \in A, y \in B and y \in C, iff (x \in A and y \in B) and (x \in A and y \in C), since repeating x \in A changes nothing, iff (x, y) \in (A \times B) \cap (A \times C). Each step runs both ways. \square
The first set is \{(1, 5), (2, 6)\}; the second is \{1, 2\} \times \{5, 6\}, four pairs. Only in the second: (1, 6) and (2, 5).
Proof. With C = A the left side is (A \times B) \cup (A \times D) = A \times (B \cup D), by the product over a union. The right side is (A \cup A) \times (B \cup D) = A \times (B \cup D). \square
No: A \neq B and neither is empty. The pair (3, 1) is in A \times B, but since 3 \notin B it is not in B \times A.
Proof. Let x \in A. Then (x, x) \in A \times A = B \times B, so x \in B. Hence A \subseteq B, and the same argument from B gives B \subseteq A. \square
Proof. If (x, y) \in A \times B, then x \in A \cup C and y \in B \cup D. If (x, y) \in C \times D, then x \in C \subseteq A \cup C and y \in D \subseteq B \cup D. Either way (x, y) \in (A \cup C) \times (B \cup D). \square
\lvert A\rvert \cdot \lvert B\rvert = 7 and 7 is prime, so one size is 1. For 12: (1, 12), (2, 6), (3, 4), (4, 3), (6, 2), (12, 1).
Proof. Let x \in A and choose y \in B. Then (x, y) \in C \times D, so x \in C; hence A \subseteq C. Choosing x \in A the same way gives B \subseteq D. \square Without it: \{1\} \times \varnothing = \varnothing \subseteq \varnothing \times \varnothing, yet \{1\} \not\subseteq \varnothing.