Mostowski collapse lemma

---

title: "Mostowski collapse lemma" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["lemmas", "lemmas-in-set-theory", "wellfoundedness"] description: "Result in mathematics and set theory" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Mostowski_collapse_lemma" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Result in mathematics and set theory ::

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

• R is set-like: R−1[x] = {y : y R x} is a set for every x,
• R is well-founded: every nonempty subset S of X contains an R-minimal element (i.e. an element x ∈ S such that R−1[x] ∩ S is empty),
• R is extensional: R−1[x] ≠ R−1[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 class (possibly 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 recursion. It provides a 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 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 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 = (X, R) (assuming the consistency of ZF) whose domain X has a subset A with no R-minimal element, but this set A is not a "set in the model". More precisely, there is no x in X such that A = R−1[x]. So M satisfies the axiom of regularity (it is "internally" well-founded), but M is not well-founded and the Mostowski collapse lemma does not apply to it.

References

• {{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 }}

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::