FOM: Re: completeness theorem for stratification?
Thomas Forster
T.Forster at dpmms.cam.ac.uk
Thu Apr 13 06:37:28 EDT 2000
A formula of set theory is typed if one can assign integers to all
its vbls (all occurrences of the same vbl get the same integer) in
such a way that if x \in y is a subformula then the integer assigned
to x is one lower than the integer assigned to y.
Rieger-Bernays permutation models (not to be confused with FM permutation)
models are the following device. Let V, \in be a model of some sort of
set theory, and \pi a permutation of V. In the new model we believe
that x is a member of y if the old model thinks that x \in \pi(y). This
construction preserves stratified formulae. In fact a formula is
(equivlent to a) stratified formula iff the class of its models is closed
under this construction. A bit of good old-fashioned model theory! There
is a similar concept of stratification in lambda-calculus and a similar
completeness theorem. See ZML 1990 pp 385-388 (for set theory) and
Theoretical Computer science 1993 pp 405-418. I have a pile of offprints
of these two that i would be only too happy to send to interested parties.
(we are about to move to new, smaller premisses!)
Thomas Forster
More information about the FOM
mailing list