gil@daffy.gatech.edu (Gil Neiger) (02/09/91)
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 "<"? - GIl Neiger gil@cc.gatech.edu
crew@CS.Stanford.EDU (Roger Crew) (02/09/91)
In article <824@mephisto.edu> gil@daffy.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[n irreflexive partial order < such that] > "not related" relation | [i.e., (p | q) iff (not(p < q) and not(q < p))] > is an equivalence [relation].... Is there a name for the relation "<"? I'd call it the complemented transpose of a total preorder (<@, as defined by p <@ q === not(q<p), is reflexive, transitive, and total). -- Roger Crew Usenet: {arpa gateways, decwrl, uunet, rutgers}!cs.stanford.edu!crew Internet: crew@CS.Stanford.EDU
sakkinen@tukki.jyu.fi (Markku Sakkinen) (02/15/91)
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)
fulk@cs.rochester.edu (Mark Fulk) (02/16/91)
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