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)$.
