Philosophy Compass, Volume 17, Issue 2, February 2022.

Brouwer’s view on induction has relatively recently been characterised as one on which it is not only intuitive (as expected) but functional, by van Dalen. He claims that Brouwer’s ‘Ur-intuition’ also yields the recursor. Appealing to Husserl’s phenomenology, I offer an analysis of Brouwer’s view that supports this characterisation and claim, even if assigning the primary role to the iterator instead. Contrasts are drawn to accounts of induction by Poincaré, Heyting, and Kreisel. On the phenomenological side, the analysis provides an (...) alternative to that in Tieszen’s Mathematical Intuition, and confirms a view of Gödel on his Dialectica Interpretation. (shrink)

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 $$\textsc {is}(A,a)$$ and an ill-typed application p(a) into $$\textsc {do}(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 $$\textsc {is}$$ and $$\textsc {do}$$ 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 $$\textrm{JMeq}$$ so that all of the axiomatic laws for not become provable. Therefore, since the extension with $$\textrm{JMeq}$$ preserves logical consistency, so does the extension with not. We shall also study conditions under which $$\textsc {is}$$ and $$\textsc {do}$$ operators can be used safely without the risk of over-generation. (shrink)

This paper discusses six formalization techniques, of varying strengths, for extending a formal system based on traditional mathematical logic. The purpose of these formalization techniques is to simulate the introduction of new syntactic constructs, along with associated semantics for them. We show that certain techniques (among the six) subsume others. To illustrate sharpness, we also consider a selection of constructs and show which techniques can and cannot be used to introduce them. The six studied techniques were selected on the basis (...) of actual practice in logic and computing. They do not form an exhaustive list. (shrink)

In §93 of The Principles of Mathematics, Bertrand Russell observes that “the variable is a very complicated logical entity, by no means easy to analyze correctly”. This assessment is borne out by the fact that even now we have no fully satisfactory understanding of the role of variables in a compositional semantics for first-order logic. In standard Tarskian semantics, variables are treated as meaning-bearing entities; moreover, they serve as the basic building blocks of all meanings, which are constructed out of (...) variable assignments. But this has disquieting consequences, including Fine’s antinomy of the variable and an undue dependence of meanings on language. Here I develop an alternative, Fregean version of predicate logic that uses the traditional quantifier–variable apparatus for the expression of generality, possesses a fully compositional, non-representational semantics, and is not subject to the antinomy of the variable. The advantages of Fregean over Tarskian predicate logic are due to the former’s treating variables not as meaningful lexical items, but as mere marks of punctuation, similar to parentheses. I submit that this is indeed how the variables of predicate logic should be construed. (shrink)

Sections 1 through 4 define, in the usual inductive style, various classes of object including one which is called the “combinatory terms of polymorphic type”. Section 5 defines a reduction relation on these terms. Section 6 shows that the weak normalizability of the combinatory terms of polymorphic type entails the weak normalizability of the lambda terms of polymorphic type. The entailment is not vacuous, because the combinatory terms of polymorphic type are indeed weakly normalizable, as is proven in Sect. 7 (...) using Tait and Girard’s computability predicates. The remainder of the paper is devoted to arguing that interesting consequences would follow from the existence of an “ordinally informative” proof, i.e. one which uses transfinite induction over recursive ordinal numbers and otherwise finitary methods, of normalizability for as large a class of the terms as possible. (shrink)

The idea that natural language grammar and planned action are relatedsystems has been implicit in psychological theory for more than acentury. However, formal theories in the two domains have tendedto look very different. This article argues that both faculties sharethe formal character of applicative systems based on operationscorresponding to the same two combinatory operations, namely functional composition and type-raising. Viewing them in thisway suggests simpler and more cognitively plausible accounts of bothsystems, and suggests that the language faculty evolved in the (...) speciesand develops in children by a rather direct adaptation of a moreprimitive apparatus for planning purposive action in the world bycomposing affordances of objects or tools. Theknowledge representation that underlies such planning is alsoreflected in the natural language semantics of tense, mood, andaspect, which the paper begins by arguing provides the key tounderstanding both systems. (shrink)

In this note we present an axiomatization of the classical two-valued propositional calculus, for which proofs of decidability, consistency, completeness, and independence, are almost trivial (given an understanding of truth tables).

Machine awareness is a disputed research topic, in some circles considered a crucial step in realising Artificial General Intelligence. Understanding what that is, under which conditions such feature could arise and how it can be controlled is still a matter of speculation. A more concrete object of theoretical analysis is algorithmic iteration for computational intelligence, intended as the theoretical and practical ability of algorithms to design other algorithms for actions aimed at solving well-specified tasks. We know this ability is already (...) shown by current AIs, and understanding its limits is an essential step in qualifying claims about machine awareness and Super-AI. We propose a formal translation of algorithmic iteration in a fragment of modal logic, formulate principles of transparency and faithfulness across human and machine intelligence, and consider the relevance to theoretical research on -AI as well as the practical import of our results. (shrink)

The logic of identity contains riches not seen through the coarse lens of predicate logic. This is one of several lessons to draw from the subtle treatment of identity in Martin‐Löf type theory, to which the reader will be introduced in this article. After a brief general introduction we shall mainly be concerned with the distinction between identity propositions and identity judgements. These differ from each other both in logical form and in logical strength. Along the way, connections to philosophical (...) debates concerning identity are noted. Some use of logical symbolism is inevitable in any serious discussion of type theory, but the emphasis here is on basic ideas rather than technicalities. (shrink)

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric λ-calculus) is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinators has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes in both left and right associated terms. (...) Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property. (shrink)

We investigate the system TRC of untyped illative combinatory logic that is equiconsistent with New Foundations. We prove that various unstratified combinators do not exist in TRC.

Traditional combinatory logic uses combinators S and K to represent all Turing-computable functions on natural numbers, but there are Turing-computable functions on the combinators themselves that cannot be so represented, because they access internal structure in ways that S and K cannot. Much of this expressive power is captured by adding a factorisation combinator F. The resulting SF-calculus is structure complete, in that it supports all pattern-matching functions whose patterns are in normal form, including a function that decides structural equality (...) of arbitrary normal forms. A general characterisation of the structure complete, confluent combinatory calculi is given along with some examples. These are able to represent all their Turing-computable functions whose domain is limited to normal forms. The combinator F can be typed using an existential type to represent internal type information. (shrink)

Nominal logic is a variant of first-order logic in which abstract syntax with names and binding is formalized in terms of two basic operations: name-swapping and freshness. It relies on two important principles: equivariance (validity is preserved by name-swapping), and fresh name generation ("new" or fresh names can always be chosen). It is inspired by a particular class of models for abstract syntax trees involving names and binding, drawing on ideas from Fraenkel-Mostowski set theory: finite-support models in which each value (...) can depend on only finitely many names. Although nominal logic is sound with respect to such models, it is not complete. In this paper we review nominal logic and show why finite-support models are insufficient both in theory and practice. We then identify (up to isomorphism) the class of models with respect to which nominal logic is complete: ideal-supported models in which the supports of values are elements of a proper ideal on the set of names. We also investigate an appropriate generalization of Herbrand models to nominal logic. After adjusting the syntax of nominal logic to include constants denoting names, we generalize universal theories to nominal-universal theories and prove that each such theory has an Herbrand model. (shrink)

One of the basic results in the theory of λ-conversion is the Church-Rosser Theorem, which says that, using certain rules for conversion and reduction of λ-formulae, any two interconvertible formulae can both be reduced to one formula. (I will not explain this in detail, as λ-conversion is described fully in Church's [2], where the Church-Rosser Theorem is Theorem 7 XXVII; see also Chapter 4 of Curry and Feys' [3].) The first part of the present paper contains an abstract form of (...) this theorem. (shrink)

In 1960, E. P. Wigner, a joint winner of the 1963 Nobel Prize for Physics, published a paper titled On the Unreasonable Effectiveness of Mathematics in the Natural Sciences [61]. This paper can be construed as an examination and affirmation of Galileo's tenet that “The book of nature is written in the language of mathematics”. To this effect, Wigner presented a large number of examples that demonstrate the effectiveness of mathematics in accurately describing physical phenomena. Wigner viewed these examples as (...) illustrations of what he called the empirical law of epistemology, which asserts that the mathematical formulation of the laws of nature is both appropriate and accurate, and that mathematics is actually the correct language for formulating the laws of nature. At the same time, Wigner pointed out that the reasons for the success of mathematics in the natural sciences are not completely understood; in fact, he went as far as asserting that “… the enormous usefulness of mathematics in the natural sciences is something bordering on the mysterious and there is no rational explanation for it.”. (shrink)

Pour le philosophe intéressé aux structures et aux fondements du savoir théorétique, à la constitution d'une « méta-théorétique «, θεωρíα., qui, mieux que les « Wissenschaftslehre » fichtéenne ou husserlienne et par-delà les débris de la métaphysique, veut dans une intention nouvelle faire la synthèse du « théorétique », la logique mathématique se révèle un objet privilégié.

Le problème de la formalisation de la logique hégélienne a fait l'objet récemment d'études d'inspiration et d'importance diverses. II y a d'abord le travail d'envergure de Gotthard Guenther sur le projet d'une logique non-aristotélicienne, le long article de Michael Kosok et la note de F. G. Asenjo.

A definition of a property P is impredicative if it quantifies over a domain to which P belongs. Due to influential arguments by Ramsey and Gödel, impredicative mathematics is often thought to possess special metaphysical commitments. It seems that an impredicative definition of a property P does not have the intended meaning unless P already exists, suggesting that the existence of P cannot depend on its explicit definition. Carnap (1937 [1934], p. 164) argues, however, that accepting impredicative definitions amounts to (...) choosing a "form of language" and is free from metaphysical implications. This paper explains this view in its historical context. I discuss the development of Carnap’s thought on the foundations of mathematics from the mid-1920s to the mid-1930s, concluding with an account of Carnap’s (1937 [1934]) non-Platonistic defense of impredicativity. This discussion is also important for understanding Carnap’s influential views on ontology more generally, since Carnap’s (1937 [1934]) view, according to which accepting impredicative definitions amounts to choosing a "form of language", is an early precursor of the view Carnap presents in "Empiricism, Semantics and Ontology" (1956 [1950]), according to which referring to abstract entities amounts to accepting a "linguistic framework". (shrink)

Anselm of Cantorbery wrote Proslogion, where is formulated the famous ‘Unum argumentum’ about the existence of God. This argument was been disputed and criticized by numerous logicians from an extensional view point. The classical predicate logic is not able to give a formal frame to develop an adequate analysis of this argument. According to us, this argument is not an ontological proof; it analyses the meaning of the “quo nihil maius cogitari posit”, a characterization of God, and establish, by absurd, (...) that “quod non posit cogitare non esse” by using the hypothesis: “to think in re” is taller than “to think in solo intelectu”. We discuss this relation and the difference between the meanings of the elementary predicates ‘to be in re’, ‘to be in intellectu’ and ‘to be in solo intellectu’. We propose a new logical approach of this ‘Unum argumentum’ of Anselm by using Curry’s Combinatory Logic. Indeed, Combinatory Logic is an abstract applicative formalism of operators applied to operands; in this formalism, the predicates, viewed as specific operators, can be composed and can be transformed, by an intrinsic way, into more complex predicates, by means of abstract operators, called “combinators”, studied by Combinatory Logic. We show that this formalism is a logical frame where it becomes possible to discuss and to formulate cognitive representations of the meanings of predicates used inside of the ‘Unum argumentum’ and to explain how the argument runs. (shrink)

Because the main difference between combinatory weak equality and λβ-equality is that the rule \begin{equation*}\tag{\xi} X = Y \vdash \lambda x.X = \lambda x.Y\end{equation*} is valid for the latter but not the former, it is easy to assume that another way of defining combinatory β-equality is to add rule (ξ) to the postulates for weak equality. However, to make this true, one must choose the definition of combinatory abstraction in (ξ) very carefully. If one tries to use one of the (...) more common abstraction algorithms, the result will be an equality, = ξ , that is either equivalent to βη-equality (and so strictly stronger than β-equality) or else strictly weaker than β-equality. This paper will study the relations = ξ for several commonly used abstraction algorithms, distinguish between them, and axiomatize them. (shrink)

In this essay we discuss Tarski's work on what he calledthe methodology of the deductive sciences, or more briefly, borrowing the terminology of Hilbert,metamathematics, The clearest statement of Tarski's views on this subject can be found in his textbookIntroduction to logic[41m].1Here he describes the tasks of metamathematics as “the detailed analysis and critical evaluation of the fundamental principles that are applied in the construction of logic and mathematics”. He goes on to describe what these fundamental principles are: All the expressions (...) of the discipline under consideration must be defined in terms of a small group of primitive expressions that seem immediately understandable. Furthermore, only those statements of the discipline are accepted as valid that can be deduced by precisely defined and universally accepted means from a small set of axioms whose validity seems evident. The method of constructing a discipline in strict accordance with these principles is known as thedeductive method, and the disciplines constructed in this manner are calleddeductive systems. Since contemporary mathematical logic is one of those disciplines that are subject to these principles, it itself is a deductive science. Tarski then goes on to say:“The view has become more and more common that the deductive method is the only essential feature by means of which the mathematical disciplines can be distinguished from all other sciences; not only is every mathematical discipline a deductive theory, but also, conversely, every deductive theory is a mathematical discipline”.This identification of mathematics with the deductive sciences is in our view one of the distinctive aspects of Tarski's work. Another characteristic feature is his broad view of what constitutes the domain of metamathematical investigations. A clue to this aspect of his work can also be found in Chapter 6 ofIntroduction to logic. After a discussion of the notions of completeness and consistency, he remarks that the investigations concerning these topics were among the most important factors contributing to a considerable extension of the domain of methodological studies, and caused even a fundamental change in the whole character of the methodology of deductive sciences. (shrink)

Dual combinators emerge from the aim of assigning formulas containing ← as types to combinators. This paper investigates formally some of the properties of combinatory systems that include both combinators and dual combinators. Although the addition of dual combinators to a combinatory system does not affect the unique decomposition of terms, it turns out that some terms might be redexes in two ways (with a combinator as its head, and with a dual combinator as its head). We prove a general (...) theorem stating that no dual combinatory system possesses the Church-Rosser property. Although the lack of confluence might be problematic in some cases, it is not a problem per se. In particular, we show that no damage is inflicted upon the structurally free logics, the system in which dual combinators first appeared. (shrink)

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric λ-calculus) is known to lack the Church-Rosser property. We prove a muchstrongertheorem that no symmetric combinatory logic that containsat least two proper symmetric combinatoryhas the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic,the proof is differentbecause symmetric combinators may form redexes in both left and right associated terms. Perhaps surprisingly, we are also able (...) to show that certain symmetric combinatory logics that include justone particular constantare not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property. (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)

A statement is generic if it expresses a generalization about the members of a kind, as in, ’Pear trees blossom in May,’ or, ’Birds lay egg’. In classical logic, generic statements are formalized as universally quantified conditionals: ‘For all x, if..., then....’ We want to argue that such a logical interpretation fails to capture the intensional character of generic statements because it cannot express the generic statement as a simple proposition in Aristotle’s sense, i.e., a proposition containing only one single (...) predicate. On the contrary, we want to show that typed lambda-abstraction can help us transform the classical, non-simple and extensional expression of generic statements into a new, simple and intensional formalization, through the introduction of an abductively defined operator ALL*. This new operator allows for the possibility of a single predication, e.g. fly(), because it builds, out of a concept like ‘bird’, a concrete universal, e.g. ‘birds’, upon which the single predicate can be applied to authentically formalize a generic statement, e.g. ‘birds fly’. (shrink)

We propose a reconstruction of the constellation of problems and philosophical positions on the nature and number of the primitives of logic in four authors of the nineteenth century logical scene: Peano, Padoa, Frege and Peirce. We argue that the proposed reconstruction forces us to recognize that it is in at least four different senses that a notation can be said to be simpler than another, and we trace the origins of these four senses in the writings of these authors. (...) We conclude that Frege, and even more so Peirce, developed new notations not to make drawing logical conclusions easier but in order to answer the needs of logical analysis. (shrink)