Mostowski kollaps lemma

Inom matematisk logik är Mostowskis kollapslemma , även känt som Shepherdson–Mostowski-kollapsen , en sats om mängdlära som introducerades av Andrzej Mostowski ( 1949 , sats 3) och John Shepherdson ( 1953 ).

Påstående

Antag att R är en binär relation på en klass X så att

• R är mängdliknande : R ⁻¹ [ x ] = { y : y R x } är en mängd för varje x ,
• R är välgrundad : varje icke-tom delmängd S av X innehåller ett R -minimalelement (dvs ett element x ∈ S så att R ⁻¹ [ x ] ∩ S är tomt),
• R är förlängning : R ⁻¹ [ x ] ≠ R ⁻¹ [ y ] för alla distinkta element x och y i X

Mostowskis kollapslemma säger att för varje sådan R finns det en unik transitiv klass (möjligen riktig ) vars struktur under medlemskapsrelationen är isomorf till ( X , R ), och isomorfismen är unik. Isomorfismen mappar varje element x i X till uppsättningen bilder av element y av X så att y R x (Jech 2003:69).

Generaliseringar

Varje välgrundad mängdliknande relation kan bäddas in i en välgrundad mängdliknande extensionsrelation. Detta innebär följande variant av Mostowskis kollapslemma: varje välgrundad uppsättningsliknande relation är isomorf till uppsättningsmedlemskap på en (icke-unik, och inte nödvändigtvis transitiv) klass.

En mappning F så att F ( x ) = { F ( y ): yRx } för alla x i X kan definieras för vilken välgrundad mängdliknande relation R på X som helst genom välgrundad rekursion . Det ger en homomorfism av R till en (icke-unik, i allmänhet) transitiv klass. Homomorfismen F är en isomorfism om och endast om R är extensional.

Mostowski-lemmats välgrundade antagande kan lindras eller släppas i icke välgrundade mängdteorier . I Boffas mängdteori är varje mängdliknande extensionsrelation isomorf till mängdmedlemskap på en (icke-unik) transitiv klass. I mängdteorin med Aczels anti-fundamentaxiom , är varje mängd-liknande relation bisimilar till mängd-medlemskap på en unik transitiv klass, därför är varje bisimulering-minimal mängd-liknande relation isomorf till en unik transitiv klass.

Ansökan

Varje uppsättningsmodell av ZF är setliknande och förlängningsbar. Om modellen är välgrundad är den enligt Mostowskis kollapslemma isomorf till en transitiv modell av ZF och en sådan transitiv modell är unik.

Att säga att medlemskapsrelationen för någon modell av ZF är välgrundad är starkare än att säga att axiomet regelbundenhet är sant i modellen. Det finns en modell M (förutsatt att ZF är konsistens) vars domän har en delmängd A utan något R -minimalelement, men denna uppsättning A är inte en "mängd i modellen" ( A är inte i modellens domän, även även om alla dess medlemmar är det). Mer exakt, för ingen sådan mängd A finns det x i M så att A = R ⁻¹ [ x ]. Så M uppfyller axiomet regelbundenhet (det är "internt" välgrundat) men det är inte välgrundat och kollapslemmat gäller inte för det.

•   Jech, Thomas (2003), Set Theory , Springer Monographs in Mathematics (tredje årtusendets upplaga), Berlin, New York: Springer-Verlag , ISBN 978-3-540-44085-7
• Mostowski, Andrzej (1949), "An undecidable aritmetical statement" (PDF) , Fundamenta Mathematicae , Institute of Mathematics Polish Academy of Sciences, 36 (1): 143–164, doi : 10.4064/fm-36-1-443-16
• Shepherdson, John (1953), "Inner modeller för mängdteori, del III", Journal of Symbolic Logic , Association for Symbolic Logic, 18 : 145–167, doi : 10.2307/2268947