Pairs

A notion which regularly arises in describing things is the notion of a pair. One way or another this carries two values and has a sense of which way round it is holding them: it has a first value and a second value. This can be taken as a primitive notion and used to build lists (given one other special value, the empty list), hence (finite) collections, whence collections of pairs. A collection of pairs can be interpreted as a relation (eg as r relates x to y iff [y,x] is one of the pairs in the collection r), which suffices to give us mappings. This makes pairs a good enough foundation for my tastes.

We can equally obtain the same varieties of entities, with essentially the same behaviours, by taking collections, relations or mappings as foudation. On each of these foundations we can build tools to do the descriptive tasks which call for pair-like notions: indeed, since they serve as equivalent foundations, any tool we can build in one we can build in the others.

When founded on collections, we can represent the pair x before y as a collection such as {{x},{y,empty}} or {{x},{y,x}}. Some care is needed to ensure that we can extract x and y from the collection and know which is which. [Given p={{x},{y,x}}, we know p is non-empty and has at most at most two members; if it has only one member, that is {x}={y,x}, which implies that p's one member is a singleton with y=x as the sole member of that singleton; otherwise, p has two members, one of which is a singleton, the other of which has distinct members, one of which is the sole member of the singleton; so we can identify x as the member of the singleton and y as the other member of p's other member. A slightly more laboured argument shows {{x},{y,empty}} is also unambiguous: notice, by contrast, that {{x},{y}} isn't.] Given pairs, in this form, it is possible to build relations, hence mappings, as collections of pairs. However, I find this construction of pairs somewhat contrived.

In considering relations or mappings, the notion of the singleton arises as an atomic relation, which relates some unique x to some unique y: this is consequently a mapping. Because a singleton binds together two values, and distinguishes them, singleton can serve as a pair notion. However, since it already has the name singleton, I don't need to use up the name pair on it.

From any of the foundations, we can obtain a collection called the natural numbers: its members are 0, 1, ...; every member other than 0={} is 1+n for some natural number n, and 1+n = {n,...,0}. A mapping f for which (|f) is a natural number is called a list.

We can construct the notion of lists from an arbitrary pair notion, given a non-pair to use as stop value by which to terminate [w,...,a] = Pair(a, Pair(...,Pair(w,stop)...)). However, lists as mappings from a natural number work much more comfortably, so they're what I use.

We can (as any Lisp programmer can avow) build up, from lists, any structure about which we can perform computation. In principle, any science which is to be amenable to quantitative prediction should be expressible using pairs alone: their one limitation is in the handling of infinities, which are fictitious (in the sense that they are non-exhibitable). However, using pairs to build up lists involves list of length 2 not being a simple pair (but, instead, [b,a] is Pair(a,Pair(b,stop)) - or, possibly, Pair(Pair(stop,b),a) - for some stop token, which must be a non-pair, such as empty). Why have a hard time getting lists from pairs when I could have pairs as an easy special case of lists ? Consequently

I define a pair to be a list of length 2={1,0}. This is the pair-notion that I use when the pairs are crying out to be generalised to longer lists. The pair [b,a] maps 0 to a and 1 to b: a is its first entry.

Pairs get their place in the roll of honour because they are the lists actually needed, when using collections as a foundation, for the construction of relations and (hence) mappings.