Tue May 10, 2016
234 Moses Hall, 4–6 PM
Johan van Benthem (Amsterdam and Stanford)
Decidable Versions of First-Order Predicate Logic
There are two ways of finding decidability inside first-order logic: one is by restricting attention to language fragments, the other is by generalizing the usual semantics. In this talk, I explain a recent generalized semantics by Aldo Antonelli, which leads to a decidable version of predicate logic that induces an effective translation into the Guarded Fragment. I will discuss this proposal and the resulting program.
Also, I make a comparison with existing decidable first-order semantics via general assignment models and via games, and with the move in modal logic from relational semantics to neighborhood semantics. Finally, I discuss the resulting landscape of weak decidable first-order logics, and its links with decidable fragments of the first-order language. This suggests many open problems that I will flag throughout.
Ref. H. Andréka, J. van Benthem & I. Németi, 2016, ‘On a New Semantics for First‐Order Predicate Logic’, Journal of Philosophical Logic, to appear.