Search

(Goodsell, Journal of Philosophical Logic, 51(1), 127-150 2022) establishes the noncontingency of sentences of first-order arithmetic, in a plausible higher-order modal logic. Here, the same result is derived using significantly weaker assumptions. Most notably, the assumption of rigid comprehension—that every property is coextensive with a modally rigid one—is weakened to the assumption that the Boolean algebra of properties under necessitation is countably complete. The results are generalized to extensions of the language of arithmetic, and are applied to answer a question posed by Bacon and Dorr (2024). [ABSTRACT FROM AUTHOR]

A universal number (Unum) is a number representation format that can reduce the memory contention issues in multicore processors and parallel computing systems by optimizing the bit storage in the arithmetic operations. Given the safety-critical nature of applications of Unum format, there is a dire need to rigorously assess the correctness of the Unum based arithmetic operations. Unums are of three types, namely, Unum-I, Unum-II and Unum-III (commonly known as Posits). In this paper, we provide a higher-order-logic formalization of Unum-III (posits). In particular, we formally model a posit format (binary encoding of a posit), which is comprised of the sign, exponent, regime and fraction bits, using the HOL Light theorem prover. In order to prove the correctness of a posit format, we formally verify various properties regarding conversions of a real number to a posit and a posit to a real number and the scaling factors of the regime, exponent and fraction bits of a posit using HOL Light. [ABSTRACT FROM AUTHOR]

Designing dependable multiprocessor systems requires reliable interconnection networks. Multistage interconnection networks (MINs), including shuffle-exchange networks (SENs), are widely used to establish the desired connection. The failure of these networks can degrade the overall system performance, which may lead to significant losses. In this paper, we propose to formally model and analyze the dynamic dependability aspects of SENs using a combination of dynamic fault trees (DFTs) and dynamic reliability block diagrams (DRBDs) based on higher-order logic (HOL) theorem proving. We propose to integrate these two modeling approaches for efficiently handling the considered formal dependability analysis by leveraging upon the advantages of each method. The soundness of this integration is provided through a formal proof of equivalence between the DFT and DRBD algebras. We utilize the proposed framework to provide the formal DFT and DRBD analyses of three common measures of SENs, namely: terminal, broadcast and network reliability. The proposed approach allowed us to verify generic expressions of probability of failure and reliability of these systems, which can be instantiated with any number of system components and time-to-failure functions. [ABSTRACT FROM AUTHOR]

We present an approach for representing abstract argumentation frameworks based on an encoding into classical higher-order logic. This provides a uniform framework for computer-assisted assessment of abstract argumentation frameworks using interactive and automated reasoning tools. This enables the formal analysis and verification of meta-theoretical properties as well as the flexible generation of extensions and labellings with respect to well-known argumentation semantics. [ABSTRACT FROM AUTHOR]

We introduce our implementation in HOL Light of the metatheory for Gödel–Löb provability logic (GL), covering soundness and completeness w.r.t. possible world semantics and featuring a prototype of a theorem prover for GL itself. The strategy we develop here to formalise the modal completeness proof overcomes the technical difficulty due to the non-compactness of GL and is an adaptation—according to the formal language and tools at hand—of the proof given in George Boolos’ 1995 monograph. Our theorem prover for GL relies then on this formalisation, is implemented as a tactic of HOL Light that mimics the proof search in the labelled sequent calculus G 3 KGL , and works as a decision algorithm for the provability logic: if the algorithm positively terminates, the tactic succeeds in producing a HOL Light theorem stating that the input formula is a theorem of GL; if the algorithm negatively terminates, the tactic extracts a model falsifying the input formula. We discuss our code for the formal proof of modal completeness and the design of our proof search algorithm. Furthermore, we propose some examples of the latter’s interactive and automated use. [ABSTRACT FROM AUTHOR]

A shallow semantical embedding for public announcement logic (PAL) with relativized common knowledge is presented. This embedding enables the first-time automation of this logic with off-the-shelf theorem provers for classical higher-order logic. It is demonstrated (i) how meta-theoretical studies can be automated this way and (ii) how non-trivial reasoning in the target logic (PAL), required for instance to obtain a convincing encoding and automation of the wise men puzzle, can be realized. Key to the presented semantical embedding is that evaluation domains are modelled explicitly and treated as an additional parameter in the encodings of the constituents of the embedded target logic; in previous related works, e.g. on the embedding of normal modal logics, evaluation domains were implicitly shared between meta-logic and target logic. The work presented in this article constitutes an important addition to the pluralist LogiKEy knowledge engineering methodology, which enables experimentation with logics and their combinations, with general and domain knowledge, and with concrete use cases—all at the same time. [ABSTRACT FROM AUTHOR]

Zermelo's Theorem that the axiom of choice is equivalent to the principle that every set can be well-ordered goes through in third-order logic, but in second-order logic we run into expressivity issues. In this note, we show that in a natural extension of second-order logic weaker than third-order logic, choice still implies the well-ordering principle. Moreover, this extended second-order logic with choice is conservative over ordinary second-order logic with the well-ordering principle. We also discuss a variant choice principle, due to Hilbert and Ackermann, which neither implies nor is implied by the well-ordering principle. [ABSTRACT FROM AUTHOR]

Some propositions are true, and it is true that some propositions are true. Each of these facts looks like an impeccable ground of the other. But they cannot both ground each other, since grounding is asymmetric. This paper explores two new diagnoses of this much discussed puzzle. The tools of higher-order logic are used to show how both diagnoses can be fleshed out into strong and consistent theories of grounding. These theories of grounding in turn demand new theories of the granularity of propositions, properties, and relations. Even those who are uninterested in grounding should take seriously these pictures of reality's logical structure, which are in many ways reminiscent of Russell's and Wittgenstein's logical atomism. [ABSTRACT FROM AUTHOR]

What is absolutely unrestricted quantification? We distinguish two theoretical roles and identify two conceptions of absolute generality: maximally strong generality and maximally inclusive generality. We also distinguish two corresponding kinds of absolute domain. A maximally strong domain contains every potential counterexample to a generalisation. A maximally inclusive domain is such that no domain extends it. We argue that both conceptions of absolute generality are legitimate and investigate the relations between them. Although these conceptions coincide in standard settings, we show how they diverge under more complex assumptions about the structure of meaningful predication, such as cumulative type theory. We conclude by arguing that maximally strong generality is the more theoretically valuable conception. [ABSTRACT FROM AUTHOR]

The Isabelle Higher-order Tarski–Grothendieck object logic includes in its foundations both higher-order logic and set theory, which allows importing the libraries of Isabelle/HOL and Isabelle/Mizar. The two libraries, however, define all the basic concepts independently, which means that the results in the two are disconnected. In this paper, we align significant parts of these two libraries, by defining isomorphisms between their concepts, including the real numbers and algebraic structures. The isomorphisms allow us to transport theorems between the foundations and use the results from the libraries simultaneously. [ABSTRACT FROM AUTHOR]

Can conjunctive propositions be identical without their conjuncts being identical? Can universally quantified propositions be identical without their instances being identical? On a common conception of propositions, on which they inherit the logical structure of the sentences which express them, the answer is negative both times. Here, it will be shown that such a negative answer to both questions is inconsistent, assuming a standard type-theoretic formalization of theorizing about propositions. The result is not specific to conjunction and universal quantification, but applies to any binary operator and propositional quantifier. It is also shown that the result essentially arises out of giving a negative answer to both questions, as each negative answer is consistent by itself. [ABSTRACT FROM AUTHOR]

We recently designed two calculi as stepping stones towards superposition for full higher-order logic: Boolean-free λ -superposition and superposition for first-order logic with interpreted Booleans. Stepping on these stones, we finally reach a sound and refutationally complete calculus for higher-order logic with polymorphism, extensionality, Hilbert choice, and Henkin semantics. In addition to the complexity of combining the calculus’s two predecessors, new challenges arise from the interplay between λ -terms and Booleans. Our implementation in Zipperposition outperforms all other higher-order theorem provers and is on a par with an earlier, pragmatic prototype of Booleans in Zipperposition. [ABSTRACT FROM AUTHOR]

Isabelle is a generic theorem prover with a fragment of higher-order logic as a metalogic for defining object logics. Isabelle also provides proof terms. We formalize this metalogic and the language of proof terms in Isabelle/HOL, define an executable (but inefficient) proof term checker and prove its correctness w.r.t. the metalogic. We integrate the proof checker with Isabelle and run it on a range of logics and theories to check the correctness of all the proofs in those theories. [ABSTRACT FROM AUTHOR]

Abstract Two-dimensional (2D) image processing systems are concerned with the processing of the images represented as 2D arrays and are widely used in medicine, transportation and many other autonomous systems. The dynamics of these systems are generally modeled using 2D difference equations, which are mathematically analyzed using the 2D z-transform. It mainly involves a transformation of the difference equations-based models of these systems to their corresponding algebraic equations, mapping the 2D arrays (2D discrete-time signals) over the ( $$z_1$$ z 1 , $$z_2$$ z 2 )-domain. Finally, these ( $$z_1$$ z 1 , $$z_2$$ z 2 )-domain representations are used to analyze various properties of these systems, such as transfer function and stability. Conventional techniques, such as paper-and-pencil proof methods, and computer-based simulation techniques for analyzing these filters cannot assert the accuracy of the analysis due to their inherent limitations like human error proneness, limited computational resources and approximations of the mathematical expressions and results. In this paper, as a complimentary technique, we propose to use formal methods, higher-order logic (HOL) theorem proving, for formally analyzing the image processing filters. These methods can overcome the limitations of the conventional techniques and thus ascertain the accuracy of the analysis. In particular, we formalize the 2D z-transform based on the multivariate theories of calculus using the HOL Light theorem prover. Moreover, we formally analyze a generic ( $$L_1,L_2$$ L 1 , L 2 )-order 2D infinite impulse response image processing filter. We illustrate the practical effectiveness of our proposed approach by formally analyzing a second-order image processing filter.

Bond graph is a unified graphical approach for describing the dynamics of complex engineering and physical systems and is widely adopted in a variety of domains, such as, electrical, mechanical, medical, thermal and fluid mechanics. Traditionally, these dynamics are analyzed using paper-and-pencil proof methods and computer-based techniques. However, both of these techniques suffer from their inherent limitations, such as human-error proneness, approximations of results and enormous computational requirements. Thus, these techniques cannot be trusted for performing the bond graph based dynamical analysis of systems from the safety-critical domains like robotics and medicine. Formal methods, in particular, higher-order-logic theorem proving, can overcome the shortcomings of these traditional methods and provide an accurate analysis of these systems. It has been widely used for analyzing the dynamics of engineering and physical systems. In this paper, we propose to use higher-order-logic theorem proving for performing the bond graph based analysis of the physical systems. In particular, we provide formalization of bond graph, which mainly includes functions that allow conversion of a bond graph to its corresponding mathematical model (state–space model) and the verification of its various properties, such as, stability. To illustrate the practical effectiveness of our proposed approach, we present the formal stability analysis of a prosthetic mechatronic hand using HOL Light theorem prover. Moreover, to help non-experts in HOL, we encode our formally verified stability theorems in MATLAB to perform the stability analysis of an anthropomorphic prosthetic mechatronic hand. [ABSTRACT FROM AUTHOR]

Fractional-order PID control is a landmark in the development of fractional-order control theory. It can improve the control precision and accuracy of systems and achieve more robust control results. As a theorem-proving formal verification method, it can be applied to an arbitrary system represented by a mathematical model. It is the ideal verification method because it is not subject to limits on state numbers. This paper presents the higher-order logic (HOL) formal verification and modeling of fractional-order PID controller systems. Firstly, a fractional-order PID controller was designed. The accuracy of fractional-order PID control can be supported by simulation, comparing integral-order PID controls. Secondly, the superior property of fractional-order PID control is validated via higher-order logic theorem proofs. An important basic property, the relationship between fractional-order differential calculus and integral-order differential calculus, was analyzed via a higher-order logic theorem proof. Then, the relations between the fractional-order PID controller and integral-order PID controller were verified based on the fractional-order Grünwald–Letnikov definition for higher-order logic theorem proofs. Formalization models of the fractional-order PID controller and the fractional-order closed-loop control system were established. Finally, the stability of the fractional-order control systems was verified based on established formal models and theorems. The results show that the fractional-order PID controllers can be conducive to the control performance of control systems, and the higher-order logic formal verification method can ensure the reliability and security of fractional-order control systems. [ABSTRACT FROM AUTHOR]

Two-dimensional (2D) image processing systems are concerned with the processing of the images represented as 2D arrays and are widely used in medicine, transportation and many other autonomous systems. The dynamics of these systems are generally modeled using 2D difference equations, which are mathematically analyzed using the 2D z-transform. It mainly involves a transformation of the difference equations-based models of these systems to their corresponding algebraic equations, mapping the 2D arrays (2D discrete-time signals) over the ( z 1 , z 2 )-domain. Finally, these ( z 1 , z 2 )-domain representations are used to analyze various properties of these systems, such as transfer function and stability. Conventional techniques, such as paper-and-pencil proof methods, and computer-based simulation techniques for analyzing these filters cannot assert the accuracy of the analysis due to their inherent limitations like human error proneness, limited computational resources and approximations of the mathematical expressions and results. In this paper, as a complimentary technique, we propose to use formal methods, higher-order logic (HOL) theorem proving, for formally analyzing the image processing filters. These methods can overcome the limitations of the conventional techniques and thus ascertain the accuracy of the analysis. In particular, we formalize the 2D z-transform based on the multivariate theories of calculus using the HOL Light theorem prover. Moreover, we formally analyze a generic ( L 1 , L 2 )-order 2D infinite impulse response image processing filter. We illustrate the practical effectiveness of our proposed approach by formally analyzing a second-order image processing filter. [ABSTRACT FROM AUTHOR]

What is the relation between metaphysical necessity and essence? This paper defends the view that the relation is one of identity: metaphysical necessity is a special case of essence. My argument consists in showing that the best joint theory of essence and metaphysical necessity is one in which metaphysical necessity is just a special case of essence. The argument is made against the backdrop of a novel, higher-order logic of essence (HLE), whose core features are introduced in the first part of the paper. The second part investigates the relation between metaphysical necessity and essence in the context of HLE. Reductive hypotheses are among the most natural hypotheses to be explored in the context of HLE. But they also have to be weighed against their non-reductive rivals. I investigate three different reductive hypotheses and argue that two of them fare better than their non-reductive rivals: they are simpler, more natural, and more systematic. Specifically, I argue that one candidate reduction, according to which metaphysical necessity is truth in virtue of the nature of all propositions, is superior to the others, including one proposed by Kit Fine, according to which metaphysical necessity is truth in virtue of the nature of all objects. The paper concludes by offering some reasons to think that the best joint theory of essence and metaphysical necessity is one in which the logic of metaphysical necessity includes S4, but not S5. [ABSTRACT FROM AUTHOR]

A famous passage in Section 64 of Frege’s Grundlagen may be seen as a justification for the truth of abstraction principles. The justification is grounded in the procedure of content recarving which Frege describes in the passage. In this paper I argue that Frege’s procedure of content recarving while possibly correct in the case of first-order equivalence relations is insufficient to grant the truth of second-order abstractions. Moreover, I propose a possible way of justifying second-order abstractions by referring to the operation of content recarving and I show that the proposal relies to a certain extent on the Basic Law V. Therefore, if we are to justify the truth of second-order abstractions by invoking the content recarving procedure we are committed to a special status of some instances of the Basic Law V and thus to a special status of extensions of concepts as abstract objects.

Often philosophers, logicians, and mathematicians employ a notion of intended structure when talking about a branch of mathematics. In addition, we know that there are foundational mathematical theories that can find representatives for the objects of informal mathematics. In this paper, we examine how faithfully foundational theories can represent intended structures, and show that this question is closely linked to the decidability of the theory of the intended structure. We argue that this sheds light on the trade-off between expressive power and meta-theoretic properties when comparing first-order and second-order logic. [ABSTRACT FROM AUTHOR]

Decades of work have gone into developing efficient proof calculi, data structures, algorithms, and heuristics for first-order automatic theorem proving. Higher-order provers lag behind in terms of efficiency. Instead of developing a new higher-order prover from the ground up, we propose to start with the state-of-the-art superposition prover E and gradually enrich it with higher-order features. We explain how to extend the prover's data structures, algorithms, and heuristics to λ -free higher-order logic, a formalism that supports partial application and applied variables. Our extension outperforms the traditional encoding and appears promising as a stepping stone toward full higher-order logic. [ABSTRACT FROM AUTHOR]

We develop a theory of necessity operators within a version of higher-order logic that is neutral about how fine-grained reality is. The theory is axiomatized in terms of the primitive of being a necessity, and we show how the central notions in the philosophy of modality can be recovered from it. Various questions are formulated and settled within the framework, including questions about the ordering of necessities under strength, the existence of broadest necessities satisfying various logical conditions, and questions about their logical behaviour. We also wield the framework to probe the conditions under which a logicist account of necessities is possible, in which the theory is completely reducible to logic. [ABSTRACT FROM AUTHOR]

Orthodoxy holds that there is a determinate fact of the matter about every arithmetical claim. Little argument has been supplied in favour of orthodoxy, and work of Field, Warren and Waxman, and others suggests that the presumption in its favour is unjustified. This paper supports orthodoxy by establishing the determinacy of arithmetic in a well-motivated modal plural logic (Theorem 1). Recasting this result in higher-order logic (Theorem 13) reveals that even the nominalist who thinks that there are only finitely many things should think that there is some sense in which arithmetic is true and determinate. [ABSTRACT FROM AUTHOR]

The functorial structure of type constructors is the foundation for many definition and proof principles in higher-order logic (HOL). For example, inductive and coinductive datatypes can be built modularly from bounded natural functors (BNFs), a class of well-behaved type constructors. Composition, fixpoints, and—under certain conditions—subtypes are known to preserve the BNF structure. In this article, we tackle the preservation question for quotients, the last important principle for introducing new types in HOL. We identify sufficient conditions under which a quotient inherits the BNF structure from its underlying type. Surprisingly, lifting the structure in the obvious manner fails for some quotients, a problem that also affects the quotients of polynomial functors used in the Lean proof assistant. We provide a strictly more general lifting scheme that supports such problematic quotients. We extend the Isabelle/HOL proof assistant with a command that automates the registration of a quotient type as a BNF, reducing the proof burden on the user from the full set of BNF axioms to our inheritance conditions. We demonstrate the command’s usefulness through several case studies. [ABSTRACT FROM AUTHOR]

This paper investigates the connection between two recent trends in philosophy: higher-orderism and conceptual engineering. Higher-orderists use higher-order quantifiers (in particular quantifiers binding variables that occupy the syntactic positions of predicates) to express certain key metaphysical doctrines, such as the claim that there are properties. I argue that, on a natural construal, the higher-orderist approach involves an engineering project concerning, among others, the concept of existence. I distinguish between a modest construal of this project, on which it aims at engineering higher-order analogues of the familiar notion of first-order existence, and an ambitious construal, on which it additionally aims at engineering a broadened notion of existence that subsumes first-order and higher-order existence. After identifying a substantial problem for the ambitious project, I investigate a possible response which is based on adopting a cumulative type theory as the background higher-order logic. While effective against the problem at hand, this strategy turns out to undermine a major reason to embrace higher-orderism in the first place, namely the idea that higher-orderism dissolves a range of otherwise intractable debates in metaphysics. Higher-orderists are therefore best advised to pursue their engineering project on the modest variant and against the background of standard type theory. [ABSTRACT FROM AUTHOR]