Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Proof-theoretic Conservativity for HOL with Ad-hoc Overloading
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.ORCID iD: 0000-0001-7708-348X
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.ORCID iD: 0000-0001-8967-6987
2020 (English)In: Theoretical Aspects of Computing - ICTAC 2020 - 17th International Colloquium, Macau, China, November 30 - December 4, 2020 / [ed] Violet Ka I Pun, Volker Stolz, Adenilso da Silva Simão, Springer, 2020, Vol. 12545, p. 23-42Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer, 2020. Vol. 12545, p. 23-42
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349
Keywords [en]
Classical higher-order logic, Conservative theory extension, Proof-theoretic conservativity, Ad-hoc overloading, Isabelle
National Category
Computer Sciences Algebra and Logic
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-430371DOI: 10.1007/978-3-030-64276-1_2ISI: 000705051400002ISBN: 978-3-030-64276-1 (print)OAI: oai:DiVA.org:uu-430371DiVA, id: diva2:1515435
Conference
Theoretical Aspects of Computing (ICTAC), Nov 30-Dec 4, 2020, online, Macau, China
Available from: 2021-01-08 Created: 2021-01-08 Last updated: 2021-11-05Bibliographically approved
In thesis
1. Conservative Definitions for Higher-order Logic with Ad-hoc Overloading
Open this publication in new window or tab >>Conservative Definitions for Higher-order Logic with Ad-hoc Overloading
2021 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2021. p. 34
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 2021
Keywords
higher-order logic (HOL), conservative extension, ad-hoc overloading, definitions
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-435841 (URN)978-91-513-1150-0 (ISBN)
Public defence
2021-04-26, 2446, ITC, Lägerhyddsvägen 2, Uppsala, 09:15 (English)
Opponent
Supervisors
Note

Cover art by Melanie Rees, 2020.

Available from: 2021-03-29 Created: 2021-03-01 Last updated: 2021-04-23

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full texthttps://www.researchgate.net/publication/347362298_Theoretical_Aspects_of_Computing_-_ICTAC_2020_17th_International_Colloquium_Macau_China_November_30_-_December_4_2020_Proceedings_17th_International_Colloquium_Macau_China_November_30_-_December_4_202

Authority records

Gengelbach, ArveWeber, Tjark

Search in DiVA

By author/editor
Gengelbach, ArveWeber, Tjark
By organisation
Computing Science
Computer SciencesAlgebra and Logic

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 85 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf