Col·lapse de Mostowski

En lògica matemàtica, el lema del col·lapse de Mostowski, també conegut com el col·lapse de Shepherdson–Mostowski, és un teorema en teoria de conjunts introduït per Andrzej Mostowski (1949, theorem 3) i John Shepherdson (1953).

Suposem que ${\displaystyle R}$ és una relació binària en una classe ${\displaystyle X}$ tal que

• ${\displaystyle R}$ és local: ${\displaystyle R^{-1}[x]=\{y:yRx\}}$ és un conjunt per a cada ${\displaystyle x\in X}$,
• ${\displaystyle R}$ està ben fonamentada: cada subconjunt no buit ${\displaystyle S}$ de ${\displaystyle X}$ conté un element ${\displaystyle R}$-mínim (és a dir, hi ha un element ${\displaystyle x\in S}$ tal que ${\displaystyle R^{-1}[x]\cap S}$ és buit),
• ${\displaystyle R}$ és extensional: ${\displaystyle R^{-1}[x]\neq R^{-1}[y]}$ per a qualsevol parell d'elements diferents ${\displaystyle x}$ i ${\displaystyle y}$ de ${\displaystyle X}$.

El lema del col·lapse de Mostowski afirma que per a tota relació binària ${\displaystyle R}$ d'aquest tipus existeix una única classe transitiva (possiblement pròpia) l'estructura de la qual sota la relació de pertinença és isomòrfica a ${\displaystyle (X,R)}$, i l'isomorfisme és únic. L'isomorfisme envia cada element ${\displaystyle x}$ de ${\displaystyle X}$ al conjunt d'imatges dels elements ${\displaystyle y}$ de ${\displaystyle X}$ tals que ${\displaystyle yRx}$ (Jech 2003:69).

Per a tota relació local ben fonamentada existeix una immersió en una relació extensional local ben fonamentada. Això implica la següent variant del lema de col·lapse de Mostowski: tota relació local ben fonamentada és isomòrfica a la relació de pertinença entre conjunts d'una classe (no única i no necessàriament transitiva).

Per a tota relació binària ${\displaystyle R}$ local i ben fonamentada en ${\displaystyle X}$ es pot definir, per recursivitat ben fonamentada, una aplicació ${\displaystyle F}$ tal que ${\displaystyle F(x)=\{F(y):yRx\}}$ per a tota ${\displaystyle x}$ en ${\displaystyle X}$. Aquesta aplicació ${\displaystyle F}$ és un homomorfisme exhaustiu de ${\displaystyle R}$ a una classe transitiva (no única, en general). L'homomorfisme ${\displaystyle F}$ és un isomorfisme si i només si ${\displaystyle R}$ és extensional.

L'assumpció de bona fonamentació del lema de Mostowski es pot alleujar o eliminar en teories de conjunts no ben fonamentades. En la teoria de conjunts de Boffa, tota relació extensional local és isomòrfica a la relació de pertinença entre conjunts d'una classe transitiva (no única). En la teoria de conjunts amb l'axioma anti-fundament d'Aczel, cada relació local és bisimilar a la relació de pertinença entre conjunts d'una classe transitiva única, per tant, cada relació local mínima respecte la bisimulació és isomòrfica a una classe transitiva única.

Tots els models de ZF que són conjunts, són locals i extensionals. Si el model està ben fonamentat, pel lema del col·lapse de Mostowski, llavors és isomorf a un model transitiu de ZF i aquest model transitiu és únic.

Dir que la relació de pertinença d'algun model de ZF està ben fonamentada és més fort que dir que l'axioma de regularitat és cert en el model. Existeix un model ${\displaystyle (M,R)}$ de ZF (suposant la consistència de ZF) tal que hi ha un subconjunt ${\displaystyle A}$ de ${\displaystyle M}$ sense element ${\displaystyle R}$-mínim, però tal que ${\displaystyle A\notin M}$. Més precisament, no existeix cap ${\displaystyle {\ce {x}}}$ en ${\displaystyle M}$ tal que ${\displaystyle A=R^{-1}[x]}$. Per tant, ${\displaystyle M}$ compleix l'axioma de regularitat (està "interiorment" ben fonamentat), però no està ben fonamentat i, per tant, el lema del col·lapse de Mostowski no s'hi aplica.

• Jech, Thomas (2003), Set Theory (third millennium ed.), Springer Monographs in Mathematics, Berlin (Nova York): Springer-Verlag, ISBN 978-3-540-44085-7
• Mostowski, Andrzej (1949), "An undecidable arithmetical statement", Fundamenta Mathematicae (Institute of Mathematics Polish Academy of Sciences), doi:10.4064/fm-36-1-143-164, <http://matwbn.icm.edu.pl/ksiazki/fm/fm36/fm36120.pdf>
• Shepherdson, John (1953), "Inner models for set theory, Part III", Journal of Symbolic Logic (Association for Symbolic Logic), DOI 10.2307/2268947