CS Paper Radar

Two applications of the point-free coderivative

Zoltan A. Kocsis

cs.LO math.LOmath.CT ·submitted 2026-09-24 11:55 UTC · v1

Abstract

We present two new applications of Simmons' point-free Cantor-Bendixson coderivative operator in intuitionistic logic. First, we use it to give a simplified proof of the recent result of Xu and Ye that the free Heyting algebra on two generators does not occur as the Heyting algebra of subterminal objects in any elementary topos. Then we use it to prove that complete Heyting algebra semantics is not strongly complete for intuitionistic second-order propositional logic: semantic consequence from an arbitrary set of assumptions does not coincide with ordinary syntactic consequence.

Comment
23 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Complete Heyting Algebra Semantics for an Intuitionistic Version of Matching Logic (Extended Abstract)

cs.LO ·2026-09-28 ·Horaţiu Cheval
publishedtheory similarity 0.66
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

We present work in progress towards an intuitionistic version of Applicative Matching Logic. We introduce a semantics based on complete Heyting algebras, and propose a proof system which we prove to be sound relative to this semantics.

0.36

Restricted Peirce's Law and Natural Deduction

cs.LO ·2026-10-29 ·Satoru Niki
publishedtheoryhot direction similarity 0.65
Abstract · In Proceedings NCL'26, arXiv:2610.34489

The constructive logic JP' is known to be the weakest logic between intuitionistic and minimal logic that satisfies Glivenko's theorem. In spite of this natural and desirable formal property, the motivation for its notion of negation remains rather elusive: it can be characterised by a restriction of Peirce's law or by the double negation of ex falso quodlibet, neither of which is very intuitive. In order to have an alternative perspective on this negation, we study in this paper a couple of natural deduction systems for JP'. We first present a system that is normalisable and satisfies a restricted form of the subformula property. Then a modification of this system is introduced, whose rules satisfy the separation of connectives and the full subformula property. Afterwards we turn our attention to a typed lambda-calculus, with respect to which our natural deduction enjoys the Curry-Howard correspondence, followed by a concluding discussion.

0.40

New Proofs of Weak Normalization for Propositional Logic

cs.LO ·2026-09-13 ·S P Suresh
similarity 0.60
Abstract

We present new proofs of weak normalization for intuitionistic and classical propositional logics (with the full set of operators -- falsum, implication, conjunction and disjunction). These proofs work with cuts rather than cut segments, and they provide explicit ``local'' rules for determining whether to contract a whole proof or reduce one of its subproofs, and in the latter case, which subproof to reduce. Interestingly, much of the complication in the case of intuitionistic logic is due to the disjunction elimination rule, while our version of the same rule for classical logic has falsum as conclusion always, and so is much easier to handle. All the complication in the case of classical logic shifts to cuts involving the reductio ad absurdum rule. We also discuss a formalization of the entire proof in Lean, and present a deterministic algorithm for weak normalization.

0.20

Fine Selection for Intuitionistic Modal Logic

cs.LO math.LO ·2026-09-22 ·David Fernández-Duque
similarity 0.59
Abstract · This version corrects various typos and inaccuracies which, while minor, affected legibility. Notably, the definition of $Σ$-trees was missi…

We extend Fine's selection method to the setting of intuitionistic modal logic and use it to provide a model-theoretic proof that Fischer Servi-style intuitionistic $\sf K4$ has the finite model property.

0.23

Towards an Operational Proof-theoretic Semantics

cs.LO ·2026-10-05 ·Alexander V. Gheorghiu
hot direction similarity 0.58
Abstract

Model-theoretic semantics comes with a computational counterpart: to check validity is to search for a countermodel, and tableaux, resolution, and satisfiability solvers make the semantics something one can run. Proof-theoretic semantics -- the younger paradigm in which meaning is given by inferential role rather than by denotation -- has no established counterpart. This paper proposes one: logic programming. We show that Sandqvist's base-extension semantics for intuitionistic propositional logic is executable in a precise sense. Bases are logic programs, and to each formula $\varphi$ we assign a goal $[\![\varphi]\!]$ of a second-order hereditary Harrop language such that $\varphi$ is supported in a base $\mathcal{B}$ exactly when $[\![\varphi]\!]$ is operationally derivable from $\mathcal{B}$ read as a program. The encoding is the Russell-Prawitz translation of the connectives with quantification restricted to atoms, and this restriction is not a limitation but the point: it is what the support clauses themselves demand. The correspondence is exact base by base, not merely at the level of validity, so that intuitionistic validity becomes the success of a single query against the empty program. Logic programming stands to proof-theoretic semantics as tableaux and satisfiability solvers stand to model-theoretic semantics.

0.33

A minimal intuitionistic public announcement logic

cs.LO ·2026-11-10 ·Philippe Balbiani, Hans van Ditmarsch, Cigdem Gencer, Clara Lerouvillois
similarity 0.55
Abstract

We introduce intuitionistic public announcement logics Lmin and Lequ determined by classes of birelational frames where the intuitionistic preorder and the modal accessibility relation do not need to satisfy the confluence conditions traditionally considered within the framework of IPAL. Our logics can be seen as generalisations of IPAL seeing that their language is based on a binary epistemic modality of "relativised knowledge" that allows us to define valid reduction axioms. Our main results are the soundness and completeness of Lmin with respect to the class of all birelational frames and the soundness and completeness of Lequ with respect to the class of all birelational frames where the modal accessibility relation is an equivalence relation.

0.24

Higher Tripos Theory

cs.LO ·2026-10-19 ·Yoshihiro Maruyama
similarity 0.54
Abstract

Tripos theory constructs categorical models of higher-order logic from indexed logical data. We develop higher tripos theory and higher tripos-to-topos construction recovering the classical construction on zero-types through a covering criterion. The higher tripos-to-topos construction yields elementary $\infty$-toposes with closed bounded hierarchies of univalent universes, thus establishing a logical adjunction between $\infty$-triposes and elementary $\infty$-toposes with univalent universes. We also construct a logically conservative higher completion of regular $1$-categories with weak section families and a finite-limit-closed projective cover. This completion preserves original maps, predicates, and existing dependent products, and gives criteria for extending interpretations while preserving logical structure. With strongly inaccessible size bounds, Kleene assemblies instantiate the construction, producing a cumulative hierarchy of univalent universes that classifies every family in the completion and recovering the effective topos as the category of zero-types. We then establish an arithmetical completeness result: for a uniformly computably presented family, the numerical index set for identity with a fixed classifier code is $Π^0_2$-complete. We also construct two inequivalent univalent classifiers with the same global homotopy type: every internal map from one to the natural-number object is constant, whereas the other admits a nonconstant such map. These reconstruction, preservation, and computability results contribute to the higher effective-topos program of Awodey-Emmenegger and Anel-Awodey-Barton.

0.37

A generalised and modular proof-theoretic semantics for sequent systems

cs.LO math.LO ·2026-10-16 ·Victor Barroso-Nascimento, Arghya Chakrabarty, Elaine Pimentel
similarity 0.54
Abstract

Base-extension semantics explains logical consequence via derivability in atomic systems. Extending this approach across logics requires careful control of structural principles and contexts. We present a modular sequent-based framework in which support is indexed by multisets of atomic resources and the semantic clauses for connectives are guided by their left introduction rules. The framework separates additive from multiplicative behaviour and makes explicit the contributions of structural rules and restrictions on sequents. We establish soundness and completeness for classical and intuitionistic propositional logic and for multiplicative-additive fragments of classical and intuitionistic linear logic. We then investigate axiomatic extensions of intuitionistic logic through Jankov logic. Two classes of atomic bases yield sound and complete semantics. Completeness is proven using two novel and modular methods using simulation bases, one of which is constructive. These results provide a common semantic treatment of several logical systems while identifying the additional conditions needed to extend the framework beyond structural variations.

0.16