uspořádaná množina

Množina M a na ní relace uspořádání ≤. Uspořádaná množina se označuje (M, ≤) a nazývá se též částečně uspořádaná množina. Každá podmnožina N uspořádané množiny. M je uspořádaná vzhledem k relaci ≤. Je-li x ≤ y, říká se, že prvek x je menší nebo roven prvku y nebo prvek y je větší nebo roven prvku x. Zápis x < y znamená x ≤ y, x ≠ y, a vyjadřuje se slovy x je menší než y, nebo x je před y, nebo y je větší než x nebo y je za x. Prvek z je mezi prvky x a y, jestliže x < z a z < y, nebo y < z, z < x. Dva prvky x, y jsou neporovnatelné, jestliže neplatí ani x ≤ y, ani y ≤ x. Je-li N podmnožina, a prvek množiny M a platí-li a ≤ x (x ≤ a) pro každé x ∈ N, říká se, že a je dolní (horní) mez množiny N. Má-li sama množina M dolní (horní) mez, je tato mez jediná a nazývá se nejmenší (největší) prvek množiny M. Jestliže množina všech horních (dolních) mezi podmnožiny N ⊂ M má nejmenší (největší) prvek n, nazývá se n suprémum (infimum) množiny N. Největší (nejmenší) prvek množiny je nutno odlišovat od maximálního (minimálního) prvku: to je takový prvek a, že z podmínky a ≤ x (x ≤ a) plyne a = x. Uspořádání ≤ na množině M se jmenuje lineární, jestliže pro libovolné prvky x, y v M platí x ≤ y nebo y ≤ x. Lineární uspořádání na množině M se nazývá husté, jestliže pro libovolné dva různé prvky existuje vždy prvek množiny M, který je mezi nimi. Lineární uspořádání se nazývá dobré, má-li každá neprázdná podmnožina množiny M nemenší prvek. Příkladem hustého uspořádání je obvyklé uspořádání množiny racionálních čísel podle velikostí, příkladem dobrého uspořádání je obvyklé uspořádání množiny všech přirozených čísel. Řezem v lineárně uspořádané množině (M, ≤ ) se rozumí uspořádaná dvojice (A, B) neprázdných podmnožin množiny M takových, že A U B = M, A ∩ B = ∅ a x ≤ y pro každé x v A a každé y v B. Řez se nazývá skok, má-li A největší a B nejmenší prvek, nazývá se mezera, nemá-li A největší ani B nejmenší prvek. Lineární uspořádání na množině aspoň dvouprvkové je husté, právě když množina nemá skoky. Přidáním mezer k množině racionálních čísel vzniká množina reálných čísel. Důležitým příkladem lineárního uspořádáni je lexikografické uspořádání slov.