2003-03-04

The trouble with triples (and other tuples)

Ever since I first studied discrete mathematics and read Paul R. Halmos' Naive Set Theory, I've been bothered by the conventional definition of tuples in terms of sets.

The definition usually goes something like this: An ordered pair (that is, a 2-tuple) <a, b> is the set { {a}, {a, b} }. It is easy to see that this definition results in the desirable property that <a, b> = <c, d> if and only if a = c and b = d.

However, this leaves us with a strange result when we want to represent the ordered pair <a, a>. Plugging a for b above, we have:

<a, a>
= { { a }, { a, a } }
= { { a }, { a } }
= { { a } }.

This gets ugly when we ask about the cardinality of the ordered pair <a, b>. If ab, then the cardinality is 2, which fits nicely with the object being an ordered pair. If, however, a = b, the cardinality is 1! It is just not natural for an object supposedly containing two elements to have a cardinality of 1.

Aside: Whenever one thing is modeled by another, you must contend with the fidelity of the modeling. Most instances of modeling involve ignoring certain aspects of what is being modeled and reflecting others in the model. The fidelity of the model is the degree to which properties and operations on the model correspond to properties and operations on the subject. Therefore, the conventional ordered pair definition is perfectly fine if fidelity with respect to cardinality is not important, but I consider cardinality to be a rather significant property of a sequential structure. I would expect a model of a sequence to have a natural preservation of cardinality (length).

Extending the above ordered pair (2-tuple) construction to triples (3-tuples) yields:

<a, b, c>
= <a, <b, c> >
= { { a }, { a, <b, c> } }
= { { a }, { a, { { b }, { b, c } } } }.

Plugging a for both b and c yields:

<a, a, a>
= <a, <a, a> >
= { { a }, { a, <a, a> } }
= { { a }, { a, { { a }, { a, a } } } }
= { { a }, { a, { { a }, { a } } } }
= { { a }, { a, { { a } } } }
= <a, { { a } } >.

Not only do we have a cardinality of 2 for a 3-tuple, but we also have a perfectly valid interpretation of a single underlying set as either an ordered pair (<a, { { a } } >) or as a triple (<a, a, a>)! This latter complaint isn't really surprising given the way 3-tuples are defined in terms of 2-tuples in the first place. But, the implication is that you cannot write an is-triple predictate, because you can't tell the difference between an ordered pair with something that could be interepreted as another tuple as its second element and an ordered pair with something that should be interpreted as another tuple as its second element.

We've seen how the conventional modeling of tuples as sets fails to preserve an important property of sequences (cardinality of the resulting sets doesn't correspond to size of the tuples), and how the convention leads to ambiguous interpretations. Now, lets have a look at the most important operation on a tuple: selection. If P is an ordered pair, then we will refer to its first element as P0 and its second element as P1. How shall we express Pi in terms of P? An easy answer is:

P0 = a: ∃ b : P = <a, b>
P1 = b: ∃ a : P = <a, b>

But, you can see that we have to know in advance that we are treating P as an ordered pair. We are not treating it as a generic tuple of some size n to be indexed by some integer 0 ≤ i < n. The selection formulas for the first two elements of a 3-tuple would differ from the formulas just given. And, with the example above that demonstrated ambiguity, applying the formula just shown for P1 would yeild { { a } } instead of just a!

The net result of the above is that while the conventional representation of tuples can work fine for some applications, it has some important limitations, including the inability to use them in mixed environments (you cannot have a set S of tuples and partition it into sets of various tuple sizes, because you cannot in general tell the difference between tuples of of varying sizes). For some applications, you will need a more robust collection construct to model the sequential concept.

Many people treat set theory as if it were The Foundation of Mathematics, with some special claim to that title by virtue of its concept of "set" being an extremely stripped down modeling of a collective concept. I, however, do not share that view (as is probably evident by now). I think that there are reasons to look elsewhere for foundational constructs, and further that there is no reason to require there to be a One True Collection (as sets are often treated).

While there may be a great generic set-based way to model a generic sequential collection that has fidelity over broad application areas, I have not seen it. I take the tuple troubles pointed out above to be evidence that obtaining generic temporality (I prefer the term "temporal" to the term "sequential" for reasons I'll give in a moment) from a non-temporal construct is tricky. In fact, I referred to it as "conventional" above because it connotes not only "common" and "normal", but also "agreed" (the connotation of "unoriginal" doesn't really apply in my opinion, because the construction is clever, if problematic). It is the "agreed" meaning that actually causes the problems. Tuples of various sorts are not self-identifying as such. Information from outside (a convention) is required to determine that some sets are to be treated as plain old sets, and some are to be treated as ordered pairs, and so on.

I view temporality as a sufficiently intuitive concept to be an appropriate property of a primitive collective construct. In fact, since temporality is a part of our everyday experience, and since communication takes place on a temporal background (order of presentation), I view temporality as even more basic than atemporality. There are two reasons I use the term "temporal" rather than "sequential" to refer to this ordering notion. The first is that our time sense is a very basic example of ordering, and the second is that the term "sequence" has some specific additional connotations that I want to avoid at this point in the development of alternative conceptions of structures.

In my conceptualization, there is a family of four primitive collective constructs based on two boolean properties: temporality and plurality. A set is an atemporal (unordered), aplural (containing at most one of each kind) collection. A bag is an atemporal, plural collection. A sequence is a temporal, plural collection, and an order is a temporal, aplural collection.

Another way of looking at plurality is that some collections (sets and orders) deal with species (e.g., "the electron"), and some (bags and sequences) deal with specimens (e.g., "that electron").

With this broader palette of primitive constructs, it is much easier to model a broader set of constructs without introducing strange representational artifacts. But, if forced to choose only one to use, I would use sequences, since it is easier to ignore its temporality and/or plurality properties to model any of the other three constructs. And, the sequence corresponds directly to the way we use language to describe collections. For example, we say: "the set containing a, b, and c", which has a definite order of presentation, even though we know we are supposed to treat the order as insignificant because the words refer to a set. The same is true of the shorthand {a, b, c}. And, after all, ignoring some properties of objects is a normal step in the modeling process (we do it quite readily in counting arbitrary objects).

1 comment:

Gregor Purdy said...

[[ IMPORTING OLD BLOG COMMENT FROM "Gregor" <gregor@focusresearch.com> at 2007-05-28 4:53 PM -- http://www.focusresearch.com/gregor ]]

A recent article at Good Math, Bad Math dealt with the Axiom of Pairing, and some of the comments on that article touch on the issues treated here, although not as completely.