CHAPTER Addenda to Pure Combinatory Logic This chapter will treat various additions to, and modifications of, the subject matter of Chapters-7. ...

Human language, hominin tool production modes, and multimodal communications systems of primates and other animals are currently well-studied for how they display compositionality or combinatoriality. In all cases, the former is defined as a kind of hierarchical nesting and the latter as a lack thereof. In this article, I extend research on combinatoriality and compositionality further to investigations of everyday primate skills. Daily locomotion modes as well as behaviors associated with subsistence practices, hygiene, or body modification rely on the hierarchical (...) nesting of different behavioral and cognitive actions into complex skills. I introduce a scheme which uses hierarchical organization to differentiate combinatorial from compositional skills. Combinatorial skills are defined either as aggregational or linearly hierarchical depending on whether the skill occurs momentarily in space or unfolds sequentially over time. Compositional skills are defined either as nested or interactionally hierarchical depending on whether the skill results in new constructs or in new interactions between existing constructs. The methodology I propose combines epistemological hierarchy theory with data from primatological field research and experimental and comparative psychological research and provides a means to integrate current constructionist and extended views on cognition and action with older research on behavioral logics in psychology and operational chain thinking in anthropology. The approach furthermore synchronizes with ongoing research on teleonomy, intentionality, and creativity. -/- . (shrink)

Combinatorial behavior involves combining different elements into larger aggregates with meaning. It is generally contrasted with compositionality, which involves the combining of meaningful elements into larger constituents whose meaning is derived from its component parts. Combinatoriality is commonly considered a capacity found in primates and other animals, whereas compositionality often is considered uniquely human. Questioning the validity of this claim, this multidisciplinary special issue of the International Journal of Primatology unites papers that each study aspects of combinatoriality and compositionality (...) found in primate and bird communication systems, tool use, skills, and human language. The majority of authors conclude that compositionality is evolutionarily preceded by combinatoriality and that neither are uniquely human. This introduction briefly introduces readers to the major findings and issues raised by the contributors. -/- . (shrink)

Logical geometry systematically studies Aristotelian diagrams, such as the classical square of oppositions and its extensions. These investigations rely heavily on the use of bitstrings, which are compact combinatorial representations of formulas that allow us to quickly determine their Aristotelian relations. However, because of their general nature, bitstrings can be applied to a wide variety of topics in philosophical logic beyond those of logical geometry. Hence, the main aim of this paper is to present a systematic technique for assigning (...) bitstrings to arbitrary finite fragments of formulas in arbitrary logical systems, and to study the logical and combinatorial properties of this technique. It is based on the partition of logical space that is induced by a given fragment, and sheds new light on a number of interesting issues, such as the logic-dependence of the Aristotelian relations and the subtle interplay between the Aristotelian and Boolean structure of logical fragments. Finally, the bitstring technique also allows us to systematically analyze fragments from contemporary logical systems, such as public announcement logic, which could not be done before. (shrink)

David Armstrong's book is a contribution to the philosophical discussion about possible worlds. Taking Wittgenstein's Tractatus as his point of departure, Professor Armstrong argues that nonactual possibilities and possible worlds are recombinations of actually existing elements, and as such are useful fictions. There is an extended criticism of the alternative-possible-worlds approach championed by the American philosopher David Lewis. This major work will be read with interest by a wide range of philosophers.

We study the fine structure of the core model for one Woodin cardinal, building of the work of Mitchell and Steel on inner models of the form . We generalize to some combinatorial principles that were shown by Jensen to hold in L. We show that satisfies the statement: “□κ holds whenever κ the least measurable cardinal λ of order λ++”. We introduce a hierarchy of combinatorial principles □κ, λ for 1 λ κ such that □κ□κ, 1 □κ, (...) λ □κ, κ□κ*. We prove that if holds in V. As an application, we show that ZFC + PFA Con. We also obtain one Woodin cardinal as a lower bound on the consistency strength of stationary reflection at κ+ for a singular, countably closed limit cardinal κ such that # exists; likewise for the failure of □κ* at such a κ. (shrink)

We show that linear logic can serve as an expressive framework in which to model a rich variety of combinatorial auction mechanisms. Due to its resource-sensitive nature, linear logic can easily represent bids in combinatorial auctions in which goods may be sold in multiple units, and we show how it naturally generalises several bidding languages familiar from the literature. Moreover, the winner determination problem, i.e., the problem of computing an allocation of goods to bidders producing a certain amount (...) of revenue for the auctioneer, can be modelled as the problem of finding a proof for a particular linear logic sequent. (shrink)

We introduce combinatorial principles that characterize strong compactness and supercompactness for inaccessible cardinals but also make sense for successor cardinals. Their consistency is established from what is supposedly optimal. Utilizing the failure of a weak version of a square, we show that the best currently known lower bounds for the consistency strength of these principles can be applied.

We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for (...) pairs (RT₂²) splits into a stable version (SRT₂²) and a cohesive principle (COH). We show that the same is true of ADS and CAC, and that in their cases the stable versions are strictly weaker than the full ones (which is not known to be the case for RT₂² and SRT₂²). We also analyze the relationships between these principles and other systems and principles previously studied by reverse mathematics, such as WKL₀, DNR, and BΣ₂. We show, for instance, that WKL₀ is incomparable with all of the systems we study. We also prove computability-theoretic and conservation results for them. Among these results are a strengthening of the fact, proved by Cholak, Jockusch, and Slaman, that COH is Π₁¹-conservative over the base system RCA₀. We also prove that CAC does not imply DNR which, combined with a recent result of Hirschfeldt, Jockusch, Kjos-Hanssen, Lempp, and Slaman, shows that CAC does not imply SRT₂² (and so does not imply RT₂²). This answers a question of Cholak, Jockusch, and Slaman. Our proofs suggest that the essential distinction between ADS and CAC on the one hand and RT₂² on the other is that the colorings needed for our analysis are in some way transitive. We formalize this intuition as the notions of transitive and semitransitive colorings and show that the existence of homogeneous sets for such colorings is equivalent to ADS and CAC, respectively. We finish with several open questions. (shrink)

We introduce, in a general setting, an ‘‘analytic’’ version of standard equational calculi of combinatory logic. Analyticity lies on the one side in the fact that these calculi are characterized by the presence of combinatory introduction rules in place of combinatory axioms, and on the other side in that the transitivity rule proves to be eliminable. Apart from consistency, which follows immediately, we discuss other almost direct consequences of analyticity and the main transitivity elimination theorem; in particular the Church−Rosser and (...) the leftmostreduction theorems for the associated notions of reduction. The last two sections deal with analytic combinatory calculi with the extensionality rule added. Here, as far as the elimination of transitivity is concerned, we have only partial results, which unfortunately do not cover, at present, full CL + Ext. Yet, they are sufficient to prove the decidability of weaker combinatory calculi with extensionality, including e.g. BCK + Ext. (shrink)

The authors aim to reinstate a spirit of philosophical enquiry in physics. They abandon the intuitive continuum concepts and build up constructively a combinatorial mathematics of process. This radical change alone makes it possible to calculate the coupling constants of the fundamental fields which? via high energy scattering? are the bridge from the combinatorial world into dynamics. The untenable distinction between what is?observed?, or measured, and what is not, upon which current quantum theory is based, is not needed. (...) If we are to speak of mind, this has to be present? albeit in primitive form? at the most basic level, and not to be dragged in at one arbitrary point to avoid the difficulties about quantum observation. There is a growing literature on information-theoretic models for physics, but hitherto the two disciplines have gone in parallel. In this book they interact vitally. (shrink)

It is proved that $\Pi^1_1$ -indescribability in $P_{\kappa}\lambda$ can be characterized by combinatorial properties without taking care of cofinality of $\lambda$ . We extend Carr's theorem proving that the hypothesis $\kappa$ is $2^{\lambda^{<\kappa}}$ -Shelah is rather stronger than $\kappa$ is $\lambda$ -supercompact.

Reader-friendly without compromising the precision of exposition, the book includes many new research results not found in the available literature.

Combinatory logic started as a programme in the foundation of mathematics and in an historical context at a time when such endeavours attracted the most gifted among the mathematicians. This small volume arose under quite differ ent circumstances, namely within the context of reworking the mathematical foundations of computer science. I have been very lucky in finding gifted students who agreed to work with me and chose, for their Ph. D. theses, subjects that arose from my own attempts 1 to (...) create a coherent mathematical view of these foundations. The result of this collaborative work is presented here in the hope that it does justice to the individual contributor and that the reader has a chance of judging the work as a whole. E. Engeler ETH Zurich, April 1994 lCollected in Chapter III, An Algebraization of Algorithmics, in Algorithmic Properties of Structures, Selected Papers of Erwin Engeler, World Scientific PubJ. Co. , Singapore, 1993, pp. 183-257. I Historical and Philosophical Background Erwin Engeler In the fall of 1928 a young American turned up at the Mathematical Institute of Gottingen, a mecca of mathematicians at the time; he was a young man with a dream and his name was H. B. Curry. He felt that he had the tools in hand with which to solve the problem of foundations of mathematics mice and for all. His was an approach that came to be called "formalist" and embodied that later became known as Combinatory Logic. (shrink)

Are there practical reasons for and against belief? For example, do the practical benefits to oneself or others of holding a certain belief count in favor of that belief? I argue "No." My argument involves considering how practical reasons for belief, if there were such things, would combine with other reasons for belief in order to determine all-things-considered verdicts, especially in cases involving equally balanced reasons of either a practical or an epistemic sort.

In his long and illuminating paper [1] Joe Barback defined and showed to be non-vacuous a class of infinite regressive isols he has termed “complete y torre” isols. These particular isols a enjoy a property that Barback has since labelled combinatoriality. In [2], he provides a list of properties characterizing the combinatoria isols. In Section 2 of our paper, we extend this list of characterizations to include the fact that an infinite regressive isol X is combinatorial if and only (...) if its associated Dekker semiring D satisfies all those Π2 sentences of the anguage LN for isol theory that are true in the set ω of natural numbers. of the various function and relation symbols of LN via the “lifting ” to D of their Σ1 definitions in ω coincide with their interpretations via isolic extension.) We also note in Section 2 that Π2-correctness, for semirings D, cannot be improved to Π 3-correctness, no matter how many additional properties we succeed in attaching to a combinatoria isol; there is a fixed equation image sentence that blocks such extension. In Section 3, we provide a proof of the existence of combinatorial isols that does not involve verification of the extremely strong properties that characterize Barback's CT isols. (shrink)

We employ the notions of "sequential function" and "interrogation" (dialogue) in order to define new partial combinatory algebra structures on sets of functions. These structures are analyzed using Longley's preorder-enriched category of partial combinatory algebras and decidable applicative structures. We also investigate total combinatory algebras of partial functions. One of the results is that every realizability topos is a geometric quotient of a realizability topos on a total combinatory algebra.

We prove that the theory IΔ0, extended by a weak version of the Δ0-Pigeonhole Principle, proves that every integer is the sum of four squares (Lagrange's theorem). Since the required weak version is derivable from the theory IΔ0 + ∀x (xlog(x) exists), our results give a positive answer to a question of Macintyre (1986). In the rest of the paper we consider the number-theoretical consequences of a new combinatorial principle, the ‘Δ0-Equipartition Principle’ (Δ0EQ). In particular we give a new (...) proof, which can be formalized in IΔ0 + Δ0EQ, of the fact that every prime of the form 4n + 1 is the sum of two squares. (shrink)

The purpose of this paper is to review and critique Wessel Reijers and Bert Gordijn’s paper Moving from value sensitive design to virtuous practice design. In doing so, it draws on recent literature on developing value sensitive design (VSD) to show how the authors’ virtuous practice design (VPD), at minimum, is not mutually exclusive to VSD. This paper argues that virtuous practice is not exclusive to the basic methodological underpinnings of VSD. This can therefore strengthen, rather than exclude the VSD (...) approach. Likewise, this paper presents not only a critique of what was offered as a “potentially fruitful alternative to VSD” but further clarifies and contributes to the VSD scholarship in extending its potential methodological practices and scope. It is concluded that VPD does not appear to offer any original contribution that more recent instantiations of VSD have not already proposed and implemented. (shrink)

Using a dictionary translating a variety of classical and modern covering properties into combinatorial properties of continuous images, we get a simple way to understand the interrelations between these properties in ZFC and in the realm of the trichotomy axiom for upward closed families of sets of natural numbers. While it is now known that the answer to the Hurewicz 1927 problem is positive, it is shown here that semifilter trichotomy implies a negative answer to a slightly stronger form (...) of this problem. (shrink)

Introduction Combinatory logic deals with a class of formal systems designed for studying certain primitive ways in which functions can be combined to form ...

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)

Brendle, J., H. Judah and S. Shelah, Combinatorial properties of Hechler forcing, Annals of Pure and Applied Logic 59 185–199. Using a notion of rank for Hechler forcing we show: assuming ωV1 = ωL1, there is no real in V[d] which is eventually different from the reals in L[ d], where d is Hechler over V; adding one Hechler real makes the invariants on the left-hand side of Cichoń's diagram equal ω1 and those on the right-hand side equal 2ω (...) and produces a maximal almost disjoint family of subsets of ω of size ω1; there is no perfect set of random reals over V in V[ r][ d], where r is random over V and d Hechler over V[r], thus answering a question of the first and second authors. (shrink)

This paper explores the prospects of a combinatorial account of modality. We argue against David M. Armstrong’s version of combinatorialism, which seeks to do without modal primitives, on the grounds, among other things, that Armstrong’s basic ontological categories are themselves subject to non-contingent constraints on recombination. We outline an alternative version, which acknowledges the necessity of modal primitives, at the level of ontology, and not just of our concepts.

We prove a combinatorial result for models of the 4-fragment of the Simple Theory of Types , TST4. The result says that if is a standard transitive and rich model of TST4, then satisfies the 0,0,n-property, for all n≥2. This property has arisen in the context of the consistency problem of the theory New Foundations . The result is a weak form of the combinatorial condition that was shown in Tzouvaras [5] to be equivalent to the consistency of (...) NF. Such weak versions were introduced in Tzouvaras [6] in order to relax the intractability of the original condition. The result strengthens one of the main theorems of Tzouvaras [5, Theorem 3.6] which is just equivalent to the 0,0,2-property. (shrink)

This paper focuses on the possibility of conceiving a form of ontological nihilism, starting from D. M. Armstrong’s combinatorialism. This possibility has been suggested by Efird and Stoneham, by means of proposing an alternative strategy to the ‘subtraction argument’. They claim that it is possible to sustain such nihilism trough the concepts of construction and totality state of affairs. However, this hypothesis will require the acceptance of non-instanciated universals, that is, platonic universals. Yet this is opposite to requirements that are (...) basic for a combinatorial theory, which should uphold that universals exist only in their instantiations. Then, the assumption of platonic universals results in high costs for a combinatorial naturalism, according to which only exists what is located in space and time. (shrink)

This paper focuses on the possibility of conceiving a form of ontological nihilism, starting from D. M. Armstrong’s combinatorialism. This possibility has been suggested by Efird and Stoneham, by means of proposing an alternative strategy to the ‘subtraction argument’. They claim that it is possible to sustain such nihilism trough the concepts of construction and totality state of affairs. However, this hypothesis will require the acceptance of non-instanciated universals, that is, platonic universals. Yet this is opposite to requirements that are (...) basic for a combinatorial theory, which should uphold that universals exist only in their instantiations. Then, the assumption of platonic universals results in high costs for a combinatorial naturalism, according to which only exists what is located in space and time. (shrink)

The axioms of projective and affine plane geometry are turned into rules of proof by which formal derivations are constructed. The rules act only on atomic formulas. It is shown that proof search for the derivability of atomic cases from atomic assumptions by these rules terminates . This decision method is based on the central result of the combinatorial analysis of derivations by the geometric rules: The geometric objects that occur in derivations by the rules can be restricted to (...) those known from the assumptions and cases. This “subterm property” is proved by permuting suitably the order of application of the geometric rules. As an example of the decision method, it is shown that there cannot exist a derivation of Euclid’s fifth postulate if the rule that corresponds to the uniqueness of the parallel line construction is taken away from the system of plane affine geometry. (shrink)

Suppose that is a normalized family in a Banach space indexed by the dyadic tree S. Using Stern's combinatorial theorem we extend important results from sequences in Banach spaces to tree‐families. More precisely, assuming that for any infinite chain β of S the sequence is weakly null, we prove that there exists a subtree T of S such that for any infinite chain β of T the sequence is nearly (resp., convexly) unconditional. In the case where is a family (...) of continuous functions, under some additional assumptions, we prove the existence of a subtree T of S such that for any infinite chain β of T, the sequence is unconditional. Finally, in the more general setting where for any chain β, is a Schauder basic sequence, we obtain a dichotomy result concerning the semi‐boundedly completeness of the sequences. (shrink)

We give an overview of a research line concentrated on finding to which extent compactness fails at the level of first uncountable cardinal and to which extent it could be recovered on some other perhaps not so large cardinal. While this is of great interest to set theorists, one of the main motivations behind this line of research is in its applicability to other areas of mathematics. We give some details about this and we expose some possible directions for further (...) research. (shrink)

In this paper, I present a modified and extended version of combinatory logic. Schönfinkel originated the study of combinatory logic (in [2]), but its development is primarily due to H. B. Curry. In the present paper, I will make use of both the symbolism (with some modification) and the results of Curry, as found in [1].What is novel about my version of combinatory logic is a kind of combinators which I call discriminators. These combinators discriminate between different symbols, and yield (...) values which are determined by the symbols which are their arguments. If the normal combinators investigated by Curry are considered as functions taking (combinations of) symbols as arguments and yielding symbols as values, these combinators can rearrange and cancel their arguments or introduce new symbols. (shrink)

Department of Economics, George Mason University, MSN 1D3, Carow Hall, Fairfax VA 22030, USA E-mail: [email protected] (http://hanson.gmu.edu).

Understanding whether the long and elaborate songs of male gibbons have syntax and hierarchical structures is an interesting question in the evolution of language, because gibbons are near humans in the phylogenetic tree and a hierarchically organized syntax is considered to be a basic component of human language. We conducted field research at Danum Valley Conservation Area in northern Borneo to test the hypothesis that gibbon songs have syntax and chunks. We followed one Mueller’s gibbon group for 1 week in (...) the dry and rainy seasons every year from 2001 to 2009, collecting vocal and behavioral data. Results show that songs emitted by the studied male gibbon were governed by combinatory rules. Some context-dependent songs had different combinatory rules, although they overlapped with the songs whose contexts were uncertain. The male Mueller’s songs had characteristics that suggest existence of chunk structure. These results provided an important perspective in the study of language origin. (shrink)

We characterize the polynomial time operations as those which are provably total in a first order system, which comprises (untyped) combinatory logic with extensionality, together with positive “safe induction” on the set of binary strings. The formalization of safe induction is inspired by Leivants idea of ramification. We also show how to replace ramification by means of modal logic.

Separates the purely combinatorial component of Arrow's impossibility theorem in the theory of collective preference from its decision-theoretic part, and likewise for the closely related Blair/Bordes/Kelly/Suzumura theorem. Such a separation provides a particularly elegant proof of Arrow's result, via a new 'splitting theorem'.

We study combinatorial principles related to the isomorphism property and the special model axiom in nonstandard analysis.

Human cognition is unique in the way in which it relies on combinatorial (or compositional) structures. Language provides ample evidence for the existence of combinatorial structures, but they can also be found in visual cognition. To understand the neural basis of human cognition, it is therefore essential to understand how combinatorial structures can be instantiated in neural terms. In his recent book on the foundations of language, Jackendoff described four fundamental problems for a neural instantiation of (...) class='Hi'>combinatorial structures: the massiveness of the binding problem, the problem of 2, the problem of variables, and the transformation of combinatorial structures from working memory to long-term memory. This paper aims to show that these problems can be solved by means of neural “blackboard” architectures. For this purpose, a neural blackboard architecture for sentence structure is presented. In this architecture, neural structures that encode for words are temporarily bound in a manner that preserves the structure of the sentence. It is shown that the architecture solves the four problems presented by Jackendoff. The ability of the architecture to instantiate sentence structures is illustrated with examples of sentence complexity observed in human language performance. Similarities exist between the architecture for sentence structure and blackboard architectures for combinatorial structures in visual cognition, derived from the structure of the visual cortex. These architectures are briefly discussed, together with an example of a combinatorial structure in which the blackboard architectures for language and vision are combined. In this way, the architecture for language is grounded in perception. Perspectives and potential developments of the architectures are discussed. Key Words: binding; blackboard architectures; combinatorial structure; compositionality; language; dynamic system; neurocognition; sentence complexity; sentence structure; working memory; variables; vision. (shrink)

The results of this paper extend some of the intimate relations that are known to obtain between combinatory logic and certain substructural logics to establish a general characterization theorem that applies to a very broad family of such logics. In particular, I demonstrate that, for every combinator X, if LX is the logic that results by adding the set of types assigned to X (in an appropriate type assignment system, TAS) as axioms to the basic positive relevant logic B∘T, then (...) LX is sound and complete with respect to the class of frames in the Routley-Meyer relational semantics for relevant and substructural logics that meet a first-order condition that corresponds in a very direct way to the structure of the combinator X itself. (shrink)

Given an admissible indexing φ of the countable atomless Boolean algebra B, an automorphism F of B is said to be recursively presented (relative to φ) if there exists a recursive function $p \in \operatorname{Sym}(\omega)$ such that F ⚬ φ = φ ⚬ p. Our key result on recursiveness: Both the subset of $\operatorname{Aut}(\mathscr{B})$ consisting of all those automorphisms which are recursively presented relative to some indexing, and its complement, the set of all "totally nonrecursive" automorphisms, are uncountable. This arises (...) as a consequence of the following combinatorial investigations: (1) A comparison of the cycle structures of f and f̄, where f is a permutation of some free basis of B and f̄ is the automorphism of B induced by f. (2) An explicit description of the permutations of ω whose conjugacy classes in $\operatorname{Sym}(\omega)$ are (a) uncountable, (b) countably infinite, and (c) finite. (shrink)

Within the controversy between the combinatorial and the connectionist approaches to cognition it has been argued that our semantic and syntactic capacities provide evidence for the combinatorial approach. In this paper I offer a counter-weight to this argument by pointing out that the same type of considerations, when applied to the pragmatics of adjectives, provide evidence for connectionism.

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)