SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Logic and Scientific Methods

1997-01-01
María Luisa Dalla Chiara , Kees Doets , Daniele Mundici +1 more

Evidence and plausibility in neighborhood structures

2013-08-27
Johan van Benthem , David Fernández‐Duque , Eric Pacuit
View PDF Chat

The logical study of science

1982-06-01
Johan van Benthem

A Simple Logic of Functional Dependence

2021-03-24
Alexandru Baltag , Johan van Benthem
Abstract This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within … Abstract This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games.
View PDF Chat

The many faces of interpolation

2008-07-18
Johan van Benthem
View PDF Chat

Lindstrom theorems for fragments of first-order logic

2009-08-03
Johan van Benthem , Balder ten Cate , Jouko Väänánen
Lindstr\"om theorems characterize logics in terms of model-theoretic conditions such as Compactness and the L\"owenheim-Skolem property. Most existing characterizations of this kind concern extensions of first-order logic. But on the … Lindstr\"om theorems characterize logics in terms of model-theoretic conditions such as Compactness and the L\"owenheim-Skolem property. Most existing characterizations of this kind concern extensions of first-order logic. But on the other hand, many logics relevant to computer science are fragments or extensions of fragments of first-order logic, e.g., k-variable logics and various modal logics. Finding Lindstr\"om theorems for these languages can be challenging, as most known techniques rely on coding arguments that seem to require the full expressive power of first-order logic. In this paper, we provide Lindstr\"om theorems for several fragments of first-order logic, including the k-variable fragments for k>2, Tarski's relation algebra, graded modal logic, and the binary guarded fragment. We use two different proof techniques. One is a modification of the original Lindstr\"om proof. The other involves the modal concepts of bisimulation, tree unraveling, and finite depth. Our results also imply semantic preservation theorems.
View PDF Chat

THE MODAL LOGIC OF STEPWISE REMOVAL

2020-07-21
Johan van Benthem , Krzysztof Mierzewski , Francesca Zaffora Blando
Abstract We investigate the modal logic of stepwise removal of objects, both for its intrinsic interest as a logic of quantification without replacement, and as a pilot study to better … Abstract We investigate the modal logic of stepwise removal of objects, both for its intrinsic interest as a logic of quantification without replacement, and as a pilot study to better understand the complexity jumps between dynamic epistemic logics of model transformations and logics of freely chosen graph changes that get registered in a growing memory. After introducing this logic ( MLSR ) and its corresponding removal modality, we analyze its expressive power and prove a bisimulation characterization theorem. We then provide a complete Hilbert-style axiomatization for the logic of stepwise removal in a hybrid language enriched with nominals and public announcement operators. Next, we show that model-checking for MLSR is PSPACE-complete, while its satisfiability problem is undecidable. Lastly, we consider an issue of fine-structure: the expressive power gained by adding the stepwise removal modality to fragments of first-order logic.
View PDF Chat

Lindstrom theorems for fragments of first-order logic

2007-07-01
Balder ten Cate , Johan van Benthem , Jouko Väänánen
Lindstrom theorems characterize logics in terms of model-theoretic conditions such as Compactness and the Lowenheim-Skolem property. Most existing Lindstrom theorems concern extensions of first-order logic. On the other hand, many … Lindstrom theorems characterize logics in terms of model-theoretic conditions such as Compactness and the Lowenheim-Skolem property. Most existing Lindstrom theorems concern extensions of first-order logic. On the other hand, many logics relevant to computer science are fragments or extensions of fragments of first-order logic, e.g., k-variable logics and various modal logics. Finding Lindstrom theorems for these languages can be challenging, as most known techniques rely on coding arguments that seem to require the full expressive power of first-order logic. In this paper, we provide Lindstrom characterizations for a number of fragments of first-order logic. These include the k-variable fragments for k > 2, Tarski's relation algebra, graded modal logic, and the binary guarded fragment. We use two different proof techniques. One is a modification of the original Lindstrom proof. The other involves the modal concepts of bisimulation, tree unraveling, and finite depth. Our results also imply semantic preservation theorems. Characterizing the 2-variable fragment or the full guarded fragment remain open problems.
View PDF Chat

Changing a Semantics: Opportunism or Courage?

2014-01-01
Hajnal Andréka , Johan van Benthem , Nick Bezhanishvili +1 more
View PDF Chat

A New Game Equivalence and its Modal Logic

2017-07-25
Johan van Benthem , Nick Bezhanishvili , Sebastian Enqvist
We revisit the crucial issue of natural game equivalences, and semantics of game logics based on these. We present reasons for investigating finer concepts of game equivalence than equality of … We revisit the crucial issue of natural game equivalences, and semantics of game logics based on these. We present reasons for investigating finer concepts of game equivalence than equality of standard powers, though staying short of modal bisimulation. Concretely, we propose a more finegrained notion of equality of "basic powers" which record what players can force plus what they leave to others to do, a crucial feature of interaction. This notion is closer to game-theoretic strategic form, as we explain in detail, while remaining amenable to logical analysis. We determine the properties of basic powers via a new representation theorem, find a matching "instantial neighborhood game logic", and show how our analysis can be extended to a new game algebra and dynamic game logic.
View PDF Chat

A set-theoretical equivalent of the prime ideal theorem for Boolean algebras

1975-01-01
Johan van Benthem
View PDF Chat

A note on Jónsson's theorem

1988-12-01
Johan van Benthem

Mathematical Logic and Natural Language: Life at the border

2003-01-01
Johan van Benthem

Computing rational beliefs under limited foresight.

2015-02-12
Johan van Benthem , Chanjuan Liu , Paolo Turrini

Joachim Lambek: The beauty of mathematics in language

2010-01-01
Johan van Benthem , Michael Moortgat

A Logical Analysis of Dynamic Dependence

2022-01-01
Alexandru Baltag , Johan van Benthem , Dazhu Li
Many forms of dependence manifest themselves over time, with behavior of variables in dynamical systems as a paradigmatic example. This paper studies temporal dependence in dynamical systems from a logical … Many forms of dependence manifest themselves over time, with behavior of variables in dynamical systems as a paradigmatic example. This paper studies temporal dependence in dynamical systems from a logical perspective, by enriching a minimal modal base logic of static functional dependencies. We first introduce a logic for dynamical systems featuring temporalized variables, provide a complete axiomatic proof calculus, and show that its satisfiability problem is decidable. Then, to capture explicit reasoning about dynamic transition functions, we enhance the framework with function symbols and term identity. Next we combine temporalized variables with a modality for next-time truth from standard temporal logic, where modal correspondence analysis reveals the principles needed for a complete and decidable logic of timed dynamical systems supporting reductions between the two ways of referring to time. Our final result is an axiomatization of a general decidable logic of dependencies in arbitrary dynamical systems. We conclude with a brief outlook on how the systems introduced here mesh with richer temporal logics of system behavior, and with dynamic topological logic.
View PDF Chat

Nonstandard Reasoning

2015-01-01
Johan van Benthem

Evidence and plausibility in neighborhood structures

2013-01-01
Johan van Benthem , David Fernández‐Duque , Eric Pacuit
The intuitive notion of evidence has both semantic and syntactic features. In this paper, we develop an {\em evidence logic} for epistemic agents faced with possibly contradictory evidence from different … The intuitive notion of evidence has both semantic and syntactic features. In this paper, we develop an {\em evidence logic} for epistemic agents faced with possibly contradictory evidence from different sources. The logic is based on a neighborhood semantics, where a neighborhood $N$ indicates that the agent has reason to believe that the true state of the world lies in $N$. Further notions of relative plausibility between worlds and beliefs based on the latter ordering are then defined in terms of this evidence structure, yielding our intended models for evidence-based beliefs. In addition, we also consider a second more general flavor, where belief and plausibility are modeled using additional primitive relations, and we prove a representation theorem showing that each such general model is a $p$-morphic image of an intended one. This semantics invites a number of natural special cases, depending on how uniform we make the evidence sets, and how coherent their total structure. We give a structural study of the resulting `uniform' and `flat' models. Our main result are sound and complete axiomatizations for the logics of all four major model classes with respect to the modal language of evidence, belief and safe belief. We conclude with an outlook toward logics for the dynamics of changing evidence, and the resulting language extensions and connections with logics of plausibility change.

Local Dependence and Guarding

2022-01-01
Johan van Benthem , Balder ten Cate , Raoul Koudijs
We study LFD, a base logic of functional dependence introduced by Baltag and van Benthem (2021) and its connections with the guarded fragment GF of first-order logic. Like other logics … We study LFD, a base logic of functional dependence introduced by Baltag and van Benthem (2021) and its connections with the guarded fragment GF of first-order logic. Like other logics of dependence, the semantics of LFD uses teams: sets of permissible variable assignments. What sets LFD apart is its ability to express local dependence between variables and local dependence of statements on variables. Known features of LFD include decidability, explicit axiomatization, finite model property, and a bisimulation characterization. Others, including the complexity of satisfiability, remained open so far. More generally, what has been lacking is a good understanding of what makes the LFD approach to dependence computationally well-behaved, and how it relates to other decidable logics. In particular, how do allowing variable dependencies and guarding quantifiers compare as logical devices? We provide a new compositional translation from GF into LFD, and conversely, we translate LFD into GF in an `almost compositional' manner. Using these two translations, we transfer known results about GF to LFD in a uniform manner, yielding, e.g., tight complexity bounds for LFD satisfiability, as well as Craig interpolation. Conversely, e.g., the finite model property of LFD transfers to GF. Thus, local dependence and guarding turn out to be intricately entangled notions.
View PDF Chat

Knowability as continuity: a topological account of informational dependence

2024-01-01
Alexandru Baltag , Johan van Benthem
We study knowable informational dependence between empirical questions, modeled as continuous functional dependence between variables in a topological setting. We also investigate epistemic independence in topological terms and show that … We study knowable informational dependence between empirical questions, modeled as continuous functional dependence between variables in a topological setting. We also investigate epistemic independence in topological terms and show that it is compatible with functional (but non-continuous) dependence. We then proceed to study a stronger notion of knowability based on uniformly continuous dependence. On the technical logical side, we determine the complete logics of languages that combine general functional dependence, continuous dependence, and uniformly continuous dependence.

Knowability as continuity: a topological account of informational dependence

2024-01-01
Alexandru Baltag , Johan van Benthem
We study knowable informational dependence between empirical questions, modeled as continuous functional dependence between variables in a topological setting. We also investigate epistemic independence in topological terms and show that … We study knowable informational dependence between empirical questions, modeled as continuous functional dependence between variables in a topological setting. We also investigate epistemic independence in topological terms and show that it is compatible with functional (but non-continuous) dependence. We then proceed to study a stronger notion of knowability based on uniformly continuous dependence. On the technical logical side, we determine the complete logics of languages that combine general functional dependence, continuous dependence, and uniformly continuous dependence.

A Logical Analysis of Dynamic Dependence

2022-01-01
Alexandru Baltag , Johan van Benthem , Dazhu Li
Many forms of dependence manifest themselves over time, with behavior of variables in dynamical systems as a paradigmatic example. This paper studies temporal dependence in dynamical systems from a logical … Many forms of dependence manifest themselves over time, with behavior of variables in dynamical systems as a paradigmatic example. This paper studies temporal dependence in dynamical systems from a logical perspective, by enriching a minimal modal base logic of static functional dependencies. We first introduce a logic for dynamical systems featuring temporalized variables, provide a complete axiomatic proof calculus, and show that its satisfiability problem is decidable. Then, to capture explicit reasoning about dynamic transition functions, we enhance the framework with function symbols and term identity. Next we combine temporalized variables with a modality for next-time truth from standard temporal logic, where modal correspondence analysis reveals the principles needed for a complete and decidable logic of timed dynamical systems supporting reductions between the two ways of referring to time. Our final result is an axiomatization of a general decidable logic of dependencies in arbitrary dynamical systems. We conclude with a brief outlook on how the systems introduced here mesh with richer temporal logics of system behavior, and with dynamic topological logic.
View PDF Chat

Local Dependence and Guarding

2022-01-01
Johan van Benthem , Balder ten Cate , Raoul Koudijs
We study LFD, a base logic of functional dependence introduced by Baltag and van Benthem (2021) and its connections with the guarded fragment GF of first-order logic. Like other logics … We study LFD, a base logic of functional dependence introduced by Baltag and van Benthem (2021) and its connections with the guarded fragment GF of first-order logic. Like other logics of dependence, the semantics of LFD uses teams: sets of permissible variable assignments. What sets LFD apart is its ability to express local dependence between variables and local dependence of statements on variables. Known features of LFD include decidability, explicit axiomatization, finite model property, and a bisimulation characterization. Others, including the complexity of satisfiability, remained open so far. More generally, what has been lacking is a good understanding of what makes the LFD approach to dependence computationally well-behaved, and how it relates to other decidable logics. In particular, how do allowing variable dependencies and guarding quantifiers compare as logical devices? We provide a new compositional translation from GF into LFD, and conversely, we translate LFD into GF in an `almost compositional' manner. Using these two translations, we transfer known results about GF to LFD in a uniform manner, yielding, e.g., tight complexity bounds for LFD satisfiability, as well as Craig interpolation. Conversely, e.g., the finite model property of LFD transfers to GF. Thus, local dependence and guarding turn out to be intricately entangled notions.
View PDF Chat

A Simple Logic of Functional Dependence

2021-03-24
Alexandru Baltag , Johan van Benthem
Abstract This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within … Abstract This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games.
View PDF Chat

THE MODAL LOGIC OF STEPWISE REMOVAL

2020-07-21
Johan van Benthem , Krzysztof Mierzewski , Francesca Zaffora Blando
Abstract We investigate the modal logic of stepwise removal of objects, both for its intrinsic interest as a logic of quantification without replacement, and as a pilot study to better … Abstract We investigate the modal logic of stepwise removal of objects, both for its intrinsic interest as a logic of quantification without replacement, and as a pilot study to better understand the complexity jumps between dynamic epistemic logics of model transformations and logics of freely chosen graph changes that get registered in a growing memory. After introducing this logic ( MLSR ) and its corresponding removal modality, we analyze its expressive power and prove a bisimulation characterization theorem. We then provide a complete Hilbert-style axiomatization for the logic of stepwise removal in a hybrid language enriched with nominals and public announcement operators. Next, we show that model-checking for MLSR is PSPACE-complete, while its satisfiability problem is undecidable. Lastly, we consider an issue of fine-structure: the expressive power gained by adding the stepwise removal modality to fragments of first-order logic.
View PDF Chat

A New Game Equivalence and its Modal Logic

2017-07-25
Johan van Benthem , Nick Bezhanishvili , Sebastian Enqvist
We revisit the crucial issue of natural game equivalences, and semantics of game logics based on these. We present reasons for investigating finer concepts of game equivalence than equality of … We revisit the crucial issue of natural game equivalences, and semantics of game logics based on these. We present reasons for investigating finer concepts of game equivalence than equality of standard powers, though staying short of modal bisimulation. Concretely, we propose a more finegrained notion of equality of "basic powers" which record what players can force plus what they leave to others to do, a crucial feature of interaction. This notion is closer to game-theoretic strategic form, as we explain in detail, while remaining amenable to logical analysis. We determine the properties of basic powers via a new representation theorem, find a matching "instantial neighborhood game logic", and show how our analysis can be extended to a new game algebra and dynamic game logic.
View PDF Chat

Computing rational beliefs under limited foresight.

2015-02-12
Johan van Benthem , Chanjuan Liu , Paolo Turrini

Nonstandard Reasoning

2015-01-01
Johan van Benthem

Changing a Semantics: Opportunism or Courage?

2014-01-01
Hajnal Andréka , Johan van Benthem , Nick Bezhanishvili +1 more
View PDF Chat

Evidence and plausibility in neighborhood structures

2013-08-27
Johan van Benthem , David Fernández‐Duque , Eric Pacuit
View PDF Chat

Evidence and plausibility in neighborhood structures

2013-01-01
Johan van Benthem , David Fernández‐Duque , Eric Pacuit
The intuitive notion of evidence has both semantic and syntactic features. In this paper, we develop an {\em evidence logic} for epistemic agents faced with possibly contradictory evidence from different … The intuitive notion of evidence has both semantic and syntactic features. In this paper, we develop an {\em evidence logic} for epistemic agents faced with possibly contradictory evidence from different sources. The logic is based on a neighborhood semantics, where a neighborhood $N$ indicates that the agent has reason to believe that the true state of the world lies in $N$. Further notions of relative plausibility between worlds and beliefs based on the latter ordering are then defined in terms of this evidence structure, yielding our intended models for evidence-based beliefs. In addition, we also consider a second more general flavor, where belief and plausibility are modeled using additional primitive relations, and we prove a representation theorem showing that each such general model is a $p$-morphic image of an intended one. This semantics invites a number of natural special cases, depending on how uniform we make the evidence sets, and how coherent their total structure. We give a structural study of the resulting `uniform' and `flat' models. Our main result are sound and complete axiomatizations for the logics of all four major model classes with respect to the modal language of evidence, belief and safe belief. We conclude with an outlook toward logics for the dynamics of changing evidence, and the resulting language extensions and connections with logics of plausibility change.

Joachim Lambek: The beauty of mathematics in language

2010-01-01
Johan van Benthem , Michael Moortgat

Lindstrom theorems for fragments of first-order logic

2009-08-03
Johan van Benthem , Balder ten Cate , Jouko Väänánen
Lindstr\"om theorems characterize logics in terms of model-theoretic conditions such as Compactness and the L\"owenheim-Skolem property. Most existing characterizations of this kind concern extensions of first-order logic. But on the … Lindstr\"om theorems characterize logics in terms of model-theoretic conditions such as Compactness and the L\"owenheim-Skolem property. Most existing characterizations of this kind concern extensions of first-order logic. But on the other hand, many logics relevant to computer science are fragments or extensions of fragments of first-order logic, e.g., k-variable logics and various modal logics. Finding Lindstr\"om theorems for these languages can be challenging, as most known techniques rely on coding arguments that seem to require the full expressive power of first-order logic. In this paper, we provide Lindstr\"om theorems for several fragments of first-order logic, including the k-variable fragments for k>2, Tarski's relation algebra, graded modal logic, and the binary guarded fragment. We use two different proof techniques. One is a modification of the original Lindstr\"om proof. The other involves the modal concepts of bisimulation, tree unraveling, and finite depth. Our results also imply semantic preservation theorems.
View PDF Chat

The many faces of interpolation

2008-07-18
Johan van Benthem
View PDF Chat

Lindstrom theorems for fragments of first-order logic

2007-07-01
Balder ten Cate , Johan van Benthem , Jouko Väänánen
Lindstrom theorems characterize logics in terms of model-theoretic conditions such as Compactness and the Lowenheim-Skolem property. Most existing Lindstrom theorems concern extensions of first-order logic. On the other hand, many … Lindstrom theorems characterize logics in terms of model-theoretic conditions such as Compactness and the Lowenheim-Skolem property. Most existing Lindstrom theorems concern extensions of first-order logic. On the other hand, many logics relevant to computer science are fragments or extensions of fragments of first-order logic, e.g., k-variable logics and various modal logics. Finding Lindstrom theorems for these languages can be challenging, as most known techniques rely on coding arguments that seem to require the full expressive power of first-order logic. In this paper, we provide Lindstrom characterizations for a number of fragments of first-order logic. These include the k-variable fragments for k > 2, Tarski's relation algebra, graded modal logic, and the binary guarded fragment. We use two different proof techniques. One is a modification of the original Lindstrom proof. The other involves the modal concepts of bisimulation, tree unraveling, and finite depth. Our results also imply semantic preservation theorems. Characterizing the 2-variable fragment or the full guarded fragment remain open problems.
View PDF Chat

Mathematical Logic and Natural Language: Life at the border

2003-01-01
Johan van Benthem

Logic and Scientific Methods

1997-01-01
María Luisa Dalla Chiara , Kees Doets , Daniele Mundici +1 more

A note on Jónsson's theorem

1988-12-01
Johan van Benthem

The logical study of science

1982-06-01
Johan van Benthem

A set-theoretical equivalent of the prime ideal theorem for Boolean algebras

1975-01-01
Johan van Benthem
View PDF Chat
Coauthor Papers Together
Balder ten Cate 3
Alexandru Baltag 3
Nick Bezhanishvili 2
David Fernández‐Duque 2
Jouko Väänánen 2
Eric Pacuit 2
Sebastian Enqvist 1
Raoul Koudijs 1
Daniele Mundici 1
Krzysztof Mierzewski 1
Hajnal Andréka 1
Chanjuan Liu 1
István Németi 1
María Luisa Dalla Chiara 1
Kees Doets 1
Paolo Turrini 1
Michael Moortgat 1
Dazhu Li 1
Francesca Zaffora Blando 1