Recent berkeleylogic_wp items

Completeness for an Intuitionistic Modal Logic of Vagueness

Sat, 14 Jan 2023 00:00:00 +0000

Completeness for an Intuitionistic Modal Logic of Vagueness

B-Frame Duality

Fri, 5 Aug 2022 00:00:00 +0000

This paper introduces the category of b-frames as a new tool in the study of complete lattices. B-frames can be seen as a generalization of posets, which play an important role in the representation theory of Heyting algebras, but also in the study of complete Boolean algebras in forcing. This paper combines ideas from the two traditions in order to generalize some techniques and results to the wider context of complete lattices. In particular, we lift a representation theorem of Allwein and MacCaull to a duality between complete lattices and b-frames, and we derive alternative characterizations of several classes of complete lattices from this duality. This framework is then used to obtain new results in the theory of complete Heyting algebras and the semantics of intuitionistic propositional logic.

A fundamental non-classical logic

Sun, 17 Jul 2022 00:00:00 +0000

We give a proof-theoretic as well as a semantic characterization of a logic in the signature with conjunction, disjunction, negation, and the universal and existential quantifiers that we suggest has a certain fundamental status. We present a Fitch-style natural deduction system for the logic that contains only the introduction and elimination rules for the logical constants. From this starting point, if one adds the rule that Fitch called Reiteration, one obtains a proof system for intuitionistic logic in the given signature; if instead of adding Reiteration, one adds the rule of Reductio ad Absurdum, one obtains a proof system for orthologic; by adding both Reiteration and Reductio, one obtains a proof system for classical logic. Arguably neither Reiteration nor Reductio is as intimately related to the meaning of the connectives as the introduction and elimination rules are, so the base logic we identify serves as a more fundamental starting point and common ground between proponents...

A partial-state space model of unawareness

Wed, 22 Jun 2022 00:00:00 +0000

A partial-state space model of unawareness

The Orthologic of Epistemic Modals

Fri, 28 Jan 2022 00:00:00 +0000

Epistemic modals have peculiar logical features that are challenging to account for in a broadly classical framework. For instance, while a sentence of the form $p\wedge\Diamond\neg p$ ('$p$, but it might be that not~$p$') appears to be a contradiction, $\Diamond\neg p$ does not entail $\neg p$, which would follow in classical logic. Likewise, the classical laws of distributivity and disjunctive syllogism fail for epistemic modals. Existing attempts to account for these facts generally either under- or over-correct. Some theories predict that $p\wedge\Diamond\neg p$, a so-called epistemic contradiction, is a contradiction only in an etiolated sense, under a notion of entailment that does not always allow us to replace $p\wedge\Diamond\neg p$ with a contradiction; these theories underpredict the infelicity of embedded epistemic contradictions. Other theories savage classical logic, eliminating not just rules that intuitively fail, like distributivity...

Split Cycle: A New Condorcet Consistent Voting Method Independent of Clones and Immune to Spoilers

Sun, 19 Apr 2020 00:00:00 +0000

We propose a Condorcet consistent voting method that we call Split Cycle. Split Cycle belongs to the small family of known voting methods satisfying the anti-vote-splitting criterion of independence of clones. In this family, only Split Cycle satisfies a new criterion we call immunity to spoilers, which concerns adding candidates to elections, as well as the known criteria of positive involvement and negative involvement, which concern adding voters to elections. Thus, in contrast to other clone-independent methods, Split Cycle mitigates both “spoiler effects” and “strong no show paradoxes.”

Choice-free representation of ortholattices

Sun, 5 Apr 2020 00:00:00 +0000

Choice-free representation of ortholattices

On the Logic of Belief and Propositional Quantification

Sun, 16 Feb 2020 00:00:00 +0000

We consider extending the modal logic KD45, commonly taken as the baseline system for belief, with propositional quantifiers that can be used to formalize natural language sentences such as “everything I believe is true” or “there is some-thing that I neither believe nor disbelieve.” Our main results are axiomatizations of the logics with propositional quantifiers of natural classes of complete Boolean algebras with an operator (BAOs) validating KD45. Among them is the class of complete, atomic, and completely multiplicative BAOs validating KD45. Hence, by duality, we also cover the usual method of adding propositional quantifiers to normal modal logics by considering their classes of Kripke frames. In addition, we obtain decidability for all the concrete logics we discuss.

ULTRAHOMOGENEOUS AND EXISTENTIALLY CLOSED HEYTING ALGEBRAS

Sun, 19 Jan 2020 00:00:00 +0000

ULTRAHOMOGENEOUS AND EXISTENTIALLY CLOSED HEYTING ALGEBRAS

Intuitionism and Nuclei

Sun, 19 Jan 2020 00:00:00 +0000

Intuitionism and Nuclei

Incompleteness and jump hierarchies

Tue, 14 Jan 2020 00:00:00 +0000

Incompleteness and jump hierarchies

Reflection ranks and ordinal analysis

Tue, 14 Jan 2020 00:00:00 +0000

It is well-known that natural axiomatic theories are well-ordered by consistency strength. However, it is possible to construct descending chains of artificial theories with respect to consistency strength. We provide an explanation of this well-orderness phenomenon by studying a coarsening of the consistency strength order, namely, the $\Pi^1_1$ reflection strength order. We prove that there are no descending sequences of $\Pi^1_1$ sound extensions of $\mathsf{ACA}_0$ in this order. Accordingly, we can attach a rank in this order, which we call reflection rank, to any $\Pi^1_1$ sound extension of $\mathsf{ACA}_0$. We prove that for any $\Pi^1_1$ sound theory $T$ extending $\mathsf{ACA}_0^+$, the reflection rank of $T$ equals the proof-theoretic ordinal of $T$. We also prove that the proof-theoretic ordinal of $\alpha$ iterated $\Pi^1_1$ reflection is $\varepsilon_\alpha$. Finally, we use our results to provide straightforward well-foundedness proofs of ordinal notation systems...

A note on the consistency operator

Thu, 9 May 2019 00:00:00 +0000

A note on the consistency operator

On the Logics with Propositional Quantifiers Extending S5Π

Mon, 20 Aug 2018 00:00:00 +0000

Scroggs's theorem on the extensions of S5 is an early landmark in the modern mathematical studies of modal logics. From it, we know that the lattice of normal extensions of S5 is isomorphic to the inverse order of the natural numbers with infinity and that all extensions of S5 are in fact normal. In this paper, we consider extending Scroggs's theorem to modal logics with propositional quantifiers governed by the axioms and rules analogous to the usual ones for ordinary quantifiers. We call them Π-logics. Taking S5Π, the smallest normal Π-logic extending S5, as the natural counterpart to S5 in Scroggs's theorem, we show that all normal Π-logics extending S5Π are complete with respect to their complete simple S5 algebras, that they form a lattice that is isomorphic to the lattice of the open sets of the disjoint union of two copies of the one-point compactification of N, that they have arbitrarily high Turing-degrees, and that there are non-normal Π-logics extending S5Π.

Operationalism Meets Modal Logic

Sat, 23 Jun 2018 00:00:00 +0000

Guided by a desire to eliminate language that refers to unobservable structure from mechanics, Ernst Mach proposed a definition of mass in terms of more directly observable data. A great deal of literature surrounds the question of whether this proposed definition accomplishes its stated goal, or even whether it constitutes a definition. In this talk we aim to bring clarity to this debate by using methods from model theory and from modal logic to classify, reconstruct, and evaluate these arguments. In particular, we exhibit a general construction of first-order modal frames for appropriately presented scientific theories with epistemic constraints. These frames allow us to characterize which properties are “modally definable” in the sense of Bressan.

One Modal Logic to Rule Them All? (Extended Technical Report)

Mon, 26 Mar 2018 00:00:00 +0000

One Modal Logic to Rule Them All? (Extended Technical Report)

Fine's canonicity theorem for some classes of neighborhood frames

Thu, 22 Feb 2018 00:00:00 +0000

Fine's canonicity theorem for some classes of neighborhood frames

Modal Correspondence Theory for Possibility Semantics

Wed, 21 Feb 2018 00:00:00 +0000

New version: https://escholarship.org/uc/item/2kf0p9bg

Possibility Frames and Forcing for Modal Logic (February 2018)

Sat, 17 Feb 2018 00:00:00 +0000

Possibility Frames and Forcing for Modal Logic (February 2018)

A Representation Theorem for Possibility Models

Sat, 30 Dec 2017 00:00:00 +0000

This paper is about the relation between two kinds of models for propositional modal logic: possibility models in the style of Humberstone and possible world models in the style of Kripke. We show that every countable possibility model M is completed by a Kripke model K, its worldization; every total world of K is the limit of more and more refined possibilities in M, and every possibility in M is realized by some total world of K. In addition, we define a general notion of a possibilization of a Kripke model, which is a possibility model whose possibilities are sets of worlds from the Kripke model. We then characterize the class of possibility models that are isomorphic to the possibilization of some Kripke model. In particular, every possibility model in this class can be represented as a possibilization of one of its worldizations; and every possibility model can be naturally transformed into one in this...

Arrow's Decisive Coalitions

Sun, 8 Oct 2017 00:00:00 +0000

In his classic monograph, Social Choice and Individual Values, Arrow introduced the notion of a decisive coalition of voters as part of his mathematical framework for social choice theory. The subsequent literature on Arrow’s Impossibility Theorem has shown the importance for social choice theory of reasoning about coalitions of voters with different grades of decisiveness. The goal of this paper is a fine-grained analysis of reasoning about decisive coalitions, formalizing how the concept of a decisive coalition gives rise to a social choice theoretic language and logic all of its own. We show that given Arrow’s axioms of the Independence of Irrelevant Alternatives and Universal Domain, rationality postulates for social preference correspond to strong axioms about decisive coalitions. We demonstrate this correspondence with results of a kind familiar in economics—representation theorems—as well as results of a kind coming from mathematical logic—completeness theorems. We present...

ON THE INEVITABILITY OF THE CONSISTENCY OPERATOR

Sun, 8 Oct 2017 00:00:00 +0000

ON THE INEVITABILITY OF THE CONSISTENCY OPERATOR

Results in Modal Correspondence Theory for Possibility Semantics

Thu, 5 Oct 2017 00:00:00 +0000

Results in Modal Correspondence Theory for Possibility Semantics

Possibility Frames and Forcing for Modal Logic (June 2016)

Tue, 21 Jun 2016 00:00:00 +0000

New version: https://escholarship.org/uc/item/0tm6b30q

First-order possibility models and finitary completeness proofs

Wed, 24 Feb 2016 00:00:00 +0000

This paper builds on Humberstone's idea of defining models of propositional modal logic where total possible worlds are replaced by partial possibilities. We follow a suggestion of Humberstone by introducing possibility models for quantified modal logic. We show that a simple quantified modal logic is sound and complete for our semantics. Although Holliday showed that for many propositional modal logics, it is possible to give a completeness proof using a canonical model construction where every possibility consists of finitely many formulas, we show that this is impossible to do in the first-order case. However, one can still construct a canonical model where every possibility consists of a computable set of formulas and thus still of finitely much information.

Scott Ranks of Models of a Theory

Wed, 24 Feb 2016 00:00:00 +0000

The Scott rank of a countable structure is a measure, coming from the proof of Scott's isomorphism theorem, of the complexity of that structure. The Scott spectrum of a theory (by which we mean a sentence of $\mc{L}_{\omega_1 \omega}$) is the set of Scott ranks of countable models of that theory. In $ZFC + PD$ we give a descriptive-set-theoretic classification of the sets of ordinals which are the Scott spectrum of a theory: they are particular $\bfSigma^1_1$ classes of ordinals.

Our investigation of Scott spectra leads to the resolution (in $ZFC$) of a number of open problems about Scott ranks. We answer a question of Montalb\'an by showing, for each $\alpha < \omega_1$, that there is a $\Pi^{\infi}_2$ theory with no models of Scott rank less than $\alpha$. We also answer a question of Knight and Calvert by showing that there are computable models of high Scott rank which are not computably approximable by models of low Scott rank. Finally, we answer a question of...

Possibility Frames and Forcing for Modal Logic

Fri, 1 Jan 2016 00:00:00 +0000

New version: https://escholarship.org/uc/item/0tm6b30q