Mostowski collapse lemma

From Wikipedia, the free encyclopedia

In mathematical logic, the Mostowski collapse lemma states that for any binary relation R on a class X such that

  • R is well-founded: every nonempty subset of X contains an R-minimal element,
  • R is set-like: R−1[x] = {y : y R x} is a set for every x,
  • R is extensional: R−1[x] ≠ R−1[y] for every distinct elements x and y of X,

there exists a unique transitive class (possibly proper) whose structure under the membership relation is isomorphic to (X, R), and the isomorphism is unique, too. The isomorphism maps each element x of X to the set of images of elements y of X such that y R x.

It is named for Andrzej Mostowski.

 This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.
Languages