Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!rochester!fulk
From: fulk@cs.rochester.edu (Mark Fulk)
Newsgroups: comp.theory
Subject: Re: Name for a Relation?
Message-ID: <1991Feb15.171244.16710@cs.rochester.edu>
Date: 15 Feb 91 17:12:44 GMT
References: <1991Feb9.000807.11653@Neon.Stanford.EDU> <37213@netnews.upenn.edu> <1991Feb15.073024.24630@tukki.jyu.fi>
Organization: University of Rochester Computer Science Department
Lines: 53

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 "<"?

The relation "<=" defined by x<=z iff x<z or x|z is a pre-order of
a total order.  If you call "<" a strict order, I guess a fair term
would be a "strict pre-total-order."

1) The equivalence relation "|" respects the ordering, in a
particularly strong sense:

w|x and y|z -> [w<y iff x<z]

Proof:
Assume w|x, y|z, and w<y.
not w|z, because otherwise w|y by transitivity of |.
not z<w, because then y<z by transitivity of <.
Therefore, w<z.

not x|z, because otherwise w|z by transitivity of |.
not x>z, because otherwise x>w by transitivity of >.
Therefore x<z.

So we have w|x and y|z imply [w<y implies x<z].
By symmetry, we have w|x and y|z imply [x<z implies w<y].
This establishes the claim.

(Please pardon the tedious proof; I found the problem messy
enough that I wanted to be very formal to be sure.)

2) The quotient order is total: if two |-classes are incomparable,
all of their elements are incomparable, and they should not be
separate |-classes.

Mark