Search

The aim of this paper is to define a partial Propositional Type Theory. Our system is partial in a double sense: the hierarchy of (propositional) types contains partial functions and some expressions of the language, including formulas, may be undefined. The specific interpretation we give to the undefined value is that of Kleene's strong logic of indeterminacy. We present a semantics for the new system and prove that every element of any domain of the hierarchy has a name in the object language. Finally, we provide a proof system and a (constructive) proof of completeness. [ABSTRACT FROM AUTHOR]

Although the Linux kernel is widely used, its complexity makes errors common and potentially serious. Traditional formal verification methods often have high overhead and rely heavily on manual coding. They typically verify only specific functionalities of the kernel or target microkernels and do not support continuous verification of the entire kernel. To address these limitations, we introduce LMVM (Linux Kernel Modeling and Verification Method), a formal method based on type theory that ensures the correct design of the Linux architecture. In the model, the kernel is treated as a top-level type, subdivided into the following sublevels: subsystem, dentry, file, struct, function, and base. These types are defined in the structure and relationships. The verification process includes checking the design specifications for both type relationships and the presence of each type. Our contribution lies primarily in the following two points: 1. This is a lightweight verification. As long as the modeling is complete, architectural errors in the design phase can be identified promptly. 2. The designed "model refactor" module supports kernel updating, and the kernel can be continuously verified by extending the kernel model. To test its usefulness, we develop a set of security communication mechanisms in the kernel, which are verified using our method. [ABSTRACT FROM AUTHOR]

Based on Kolchinsky and Wolpert's work on the semantics of autonomous agents, I propose an application of Mathematical Logic and Probability to model cognitive processes. In this work, I will follow Bateson's insights on the hierarchy of learning in complex organisms and formalize his idea of applying Russell's Type Theory. Following Weaver's three levels for the communication problem, I link the Kolchinsky–Wolpert model to Bateson's insights, and I reach a semantic and conceptual hierarchy in living systems as an explicative model of some adaptive constraints. Due to the generality of Kolchinsky and Wolpert's hypotheses, I highlight some fundamental gaps between the results in current Artificial Intelligence and the semantic structures in human beings. In light of the consequences of my model, I conclude the paper by proposing a general definition of knowledge in probabilistic terms, overturning de Finetti's Subjectivist Definition of Probability. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with the development of a general set theory using the single axiom version of Lesniewski's mereology. The specification of mereology, and further of Tarski's geometry of solids will rely on the Calculus of Inductive Constructions (CIC). In the first, part we provide a specification of Lesniewski's mereology as a model for an atomless Boolean algebra using Clay's ideas. In the second part, we interpret Lesniewski's mereology in monadic second-order logic using names and develop a full version of mereology referred to as CIC-based Monadic Mereology (λ-MM) allowing an expressive theory while involving only two axioms. In the third part, we propose a modeling of Tarski's geometry of solids relying on λ-MM. It is intended to serve as a basis for spatial reasoning. All parts have been proved using a translation in type theory. [ABSTRACT FROM AUTHOR]

Constructed Past Theory (CPT) is an abstract representation of how information about the past is produced and interpreted. It is grounded in the assertion that whatever we can write or say about anything in the past is the product of cognition. Understanding how information about the past is produced requires the identification and analysis of both the sources on which that information is based and the way in which the constructor approaches the task to select, analyze, and organize information to achieve the purpose for which the information was sought. CPT models this dual process, providing a basis for evaluation. It is descriptive, not prescriptive. CPT has been articulated using UML class diagrams with the objective of facilitating implementation in automated systems. This article reformulates CPT using type theory and extends its reach by applying and adapting concepts from semiotics. The results are more detailed models that facilitate differentiating what things meant to people in the past from how the constructor understands them. This article concludes with suggestions for applying CPG concepts in constructing information about the past and identifying areas where further research is needed. [ABSTRACT FROM AUTHOR]

Although the Linux kernel is widely used, its complexity makes errors common and potentially serious. Traditional formal verification methods often have high overhead and rely heavily on manual coding. They typically verify only specific functionalities of the kernel or target microkernels and do not support continuous verification of the entire kernel. To address these limitations, we introduce LMVM (Linux Kernel Modeling and Verification Method), a formal method based on type theory that ensures the correct design of the Linux architecture. In the model, the kernel is treated as a top-level type, subdivided into the following sublevels: subsystem, dentry, file, struct, function, and base. These types are defined in the structure and relationships. The verification process includes checking the design specifications for both type relationships and the presence of each type. Our contribution lies primarily in the following two points: 1. This is a lightweight verification. As long as the modeling is complete, architectural errors in the design phase can be identified promptly. 2. The designed “model refactor” module supports kernel updating, and the kernel can be continuously verified by extending the kernel model. To test its usefulness, we develop a set of security communication mechanisms in the kernel, which are verified using our method.

Neil Tennant’s core logic is a type of bilateralist natural deduction system based on proofs and refutations. We present a proof system for propositional core logic, explain its connections to bilateralism, and explore the possibility of using it as a type theory, in the same kind of way intuitionistic logic is often used as a type theory. Our proof system is not Tennant’s own, but it is very closely related, and determines the same consequence relation. The difference, however, matters for our purposes, and we discuss this. We then turn to the question of strong normalization, showing that although Tennant’s proof system for core logic is not strongly normalizing, our modified system is.

Abstract It is often claimed that the theory of function levels proposed by Frege in Grundgesetze der Arithmetik anticipates the hierarchy of types that underlies Church’s simple theory of types. This claim roughly states that Frege presupposes a type of functions in the sense of simple type theory in the expository language of Grundgesetze. However, this view makes it hard to accommodate function names of two arguments and view functions as incomplete entities. I propose and defend an alternative interpretation of first-level function names in Grundgesetze into simple type-theoretic open terms rather than into closed terms of a function type. This interpretation offers a still unhistorical but more faithful type-theoretic approximation of Frege’s theory of levels and can be naturally extended to accommodate second-level functions. It is made possible by two key observations that Frege’s Roman markers behave essentially like open terms and that Frege lacks a clear criterion for distinguishing between Roman markers and function names.

Higher-order logic, with its type-theoretic apparatus known as the simple theory of types (STT), has increasingly come to be employed in theorising about properties, relations, and states of affairs – or ‘intensional entities’ for short. This paper argues against this employment of STT and offers an alternative: ordinal type theory (OTT). Very roughly, STT and OTT can be regarded as complementary simplifications of the ‘ramified theory of types’ outlined in the Introduction to Principia Mathematica (on a realist reading). While STT, understood as a theory of intensional entities, retains the Fregean division of properties and relations into a multiplicity of categories according to their adicities and ‘input types’ and discards the division of intensional entities into different ‘orders’, OTT takes the opposite approach: it retains the hierarchy of orders (though with some modifications) and discards the categorisation of properties and relations according to their adicities and input types. In contrast to STT, this latter approach avoids intensional counterparts of the Epimenides and related paradoxes. Fundamental intensional entities lie at the base of the proposed hierarchy and are also given a prominent part to play in the individuation of non-fundamental intensional entities. [ABSTRACT FROM AUTHOR]

As a celebration of the Tractatus 100th anniversary it might be worth revisiting its relation to the later writings. From the former to the latter, David Pears recalls that "everyone is aware of the holistic character of Wittgenstein's later philosophy, but it is not so well known that it was already beginning to establish itself in the Tractatus" (The False Prison, 1987). From the latter to the former, Stephen Hilmy's (The Later Wittgenstein, 1987) extensive study of the Nachlass has helped removing classical misconceptions such as Hintikka's claim that "Wittgenstein in the Philosophical Investigations almost completely gave up the calculus analogy." Hilmy points out that even in the Investigations one finds the use of the calculus/game paradigm to the understanding of language, such as "in operating with the word" (Part I, §559) and "it plays a different part in the calculus". Hilmy also quotes from a late (1946) unpublished manuscript (MS 130) "this sentence has use in the calculus of language", which seems to be compatible with "asking whether and how a proposition can be verified is only a particular way of asking 'How do you mean?'" Central in this back and forth there is an aspect which seems to deserve attention in the discussion of a semantics for the language of mathematics which might be based on (normalisation of) proofs and/or Hintikka/Lorenzen game-dialogue: the explication of consequences. Such a discussion is substantially supported by the use of the open and searchable The Wittgenstein Archives at the University of Bergen. These findings are framed within the discussion of the meaning of logical constants in the context of natural deduction style rules of inference. [ABSTRACT FROM AUTHOR]

Intuitively speaking, a multiple artwork is one that admits of multiple 'instances' which are capable of playing a particular role in the appreciation of the work. The 'explananda' in the title of this article are things that have been proposed as requiring explanation by any adequate ontology of multiple artworks so conceived. This assumes that the ontology of art is in the business of explaining certain things, an assumption I defend. At least nine purported explananda have been proposed in the relevant literature. I begin by offering a preliminary sketch of these explananda, identifying how they are grounded in our ordinary artistic practice and discourse, and how they have structured recent debates in the ontology of art. I next argue that the notion of 'instance' must be understood in a particular way if instance multiplicity is to capture the standard distinction between singular and multiple art forms. I then assess the relative significance and implications of the nine explananda for an adjudication of the debates in the ontology of art. I identify problems for the historically dominant 'type' theory of multiples, and propose an alternative account that speaks to all nine explananda. I conclude by reflecting on where this leaves us and how we should proceed. [ABSTRACT FROM AUTHOR]

In formal semantics based on modern type theories, some sentences may be interpreted as judgements and some as logical propositions. When interpreting composite sentences, one may want to turn a judgemental interpretation or an ill-typed semantic interpretation into a proposition in order to obtain an intended semantics. For instance, an incorrect judgement a : A may be turned into its propositional form I S (A , a) and an ill-typed application p(a) into D O (p , a) , so that the propositional forms can take part in logical compositions that interpret composite sentences, especially those that involve negations and conditionals.In this paper, we propose an operator not that facilitates such a transformation. Introducing not axiomatically, with five axiomatic laws to govern its behaviour, we shall use it to define I S and D O and give examples to illustrate its use in semantic interpretation. The introduction of not into type theories is logically consistent – this is justified by showing that not can be defined by means of the heterogeneous equality JMeq so that all of the axiomatic laws for not become provable. Therefore, since the extension with JMeq preserves logical consistency, so does the extension with not. We shall also study conditions under which I S and D O operators can be used safely without the risk of over-generation. [ABSTRACT FROM AUTHOR]

Neil Tennant's core logic is a type of bilateralist natural deduction system based on proofs and refutations. We present a proof system for propositional core logic, explain its connections to bilateralism, and explore the possibility of using it as a type theory, in the same kind of way intuitionistic logic is often used as a type theory. Our proof system is not Tennant's own, but it is very closely related. The difference matters for our purposes, and we discuss this. We then turn to the question of strong normalization, showing that although Tennant's proof system for core logic is not strongly normalizing, our modified system is. [ABSTRACT FROM AUTHOR]

Call a quantifier 'unrestricted' if it ranges over absolutely all objects. Arguably, unrestricted quantification is often presupposed in philosophical inquiry. However, developing a semantic theory that vindicates unrestricted quantification proves rather difficult, at least as long as we formulate our semantic theory within a classical first-order language. It has been argued that using a type theory as framework for our semantic theory provides a resolution of this problem, at least if a broadly Fregean interpretation of type theory is assumed. However, the intelligibility of this interpretation has been questioned. In this paper I introduce a type-free theory of properties that can also be used to vindicate unrestricted quantification. This alternative emerges very naturally by reflecting on the features on which the type-theoretic solution of the problem of unrestricted quantification relies. Although this alternative theory is formulated in a non-classical logic, it preserves the deductive strength of classical strict type theory in a natural way. The ideas developed in this paper make crucial use of Russell's notion of range of significance. [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 Russell–Myhill theorem threatens a familiar structured conception of propositions according to which two sentences express the same proposition only if they share the same syntactic structure and their corresponding syntactic constituents share the same semantic value. Given the role of the principle of universal instantiation in the derivation of the theorem in simple type theory, one may hope to rehabilitate the core of the structured view of propositions in ramified type theory, where the principle is systematically restricted. We suggest otherwise. The ramified core of the structured theory of propositions remains inconsistent in ramified type theory augmented with axioms of reducibility. This is significant because reducibility has been thought to be perfectly consistent with the ramified approach to the intensional antinomies. Nor is the addition of reducibility to ramified type theory sufficient to restore other intensional puzzles such as Prior's paradox or Kripke's puzzle about time and thought. [ABSTRACT FROM AUTHOR]

Transparent intensional logic (TIL) is a well-explored type-theoretical framework for semantics of natural language. However, its treatment of polymorphic functions, which are essential for the analysis of various natural language phenomena, is still underdeveloped. In this paper, we address this issue and propose an extension of TIL that introduces polymorphism via type variables ranging over types and generalized variables ranging over constructions and types. Furthermore, we offer an analysis of sentences involving non-specific notional attitudes of the general form 'A considers (believes, desires, wants, seeks,...) something'. [ABSTRACT FROM AUTHOR]

The video games industry has been growing constantly for the past several decades, but there is no empirically validated industry standard for measuring motivation of play. Although there have been a number of player typologies, they display sizable deviations in the player types described, many of which are insufficiently supported by validation studies. The literature thus far lacks an attempt to test these deviations by bringing differences in the specifics on the same scale. A survey (n = 1090) across 440 different games using an 80-item questionnaire found eleven motivations of play: Social, Social Competition, Challenge, Escapism, Role-Playing, Power Fantasy, Creation, Exploration, Completion, Griefing, and Competitive Team-Play. These results map onto some established types, add some new ones that are not as embedded in the literature, and re-contextualize others such as immersion which, while highly present in the literature, were not found to be distinct motivations of play. [ABSTRACT FROM AUTHOR]

Constructed Past Theory (CPT) is an abstract representation of how information about the past is produced and interpreted. It is grounded in the assertion that whatever we can write or say about anything in the past is the product of cognition. Understanding how information about the past is produced requires the identification and analysis of both the sources on which that information is based and the way in which the constructor approaches the task to select, analyze, and organize information to achieve the purpose for which the information was sought. CPT models this dual process, providing a basis for evaluation. It is descriptive, not prescriptive. CPT has been articulated using UML class diagrams with the objective of facilitating implementation in automated systems. This article reformulates CPT using type theory and extends its reach by applying and adapting concepts from semiotics. The results are more detailed models that facilitate differentiating what things meant to people in the past from how the constructor understands them. This article concludes with suggestions for applying CPG concepts in constructing information about the past and identifying areas where further research is needed.

Powerful yet effective induction principles play an important role in computing, being a paramount component of programming languages, automated reasoning, and program verification systems. The Bar Induction (BI) principle is a fundamental concept of intuitionism, which is equivalent to the standard principle of transfinite induction. In this work, we investigate the compatibility of several variants of BI with Constructive Type Theory (CTT), a dependent type theory in the spirit of Martin-Löf's extensional theory. We first show that CTT is compatible with a BI principle for sequences of numbers. Then, we establish the compatibility of CTT with a more general BI principle for sequences of name-free closed terms. The formalization of the latter principle within the theory involved enriching CTT's term syntax with a limit constructor and showing that consistency is preserved. Furthermore, we provide novel insights regarding BI, such as the non-truncated version of BI on monotone bars being intuitionistically false. These enhancements are carried out formally using the Nuprl proof assistant that implements CTT and the formalization of CTT within the Coq proof assistant presented in previous works. [ABSTRACT FROM AUTHOR]

The λΠ-calculus modulo theory is a logical framework in which many type systems can be expressed as theories. We present such a theory, the theory U, where proofs of several logical systems can be expressed. Moreover, we identify a sub-theory of U corresponding to each of these systems, and prove that, when a proof in U uses only symbols of a sub-theory, then it is a proof in that sub-theory. [ABSTRACT FROM AUTHOR]

Werner's set-theoretical model is one of the simplest models of CIC. It combines a functional view of predicative universes with a collapsed view of the impredicative sort " ${\tt Prop}$ ". However, this model of ${\tt Prop}$ is so coarse that the principle of excluded middle $P \lor \neg P$ holds. Following our previous work, we interpret ${\tt Prop}$ into a topological space (a special case of Heyting algebra) to make the model more intuitionistic without sacrificing simplicity. We improve on that work by providing a full interpretation of dependent product types, using Alexandroff spaces. We also extend our approach to inductive types by adding support for ${\mathsf{list}}$ s. [ABSTRACT FROM AUTHOR]

Let F be a non-Archimedean local field, A be a central simple F -algebra, and G be the multiplicative group of A. It is known that for every irreducible supercuspidal representation π , there exists a [ G , π ] G -type (J , λ) , called a (maximal) simple type. We will show that [ G , π ] G -types defined over some maximal compact subgroup are unique up to G -conjugations under some unramifiedness assumption on a simple stratum. [ABSTRACT FROM AUTHOR]

We describe the categorical semantics for a simply typed variant and a simplified dependently typed variant of Cocon, a contextual modal type theory where the box modality mediates between the weak function space that is used to represent higher-order abstract syntax (HOAS) trees and the strong function space that describes (recursive) computations about them. What makes Cocon different from standard type theories is the presence of first-class contexts and contextual objects to describe syntax trees that are closed with respect to a given context of assumptions. Following M. Hofmann’s work, we use a presheaf model to characterise HOAS trees. Surprisingly, this model already provides the necessary structure to also model Cocon. In particular, we can capture the contextual objects of Cocon using a comonad ♭ that restricts presheaves to their closed elements. This gives a simple semantic characterisation of the invariants of contextual types (e.g. substitution invariance) and identifies Cocon as a type-theoretic syntax of presheaf models. We further extend this characterisation to dependent types using categories with families and show that we can model a fragment of Cocon without recursor in the Fitch-style dependent modal type theory presented by Birkedal et al. [ABSTRACT FROM AUTHOR]

There is a plethora of semantics of computational models, nevertheless, the semantics of combinatory logic are among the less investigated ones. In this paper, we propose semantics for the computational system of combinatory logic with intersection types. We define extensional applicative structures endowed with special elements corresponding to primitive combinators. We prove two soundness and completeness results. First, the equational theory of untyped combinatory logic is proven to be sound and complete with respect to the proposed semantics. Second, the system of the combinatory logic with intersection types is proven to be sound and complete with respect to the proposed semantics. The usual approach to the semantics for calculi with types that can be found in the literature is based on models for the untyped calculus endowed with a valuation of type variables which enables the interpretation of types to be defined inductively. We propose, however, a different approach. In the semantics we propose, the interpretation of types is represented as a family of subsets that satisfies certain properties, whereas for a given valuation of term variables, the interpretation of terms is defined inductively. Due to the wide applicability of semantics of computational models, the presented approach could be further developed to other computational models and beyond—to current and foreseen application of semantics to large distributed systems and new challenging technologies.

We present a cubical type theory based on the Cartesian cube category (faces, degeneracies, symmetries, diagonals, but no connections or reversal) with univalent universes, each containing Π, Σ, path, identity, natural number, boolean, suspension, and glue (equivalence extension) types. The type theory includes a syntactic description of a uniform Kan operation, along with judgmental equality rules defining the Kan operation on each type. The Kan operation uses both a different set of generating trivial cofibrations and a different set of generating cofibrations than the Cohen, Coquand, Huber, and Mörtberg (CCHM) model. Next, we describe a constructive model of this type theory in Cartesian cubical sets. We give a mechanized proof, using Agda as the internal language of cubical sets in the style introduced by Orton and Pitts, that glue, Π, Σ, path, identity, boolean, natural number, suspension types, and the universe itself are Kan in this model, and that the universe is univalent. An advantage of this formal approach is that our construction can also be interpreted in a range of other models, including cubical sets on the connections cube category and the De Morgan cube category, as used in the CCHM model, and bicubical sets, as used in directed type theory. [ABSTRACT FROM AUTHOR]