mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

, the Mostowski collapse lemma, also known as the Shepherdson–Mostowski collapse, is a theorem of

set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...

introduced by and .

Statement

Suppose that ''R'' is a binary relation on a class ''X'' such that *''R'' is set-like: ''R''⁻¹ 'x''= is a set for every ''x'', *''R'' is

well-founded In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s ...

: every nonempty subset ''S'' of ''X'' contains an ''R''-minimal element (i.e. an element ''x'' ∈ ''S'' such that ''R''⁻¹ 'x''∩ ''S'' is empty), *''R'' is

extensional In any of several fields of study that treat the use of signs — for example, in linguistics, logic, mathematics, semantics, semiotics, and philosophy of language — an extensional context (or transparent context) is a syntactic environment in w ...

: ''R''⁻¹ 'x''≠ ''R''⁻¹ '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 Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map for ...

) 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'') = 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 In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "sa ...

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 In the foundations of mathematics, Aczel's anti-foundation axiom is an axiom set forth by , as an alternative to the axiom of foundation in Zermelo–Fraenkel set theory. It states that every accessible pointed directed graph corresponds to exac ...

, 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 A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...

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 In mathematical set theory, a transitive model is a model of set theory that is standard and transitive. Standard means that the membership relation is the usual one, and transitive means that the model is a transitive set or class. Examples *An i ...

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 In mathematics, the axiom of regularity (also known as the axiom of foundation) is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set ''A'' contains an element that is disjoint from ''A''. In first-order logic, the ...

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''⁻¹ '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

* * * {{Set theory Lemmas Lemmas in set theory Wellfoundedness