Re: Sets and Lists, again

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Sat, 20 May 2006 17:25:48 GMT
Message-ID: <wiIbg.10289$A26.254147@ursa-nb00s0.nbnet.nb.ca>

Marshall wrote:

> 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.

And a map is a 1:1 function. Thus if one has a relation of tuples r in R and a finite range of i in [0..n], as long as one has a function f(r) in [0..n] with inverse f'(i) in R such that r = f'(f(r)) and i = f(f'(i)), one has a list.

But one also has a list if one has a relation of tuples r in R and a binary relation over R that is a total order. Depending on the definition of quasi order used, one might have a list with one of those too.

> It is important to be clear about the differences among: set, relation,
> bag, ordered set, ordered bag, list.

Of those, a list is just a set, a function and its inverse, or a set and a total order binary relation.

  It's also important to distinguish
> between a total order, a partial order, and a quasi order.

Yes. A partial order that is not a total order can yield multiple linear orders using a topological sort, and that seems important enough to me.

  (I will
> admit
> that I don't really understand the last of these yet.)

The fact that there are two mutually exclusive definitions for 'quasi order' might have something to do with the difficulty comprehending it. Received on Sat May 20 2006 - 12:25:48 CDT