Mostowski collapse lemma

Mostowski collapse lemma

In mathematical logic, the Mostowski collapse lemma is a statement in set theory named for Andrzej Mostowski.

Contents

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 xS 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 any 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.

Note that the saying 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−1[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

  • Jech, Thomas (2003), Set Theory, Springer Monographs in Mathematics (third millennium ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-44085-7 

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Mostowski — Mostowski, Mostowska is surname of: Mostowski Palace (Polish: Pałac Mostowskich), an 18th century palace in Warsaw Andrzej Mostowski (1913 1975), a Polish mathematician Mostowski collapse lemma, in mathematical logic Ehrenfeucht–Mostowski theorem …   Wikipedia

  • Andrzej Mostowski — (1 November 1913 – 22 August 1975) was a Polish mathematician. He is perhaps best remembered for the Mostowski collapse lemma.Born in Lwów, Austria Hungary, Mostowski entered University of Warsaw in 1931. He was influenced by Kuratowski,… …   Wikipedia

  • List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia

  • Forcing — En mathématiques, et plus précisément en logique mathématique, le forcing est une technique inventée par Paul Cohen pour prouver des résultats de cohérence et d indépendance en théorie des ensembles. Elle a été utilisée pour la première fois en… …   Wikipédia en Français

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Well-founded relation — In mathematics, a binary relation, R, is well founded (or wellfounded) on a class X if and only if every non empty subset of X has a minimal element with respect to R; that is, for every non empty subset S of X, there is an element m of S such… …   Wikipedia

  • Forcing (mathematics) — For the use of forcing in recursion theory, see Forcing (recursion theory). In the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1963,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”