5 Set Theory

5.4 Cartesian Products

5.4.1 Beginning Activity 1 (An Equation with Two Variables)

In Section 2.3, we introduced the concept of the truth set of an open sentence with one variable. This was defined to be the set of all elements in the universal set that can be substituted for the variable to make the open sentence a true statement.

In previous mathematics courses, we have also had experience with open sentences with two variables. For example, if we assume that $x$ and $y$ represent real numbers, then the equation

$$2x+3y=12$$

is an open sentence with two variables. An element of the truth set of this open sentence (also called a solution of the equation) is an ordered pair ($a,b$) of real numbers so that when $a$ is substituted for $x$ and $b$ is substituted for $y$, the open sentence becomes a true statement (a true equation in this case). For example, we see that the ordered pair $(6,0)$ is in the truth set for this open sentence since

$$2\cdot 6+3\cdot 0=12$$

is a true statement. On the other hand, the ordered pair $(4,1)$ is not in the truth set for this open sentence since

$$2\cdot 4+3\cdot 1=12$$

is a false statement.
Important Note: The order of the two numbers in the ordered pair is very important. We are using the convention that the first number is to be substituted for $x$ and the second number is to be substituted for $y$. With this convention, $(3,2)$ is a solution of the equation $2x+3y=12$, but $(2,3)$ is not a solution of this equation.

1. List six different elements of the truth set (often called the solution set) of the open sentence with two variables $2x+3y=12$.

2. From previous mathematics courses, we know that the graph of the equation $2x+3y=12$ is a straight line. Sketch the graph of the equation $2x+3y=12$ in the $xy$-coordinate plane. What does the graph of the equation $2x+3y=12$ show?

3. Write a description of the solution set $S$ of the equation $2x+3y=12$ using set builder notation.

5.4.2 Beginning Activity 2 (The Cartesian Product of Two Sets)

In Activity 1, we worked with ordered pairs without providing a formal definition of an ordered pair. We instead relied on your previous work with ordered pairs, primarily from graphing equations with two variables. Following is a formal definition of an ordered pair.

Definition. Let $A$ and $B$ be sets. An ordered pair (with first element from $A$ and second element from $B$) is a single pair of objects, denoted by ($a,b$), with $a\in A$ and $b\in B$ and an implied order. This means that for two ordered pairs to be equal, they must contain exactly the same objects in the same order. That is, if $a,c\in A$ and $b,d\in B$, then

$$(a,b)=(c,d)\text{ if and only if }a=c\text{ and }b=d.$$

The objects in the ordered pair are called the coordinates of the ordered pair. In the ordered pair $(a,b),a$ is the first coordinate and $b$ is the second coordinate.

We will now introduce a new set operation that gives a way of combining elements from two given sets to form ordered pairs. The basic idea is that we will create a set of ordered pairs.

Definition. If $A$ and $B$ are sets, then the Cartesian product, $A\times B$, of $A$ and $B$ is the set of all ordered pairs $(x,y)$ where $x\in A$ and $y\in B$. We use the notation $A\times B$ for the Cartesian product of $A$ and $B$, and using set builder notation, we can write

$$A\times B=\{(x,y)\mid x\in A\text{ and }y\in B\}.$$

We frequently read $A\times B$ as "$A$ cross $B$." In the case where the two sets are the same, we will write $A^2$ for $A\times A$. That is,

$$A^2=A\times A=\{(a,b)\mid a\in A\text{ and }b\in A\}.$$

Let $A=\{1,2,3\}$ and $B=\{a,b\}$.

1. Is the ordered pair ($3,a$) in the Cartesian product $A\times B$? Explain.

2. Is the ordered pair ($3,a$) in the Cartesian product $A\times A$? Explain.

3. Is the ordered pair $(3,1)$ in the Cartesian product $A\times A$? Explain.

4. Use the roster method to specify all the elements of $A\times B$. (Remember that the elements of $A\times B$ will be ordered pairs.)

5. Use the roster method to specify all of the elements of the set $A\times A=A^2$.

6. List all the relationships between the sets in Part (1) that you observe.

5.4.3 The Cartesian Plane

In Beginning Activity 1, we sketched the graph of the equation $2x+3y=12$ in the $xy$-plane. This $xy$-plane, with which you are familiar, is a representation of the set $ℝ\times ℝ$ or ${ℝ}^2$. This plane is called the Cartesian plane.

The basic idea is that each ordered pair of real numbers corresponds to a point in the plane, and each point in the plane corresponds to an ordered pair of real numbers. This geometric representation of ${ℝ}^2$ is an extension of the geometric representation of $ℝ$ as a straight line whose points correspond to real numbers.

Since the Cartesian product ${ℝ}^2$ corresponds to the Cartesian plane, the Cartesian product of two subsets of $ℝ$ corresponds to a subset of the Cartesian plane. For example, if $A$ is the interval [ 1,3 ], and $B$ is the interval [ 2,5 ], then

$$A\times B=\{(x,y)\in {ℝ}^2\mid 1\le x\le 3\text{ and }2\le y\le 5\}.$$

A graph of the set $A\times B$ can then be drawn in the Cartesian plane as shown in Figure 5.6.

Figure 5.6: Cartesian Product $A\times B$

This illustrates that the graph of a Cartesian product of two intervals of finite length in $ℝ$ corresponds to the interior of a rectangle and possibly some or all of its
boundary. The solid line for the boundary in Figure 5.6 indicates that the boundary is included. In this case, the Cartesian product contained all of the boundary of the rectangle. When the graph does not contain a portion of the boundary, we usually draw that portion of the boundary with a dotted line.

Note: A Caution about Notation. The standard notation for an open interval in $ℝ$ is the same as the notation for an ordered pair, which is an element of $ℝ\times ℝ$. We need to use the context in which the notation is used to determine which interpretation is intended. For example,

• If we write $(\sqrt{2},7)\in ℝ\times ℝ$, then we are using $(\sqrt{2},7)$ to represent an ordered pair of real numbers.

• If we write $(1,2)\times \{4\}$, then we are interpreting $(1,2)$ as an open interval. We could write

The following progress check explores some of the same ideas explored in Progress Check 5.23 except that intervals of real numbers are used for the sets.

5.4.4 Progress Check 5.24 (Cartesian Products of Intervals)

We will use the following intervals that are subsets of $ℝ$.

$$A=[0,2]T=(1,2)B=[2,4)C=(3,5]$$

1. Draw a graph of each of the following subsets of the Cartesian plane and write each subset using set builder notation.

   1. $A\times B$

   2. $T\times B$

   3. $A\times C$

   4. $A\times (B\cap C)$

   5. $(A\times B)\cap (A\times C)$

   6. $A\times (B\cup C)$

   7. $(A\times B)\cup (A\times C)$

   8. $A\times (B-C)$

   9. $(A\times B)-(A\times C)$

   10. $B\times A$

2. List all the relationships between the sets in Part (1) that you observe.

One purpose of the work in Progress Checks 5.23 and 5.24 was to indicate the plausibility of many of the results contained in the next theorem.

Theorem 5.25. Let $A,B$, and $C$ be sets. Then

1. $A\times (B\cap C)=(A\times B)\cap (A\times C)$

2. $A\times (B\cup C)=(A\times B)\cup (A\times C)$

3. $(A\cap B)\times C=(A\times C)\cap (B\times C)$

4. $(A\cup B)\times C=(A\times C)\cup (B\times C)$

5. $A\times (B-C)=(A\times B)-(A\times C)$

6. $(A-B)\times C=(A\times C)-(B\times C)$

7. If $T\subseteq A$, then $T\times B\subseteq A\times B$.

8. If $Y\subseteq B$, then $A\times Y\subseteq A\times B$.

We will not prove all these results; rather, we will prove Part (2) of Theorem 5.25 and leave some of the rest to the exercises. In constructing these proofs, we need to keep in mind that Cartesian products are sets, and so we follow many of the same principles to prove set relationships that were introduced in Sections 5.2 and 5.3.

The other thing to remember is that the elements of a Cartesian product are ordered pairs. So when we start a proof of a result such as Part (2) of Theorem 5.25, the primary goal is to prove that the two sets are equal. We will do this by proving that each one is a subset of the other one. So if we want to prove that $A\times (B\cup C)\subseteq (A\times B)\cup (A\times C)$, we can start by choosing an arbitrary element of $A\times (B\cup C)$. The goal is then to show that this element must be in $(A\times B)\cup (A\times C)$. When we start by choosing an arbitrary element of $A\times (B\cup C)$, we could give that element a name. For example, we could start by letting

$$u\text{ be an element of }A\times (B\cup C).$$ (1)

We can then use the definition of "ordered pair" to conclude that

$$\text{ there exists }x\in A\text{ and there exists }y\in B\cup C\text{ such that }u=(x,y)\text{. }$$ (2)

In order to prove that $A\times (B\cup C)\subseteq (A\times B)\cup (A\times C)$, we must now show that the ordered pair $u$ from (1) is in $(A\times B)\cup (A\times C)$. In order to do this, we can use the definition of set union and prove that

$$u\in (A\times B)\text{ or }u\in (A\times C).$$ (3)

Since $u=(x,y)$, we can prove (3) by proving that

$$(x\in A\text{ and }y\in B)\text{ or }(x\in A\text{ and }y\in C).$$ (4)

If we look at the sentences in (2) and (4), it would seem that we are very close to proving that $A\times (B\cup C)\subseteq (A\times B)\cup (A\times C)$. Following is a proof of Part (2) of Theorem 5.25.

Theorem 5.25 (Part (2)). Let $A,B$, and $C$ be sets. Then

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

Proof. Let $A,B$, and $C$ be sets. We will prove that $A\times (B\cup C)$ is equal to $(A\times B)\cup (A\times C)$ by proving that each set is a subset of the other set.

To prove that $A\times (B\cup C)\subseteq (A\times B)\cup (A\times C)$, we let $u\in A\times (B\cup C)$. Then there exists $x\in A$ and there exists $y\in B\cup C$ such that $u=(x,y)$. Since $y\in B\cup C$, we know that $y\in B$ or $y\in C$.

In the case where $y\in B$, we have $u=(x,y)$, where $x\in A$ and $y\in B$. So in this case, $u\in A\times B$, and hence $u\in (A\times B)\cup (A\times C)$. Similarly, in the case where $y\in C$, we have $u=(x,y)$, where $x\in A$ and $y\in C$. So in this case, $u\in A\times C$ and, hence, $u\in (A\times B)\cup (A\times C)$.

In both cases, $u\in (A\times B)\cup (A\times C)$. Hence, we may conclude that if $u$ is an element of $A\times (B\cup C)$, then $u\in (A\times B)\cup (A\times C)$, and this proves that

$$A\times (B\cup C)\subseteq (A\times B)\cup (A\times C)$$ (1)

We must now prove that $(A\times B)\cup (A\times C)\subseteq A\times (B\cup C)$. So we let $v\in (A\times B)\cup (A\times C)$. Then $v\in (A\times B)$ or $v\in (A\times C)$.

In the case where $v\in (A\times B)$, we know that there exists $s\in A$ and there exists $t\in B$ such that $v=(s,t)$. But since $t\in B$, we know that $t\in B\cup C$, and hence $v\in A\times (B\cup C)$. Similarly, in the case where $v\in (A\times C)$, we know that there exists $s\in A$ and there exists $t\in C$ such that $v=(s,t)$. But because $t\in C$, we can conclude that $t\in B\cup C$ and, hence, $v\in A\times (B\cup C)$.

In both cases, $v\in A\times (B\cup C)$. Hence, we may conclude that if $v\in (A\times B)\cup (A\times C)$, then $v\in A\times (B\cup C)$, and this proves that

$$(A\times B)\cup (A\times C)\subseteq A\times (B\cup C)$$ (2)

The relationshipsin (1) and (2) prove that $A\times (B\cup C)=(A\times B)\cup (A\times C)$. $\mathrm{\square }$

Final Note. The definition of an ordered pair in Beginning Activity 2 may have seemed like a lengthy definition, but in some areas of mathematics, an even more formal and precise definition of "ordered pair" is needed. This definition is explored in Exercise (10).

5.4.5 Exercises for Section 5.4

1. $(\star )$ Let $A=\{1,2\},B=\{a,b,c,d\}$, and $C=\{1,a,b\}$. Use the roster method to list all of the elements of each of the following sets:

   1. $A\times B$

   2. $B\times A$

   3. $A\times C$

   4. $A^2$

   5. $A\times (B\cap C)$

   6. $(A\times B)\cap (A\times C)$

   7. $A\times \mathrm{\varnothing }$

   8. $B\times \{2\}$

2. Sketch a graph of each of the following Cartesian products in the Cartesian plane.

   1. $[0,2]\times [1,3]$

   2. $(0,2)\times (1,3]$

   3. $[2,3]\times \{1\}$

   4. $\{1\}\times [2,3]$

   5. $ℝ\times (2,4)$

   6. $(2,4)\times ℝ$

   7. $ℝ\times \{-1\}$

   8. $\{-1\}\times [1,+\mathrm{\infty })$

3. $(\star )$ Prove Theorem 5.25, $\mathrm{Part}(1):A\times (B\cap C)=(A\times B)\cap (A\times C)$.

4. $(\star )$ Prove Theorem 5.25, Part (4): $(A\cup B)\times C=(A\times C)\cup (B\times C)$.

5. Prove Theorem 5.25, Part (5): $A\times (B-C)=(A\times B)-(A\times C)$.

6. Prove Theorem 5.25, Part (7): If $T\subseteq A$, then $T\times B\subseteq A\times B$.

7. Let $A=\{1\},B=\{2\}$, and $C=\{3\}$.

   1. Explain why $A\times B\ne B\times A$.

   2. Explain why ($A\times B$) × $C\ne A\times (B\times C)$.

8. Let $A$ and $B$ be nonempty sets. Prove that $A\times B=B\times A$ if and only if $A=B$.

9. Is the following proposition true or false? Justify your conclusion.

   Let $A,B$, and $C$ be sets with $A\ne \mathrm{\varnothing }$. If $A\times B=A\times C$, then $B=C$. Explain where the assumption that $A\ne \mathrm{\varnothing }$ is needed.

5.4.6 Explorations and Activities

1. (A Set Theoretic Definition of an Ordered Pair) In elementary mathematics, the notion of an ordered pair introduced at the beginning of this section will suffice. However, if we are interested in a formal development of the Cartesian product of two sets, we need a more precise definition of ordered pair. Following is one way to do this in terms of sets. This definition is credited to Kazimierz Kuratowski (1896-1980). Kuratowski was a famous Polish mathematician whose main work was in the areas of topology and set theory. He was appointed the Director of the Polish Academy of Sciences and served in that position for 19 years.

   Let $x$ be an element of the set $A$, and let $y$ be an element of the set $B$. The ordered pair $(x,y)$ is defined to be the set $\{\{x\},\{x,y\}\}$. That is,

   $$(x,y)=\{\{x\},\{x,y\}\}.$$

   1. Explain how this definition allows us to distinguish between the ordered pairs $(3,5)$ and $(5,3)$.

   2. Let $A$ and $B$ be sets and let $a,c\in A$ and $b,d\in B$. Use this definition of an ordered pair and the concept of set equality to prove that $(a,b)=$ ($c,d$) if and only if $a=c$ and $b=d$.

      An ordered triple can be thought of as a single triple of objects, denoted by ($a,b,c$), with an implied order. This means that in order for two ordered triples to be equal, they must contain exactly the same objects in the same order. That is, $(a,b,c)=(p,q,r)$ if and only if $a=p,b=q$ and $c=r$.

   3. Let $A,B$, and $C$ be sets, and let $x\in A,y\in B$, and $z\in C$. Write a set theoretic definition of the ordered triple $(x,y,z)$ similar to the set theoretic definition of "ordered pair."