Oszacowanie liczby rozszerzeń porządku

[materla]

Prosiłbym o oszacowanie liczby rozszerzeń skończonego porządku do porządku liniowego, co jak wiadomo można zrobić.

[Jakub Gurak]

Na niepustym skończonym zbiorze \(\displaystyle{ X}\), zbiorze \(\displaystyle{ n}\)- elemento\(\displaystyle{ }\)wym rozważ porządek identycznościowy \(\displaystyle{ I _{X}, }\) i zauważ, że dowolny porządek liniowy \(\displaystyle{ \le }\) na \(\displaystyle{ X}\) rozszerza porządek \(\displaystyle{ I _{X} }\), gdyż wtedy \(\displaystyle{ \le }\) jest relacji zwrotną, a więc \(\displaystyle{ \left( \le \right) \supset \left( I _{X} \right) }\), czyli porządek \(\displaystyle{ \le }\) rozszerza porządek \(\displaystyle{ I _{X}. }\)
Zatem tych porządków rozszerzających jest tutaj tyle, ile jest wszystkich porządków liniowych na zbiorze \(\displaystyle{ n}\)- elementowym, czyli tyle ile jest wszystkich bijekcji zbioru \(\displaystyle{ n}\)- elementowego, czyli \(\displaystyle{ n!}\)

W innym przypadku tych porządków jest oczywiście co najwyżej \(\displaystyle{ n!}\) i co najmniej \(\displaystyle{ 1.}\)