Mostowského kolapsové lemma - Mostowski collapse lemma

v matematická logika, Mostowského kolapsové lemma, také známý jako Shepherdson – Mostowski se zhroutil, je věta o teorie množin představil Andrzej Mostowski  (1949, věta 3) a John Shepherdson  (1953 ).

Prohlášení

Předpokládejme to R je binární relace ve třídě X takhle

  • R je set-like: R−1[X] = {y : y R X} je sada pro každého X,
  • R je opodstatněný: každá neprázdná podmnožina S z X obsahuje R-minimální prvek (tj. prvek X ∈ S takhle R−1[X] ∩ S je prázdný),
  • R je extenzní: R−1[X] ≠ R−1[y] pro všechny odlišné prvky X a y z X

Lemma Mostowského kolapsu uvádí, že pro každý takový R existuje jedinečný tranzitivní třída (možná správně ) jehož struktura v rámci členského vztahu je izomorfní s (X, R) a izomorfismus je jedinečný. Izomorfismus mapuje každý prvek X z X na sadu obrazů prvků y z X takhle y R x (Jech 2003: 69).

Zobecnění

Každý opodstatněný set-like vztah může být vložen do fundované set-like extenzní relace. Z toho vyplývá následující varianta lumatu Mostowského kolapsu: každý dobře podložený vztah typu set je izomorfní s množinou členství ve třídě (nejedinečné a ne nutně tranzitivní).

Mapování F takhle F(X) = {F(y) : y R x} pro všechny X v X lze definovat pro jakýkoli opodstatněný relační vztah R na X podle fundovaná rekurze. Poskytuje homomorfismus z R do (nejjedinečné, obecně) tranzitivní třídy. Homomorfismus F je izomorfismus právě tehdy R je rozšiřující.

Předpoklad opodstatněnosti mostowského lemmatu lze zmírnit nebo upustit nepodložené teorie množin. V Boffově teorii množin je každý setový extenzní vztah izomorfní s set-členstvím v (ne-jedinečné) tranzitivní třídě. V teorii množin s Aczelův anti-nadační axiom, každý set-like vztah je bisimilar k set-membership na jedinečné tranzitivní třídě, proto je každá relace typu bisimulation-minimum set-like isomorphic to a unique transitive class.

aplikace

Každá sada Modelka z ZF je set-like a Extensional. Pokud je model opodstatněný, je podle lumatu Mostowského kolapsu izomorfní s a tranzitivní model ZF a takový tranzitivní model je jedinečný.

Říkat, že členský vztah nějakého modelu ZF je opodstatněný, je silnější než říkat, že axiom pravidelnosti platí v modelu. Existuje model M (za předpokladu konzistence ZF), jehož doména má podmnožinu A bez č R-minimální prvek, ale tato sada A není „sada v modelu“ (A není v doméně modelu, i když všichni jeho členové jsou). Přesněji řečeno, pro žádnou takovou sadu A tady existuje X v M takhle A = R−1[X]. Tak M splňuje axiom pravidelnosti (je „interně“ opodstatněný), ale není opodstatněný a kolapsové lemma se na něj nevztahuje.

Reference

  • Jech, Thomas (2003), Teorie množin, Springer Monografie z matematiky (ed. Třetího tisíciletí), Berlín, New York: Springer-Verlag, ISBN  978-3-540-44085-7
  • Mostowski, Andrzej (1949), „Nerozhodnutelný aritmetický výrok“ (PDF), Fundamenta Mathematicae, Matematický ústav Polské akademie věd, 36 (1): 143–164, doi:10,4064 / fm-36-1-143-164
  • Shepherdson, Johne (1953), „Vnitřní modely pro teorii množin, část III“, Journal of Symbolic Logic, Sdružení pro symbolickou logiku, 18: 145–167, doi:10.2307/2268947