W3C home > Mailing lists > Public > www-rdf-logic@w3.org > May 2001

RE: Is the meaning of order intrinsic ?

From: Ziv Hellman <ziv@unicorn.com>
Date: Sat, 26 May 2001 17:45:37 +0200
Message-ID: <6194CD944604E94EB76F9A1A6D0EDD2310CF74@calvin.unicorn.co.il>
To: "Seth Russell" <seth@robustai.net>, <cg@cs.uah.edu>, <www-rdf-logic@w3.org>
> Can anyone define (designate) order itself without using 
> order?   Has anyone
> studied this?  Are there any URLs to their thoughts ?

"Order" is a concept very well-studied in logic and set theory. In fact,
it is sometimes surprising just how little one needs to define/designate
order -- basically just a syntactic binary symbol and a couple of simple
axioms. This is actually a good little example of the interplay between
syntax, constraints, models and our subjective interpretations, that has
caused much locking of horns on this list, so it is worthwhile going
through in some detail the standard model-theoretic point of view on the
matter.

To avoid needless complications, for the rest of this posting I will
equate the word "order" with "total anti-symmetric order" that in plain
language means that I am assuming everything can be placed somewhere in
this one order that is being defined -- so if a and b are objects either
a is greater than b or b is greater than a, i.e. avoiding the
possibility that they are "apples and oranges" and cannot even be
compared  -- and that no two or more objects are "equally placed" in the
order, i.e. discounting the possibility of objects being in "a tie for
second place" and so forth. 

Begin with any binary relation symbol you like (hard-core RDFers believe
everything in life can be reduced to binary relations so there should be
no shortage of these), call it R for short and write a R b for a graphic
representation of the relation. Add to the mix the following axioms:

1) Totality: For each x and each y, either x R y or y R x .
2) Anti-symmetry: For each x and each y, x R y implies not (y R x).  
( One might object at this point and ask if this is not begging the
question because distinguishing between x R y and y R x seems to require
a prior notion of "ordering". But this is really a surface artefact of
the linear form of graphically writing out the relation and does not
touch upon the deeper matter of how objects are related, that has
nothing to do with any particular way of expressing that relation. To
give a concrete example, we recognise that saying "Fred is John's
father" is the same as "John's father is Fred" despite the different
ordering of the names in the sentences, but that both are different from
"John is Fred's father", because Fred and John are involved in a
relationship that at some abstract level is set down forever no matter
how one expresses or writes down a representation of that relationship )
3) Transitivity: For each x and each y and each z, if x R y and y R z,
then x R z.

And that's it. Any model including the symbol R and these three axioms
is now going to have an "order" imposed on it. What is remarkable here
is that there is no need to attach any "meaning" to the syntactical
symbols and axioms: they exist independently of any subjective meaning
we wish to attach to them. We could interpret R as meaning "greater
than", "less than", "before", "after", "older than", "having better
eye-sight", "owning larger tracts of land", and it really will not
matter -- in terms of formal structure the models will all be the same.
Conversely, the formal syntax and axioms _themselves_ cannot supply
meaning, that has to be found in the semantics of what happens in
particular models we work with. It is quite conceivable that during the
modelling of some complicated system one will inadvertently define or
derive equivalent axioms and suddenly notice that one has an order that
was not expected aforethought, with all the attendant implications.

The only "weakness" in this approach is that whilst it certainly
includes the standard notion we have in our head of 0 < 1 < 2 < 3 < ....
-- the "quintessential" order as it were -- as a model, it also includes
lots and lots of wild and strange models of order, from the relatively
"tame" negative and positive integers together, . . .  < -2 < -1 < 0 < 1
< 2 < . . . which is infinitely ordered in both directions, or anything
like  . . . a < b < c . . . q < r . . . where the elliptic dots ...
stand for all sorts of infinities and ordinals galore. One can of course
add axioms to eliminate certain irregularities, like decreeing that
there is one and only one element that is first in the order, and so
forth, but it seems that no matter what one adds there are always
non-standard models that pop up to bugger one's thinking on the matter.


Cheers,

Ziv
Received on Saturday, 26 May 2001 10:46:21 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 22:45:38 UTC