CS Paper Radar

Nonstandard Axiomatic Semantics

Patrick Cousot

cs.LO ·submitted 2026-08-24 09:00 UTC · v1

Abstract

Similar to Skolem's nonstandard models of Peano's naturals, we show that axiomatic semantics based on Hoare logic has nonstandard models and so does not specify a unique, well-defined, and formal operational semantics of programming languages. We propose to enrich axiomatic semantics with additional proof obligations to solve this ambiguity problem. These proof obligations are always satisfied for standard trace models so that Hoare logic proofs are unchanged for these standard models.

Comment
ICTAC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Towards an Operational Proof-theoretic Semantics

cs.LO ·2026-10-05 ·Alexander V. Gheorghiu
hot direction similarity 0.64
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

Formalization of Fragments of the Theory of Hereditarily Finite Sets

cs.LO ·2026-09-28 ·Zuzana Haniková, Štěpán Holub
published similarity 0.62
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

The axiomatization of the theory of hereditarily finite sets in first-order classical logic is systematically explored and formalized in Isabelle/HOL. The formalization uses a hierarchy of locales, each corresponding to a fragment of the theory given by a particular collection of axioms. An inductive definition of first-order definable predicates is introduced and used to formalize axiom schemata. Special attention is paid to several equivalent axioms of finiteness, as well as to several equivalent ways of expressing regularity. The work also formalizes several facts about the independence of an axiom from a system of axioms by defining appropriate models.

0.44

Internal Reasoning and Consistency in Reflective Grounded Arithmetic

cs.LO math.LOcs.PL ·2026-08-17 ·Bryan Ford
theory similarity 0.62
Abstract · title adjusted and substantially revised; now 177 pages

Reflective Grounded Arithmetic (RGA) is a paracomplete arithmetic allowing direct expression of any general-recursive computation. Every RGA term is a program and truth is grounded evaluation, with a proof certificate at each universal quantifier. This paper shows, in a machine-checked Isabelle/HOL development, that such a system is powerful enough to carry out its own metamathematics. A fuel-indexed decider of RGA's grounded semantics and checkers for RGA's proofs are compiled primitive-recursive RGA terms. RGA proves internally that its decider never affirms $0 = 1$, and that every well-formed term it affirms has an RGA proof accepted by a transparent test. RGA proves that, for each valid RGA proof, its conclusion is true. RGA proves that each grounded-true well-formed term is provable. RGA proves that no proof in either of two decided classes of RGA proofs derives $0 = 1$. Gödel's incompleteness theorems hold for RGA, but their proofs must be adapted. In RGA an implication $A \rightarrow B$ is strictly stronger than an entailment $A \vdash B$: RGA discharges a hypothesis only when it can prove the hypothesis decided, a restriction needed to defuse Curry's paradox. RGA's implication is material and RGA has the disjunction property, so RGA proves no implication between ungrounded sentences. The implications that the textbook proof of Gödel's second theorem uses are of this kind and fail, but the entailments and rules it uses hold: Gödel's proof survives as entailments. RGA does not prove its consistency sentence $\mathit{Con}$: RGA carries out Gödel's argument internally, with a decided proof predicate and explicit proof transformers, and only the last step, that RGA does not prove $0 = 1$, is left to HOL. RGA also proves its own second incompleteness theorem as an entailment from $\mathit{Con}$, and as a single sentence quantified over proofs.

0.41

Internal Languages for Thin Epsilon-Hyperdoctrines: Soundness, Completeness, and Rocq Formalization

cs.LO math.LOmath.CT ·2026-10-10 ·Zoltán Gábor Molnár, Csaba Tóth
code/data similarity 0.59
Abstract · 41 pages, 1 figure. Rocq formalization: https://github.com/mozow01/HyperLogic

We present a typed proof-term calculus for intuitionistic intensional first-order logic with Hilbert's epsilon-operator and prove its soundness and completeness with respect to hyperdoctrinal models with thin bicartesian closed setoid categories (BiCCCs) as fibres and formula-indexed witness selections. The calculus provides an explicit internal language for these epsilon-hyperdoctrines: for each fixed typed signature, its syntactic term model is initial for syntax-indexed, interpretation-preserving model morphisms, with uniqueness up to setoid equality. The nested epsilon syntax is organized by a well-founded dependency relation on formula labels. Concrete countermodels exhibit failure of excluded middle and show that formula conversion need not identify the selected witnesses. We also compare the full calculus with its epsilon-free and epsilon-only fragments. The principal constructions and metatheorems are formalized in Rocq. With setoid BiCCCs, proof irrelevance is a choice of equality, not the erasure of proofs: the proofs and their categorical operations remain available as the basis for a future proof-relevant categorical semantics.

0.43

Gödel's Incompleteness Theorems in Grounded Arithmetic

cs.LO math.LOcs.PL ·2026-11-10 ·Bryan Ford
theory similarity 0.58
Abstract · 103 pages; splits the Goedel incompleteness material out of Internal Reasoning companion paper 2608.16140, which is getting a corresponding …

Reflective Grounded Arithmetic (RGA) is a paracomplete arithmetic in which every term is a program and truth is grounded evaluation. RGA discharges a hypothesis only when it proves the hypothesis decided. This paper shows, in a machine-checked Isabelle/HOL development, how Gödel's incompleteness theorems hold for RGA and for systems built on it. RGA's implication is material and RGA has the disjunction property, so the implications the textbook proof of the second theorem uses fail while its entailments and rules hold: Gödel's proof survives as entailments. RGA does not prove its consistency sentence Con, and RGA derives its own second theorem as the entailment $\mathit{Con}\vdash\neg\mathit{Pr}(\ulcorner\mathit{Con}\urcorner)$ and as one sentence quantified over proofs. The second theorem is then proved once, for every Gödel extension of RGA: an entailment relation on RGA's language, closed under RGA's rules, with a checker that meets three structural conditions, NEC, D3 and EXPL as proof transformers, D1 as closed acceptance, and consistency. D2 is not among the conditions. RGA with its checker is one instance. Inductive Grounded Arithmetic (IGA), RGA with ground induction, is another, its checker adding one rule detector, and IGA does not derive its consistency sentence for it. Adoption, a reflection rule whose premise is a derived warrant that the checker accepts computed proofs of every instance of a universal, gives consistent extensions RGA$^+$ and IGA$^+$. RGA$^+$ derives RGA's consistency sentence and IGA$^+$ derives RGA's and IGA's, so each strictly extends its base, and IGA$^+$ both. The second theorem holds at every adopted notation claim, and adopting Turing's code for that claim's checker derives its consistency sentence, so no claim certifies itself. Whether IGA alone derives RGA's consistency sentence is open, and the paper names what two routes to an answer need.

0.29

Proofs Without Nominals: Gödel's Ontological Argument, its Shallow Embedding, and the Open Questions of the Monatshefte Notes

cs.LO cs.AImath.LO ·2026-09-28 ·Christoph Benzmüller
theory similarity 0.58
Abstract · 51 pages. New in v5: the witness criterion and the whole-term condition come apart (a proof with the nominal in a context alone); three open…

The shallow embedding of higher-order modal logic in classical higher-order logic, used in Benzmüller and Scott's Notes on Gödel's and Scott's variants of the ontological argument, reaches beyond the modal object language: its quantifiers range over domains containing the nominals and satisfaction operators of hybrid logic. A proof using one proves a theorem of the embedding, not necessarily of the modal logic. Whether a result is one of the modal logic can be settled by replaying it in an explicit calculus, or, more cheaply and for all results at once, by analysing what the embedding's proofs substitute. Every statement the Notes prove has a proof in the embedding substituting nothing outside the object language, 294 of them explicit. The Notes' own proofs substitute none either; what it flags are terms a prover introduced. A soundness theorem over general models closed under the object language, and a sentence of that language the embedding proves but which fails in such a model, fix what the certificate says. The Notes' three open questions are settled too, without nominals, but by the empty instance of the conjunction axiom, too cheaply to convince. Generalised to Gödel's "any number of summands", the axiom covers the empty conjunction and the singleton. This article restricts it to at least two different conjuncts, a non-degenerate reading of Gödel's footnote, and settles them again without nominals. In effect only the empty conjunction is excluded; the singleton comes back with the other axioms. In one variant the restriction refutes the possible existence of a God-like being; the answers return, with no side condition, once the Notes' non-emptiness clause is confined to Gödel's essence. Every theorem here is verified in Isabelle/HOL and independently in Lean 4, the separating model in its propositional part; the countermodels are Nitpick's, checked by the build.

0.45

The Formalization of two Computational Models in Dafny

cs.LO cs.FLcs.PL ·2026-09-28 ·Ştefan Ciobâc\b{a}, Diana-Elena Gratie, Dragoş-Irinel Rotariu
publishedtheory similarity 0.58
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

We describe the formalization in Dafny of two computational models, Turing Machines and the Lambda Calculus. We present several application of the formalizations: machine proofs of termination for Turing machines, Dafny proofs for Church encodings, and a mechanized proof of the Church-Rosser theorem.

0.41

Idealizing Useful Fictions in Omega Grounded Arithmetic

cs.LO math.LOcs.PL ·2026-08-18 ·Bryan Ford
theory similarity 0.57
Abstract

Grounded arithmetic is a family of formal systems for reasoning about computation in which a statement may be asserted only when a terminating computation backs it; the logics are paracomplete - for a sentence whose backing computation never settles, neither the sentence nor its negation is derivable, so paradoxes like the Liar are harmless rather than explosive. The reflective member of the family, RGA, can quantify over its own computations, but cannot certify that its own unbounded searches have definite yes-or-no answers. This paper studies what happens when that openness is closed by exactly one rule - ATI, the $ω$-grounded universal: if every numeric instance of a universal sentence is certified decided, the universal is certified decided. The resulting system, OGA, shares RGA's syntax and rules symbol-for-symbol otherwise, and every consequence is developed as a machine-checked theorem. Decidedness certificates become abundant - every totality question about a computable function is certified to have an answer, whether or not anyone can produce it - and this is exactly the provable separation between the two systems. OGA is complete for its own semantics; certified-but-unresolved sentences receive values built from the system's own open questions. Provability remains recursively enumerable, with a primitive-recursive certificate checker, while $ω$-truth deliberately is not. Within that asymmetry, incompleteness takes a new form. The Gödel sentence is classified, unconditionally, as a genuine fiction: neither provable nor refutable, yet valued, and carrying a computable pedigree recording exactly what adopting it as an axiom commits one to. The adoption is itself a theorem suite: extending OGA by any finite stock of true fictions is consistent, and independently certified adoptions can never collide.

0.26