To save content items to your account,
please confirm that you agree to abide by our usage policies.
If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account.
Find out more about saving content to .
To save content items to your Kindle, first ensure no-reply@cambridge.org
is added to your Approved Personal Document E-mail List under your Personal Document Settings
on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part
of your Kindle email address below.
Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations.
‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi.
‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
We show that for any class of Boolean algebras with an associative operator, if it contains the complex algebra of $(\mathcal {P}(\mathbb {N}), \cup )$, its equational theory is undecidable. Equivalently, any associative normal modal logic valid over the frame $(\mathcal {P}(\mathbb {N}), \cup )$ is undecidable. This settles a long-open question on the decidability of hyperboolean modal logic [16], and addresses several related problems.
It is a long-standing open problem whether modal logics of the form $\mathbf {K}\oplus \Box ^np\to \Box ^mp$ for $n>m>1$ have the finite model property (FMP). We solve this by showing that any modal logic axiomatized by formulas of the form $\Box ^np\to \Box ^mp$ where $n>m>1$ has the FMP.
We investigate the relationship between various versions of Ramsey’s theorem and bounding schemes in a model $\mathcal {N}$ of a fragment of arithmetic $F$. Our primary objective is to recast and extend the seminal results of Hirst [15] (see Theorem 1) through the modern lens of Weihrauch reducibility. By extracting explicit Weihrauch reductions from classical proofs, we expose the uniform computational content underlying these combinatorial principles, yielding a deeper and more refined understanding of their reverse mathematical strength.
Our results, informally stated in our terminology and established inside $\mathcal {N}$, are as follows: The following are equivalent: $\mathrm {B}\Sigma ^0_2$, the statement that the finite union of finite c.e. sets is finite, and the Infinite Pigeonhole Principle (see Theorem 3). We also discuss the Weihrauch relations between these logically equivalent principles (see Section 4). The Infinite Pigeonhole Principle is Weihrauch reducible to $\mathrm {RT}^2_2$ (see Theorem 4). There is also another principle logically equivalent to $\mathrm {B}\Sigma ^0_2$ which is Weihrauch reducible to $\mathrm {SRT}^2_2$ (see Theorem 5). We show that there is a principle which is equivalent to $\mathrm {B}\Sigma ^0_3$ (see Theorem 6) and Weihrauch reducible to $\mathrm {SRT}^2_{<\infty }$ (Theorem 7). We discuss some equivalences with $\mathrm {B}\Sigma ^0_{n}$ (see Section 6.1) and end with a problem Weihrauch reducible to $\mathrm {RT}^{n+1}_{2}$ (Section 6.2).
Since we work within the model $\mathcal {N}$, many standard definitions must be adjusted. Due to the expository nature of this article, these definitions are introduced throughout the text as needed. Reading the article from start to finish will provide a better understanding of the ideas involved than focusing only on individual theorems.
Many logical properties are known to be undecidable for normal modal logics, with few exceptions such as the consistency and the coincidence with $\mathsf {K}$. This article shows that the property of being a union-splitting in $\mathop {\mathsf {NExt}}{\mathsf {K}}$, the lattice of normal modal logics, is decidable, thus answering Problem 2 in [F. Wolter and M. Zakharyaschev, 2007]. This is done by providing a semantic characterization of union-splittings in terms of finite modal algebras. Moreover, by clarifying the connection to union-splittings, we show that in $\mathop {\mathsf {NExt}}{\mathsf {K}}$, having a decidable axiomatization problem and being a (un)decidable formula are also decidable. The latter answers Problem 17.3 in [A. Chagrov and M. Zakharyaschev, 1997] for $\mathop {\mathsf {NExt}}{\mathsf {K}}$.1
Kurt Gödel proved that it is not possible to characterize intuitionistic propositional logic (${IPL}$) by means of finite and deterministic truth-tables. After extending the same result with respect to non-deterministic matrices (Nmatrices), we provide a semantical characterization of ${IPL}$ by means of a $3$-valued Nmatrix with a restricted set of valuations. This structure allows to define an algorithm to delete unsound rows from the non-deterministic truth-tables generated for each formula, which constitutes a new and very simple decision procedure for ${IPL}$. This method can be seen as truth-tables in a broader sense, and a way to overcome Gödel’s limiting result.
A field K in a ring language $\mathcal {L}$ is finitely undecidable if $\mbox {Cons}(T)$ is undecidable for every nonempty finite $T \subseteq {\mathtt{Th}}(K; \mathcal {L})$. We extend a construction of Ziegler and (among other results) use a first-order classification of Anscombe and Jahnke to prove every NIP henselian nontrivially valued field is finitely undecidable. We conclude (assuming the NIP Fields Conjecture) that every NIP field is finitely undecidable. This work is drawn from the author’s PhD thesis [48, Chapter 3].
This paper extends the investigations into logical properties of the quantified argument calculus (Quarc) by suggesting a series of proper subsystems which, although retaining the entire vocabulary of Quarc, restrict quantification in such a way as to make the result decidable. The proof of decidability is via a procedure that prunes the infinite branches of a derivation tree in what is a syntactic counterpart of semantic filtration. We demonstrate an application of one of these systems by showing that Aristotle’s assertoric syllogistic is embeddable within, thus also providing another method of showing its decidability.
We prove that the class of all the rings $\mathbb {Z}/m\mathbb {Z}$ for all $m>1$ is decidable. This gives a positive solution to a problem of Ax asked in his celebrated 1968 paper on the elementary theory of finite fields [1, Problem 5, p. 270]. In our proof, we reduce the problem to the decidability of the ring of adeles $\mathbb {A}_{\mathbb {Q}}$ of $\mathbb {Q}$.
We show that the first-order logical theory of the binary overlap-free words (and, more generally, the $\alpha $-free words for rational $\alpha $, $2 < \alpha \leq 7/3$), is decidable. As a consequence, many results previously obtained about this class through tedious case-based proofs can now be proved “automatically,” using a decision procedure, and new claims can be proved or disproved simply by restating them as logical formulas.
Propositional modal logic over relational frames is naturally extended with propositional quantifiers by letting them range over arbitrary sets of worlds of the relevant frame. This is also known as second-order propositional modal logic. The propositionally quantified modal logic of a class of relational frames is often not axiomatizable, although there are known exceptions, most notably the case of frames validating the strong modal logic $\mathrm {S5}$. Here, we develop new general methods with which many of the open questions in this area can be answered. We illustrate the usefulness of these methods by applying them to a range of examples, which provide a detailed picture of which normal modal logics define classes of relational frames whose propositionally quantified modal logic is axiomatizable. We also apply these methods to establish new results in the multimodal case.
In Baghdad in the mid twelfth century Abū al-Barakāt proposes a radical new procedure for finding the conclusions of premise-pairs in syllogistic logic, and for identifying those premise-pairs that have no conclusions. The procedure makes no use of features of the standard Aristotelian apparatus, such as conversions or syllogistic figures. In place of these al-Barakāt writes out pages of diagrams consisting of labelled horizontal lines. He gives no instructions and no proof that the procedure will yield correct results. So the reader has to work out what his procedure is and whether it is correct. The procedure turns out to be insightful and entirely correct, but this paper may be the first study to give a full description of the procedure and a rigorous proof of its correctness.
Satisfaction systems and reductions between them are presented as an appropriate context for analyzing the satisfiability and the validity problems. The notion of reduction is generalized in order to cope with the meet-combination of logics. Reductions between satisfaction systems induce reductions between the respective satisfiability problems and (under mild conditions) also between their validity problems. Sufficient conditions are provided for relating satisfiability problems to validity problems. Reflection results for decidability in the presence of reductions are established. The validity problem in the meet-combination is proved to be decidable whenever the validity problem for the components are decidable. Several examples are discussed, namely, involving modal and intuitionistic logics, as well as the meet-combination of $\textrm {K}$ modal logic and intuitionistic logic.
We consider the structures $(\mathbb {Z}; \mathrm {SF}^{\mathbb {Z}})$, $(\mathbb {Z}; <, \mathrm {SF}^{\mathbb {Z}})$, $(\mathbb {Q}; \mathrm {SF}^{\mathbb {Q}})$, and $(\mathbb {Q}; <, \mathrm {SF}^{\mathbb {Q}})$ where $\mathbb {Z}$ is the additive group of integers, $\mathrm {SF}^{\mathbb {Z}}$ is the set of $a \in \mathbb {Z}$ such that $v_{p}(a) < 2$ for every prime p and corresponding p-adic valuation $v_{p}$, $\mathbb {Q}$ and $\mathrm {SF}^{\mathbb {Q}}$ are defined likewise for rational numbers, and $<$ denotes the natural ordering on each of these domains. We prove that the second structure is model-theoretically wild while the other three structures are model-theoretically tame. Moreover, all these results can be seen as examples where number-theoretic randomness yields model-theoretic consequences.
The prevalent interpretation of Gödel’s Second Theorem states that a sufficiently adequate and consistent theory does not prove its consistency. It is however not entirely clear how to justify this informal reading, as the formulation of the underlying mathematical theorem depends on several arbitrary formalisation choices. In this paper I examine the theorem’s dependency regarding Gödel numberings. I introduce deviant numberings, yielding provability predicates satisfying Löb’s conditions, which result in provable consistency sentences. According to the main result of this paper however, these “counterexamples” do not refute the theorem’s prevalent interpretation, since once a natural class of admissible numberings is singled out, invariance is maintained.
In this paper we explore the following question: how weak can a logic be for Rosser’s essential undecidability result to be provable for a weak arithmetical theory? It is well known that Robinson’s Q is essentially undecidable in intuitionistic logic, and P. Hájek proved it in the fuzzy logic BL for Grzegorczyk’s variant of Q which interprets the arithmetic operations as nontotal nonfunctional relations. We present a proof of essential undecidability in a much weaker substructural logic and for a much weaker arithmetic theory, a version of Robinson’s R (with arithmetic operations also interpreted as mere relations). Our result is based on a structural version of the undecidability argument introduced by Kleene and we show that it goes well beyond the scope of the Boolean, intuitionistic, or fuzzy logic.
In this article, we tell a story about incompleteness in modal logic. The story weaves together an article of van Benthem (1979), “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of completely additive modal algebras, or as we call them, ${\cal V}$-baos. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s article resolves the open question in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to ${\cal V}$-baos, namely the provability logic $GLB$ (Japaridze, 1988; Boolos, 1993). We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is ${\cal V}$-complete. After these results, we generalize the Blok Dichotomy (Blok, 1978) to degrees of ${\cal V}$-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness.
In this article we study proofs of some general forms of the Second Incompleteness Theorem. These forms conform to the Feferman format, where the proof predicate is fixed and the representation of the set of axioms varies. We extend the Feferman framework in one important point: we allow the interpretation of number theory to vary.
We provide algebraic conditions ensuring the decidability of the theory of modules over effectively given Prüfer (in particular Bézout) domains with infinite residue fields in terms of a suitable generalization of the prime radical relation. For Bézout domains these conditions are also necessary.
We show that under Dickson’s conjecture about the distribution of primes in the natural numbers, the theory Th (ℤ , +, 1, 0, Pr) where Pr is a predicate for the prime numbers and their negations is decidable, unstable, and supersimple. This is in contrast with Th (ℤ , +, 0, Pr, <) which is known to be undecidable by the works of Jockusch, Bateman, and Woods.
We show that the theory of the real field with a generic real power function is decidable, relative to an oracle for the rational cut of the exponent of the power function. We also show the existence of generic computable real numbers, hence providing an example of a decidable o-minimal proper expansion of the real field by an analytic function.
Recommend this
Email your librarian or administrator to recommend adding this to your organisation's collection.