Editing Mostowski collapse lemma

{{Short description|Result in mathematics and set theory}}

In [[mathematical logic]], the '''Mostowski collapse lemma''', also known as the '''Shepherdson&ndash;Mostowski collapse''', is a theorem of [[set theory]] introduced by {{harvs|txt|authorlink=Andrzej Mostowski|first=Andrzej|last= Mostowski|year=1949|loc=theorem 3}} and {{harvs|txt|authorlink=John C. Shepherdson|first=John|last= Shepherdson|year=1953}}.

==Statement==
Suppose that ''R'' is a binary relation on a class ''X'' such that
*''R'' is [[binary relation#Relations over a set|set-like]]: ''R''<sup>−1</sup>[''x''] = {''y'' : ''y'' ''R'' ''x''} is a set for every ''x'',
*''R'' is [[well-founded relation|well-founded]]: every nonempty subset ''S'' of ''X'' contains an ''R''-minimal element (i.e. an element ''x'' ∈ ''S'' such that ''R''<sup>−1</sup>[''x''] ∩ ''S'' is empty),
*''R'' is [[axiom of extensionality|extensional]]: ''R''<sup>−1</sup>[''x''] ≠ ''R''<sup>−1</sup>[''y''] for every distinct elements ''x'' and ''y'' of ''X''
The Mostowski collapse lemma states that for every such ''R'' there exists a unique [[transitive set|transitive]] class (possibly [[proper class|proper]]) whose structure under the membership relation is isomorphic to (''X'', ''R''), and the isomorphism is unique. The isomorphism maps each element ''x'' of ''X'' to the set of images of elements ''y'' of ''X'' such that ''y R x'' (Jech 2003:69).

==Generalizations==
Every well-founded set-like relation can be embedded into a well-founded set-like extensional relation. This implies the following variant of the Mostowski collapse lemma: every well-founded set-like relation is isomorphic to set-membership on a (non-unique, and not necessarily transitive) class.

A mapping ''F'' such that ''F''(''x'') = {''F''(''y'') : ''y R x''} for all ''x'' in ''X'' can be defined for any well-founded set-like relation ''R'' on ''X'' by [[well-founded relation|well-founded recursion]]. It provides a [[homomorphism#Relational structures|homomorphism]] of ''R'' onto a (non-unique, in general) transitive class. The homomorphism ''F'' is an isomorphism if and only if ''R'' is extensional.

The well-foundedness assumption of the Mostowski lemma can be alleviated or dropped in [[non-well-founded set theory|non-well-founded set theories]]. In Boffa's set theory, every set-like extensional relation is isomorphic to set-membership on a (non-unique) transitive class. In set theory with [[Aczel's anti-foundation axiom]], every set-like relation is [[bisimulation|bisimilar]] to set-membership on a unique transitive class, hence every bisimulation-minimal set-like relation is isomorphic to a unique transitive class.

==Application==
Every set [[model theory|model]] of [[Zermelo–Fraenkel set theory|ZF]] is set-like and extensional. If the model is well-founded, then by the Mostowski collapse lemma it is isomorphic to a [[transitive model]] of ZF and such a transitive model is unique.

Saying that the membership relation of some model of ZF is well-founded is stronger than saying that the [[axiom of regularity]] is true in the model. There exists a model ''M'' (assuming the consistency of ZF) whose domain has a subset ''A'' with no ''R''-minimal element, but this set ''A'' is not a "set in the model" (''A'' is not in the domain of the model, even though all of its members are). More precisely, for no such set ''A'' there exists ''x'' in ''M'' such that ''A'' = ''R''<sup>−1</sup>[''x'']. So ''M'' satisfies the axiom of regularity (it is "internally" well-founded) but it is not well-founded and the collapse lemma does not apply to it.

==References==

* {{Citation | last1=Jech | first1=Thomas | author1-link=Thomas Jech | title=Set Theory | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=third millennium | series=Springer Monographs in Mathematics | isbn=978-3-540-44085-7 | year=2003}}
*{{citation|title=An undecidable arithmetical statement
|first=Andrzej|last= Mostowski | authorlink = Andrzej Mostowski
|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm36/fm36120.pdf 
|publisher= Institute of Mathematics Polish Academy of Sciences
|journal= [[Fundamenta Mathematicae]]
|year= 1949
|volume =36
|issue =1
|pages= 143–164
 |doi=10.4064/fm-36-1-143-164
|doi-access=free
}}
*{{citation|title=Inner models for set theory, Part III
|first=John|last= Shepherdson | authorlink = John C. Shepherdson 
|publisher= Association for Symbolic Logic
|journal= [[Journal of Symbolic Logic]]
|year= 1953
|volume =18
|issue=2 |pages= 145–167
 |doi=10.2307/2268947
|jstor=2268947 |s2cid=35526998 }}

{{Mathematical logic}}
{{Set theory}}

[[Category:Lemmas]]
[[Category:Lemmas in set theory]]
[[Category:Wellfoundedness]]