Löwenheimova–Skolemova věta

Löwenheimova-Skolemova věta je matematické tvrzení z oblasti teorie modelů tvrdící, že teorie, která má nekonečný model, má také model libovolné jiné (tj. větší či menší) nekonečné velikosti neboli kardinality (pokud není menší, než počet funkčních a predikátových symbolů dané teorie, ovšem těch mají běžné teorie jen konečně mnoho) a že existuje elementární vnoření menšího z těchto dvou modelů do většího.

Název nese podle německého logika a matematika Leopolda Löwenheima a norského matematika Thoralfa Skolema.

Znění

Kardinalitou jazyka L se ve znění Löwenheimovy-Skolemovy věty myslí vždy kardinální číslo $\|L\|=\aleph _{0} |L|$ (viz funkce alef). Díky této definici lze Löwenheimovu-Skolemovu větu vyslovit jako dvě samostatná tvrzení nazývané Löwenheimova-Skolemova věta nahoru resp. dolů takto:

Nechť A je model (nějaké teorie) v jazyce L:

Löwenheimova-Skolemova věta nahoru: Pro libovolný kardinál $\kappa \geq \|L\| |A|$ existuje elementární rozšíření B modelu A mohutnosti právě $\kappa$ .
Löwenheimova-Skolemova věta dolů: Pro libovolný kardinál $\|L\|\leq \kappa \leq |A|$ existuje elementární podmodel B modelu A mohutnosti právě $\kappa$ .

Za cenu mírného oslabení (vynechání tvrzení o elementárním vnoření/rozšíření) lze obě odrážky sloučit:

Má-li teorie $T$ nekonečný model, má model každé nekonečné mohutnosti, která není menší, než počet (funkčních a predikátových) symbolů jazyka teorie $T$ .

To, že předpoklad o počtu symbolů nelze vynechat, je patrné například na tom, že pro každou (konečnou či nekonečnou) mohutnost $\kappa$ lze uvažovat teorii, která má $\kappa$ konstant a pro každé dvě různé z nich obsahuje axiom, že si nejsou rovny. Obsahuje tedy axiomy $c_{0}\not =c_{1},c_{1}\not =c_{2},c_{0}\not =c_{2}$ atd. Každý její model má mohutnost alespoň $\kappa$ , pro nespočetné $\kappa$ tedy neplatí, že teorie má model každé nekonečné mohutnosti. (To je také princip důkazu Löwenheimovy-Skolemovy věty nahoru.)

Skolemův paradox

Skolemův paradox je tvrzení, které je přímým důsledkem Löwenheimovy-Skolemovy věty dolů. Spočívá v následující úvaze.

Princip paradoxu

Jazyk teorie množin je pouze jednoprvkový, tedy (viz definice před zněním Löwenheimovy-Skolemovy věty) má spočetnou kardinalitu. Je-li teorie množin (například v Zermelově-Fraenkelově axiomatizaci) bezesporná, má nějaký model, a tedy dle Löwenheimovy-Skolemovy věty dolů má i spočetný model S. Protože však v teorii množin je dokazatelná existence nespočetné množiny, musí být nějaká nespočetná množina, a tedy i všechny její prvky, v modelu S. Tedy model S obsahuje nespočetně mnoho prvků, což je (zdánlivě) spor.

Řešení

Řešení Skolemova paradoxu je velmi jednoduché, neboť spočívá pouze v ukázání chybnosti úvahy vedoucí zdánlivě ke sporu. Chybnost této úvahy spočívá v tom, že množina, která je „ve smyslu modelu S“ nespočetná (tj. v S o ní platí, že je nespočetná), nemusí (a Skolemův paradox říká, že ani nemůže) být nespočetná „absolutně“. Nespočetnost takové množiny „ve smyslu S“ znamená pouze to, že v S neexistuje bijekce mezi touto množinou a množinou přirozených čísel v S (ta jsou stejná jako „absolutní přirozená čísla“). Taková bijekce však může existovat (a Skolemův paradox říká, že existuje) mimo S, tedy „absolutně“ může (musí) být tato množina spočetná. Tedy i množina, která je „ve smyslu S“ nespočetná, může být podmnožinou („absolutně“) spočetné množiny S.

Související články