The Experts below are selected from a list of 2774037 Experts worldwide ranked by ideXlab platform
Christoph Benzmüller - One of the best experts on this subject based on the ideXlab platform.
-
higher order semantics and Extensionality
Journal of Symbolic Logic, 2004Co-Authors: Christoph Benzmüller, Chad E Brown, Michael KohlhaseAbstract:In this paper we re-examine the semantics of classical higher-order logic with the purpose of clarifying the role of Extensionality. To reach this goal, we distinguish nine classes of higher-order models with respect to various combinations of Boolean Extensionality and three forms of functional Extensionality. Furthermore, we develop a methodology of abstract consistency methods (by providing the necessary model existence theorems) needed to analyze completeness of (machine-oriented) higher-order calculi with respect to these model classes.
-
Comparing Approaches To Resolution Based Higher-Order Theorem Proving
Synthese, 2002Co-Authors: Christoph BenzmüllerAbstract:We investigate several approaches to resolution based automated theoremproving in classical higher-order logic (based on Church's simply typedλ-calculus) and discuss their requirements with respect to Henkincompleteness and full Extensionality. In particular we focus on Andrews' higher-order resolution (Andrews 1971), Huet's constrained resolution (Huet1972), higher-order E-resolution, and extensional higher-order resolution(Benzmüller and Kohlhase 1997). With the help of examples we illustratethe parallels and differences of the Extensionality treatment of these approachesand demonstrate that extensional higher-order resolution is the sole approach thatcan completely avoid additional Extensionality axioms.
-
CADE - Extensional Higher-Order Paramodulation and RUE-Resolution
Automated Deduction — CADE-16, 1999Co-Authors: Christoph BenzmüllerAbstract:This paper presents two approaches to primitive equality treatment in higher-order (HO) automated theorem proving: a calculus EP adapting traditional first-order (FO) paramodulation [RW69], and a calculus ERUE adapting FO RUE-Resolution [Dig79] to classical type theory, i.e., HO logic based on Church's simply typed λ-calculus. EP and ERUE extend the extensional HO resolution approach ER [BK98a]. In order to reach Henkin completeness without the need for additional Extensionality axioms both calculi employ new, positive Extensionality rules analogously to the respective negative ones provided by ER that operate on unification constraints. As the Extensionality rules have an intrinsic and unavoidable difference-reducing character the HO paramodulation approach loses its pure term-rewriting character. On the other hand examples demonstrate that the Extensionality rules harmonise quite well with the difference-reducing HO RUE-resolution idea.
-
Extensional higher-order paramodulation and RUE-Resolution
Lecture Notes in Computer Science, 1999Co-Authors: Christoph BenzmüllerAbstract:This paper presents two approaches to primitive equality treatment in higher-order (HO) automated theorem proving: a calculus eP adapting traditional first-order (FO) paramodulation [RW69], and a calculus eRUe adapting FO RUE-Resolution [Dig79] to classical type theory, i.e., HO logic based on Church's simply typed λ-calculus. eP and eRUe extend the extensional HO resolution approach eR [BK98a]. In order to reach Henkin completeness without the need for additional Extensionality axioms both calculi employ new, positive Extensionality rules analogously to the respective negative ones provided by eR that operate on unification constraints. As the Extensionality rules have an intrinsic and unavoidable difference-reducing character the HO paramodulation approach loses its pure term-rewriting character. On the other hand examples demonstrate that the Extensionality rules harmonise quite well with the difference-reducing HO RUE-resolution idea.
-
system description leo a higher order theorem prover
Conference on Automated Deduction, 1998Co-Authors: Christoph Benzmüller, Michael KohlhaseAbstract:Many (mathematical) problems, such as Cantor’s theorem, can be expressed very elegantly in higher-order logic, but lead to an exhaustive and un-intuitive formulation when coded in first-order logic. Thus, despite the difficulty of higher-order automated theorem proving, which has to deal with problems like the undecidability of higher-order unification (HOU) and the need for primitive substitution, there are proof problems which lie beyond the capabilities of first-order theorem provers, but instead can be solved easily by an higher-order theorem prover (HOATP) like Leo .T his is due to the expressiveness of higher-order Logic and, in the special case of Leo, due to an appropriate handling of the Extensionality principles (functional Extensionality and Extensionality on truth values). Leo uses a higher-order Logic based upon Church’s simply typed λ-calculus, so that the comprehension axioms are implicitly handled by αβη-equality. Leo employs a higher-order resolution calculus ERES (see [3] in this volume for details), where the search for empty clauses and higher-order pre-unification [6] are interleaved: the unifiability preconditions of the resolution and factoring rules are residuated as special negative equality literals that are treated by special unification rules. In contrast to other HOATP’s (such as Tps [1]) Extensionality principles are build in into Leo’s unification, and hence do not have to be axiomatized in order to achieve Henkin completeness. Architecture
Michael Kohlhase - One of the best experts on this subject based on the ideXlab platform.
-
higher order semantics and Extensionality
Journal of Symbolic Logic, 2004Co-Authors: Christoph Benzmüller, Chad E Brown, Michael KohlhaseAbstract:In this paper we re-examine the semantics of classical higher-order logic with the purpose of clarifying the role of Extensionality. To reach this goal, we distinguish nine classes of higher-order models with respect to various combinations of Boolean Extensionality and three forms of functional Extensionality. Furthermore, we develop a methodology of abstract consistency methods (by providing the necessary model existence theorems) needed to analyze completeness of (machine-oriented) higher-order calculi with respect to these model classes.
-
system description leo a higher order theorem prover
Conference on Automated Deduction, 1998Co-Authors: Christoph Benzmüller, Michael KohlhaseAbstract:Many (mathematical) problems, such as Cantor’s theorem, can be expressed very elegantly in higher-order logic, but lead to an exhaustive and un-intuitive formulation when coded in first-order logic. Thus, despite the difficulty of higher-order automated theorem proving, which has to deal with problems like the undecidability of higher-order unification (HOU) and the need for primitive substitution, there are proof problems which lie beyond the capabilities of first-order theorem provers, but instead can be solved easily by an higher-order theorem prover (HOATP) like Leo .T his is due to the expressiveness of higher-order Logic and, in the special case of Leo, due to an appropriate handling of the Extensionality principles (functional Extensionality and Extensionality on truth values). Leo uses a higher-order Logic based upon Church’s simply typed λ-calculus, so that the comprehension axioms are implicitly handled by αβη-equality. Leo employs a higher-order resolution calculus ERES (see [3] in this volume for details), where the search for empty clauses and higher-order pre-unification [6] are interleaved: the unifiability preconditions of the resolution and factoring rules are residuated as special negative equality literals that are treated by special unification rules. In contrast to other HOATP’s (such as Tps [1]) Extensionality principles are build in into Leo’s unification, and hence do not have to be axiomatized in order to achieve Henkin completeness. Architecture
Ioanna Symeonidou - One of the best experts on this subject based on the ideXlab platform.
-
IJCAI - The Intricacies of Three-Valued Extensional Semantics for Higher-Order Logic Programs
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018Co-Authors: Panos Rondogiannis, Ioanna SymeonidouAbstract:In this paper we examine the problem of providing a purely extensional three-valued semantics for higher-order logic programs with negation. We demonstrate that a technique that was proposed by M. Bezem for providing extensional semantics to positive higher-order logic programs, fails when applied to higher-order logic programs with negation. On the positive side, we demonstrate that for stratified higher-order logic programs, Extensionality is indeed achieved by the technique. We analyze the reasons of the failure of Extensionality in the general case, arguing that a three-valued setting can not distinguish between certain predicates that appear to have a different behaviour inside a program context, but which happen to be identical as three-valued relations.
-
The intricacies of three-valued extensional semantics for higher-order logic programs
Theory and Practice of Logic Programming, 2017Co-Authors: Panos Rondogiannis, Ioanna SymeonidouAbstract:AbstractM. Bezem defined an extensional semantics for positive higher-order logic programs. Recently, it was demonstrated by Rondogiannis and Symeonidou that Bezem's technique can be extended to higher-order logic programs with negation, retaining its extensional properties, provided that it is interpreted under a logic with an infinite number of truth values. Rondogiannis and Symeonidou also demonstrated that Bezem's technique, when extended under the stable model semantics, does not in general lead to extensional stable models. In this paper, we consider the problem of extending Bezem's technique under the well-founded semantics. We demonstrate that the well-founded extensionfailsto retain Extensionality in the general case. On the positive side, we demonstrate that for stratified higher-order logic programs, Extensionality is indeed achieved. We analyze the reasons of the failure of Extensionality in the general case, arguing that a three-valued setting cannot distinguish between certain predicates that appear to have a different behaviour inside a program context, but which happen to be identical as three-valued relations.
-
The Intricacies of 3-Valued Extensional Semantics for Higher-Order Logic Programs
arXiv: Programming Languages, 2017Co-Authors: Panos Rondogiannis, Ioanna SymeonidouAbstract:In (Bezem 1999; Bezem 2001), M. Bezem defined an extensional semantics for positive higher-order logic programs. Recently, it was demonstrated in (Rondogiannis and Symeonidou 2016) that Bezem's technique can be extended to higher-order logic programs with negation, retaining its extensional properties, provided that it is interpreted under a logic with an infinite number of truth values. In (Rondogiannis and Symeonidou 2017) it was also demonstrated that Bezem's technique, when extended under the stable model semantics, does not in general lead to extensional stable models. In this paper we consider the problem of extending Bezem's technique under the well-founded semantics. We demonstrate that the well-founded extension fails to retain Extensionality in the general case. On the positive side, we demonstrate that for stratified higher-order logic programs, Extensionality is indeed achieved. We analyze the reasons of the failure of Extensionality in the general case, arguing that a three-valued setting can not distinguish between certain predicates that appear to have a different behaviour inside a program context, but which happen to be identical as three-valued relations. The paper is under consideration for acceptance in TPLP.
Hiroyuki Inaoka - One of the best experts on this subject based on the ideXlab platform.
-
On Evans's Vague Object from Set Theoretic Viewpoint
Journal of Philosophical Logic, 2006Co-Authors: Shunsuke Yatabe, Hiroyuki InaokaAbstract:Gareth Evans proved that if two objects are indeterminately equal then they are different in reality. He insisted that this contradicts the assumption that there can be vague objects. However we show the consistency between Evans's proof and the existence of vague objects within classical logic. We formalize Evans's proof in a set theory without the axiom of Extensionality, and we define a set to be vague if it violates Extensionality with respect to some other set. There exist models of set theory where the axiom of Extensionality does not hold, so this shows that there can be vague objects.
-
vagueness and Extensionality
Fuzzy Systems and Knowledge Discovery, 2005Co-Authors: Shunsuke Yatabe, Hiroyuki InaokaAbstract:We introduce a property of set to represent vagueness without using truth value. It has gotten less attention in fuzzy set theory. We introduce it by analyzing a well-known philosophical argument by Gearth Evans. To interpret ‘a is a vague object' as ‘the Axiom of Extensionality is violated for a' allows us to represent a vague object in Evans's sense, even within classical logic, and of course within fuzzy logic.
Aaron Cotnoir - One of the best experts on this subject based on the ideXlab platform.
-
Strange Parts: The Metaphysics of Non‐classical Mereologies
Philosophy Compass, 2013Co-Authors: Aaron CotnoirAbstract:The dominant theory of parts and wholes – classical extensional mereology – has faced a number of challenges in the recent literature. This article gives a sampling of some of the alleged counterexamples to some of the more controversial principles involving the connections between parthood and identity. Along the way, some of the main revisionary approaches are reviewed. First, counterexamples to Extensionality are reviewed. The ‘supplementation’ axioms that generate Extensionality are examined more carefully, and a suggested revision is considered. Second, the paper considers an alternative approach that focuses the blame on antisymmetry but allows us to keep natural supplementation axioms. Third, we look at counterexamples to the idempotency of composition and the associated ‘parts just once’ principle. We explore options for developing weaker mereologies that avoid such commitments.
-
non wellfounded mereology
Review of Symbolic Logic, 2012Co-Authors: Aaron Cotnoir, Andrew BaconAbstract:This paper is a systematic exploration of non-wellfounded mereology. Motivations and applications suggested in the literature are considered. Some are exotic like Borges' ALEPH, and the TRINITY; other examples are less so, like TIME TRAVELING BRICKS, and even Geach's TIBBLES THE CAT. The authors point out that the transitivity of non-wellfounded parthood is inconsistent with Extensionality. A non-wellfounded mereology is developed with careful consideration paid to rival notions of supplementation and fusion. Two equivalent axiomatizations are given, and are compared to classical mereology. We provide a class of models with respect to which the non-wellfounded mereology is sound and complete. This paper explores the prospects of non-wellfounded mereology. An order < (in this case proper parthood) on a domain is said to be wellfounded if every nonempty subset of that domain has a <-minimal element. We say that x is a <-minimal element of a set S if there is no y in S such that y < x. Wellfoundedness rules out any infinite descending <-chains. There are atomless mereologies, sometimes called gunky, in which proper parthood chains are all infinite. 1 This is one interesting and important case of a non- wellfounded mereology. But notice, wellfoundedness also rules out structures in which for some x, x < x; likewise, it rules out cases in which there is some x and y such that x < y and y < x. That is, wellfoundedness rules out parthood loops. In this paper, we explore a non-wellfounded mereology that allows for both these sorts of parthood loops. In §1, we briefly survey some applications for non-wellfounded mereology that have been suggested in the literature. In §2, we consider difficulties with the classical definitions of parthood and proper parthood; we discuss Extensionality principles in mereology, and argue that Extensionality is inconsistent with the transitivity of parthood in certain non- wellfounded scenarios. In §3, we examine supplementation principles and rival notions of fusion for non-wellfounded mereology. §4 examines the relationship between classical mereology and non-wellfounded mereology. We show that the latter is a simple generaliza- tion of the former. Finally, we give a class of models for which non-wellfounded mereology is sound and complete in §5.
-
anti symmetry and non extensional mereology
The Philosophical Quarterly, 2010Co-Authors: Aaron CotnoirAbstract:I examine the link between Extensionality principles of classical mereology and the anti-symmetry of parthood. Varzi's most recent defence of Extensionality depends crucially on assuming anti-symmetry. I examine the notions of proper parthood, weak supplementation and non-well-foundedness. By rejecting anti-symmetry, the anti-extensionalist has a unified, independently grounded response to Varzi's arguments. I give a formal construction of a non-extensional mereology in which anti-symmetry fails. If the notion of ‘mereological equivalence’ is made explicit, this non-anti-symmetric mereology recaptures all of the structure of classical mereology.
-
Anti‐Symmetry and Non‐Extensional Mereology
The Philosophical Quarterly, 2010Co-Authors: Aaron CotnoirAbstract:I examine the link between Extensionality principles of classical mereology and the anti-symmetry of parthood. Varzi's most recent defence of Extensionality depends crucially on assuming anti-symmetry. I examine the notions of proper parthood, weak supplementation and non-well-foundedness. By rejecting anti-symmetry, the anti-extensionalist has a unified, independently grounded response to Varzi's arguments. I give a formal construction of a non-extensional mereology in which anti-symmetry fails. If the notion of ‘mereological equivalence’ is made explicit, this non-anti-symmetric mereology recaptures all of the structure of classical mereology.
