Lemma del collasso di Mostowski

Nella logica matematica, il lemma del collasso di Mostowski, noto anche come collasso di Shepherdson-Mostowski, è un teorema della teoria degli insiemi introdotto da Andrzej Mostowski nel 1949 e da John Shepherdson nel 1953.

Enunciato

Si supponga che R sia una relazione binaria su una classe X tale che:

R è set-like, ovvero il segmento iniziale R⁻¹[x] = {y: y R x} è un insieme per ogni x;
R è ben fondata, ovvero ogni sottoinsieme S non vuoto di X contiene un elemento minimale rispetto a R;
R è estensionale, ovvero R⁻¹[x] ≠ R⁻¹[y] per ogni coppia di elementi distinti (x, y) di X.

Il lemma di collasso di Mostowski afferma che per ogni R esiste un'unica classe transitiva (possibilmente una classe propria^[1]) la cui struttura sotto la relazione di appartenenza è isomorfa a (X, R), e tale isomorfismo esiste unico. L’isomorfismo mappa ogni elemento x di X sull'insieme delle immagini degli elementi y di X tali che y R x (Jech 2003:69).

Generalizzazioni

Ogni relazione set-like ben fondata può essere incorporata in una relazione estensionale, set-like e ben fondata. Ciò implica la seguente variante del lemma del collasso di Mostowski: ogni relazione set-like ben fondata è isomorfa alla relazione di appartenenza su una classe (non unica e non necessariamente transitiva).

Una mappa F tale che F(x) = {F(y): y R x} per ogni x in X può essere definita per qualsiasi relazione ben fondata di tipo set-like R su X mediante ricorsione ben fondata. Ciò fornisce un omomorfismo di R su una classe transitiva (non unica, in generale). L'omomorfismo F è un isomorfismo se e solo se R è estensionale.

L'ipotesi di relazione ben fondata del lemma di Mostowski può essere alleggerita o del tutto rimossa al’interno di teorie degli insiemi non ben fondate. Nella teoria degli insiemi di Boffa, ogni relazione estensiva e set-like è isomorfa all'appartenenza a un insieme definito su una classe transitiva (non unica). Nella teoria degli insiemi con l'assioma di anti-fondazione di Aczel, ogni relazione simile a un insieme è bisimilare all'appartenenza definita su una classe transitiva unica, quindi ogni relazione set-like bisimilare-minimale è isomorfa a una classe transitiva unica.

Applicazioni

Ogni modello insiemistico di Zermelo-Frenkel è set-like ed è estensionale. Se il modello è ben fondato, allora per il lemma del collasso di Mostowski è isomorfo a un modello transitivo di ZF e tale modello transitivo è unico.

Affermare che la relazione di appartenenza di qualche modello di ZF è ben fondata è più forte che asserire che l'assioma di regolarità è vero nel modello. Infatti, esiste un modello M (assumendo la consistenza di ZF) il cui dominio ha un sottoinsieme A senza alcun elemento minimale rispetto a R, ma questo insieme A non è un "insieme all'interno del modello" (A non appartiene al dominio del modello, sebbene tutti i suoi membri ci appartengano). Più precisamente, per nessun insieme A siffatto esiste x in M tale che A = R⁻¹[x]. Quindi, il modello M soddisfa l'assioma di regolarità (è “internamente” ben fondato), ma ad esso non è applicabile il lemma del collasso.

Note

^ Una classe che non è un insieme

Bibliografia

Thomas Jech, Set Theory, Springer Monographs in Mathematics, 3, millennium, Berlino, New York, Springer-Verlag, 2003, ISBN 978-3-540-44085-7.
Andrzej Mostowski, An undecidable arithmetical statement (PDF), in Fundamenta Mathematicae, vol. 36, n. 1, Institute of Mathematics Polish Academy of Sciences, 1949, pp. 143–164, DOI:10.4064/fm-36-1-143-164.
John Shepherdson, Inner models for set theory, Part III, in Journal of Symbolic Logic, vol. 18, Association for Symbolic Logic, 1953, pp. 145–167, DOI:10.2307/2268947.