Cartesian Product

Definition

The Cartesian product of two sets \( A \) and \( B \), denoted \( A \times B \), is the set of all ordered pairs \( (a, b) \) where \( a \in A \) and \( b \in B \).

Example: Let’s consider two sets:

\[ A = \{1, 2\} \quad \text{and} \quad B = \{x, y\} \]

The Cartesian product \( A \times B \) is given by all possible ordered pairs where the first element comes from \( A \) and the second element comes from \( B \):

\[ A \times B = \{ (1, x), (1, y), (2, x), (2, y) \} \]

Formally,

For two sets \( A \) and \( B \), the Cartesian product \( A \times B \) is defined as:

\[ A \times B = \{ (a, b) \mid a \in A \text{ and } b \in B \} \]

This product is a set of ordered pairs, where each element from \( A \) is paired with each element from \( B \).

Note: The Cartesian product is not commutative, meaning \( A \times B \neq B \times A \) in general, as \( A \times B \) and \( B \times A \) differ in the order of elements in each ordered pair.

To build an intuition for the Cartesian product of two sets, let’s think of it as a way to make connections between elements of one set and elements of another. By connecting each item in one set with each item in another, we create all possible pairs that reflect the relationships between elements in these sets.

Example: Connecting Scientists' Names

Imagine two sets related to famous scientists:

Set \( A \): First names of scientists, such as

\[ A = \{\text{Albert}, \text{Niels}, \text{Werner}\} \]
Set \( B \): Last names of scientists, like

\[ B = \{\text{Einstein}, \text{Bohr}, \text{Heisenberg}\} \]

The Cartesian product \( A \times B \) is the set of all possible combinations of first names and last names. Each element of \( A \) is paired with each element of \( B \), creating a list of pairs. So, if we consider all possible combinations, we get:

\[ A \times B = \{(\text{Albert, Einstein}), (\text{Albert, Bohr}), (\text{Albert, Heisenberg}), (\text{Niels, Einstein}), (\text{Niels, Bohr}), (\text{Niels, Heisenberg}), (\text{Werner, Einstein}), (\text{Werner, Bohr}), (\text{Werner, Heisenberg})\} \]

This product includes every possible pairing of first and last names, even though only a few are "real" names of famous scientists. But that’s the purpose of the Cartesian product: it allows us to consider all possible connections between two sets, whether they have real meaning or not.

Why Use Cartesian Products?

The Cartesian product sets the foundation for defining relations between sets by letting us focus on specific, meaningful connections. In our example, we’re not interested in all pairings of names, only the ones that match actual scientists:

\[ \{\text{(Albert, Einstein)}, \text{(Niels, Bohr)}, \text{(Werner, Heisenberg)}\} \]

This subset of pairs represents a relation—specifically, the relation of “matching first and last names.”

Looking Ahead: Defining Functions

Later, we’ll refine this idea to study functions, which are specific types of relations where each element in one set (like first names) matches with exactly one element in the other (like last names). The Cartesian product gives us a systematic way to explore these mappings by first providing all possible pairings, allowing us to examine meaningful ones that fit the rules of functions.

Properties of Cartesian Product

The Cartesian product \( A \times B \) of two sets \( A \) and \( B \) has several important properties:

Non-Commutative: Generally, \( A \times B \neq B \times A \), since the ordered pairs \( (a, b) \) and \( (b, a) \) have reversed positions. This means that the Cartesian product is not commutative.
Associative for Multiple Sets: For three sets \( A \), \( B \), and \( C \), the Cartesian product is associative in grouping:

\[ (A \times B) \times C = A \times (B \times C) \]

although the elements are ordered differently in each.
Cardinality: If \( |A| = m \) and \( |B| = n \), then \( |A \times B| = m \times n \). This tells us that the number of elements in \( A \times B \) is the product of the number of elements in each set.
Distributive Over Union: The Cartesian product distributes over the union of sets:

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

and similarly,

\[ (A \cup B) \times C = (A \times C) \cup (B \times C) \]
Distributive Over Intersection: The Cartesian product distributes over intersection as well:

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

and

\[ (A \cap B) \times C = (A \times C) \cap (B \times C) \]
Empty Set: If either \( A \) or \( B \) is the empty set \( \emptyset \), then their Cartesian product is also empty:

\[ A \times \emptyset = \emptyset \quad \text{and} \quad \emptyset \times B = \emptyset \]

For more information on properties (but they are not important for us): Wikipedia

Graphical Representation of Cartesian Product

Let the two sets be:

\[ A = \{1, 2, 3\}, \quad B = \{4, 5, 6\}. \]

The Cartesian product \( A \times B \) is:

\[ A \times B = \{(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)\}. \]

How to Represent Graphically:

Place the elements of \( A \) along one axis (horizontal).
Place the elements of \( B \) along the other axis (vertical).
For each pair \( (a, b) \in A \times B \), plot a point where the \( x \)-coordinate is \( a \) (from \( A \)) and the \( y \)-coordinate is \( b \) (from \( B \)).

For example:

The pair \( (1, 4) \) corresponds to the intersection of \( 1 \) on the horizontal axis and \( 4 \) on the vertical axis.
The pair \( (3, 6) \) corresponds to the intersection of \( 3 \) on the horizontal axis and \( 6 \) on the vertical axis.

Key Insight:

When you finish, the graph will show a grid of points, illustrating that each element in \( A \) is connected to every element in \( B \), which is the essence of the Cartesian product.

Cartesian products involving intervals

When one of the sets in a Cartesian product is a discrete set (like \(\{1, 2, 3\}\)) and the other is a continuous interval (like \([2, 5]\)), the result is an infinite collection of points, forming a series of continuous lines.

Example:

Let:

\[ A = \{1, 2, 3\} \quad \text{(a discrete set of three points)} \]

and:

\[ B = [2, 5] \quad \text{(a continuous interval)}. \]

The Cartesian product \( A \times B \) is defined as:

\[ A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}. \]

Interpretation:

For each \( a \in A \) (i.e., \( a = 1, 2, 3 \)), we pair it with all values of \( b \in [2, 5] \).
This results in three continuous vertical lines in the Cartesian plane:
- The line \( x = 1 \) with \( y \in [2, 5] \),
- The line \( x = 2 \) with \( y \in [2, 5] \),
- The line \( x = 3 \) with \( y \in [2, 5] \).

Representation:

Each line corresponds to one value of \( a \) in \( A \), and it spans the entire interval \([2, 5]\) on the \( y \)-axis:

\[ \begin{aligned} &\text{For } x = 1: \quad (1, y) \text{ for all } y \in [2, 5], \\ &\text{For } x = 2: \quad (2, y) \text{ for all } y \in [2, 5], \\ &\text{For } x = 3: \quad (3, y) \text{ for all } y \in [2, 5]. \end{aligned} \]

Key Insight:

The Cartesian product \( A \times B \) produces three continuous vertical lines:

The first at \( x = 1 \),
The second at \( x = 2 \),
The third at \( x = 3 \),

each extending from \( y = 2 \) to \( y = 5 \). This is an infinite set of points because each \( x \) value is paired with all possible \( y \)-values within the interval \([2, 5]\).

When both sets in a Cartesian product are continuous intervals, the result is a rectangle in the Cartesian plane, representing all possible points formed by pairing one value from the first interval with one from the second.

Example:

Let:

\[ A = [1, 3] \quad \text{(a continuous interval on the \( x \)-axis)} \]

\[ B = [2, 5] \quad \text{(a continuous interval on the \( y \)-axis)}. \]

The Cartesian product \( A \times B \) is defined as:

\[ A \times B = \{(x, y) \mid x \in [1, 3], \, y \in [2, 5]\}. \]

Interpretation:

For every value of \( x \) in \([1, 3]\), pair it with every value of \( y \) in \([2, 5]\).
The result is a continuous region in the Cartesian plane that forms a rectangle:
The horizontal range is \( x \in [1, 3] \),
The vertical range is \( y \in [2, 5] \).

Boundaries of the Rectangle

The Cartesian product fills all points within the rectangle bounded by the corners:

\[ (1, 2), \, (1, 5), \, (3, 2), \, (3, 5). \]

Thus, the rectangle spans:

Left side at \( x = 1 \),
Right side at \( x = 3 \),
Bottom at \( y = 2 \),
Top at \( y = 5 \).

Visual Representation

The Cartesian product \( [1, 3] \times [2, 5] \) includes every point \( (x, y) \) within this rectangle, forming a solid filled region in the plane. Each pair \( (x, y) \) corresponds to one specific coordinate within the rectangle.

Cartesian Product of a Set with Itself

When we take the Cartesian product of a set with itself, we are pairing every element of the set with every other element of the same set. For a set \( A \), the Cartesian product \( A \times A \) is defined as:

\[ A \times A = \{(a_1, a_2) \mid a_1 \in A, a_2 \in A\}. \]

This represents all possible ordered pairs formed by taking elements from \( A \).

Example 1:

Let \( A = \{1, 2, 3\} \). The Cartesian product \( A \times A \) is:

\[ A \times A = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)\}. \]

Here, \( A \times A \) includes: - Pairs where both elements are the same, like \( (1, 1), (2, 2), (3, 3) \). - Pairs where the elements are different, like \( (1, 2), (2, 1), (2, 3), \) etc.

This can be visualized as a grid of points if \( A \) is finite.

Example 2:

If \( A = \mathbb{R} \) (the set of all real numbers), the Cartesian product \( \mathbb{R} \times \mathbb{R} \) represents the entire 2D Cartesian plane. Every point \( (x, y) \) where \( x, y \in \mathbb{R} \) belongs to this product.

When a set is paired with itself in a Cartesian product, \( A \times A \) is commonly written as \( A^2 \). This notation emphasizes that the result represents ordered pairs of elements from \( A \).

Examples:

\( \mathbb{R} \times \mathbb{R} = \mathbb{R}^2 \):
- Represents the 2D Cartesian plane.
- Example: \( (2.5, -3.1) \in \mathbb{R}^2 \).
\( \mathbb{N} \times \mathbb{N} = \mathbb{N}^2 \):
- Represents a discrete 2D grid of natural numbers.
- Example: \( (3, 5) \in \mathbb{N}^2 \).
\( \mathbb{Z} \times \mathbb{Z} = \mathbb{Z}^2 \):
- Represents a 2D lattice of integers, covering all quadrants.
- Example: \( (-4, 7) \in \mathbb{Z}^2 \).

Cartesian Product of Three Sets

The Cartesian product of three sets \( A \), \( B \), and \( C \), written as \( A \times B \times C \), is the set of all ordered triples \( (a, b, c) \), where \( a \in A \), \( b \in B \), and \( c \in C \). Formally:

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

Example:

Let:

\[ A = \{1, 2\}, \quad B = \{x, y\}, \quad C = \{p, q\}. \]

Then:

\[ A \times B \times C = \{(1, x, p), (1, x, q), (1, y, p), (1, y, q), (2, x, p), (2, x, q), (2, y, p), (2, y, q)\}. \]

Ternary Product of the Same Set \( A \)

If \( A \) is a single set and we form the ternary product \( A \times A \times A = A^3 \), it includes all ordered triples \( (a_1, a_2, a_3) \) where \( a_1, a_2, a_3 \in A \).

Example: \( A = \{1, 2\} \)

\[ A^3 = \{(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)\}. \]