Nakopírovat to, za co mně ogg pochválil.
Dopsat do článku Fundované jádro o mohutnosti definované pomocí ranku.
Jazyk (matematická logika)
Důkaz (výroková a predikátová logika)

Forsing

Ultrafiltr verze 2

Ultrafiltr je matematický pojem z teorie množin. Je-li $P$ množina vybavená částečným uspořádáním $\leq _{P}$ , pak ultrafiltrem $F$ je každý netriviální filtr na $P$ , který není vlastní podmnožinou jiného netriviálního filtru na $P$ . Netriviálním filtrem na $P$ je každá neprázdná dolů usměrněná horní vlastní podmnožina $P$ .

Nejčastějším případem jsou ultrafiltry na potenční algebře, kdy $P=\mathbb {P} (X)$ pro nějakou množinu $X$ (která sama nemusí mít žádnou strukturu neboli dodatečnou informaci) a $a\leq _{P}b$ znamená, že $a\subseteq b$ (tj. $a$ je podmnožinou $b$ ). V takovém případě výše uvedená definice znamená, že množina $F\subseteq \mathbb {P}$ je (netriviálním) filtrem, právě když splňuje následující axiomy:

Netriviálnost: $\emptyset \subsetneq F\subsetneq \mathbb {P} (X)$ , kde $\subsetneq$ značí „je vlastní podmnožina“. $F$ tedy musí obsahovat některé podmnožiny $X$ , ale ne všechny. Vzhledem k druhému axiomu je toto ekvivalentní s tvrzením, že $F$ obsahuje $X$ , ale nikoli prázdnou množinu.
Horní množina: S každou množinou $A\in F$ obsahuje $F$ i všechny její nadmnožiny $A\subseteq B\subseteq X$ .
Usměrněnost dolů: S každými dvěma množinami obsahuje $F$ i nějakou jejich společnou podmnožinu. Vzhledem k axiomu 2 je to ekvivalentní požadavku, aby pro každé $a,b\in F$ platilo $a\cap b\in F$ .

Nap59kl

Ultrafiltr je pak netriviální filtr, jehož žádná vlastní nadmnožina není netriviálním filtrem na $\mathbb {P} (X)$ .

každá podmnožina $P$ splňující tyto čtyři axiomy:

$\emptyset \subsetneq F\subsetneq P$ , tj. $F$ není prázdná, ale neobsahuje všechny prvky $P$ . (Znak $\subsetneq$ znamená „je vlastní podmnožinou“).
S každým svým prvkem obsahuje i všechny větší, tj. pro každé $x,y\in P$ , je-li $x\leq _{P}y$ a $x\in F$ , pak $y\in F$ .
Pro každé $x,y\in U$ existuje $z\in U$ takové, že $z\leq x$ a $z\leq y$ . Sice pro dvojici prvků $x,y\in P$ nemusí v obecné částečně uspořádané množině $P$ (na rozdíl např. od polosvazu) vůbec existovat dolní závora, tj. $z\in P,z\leq _{P}x,z\leq _{P}y$ (protipříkladem je množina $\{2,3\}$ částečně uspořádaná delitelností). Ovšem tento axiom tvrdí, že pokud toto $x$ i $y$ leží v $F$ pak nejméně jedno takové $z$ nejen existuje, ale také leží v $F$ .
Pokud $U_{2}$ splňuje podmínky 1 až 3 (čili jde o filtr) a $U\subseteq U_{2}$ , pak $U=U_{2}$ . Tj. $U$ nemá vlastní nadmnožinu, která by též byla filtrem.

Příklad: Je-li $P=\{1,2,3,4\}$ a $\leq _{P}$ relace „je dělitelem“ (takže např. platí $2\leq _{P}4$ , ale ne $2\leq _{P}3$ ), pak

Prázdná množina ani množina $\{1,2,3,4\}$ není filtrem (a tedy ani ultrafiltrem): nesplňuje první axiom.
Množina $\{3\}$ není filtrem vzhledem k druhému axiomu: neobsahuje číslo 4.
$\{2,3\}$ není filtrem podle axiomu tři.
$\{4\}$ je filtr, ale ne ultrafiltr, protože jej lze rozšířit do filtru $\{2,4\}$ .

Příklad

Terminologie =

Někdy se množiny patřící do (ultra)filtru označují jako „velké“; pak filtrem na $\mathbb {P} (X)$ je každé rozdělení množin na malé a velké, v němž

X je velká, ale prázdná množina nikoli.
Každá nadmnožina velké množiny je velká.
Průnik dvou velkých množin je velký.

Ultrafiltr je pak filtr, v němž pro každou $A\subseteq X$ je velká buď $A$ nebo její doplněk $X-A$ .

Užívá se též formulace, že ultrafiltry jsou právě „maximální filtry“; toto úsporné názvosloví vyjadřuje, že

Množina všech filtrů na $\mathbb {P} (X)$ je podmnožina $\mathbb {P} (\mathbb {P} (X))$ a tedy na ní relace $\subseteq$ tvoří částečné uspořádání.
Ultrafiltry jsou právě ty její prvky, které jsou maximálními prvky vzhledem k $\subseteq$ .

Na obecné uspořádané množině

Filtr na potenční algebře s relací $\subseteq$ (což je množina podmnožin $X$ neboli množina prvků $P=\mathbb {P} (X)$ ) je pouze speciálním případem obecnější definice filtru na částečně uspořádané množině $(P,\leq _{P})$ , což je množina prvků $P$ .

Konvence není jednotná v tom, zda pojem „filtr“ zahrnuje i triviální filtry $F=\emptyset$ a $F=P$ . Netriviálním filtrem je každá podmnožina $P$ , která je

horní podmnožinou $P$ , tj. s každým prvkem obsahuje i všechny větší prvky: pokud $x\in F,y\in P,x\leq _{P}y$ pak $y\in F$ .
Dolů usměrněnou množinou: s každou dvojicí svých prvků musí $F$ obsahovat i nějakou její dolní závoru, tj. pro každé $x,y\in F$ existuje $z\in F$ takové, že $z\leq _{P}x,z\leq _{P}y$ . Bez dodatečných předpokladů (např. $P$ je dolní polosvaz) nemusí takové $z$ existovat ani v $P$ (například když $P$ je $\{2,3\}$ s relací dělitelnosti). Tento axiom však vyžaduje, aby alespoň jedna dolní závora existovala v $P$ a navíc byla prvkem $F$ .

Netriviálním filtrem na $P$ je každá neprázdná dolů usměrněná horní vlastní podmnožina $P$ .

dd ...

Ultrafiltr verze 1

Ultrafiltr je matematický pojem z teorie množin. Je-li $P$ množina vybavená částečným uspořádáním $\leq _{P}$ , pak ultrafiltrem $F$ je každá podmnožina $P$ splňující tyto čtyři axiomy:

$\emptyset \subsetneq F\subsetneq P$ , tj. $F$ není prázdná, ale neobsahuje všechny prvky $P$ . (Znak $\subsetneq$ znamená „je vlastní podmnožinou“).
S každým svým prvkem obsahuje i všechny větší, tj. pro každé $x,y\in P$ , je-li $x\leq _{P}y$ a $x\in F$ , pak $y\in F$ .
Pro každé $x,y\in U$ existuje $z\in U$ takové, že $z\leq x$ a $z\leq y$ . Sice pro dvojici prvků $x,y\in P$ nemusí v obecné částečně uspořádané množině $P$ (na rozdíl např. od polosvazu) vůbec existovat dolní závora, tj. $z\in P,z\leq _{P}x,z\leq _{P}y$ (protipříkladem je množina $\{2,3\}$ částečně uspořádaná delitelností). Ovšem tento axiom tvrdí, že pokud toto $x$ i $y$ leží v $F$ pak nejméně jedno takové $z$ nejen existuje, ale také leží v $F$ .
Pokud $U_{2}$ splňuje podmínky 1 až 3 (čili jde o filtr) a $U\subseteq U_{2}$ , pak $U=U_{2}$ . Tj. $U$ nemá vlastní nadmnožinu, která by též byla filtrem.

Příklad: Je-li $P=\{1,2,3,4\}$ a $\leq _{P}$ relace „je dělitelem“ (takže např. platí $2\leq _{P}4$ , ale ne $2\leq _{P}3$ ), pak

Prázdná množina ani množina $\{1,2,3,4\}$ není filtrem (a tedy ani ultrafiltrem): nesplňuje první axiom.
Množina $\{3\}$ není filtrem vzhledem k druhému axiomu: neobsahuje číslo 4.
$\{2,3\}$ není filtrem podle axiomu tři.
$\{4\}$ je filtr, ale ne ultrafiltr, protože jej lze rozšířit do filtru $\{2,4\}$ .

$\{2,4\}$ je již ultrafiltr, protože jediný větší filtr je celé $\{1,2,3,4\}$ : díky druhému axiomu nelze přidat jen číslo 1 a díky třetímu nelze přidat jen číslo 3.

Ultrafiltry na potenčních algebrách

Nejběžnější filtry a ultrafiltry se definují na potenčních algebrách, tj. potenčních množině nějaké množiny $X$ (která sama nemusí mít žádnou strukturu). Pak $P=\mathbb {P} (X)$ je množina všech podmnožin $X$ a pro podmnožiny $a,b\in X$ platí $a\leq _{P}b$ právě když $a\subseteq b$ (tj. $a$ je podmnožinou $b$ a může jí být i rovno).

V takovém případě je filtrem každá množina podmnožin $X$ , tj. $F\subseteq \mathbb {P} (X)$ , která

Není prázdnou množinou $\emptyset \subseteq \mathbb {P} (X)$ ani množinou $\mathbb {P} (X)\subseteq \mathbb {P} (X)$ . Díky axiomu 2 je tato podmínka ekvivalentní s tvrzením, že $F$ obsahuje prázdnou množinu $\emptyset \in \mathbb {P} (X)$ , ale nikoli samotnou $X$ . (Některé zdroje ovšem v definici filtru připouštějí, aby $F=P$ , a vyžadují tedy jen jeho neprázdnost).
S každým svým prvkem $A\in X$ obsahuje i všechny jeho nadmnožiny $B,A\subseteq B\subseteq \mathbb {P} (X)$ .
S každými dvěma prvky obsahuje i jejich průnik.

Ultrafiltr je pak filtr, který již nelze rozšířit do filtru, který byl jeho vlastní nadmnožinou.

Užívá se též formulace, že ultrafiltry jsou právě „maximální filtry“; toto úsporné názvosloví vyjadřuje, že

Množina všech filtrů na $\mathbb {P} (X)$ je podmnožina $\mathbb {P} (\mathbb {P} (X))$ a tedy na ní relace $\subseteq$ tvoří částečné uspořádání.
Ultrafiltry jsou právě ty její prvky, které jsou maximálními prvky vzhledem k $\subseteq$ .

Někdy se množiny patřící do (ultra)filtru označují jako „velké“; pak filtrem na $\mathbb {P} (X)$ je každé rozdělení množin na malé a velké, v němž

X je velká, ale prázdná množina nikoli.
Každá nadmnožina velké množiny je velká.
Průnik dvou velkých množin je velký.

Ultrafiltr je pak filtr, v němž pro každou $A\subseteq X$ je velká buď $A$ nebo její doplněk $X-A$ .

Příklad

Buď $X=\mathbb {Z}$ množina všech celých čísel. Pak $P=\mathbb {P} (\mathbb {Z} )$ je množina všech podmnožin $\mathbb {Z}$ a

Množina všech $A\subseteq X$ , které neobsahují nulu, není filtrem, protože porušuje první podmínku (neobsahuje prázdnou množinu). Podobně

Množina všech nekonečných množin nesplňuje druhou podmínku, protože průnik

Predikátová logika prvního řádu

Predikátová logika prvního řádu (často jen predikátová logika, nehrozí-li nedorozumění). je obor matematické logiky, který exaktně formalizuje pojem "dokazatelnost formule" podobně jako výroková logika, ale pro mnohem širší okruh přípustných formulí, neboť povoluje i značky (tzv. kvantifikátory) znamenající "pro každé" a "existuje". Povoluje je jen pro objekty, zatímco logika vyššího řádu i pro množiny objektů či množiny množin objektů atd. Přesto tyto prostředky stačí na vyjádření tak širokého množství matematických tvrzení, že je predikátová logika prvního řádu zdaleka nejšířeji používaným systémem, jak formalizovat pojem důkaz tak, aby odpovídal jeho m

Základními pojmy jsou jazyk, formule, teorie (tj. predikátová teorie prvního řádku) a důkaz. Toto vše jsou pojmy syntaktické, tj. pouhé symboly a pravidla, jak s nimi manipulovat. Zároveň predikátová

Kam. V logice prvního řádu tedy není možné formulovat v Peanově aritmetice matematickou indukci jako jediný výrok „Pro každou množinu x platí “

Relativizace formule

Relativizace formule a absolutnost vlastnosti je pojem z matematické logiky, který se uplatňuje při studiu axiomatických teorií množin jako je ZFC. Vlastnost $\phi$ je absolutní v modelu $\mathbb {M}$ , pokud v rámci modelu (tj. relativizovaně) platí právě tehdy, platí-li absolutně (tj. „objektivně“).

Buď například $\mathbb {M} =\langle M,R\rangle$ model Zermelovy–Fraenkelovy teorie množin (ZF), což znamená, že

$M$ je množina (většina úvah ovšem platí, když $M$ je třída),
$R$ je binární relace na $M$ ,
A jsou splněny Zermelovy–Fraenkelovy axiomy.

ZF je teorie (konkrétně predikátová teorie prvního řádu) se symbolem „náležení“. Model $\mathbb {M} =(M,R)$ tento symbol realizuje relací $R$ na nosné množině $M$ ; ta může být naprosto odlišná od absolutního náležení.

Relativizace

Pojmy „relativizace“ a „absolutnosti“ by neměly smysl pro většinu teorií, například

pro aritmetiku – s výjimkou modelů, jejich nosná množina obsahuje jen přirozená čísla, nebo alespoň objekty, na nichž je v „absolutním“ světě zaveden nějaký druh sčítání.
Euklidovskou geometrii – s výjimkou modelů, na jejichž nosné množině (která reprezentuje body a přímky) je absolutně zavedena nějaká obdoba pojmů rovnoběžnost a bod leží na úsečce.
Obecně: neexistuje-li odpovídající absolutní pojem, nemají tyto pojmy smysl, protože relativní pojem v modelu není s čím srovnávat.

Axiomatická teorie množin má však výsadní postavení, neboť se hodí k popisu „matematické pravdy“ a reprezentuje každý objekt jako množinu (například dvojku jako $\{\emptyset ,\{\emptyset \}\}$ ). Je tedy možné srovnávat relaci $R$ s absolutním náležením. Tato relace může být zcela odlišná od absolutního náležení, ale je-li totožná, říkáme, že model má absolutní náležení.

Dále lze zkoumat absolutnost pojmů, které jsou definovány pomocí náležení. Například $c=\{a,b\}$ (čteno „ $a$ je (neuspořádaná) dvojice prvků $a$ a $b$ “) je zkratkou pro: Pro každé $d$ platí, že $d\in c$ , právě když $d$ je rovno $a$ nebo $b$ .

Relativizace této formule do $M$ je vytvořena

a) Nahrazením každého absolutního náležení

p\in q

relativním náležením

(p,q)\in R

; aby vynikla podobnost (

R

i absolutní náležení jsou binární relace), píše se místo

(p,q)\in R

někdy

pRq\in

.

b)Úpravou každého kvantifikátoru „existuje

p

takové, že“ formulací „existuje

p\in M

takové, že“.

c) Úpravou každého výrazu „Pro každé

p

platí“ formulací „Pro každé

p

, které náleží do

M

, platí“.

Poznámka: Predikátová logika přesně vymezuje, co je to „formule“ (nikoli věta přirozeného jazyka, ale posloupnost symbolů), ovšem zde použití slovního popisu nepředstavuje újmu na přesnosti.

Relativizace formule $c=\{a,b\}$ do modelu $\mathbb {M} =(M,R)$ tedy zní: Pro každé $d\in M$ platí, že $dRc$ , právě když $d$ je rovno $a$ nebo $b$ a označuje se $c=\{a,b\}^{M}$ . Tato formule tedy vyžadovala po jedné úpravě typu a) a typu c). Úprava typu b) nebyla zapotřebí, protože existenční kvantifikátor se ve formuli nevyskytoval.

Absolutnost

Formule $c=\{a,b\}$ se nazývá absolutní v modelu $\mathbb {M}$ , pokud pro každé $a,b,c\in M$ platí $c=\{a,b\}$ právě když $c=\{a,b\}^{M}$ .

Ani v modelu s absolutním náležením nemusí pojem neuspořádané dvojice (tj. $c=\{a,b\}$ ) být absolutní. Pro libovolné, navzájem různé matematické objekty $u,v,w$ takové, že do $M$ náleží $u,v$ a rovněž $\{u,v\}$ , ovšem nikoli $w$ , je formule Nelze pochopit (neznámá funkce „\b“): {\displaystyle c=\{a,\b}} při přiřazení $a\rightarrow u,b\rightarrow v,c\rightarrow \{u,v,w\}$ splněna relativně v $\mathbb {M}$ , ovšem samozřejmě ne absolutně. Platí Nelze pochopit (syntaktická chyba): {\displaystyle \{u, v\}^M = \{u, v, w\} \not = {u, v\}} .

Tranzitivní model

Ani v teorii s absolutním náležením nemusí tedy být absolutní mnohé elementární pojmy; dokonce ani natolik zásadní, jako $c=\{a,b\}$ . To je však absolutní v tranzitivních modelech, tj. v modelech s absolutním náležením, v němž $M$ je tranzitivní množina (případně třída).

Tranzitivní modely jsou intenzívně studovány pro svoji přehlednost, protože v nich je mnoho pojmů absolutních. Příkladem takového modelu je třída všech Goedelových konstruovatelných množin, pomocí nichž se dokazuje, (relativní) bezespornost AC a GCH.

Skolemův paradox

Skolemův paradox je zdánlivý rozpor pramenící z následujících faktů:

Je-li ZFC bezesporná (jak všichni věří), dle Gödelovy věty o úplnosti má nějaký model.
Dle

Mostowského kolaps

Model $\mathbb {M} =(M,R)$ teorie ZF splňuje předpoklady Mostowského věty o kolapsu, právě když je na něm relace $R$ (realizující náležení) fundovaná. To je silnější předpoklad, než že model splňuje axiom fundovanosti, který je v podstatě relativizací formule „ $R$ je fundovaná“ do modelu $\mathbb {M}$ .

xx