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