This paper starts from the observation that the standard arguments for compositionality are really arguments for the computability of semantics. Since computability does not entail compositionality, the question of what justifies compositionality recurs. The paper then elaborates on the idea of recursive semantics as corresponding to computable semantics. It is then shown by means of time complexity theory and with the use of term rewriting as systems of semantic computation, that syntactically unrestricted, noncompositional recursive semantics leads to computational explosion (factorial complexity). Hence, with combinatorially unrestricted syntax, semantics with tractable time complexity is compositional.

The injective version of Cantor’s theorem appears in full second-order logic as the inconsistency of the abstraction principle, Frege’s Basic Law V (BLV), an inconsistency easily shown using Russell’s paradox. This incompatibility is akin to others—most notably that of a (Dedekind) infinite universe with the Nuisance Principle (NP) discussed by neo-Fregean philosophers of mathematics. This paper uses the Burali–Forti paradox to demonstrate this incompatibility, and another closely related, without appeal to principles related to the axiom of choice—a result hitherto unestablished. It discusses both the general interest of this result, its interest to neo-Fregean philosophy of mathematics, and the potential significance of the Burali–Fortian method of proof.

There has been a recent interest in hierarchical generalizations of classic incompleteness results. This paper provides evidence that such generalizations are readily obtainable from suitably formulated hierarchical versions of the principles used in the original proofs. By collecting such principles, we prove hierarchical versions of Mostowski’s theorem on independent formulae, Kripke’s theorem on flexible formulae, Woodin’s theorem on the universal algorithm, and a few related results. As a corollary, we obtain the expected result that the formula expressing “ $\mathrm {T}$ is $\Sigma _n$ -ill” is a canonical example of a $\Sigma _{n+1}$ formula that is $\Pi _{n+1}$ -conservative over $\mathrm {T}$ .

Any set of truth-functional connectives has sequent calculus rules that can be generated systematically from the truth tables of the connectives. Such a sequent calculus gives rise to a multi-conclusion natural deduction system and to a version of Parigot’s free deduction. The elimination rules are “general,” but can be systematically simplified. Cut-elimination and normalization hold. Restriction to a single formula in the succedent yields intuitionistic versions of these systems. The rules also yield generalized lambda calculi providing proof terms for natural deduction proofs as in the Curry–Howard isomorphism. Addition of an indirect proof rule yields classical single-conclusion versions of these systems. Gentzen’s standard systems arise as special cases.

Is knowledge definable as justified true belief (“JTB”)? We argue that one can legitimately answer positively or negatively, depending on whether or not one’s true belief is justified by what we call adequate reasons. To facilitate our argument we introduce a simple propositional logic of reason-based belief, and give an axiomatic characterization of the notion of adequacy for reasons. We show that this logic is sufficiently flexible to accommodate various useful features, including quantification over reasons. We use our framework to contrast two notions of JTB: one internalist, the other externalist. We argue that Gettier cases essentially challenge the internalist notion but not the externalist one. Our approach commits us to a form of infallibilism about knowledge, but it also leaves us with a puzzle, namely whether knowledge involves the possession of only adequate reasons, or leaves room for some inadequate reasons. We favor the latter position, which reflects a milder and more realistic version of infallibilism.

This paper explores relational syllogistic logics, a family of logical systems related to reasoning about relations in extensions of the classical syllogistic. These are all decidable logical systems. We prove completeness theorems and complexity results for a natural subfamily of relational syllogistic logics, parametrized by constructors for terms and for sentences.

We propose a dynamic hyperintensional logic of belief revision for non-omniscient agents, reducing the logical omniscience phenomena affecting standard doxastic/epistemic logic as well as AGM belief revision theory. Our agents don’t know all a priori truths; their belief states are not closed under classical logical consequence; and their belief update policies are such that logically or necessarily equivalent contents can lead to different revisions. We model both plain and conditional belief, then focus on dynamic belief revision. The key idea we exploit to achieve non-omniscience focuses on topic- or subject matter-sensitivity: a feature of belief states which is gaining growing attention in the recent literature.