The main goals of this section is make precise what we mean by a list, and to define various other useful objects in terms of them.
We start with ordered pairs. There is a simple way to define ordered pairs which unfortunately does not generalise to ordered triples or beyond, but which we can use as a starting point to construct lists.
What do we want from such a construction?
Given any \({ x }\) and \({ y }\), not necessarily distinct, we should be able to define the pair \({ ( x , y ) }\).
Given any \({ z }\) we should be able to determine whether it is an ordered pair, i.e. whether there exist \({ x }\) and \({ y }\) such that \({ z = ( x , y ) }\).
Given any \({ z }\) which is an ordered pair we should be able to find \({ x }\) and \({ y }\) such that \({ z = ( x , y ) }\).
The \({ x }\) and \({ y }\) above should be uniquely determined by \({ z }\). In other words if also \({ z = ( v , w ) }\) for some \({ v }\) and \({ w }\) then it must be the case that \({ v = x }\) and \({ w = y }\).
With these considerations in mind, we define the Kuratowski pair of \({ x }\) and \({ y }\) as \[ « x , y » = \{ \{ x \} , \{ x , y \} \} . \] I’ve avoided writing this as \({ ( x , y ) }\) for two reasons. First, we don’t yet know that it has the properties listed above. Second, even if it does there might be other constructions which have the same properties and we shouldn’t prematurely commit ourselves to a particular implementation of ordered pairs.
The first property above is fairly obvious. For every \({ x }\) and \({ y }\) the set \({ « x , y » }\) does indeed exist, as a simple consequence of the Axiom of Pairing. The second is much less obvious. What properties does \({ « x , y » }\) have which set it apart from things which are not Kuratowski pairs?
\({ « x , y » }\) is a non-empty set of non-empty sets.
\({ ⋂ « x , y » }\) has exactly one member.
\({ [ ⋃ « x , y » ] ∖ [ ⋂ « x , y » ] }\) has at most one member.
These are all properties which we can express in our language. We can say that a set \({ A }\) has at least one member, even though we don’t have a notation for numbers, by saying \({ ∃ w . w ∈ A }\). Similarly, we can say that \({ A }\) has at least one member by saying that any two members must be equal: \[ ∀ u ∈ A . ∀ v ∈ A . [ u = v ] . \] We can say that a set has exactly one member by taking these two statements and joining them with an \({ ∧ }\).
Each statement is true. The first is clear. The second and third follow from \({ ⋂ « x , y » = \{ x \} }\) and \({ ⋃ « x , y » = \{ x , y \} }\), so \({ [ ⋃ « x , y » ] ∖ [ ⋂ « x , y » ] }\) is either \({ ∅ }\) or \({ \{ y \} }\), according to whether \({ x = y }\) or not.
Is it true that if \({ z }\) satisfies the three conditions
\({ z }\) is a non-empty set of non-empty sets,
\({ ⋂ z }\) has exactly one member, and
\({ [ ⋃ z ] ∖ [ ⋂ z ] }\) has at most one member
then \({ z }\) is an ordered pair? Yes. Suppose \({ z }\) is such a set. Let \({ x }\) be the only member of \({ ⋂ z }\). Let \({ y }\) be the only member of \({ [ ⋃ z ] ∖ [ ⋂ z ] }\), if there is one, and let it be the only member of \({ ⋂ z }\) otherwise. We always have \({ ⋂ z ⊆ ⋃ z }\) so \[ ⋃ z = [ ⋂ z ] ∪ [ [ ⋃ z ] ∖ [ ⋂ z ] ] . \] Now \({ ⋂ z = \{ x \} }\) and either \({ ⋂ z = \{ y \} }\) or \({ ⋂ z = ∅ }\) and \({ [ ⋃ z ] ∖ [ ⋂ z ] = \{ y \} }\) or \({ ⋂ z = \{ y \} }\). In either case we have \[ ⋂ z = \{ x \} \] and \[ ⋃ z = \{ x , y \} . \] Any member of \({ z }\) is a subset of \({ ⋃ z }\) and a superset of \({ ⋂ z }\) but the only sets like that are \({ \{ x \} }\) and \({ \{ x , y \} }\), so \[ z ⊆ \{ \{ x \} , \{ x , y \} \} \] or \[ z ⊆ « x , y » . \] It’s easy to check that any proper subset of \({ « x , y » }\) would violate at least one of the conditions above so \[ z = « x , y » \] This shows that the second of our three properties holds, i.e. that we can identify which sets are Kuratowski pairs. It also shows that the third property holds though, since we’ve uniquely identified \({ x }\) and \({ y }\) from the pair. I’ll refer to \({ x }\) as the left component and \({ y }\) as the right component.
You might reasonably hope to generalise the construction above to triples by defining \[ « x , y , z » = \{ \{ x \} , \{ x , y \} , \{ x , y , z \} \} . \] This turns out not to work though. With this definition \[ « v , v , w » = \{ \{ v \} , \{ v , v \} , \{ v , v , w \} \} \] so \[ « v , v , w » = \{ \{ v \} , \{ v , w \} \} \] and \[ « v , w , w » = \{ \{ v \} , \{ v , w \} , \{ v , w , w \} \} \] so \[ « v , w , w » = \{ \{ v \} , \{ v , w \} \} \] and hence \[ « v , v , w » = « v , w , w » . \] In other words, we have no way of identifying the middle component of the triple. This is in contrast to the situation with pairs, where we could identify the left and right components from the pair.
We’d like to have not just pairs and triples but lists of arbitrary finite length. The Kuratowski construction works for pairs, but not for length greater than two. We can still use it to define lists though. The idea is to define lists as sets of Kuratowski pairs. Each member of the set will have as its left component an element of the list and as it’s right component the list of all subsequent elements. An empty list is just the empty set. A list with one element, say \({ z }\) will be a set whose only member is a pair with \({ z }\) as its left component and the list of all subsequent elements, which is just the empty list, as it’s right component. In other words, \[ ( ) = ∅ \] and \[ ( z ) = \{ « z , ( ) » \} . \] Similarly, a list with two elements, say \({ y }\) and \({ z }\) is a set with two members, one of which is the pair from \({ ( z ) }\) and the other of which is a pair with \({ y }\) as its left component and the set \({ ( z ) }\) as its right component, \[ ( y , z ) = \{ « y , ( z ) » , « z , ( ) » \} . \] Similarly for lists with three elements. \[ ( x , y , z ) = \{ « x , ( y , z ) » , « y , ( z ) » , « z , ( ) » \} . \] You can expand these out, but it rapidly becomes messy. \[ ( x , y , z ) = \{ « x , \{ « y , \{ « z , ∅ » \} » , « z , ∅ » \} » , « y , \{ « z , ∅ » \} » , « z , ∅ » \} . \] To write this fully in our language of course we should proceed further and write each of the seven Kuratowski pairs above as a set of sets, as in the definition of Kuratowski pairs. Fortunately we don’t really need to do that. Even the expansion above isn’t ever needed. We can think of lists as being built from the empty list and prepending elements one at a time. The empty list is the empty set. To prepend an element \({ x }\) to a list \({ A }\) we form the set \[ A ∪ \{ « x , A » \} , \] which is \[ A ∪ \{ \{ \{ x \} , \{ x , A \} \} \} . \]
Everything you might want to do with lists can be done using three basic operations. One is the prepending operation described above, which adds a pair to an existing list. The other two extract the left and right components of the most recently added pair. How do we know which pair was added most recently? It’s the one whose right component is a superset of the right components of the others. Taking the left component of this pair gives the first element of the list. Taking its right component gives the result of removing that element from the list. These only work on non-empty lists, of course.
As an example of decomposing a list operation into these three basic operations, consider reversing a list. We start with the list we want to reverse and an empty list. One by one we remove elements from the list we started with and prepend them to the list which was initially empty until the list we started with has been emptied.
As another example, consider the problem of concatenating two lists, which I’ll call the left list and right list, to distinguish the positions of their elements in the combined list. We start by reversing the left list. We then removed elements from it one at a time and prepend them to the right list. We continue until the left list is empty. The right list will then be their concatenation.
I’ve chosen a representation where new elements are added to a list
from the left. I could equally have chosen one where we add elements
from the right, appending rather than prepending. This particular choice
of representation for lists is borrowed from LISP though and for
historical reasons the choice there is that the newest list element is
the first rather than the last. The three basic list operations
described above have the names cons, car and
cdr in LISP, again for historical reasons. Racket is a
descendent of LISP and those functions all put in a brief appearance in
the Racket program in the introductory chapter.
An important principle in computer science is that of abstraction through interfaces. The idea is to separate the interface from the details of its implementation. A user should be able to rely on the public interface of a system without needing to know any of the details of how it is implemented. In fact, using details of the implementation which are not part of the public interface is strongly discouraged.
In our case we have a notion of lists and basic list operations, like adding an element to the list, extracting the most recently added element and extracting the remainder of the list. The particular implementation may be rather complicated but should never be needed and indeed should never be used beyond proving a small number of basic properties, the fact that if we add an element and then remove it then we are left with the same list we started with, and that the element we extracted is the one we added. Any more complicated operations, like reversal or concatenation should be defined in terms of the basic operations and any properties of the those more complicated operations should be proved from the properties of the basic operations, without reference to the implementation. This is done partly to reduce cognitive load and partly to allow the implementation to be replaced by a different one without any need for external changes.
There’s a difference between mathematics and computer science, but it’s one which makes the principle of separating the interface and implementation even more useful in mathematics than in computer science. The two subjects have different notions of an efficient implementation. The efficiency of an implementation of lists in a programming language or library is mostly a matter of resource usage, and the most important resource is usually time. A program which uses lists won’t need to be rewritten if the list implementation changes, provided it relies only on the public interface and not on the details of the previous implementation, but it may well run faster, so there is an obvious benefit to replacing a simple but slow implementation with a more complicated but faster one. For an implementation of lists in set theory the situation is different. What makes an implementation efficient is the ease with which we can prove that the basic operations have the required properties. Once this is done there’s no real advantage to replacing it with a different implementation. The same applies to abstraction through interfaces in general. Separating interface and implementation is useful in both subjects, but in mathematics efficiency of implementation is a pedagogical issue rather than a practical one.
One advantage of the abstract approach described above is that often we realise that two different interfaces are in fact the same, except for names. Stacks appeared as a data structure in the introductory chapter. I didn’t define them precisely there but the basic operations on a stack are pushing something on to it and popping something off. An implementation of a stack just needs to provide these operations and ensure that the item popped off is the same as the one which was pushed and that the stack after a push and a pop is the same as it was before. If this sounds similar to the rules for lists then that’s because they are, except for terminology, identical. A stack is just a list. In a computing application you might or might not want to implement a stack as a list but from a mathematical point of view there’s no reason not to.
There are a number of ways we could define ordered pairs in set theory. The usual choice is Kuratowski pairs. An equal valid choice would be Kuratowski pairs with the left and right components swapped. The choice of which to call left and which to call right was entirely arbitrary. There are a number of other options available. The particular choice I’m going to make here is to regard ordered pairs as lists with two elements. As long as we only use the basic operations and properties it doesn’t matter which implementation we choose. One minor advantage of using lists of length two though is that we can now entirely forget the notation \({ « x , y » }\).
The set of ordered pairs \({ ( x , y ) }\) with \({ x ∈ A }\) and \({ y ∈ B }\) is called the Cartesian product of \({ A }\) and \({ B }\), written \({ A × B }\). In the common special case where \({ A = B }\) we often write \({ A ^ 2 }\) rather than \({ A × A }\). In a similar way we define \({ A ^ 3 }\) to be the list of ordered triples, i.e. lists of the form \(( x , y , z )\), where each of \({ x }\), \({ y }\) and \({ z }\) is an element of \({ A }\).
\({ A × B }\) is indeed a set, as are \({ A ^ 2 }\) and \({ A ^ 3 }\). This is less obvious than it might seem, but still true.
If \({ A }\) and \({ B }\) are finite sets then \({ A × B }\) is finite. This is proved by a double induction on sets. Suppose \({ x ∈ A }\). Let \({ D }\) be the set of subsets \({ C }\) of \({ B }\) such that \({ \{ x \} × C }\) is finite. \({ \{ x \} × ∅ }\) is \({ ∅ }\), which is finite, so \({ ∅ ∈ D }\). If \({ C ∈ D }\) and \({ y ∈ B }\) then \[ \{ x \} × [ C ∪ \{ y \} ] = [ \{ x \} × C ] ∪ \{ ( x , y ) \} . \] This is the union of two finite sets and so is finite. In other words, \({ ∅ ∈ D }\) and if \({ C ∈ D }\) and \({ y ∈ B }\) then \({ C ∪ \{ y \} ∈ D }\). \({ B }\) is finite so by induction \({ B ∈ D }\). In other words \({ \{ x \} × B \} }\) is finite. Now let \({ F }\) be the set of all subsets \({ E }\) of \({ A }\) such that \({ E × B }\) is finite. \({ ∅ × B }\) is \({ ∅ }\), which is finite, so \({ ∅ ∈ F }\). If \({ x ∈ A }\) then, as we just saw, \({ \{ x \} × B \} }\) is finite. Suppose \({ E ∈ F }\). \[ [ E ∪ \{ x \} ] × B = [ E × B ] ∪ [ \{ x \} × B ] \] so \({ [ E ∪ \{ x \} ] × B }\) is the union of two finite sets and so is finite. In other words, \({ ∅ ∈ F }\) and if \({ E ∈ F }\) and \({ x ∈ A }\) then \({ E ∪ \{ x \} ∈ F }\). \({ A }\) is finite so by induction \({ A ∈ F }\). In other words, \({ A × B }\) is finite.
In particular, if \({ A }\) is finite then so are \({ A ^ 2 }\) and \({ A ^ 3 }\).