Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!rice!uupsi!sunic!news.funet.fi!tukki.jyu.fi!sakkinen
From: sakkinen@tukki.jyu.fi (Markku Sakkinen)
Newsgroups: comp.theory
Subject: Re: Name for a Relation?
Message-ID: <1991Feb15.073024.24630@tukki.jyu.fi>
Date: 15 Feb 91 07:30:24 GMT
References: <824@mephisto.edu> <1991Feb9.000807.11653@Neon.Stanford.EDU> <37213@netnews.upenn.edu>
Reply-To: sakkinen@jytko.jyu.fi (Markku Sakkinen)
Organization: University of Jyvaskyla, Finland
Lines: 54

In article <824@mephisto.edu> gil@cc.gatech.edu (Gil Neiger) writes:

> I am dealing with a kind of relation and I'm wondering if there's
> a name for it.  It's a binary relation that is irreflexive, transitive
> and antisymmetric (in other words, it's a partial order that's
> irreflexive).  Added to this I have the following condition:  the
> "not related" relation is an equivalence class.
> 
> More formally, suppose that my relation is denoted by "<".  Define
> "not related," using the symbol "|" as follows:
> 
> 	(p | q) if and only if (not(p < q) and not(q < p))
> 
> My relation < has the property that
> 
> 	if p|q and q|r, then p|r.
> 
> Thus, the "not related" relation (|) is transitive; since < is
> irreflexive, | is reflexive; by definition it is symmetric.
> 
> Given all this, is there a name for the relation "<"?

It may be illuminating to look at this also from the
more general viewpoint of quasi-orders (preorders),
like Roger Crew already did.  Whereas a partial order can be
defined either in the more usual way with 'less-or-equal' (`<=')
or as strict with `<', a general quasi-order cannot be uniquely
determined by `<'.

An interesting subset of quasi-orders are "weak orders"
(so called at least by Suppes), which can be considered as
total (linear) orders between equivalence classes.
A quasi-order that is both a weak order and a partial order
is total.  In a paper, I have used the term "virtual weak order"
for a quasi-order that can be transformed into a weak order
by making incomparable (not related) elements equivalent.
The necessary and sufficient condition is exactly that the
"not related" relation be transitive.

Since your type of relation is a partial order, there is moreover
a one-to-one relationship between such orders and the corresponding
weak orders.  If your purpose is to represent such orders in
a computer, the good news is that they are no worse
than total orders;  i.e., for N elements you will need
only space proportional to N (or N*log N), while partial orders
and quasi-orders in general need N*N (or N*N*log N).

Markku Sakkinen
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
          SAKKINEN@FINJYU.bitnet (alternative network address)