The article investigates a system of polymorphically typed combinatory logic which is equivalent to Gödel’s T. A notion of (strong) reduction is defined over terms of this system and it is proved that the class of well-formed terms is closed under both bracket abstraction and reduction. The main new result is that the number of contractions needed to reduce a term to normal form is computed by an ε0-recursive function. The ordinal assignments used to obtain this result are also used (...) to prove that the system under consideration is indeed equivalent to Gödel’s T. It is hoped that the methods used here can be extended so as to obtain similar results for stronger systems of polymorphically typed combinatory terms. An interesting corollary of such results is that they yield ordinally informative proofs of normalizability for sub-systems of second-order intuitionist logic, in natural deduction style. (shrink)

We provide a full characterization of computational error states for information systems. The class of errors considered is general enough to include human rational processes, logical reasoning, scientific progress and data processing in some functional programming languages. The aim is to reach a full taxonomy of error states by analysing the recovery and processing of data. We conclude by presenting machine-readable checking and resolve algorithms.

The investigations on higher-order type theories and on the related notion of parametric polymorphism constitute the technical counterpart of the old foundational problem of the circularity of second and higher-order logic. However, the epistemological significance of such investigations has not received much attention in the contemporary foundational debate.We discuss Girard’s normalization proof for second order type theory or System F and compare it with two faulty consistency arguments: the one given by Frege for the logical system of the Grundgesetze and (...) the one given by Martin-Löf for the intuitionistic type theory with a type of all types.The comparison suggests that the question of the circularity of second order logic cannot be reduced to Russell’s and Poincaré’s 1906 “vicious circle” diagnosis. Rather, it reveals a bunch of mathematical and logical ideas hidden behind the hazardous idea of impredicative quantification, constituting a vast domain for foundational research. (shrink)

The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.

It has often been remarked that the metatheory of strong reduction $\succ$ , the combinatory analogue of βη-reduction ${\twoheadrightarrow_{\beta\eta}}$ in λ-calculus, is rather complicated. In particular, although the confluence of $\succ$ is an easy consequence of ${\twoheadrightarrow_{\beta\eta}}$ being confluent, no direct proof of this fact is known. Curry and Hindley’s problem, dating back to 1958, asks for a self-contained proof of the confluence of $\succ$ , one which makes no detour through λ-calculus. We answer positively to this question, by extending (...) and exploiting the technique of transitivity elimination for ‘analytic’ combinatory proof systems, which has been introduced in previous papers of ours. Indeed, a very short proof of the confluence of $\succ$ immediately follows from the main result of the present paper, namely that a certain analytic proof system G e [ $\mathbb {C}$ ] , which is equivalent to the standard proof system CL ext of Combinatory Logic with extensionality, admits effective transitivity elimination. In turn, the proof of transitivity elimination—which, by the way, we are able to provide not only for G e [ $\mathbb {C}$ ] but also, in full generality, for arbitrary analytic combinatory systems with extensionality—employs purely proof-theoretical techniques, and is entirely contained within the theory of combinators. (shrink)

In classical logic, a contradiction allows one to derive every other sentence of the underlying language; paraconsistent logics came relatively recently to subvert this explosive principle, by allowing for the subsistence of contradictory yet non-trivial theories. Therefore our surprise to find Wittgenstein, already at the 1930s, in comments and lectures delivered on the foundations of mathematics, as well as in other writings, counseling a certain tolerance on what concerns the presence of contradictions in a mathematical system. ‘Contradiction. Why just this (...) spectre? This is really very suspicious.’ ( Philosophical Remarks III–56) In the last decades, several authors (e.g. Arrington, Hintikka, Van Heijenoort, Wright, Wrigley) have been digging into Wittgenstein’s rather non-standard standpoint on what concerns the interpretation and import of contradiction in logic and mathematics, and many other authors (e.g. da Costa, Goldstein, Granger, Marconi) have been investigating the possibility of taking Wittgenstein seriously as one of the early forerunners of paraconsistency. While many advances have been made on the first front, the second set of investigations has led almost exclusively to negative results: no, no operational proposal about the construction of a logic in which (some) contradictions are made inoffensive can be read from Wittgenstein’s philosophical work; in fact, it appears that the most one can find there is the exhortation for mathematicians to alter their attitude with respect to contradictions and to consistency proofs. The play is done, and one looks for a resume of the opera. This paper fills that blank, as a thorough investigation of the possible relations between Wittgenstein and paraconsistency. DOI:10.5007/1808-1711.2010v14n1p135. (shrink)

Questions of definedness are ubiquitous in mathematics. Informally, these involve reasoning about expressions which may or may not have a value. This paper surveys work on logics in which such reasoning can be carried out directly, especially in computational contexts. It begins with a general logic of partial terms, continues with partial combinatory and lambda calculi, and concludes with an expressively rich theory of partial functions and polymorphic types, where termination of functional programs can be established in a natural way.

We constructively prove completeness for intuitionistic first-order logic, iFOL, showing that a formula is provable in iFOL if and only if it is uniformly valid in intuitionistic evidence semantics as defined in intuitionistic type theory extended with an intersection operator.Our completeness proof provides an effective procedure that converts any uniform evidence into a formal iFOL proof. Uniform evidence can involve arbitrary concepts from type theory such as ordinals, topological structures, algebras and so forth. We have implemented that procedure in the (...) Nuprl proof assistant.Our result demonstrates the value of uniform validity as a semantic notion for studying logical theories, and it provides new techniques for showing that formulas are not intuitionistically provable. Here we demonstrate its value for minimal and intuitionistic first-order logic. (shrink)

We expose some basic elements of a style of programming supported by functional languages like Haskell by relating them to a coherent set of notions and techniques from Curry’s work in combinatory logic and formal systems, and their algebraic and categorical interpretations. Our account takes the form of a commentary to a simple fragment of Haskell code attempting to isolate the conceptual sources of the linguistic abstractions involved.

In the early thirties, Church developed predicate calculus within a system based on lambda calculus. Rosser and Kleene developed Arithmetic within this system, but using a Godelization technique showed the system to be inconsistent.Alternative systems to that of Church have been developed, but so far more complex definitions of the natural numbers have had to be used. The present paper based on a system of illative combinatory logic developed previously by the author, does allow the use of the Church numerals. (...) Given a new definition of equality all the Peano-type axioms of Mendelson except one can be derived. A rather weak extra axiom allows the proof of the remaining Peano axiom. Note. The illative combinatory logic used in this paper is similar to the logic employed in computer languages such as ML. (shrink)

The implicational fragment of the relevance logic "ticket entailment" is closely related to the so-called hereditary right maximal terms. I prove that the terms that need to be considered as inhabitants of the types which are theorems of $T_\rightarrow$ are in normal form and built in all but one casefrom B, B' and W only. As a tool in the proof ordered term rewriting systems are introduced. Based on the main theorem I define $FIT_\rightarrow$ - a Fitch-style calculus (related to (...) $FT_\rightarrow$ ) for the implicational fragment of ticket entailment. (shrink)

The implicational fragment of the relevance logic "ticket entailment" is closely related to the so-called hereditary right maximal terms. I prove that the terms that need to be considered as inhabitants of the types which are theorems of $T_\rightarrow$ are in normal form and built in all but one casefrom B, B' and W only. As a tool in the proof ordered term rewriting systems are introduced. Based on the main theorem I define $FIT_\rightarrow$ - a Fitch-style calculus for the (...) implicational fragment of ticket entailment. (shrink)

The meaning of a formula built out of proof-functional connectives depends in an essential way upon the intensional aspect of the proofs of the component subformulas. We study three such connectives, strong equivalence (where the two directions of the equivalence are established by mutually inverse maps), strong conjunction (where the two components of the conjunction are established by the same proof) and relevant implication (where the implication is established by an identity map). For each of these connectives we give a (...) type assignment system, a realizability semantics, and a completeness theorem. This form of completeness implies the semantic completeness of the type assignment system. (shrink)

This paper introduces λ-grammar, a form of categorial grammar that has much in common with LFG. Like other forms of categorial grammar, λ-grammars are multi-dimensional and their components are combined in a strictly parallel fashion. Grammatical representations are combined with the help of linear combinators, closed pure λ-terms in which each abstractor binds exactly one variable. Mathematically this is equivalent to employing linear logic, in use in LFG for semantic composition, but the method seems more practicable.

My modest aim in this paper is to prove certain relations between some type of hyper-intensional operators, namely context shifting operators, and compositionality in natural languages. Various authors (e.g. von Fintel & Matthewson 2008; Stalnaker 2014) have argued that context-shifting operators are incompatible with compositionality. In fact, some of them understand Kaplan’s (1989) famous ban on context-shifting operators as a constraint on compositionality. Others, (e.g. Rabern 2013) take contextshifting operators to be compatible with compositionality but, unfortunately, do not provide a (...) proof, or an argument in favor of their position. The aim of this paper is to do precisely that. Additionally, I provide a new proof that compositionality for propositional content (intension) is a proper generalization of compositionality for character (hyper-intensions). (shrink)