Uspořádané množiny Jan Paseka Masarykova univerzita Brno Uspořádané množiny ­ p.1/44 Abstrakt Uspořádané množiny ­ p.2/44 Abstrakt V této kapitole budeme podrobněji studovat relace na množině, které splňují současně několik z dříve definovaných vlastností relací. Uspořádané množiny ­ p.2/44 Abstrakt V této kapitole budeme podrobněji studovat relace na množině, které splňují současně několik z dříve definovaných vlastností relací. Stěžejním pojmem je uspořádání jakožto reflexivní, antisymetrická a tranzitivní relace na množině. Uspořádané množiny ­ p.2/44 Abstrakt V této kapitole budeme podrobněji studovat relace na množině, které splňují současně několik z dříve definovaných vlastností relací. Stěžejním pojmem je uspořádání jakožto reflexivní, antisymetrická a tranzitivní relace na množině. Dalším pojmem je pojem hasseovského diagramu uspořádané množiny, který koresponduje zjednodušenému uzlovému grafu relace. Uspořádané množiny ­ p.2/44 Abstrakt V této kapitole budeme podrobněji studovat relace na množině, které splňují současně několik z dříve definovaných vlastností relací. Stěžejním pojmem je uspořádání jakožto reflexivní, antisymetrická a tranzitivní relace na množině. Dalším pojmem je pojem hasseovského diagramu uspořádané množiny, který koresponduje zjednodušenému uzlovému grafu relace. Aplikací výše uvedených pojmů zkonstruujeme množinu reálných čísel. Uspořádané množiny ­ p.2/44 Obsah přednášky Ú vod Uspořádání a uspořádaná množina, řetězec. Hasseovský diagram uspořádané množiny. Uspořádané množiny ­ p.3/44 Obsah přednášky Ú vod Uspořádání a uspořádaná množina, řetězec. Hasseovský diagram uspořádané množiny. Největší a nejmeněí prvek. Maximální a minimální prvek. Uspořádané množiny ­ p.3/44 Obsah přednášky Ú vod Uspořádání a uspořádaná množina, řetězec. Hasseovský diagram uspořádané množiny. Největší a nejmeněí prvek. Maximální a minimální prvek. Ř ez, skok, mezera. Konstrukce reálných čísel. Uspořádané množiny ­ p.3/44 Relace uspořádání Necht' (A, ) je množina s relací, přičemž relace je reflexivní, antisymetrická a tranzitivní. Uspořádané množiny ­ p.4/44 Relace uspořádání Necht' (A, ) je množina s relací, přičemž relace je reflexivní, antisymetrická a tranzitivní. Pak relace se nazývá uspořádání a (A, ) se nazývá uspořádaná množina. Uspořádané množiny ­ p.4/44 Relace uspořádání Necht' (A, ) je množina s relací, přičemž relace je reflexivní, antisymetrická a tranzitivní. Pak relace se nazývá uspořádání a (A, ) se nazývá uspořádaná množina. Je ­ li navíc relace úplná, pak se nazývá lineární uspořádání. Uspořádané množiny ­ p.4/44 Relace uspořádání Necht' (A, ) je množina s relací, přičemž relace je reflexivní, antisymetrická a tranzitivní. Pak relace se nazývá uspořádání a (A, ) se nazývá uspořádaná množina. Je ­ li navíc relace úplná, pak se nazývá lineární uspořádání. (A, ) se pak nazývá lineárně uspořádaná množina nebo krátce řetězec. Uspořádané množiny ­ p.4/44 Příklady uspořádání I Příklad U 1. Relace inkluze R = na množině 2A = P(A) (tzn. na množině všech podmnožin množiny A) je relací uspořádání. Uspořádané množiny ­ p.5/44 Příklady uspořádání I Příklad U 1. Relace inkluze R = na množině 2A = P(A) (tzn. na množině všech podmnožin množiny A) je relací uspořádání. Přitom (2A , ) je lineárně uspořádaná množina právě když množina A je prázdná nebo jednoprv- ková (tzn. právě když množina 2A má jeden nebo dva prvky). Uspořádané množiny ­ p.5/44 Příklady uspořádání II Příklad U 2. Relace dělitelnosti | na množině všech přirozených čísel N je relací uspořádání. Uspořádané množiny ­ p.6/44 Příklady uspořádání II Příklad U 2. Relace dělitelnosti | na množině všech přirozených čísel N je relací uspořádání. Přitom (N, | ) není lineárně uspořádaná množina. Uspořádané množiny ­ p.6/44 Příklady uspořádání II Příklad U 2. Relace dělitelnosti | na množině všech přirozených čísel N je relací uspořádání. Přitom (N, | ) není lineárně uspořádaná množina. Relace dělitelnosti na množině všech celých čísel Z není relací uspořádání, a to proto, že není antisymetrická. Uspořádané množiny ­ p.6/44 Příklady uspořádání III Příklad U 3. Relace uspořádání čísel podle velikosti na množině N je relací lineárního uspořádání. Uspořádané množiny ­ p.7/44 Příklady uspořádání III Příklad U 3. Relace uspořádání čísel podle velikosti na množině N je relací lineárního uspořádání. Tedy (N, ) je lineárně uspořádaná množina. Uspořádané množiny ­ p.7/44 Příklady uspořádání III Příklad U 3. Relace uspořádání čísel podle velikosti na množině N je relací lineárního uspořádání. Tedy (N, ) je lineárně uspořádaná množina. Relací "uspořádání čísel podle velikosti" rozumíme relaci definovanou způsobem známým ze střední školy, tzn. x y právě když y - x je nezáporné číslo. Uspořádané množiny ­ p.7/44 Příklady uspořádání IV Příklad U 4. Relace uspořádání čísel podle velikosti je relací lineárního uspořádání na množině všech celých čísel Z, racionálních čísel Q a reálných čísel R. Uspořádané množiny ­ p.8/44 Příklady uspořádání IV Příklad U 4. Relace uspořádání čísel podle velikosti je relací lineárního uspořádání na množině všech celých čísel Z, racionálních čísel Q a reálných čísel R. Dostáváme tak lineárně uspořádané množiny (Z, ) , (Q, ) a (R, ) . Uspořádané množiny ­ p.8/44 Příklady uspořádání V Příklad U 5. Pro libovolnou množinu A je diagonální relace A uspořádání na A. Uspořádané množiny ­ p.9/44 Příklady uspořádání V Příklad U 5. Pro libovolnou množinu A je diagonální relace A uspořádání na A. Uspořádaná množina (A, A) se nazývá protiřetězec. Uspořádané množiny ­ p.9/44 Příklady uspořádání VI Příklad U 6. Bud' n přirozené číslo a uvažme množinu Dn dělitelů čísla n. Relace dělitelnosti | na množině Dn je relací uspořádání. Uspořádané množiny ­ p.10/44 Příklady uspořádání VI Příklad U 6. Bud' n přirozené číslo a uvažme množinu Dn dělitelů čísla n. Relace dělitelnosti | na množině Dn je relací uspořádání. Přitom (Dn, | ) není lineárně uspořádaná mno- žina. Uspořádané množiny ­ p.10/44 Ú mluva Libovolnou relaci uspořádání budeme v dalším při obecných úvahách označovat symbolem ("menší nebo rovno") místo symbolu nebo jiných řeckých písmen. Uspořádané množiny ­ p.11/44 Ú mluva Libovolnou relaci uspořádání budeme v dalším při obecných úvahách označovat symbolem ("menší nebo rovno") místo symbolu nebo jiných řeckých písmen. Totiž klasickým příkladem relace uspořádání je uspořádání čísel podle velikosti, označované standardně symbolem Uspořádané množiny ­ p.11/44 Ú mluva Libovolnou relaci uspořádání budeme v dalším při obecných úvahách označovat symbolem ("menší nebo rovno") místo symbolu nebo jiných řeckých písmen. Totiž klasickým příkladem relace uspořádání je uspořádání čísel podle velikosti, označované standardně symbolem Místo konjunkce x y x = y budeme stručně psát x < y Uspořádané množiny ­ p.11/44 Grafické znázornění I Uspořádanou množinu (A, ) můžeme (zejména, je ­ li množina A konečná) znázorňovat graficky. Uspořádané množiny ­ p.12/44 Grafické znázornění I Uspořádanou množinu (A, ) můžeme (zejména, je ­ li množina A konečná) znázorňovat graficky. Postupujeme přitom následujícím způsobem: Uspořádané množiny ­ p.12/44 Grafické znázornění I Uspořádanou množinu (A, ) můžeme (zejména, je ­ li množina A konečná) znázorňovat graficky. Postupujeme přitom následujícím způsobem: 1. Prvky množiny A znázorníme jako body v rovině. Uspořádané množiny ­ p.12/44 Grafické znázornění I Uspořádanou množinu (A, ) můžeme (zejména, je ­ li množina A konečná) znázorňovat graficky. Postupujeme přitom následujícím způsobem: 1. Prvky množiny A znázorníme jako body v rovině. 2. Je ­ li x < y pak bod x nakreslíme níže než bod y. Uspořádané množiny ­ p.12/44 Grafické znázornění I Uspořádanou množinu (A, ) můžeme (zejména, je ­ li množina A konečná) znázorňovat graficky. Postupujeme přitom následujícím způsobem: 1. Prvky množiny A znázorníme jako body v rovině. 2. Je ­ li x < y pak bod x nakreslíme níže než bod y. 3. Dva body x, y spojíme úsečkou právě tehdy, když x < y a neexistuje žádný bod "mezi nimi", tzn. neexistuje k A tak, že x < k k < y . Uspořádané množiny ­ p.12/44 Grafické znázornění II Výsledný graf se pak nazývá hasseovský diagram uspořádané množiny (A, ) . Uspořádané množiny ­ p.13/44 Grafické znázornění II Výsledný graf se pak nazývá hasseovský diagram uspořádané množiny (A, ) . Jedná se o zjednodušený uzlový graf relace . Uspořádané množiny ­ p.13/44 Grafické znázornění II Výsledný graf se pak nazývá hasseovský diagram uspořádané množiny (A, ) . Jedná se o zjednodušený uzlový graf relace . Jsou vynechány šipky, které by měly být u každého bodu. Uspořádané množiny ­ p.13/44 Grafické znázornění II Výsledný graf se pak nazývá hasseovský diagram uspořádané množiny (A, ) . Jedná se o zjednodušený uzlový graf relace . Jsou vynechány šipky, které by měly být u každého bodu. Je vynechána orientace šipek, která je nahrazena umístěním bodu "níže" či "výše". Uspořádané množiny ­ p.13/44 Grafické znázornění II Výsledný graf se pak nazývá hasseovský diagram uspořádané množiny (A, ) . Jedná se o zjednodušený uzlový graf relace . Jsou vynechány šipky, které by měly být u každého bodu. Je vynechána orientace šipek, která je nahrazena umístěním bodu "níže" či "výše". Jsou vynechány "zbytečné" šipky, jejichž existence plyne z tranzitivnosti relace . Uspořádané množiny ­ p.13/44 Příklady uspořádání VII Příklad U 7. Necht' A = {a, b, c} ; potom je 2A = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. Hasseovský diagram uspořádané množiny (2A , ) je znázorněn na obrázku a). Č ást hasseovského diagramu uspořádané množiny (N, | ) z příkladu je znázorněna na obrázku b). Č ást hasseovského diagramu uspořádané množiny (N, ) je znázorněna na obrázku c). Uspořádané množiny ­ p.14/44 Příklady uspořádání VII Příklad U 7. Necht' A = {a, b, c} ; potom je 2A = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. Hasseovský diagram uspořádané množiny (2A , ) je znázorněn na obrázku a). Č ást hasseovského diagramu uspořádané množiny (N, | ) z příkladu je znázorněna na obrázku b). Č ást hasseovského diagramu uspořádané množiny (N, ) je znázorněna na obrázku c). Uspořádané množiny ­ p.14/44 Příklady uspořádání VII Příklad U 7. Hasseovské diagramy ¤§¨ ¤§¨ a) b) c) Uspořádané množiny ­ p.15/44 Duální uspořádání Je-li uspořádání na množině A, pak inverzní relace -1 je rovněž uspořádání na A a toto uspořádání obvykle značíme symbolem . Uspořádané množiny ­ p.16/44 Duální uspořádání Je-li uspořádání na množině A, pak inverzní relace -1 je rovněž uspořádání na A a toto uspořádání obvykle značíme symbolem . Příslušná uspořádaná množina (A, ) se pak nazývá duálně uspořádaná k množině (A, ). Uspořádané množiny ­ p.16/44 Duální uspořádání Je-li uspořádání na množině A, pak inverzní relace -1 je rovněž uspořádání na A a toto uspořádání obvykle značíme symbolem . Příslušná uspořádaná množina (A, ) se pak nazývá duálně uspořádaná k množině (A, ). Je-li množina A konečná, potom hasseovský dia- gram uspořádané množiny (A, ) vznikne překlo- pením hasseovského diagramu množiny (A, ) ,,vzhůru nohama". Uspořádané množiny ­ p.16/44 Význačné prvky Necht' (M, ) je uspořádaná množina. Prvek a M se nazývá Uspořádané množiny ­ p.17/44 Význačné prvky Necht' (M, ) je uspořádaná množina. Prvek a M se nazývá nejmenší, jestliže pro každé x M platí: a x Uspořádané množiny ­ p.17/44 Význačné prvky Necht' (M, ) je uspořádaná množina. Prvek a M se nazývá nejmenší, jestliže pro každé x M platí: a x největší, jestliže pro každé x M platí: x a Uspořádané množiny ­ p.17/44 Význačné prvky Necht' (M, ) je uspořádaná množina. Prvek a M se nazývá nejmenší, jestliže pro každé x M platí: a x největší, jestliže pro každé x M platí: x a minimální, jestliže neexistuje prvek x M s vlastností: x < a Uspořádané množiny ­ p.18/44 Význačné prvky Necht' (M, ) je uspořádaná množina. Prvek a M se nazývá nejmenší, jestliže pro každé x M platí: a x největší, jestliže pro každé x M platí: x a minimální, jestliže neexistuje prvek x M s vlastností: x < a maximální, jestliže neexistuje prvek x M s vlastností: a < x . Uspořádané množiny ­ p.19/44 Srovnatelné prvky Dále, dva prvky x, y M se nazývají srovnatelné, jestliže platí, že x y nebo y x . V opačném případě se prvky x, y nazývají nesrovnatelné. Uspořádané množiny ­ p.20/44 Příklady uspořádání - VIII Příklad U.8 Necht' uspořádaná množina (A, ) je zadána následujícím hasseovským diagramem: ¤ Nejmenším prvkem této uspořádané množiny je prvek a, největší prvek zde neexistuje. Uspořádané množiny ­ p.21/44 Příklady uspořádání - VIII Příklad U.8 Necht' uspořádaná množina (A, ) je zadána následujícím hasseovským diagramem: ¤ Minimálním prvkem je prvek a a maximálními prvky jsou prvky b, e . Uspořádané množiny ­ p.22/44 Příklady uspořádání - VIII Příklad U.8 Necht' uspořádaná množina (A, ) je zadána hasseovským diagramem: ¤ Nesrovnatelnými prvky jsou dvojice prvků b, c , resp. b, d , resp. b, e , resp. c, d . Všechny ostatní dvojice prvků jsou srovnatelné prvky. Uspořádané množiny ­ p.23/44 Příklady uspořádání - IX Příklad U.9 V uspořádané množině (, | ) je číslo 1 nejmenším prvkem a číslo 0 je největším prvkem. Uspořádané množiny ­ p.24/44 Příklady uspořádání - IX Příklad U.9 V uspořádané množině (, | ) je číslo 1 nejmenším prvkem a číslo 0 je největším prvkem. V uspořádané množině (N, | ), kde oproti předchozímu chybí číslo 0, je číslo 1 stále nejmenším prvkem, avšak není zde největší prvek a neexistují zde ani žádné maximální prvky. Uspořádané množiny ­ p.24/44 Příklady uspořádání - IX Příklad U.9 V uspořádané množině (, | ) je číslo 1 nejmenším prvkem a číslo 0 je největším prvkem. V uspořádané množině (N, | ), kde oproti předchozímu chybí číslo 0, je číslo 1 stále nejmenším prvkem, avšak není zde největší prvek a neexistují zde ani žádné maximální prvky. V uspořádané množině (N-{1}, | ) není nejmenší prvek a minimálními prvky jsou zde právě všechna prvočísla. Uspořádané množiny ­ p.24/44 Příklady uspořádání - X Příklad U.10 Je-li A neprázdná množina, pak v protiřetězci (A, A) jsou všechny prvky současně minimálními i maximálními prvky. Uspořádané množiny ­ p.25/44 Příklady uspořádání - X Příklad U.10 Je-li A neprázdná množina, pak v protiřetězci (A, A) jsou všechny prvky současně minimálními i maximálními prvky. Není-li přitom množina A jednoprvková, neexistují zde nejmenší ani největší prvek. Uspořádané množiny ­ p.25/44 Zobrazení zachovávající uspořádání Necht' (A, ) a (B, ) jsou dvě uspořádané množiny a necht' f : A B je zobrazení. Uspořádané množiny ­ p.26/44 Zobrazení zachovávající uspořádání Necht' (A, ) a (B, ) jsou dvě uspořádané množiny a necht' f : A B je zobrazení. Ř ekneme, že zobrazení f je izotonní, je-li splněna podmínka (x, y A)(x y = f(x) f(y)). Uspořádané množiny ­ p.26/44 Příklady izotonních zobrazení - I Příklad I.1 Identické zobrazení idN na množině N všech přirozených čísel je izotonním zobrazením uspořádané množiny (N, | ) s uspořádáním daným dělitelností čídel na uspořádanou množinu (N, ) s obvyklým uspořádáním čísel podle velikosti. Uspořádané množiny ­ p.27/44 Příklady izotonních zobrazení - I Příklad I.1 Identické zobrazení idN na množině N všech přirozených čísel je izotonním zobrazením uspořádané množiny (N, | ) s uspořádáním daným dělitelností čídel na uspořádanou množinu (N, ) s obvyklým uspořádáním čísel podle velikosti. Ale, idN : (N, ) (N, | ) není izotonním zobrazením. Uspořádané množiny ­ p.27/44 Příklady izotonních zobrazení - I Příklad I.1 Identické zobrazení idN na množině N všech přirozených čísel je izotonním zobrazením uspořádané množiny (N, | ) s uspořádáním daným dělitelností čídel na uspořádanou množinu (N, ) s obvyklým uspořádáním čísel podle velikosti. Ale, idN : (N, ) (N, | ) není izotonním zobrazením. Totiž, například 2 3, ale neplatí 2|3. Uspořádané množiny ­ p.27/44 Příklady izotonních zobrazení - II Příklad I.2 Pro libovolnou uspořádanou množinu (A, ) je identita idA na A izotonním zobrazením protiřetězce (A, A) na množinu (A, ). Uspořádané množiny ­ p.28/44 Příklady izotonních zobrazení - II Příklad I.2 Pro libovolnou uspořádanou množinu (A, ) je identita idA na A izotonním zobrazením protiřetězce (A, A) na množinu (A, ). Ale, idN : (N, ) (N, A ) není izotonním zobrazením. Uspořádané množiny ­ p.28/44 Příklady izotonních zobrazení - II Příklad I.2 Pro libovolnou uspořádanou množinu (A, ) je identita idA na A izotonním zobrazením protiřetězce (A, A) na množinu (A, ). Ale, idN : (N, ) (N, A ) není izotonním zobrazením. Totiž, například 2 3, ale neplatí 2 = 3. Uspořádané množiny ­ p.28/44 Izomorfismy Necht' (A, ) a (B, ) jsou uspořádané množiny a necht' f : A B je zobrazení. Uspořádané množiny ­ p.29/44 Izomorfismy Necht' (A, ) a (B, ) jsou uspořádané množiny a necht' f : A B je zobrazení. Ř ekneme, že zobrazení f je izomorfismus a uspořádané množiny (A, ) a (B, ) jsou izomorfní, jestliže f je bijekce a obě zobrazení f i f-1 jsou izotonní. Uspořádané množiny ­ p.29/44 Izomorfismy Necht' (A, ) a (B, ) jsou uspořádané množiny a necht' f : A B je zobrazení. Ř ekneme, že zobrazení f je izomorfismus a uspořádané množiny (A, ) a (B, ) jsou izomorfní, jestliže f je bijekce a obě zobrazení f i f-1 jsou izotonní. Je-li f je bijekce, je f izomorfismus právě tehdy,když (x, y A)(x y f(x) f(y)). Uspořádané množiny ­ p.29/44 Izomorfní množiny Uspořádané množiny ­ p.30/44 Konstrukce reálných čísel I Bud' (A, ) uspořádaná množina. Ř ekneme, že podmnožina B A je hustá v (A, ), jestliže pro každá x, y A splňující x < y existuje z B takové, že platí x < z < y. Uspořádané množiny ­ p.31/44 Konstrukce reálných čísel I Bud' (A, ) uspořádaná množina. Ř ekneme, že podmnožina B A je hustá v (A, ), jestliže pro každá x, y A splňující x < y existuje z B takové, že platí x < z < y. Při obvyklém uspořádání čísel podle velikosti není řetězec (Z, ) hustý, zatímco řetězec (Q, ) hustý je. Uspořádané množiny ­ p.31/44 Konstrukce reálných čísel I Bud' (A, ) uspořádaná množina. Ř ekneme, že podmnožina B A je hustá v (A, ), jestliže pro každá x, y A splňující x < y existuje z B takové, že platí x < z < y. Při obvyklém uspořádání čísel podle velikosti není řetězec (Z, ) hustý, zatímco řetězec (Q, ) hustý je. Zvolíme z = x+y 2 . Uspořádané množiny ­ p.31/44 Konstrukce reálných čísel II Necht' (A, ) je úplně uspořádaná množina, tedy řetězec, a necht' G, H A jsou neprázdné podmnožiny. Uspořádané množiny ­ p.32/44 Konstrukce reálných čísel II Necht' (A, ) je úplně uspořádaná množina, tedy řetězec, a necht' G, H A jsou neprázdné podmnožiny. Ř ekneme, že uspořádaná dvojice (G, H) je řez v množině (A, ), platí-li následující podmínky: Uspořádané množiny ­ p.32/44 Konstrukce reálných čísel II Necht' (A, ) je úplně uspořádaná množina, tedy řetězec, a necht' G, H A jsou neprázdné podmnožiny. Ř ekneme, že uspořádaná dvojice (G, H) je řez v množině (A, ), platí-li následující podmínky: G H = A, G H = , (x G)(y H)(x < y). Uspořádané množiny ­ p.32/44 Konstrukce reálných čísel III Je zřejmé, že pak platí také podmínky: Uspořádané množiny ­ p.33/44 Konstrukce reálných čísel III Je zřejmé, že pak platí také podmínky: (a A)(x G)(a < x = a G), Uspořádané množiny ­ p.33/44 Konstrukce reálných čísel III Je zřejmé, že pak platí také podmínky: (a A)(x G)(a < x = a G), (b A)(y H)(y < b = b H). Uspořádané množiny ­ p.33/44 Konstrukce reálných čísel IV Ř ez (G, H) v řetězci (A, ) se nazývá Uspořádané množiny ­ p.34/44 Konstrukce reálných čísel IV Ř ez (G, H) v řetězci (A, ) se nazývá skok, obsahuje-li G největší prvek a H nejmenší prvek, Uspořádané množiny ­ p.34/44 Konstrukce reálných čísel IV Ř ez (G, H) v řetězci (A, ) se nazývá skok, obsahuje-li G největší prvek a H nejmenší prvek, mezera, neobsahuje-li G největší prvek ani H nejmenší prvek, Uspořádané množiny ­ p.34/44 Konstrukce reálných čísel IV Ř ez (G, H) v řetězci (A, ) se nazývá skok, obsahuje-li G největší prvek a H nejmenší prvek, mezera, neobsahuje-li G největší prvek ani H nejmenší prvek, dedekindovský řez 1. druhu, obsahuje-li G největší prvek, avšak H neobsahuje nejmenší prvek, Uspořádané množiny ­ p.34/44 Konstrukce reálných čísel IV Ř ez (G, H) v řetězci (A, ) se nazývá skok, obsahuje-li G největší prvek a H nejmenší prvek, mezera, neobsahuje-li G největší prvek ani H nejmenší prvek, dedekindovský řez 1. druhu, obsahuje-li G největší prvek, avšak H neobsahuje nejmenší prvek, dedekindovský řez 2. druhu, neobsahuje-li G největší prvek, avšak H obsahuje nejmenší prvek. Uspořádané množiny ­ p.34/44 Konstrukce reálných čísel V Při obvyklém uspořádání čísel podle velikosti je v řetězci (Z, ) každý řez skokem, zatímco v řetězci (Q, ) žádný skok není. Uspořádané množiny ­ p.35/44 Konstrukce reálných čísel V Při obvyklém uspořádání čísel podle velikosti je v řetězci (Z, ) každý řez skokem, zatímco v řetězci (Q, ) žádný skok není. V řetězci (Q, ) pro každé q Q jsou { x Q | x q}, {y Q | q < y} , resp. { x Q | x < q}, {y Q | q y} d edekindovské řezy 1. druhu. , resp. 2. druhu. Uspořádané množiny ­ p.35/44 Konstrukce reálných čísel VI V řetězci (Q, ) pro každé q Q jsou { x Q | x q}, {y Q | q < y} , resp. { x Q | x < q}, {y Q | q y} d edekindovské řezy 1. druhu. , resp. 2. druhu. Uspořádané množiny ­ p.36/44 Konstrukce reálných čísel VI V řetězci (Q, ) pro každé q Q jsou { x Q | x q}, {y Q | q < y} , resp. { x Q | x < q}, {y Q | q y} d edekindovské řezy 1. druhu. , resp. 2. druhu. Pro každé r R - Q { x Q | x < r}, {y Q | r < y} j e mezera. Uspořádané množiny ­ p.36/44 Konstrukce reálných čísel VII Dedekindova konstrukce reálných čísel Uspořádané množiny ­ p.37/44 Konstrukce reálných čísel VII Dedekindova konstrukce reálných čísel S pomocí množiny Q všech racionálních čísel sestrojíme množinu R všech reálných čísel. Uspořádané množiny ­ p.37/44 Konstrukce reálných čísel VII Dedekindova konstrukce reálných čísel S pomocí množiny Q všech racionálních čísel sestrojíme množinu R všech reálných čísel. Označme R množinu všech dedekindovských řezů 1. druhu a všech mezer v řetězci (Q, ). Uspořádané množiny ­ p.37/44 Konstrukce reálných čísel VII Dedekindova konstrukce reálných čísel S pomocí množiny Q všech racionálních čísel sestrojíme množinu R všech reálných čísel. Označme R množinu všech dedekindovských řezů 1. druhu a všech mezer v řetězci (Q, ). Na množině R definujeme relaci následujícím předpisem. Pro libovolné dva řezy (G, H), (K, L) R klademe: (G, H) (K, L) G K L H. Uspořádané množiny ­ p.37/44 Konstrukce reálných čísel VIII (R, ) je řetězec. Uspořádané množiny ­ p.38/44 Konstrukce reálných čísel VIII (R, ) je řetězec. Zobrazení : R R dané pro každé r R předpisem (r) = { x Q | x r}, {y Q | r < y} j e izomorfismus řetězce (R, ) s obvyklým uspořádáním čísel na řetězec (R, ). Uspořádané množiny ­ p.38/44 Konstrukce reálných čísel IX V izomorfismu : R R racionálním číslům odpovídají dedekindovské řezy 1. druhu a iracionálním číslům odpovídají mezery. Uspořádané množiny ­ p.39/44 Konstrukce reálných čísel IX V izomorfismu : R R racionálním číslům odpovídají dedekindovské řezy 1. druhu a iracionálním číslům odpovídají mezery. Tvrzení. Množina Q je hustá v řetězci (R, ). Uspořádané množiny ­ p.39/44 Konstrukce reálných čísel IX V izomorfismu : R R racionálním číslům odpovídají dedekindovské řezy 1. druhu a iracionálním číslům odpovídají mezery. Tvrzení. Množina Q je hustá v řetězci (R, ). Uspořádané množiny ­ p.39/44