Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complete preorders (and other binary relations)

  1. Aug 30, 2006 #1


    User Avatar
    Science Advisor
    Homework Helper

    Is there a commonly-used name for a complete preorder (a transitive and total relation, Sloan's A000670 and A011782 for labeled and unlabeled, respectively) within set theory? (Not a total order, mind you -- it need not be antisymmetric.) I've heard the term "weak order", but that's from the same field that uses "linear order" for total orders, so I wanted some clarification if anyone knows of something else.

    Also, does anyone know about counting the number of elements in complete relations? Götz Pfeiffer has an excellent paper Counting Transitive Relations about counting transitive relations (mentioning 26 classes of relations along the way), but he doesn't touch on the slightly-more-manegable complete relations at all.
    Last edited: Aug 30, 2006
  2. jcsd
  3. Aug 30, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I've heard the term "total preorder".

    What's a "complete relation"? I've not heard the term before. Is it one where at least one of xRy and yRx is true?
  4. Aug 30, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    Ah, yes, that's the term. I knew I had heard something like that, thanks.

    Yes, xRy V yRx for every x, y in the set. What do you call that, totality?

    In any case, on the second part of my question, I've been putting together a spreadsheet with the values (actually their logarithms, since otherwise they'd be prohibitively large) of combinations of properties for labeled binary relations. With C = complete/total, R = reflexive, S = symmetric, T = transitive, and A = antisymmetric, I have all 17 interesting combinations figured out now:
    --, R, C, S, RS, T, TA, ST, RT, CT, CTA, A, RA, CA, STA, RTA, RST

    I have a OEIS number for each one (with modification if needed), and values at least as far as Sloan's sequences go (and further in some cases).
    Last edited: Aug 30, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Complete preorders binary Date
B Not sure what this problem would be called... Apr 4, 2017
Lattice/Complete lattice Jun 10, 2014
Confidence of complete spatial randomness May 8, 2014
Complete Random Design vs RCBD Sep 7, 2013
Completeness notions in logic Feb 23, 2013