# Naive Set Theory: Relations

## Cartesian Products

The ordering of elements in sets has not mattered so far in our discussion of sets. The set $\{x, y\}$ is identical to the set $\{y, x\}$. However, what if *did* want the ordering of the elements to matter? Ideally we would like to be able to construct an object $(x, y)$ that is not the same as an object $(y, x)$. Such a thing is in fact the familiar ordered pair. The question, of course, how to define it in terms of sets.

An **ordered pair** of elements $(a, b)$ is defined as the set $\{\{a\}, \{a, b\}\}$, where $a$ is called the **first coordinate** and $b$ is called the **second coordinate**. If $a = b$, then the ordered pair $(a, a)$ simply corresponds to the set $\{\{a\}\}$. Happily enough, we find that $(a, b) \neq (b, a)$; the *order* in which the elements in an ordered pair are listed is, as we intended, important. This definition was first introduced by Kazimierz Kuratowski in a 1921 article in the Polish mathematical journal Fundamenta Mathematicae.

The **Cartesian product** of two sets $A$ and $B$, denoted as $A \times B$, is the set of all ordered pairs of elements $a$ and $b$ such that $a \in A$ and $b \in B$. Formally,

$$A \times B = \{ (a, b) : a \in A \text{ or } b \in B\}$$

Cartesian products should feel familiar. Middle school algebra covers the 2D plane, often denoted $\mathbb{R}^2$, and pairs and triples of numbers are the focus of much math after that. However, it's important to note that the Cartesian product of two sets by itself does not provide anything more than a definition upon which more useful things can be built. As we'll see, the Cartesian product has all kinds of useful mathematical objects built on top of it.

## Problems

Write out the following Cartesian products:

- $\{1, 2\} \times \{3, 4\}$
- $\{a, b\} \times \{a, b\}$
- $\{e, f, g\} \times \{a, f, q\}$
- $\{a, b, c, d\} \times \{1, 2\}$

- $\{1, 2\} \times \{3, 4\} = \{(1,3), (1,4), (2, 3), (2, 4)\}$
- $\{a, b\} \times \{a, b\} = \{(a, a), (a, b), (b, a), (b, b)\}$
- $\{e, f, g\} \times \{a, f, q\} = \{(e, a), (e, f), (e, q), (f, a), (f, f), (f, q), (g, a), (g, f), (g, q)\}$
- $\{a, b, c, d\} \times \{1, 2\} = \{(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2), (d, 1), (d, 2)\}$

Evaluate the following Cartesian product:

$$(\{a, b\} \times \{1, 2\}) \times \{\alpha, \beta\}$$

First evaluate the product inside the parentheses:

$\left(\{a, b\} \times \{1, 2\}\right) \times \{\alpha, \beta\} = \{ (a,1), (a,2), (b,1), (b,2) \} \times \{\alpha, \beta \}$

The fact that the cartesian product is between a set containing ordered pairs and one containing "regular" elements makes no difference:

$\begin{align*} \begin{matrix} \left(\{a, b\} \times \{1, 2\}\right) \times \{\alpha, \beta\} = \\ \vphantom{\,} \\ \vphantom{\,} \\ \vphantom{\,} \end{matrix} & \begin{matrix} \{ ((a,1), \alpha), \, ((a,1), \beta), \\ \, \, ((a,2), \alpha), \, ((a,2), \beta), \\ \, \, ((b,1), \alpha), \, ((b,1), \beta), \\ \, \, ((b,2), \alpha), \, ((b,2), \beta) \} \end{matrix} \end{align*}$

To anyone familiar with multivariable math, this

*looks*like it should be simplified from ordered pairs containing ordered pairs to ordered triplets. However, note that so far we only have a definition for ordered pairs. Perhaps later we will find a definition for ordered n-tuples that expands on the definition of ordered pairs that will allow us to simplify the notation here.Show that $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$.

$\implies$: Assume $(a, b) = (c, d)$. Then $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}$. By definition of set equality, either $\{a\} = \{c\}$ or $\{a\} = \{c, d\}$, and likewise either $\{a, b\} = \{c\}$ or $\{a, b\} = \{c, d\}$.

If $\{a\} = \{c, d\}$, then $c = d$ and $a = c = d$. Therefore $(c, d) = \{\{a\}\} = (a, b)$. As a result, $a = b$, so $a = b = c = d$. Thus $(a, b) = (c, d)$ as desired. An identical argument holds if $\{a, b\} = \{c\}$.

If instead $\{a\} = \{c\}$, then $a = c$. We consider the case where $\{a, b\} = \{c, d\}$, since the case where $\{a, b\} = \{c\}$ was already covered. Then either $a = d$ or $b = d$. If $a = d$, then $c=d$, and it follows that $a=b=c=d$ as above. If instead $b = d$, we have $a=c$ and $b=d$, from which it again follows that $(a, b) = (c, d)$.

In any case, $(a, b) = (c, d)$ implies that $a = c$ and $b = d$.

$\impliedby$: If $a = c$ and $b = d$, then it follows trivially that $(a, b) = (c, d)$.