Toto je výtažek ze skript prof. Pultra, který jsem vytvořil při učení se na zkoušku. Jsou zde především definice a věty. Pro důkazy doporučuji oficiální zdroj.
Množiny, relace, zobrazení
Buď , . Výrazem
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: f\̲[̲A]
rozumíme obrazy prvků z A. VýrazemParseError: KaTeX parse error: Undefined control sequence: \[ at position 7: f^{-1}\̲[̲B]
rozumíme prvky z X, které se zobrazí do B (žádný inverz, ačkoli to tak vypadá).Částečná uspořádání
Předuspořádání (preorder) je relace reflexivní a tranzitivní. Předuspořádání je uspořádání (někdy také částečné uspořádání), pokud je navíc antisymetrické - . Uspořádání je lineární, pokud jsou navíc každé dva prvky porovnatelné - .
U uspořádání je dobré si představovat tzv. Hasseho diagram (bráno na Algebře I). Ten kreslíme s hranami orientovanými nahoru, z toho pochází názvy "horní" a "dolní". U lineárních uspořádání je tímto diagramem "řetízek" (lze dokázat).
Definujme , neboli prvky "menší rovné x" (v Hasseho diagramu "předchůdci x"), obdobně .
Zobrazení f mezi uspořádanými množinami nazveme isotonní (někdy také monotonní), pokud .
Suprema a infima
Prvek nazveme horní mez množiny , pokud , zkráceně . Obdobně dolní mez.
Nejmenší horní mez nazveme supremum M - . Tj. je to horní mez a je menšíRovna všem ostatním horním mezím. Nemusí vždy existovat. Obdobně infimum.
Věta: , pro konečný počet , pokud suprema existují. Obdobně pro infima.
Zornovo lemma
Mějme uspořádání . Nechť ke každé , která je uspořádána lineárně ("řetízky z X a jejich podmnožiny") existuje horní mez. Pak pro každé existuje maximální takové, že (tj. z x nelze "jet nahoru" do nekonečna).
Množinu C podmnožin X nazveme řetěz, pokud . Neboli C je inkluzí uspořádaná lineárně.
Princip maximality
Buď a pro každý řetěz existuje takové, že . Pak pro každou existuje největší Y z A obsahující X.
Princip maximality a Zornovo lemma jsou nezávislá tvrzení v teorii množin (nelze je dokázat ani vyvrátit). Jsou ekvivalentní axiomu výběru.
Svazy
Uspořádanou množinu nazveme dolní polosvaz, pokud pro každé dva prvky existuje infimum. To platí, právě když každá konečná neprázdná podmnožina má infimum (z věty výše). Obdobně definujme horní polosvaz.
Pokud je v dolním polosvazu největší prvek (označme ho 1, tedy ), nazveme ho dolní polosvaz s jednotkou. Zde má i prázdná množina infimum (a to 1), tedy každá konečná množina má infimum. Obdobně definujme horní polosvaz s nulou (má nejmenší prvek).
Svaz (anglicky Lattice) je dolní polosvaz, který je horní polosvaz (tj. každé dva prvky mají supremum i infimum). Analogicky definujme svaz s nulou a jednotkou (také omezený svaz) - svaz, kde existuje největší a nejmenší prvek.
Příklad svazu: přirozená čísla s relací dělitelnosti, supremum je nejmenší společný násobek, infimum je největší společný dělitel.
Úplný svaz je svaz, kde každá (i nekonečná) podmnožina má supremum a infimum. V Hasseho diagramu si představujme "zdroj" (nejnižší vrchol) a "stok" (nejvyšší vrchol) svazu.
Vidíme, že konečný svaz s 0 a 1 je úplný svaz (každá podmnožina je konečná). Nekonečný svaz s 0 a 1 nemusí být úplný - mohou chybět suprema či infima nekonečných množin.
Věta: Nechť v má každá podmnožina supremum. Pak je úplný svaz (nevyžadujeme infimum).
Podmnožinu D uspořádané množiny nazveme (nahoru) usměrněná, když každé dva prvky z D mají horní mez v D.
Adjunkce
Isotonní zobrazení nazveme navzájem (galoisovsky) adjugovaná, f nalevo, g napravo, pokud
.
Adjunkcí se myslí "uspořádaná dvojice" těchto zobrazení. Tedy když (f,g) jsou adjugovaná, nemusí (g,f) být adjugovaná. Pro f nalevo nemusí existovat pravý adjunkt.
Věta: Existuje-li pro f nalevo pravý adjunkt (resp. pro f napravo levý adjunkt), je určen jednoznačně. Důkaz snadný (nechť existují dva ... pak jsou si rovny).
Pro izomorfizmus je adjunktem , a to zprava i zleva.
Věta: Isotonní zobrazení jsou adjugovaná (f nalevo, g napravo), právě když a .
Věta: Jsou-li adjugovaná, pak a .
Věta: Levé Galoisovy adjunkty zachovávají suprema a pravé zachovávají infima.
Věta: Jsou-li X, Y úplné svazy, pak je levý adjunkt (tj. existuje k němu pravý adjunkt g), právě když f zachovává suprema.
Dvě věty o pevných bodech
Věta (Bourbakiho věta o pevném bodě): Nechť v je nejmenší prvek a nechť zde každý řetězec supremum. Nechť zachovává suprema těchto řetězců. Pak f má pevný bod y (tj. f(y)=y) a když má více pevných bodů, existuje mezi nimi nejmenší.
Věta (Tarského-Knasterová): Každé isotonní zobrazení úplného svazu do sebe sama má pevný bod.
Věta (Cantor-Bernsteinova): Nechť jsou prostá. Pak existuje izomorfismus . Existuje dokonce takový, že v každém bodě odpovídá f, nebo inverzi g.
Pro X,Y konečné je takovým h už přímo f nebo inverze g.
Relace "hluboko pod"
Řekneme, že x je hluboko pod y (značíme ) v uspořádané , když pro každou usměrněnou platí: .
Pozorování:
Když , pak .
Když , pak .
Svazy jako algebry
Lehké opakování Algebry I.
Definujme binární operaci (průsek) axiomy:
(asociativita)
(komutativita)
(idempotence)
Definujme binární operaci (spojení) axiomy:
(asociativita)
(komutativita)
(idempotence)
Navíc ať platí axiomy absorpce:
Věta: Nechť jsou na X binární operace , splňující axiomy výše. Pak na X existuje právě jedno uspořádání takové, že , a tedy tvoří svaz.
Mnohým pomůže, pokud se na průsek koukají jako na "minimum", spojení jako "maximum". Právě tak operace vypadají v lineárním uspořádání (LO) (btw. LO je svaz).
Vidíme, že daná algebra nám jednoznačně určuje svaz, svaz zase určuje algebru. Na svazy tedy lze nahlížet oběma způsoby, jako na algebry a jako na uspořádání.
Modularita, distributivita
Svaz nazveme modulární, pokud .
V řeči LO: . Pro b<=a máme a=a; pro a<=b<=c máme b=b; pro c<=b máme c=c; LO je modulární. Jak to poznat rychleji?
Věta: Svaz je modulární, právě když neobsahuje podsvaz izomorfní s (obrázek).
Svaz nazveme distributivní, pokud .
Věta: Svaz je distributivní, právě když .
Tj. distributivitu můžeme vyžadovat pro jednu operaci, ve svazu to implikuje distributivitu i druhé operace.
Pokud by v distributivním svazu platilo , pak by v něm z distributivity platilo i . Jelikož (infimum), pak by platilo i , což platí, tedy distributivní svaz je modulární.
Věta: Svaz je distributivní, právě když neobsahuje podsvaz izomorfní s a (obrázek).
Ideály a filtry v distributivních svazech
V distributivním svazu L s nulou a jednotkou nazveme podmnožinu ideál, pokud:
Příklady: L je ideál, je ideál. Ideál jsou to jakési "cesty od nuly nahoru", uzavřené na supremum dvou prvků.
V distributivním svazu L s nulou a jednotkou nazveme podmnožinu filtr, pokud:
Příklady: L je filtr, je filtr. Filtr jsou to jakési "cesty od jednotky dolů", uzavřené na infimum dvou prvků.
Filtr či ideál nazveme vlastní, pokud to není celý svaz L.
Vlastní ideál J nazveme prvoideál, pokud nebo .
Vlastní filtr F nazveme prvofiltr, pokud nebo .
Birkhoffova věta: Nechť ve svazu máme ideál J a filtr F disjunktní. Pak existují prvoideál a prvofiltr , které jsou také disjunktní.
Pseudokomplementy a komplementy
Mějme L svaz s nulou, . Pokud existuje největší prvek x takový, že , nazveme ho pseudokomplement prvku a, značíme .
Pseudokomplementární svaz je svaz s nulou, kde každý prvek má pseudokomplement.
Věty: v pseudokomplementárním svazu platí:
Prvek a nazveme komplement b, pokud . Relace "být komplement" je symetrická díky komutativitě spojení a průseku.
Heytingovy algebry
Binární operaci na svazu nazveme Heytingová, pokud .
Svaz s 0 a 1 a Heytingovou operací nazveme Heytingová algebra.
Heytingova algebra je vždy distributivní a pseudokomplementární svaz.
Booleovy algebry
Booleova algebra (BA) je distributivní svaz, kde každý prvek má komplement. Komplement značme .
Věta: Každá BA je Heytingova. Operaci definujme jako .
Věta: Buď F vlastní filtr v BA L (tj. F není celé L, v BA se jim někdy říká ultrafiltry). Pak jsou tato tvrzení ekvivalentní:
F je maximální filtr
F je prvofiltr
Pro každé : nebo
Pro Heytingovu algebru L definujme .
Věta: je Booleova algebra.
Základní pojmy univerzální algebry
Opakování základů, které se berou na VPL, Algebře I, TeMnu a dalších předmětech.
Algebra je množina opatřená systémem operací. Typem se myslí "sekvence arit" operací. Např. aritmetika (plus, krát, 0, 1) má typ (2,2,0,0). Typ nazveme konečný, když máme konečně mnoho operací konečné arity. Typ nazveme finitární, když máme operace konečné arity (může jich být i nekonečně).
Systém všech algeber typu a všech jejich homomorfismů se značí .
Zobrazení nazveme homomorfismem k funkcím a , když .
Pán Pultr to zapisuje trochu fikaně. n-tice prvků z X jsou vlastně zobrazení z do X (prvnímu prvku přiřadíme něco z X, druhému ... vyrobíme všechny n-tice). Množinu těchto zobrazení (n-tic) označme . Podmínkou homomorfismu je tedy (skládání funkcí různé arity podle mě není úplně průhledné). Tato druhá definice je kratší a nepředpokládá konečnost n.
Věta: Nechť jsou n-ární operace na , prosté, libovolné a takové, že . Pokud jsou f, g homomorfismy, pak i h je homomorfismus.
Věta: Nechť jsou n-ární operace na , na, libovolné a takové, že . Pokud jsou f, g homomorfismy, pak i h je homomorfismus.
Věta: Buďte algebry stejného typu.
Buď prostý a libovolný homomorfismus. Pak existuje homomorfismus takový, že , právě když
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: g\̲[̲Z] \subseteq f\…
.Buď homomorfismus "na" a libovolný hom. Pak existuje hom. takový, že , právě když .
Podalgebra je podmnožina algebry, uzavřená na všechny operace. Nové operace vzniknou "restrikcí". Je zde zobrazení vložení (podalgebry do algebry), které je homomorfismus.
Průnik podalgeber je podalgebra. Pro každou M podmnožinu algebry A existuje nejmenší B podalgebra A, obsahující M. Značíme .
Volné algebry
Třídu algeber nazveme triviální, když jsou všechny algebry nad jednoprvkovými množinami.
Buď A podtřída , M množina. Volná algebra nad M vzhledem k třídě A je spolu se zobrazením takovým, že pro každou a každé existuje právě jeden homomorfismus tak že .
Věta:
Je-li A netriviální třída algeber, je zobrazení vždy prosté.
Množina generuje algebru F(M).
Pokud volná algebra nad M existuje, je až na izomorfizmus jednoznačně určená.
Věta: Buď finitární typ a netriviální třída algeber uzavřená na součiny, podalgebry a izomorfismy. Pak pro každou M existuje volná algebra nad M vzhledem k A.
Třídy algeber uzavřené na základní operace. Variety
Třídami algeber zde budeme myslet třídy, uzavřené na izomorfismy. Je li v dané třídě A, jsou zde i B izomorfní s A.
Pro třídu algeber definujme:
Volně lze říci, že SA jsou podalgebry (Subalgebra), PA jsou produkty (Product) a HA jsou faktorové algebry (Homomorphic). Všechny jsou nadmnožiny A.
Tvrzení: je nejmenší třída algeber obsahující A uzavřená na podalgebry, produkty a faktorové algebry.
Topologie
Metrické prostory již známe z Analýzy, stejně tak i spojitost. Množina M je okolí bodu x, pokud obsahuje "kružnici" se středem v x a poloměrem > 0. Samotné {x} tedy není svým okolím.
Spojitost lze ekvivalentně definovat tak, že pro všechna x: ke každému V okolí f(x) existuje U okolí x takové, že obraz U se vejde do V. "Nepřítel" nám dává co nejmenší okolí f(x).
Základní pojmy
Řekneme, že na X je dána topologie pomocí okolí, když pro každé je dána neprázdná (to by měla být okolí x), kde platí:
(okolí bodu obsahuje ten bod)
(průnik okolí je okolí)
(nadmnožina okolí je okolí)
pro každou existuje , takové, že (pro U okolí x existuje W menší podokolí x takové, že U je okolí všech bodů z W )
Řekneme, že na X je topologie (pomoci otevřených množin), když:
(konečné průniky)
(libovolná sjednocení)
Pro topologii pomocí okolí definujme předpisem: . Věta: je topologie.
Pro topologii definujme předpisem: . Věta: je topologie pomocí okolí.
Vidíme, že obě definice se snaží popsat stejnou věc. Budeme používat spíše druhou definici, je jednodušší. Prvkům se také říká otevřené množiny.
Mějme topologii na X. Množinu nazveme uzavřená, když .
Vidíme, že jsou uzavřené. Sjednocení dvou uzavřených je uzavřená a průnik libovolného počtu uzavřených je uzavřená. Mohli jsme tedy začít s "opačnou definicí" topologie (pomocí uzavřených množin) a pak dodefinovat otevřené. Zkrátka díváme se na jednu topologii, ať už ji dostaneme jako otevřené či uzavřené množiny, "opačnou reprezentaci" si vždy dokážeme vyrobit (pomocí doplňků).
Pro každou definujme uzávěr M: .
Příklady
Příklady topologií nad X: (diskrétní prostor, největší topologie), (indiskrétní prostor, nejmenší topologie).
Řekneme, že je báze topologie , když (podmínka, že A je podmnožina U, je asi zbytečná).
Vidíme, že když k bázi přidáme libovolný další prvek z , zůstane bází. Jsou to jakési menší dílky, sjednocováním kterých postavíme libovolný prvek topologie.
Řekneme, že je subbáze topologie , když množina všech konečných průniků prvků z S je bází .
Domněnka: Sjednocení všech prvků subbáze musí dát celé X, abychom z ní uměli vyrobit X (což je prvek každé topologie). Vysvětlení: nemusí. Konečnými průniky pán Pultr mysli i prázdný průnik, který nám vrátí X.
Věta: každá je subbází nějaké topologie nad X. Říkáme, že A generuje danou topologii. Většinou nás zajímá nejmenší topologie, generovaná A.
Spojitá zobrazení
Zobrazení nazveme spojité v topologiích , když pro každé V okolí f(x) existuje U okolí x, které se zobrazí do V. Tj.
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 66: …tau, x \in U) f\̲[̲U] \subseteq V
.Složení spojitých zobrazení je spojité zobrazení (z tranzitivity inkluze). Pokud je nalevo diskrétní topologie, nebo napravo indiskrétní, každé zobrazení je spojité.
Spojitost zobrazení f lze vyjádřit více způsoby. Tvrzení níže jsou ekvivalentní:
f je spojité
pro každou U otevřenou v Y je
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 7: f^{-1}\̲[̲U]
otevřená v Xpro každou U uzavřenou v Y je
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 7: f^{-1}\̲[̲U]
uzavřená v Xpro každou je
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: f\̲[̲\overline{M}] \…
pro každou je
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 17: …overline{f^{-1}\̲[̲M]} \subseteq f…
Základní konstrukce
Mějme topologický prostor . Vezměme a (všechny otevřené množiny "ořežme" podle Y). Pak také tvoří topologický prostor, říkáme mu podprostor indukovaný na podmnožině Y.
Speciální požadavky
Definujme si pro topologické prostory nějaké další požadavky.
: pro každé existuje tak, že nebo .
Věta: Prostor splňuje , právě když .
: pro každé existuje tak, že .
Věta: Prostor splňuje , právě když všechny konečné množiny jsou uzavřené.
(Hausdorffův prostor): pro každé existují tak, že a U,V jsou disjunktní.
(regulární prostor): pro každé x a uzavřenou A, , existují tak, že a U,V jsou disjunktní.
(úplně regulární prostor): pro každé x a uzavřenou A, existují tak, že
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 18: …hi (x)=0, \phi \̲[̲A] \subseteq \{…
( s topologií "klasických" otevřených množin).(normální prostor): pro každé disjunktní uzavřené existují disjunktní otevřené tak, že .
Kompaktnost
Množinu nazveme pokrytí , když . Pokud je také pokrytí, nazveme ho podpokrytí vybrané z U.
Prostor nazveme kompaktní, když z každého pokrytí lze vybrat konečné podpokrytí. nazveme kompaktní, když je kompaktní.
Věta:
Každá uzavřená podmnožina kompaktního prostoru je kompaktní.
Při spojitém zobrazení, obraz kompaktní podmnožiny je kompaktní podmnožina.
Věta (Alexanderovo lemma): Nechť pro nějakou subbází prostoru platí, že z každého pokrytí X lze vybrat konečné podpokrytí. Pak je X kompaktní.
Prostor nazveme Lindelöfův, když z každého pokrytí lze vybrat spočetné podpokrytí.
Věta: V Hausdorffově prostoru X je každá kompaktní podmnožina uzavřená.
Věta: Každý Hausdorffův kompaktní prostor je normální.
Souvislost
Podmnožinu nazveme obojetná, je-li zároveň otevřená i uzavřená. Triviální obojetné jsou v každém prostoru.
Neprázdný prostor je souvislý, pokud jeho jediné obojetné množiny jsou . Podmnožina je souvislá, je-li prostor souvislý.
Lze to říci i jinak: prostor je nesouvislý, když v něm jsou neprázdné disjunktní otevřené A, B, (pak jsou obě netriviální obojetné, X nemůže být souvislý). Stejně to funguje s uzavřenými A, B.
Věta: Interval je souvislý.
Věta: Spojitý obraz souvislé množiny je souvislá množina.
Věta: Uzávěr souvislé množiny je souvislá množina.
Cestou (nebo křivkou) mezi nazveme spojité zobrazení , kde .
Prostor nazveme křivkově souvislý, když mezi každými dvěma body existuje křivka.
Věta: křivkově souvislý prostor je souvislý (obráceně to neplatí).