Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to prove this if and only if statement and I cant get anything written down.. Let le(X,≼) denote the number of linear extensions of a partially ordered set (X,≼). Prove le(X,≼)=1 if and only if ≼ is a linear ordering.

share|improve this question
1  
What are your thoughts? Can you do one of the directions? Have you proved that every poset has at least one linear extension? –  Henning Makholm Sep 11 '13 at 14:44

1 Answer 1

One direction is easy. If $(X,\leq)$ is a linear order then it only has one linear extension (show that if $(X,\leq')$ is a linear extension then it adds nothing new).

In the other direction, if $(X,\leq)$ is not a linear order then there are $a,b\in X$ such that $a\nleq b$ and $b\nleq a$. Show that you can extend $\leq$ by deciding $a\leq'b$ or you can extend it in the other direction. This must give you at least two different extensions for $(X,\leq)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.