1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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)