EF Cartesian Product

Section 9.5 Cartesian Product

Subsection 9.5.1 Definition and examples

Cartesian product: 🔗
the set of all possible ordered pairs of elements from two given sets $A$ and $B,$ where the first element in a pair is from $A$ and the second is from $B$
$A \times B$: 🔗
the Cartesian product of $A$ and $B :$ $A \times B = {(a, b) | a \in A, b \in B}$

For “small” sets, we can list the elements of the Cartesian product by listing all ways of combining an element from the first with an element from the second.

🔗

Example 9.5.1. A Cartesian product of “small” sets.

🔗

Suppose

A = {1, 2}

and

B = {a, b, c} .

Then

A \times B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)} .

🔗

Example 9.5.2. A special subset of a certain Cartesian product.

🔗

Let

N^{+}

represent the positive natural numbers:

N^{+} = N ∖ {0} .

Then we can describe the Cartesian product

Z \times N^{+}

Z \times N^{+} = {(m, n) | m, n \in Z, n > 0} \subseteq Z \times Z .

🔗

Consider the subset

A = {(m, n) \in Z \times N^{+} | n has no divisors in common with | m |} \subseteq Z \times N^{+} .

🔗

Does

A

resemble some more familiar set …?

🔗

Extend.

🔗

Define

A \times B \times C = {(a, b, c) | a \in A, b \in B, c \in C} .

🔗

Example 9.5.3.

Suppose

A = {1, 2},

B = {a, b, c},

C = {α, β} .

Then,

\begin{aligned} A \times B \times C = { & (1, a, α), (1, a, β), (1, b, α), (1, b, β), (1, c, α), (1, c, β), \\ (2, a, α), (2, a, β), (2, b, α), (2, b, β), (2, c, α), (2, c, β)} \end{aligned}

🔗

Remark 9.5.4.

🔗

Technically, there is a difference between the elements of each of the sets

\begin{aligned} (A \times B) \times C & = {((a, b), c) | a \in A, b \in B, c \in C}, \\ A \times (B \times C) & = {(a, (b, c)) | a \in A, b \in B, c \in C}, \\ A \times B \times C & = {(a, b, c) | a \in A, b \in B, c \in C}, \end{aligned}

🔗

but it is rare that anyone actually observes this technicality. Usually, we consider these three sets to be the same set.

🔗

We use special notation for Cartesian products of a set with itself.

$A^{2}$: 🔗
notation to mean $A \times A$
$A^{3}$: 🔗
notation to mean $A \times A \times A$
$A^{n}$: 🔗
notation to mean $A \times A \times \dots \times A$ involving $n$ “factors” of $A$

🔗

And so on.

🔗

Example 9.5.5. Cartesian products in linear algebra.

🔗

You have probably already encountered the notation

\begin{aligned} R^{2} & = {(x, y) | x, y \in R}, \\ R^{3} & = {(x, y, z) | x, y, z \in R}, \\ ⋮ \\ R^{n} & = {(x_{1}, x_{2}, \dots, x_{n}) | x_{j} \in R}, \\ ⋮ \end{aligned}

🔗

used to represent

2

3

-, and higher-dimensional (real) vector spaces.

🔗

Subsection 9.5.2 Visualizing Cartesian products

🔗

Cartesian products do not really lend themselves to visualization with Venn diagrams. So how should we visualize them?

🔗

The example we are probably most familiar with is that of the Cartesian plane,

R^{2} = R \times R,

where each element

(x, y)

is visualized as a point in a two-dimensional diagram, plotted according to the

x

- and

y

-coordinates of the element relative to a central set of

x y

-axes.

A point in the Cartesian plane as a set of $xy$-coordinates. — 🔗
Figure 9.5.6. Visualizing elements of $R \times R$ as points in a plane relative to a set of perpendicular axes.

🔗

To produce this visualization, we imagine the elements of the “first”

R

arrayed along the

x

-axis, and the elements of the “second”

R

as arrayed along the

y

-axis, and then imagine each element of the Cartesian product

R \times R

as a point located at a position that “lines up” with the corresponding positions on the

x

- and

y

-axes of the element’s coordinates. This is possible because the concepts of “less than” and “greater than” allow us to think of elements of

R

as “progressing” from left to right along the

x

-axis and from bottom to top along the

y

-axis.

🔗

Even though other types of sets may not have readily available notions of “less than” and “greater than”, we may still visualize a Cartesian product

A \times B

as “points” in a “plane” plotted relative to a central set of

A B

-axes. In the particular case that

A

and

B

are finite, it doesn’t really matter in what “order” we place the elements of

A

along the

A

-axis or the elements of

B

along the

B

-axis.

🔗

Example 9.5.7. Visualizing a Cartesian product between finite sets.

🔗

Consider the sets

A = {a, α, ϕ, z}

and

B = {1, 2, 3} .

Instead of listing the elements of

A \times B,

we will place them in a grid. In Figure 9.5.8, you might imagine that the elements of

A

listed along the bottom row make up a horizontal axis and the elements of

B

along the leftmost column make up a vertical axis. But take care that these “axes” are not a continuum of values — there are no other “values” between these “coordinate values” along the “axes”. For example, there is no

1.5

along the “horizontal axis.” Similarly, there are no other “points” between the elements of

A \times B .

$B$
$3$	$(a, 3)$	$(α, 3)$	$(ϕ, 3)$	$(z, 3)$
$2$	$(a, 2)$	$(α, 2)$	$(ϕ, 2)$	$(z, 2)$
$1$	$(a, 1)$	$(α, 1)$	$(ϕ, 1)$	$(z, 1)$
	$a$	$α$	$ϕ$	$z$	$A$

Figure 9.5.8. Visualizing elements of

A \times B

as “points” in a grid relative to a set of perpendicular “axes.”

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: