Re: Sets and Lists, again

From: Marshall <marshall.spight_at_gmail.com>
Date: 20 May 2006 09:08:43 -0700
Message-ID: <1148141323.785675.261540@u72g2000cwu.googlegroups.com>

David Cressey wrote:

> So, at the logical level, why isn't a list just a set of entries with some
> natural order implied by one of its attributes?

Be careful of the idea of "natural order implied by one of its attributes."
It makes it sound as if there is a distinguished order when there isn't. (Sort of like picking one key to be the primary key.) Any order you can come up with for a relation is just as "natural" as any other order. And the existence of an order on an attribute doesn't make a relation a list.

With a list, there *is* a distinguished order, (as well as all the other orders possible.)

The definition of list is: a target set (relation for our purposes) and a mapping from the natural numbers to the set. More useful in a programming context is a finite list, in which the mapping is from [0..n]. The map and the relation together form the list.

It is important to be clear about the differences among: set, relation, bag, ordered set, ordered bag, list. It's also important to distinguish between a total order, a partial order, and a quasi order. (I will admit
that I don't really understand the last of these yet.)

Marshall Received on Sat May 20 2006 - 11:08:43 CDT