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.
Written by Eddy.