Mauro Bringolf

Currently geeking out as WordPress developer at WebKinder and student of computer science at ETH.

Modeling ordered pairs using nothing but unordered sets

January 28, 2017
, ,

While studying for an exam in Discrete Mathematics I stumbled upon an interesting little thing in the lecture notes. In the chapter on basic set theory there was an example about ordered sets (tupels, lists or however you decide to call them). It showed how to define ordered sets using nothing but unordered sets. It sounds paradox but is quite simple.

With unordered set I mean a mathematical set. It has no notion of order and repetitions in notation are irrelevant. For example, these notations all mean the same set containing the numbers 1,2 and 3:

$$ \{ 1,2,3 \} = \{ 3,2,1 \} = \{ 3,1,2,1 \} $$

Sets are probably the most fundamental objects in mathematics. Some areas of mathematics even try to build everything upon sets, so it is worth looking at them in more detail. One of the first things that seems to be missing is the relative order of elements. To capture two elements and their order, one usually writes \( (1,2) \) which denotes the ordered set containing 1 first and 2 second. This is pretty much the mathematical equivalent of an array and of course not the same as \( (2,1) \), because their order is different.

$$ (1,2) \neq (2,1) \text{ but } \{1,2\} = \{2,1\} $$

There seems to be a fundamental difference between the two concepts, right? The astonishing thing is that order can be modeled without order. The notion of order introduced in ordered sets is nothing new and already contained within the notion of an unordered set. Here is a way how an ordered pair of two elements \( a \) and \( b \) can be defined using nothing but unordered sets:

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

As you can see, on the left is the ordered pair and on the right are only unordered sets. This is the standard definition for an ordered pair by Kuratowski 1. The thing on the right is sort of like a data structure built with things we have (unordered sets) for the abstract thing on the left we want to model (ordered pair). Given a proper system of axioms for sets, one can formally prove that this construction has exactly the same properties as an ordered pair. But for now I am satisfied with a bit of intuition for how it works. The main requirement for ordered pairs is the following property:

$$ (a,b) = (c,d) \Rightarrow a = c \land b = d $$

This statement captures the notion of a first and a second element within the pair. If they are different and switch positions, the resulting pair is different. This is how the first element \( x \) can be extracted from the ordered pair \( P = (x,y) \) defined as above:

$$ \forall A \in P : x \in A $$

The elements of \( P \) are sets. One contains both elements and one contains just the first element. Only the first element is contained in both and therefore satisfies this property. That means the “first” element in \( P \) can be characterized in terms of sets. Defining the second element \( y \) is a little bit more involved, but can be done as well. It is the element that is in exactly one of the sets within \( P \). Stated as mathematical formula, this looks something like the following:

\begin{split}
&\exists A \in P: y \in A \quad \land \\
&\forall B,C \in P: B \neq C \rightarrow y \not \in B \lor y \not \in C
\end{split}

In words: There is a set \( A \) in \( P \) such that \( y \) is in \( A \) and for any two different sets in \( P \) , \( y \) is not contained in one of them. The first part says that their is at least one set that contains \( y \) and the second part says that there is at most one of them. Again, only the “second” element of \( P \) satisfies this condition and can therefore be identified in terms of sets.

The last thing I want to look at is what happens for ordered pairs of the form \( (x,x) \) that contain the same element twice. Using the definition and removing repeated elements from set notation yields:

$$ (x,x) = \{ \{ x \}, \{ x,x \} \} = \{ \{ x \}, \{ x \} \} = \{ \{ x \} \} $$

The cool thing about the characterizations of the first and second element above is that they still work in this case:

The element \( x \) satisfies both of them and is therefore the first and the second element. This is a great example of a problem that sounds impossible but has a simple solution. While this one is purely theoretical there are practical questions that are similar. One that comes to my mind is public-key cryptography: Is it possible to communicate securely over an insecure channel? The unintuitive but correct answer is yes. And I think studying “easier” problems that follow this pattern helps understanding and solving harder, more useful questions later on.

References

  1. https://en.wikipedia.org/wiki/Ordered_pair#Kuratowski_definition