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

Consistent enumeration on a poset

  1. Dec 14, 2008 #1
    Hey all,

    I've got a copy of Schaum's outline of Discrete Mathematics, and in the section on ordered subsets and lattices, it includes the definition of a consistent enumeration:

    Succinctly, given a poset P, there exists f: P -> N, so that if a < b then f(a) < f(b)


    However, I had this in my notes that it was not just a function but an injection. Of course, looking at it again, I didn't consider the case of a || b. I don't know where I got this from and now I'm slightly confused. The closest I could find to this definition was a linear extension and topological sorting, which are slightly different.

    Does anyone know this topic well enough to dispell my confusion?

    - Farley
  2. jcsd
  3. Dec 14, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor

    IF P is linearly ordered, then "if a< b then f(a)< f(b)" implies that f is an injection. However, in a partially ordered set, it may happen that a and b are "not comparable" (i.e. none of a= b, a< b, nor b< a is true) in which case f(a) may equal f(b) and so f is not necessarily an injection.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Consistent enumeration on a poset
  1. Recursively enumerable? (Replies: 14)