Mostowski collapse lemma


In mathematical logic, the Mostowski collapse lemma, also known as the Shepherdson-Mostowski collapse, is a theorem of set theory introduced by and.

Statement

Suppose that R is a binary relation on a class X such that
The Mostowski collapse lemma states that for any such R there exists a unique transitive class whose structure under the membership relation is isomorphic to, 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.

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 class.
A mapping F such that F = for all x in X can be defined for any well-founded set-like relation R on X by well-founded recursion. It provides a homomorphism of R onto a 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 theories. In Boffa's set theory, every set-like extensional relation is isomorphic to set-membership on a transitive class. In set theory with Aczel's anti-foundation axiom, every set-like relation is 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 of 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 whose domain has a subset A with no R-minimal element, but this set A is not a "set in the model". More precisely, for no such set A there exists x in M such that A = R−1. So M satisfies the axiom of regularity but it is not well-founded and the collapse lemma does not apply to it.