Ordered sets and Cartesian products

Another thing that is especially important in the set theoretic foundations of logic is the notion of an ordered set. As mentioned above, sets are, by nature, unordered. Again, if $S=\{a, b\}$ and $Q=\{b, a\}$, then $S=Q$. But sometimes, we do want to talk about ordered sets, where the ordering of the members does matter. Ordered sets to the rescue!

Unlike normal sets, which are enclosed by curly braces, ordered sets are denoted with the angled braces $\langle$ and $\rangle$. For example, if we take the ordered set of $a$, $b$, and $c$ in just this order, we can write $\langle a, b, c \rangle$. The ordered set $\langle c, b, a \rangle$ is distinct from this, since it has its order reversed.

The fact that they are ordered is not the only difference between normal sets and ordered sets. Another important difference is that for ordered sets, duplicates do count for something. Namely, the ordered set $\langle a \rangle$ and the ordered set $\langle a, a\rangle$ are not the same ordered set (and in general, not the same set either). So in general, unlike normal sets, ordered sets can be distinguished at face value.

Sometimes, some ordered sets are called ordered $n$-tuples, where $n$ is the number of members of the ordered set. For small $n$, we have specific words for these tuples, but after a while, they become unwieldy, and aren’t generally used. So for example, $\langle a, b \rangle$ is an ordered pair, $\langle a, b, c \rangle$ is an ordered triple, $\langle a, b, c, d \rangle$ is an ordered quadruple, and so on.

Another important notion in set theory is the Cartesian product of two sets. If $S$ and $Q$ are two sets, their Cartesian product is denoted by $S \times Q$. Indeed, Cartesian products are one way in which one may ‘make’ ordered sets out of regular sets. In particular, if $S$ and $Q$ are sets, then $S \times Q$, their Cartesian product, is the set of all ordered pairs such that their first member is in $S$, and their second member is in $Q$.

For example, suppose $S=\{a, b\}$ and $Q=\{1, 2\}$. Then, $S \times Q=\{\langle a, 1\rangle, \langle a, 2\rangle, \langle b, 1\rangle, \langle b, 2\rangle\}$. Again, it is just the set of all ordered pairs with the first member of the pair in $S$, and the second in $Q$.

Now importantly, $S$ and $Q$ need not be different, so that $S\times S$ is itself a set, the set of all ordered pairs made up of members of $S$. So for example, if $S=\{a, b, c\}$, then $S \times S=\{\langle a, b\rangle, \langle a, c\rangle, \langle b, a\rangle, \langle b, c\rangle, \langle c, a\rangle, \langle c, b\rangle, \langle a, a\rangle, \langle b,b\rangle, \langle c,c\rangle\}$. From this, you may see why taking the Cartesian product of two sets is denoted by the $\times$ (‘product’) operator, since if a set $S$ has $3$ members, then $S \times S$ will have $9$ members, and so on. We can also write this more succinctly, akin to regular exponentiation, so that $S^2=S \times S$, $S^3=S \times S \times S$, and so on.

The name ‘Cartesian product’ comes from an interesting historical fact. ‘Cartesian’ refers to René Descartes, one of the most important philosophers in history, who was also a pioneering mathematician. As such, he devised the coordinate system you probably already know from mathematics. What does this have to do with Cartesian products? For example, think of the Cartesian product of $\mathbb{N} \times \mathbb{N}$. Its members are all pairs of natural number $\langle n, k\rangle$. Like $\langle 3, 4\rangle$, $\langle 1,1\rangle$, $\langle 6, 0\rangle$. But of course, these are exactly the coordinates of a two-dimensional coordinate system on the natural numbers.

You may be wondering what the relationship is between sets and ordered sets. In set theory books, it is customary to show how ordered sets are definable from the notion of a set. In particular, one can define the ordered pair $\langle a, b\rangle$ to be the set $\{\{a\}, \{a, b\}\}$. This is a kind of encoding, which allows one to determine the order of the two elements $a$ and $b$ from the set of two sets that are themselves not ordered in any way. This kind of definition can be further generalized to cover any $n$-tuple (for any $n$), by iterating the ordered pairs. For example, an ordered triple would be the ordered pair of an ordered pair and a third thing. That is, $\langle a, b, c\rangle=\langle\langle a, b\rangle, c\rangle$. It is then possible to further analyze $\langle\langle a, b\rangle, c\rangle$ according to our set-based definition of ordered pairs. There are alternative ways to do essentially the same thing.