Latest Tweets

Cartesian Product

In many situations we will need to list some elements by their order. For example, if we want to locate a point on a coordinate plane, we simply need its coordinates (numbers). But, here is important the exact order of those two numbers. For that purpose, we need to define ordered $n$ – tuples and Cartesian product of sets.

Ordered pair

Definition: Let $A$ and $B$ be non – empty sets and $a \in A$, $b \in B$. Ordered pair of elements $a$ and $b$, denoted by $(a,b)$, is a set

$$(a,b)= \{\{a\}, \{a, b\}\}.$$

Note: If $a=b$, then $(a,b)=(a,a)= \{\{a\}, \{a, a\}\}=\{\{a\}, \{a\}\}=\{\{a\}\}$.

Theorem: Two ordered pairs are equal if and only if their corresponding coordinates are equal, i.e.

$$(a,b) = (a’,b’) \Leftrightarrow a=a’ \land b=b’.$$

 

Cartesian product of two sets

Definition: Let $A$ and $B$ be non – empty sets. The Cartesian product (or cross product) of sets $A$ and $B$, denoted by $A \times B$, is a set:

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

Sets $A$ and $B$ are called factors of Cartesian product. If at least one of the sets $A$ or $B$ is an empty set, we have: $A \times B = \emptyset$.

Example 1: If $A = \{3, 6, 9\}$ and $B = \{4, 8, 10\}$, find $A\times B$ and $B \times A$.

Solution:

$A\times B = \{(3, 4), (3, 8), (3, 10), (6, 4), (6, 8), (6, 10), (9, 4), (9, 8), (9, 10)\}$

$B \times A = \{(4, 3), (8, 3), (10, 3), (4, 6), (8, 6), (10, 6), (4, 9), (8, 9), (10, 9)\}$

We can conclude that $A\times B \neq B \times A$. In general, Cartesian product is not commutative.

Example 2:  If three elements of $A \times B$ are $(2,6), (3,8)$ and $(4,8)$ and $A \times B$  has $6$ elements, find $A \times B$.

Solution:

We notice that $2, 3$ and $4$ are the elements of $A$ and $6$ and $8$ the elements of $B$. Therefore, $A=\{2, 3, 4\}$ and $B=\{6, 8\}$. Now we have

$A\times B = \{(2, 6), (2, 8), (3, 6), (3, 8), (4, 6), (4, 8)\}$

 

Definition: The Cartesian square of a set $A$ is the Cartesian product $A \times A = A^{2} = \{(a,b): a, b \in A\}$.

An example is $\mathbf{R^{2}}= \{(x,y): x,y \in \mathbf{R}\}$ (2 – dimensional plane).

 

Ordered n – tuples

Definition: Let $A_{1}, A_{2}$ and $A_{3}$ be non – empty sets and $a_{1} \in A_{1}, a_{2} \in A_{2}$ and $a_{3} \in A_{3}$.

Ordered triple of elements $a_{1},a_{2}$ and $a_{3}$, denoted by $(a_{1},a_{2},a_{3})$, is a set

$$(a_{1},a_{2},a_{3})=((a_{1}, a_{2}), a_{3})=\{\{(a_{1},a_{2})\}, \{(a_{1}, a_{2}), a_{3}\}\}\}.$$

Definition: Let $A_{1}, \ldots, A_{n}$  be non – empty sets and $a_{1} \in A_{1},\ldots, a_{n} \in A_{n}$.

Ordered n – tuple of elements $a_{1}, \ldots, a_{n}$, denoted by $(a_{1}, \ldots ,a_{n})$, is a set

$$(a_{1}, \ldots ,a_{n})=((a_{1}, \ldots, a_{n-1}), a_{n})=\{\{(a_{1}, \ldots, a_{n-1})\}, \{(a_{1}, \ldots, a_{n-1}), a_{n}\}\}.$$

 

Cartesian product of several sets

Definition: The n – ary Cartesian product over $n$ sets $A_{1}, \ldots A{n}$ is a set

$A_{1} \times \ldots \times A_{n} = \{(a_{1}, \ldots, a_{n}): a_{i} \in A_{i}$ for every $i \in \{1, \ldots, n\}\}$.

If at least one of the sets $A_{1}, \ldots, A_{n}$ is an empty set, we have: $A_{1} \times \ldots \times A_{n} = \emptyset$.

Definition: The n – ary Cartesian power of a set $A$ is a set

$A^{n} = A \times A \times \ldots \times A = \{(a_{1}, \ldots, a_{n}): a_{i} \in A$ for every $i \in \{1, \ldots, n\}\}$.

An example is $\mathbf{R^{3}}= \{(x,y,z): x,y,z \in \mathbf{R}\}$ (3 – dimensional space).

 

Example 3:  If $A=\{1, 2\}, B=\{3,4\}$ and $C=\{5,6\}$, find $A \times B \times C$.

Solution:

$$A \times B \times C = \{(1, 3, 5), (1, 4, 5), (1, 3, 6), (1, 4, 6), (2, 3, 5), (2, 4, 5), (2, 3, 6), (2, 4, 6)\}$$

 

Properties

Theorem: Let $A \times B$ be the Cartesian product of sets $A$ and $B$. Then

$$|A \times B| = |A| \times |B|,$$

where $|A|$ represents cardinality.

Corollary: $$|A \times B|=|B \times A|$$

Theorem: Let $A,B$ and $C$ be three sets. Cartesian product is distributive over union, intersection and set difference:

1) $(A \cup B) \times C = (A \times C) \cup (B \times C)$, $A \times (B \cup C) = (A \times B) \cup  (A \times C)$

2) $(A \cap B) \times C = (A \times C) \cap (B \times C)$, $A  \times (B \cap C) = (A \times B) \cap (A \times C)$

3) $(A \setminus B) \times C = (A \times C) \setminus (B \times C)$, $A \times (B \setminus C) = (A \times B) \setminus (A \times C)$.