Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T10:02:34.599Z Has data issue: false hasContentIssue false

Coinductive formulas and a many-sorted interpolation theorem

Published online by Cambridge University Press:  12 March 2014

Ursula Gropp*
Affiliation:
Mathematisches Institut, Universität Bonn, Bonn, West Germany
*
Equipe de Logique Mathématique, Université Paris-vii, 75251 Paris, France

Abstract

We use connections between conjunctive game formulas and the theory of inductive definitions to define the notions of a coinductive formula and its approximations. Corresponding to the theory of conjunctive game formulas we develop a theory of coinductive formulas, including a covering theorem and a normal form theorem for many sorted languages. Applying both theorems and the results on “model interpolation” obtained in this paper, we prove a many-sorted interpolation theorem for ω1ω-logic, which considers interpolation with respect to the language symbols, the quantifiers, the identity, and countably infinite conjunction and disjunction.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[B]J. Barwise, , Admissible sets and structures, Springer-Verlag, Berlin, 1975.CrossRefGoogle Scholar
[F]Feferman, S., Lectures on proof theory, Proceedings of the summer school in logic (Leeds, 1967), Lecture Notes in Mathematics, vol. 70, Springer-Verlag, Berlin, 1968, pp. 1107.CrossRefGoogle Scholar
[G]Gropp, U., Coinduktive Formeln, Diplomarbeit, Universität Bonn, Bonn, 1983.Google Scholar
[H]Harnik, V., Refinements of Vaught's normal form theorem, this Journal, vol. 44 (1979), pp. 289306.Google Scholar
[H/M]Harnik, V. and Makkai, M., Applications of Vaught sentences and the covering theorem, this Journal, vol. 41 (1976), pp. 171187.Google Scholar
[K]Keisler, H. J., Model theory for infinitary logic, North-Holland, Amsterdam, 1971.Google Scholar
[Ma 1]Makkai, M., Vaught sentences and Lindström's regular relations, Cambridge summer school in mathematical logic (1971), Lecture Notes in Mathematics, vol. 337, Springer-Verlag, Berlin, 1973, pp. 622660.CrossRefGoogle Scholar
[Ma2]Makkai, M., Admissible sets and infinitary logic, Handbook of mathematical logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, pp. 233282.CrossRefGoogle Scholar
[Mal]Malitz, J., Universal classes in infinitary languages, Duke Mathematical Journal, vol. 36 (1969), pp. 621630.CrossRefGoogle Scholar
[Mo]Moschovakis, Y. N., Elementary induction on abstract structures, North-Holland, Amsterdam, 1974.Google Scholar
[O]Oberschelp, A., On the Craig-Lyndon interpolation theorem, this Journal, vol. 33 (1968), pp. 271274.Google Scholar
[R]Ressayre, J. P., Boolean models and infinitary first order languages, Annals of Mathematical Logic, vol. 6 (1973), pp. 4192.CrossRefGoogle Scholar
[S]Stern, J., A new look at the interpolation problem, this Journal, vol. 40 (1975), pp. 113.Google Scholar
[V]Vaught, R., Descriptive set theory in Lω1ω, Cambridge summer school in mathematical logic (1971), Lecture Notes in Mathematics, vol. 337, Springer-Verlag, Berlin, 1973, pp. 574598.CrossRefGoogle Scholar