Independence-friendly logic without Henkin quantification

Archive for Mathematical Logic 60 (5):547-597 (2021)
  Copy   BIBTEX


We analyze the expressive resources of \ logic that do not stem from Henkin quantification. When one restricts attention to regular \ sentences, this amounts to the study of the fragment of \ logic which is individuated by the game-theoretical property of action recall. We prove that the fragment of prenex AR sentences can express all existential second-order properties. We then show that the same can be achieved in the non-prenex fragment of AR, by using “signalling by disjunction” instead of Henkin or signalling patterns. We also study irregular IF logic and analyze its correspondence to regular IF logic. By using new methods, we prove that the game-theoretical property of knowledge memory is a first-order syntactical constraint also for irregular sentences, and we identify another new first-order fragment. Finally we discover that irregular prefixes behave quite differently in finite and infinite models. In particular, we show that, over infinite structures, every irregular prefix is equivalent to a regular one; and we present an irregular prefix which is second order on finite models but collapses to a first-order prefix on infinite models.



    Upload a copy of this work     Papers currently archived: 80,057

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Is Hintikka's Logic First-Order?Matti Eklund & Daniel Kolak - 2002 - Synthese 131 (3):371-388.
On existential declarations of independence in if logic.Fausto Barbero - 2013 - Review of Symbolic Logic 6 (2):254-280.
Decidability of independence-friendly modal logic.Merlijn Sevenster - 2010 - Review of Symbolic Logic 3 (3):415-441.
On Minimal Models.Francicleber Ferreira & Ana Teresa Martins - 2007 - Logic Journal of the IGPL 15 (5-6):503-526.
On the First-Order Prefix Hierarchy.Eric Rosen - 2005 - Notre Dame Journal of Formal Logic 46 (2):147-164.
Classical Negation and Game-Theoretical Semantics.Tero Tulenheimo - 2014 - Notre Dame Journal of Formal Logic 55 (4):469-498.
Cooperation in Games and Epistemic Readings of Independence-Friendly Sentences.Fausto Barbero - 2017 - Journal of Logic, Language and Information 26 (3):221-260.
SO(∀∃^*) Sentences and Their Asymptotic Probabilities.Eric Rosen & Jerzy Tyszkiewicz - 2000 - Mathematical Logic Quarterly 46 (4):435-452.
Dependence of variables construed as an atomic formula.Jouko Väänänen & Wilfrid Hodges - 2010 - Annals of Pure and Applied Logic 161 (6):817-828.
Henkin quantifiers and the definability of truth.Tapani Hyttinen & Gabriel Sandu - 2000 - Journal of Philosophical Logic 29 (5):507-527.


Added to PP

4 (#1,265,930)

6 months
1 (#477,912)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Independence friendly logic.Tero Tulenheimo - 2010 - Stanford Encyclopedia of Philosophy.
Cooperation in Games and Epistemic Readings of Independence-Friendly Sentences.Fausto Barbero - 2017 - Journal of Logic, Language and Information 26 (3):221-260.

Add more citations

References found in this work

Compositional semantics for a language of imperfect information.W. Hodges - 1997 - Logic Journal of the IGPL 5 (4):539-563.
Some remarks on infinitely long formulas.L. Henkin - 1961 - Journal of Symbolic Logic 30 (1):167--183.
Finite Partially‐Ordered Quantifiers.Herbert B. Enderton - 1970 - Mathematical Logic Quarterly 16 (8):393-397.
Complexity of syntactical tree fragments of Independence-Friendly logic.Fausto Barbero - 2021 - Annals of Pure and Applied Logic 172 (1):102859.
Some combinatorics of imperfect information.Peter Cameron & Wilfrid Hodges - 2001 - Journal of Symbolic Logic 66 (2):673-684.

View all 13 references / Add more references