This paper gives the strong reduction of the combinatory calculus SCL, which was introduced as a combinatory calculus corresponding to the untyped Lambda-mu calculus. It proves the confluence of the strong reduction. By the confluence, it also proves the conservativity of the extensional equality of SCL over the combinatory calculus CL, and the consistency of SCL.

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)

Nations with legal environments that allow indigenous entrepreneurs to create legal businesses are more likely to be peaceful and prosperous nations. In addition to focusing on the role of multinational corporations, those interested in creating peace through commerce should focus on promoting legal environments that allow indigenous entrepreneurs to create peace and prosperity. In order to illustrate the relationship between improved legal environments and conflict reduction, this article describes a case study in which increased economic freedom led to reduced (...) violence in Northern Ireland between 1975 and 2000. (shrink)

This book engages with the writings of W.G. Sebald, mediated by perspectives drawn from curriculum and architecture, to explore the theme of unsettling complacency and confront difficult knowledge around trauma, discrimination and destruction. Moving beyond overly instrumentalist and reductive approaches, the authors combine disciplines in a scholarly fashion to encourage readers to stretch their understandings of currere. The chapters exemplify important, timely and complicated conversations centred on ethical response and responsibility, in order to imagine a more just and aesthetically experienced (...) world. In the analysis of bildung as human formation, the book illuminates the pertinent lessons to be learned from the works of Sebald and provokes further investigations into the questions of memory, grief, and limits of language. Through its juxtaposition of curriculum and architecture, and using the prose of Sebald as a prism, the book revitalizes questions about education and ethics, probes the unsettling of complacency, and enables conversation around difficult knowledge and ethical responsibility, as well as offering hope and resolve. An important intervention in standard approaches to understanding currere, this book provides essential context for scholars and educators with interests in the history of education, curriculum studies, cultural studies, memory studies, narrative research, Sebaldian studies, and educational philosophy. (shrink)

Let $\Gamma$ be the random bipartite graph, a countable graph with two infinite sides, edges randomly distributed between the sides, but no edges within a side. In this paper, we investigate the reducts of $\Gamma$ that preserve sides. We classify the closed permutation subgroups containing the group $\operatorname {Aut}(\Gamma)^{\ast}$ , where $\operatorname {Aut}(\Gamma)^{\ast}$ is the group of all isomorphisms and anti-isomorphisms of $\Gamma$ preserving the two sides. Our results rely on a combinatorial theorem of Nešetřil and Rödl and a (...) class='Hi'>strong finite submodel property for $\Gamma$. (shrink)

Let $R$ be a convergent term rewriting system, and let $CR$-equality on combinatory logic terms be the equality induced by $\beta \eta R$-equality on terms of the lambda calculus under any of the standard translations between these two frameworks for higher-order reasoning. We generalize the classical notion of strong reduction to a reduction relation which generates $CR$-equality and whose irreducibles are exactly the translates of long $\beta R$-normal forms. The classical notion of strong normal form (...) in combinatory logic is also generalized, yielding yet another description of these translates. Their resulting tripartite characterization extends to the combined first-order algebraic and higher-order setting the classical combinatory logic descriptions of the translates of long $\beta$-normal forms in the lambda calculus. As a consequence, the translates of long $\beta R$-normal forms are easily seen to serve as canonical representatives for $CR$-equivalence classes of combinatory logic terms for non-empty, as well as for empty, $R$. (shrink)

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 give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at (...) most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees. (shrink)

We prove that if a strongly minimal nonlocally modular reduct of an algebraically closed valued field of characteristic 0 contains +, then this reduct is bi-interpretable with the underlying field.

Jaegwon Kim, and others, have recently posed a powerful challenge to both emergentism and nom-reductive physicalism by providing arguments that these positions are committed to an untenable combination of both ‘upward’ and ‘dounward’ determination. In section 1, I illuminate how the nature of the realization relation underlies such skeptical arguments However, in section 2, I suggest that such conclusions involve a confusion between the implications of physicalism and those of a related thesis the ‘Completeness of Physics' (Co?) I show that (...) the truth of CoP poses a very serious obstacle to realized properties being efficacious in a physicalist universe and suggest that abandoning CoP offers hope for defending non-reductive physicalism. I then formulate a schema for a physicalist metaphysics, in section 3, which rejects CoP. This scenario is one where microphysical properties have a few conditional powers that they contribute to individuals when they realize certain properties In such a situation, I argue, though physicalism holds true there is still plausibly both ‘upward’ and ‘downward’ determination, where the latter is crucially an underappreciated form of determination I temn 'non- causal'. Ultimately, I conclude that this metaphysical schema offers a coherent account of Strongly emergent properties that preserves the truth of NRP albeit, in a form that is purged of any commitment to CoP. Finally, in section: 4, I carefully explore which of Kim's assumptions and arguments this metaphysics undermines. (shrink)

Iaegwon Kim, and others, have recently posed a powerful challen,ge to both emergentism cmd ncm-reductIve physicalism lyy providing arguments that these positums are cornmitted to an untenabie combmation of both `upwarcit and 'clouniwardi determmation. In secuon 1, I illuminate how the nature of the realiza:0n relatzon underlies such sicepucal arguments However, tn secuon 2, I suggest that such conclusicrns involve a confusion between the implications of physicahsm and those of a related thesis the Vompleteness of Physics' (Co?) I show tht (...) the truth of Co? poses a very senous obstacle to realized properues beeng efficacrous in a physicalut =verse cmd sikwest that abandonmg Co? offers hope for defending non- reducuve physicalism. (shrink)

The paper argues that the phenomenon of first-order phase transitions (e.g., freezing) has features that make it a candidate to be classified as 'emergent'. However, it cannot be described either as 'weakly emergent' or 'strongly emergent'; hence it escapes categorization in terms employed in the current literature on the metaphysics of science.

There is a simple technique, due to Dragalin, for proving strong cut-elimination for intuitionistic sequent calculus, but the technique is constrained to certain choices of reduction rules, preventing equally natural alternatives. We consider such a natural, alternative set of reduction rules and show that the classical technique is inapplicable. Instead we develop another approach combining two of our favorite tools—Klop’s ι-translation and perpetual reductions. These tools are of independent interest and have proved useful in a variety of (...) settings; it is therefore natural to investigate, as we do here, what they have to offer the field of sequent calculus. (shrink)

Does chemistry reduce to physics? If this means ‘Can we derive the laws of chemistry from the laws of physics?’, recent discussions suggest that the answer is ‘no’. But sup posing that kind of reduction—‘epistemological reduction’—to be impossible, the thesis of ontological reduction may still be true: that chemical properties are determined by more fundamental properties. However, even this thesis is threatened by some objections to the physicalist programme in the philosophy of mind, objections that generalize to (...) the chemical case. Two objections are discussed: that physicalism is vacuous, and that nothing grounds the asymmetry of dependence which reductionism requires. Although it might seem rather surprising that the philosophy of chemistry is affected by shock waves from debates in the philosophy of mind, these objections show that there is an argumentative gap between, on the one hand, the theoretical connection linking chemical properties with properties at the sub-atomic level, and, on the other, the philosophical thesis of ontological reduction. The aim of this paper is to identify the missing premises (among them a theory of physical possibility) that would bridge this gap. Introduction: missing elements and the mystery of discreteness The refutation of physicalism A combinatorial theory of physical possibilia Combinatorialism and the Bohr model Objections The missing premises and a disanalogy with mind. (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 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)

I argue that an adequate account of non-reductive realization must guarantee satisfaction of a certain condition on the token causal powers associated with (instances of) realized and realizing entities---namely, what I call the 'Subset Condition on Causal Powers' (first introduced in Wilson 1999). In terms of states, the condition requires that the token powers had by a realized state on a given occasion be a proper subset of the token powers had by the state that realizes it on that occasion. (...) Accounts of non-reductive realization conforming to this condition are implementing what I call 'the powers-based subset strategy'. I focus on the crucial case involving mental and brain states; the results may be generalized, as appropriate. I first situate and motivate the strategy by attention to the problem of mental causation; I make the case, in schematic terms, that implementation of the strategy makes room (contra Kim 1989, 1993, 1998, and elsewhere) for mental states to be ontologically and causally autonomous from their realizing physical states, without inducing problematic causal overdetermination, and compatible with both Physicalism and Non-reduction; and I show that several contemporary accounts of non-reductive realization (in terms of functional realization, parthood, and the determinable/determinate relation) are plausibly seen as implementing the strategy. As I also show, implementation of the powers-based strategy does not require endorsement of any particular accounts of either properties or causation---indeed, a categoricalist contingentist Humean can implement the strategy. The schematic location of the strategy in the space of available responses to the problem of mental (more generally, higher-level) causation, as well as the fact that the schema may be metaphysically instantiated, strongly suggests that the strategy is, appropriately generalized and instantiated, sufficient and moreover necessary for non-reductive realization. I go on to defend the sufficiency and necessity claims against a variety of objections, considering, along the way, how the powers-based subset strategy fares against competing accounts of purportedly non-reductive realization in terms of supervenience, token identity, and constitution. (shrink)

Some claim that Non- reductive Physicalism is an unstable position, on grounds that NRP either collapses into reductive physicalism, or expands into emergentism of a robust or ‘strong’ variety. I argue that this claim is unfounded, by attention to the notion of a degree of freedom—roughly, an independent parameter needed to characterize an entity as being in a state functionally relevant to its law-governed properties and behavior. I start by distinguishing three relations that may hold between the degrees of (...) freedom needed to characterize certain special science entities, and those needed to characterize their composing physical entities; these correspond to what I call ‘reductions’, ‘restrictions’, and ‘eliminations’ in degrees of freedom. I then argue that eliminations in degrees of freedom, in particular—when strictly fewer degrees of freedom are required to characterize certain special science entities than are required to characterize their composing physical entities—provide a basis for making sense of how certain special science entities can be both physically acceptable and ontologically irreducible to physical entities. (shrink)

The need for representations and computations over their contents in psychological explanations is often cited as both the mark of the genuinely cognitive and a source of skepticism about the reducibility of cognitive theories to neuroscience. A generic version of this anti-reductionist argument is rejected in this paper as unsound, since (i) current thinking about associative learning emphasizes the need for cognitivist resources in theories adequate to explain even the simplest form of this phenomena (Pavlovian conditioning), and yet (ii) the (...) most widely accepted recent theory of associative learning, which utilizes cognitivist resources, has already been reduced to a purely neurophysiological account. Psychoneural reduction of genuinely cognitivist theories is thus already an accomplished scientific fact, despite pronouncements by anti-reductionists about its conceptual impossibility or empirical implausibility. In addition, the specific form of reduction involved in this case (“combinatorial” reduction) provides a promising model for further cognitivist-to-neuroscience theory reductions. (shrink)

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)

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)

Reduction and reductionism have been central philosophical topics in analytic philosophy of science for more than six decades. Together they encompass a diversity of issues from metaphysics and epistemology. This article provides an introduction to the topic that illuminates how contemporary epistemological discussions took their shape historically and limns the contours of concrete cases of reduction in specific natural sciences. The unity of science and the impulse to accomplish compositional reduction in accord with a layer-cake vision of (...) the sciences, the seminal contributions of Ernest Nagel on theory reduction and how they strongly conditioned subsequent philosophical discussions, and the detailed issues pertaining to different accounts of reduction that arise in both physical and biological science (e.g., limit-case and part-whole reduction in physics, the difference-making principle in genetics, and mechanisms in molecular biology) are explored. The conclusion argues that the epistemological heterogeneity and patchwork organization of the natural sciences encourages a pluralist stance about reduction. (shrink)

Partial combinatory algebras (pcas) are algebraic structures that serve as generalized models of computation. In this article, we study embeddings of pcas. In particular, we systematize the embeddings between relativizations of Kleene’s models, of van Oosten’s sequential computation model, and of Scott’s graph model, showing that an embedding between two relativized models exists if and only if there exists a particular reduction between the oracles. We obtain a similar result for the lambda calculus, showing in particular that it (...) cannot be embedded in Kleene’s first model. (shrink)

Some claim that Non-reductive Physicalism is an unstable position, on grounds that NRP either collapses into reductive physicalism, or expands into emergentism of a robust or ‘strong’ variety. I argue that this claim is unfounded, by attention to the notion of a degree of freedom—roughly, an independent parameter needed to characterize an entity as being in a state functionally relevant to its law-governed properties and behavior. I start by distinguishing three relations that may hold between the degrees of freedom (...) needed to characterize certain special science entities, and those needed to characterize their composing physical entities; these correspond to what I call ‘reductions’, ‘restrictions’, and ‘eliminations’ in degrees of freedom. I then argue that eliminations in degrees of freedom, in particular—when strictly fewer degrees of freedom are required to characterize certain special science entities than are required to characterize their composing physical entities—provide a basis for making sense of how certain special science entities can be both physically acceptable and ontologically irreducible to physical entities. (shrink)

A subset of the Cantor cube is null-additive if its algebraic sum with any null set is null. We construct a set of cardinality continuum such that: all continuous images of the set into the Cantor cube are null-additive, it contains a homeomorphic copy of a set that is not null-additive, and it has the property $\unicode{x3b3} $, a strong combinatorial covering property. We also construct a nontrivial subset of the Cantor cube with the property $\unicode{x3b3} $ that is (...) not null additive. Set-theoretic assumptions used in our constructions are far milder than used earlier by Galvin–Miller and Bartoszyński–Recław, to obtain sets with analogous properties. We also consider products of Sierpiński sets in the context of combinatorial covering properties. (shrink)

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators or, in a more direct way, in which derivations are not translated. Both (...) translations are closely related in a canonical way. The two direct translations turn out to be complete. The paper fulfills the program of Church [1932], [1933] and Curry [1930] to base logic on a consistent system of λ-terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent). (shrink)

Two articles on the reduction of chemistry are examined. The first, by McLaughlin (1992), claims that chemistry is reduced to physics and that there is no evidence for emergence or for downward causation between the chemical and the physical level. In a more recent article, Le Poidevin (2005) maintains that his combinatorial approach provides grounding for the ontological reduction of chemistry, which also circumvents some limitations in the physicalist program. †To contact the author, please write to: Department of (...) Chemistry and Biochemistry, UCLA, 607 Charles E. Young Drive East, Box 951569, Los Angeles, CA 90095-1569; e-mail: [email protected]. (shrink)

The idea of reduction has appeared in different forms throughout the history of science and philosophy. Thales took water to be the fundamental principle of all things; Leucippus and Democritus argued that everything is composed of small, indivisible atoms; Galileo and Newton tried to explain all motion with a few basic laws; 17th century mechanism conceived of everything in terms of the motions and collisions of particles of matter; British Empiricism held that all knowledge is, at root, experiential knowledge; (...) current physicists are searching for the GUT, the “grand unified theory,” that will show that at very high energies the electromagnetic and the weak and strong nuclear forces are fused into a single unified field. Some of these projects are clearly ontological in nature (Leucippus and Democritus), others are more methodological (mechanism), and still others strive for theoretical simplification (the projects of Galileo and Newton or the search for a GUT). Nevertheless, as they all aim at revealing some kind of unity or simplicity behind the appearance of plurality or complexity, they may all be regarded as (attempted) reductions. (shrink)

Reduction and reductionism have been central philosophical topics in analytic philosophy of science for more than six decades. Together they encompass a diversity of issues from metaphysics and epistemology. This article provides an introduction to the topic that illuminates how contemporary epistemological discussions took their shape historically and limns the contours of concrete cases of reduction in specific natural sciences. The unity of science and the impulse to accomplish compositional reduction in accord with a layer-cake vision of (...) the sciences, the seminal contributions of Ernest Nagel on theory reduction and how they strongly conditioned subsequent philosophical discussions, and the detailed issues pertaining to different accounts of reduction that arise in both physical and biological science (e.g., limit-case and part-whole reduction in physics, the difference-making principle in genetics, and mechanisms in molecular biology) are explored. The conclusion argues that the epistemological heterogeneity and patchwork organization of the natural sciences encourages a pluralist stance about reduction. (shrink)