Degrees of logics with Henkin quantifiers in poor vocabularies

Archive for Mathematical Logic 43 (5):691-702 (2004)

Authors
Marcin Mostowski
Jagiellonian University
Abstract
We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L*∅ is of degree 0’. We show that the same holds also for some weaker logics like L ∅(Hω) and L ∅(Eω). We show that each logic of the form L ∅ (k)(Q), with the number of variables restricted to k, is decidable. Nevertheless – following the argument of M. Mostowski from [Mos89] – for each reasonable set theory no concrete algorithm can provably decide L (k) (Q), for some (Q). We improve also some results related to undecidability and expressibility for logics L(H4) and L(F2) of Krynicki and M. Mostowski from [KM92]
Keywords Henkin quantifiers  Degrees of unsolvability
Categories (categorize this paper)
DOI 10.1007/s00153-004-0220-8
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 47,149
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Finite Partially-Ordered Quantification.Wilbur John Walkoe Jr - 1970 - Journal of Symbolic Logic 35 (4):535-555.
Finite Partially‐Ordered Quantifiers.Herbert B. Enderton - 1970 - Mathematical Logic Quarterly 16 (8):393-397.
On the Semantics of the Henkin Quantifier.Michał Krynicki & Alistair H. Lachlan - 1979 - Journal of Symbolic Logic 44 (2):184-200.
Pure Logic with Branched Quantifiers.Marcin Mostowski - 1989 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (1):45-48.
Pure Logic with Branched Quantifiers.Marcin Mostowski - 1989 - Mathematical Logic Quarterly 35 (1):45-48.

View all 6 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Spectra of Formulae with Henkin Quantifiers.Joanna Golinska-Pilarek & Konrad Zdanowski - 2003 - In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers.
Henkin Quantifiers.M. Krynicki & M. Mostowski - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers. pp. 193--263.
Henkin Quantifiers,[W:] Krynicki M., Mostowski M., Szczerba LW (Red.).M. Krynicki - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers.
Henkin Quantifiers and the Definability of Truth.Tapani Hyttinen & Gabriel Sandu - 2000 - Journal of Philosophical Logic 29 (5):507-527.
Decidability Problems in Languages with Henkin Quantifiers.Michał Krynicki & Marcin Mostowski - 1992 - Annals of Pure and Applied Logic 58 (2):149-172.
Quantifiers, Some Problems and Ideas.M. Krynicki & M. Mostowski - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers. pp. 1--21.
Ways of Branching Quantifers.Gila Sher - 1990 - Linguistics and Philosophy 13 (4):393 - 422.
Henkin Quantifiers and Complete Problems.Andreas Blass & Yuri Gurevich - 1986 - Annals of Pure and Applied Logic 32 (1):1--16.
Quantifiers Definable by Second Order Means.M. Mostowski - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers. pp. 181--214.
A Remark on Henkin Sentences and Their Contraries.John P. Burgess - 2003 - Notre Dame Journal of Formal Logic 44 (3):185-188.
Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non--Classical Logics 8 (1-2):107--121.
Spectra of Formulae with Henkin Quantifiers.Joanna Golińska & Konrad Zdanowski - 2003 - In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers. pp. 29--45.

Analytics

Added to PP index
2013-11-23

Total views
24 ( #394,172 of 2,289,429 )

Recent downloads (6 months)
2 ( #587,611 of 2,289,429 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature