| 1. |
- Gengelbach, Arve, et al.
(författare)
-
A Verified Cyclicity Checker For Theories with Overloaded Constants
- 2022
-
Ingår i: 13th International Conference on Interactive Theorem Proving (ITP 2022). - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
-
Konferensbidrag (refereegranskat)abstract
- Non-terminating (dependencies of) definitions can lead to logical contradictions, for example when defining a boolean constant as its own negation. Some proof assistants thus detect and disallow non-terminating definitions. Termination is generally undecidable when constants may have different definitions at different type instances, which is called (ad-hoc) overloading. The Isabelle/HOL proof assistant supports overloading of constant definitions, but relies on an unclear foundation for this critical termination check. With this paper we aim to close this gap: we present a mechanised proof that, for restricted overloading, non-terminating definitions are of a detectable cyclic shape, and we describe a mechanised algorithm with its correctness proof. In addition we demonstrate this cyclicity checker on parts of the Isabelle/HOL main library. Furthermore, we introduce the first-ever formally verified kernel of a proof assistant for higher-order logic with overloaded definitions. All our results are formalised in the HOL4 theorem prover.
|
|
| 2. |
- Gengelbach, Arve
(författare)
-
Conservative Definitions for Higher-order Logic with Ad-hoc Overloading
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- With an ever growing dependency on computer systems, the need to guarantee their correct behaviour increases. Mathematically rigorous techniques like formal verification offer a way to derive a system's mathematical properties for example with the help of a theorem prover. A theorem prover is a type of software that assists a user in deriving theorems expressed in a formal language. With a theorem prover one should never be able to prove something that is contradictory, as otherwise the proof effort is worthless. This property is called consistency and is essential for formal developments.Theorem provers enjoy high confidence, since they often rely on a trusted logical kernel that is enriched with new symbols in a controlled way. Instead of asserting the existence of mathematical objects with their desired properties, new symbols are introduced through definitions. These definitions are checked by this kernel, and expected to act as abbreviations. Any theorem that is expressible without a definition should not need that definition in its proof. A definition satisfying this property is called conservative. Conservative definitions are especially important as they preserve consistency, so that a proof of a contradiction is not possible after adding these definitions.Isabelle/HOL is a prominent theorem prover with the unique feature of permitting different definitions of one constant at non-overlapping types. In addition to these so-called overloading definitions, a symbol may be used before it is defined. These features mean that consistency or conservativity arguments for simpler logics do not immediately apply to Isabelle/HOL. In the past, design flaws in the definitional mechanism made theories in the Isabelle/HOL theorem prover inconsistent, e.g. it was possible to derive a contradiction from cyclic definitions.With this thesis we show that (overloading) definitions in higher-order logic (HOL) are conservative, hence not source of inconsistency. We define and prove a notion of conservativity that applies to theories of overloading definitions in higher-order logic and formalise aspects of our results in a theorem prover. As a practical implication, when searching for a proof of a formula, our syntactic conservativity criterion allows to exclude irrelevant symbols. In particular, our results confirm that Isabelle/HOL theories are consistent, thus users cannot introduce contradictions through definitions. As a specialisation of our work, our notion of conservativity holds for variants of HOL without overloading. Overall, our work contributes to the understanding of higher-order logic with overloading definitions.
|
|
| 3. |
- Gengelbach, Arve, et al.
(författare)
-
Mechanisation of Model-theoretic Conservative Extension for HOL with Ad-hoc Overloading
- 2021
-
Ingår i: Proceedings Fifteenth Workshop on Logical Frameworks and Meta-Languages. - : Open Publishing Association. ; , s. 1-17
-
Konferensbidrag (refereegranskat)abstract
- Definitions of new symbols merely abbreviate expressions in logical frameworks, and no new facts (regarding previously defined symbols) should hold because of a new definition. In Isabelle/HOL, definable symbols are types and constants. The latter may be ad-hoc overloaded, i.e. have different definitions for non-overlapping types. We prove that symbols that are independent of a new definition may keep their interpretation in a model extension. This work revises our earlier notion of model-theoretic conservative extension and generalises an earlier model construction. We obtain consistency of theories of definitions in higher-order logic (HOL) with ad-hoc overloading as a corollary. Our results are mechanised in the HOL4 theorem prover.
|
|
| 4. |
- Gengelbach, Arve, et al.
(författare)
-
Model-theoretic Conservative Extension of Definitional Theories
- 2018
-
Ingår i: Electronic Notes in Theoretical Computer Science. - : Elsevier BV. - 1571-0661. ; 338, s. 133-145
-
Tidskriftsartikel (refereegranskat)abstract
- Many logical frameworks allow extensions, i.e. the introduction of new symbols, by definitions. Different from asserting arbitrary non-logical axioms, extensions by definitions are expected to be conservative: they should entail no new theorems in the original language. The popular theorem prover Isabelle implements a variant of higher-order logic that allows ad hoc overloading of constants. In 2015, Kunčar and Popescu introduced definitional theories, which impose a non-circularity condition on constant and type definitions in this logic, and showed that this condition is sufficient for definitional extensions to preserve consistency. We strengthen and generalize this result by showing that extensions of definitional theories are model-theoretic conservative, i.e. every model of the original theory can be expanded to a model of the extended theory.
|
|
| 5. |
- Gengelbach, Arve, et al.
(författare)
-
Proof-theoretic Conservativity for HOL with Ad-hoc Overloading
- 2020
-
Ingår i: Theoretical Aspects of Computing - ICTAC 2020 - 17th International Colloquium, Macau, China, November 30 - December 4, 2020. - Cham : Springer. - 9783030642761 ; , s. 23-42
-
Konferensbidrag (refereegranskat)abstract
- Logical frameworks are often equipped with an extensional mechanism to define new symbols. The definitional mechanism is expected to be conservative, i.e. it shall not introduce new theorems of the original language. The theorem proving framework Isabelle implements a variant of higher-order logic where constants may be ad-hoc overloaded, allowing a constant to have different definitions for non-overlapping types. In this paper we prove soundness and completeness for the logic of Isabelle/HOL with general (Henkin-style) semantics, and we prove model-theoretic and proof-theoretic conservativity for theories of definitions.
|
|
| 6. |
- Gengelbach, Arve, et al.
(författare)
-
Towards Correctly Checking for Cycles in Overloaded Definitions
- 2021
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Safe extension of a logic with definitional axioms need acyclic definitions, because cycles in definitions possibly entail contradiction. In this report we give a mechanised exact characterisation of acyclic overloading definitions. Our results support the soundness argument of the cyclicity checker of the Isabelle/HOL theorem prover, and serve as the theoretical foundation for future verification of such a cyclicity checker.
|
|
| 7. |
- Åman Pohjola, Johannes, et al.
(författare)
-
A Mechanised Semantics for HOL with Ad-hoc Overloading
- 2020
-
Konferensbidrag (refereegranskat)abstract
- Isabelle/HOL augments classical higher-order logic with ad-hoc overloading of constant definitions— that is, one constant may have several definitions for non-overlapping types. In this paper, we present a mechanised proof that HOL with ad-hoc overloading is consistent. All our results have been formalised in the HOL4 theorem prover.
|
|
