The Experts below are selected from a list of 3897 Experts worldwide ranked by ideXlab platform
Lev D. Beklemishev - One of the best experts on this subject based on the ideXlab platform.
-
AXIOMATIZATION OF PROVABLE n-Provability
Journal of Symbolic Logic, 2019Co-Authors: Evgeny Kolmakov, Lev D. BeklemishevAbstract:A formula $\phi$ is called \emph{$n$-provable} in a formal arithmetical theory $S$ if $\phi$ is provable in $S$ together with all true arithmetical $\Pi_{n}$-sentences taken as additional axioms. While in general the set of all $n$-provable formulas, for a fixed $n>0$, is not recursively enumerable, the set of formulas $\phi$ whose $n$-Provability is provable in a given r.e.\ metatheory $T$ is r.e. This set is deductively closed and will be, in general, an extension of $S$. We prove that these theories can be naturally axiomatized in terms of progressions of iterated local reflection principles. In particular, the set of provably 1-provable sentences of Peano arithmetic PA can be axiomatized by $\varepsilon_0$ times iterated local reflection schema over PA. Our characterizations yield additional information on the proof-theoretic strength of these theories (w.r.t. various measures of it) and on their axiomatizability. We also study the question of speed-up of proofs and show that in some cases a proof of $n$-Provability of a sentence can be much shorter than its proof from iterated reflection principles.
-
axiomatizing provable n Provability
Doklady Mathematics, 2018Co-Authors: E A Kolmakov, Lev D. BeklemishevAbstract:The set of all formulas whose n-Provability in a given arithmetical theory S is provable in another arithmetical theory T is a recursively enumerable extension of S. We prove that such extensions can be naturally axiomatized in terms of transfinite progressions of iterated local reflection schemata over S. Specifically, the set of all provably 1-provable sentences in Peano arithmetic PA can be axiomatized by an e0-times iterated local reflection schema over PA. The resulting characterizations provide additional information on the proof-theoretic strength of these theories and on the complexity of their axiomatization.
-
topological interpretations of Provability logic
arXiv: Logic, 2014Co-Authors: Lev D. Beklemishev, David GabelaiaAbstract:Provability logic concerns the study of modality \(\Box \) as Provability in formal systems such as Peano Arithmetic. A natural, albeit quite surprising, topological interpretation of Provability logic has been found in the 1970s by Harold Simmons and Leo Esakia. They have observed that the dual \(\Diamond \) modality, corresponding to consistency in the context of formal arithmetic, has all the basic properties of the topological derivative operator acting on a scattered space. The topic has become a long-term project for the Georgian school of logic led by Esakia, with occasional contributions from elsewhere. More recently, a new impetus came from the study of polymodal Provability logic \(\mathbf {GLP}\) that was known to be Kripke incomplete and, in general, to have a more complicated behavior than its unimodal counterpart. Topological semantics provided a better alternative to Kripke models in the sense that \(\mathbf {GLP}\) was shown to be topologically complete. At the same time, new fascinating connections with set theory and large cardinals have emerged. We give a survey of the results on topological semantics of Provability logic starting from first contributions by Esakia. However, a special emphasis is put on the recent work on topological models of polymodal Provability logic. We also include a few results that have not been published so far, most notably the results of Sect. 10.4 (due to the second author) and Sects. 10.7, 10.8 (due to the first author).
-
kripke semantics for Provability logic glp
Annals of Pure and Applied Logic, 2010Co-Authors: Lev D. BeklemishevAbstract:Abstract A well-known polymodal Provability logic GLP due to Japaridze is complete w.r.t. the arithmetical semantics where modalities correspond to reflection principles of restricted logical complexity in arithmetic. This system plays an important role in some recent applications of Provability algebras in proof theory. However, an obstacle in the study of GLP is that it is incomplete w.r.t. any class of Kripke frames. In this paper we provide a complete Kripke semantics for GLP . First, we isolate a certain subsystem J of GLP that is sound and complete w.r.t. a nice class of finite frames. Second, appropriate models for GLP are defined as the limits of chains of finite expansions of models for J . The techniques involves unions of n -elementary chains and inverse limits of Kripke models. All the results are obtained by purely modal-logical methods formalizable in elementary arithmetic.
-
kripke semantics for Provability logic glp
Logic group preprint series, 2007Co-Authors: Lev D. BeklemishevAbstract:A well-known polymodal Provability logic GLP is complete w.r.t. the arithmetical semantics where modalities correspond to re∞ection principles of restricted logical complexity in arithmetic [9, 5, 8]. This system plays an important role in some recent applications of Provability algebras in proof theory [2, 3]. However, an obstacle in the study of GLP is that it is incomplete w.r.t. any class of Kripke frames. In this paper we provide a complete Kripke semantics for GLP. First, we isolate a certain subsystem J of GLP that is sound and complete w.r.t. a nice class of flnite frames. Second, appropriate models for GLP are deflned as the limits of chains of flnite expansions of models for J. The techniques involves unions of n-elementary chains and inverse limits of Kripke models. All the results are obtained by purely modal-logical methods formalizable in elementary arithmetic.
Yong Deng - One of the best experts on this subject based on the ideXlab platform.
-
multiscale probability transformation of basic probability assignment
Mathematical Problems in Engineering, 2014Co-Authors: Qi Zhang, Yong DengAbstract:Decision making is still an open issue in the application of Dempster-Shafer evidence theory. A lot of works have been presented for it. In the transferable belief model (TBM), pignistic probabilities based on the basic probability assignments are used for decision making. In this paper, multiscale probability transformation of basic probability assignment based on the belief function and the plausibility function is proposed, which is a generalization of the pignistic probability transformation. In the multiscale probability function, a factor q based on the Tsallis entropy is used to make the multiscale probabilities diversified. An example showing that the multiscale probability transformation is more reasonable in the decision making is given.
-
multiscale probability transformation of basic probability assignment
arXiv: Artificial Intelligence, 2014Co-Authors: Qi Zhang, Yong DengAbstract:Decision making is still an open issue in the application of Dempster-Shafer evidence theory. A lot of works have been presented for it. In the transferable belief model (TBM), pignistic probabilities based on the basic probability as- signments are used for decision making. In this paper, multiscale probability transformation of basic probability assignment based on the belief function and the plausibility function is proposed, which is a generalization of the pignistic probability transformation. In the multiscale probability function, a factor q based on the Tsallis entropy is used to make the multiscale prob- abilities diversified. An example is shown that the multiscale probability transformation is more reasonable in the decision making.
Joost J Joosten - One of the best experts on this subject based on the ideXlab platform.
-
turing jumps through Provability
arXiv: Logic, 2015Co-Authors: Joost J JoostenAbstract:Fixing some computably enumerable theory $T$, the Friedman-Goldfarb-Harrington (FGH) theorem says that over elementary arithmetic, each $\Sigma_1$ formula is equivalent to some formula of the form $\Box_T \varphi$ provided that $T$ is consistent. In this paper we give various generalizations of the FGH theorem. In particular, for $n>1$ we relate $\Sigma_{n}$ formulas to Provability statements $[n]_T^{\sf True}\varphi$ which are a formalization of "provable in $T$ together with all true $\Sigma_{n+1}$ sentences". As a corollary we conclude that each $[n]_T^{\sf True}$ is $\Sigma_{n+1}$-complete. This observation yields us to consider a recursively defined hierarchy of Provability predicates $[n+1]^\Box_T$ which look a lot like $[n+1]_T^{\sf True}$ except that where $[n+1]_T^{\sf True}$ calls upon the oracle of all true $\Sigma_{n+2}$ sentences, the $[n+1]^\Box_T$ recursively calls upon the oracle of all true sentences of the form $\langle n \rangle_T^\Box\phi$. As such we obtain a `syntax-light' characterization of $\Sigma_{n+1}$ definability whence of Turing jumps which is readily extended beyond the finite. Moreover, we observe that the corresponding Provability predicates $[n+1]_T^\Box$ are well behaved in that together they provide a sound interpretation of the polymodal Provability logic ${\sf GLP}_\omega$.
-
models of transfinite Provability logic
Journal of Symbolic Logic, 2013Co-Authors: David Fernandezduque, Joost J JoostenAbstract:For any ordinal Lambda, we can define a polymodal logic GLP(A), with a modality [xi] for each xi < Lambda. These represent Provability predicates of increasing strength. Although GLP(A) has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities, denoted GLP(omega)(0). Later, Icard defined a topological model for GLP(omega)(0) which is very closely related to Ignatiev's. In this paper we show how to extend these constructions for arbitrary Lambda. More generally, for each Theta, Lambda we build a Kripke model J(Lambda)(Theta) and a topological model L-Lambda(Theta), and show that GLP(Lambda)(0) is sound for both of these structures, as well as complete, provided Theta is large enough.
-
models of transfinite Provability logic
arXiv: Logic, 2012Co-Authors: David Fernandezduque, Joost J JoostenAbstract:For any ordinal \Lambda, we can define a polymodal logic GLP(\Lambda), with a modality [\xi] for each \xi<\Lambda. These represent Provability predicates of increasing strength. Although GLP(\Lambda) has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities. Later, Icard defined a topological model for the same fragment which is very closely related to Ignatiev's. In this paper we show how to extend these constructions for arbitrary \Lambda. More generally, for each \Theta,\Lambda we build a Kripke model I(\Theta,\Lambda) and a topological model T(\Theta,\Lambda), and show that the closed fragment of GLP(\Lambda) is sound for both of these structures, as well as complete, provided \Theta is large enough.
-
kripke models of transfinite Provability logic
Advances in Modal Logic, 2012Co-Authors: David Fernandezduque, Joost J JoostenAbstract:For any ordinal Λ, we can define a polymodal logic GLPΛ, with a modality [ξ] for each ξ < Λ. These represent Provability predicates of increasing strength. Although GLPΛ has no non-trivial Kripke frames, Ignatiev showed that indeed one can construct a universal Kripke frame for the variable-free fragment with natural number modalities, denoted GLPω. In this paper we show how to extend these constructions for arbitrary Λ. More generally, for each ordinals Θ,Λ we build a Kripke model IΛ and show that GLP 0 Λ is sound for this structure. In our notation, Ignatiev’s original model becomes I0 ω .
David Fernandezduque - One of the best experts on this subject based on the ideXlab platform.
-
the polytopologies of transfinite Provability logic
Archive for Mathematical Logic, 2014Co-Authors: David FernandezduqueAbstract:Provability logics are modal or polymodal systems designed for modeling the behavior of Godel’s Provability predicate and its natural extensions. If Λ is any ordinal, the Godel-Lob calculus GLP Λ contains one modality [λ] for each λ < Λ, representing Provability predicates of increasing strength. GLP ω has no non-trivial Kripke frames, but it is sound and complete for its topological semantics, as was shown by Icard for the variable-free fragment and more recently by Beklemishev and Gabelaia for the full logic. In this paper we generalize Beklemishev and Gabelaia’s result to GLP Λ for countable Λ. We also introduce Provability ambiances, which are topological models where valuations of formulas are restricted. With this we show completeness of GLP Λ for the class of Provability ambiances based on Icard polytopologies.
-
models of transfinite Provability logic
Journal of Symbolic Logic, 2013Co-Authors: David Fernandezduque, Joost J JoostenAbstract:For any ordinal Lambda, we can define a polymodal logic GLP(A), with a modality [xi] for each xi < Lambda. These represent Provability predicates of increasing strength. Although GLP(A) has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities, denoted GLP(omega)(0). Later, Icard defined a topological model for GLP(omega)(0) which is very closely related to Ignatiev's. In this paper we show how to extend these constructions for arbitrary Lambda. More generally, for each Theta, Lambda we build a Kripke model J(Lambda)(Theta) and a topological model L-Lambda(Theta), and show that GLP(Lambda)(0) is sound for both of these structures, as well as complete, provided Theta is large enough.
-
the polytopologies of transfinite Provability logic
arXiv: Logic, 2012Co-Authors: David FernandezduqueAbstract:Provability logics are modal or polymodal systems designed for modeling the behavior of G\"odel's Provability predicate in arithmetical theories and its natural extensions. If \Lambda is any ordinal, the G\"odel-L\"ob calculus GLP(\Lambda) contains one modality [\lambda] for each \lambda<\Lambda, representing Provability predicates of increasing strength. GLP(\Lambda) has no Kripke models, but Beklemishev and Gabelaia recently proved that GLP(\omega) is complete for its class of topological models. In this paper we generalize Beklemishev and Gabelaia's result to GLP(\Lambda) for arbitrary \Lambda. We also introduce Provability ambiances, which are topological models where valuations of formulas are restricted. With this we show completeness of GLP(\Lambda) for the class of Provability ambiances based on Icard polytopologies.
-
models of transfinite Provability logic
arXiv: Logic, 2012Co-Authors: David Fernandezduque, Joost J JoostenAbstract:For any ordinal \Lambda, we can define a polymodal logic GLP(\Lambda), with a modality [\xi] for each \xi<\Lambda. These represent Provability predicates of increasing strength. Although GLP(\Lambda) has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities. Later, Icard defined a topological model for the same fragment which is very closely related to Ignatiev's. In this paper we show how to extend these constructions for arbitrary \Lambda. More generally, for each \Theta,\Lambda we build a Kripke model I(\Theta,\Lambda) and a topological model T(\Theta,\Lambda), and show that the closed fragment of GLP(\Lambda) is sound for both of these structures, as well as complete, provided \Theta is large enough.
-
kripke models of transfinite Provability logic
Advances in Modal Logic, 2012Co-Authors: David Fernandezduque, Joost J JoostenAbstract:For any ordinal Λ, we can define a polymodal logic GLPΛ, with a modality [ξ] for each ξ < Λ. These represent Provability predicates of increasing strength. Although GLPΛ has no non-trivial Kripke frames, Ignatiev showed that indeed one can construct a universal Kripke frame for the variable-free fragment with natural number modalities, denoted GLPω. In this paper we show how to extend these constructions for arbitrary Λ. More generally, for each ordinals Θ,Λ we build a Kripke model IΛ and show that GLP 0 Λ is sound for this structure. In our notation, Ignatiev’s original model becomes I0 ω .
Joseph Y Halpern - One of the best experts on this subject based on the ideXlab platform.
-
lexicographic probability conditional probability and nonstandard probability
arXiv: Computer Science and Game Theory, 2003Co-Authors: Joseph Y HalpernAbstract:The relationship between Popper spaces (conditional probability spaces that satisfy some regularity conditions), lexicographic probability systems (LPS's), and nonstandard probability spaces (NPS's) is considered. If countable additivity is assumed, Popper spaces and a subclass of LPS's are equivalent; without the assumption of countable additivity, the equivalence no longer holds. If the state space is finite, LPS's are equivalent to NPS's. However, if the state space is infinite, NPS's are shown to be more general than LPS's.
-
lexicographic probability conditional probability and nonstandard probability
Theoretical Aspects of Rationality and Knowledge, 2001Co-Authors: Joseph Y HalpernAbstract:The relationship between Popper spaces (conditional probability spaces that satisfy some regularity conditions), lexicographic probability systems (LPS's) [Blume, Brandenburger, and Dekel 1991a; Blume, Brandenburger, and Dekel 1991b], and nonstandard probability spaces (NPS's) is considered. If countable additivity is assumed, Popper spaces and a subclass of LPS's are equivalent; without the assumption of countable additivity, the equivalence no longer holds. If the state space is finite, LPS's are equivalent to NPS's. However, if the state space is infinite, NPS's are shown to be more general than LPS's.
