- From: Ziv Hellman <ziv@unicorn.com>
- Date: Sat, 26 May 2001 17:45:37 +0200
- To: "Seth Russell" <seth@robustai.net>, <cg@cs.uah.edu>, <www-rdf-logic@w3.org>
- Message-ID: <6194CD944604E94EB76F9A1A6D0EDD2310CF74@calvin.unicorn.co.il>
> 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