Order-Sorted Intensional Logic: Expressing Subtyping Polymorphism with Typing Assertions and Quantification over Concepts

Đorđe Marković Marc Denecker · 2025

Read Order-Sorted Intensional Logic: Expressing Subtyping Polymorphism with Typing Assertions and Quantification over Concepts by Đorđe Marković Marc Denecker (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09224.txt.

Introduction

Marković and Denecker propose an extension of order-sorted logic in a 2025 paper. Subtyping lets programs built for a general type work safely with subtypes. The authors ask how knowledge representation can use the same idea.

They note two limits in order-sorted logic. It cannot speak about a concept itself rather than its values, and it lacks tools to constrain the type of a term. Their answer is guarded order-sorted intensional logic. Guards carry typing notes on terms, while the intensional part allows quantification over concepts. The paper sets out the new logic and its aims. It bridges programming language ideas and formal knowledge systems.

Catalog record

CREATORĐorđe Marković Marc Denecker
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09224

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Order-Sorted Intensional Logic: Expressing Subtyping Polymorphism with Typing Assertions and Quantification over Concepts Thanks: This work was partially supported by the Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen”. Affiliation: KU Leuven, Department of computer science, Leuven, Belgium Đorđe Marković Marc Denecker Abstract Subtyping, also known as subtype polymorphism, is a concept extensively studied in programming language theory, delineating the substitutability relation among datatypes. This property ensures that programs designed for supertype objects remain compatible with their subtypes. In this paper, we explore the capability of order-sorted logic for utilizing these ideas in the context of Knowledge Representation. We recognize two fundamental limitations: First, the inability of this logic to address the concept rather than the value of non-logical symbols, and second, the lack of language constructs for constraining the type of terms. Consequently, we propose guarded order-sorted intensional logic, where guards are language constructs for annotating typing information and intensional logic provides support for quantification over concepts. 1 Introduction The logic-based approach to knowledge representation (KR) dates back to the early ages of artificial intelligence. From the inception of this approach, limitations of untyped logic were identified. These issues led to the use of many-sorted logic [ 11 ] , and order-sorted logic ( OSL ) [ 2 ] . In many-sorted logic , the domain of discourse (or universe) is partitioned into different sorts/types, all disjoint. The latter assumption is lifted in order-sorted logic , and sorts/types can be organized in a hierarchy by inclusion. When extending first-order logic with ordered sorts, the concept of subtyping polymorphism emerges [ 9 , Chapter 15] . A prime example of this concept is the modeling of characteristic behaviors among different animals. Dogs bark, cats meow, etc., while nearly all animals produce species-specific sounds. In this scenario, animal serves as the overarching type, with specific animal types acting as subtypes. In many programming languages, one can invoke a method such as produce sound for an animal, which dynamically dispatches behavior based on the specific species of the animal. Logic is characterized by model semantics, and hence, it lacks the notion of method invocation found in programming languages. Nonetheless, logical statements can draw inspiration from this concept. For instance, consider the statement: “There is an animal in my yard that is either barking or meowing” . Considering that barking and meowing are predicates defined respectively on types dog and cat which are subtypes of the type animal , expressing such statements in OSL may easily lead to untyped formulae, as we shall see later. In this paper, we explore the principles underlying subtyping polymorphism and highlight challenges in its representation within order-sorted first-order logic. Additionally, we identify the two key principles essential for naturally expressing such concepts in any logic employing order-sorts. The first principle relates to the inherent incapacity of standard OSL to condition the subtyping relation of a term. For instance, given a variable x ranging over type animal , it is impossible 1 1 1 Here we strictly talk about the incapability to constrain the subtype of a variable, and not about possible alternative modelings that would circumvent this issue by changing the ontology. to express “if x is of type dog then x is barking” . Furthermore, we show that making such typing assertions implicit (annotated) is essential for subtyping. Whereby, annotating aims to implicitly constrain the type of a variable to the type of the argument it occurs at, given that the type of the variable is a supertype of the argument. For example, a language can be extended such that the statement “ \langle\langle x is barking \rangle\rangle ” stands for “if x is of type dog then x is barking” . This is possible because predicate barking caries the typing information that an argument of type dog is expected. The second principle tackles the constraint of first-order logic to solely address the values (extensions) of non-logical symbols rather than the concepts (intensions) interpreting them and the constraint to quantify over these concepts. Principles of intensional logic ( [ 5 ] ) become crucial in overcoming these limitations. We demonstrate that by combining order-sorted logic with principles of intensional logic and introducing the innovative principle of implicit type conditions, we establish a novel language suitable for expressing subtyping polymorphism. The remainder of the paper is structured as follows: ( 2 ) Order-sorted logic preliminaries; ( 3 ) Analysis of subtyping polymorphism from the logic perspective; ( 4 ) Introduction of guarded and ( 5 ) intensional OSL ; ( 6 ) Presentation of results: Guarded order-sorted intensional logic; ( 7 ) Discussion on well-typedness in order-sorted intensional logic; ( 8 ) Semantics of the language; ( 9 ) Discussion of related work; ( 10 ) Conclusion. 2 Preliminaries – Order-sorted Logic This section formally defines order-sorted logic . We start with the notion of a vocabulary. Definition 1 . An OSL vocabulary \Sigma of non-logical symbols is a quadruple ( T_{\Sigma} , S_{\Sigma} , <:_{\Sigma} , ts_{\Sigma} ) where: • T_{\Sigma} is a set of type symbols \mathbb{T} . Type symbols \mathbb{U} (universe), \mathbb{B} (boolean), and {\rm Nature} (natural numbers) are always member of T_{\Sigma} . • S_{\Sigma} is a set of function and predicate symbols. • <:_{\Sigma} is a subtyping relation on T_{\Sigma} . Type \mathbb{S} is a direct subtype of \mathbb{T} if \mathbb{S}<:_{\Sigma}\mathbb{T} . For each type \mathbb{T} (except \mathbb{U} ) without direct supertype declaration \mathbb{T}<:_{\Sigma}\mathbb{S} , we implicitly assume \mathbb{T}<:_{\Sigma}\mathbb{U} . Accordingly, \mathbb{B}<:_{\Sigma}\mathbb{U} and {\rm Nature}<:_{\Sigma}\mathbb{U} . • ts_{\Sigma} is a type signature associating to every symbol in S_{\Sigma} a word of the following format (\mathbb{T}_{1}\times\dots\times\mathbb{T}_{n})\rightarrow\mathbb{T} (i.e., type term). If \mathbb{T}=\mathbb{B} , the symbol is a predicate symbol, otherwise it is a function symbol. The sets of predicate and function symbols are denoted with S_{\Sigma}^{p} , respectively S_{\Sigma}^{f} . Type \mathbb{T}_{1} is called a subtype of \mathbb{T}_{2} if there is a path from \mathbb{T}_{1} to \mathbb{T}_{2} in the relation <:_{\Sigma} . Proposition 1 . Given vocabulary \Sigma , every type \mathbb{T} in T_{\Sigma} (except \mathbb{U} ) is subtype of \mathbb{U} . Proof. Follows directly from Definition 1 . ∎ A symbol with type term ()\rightarrow\mathbb{T} is an object (or a constant function) symbol. A symbol with type term ()\rightarrow\mathbb{B} is a propositional symbol. Example 1 . The following vocabulary declares: types \mathbb{A}nimal (Animal), \mathbb{C}at (Cat), and \mathbb{D}og (Dog), where cat and dog are subtypes of animal; function \mathit{age} mapping animals to natural numbers; constant \mathit{tom} of type cat; and two predicates \mathit{bark} and \mathit{meow} denoting sets of dogs and cats respectively. \displaystyle\mathrm{type}\ \mathbb{A}nimal\qquad\mathrm{type}\ \mathbb{C}at<:\mathbb{A}nimal\qquad\mathrm{type}\ \mathbb{D}og<:\mathbb{A}nimal \displaystyle\mathit{age}:\mathbb{A}nimal\rightarrow{\rm Nature}\qquad\mathit{tom}:()\rightarrow\mathbb{C}at\qquad\mathit{bark}:\mathbb{D}og\rightarrow\mathbb{B}\qquad\mathit{meow}:\mathbb{C}at\rightarrow\mathbb{B} The following defines OSL terms, formulae, expressions, and sentences. Definition 2 . Given an infinite set X of variable symbols and OSL vocabulary \Sigma , an OSL term ( \tau ) and formula ( \phi ) over X and \Sigma are defined inductively (using BNF): • A term is a variable or a function term: ¡ \tau ¿ ::= ¡ x ¿ \mid ¡ f ¿(¡ \tau ¿,…, ¡ \tau ¿) where x\in X,f\in S_{\Sigma}^{f} • A formula is true or false, an atomic formula, a negation, a disjunction, or an existential quantification: ¡ \phi ¿ ::= true \mid false \mid ¡ p ¿(¡ \tau

Read the complete text