## Abstract We show that a coherent theory of partially ordered connectives can be developed along the same line as partially ordered quantification. We estimate the expressive power of various partially ordered connectives and use methods like Ehrenfeucht games and infinitary logic to get various
Hierarchies of Partially Ordered Connectives and Quantifiers
✍ Scribed by Michał Krynicki
- Publisher
- John Wiley and Sons
- Year
- 1993
- Tongue
- English
- Weight
- 381 KB
- Volume
- 39
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
Connections between partially ordered connectives and Henkin quantifiers are considered. It is proved that the logic with all partially ordered connectives and the logic with all Henkin quantifiers coincide. This implies that the hierarchy of partially ordered connectives is strongly hierarchical and gives several nondefinability results between some of them. It is also deduced that each Henkin quantifier can be defined by a quantifier of the form
what is a strengthening of the Walkoe result. MSC: 03C80.
📜 SIMILAR VOLUMES
This is to be read "For every x there is a y and for every u there is a v (depending only on u) such that y ( x , y, u , w) ." The precise meaning of this can be given in terms of SKOLEM functions; the above formula is semantically equivalent to the second-order formula Such partially-ordered quant
ON THE CONCEPT OF FORMALIZATION AND PARTIALLY ORDERED QUANTIFIERS.\* \* I would like to thank an anonymous referee for very useful comments on an earlier version of this paper and Krister Segerberg, Erik Stenius and in particular Risto Hilpinen and Patrick Sibelius for discussing the topic of this p
Nondeterministic exponential time complexity bounds are established for recognizing true propositional formulas with partially ordered quantiÿers on propositional variables.