Decision procedures for elementary sublanguages of set theory. II. Formulas involving restricted quantifiers, together with ordinal, integer, map, and domain notions
✍ Scribed by M. Breban; A. Ferro; E. G. Omodeo; J. T. Schwartz
- Publisher
- John Wiley and Sons
- Year
- 1981
- Tongue
- English
- Weight
- 801 KB
- Volume
- 34
- Category
- Article
- ISSN
- 0010-3640
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we describe a simple semi-decision algorithm applicable to a wide class of quantified formulas. The formulas we consider are built using the propositional connectives from prenex formulas in a language for which a decision algorithm for the corresponding quantifier-free theory T is available. In general the algorithm to be presented is not complete, but for certain formulas whose matrix belongs to one of several special sublanguages of set theory the algorithm is complete. Proper choice of the quantifier-free theory one starts from will allow many significant set theoretic constructs to be expressed by a quantified formula of the class for which our algorithm is complete. In particular, we shall show that various elementary but useful statements concerning simple set theoretic operations and relations, ordinals, and maps can be verified automatically by the technique to be described.