It has been known for some time that there is a primitive recursive permutation of the nonnegative integers whose inverse is recursive but not primitive recursive. For example one has this result apparently for the first time in Kuznecov [1] and implicitly in Kent [2] or J. Robinson [3], who shows that every singularly recursive function ƒ is representable aswhere A, B, C are primitive recursive and B is a permutation.

We define a class of so-called ∑-sets as a natural closure of recursively enumerable sets Wn under the relation “∈” and study its properties.

We describe a sequent calculus, based on work of Herbelin, of which the cut-free derivations are in 1-1 correspondence with the normal natural deduction proofs of intuitionistic logic. We present a simple proof of Herbelin's strong cut-elimination theorem for the calculus, using the recursive path ordering theorem of Dershowitz.

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)

This article discusses approaches to the problem of the number of preference orderings that can be constructed from a given set of alternatives. After briefly reviewing the prevalent approach to this problem, which involves determining a partitioning of the alternatives and then a permutation of the partitions, this article explains a recursive approach and shows it to have certain advantages over the partitioning one.

This paper is a continuation of the authors' work , where the main problem considered was whether a given recursive structure is recursively isomorphic to a polynomial-time structure. In that paper, a recursive Abelian group was constructed which is not recursively isomorphic to any polynomial-time Abelian group. We now show that if every element of a recursive Abelian group has finite order, then the group is recursively isomorphic to a polynomial-time group. Furthermore, if the orders are bounded, (...) then the group is recursively isomorphic to a polynomial-time group with universe A being the set of tally representations of natural numbers Tal = s{;1s};* or the set of binary representations of the natural numbers Bin. We also construct a recursive Abelian group with all elements of finite order but which has elements of arbitrary large finite order which is not isomorphic to any polynomial-time group with universe Tal or Bin. Similar results are obtained for structures , where f is a permutation on the set A. (shrink)

We summarize the essential ingredients, which enabled us to derive the path-integral for a system of harmonically interacting spin-polarized identical particles in a parabolic confining potential, including both the statistics (Bose–Einstein or Fermi–Dirac) and the harmonic interaction between the particles. This quadratic model, giving rise to repetitive Gaussian integrals, allows to derive an analytical expression for the generating function of the partition function. The calculation of this generating function circumvents the constraints on the summation over the cycles of the (...) class='Hi'>permutation group. Moreover, it allows one to calculate the canonical partition function recursively for the system with harmonic two-body interactions. Also, static one-point and two-point correlation functions can be obtained using the same technique, which make the model a powerful trial system for further variational treatments of realistic interactions. (shrink)

This essay begins by noting that “the question of the animal” has been abandoned prematurely in the current theoretical landscape in favor of the Plant, the Stone, the Object, and a more general rush toward Materialism and Realism (in their various permutations). The latest iteration of this economy of knowledge production (and planned obsolescence) may be found in the ubiquitous discourse of “the Anthropocene.” While it is a large and diverse body of thought and writing, I will focus here on (...) Bruno Latour’s influential rendition in Facing Gaia: Eight Lectures on the New Climatic Regime. I share Latour’s reservations about the concept of the Anthropocene, and I also share his desire for a more complex understanding of Gaia as an “outlaw” whose alterity pushes back against traditional concepts of nature as a totalized and homeostatic order. As I will show, however, Latour’s Actor Network Theory is far too blunt a theoretical instrument to account for the radical difference between qualitatively different orders of complexity and causation that obtain in biological vs. physical systems, which is crucial, of course, for understanding the role of the biological in the larger domain of Gaia and climate change. As I will show – drawing principally on the work of Stuart Kauffman and his proposition that the evolution of the biosphere is neither non-ergodic nor governed by entailing laws – the real “outlaw” (to use Latour’s language), when it comes to the evolution of the earth and its climate system, is the contingency and recursivity of autopoietic biological systems, which enable a form of downward and distributed causality, and a “decoupling” between micro- and macro-levels (to borrow Alicia Juarrero’s phrase), in which the alterity and negativity of temporality (hence my emphasis on “dynamic”) is irreducible and “creative.” We see this both ontogenetically and phylogenetically (as in the example of niche formation in ecosystems). In short, biology is not (only) physics – far from it. Why is this important? Because, after decades of hegemony by the neo-Darwinian reductionist paradigm, with its infatuation with the genome as the “book of life” and its subsequent engineering paradigm for biological existence, it is crucial to formulate an anti-reductionist, interdisciplinary framework for understanding the real complexity of life on the planet and its evolution. Here, however – as I argued in What is Posthumanism? – the issue isn’t just what you are thinking (the decentering of the human and humanism that Latour and I both share) but how you are thinking it. Here, Latour’s work has a desire, but no theory, for the alterity we both seek. At this crucial epistemic moment, we need, in short, an anti-reductionist anti-reductionism – not flat ontologies, but ever more “jagged” ones. (shrink)

Building on previous work by Mints, Buchholz and Schwichtenberg, a simplified version of continuous normalization for the untyped λ-calculus and Gödel’s is presented and analysed in the coalgebraic framework of non-wellfounded terms with so-called repetition constructors.The primitive recursive normalization function is uniformly continuous w.r.t. the natural metric on non-wellfounded terms. Furthermore, the number of necessary repetition constructors is locally related to the number of reduction steps needed to reach the normal form and its size.It is also shown how continuous (...) normal forms relate to derivations of strong normalizability in the typed λ-calculus and how this leads to new bounds for the sum of the height of the reduction tree and the size of the normal form.Finally, the methods are extended to an infinitary λ-calculus with ω-rule and permutative conversions and this is used to derive a strong form of normalization for an iterative version of Gödel’s system , leading to a value table semantics for number-theoretic functions. (shrink)

This note explains an error in Restall’s ‘Simplified Semantics for Relevant Logics (and some of their rivals)’ (Restall, J Philos Logic 22(5):481–511, 1993 ) concerning the modelling conditions for the axioms of assertion A → (( A → B ) → B ) (there called c 6) and permutation ( A → ( B → C )) → ( B → ( A → C )) (there called c 7). We show that the modelling conditions for assertion and (...) class='Hi'>permutation proposed in ‘Simplified Semantics’ overgenerate. In fact, they overgenerate so badly that the proposed semantics for the relevant logic R validate the rule of disjunctive syllogism. The semantics provides for no models of R in which the “base point” is inconsistent. This problem is not restricted to ‘Simplified Semantics.’ The techniques of that paper are used in Graham Priest’s textbook An Introduction to Non-Classical Logic (Priest, 2001 ), which is in wide circulation: it is important to find a solution. In this article, we explain this result, diagnose the mistake in ‘Simplified Semantics’ and propose two different corrections. (shrink)

We write$\mathcal {S}_n(A)$for the set of permutations of a setAwithnnon-fixed points and$\mathrm {{seq}}^{1-1}_n(A)$for the set of one-to-one sequences of elements ofAwith lengthnwherenis a natural number greater than$1$. With the Axiom of Choice,$|\mathcal {S}_n(A)|$and$|\mathrm {{seq}}^{1-1}_n(A)|$are equal for all infinite setsA. Among our results, we show, in ZF, that$|\mathcal {S}_n(A)|\leq |\mathrm {{seq}}^{1-1}_n(A)|$for any infinite setAif${\mathrm {AC}}_{\leq n}$is assumed and this assumption cannot be removed. In the other direction, we show that$|\mathrm {{seq}}^{1-1}_n(A)|\leq |\mathcal {S}_{n+1}(A)|$for any infinite setAand the subscript$n+1$cannot be reduced ton. Moreover, (...) we also show that “$|\mathcal {S}_n(A)|\leq |\mathcal {S}_{n+1}(A)|$for any infinite setA” is not provable in ZF. (shrink)

On a widely held characterization, triadic joint attention is the capacity to perceptually attend to an object or event together with another subject. In the last four decades, research in developmental psychology has provided increasing evidence of the crucial role that this capacity plays in socio-cognitive development, early language acquisition, and the development of perspective-taking. Yet, there is a striking discrepancy between the general agreement that joint attention is critical in various domains, and the lack of theoretical consensus on how (...) to account for it. This paper pursues three interrelated aims: (i) it examines the contrast between reductive and non-reductive views of (triadic) joint attention, by bringing into focus the notion of recursive mindreading; (ii) it assembles, advances, and discusses a number of arguments against reductive views; (iii) finally, in dialogue with some prominent non-reductive views, it outlines the case for a non-reductive view that gives pride of place to the idea that co-attenders relate to one another as a ‘you’. (shrink)

The article presents an analysis of a mystical practice of letter permutation conceived as part of the practice of “kavannah” in prayer. This practice was articulated by a 13th century anonymous ecstatic kabbalist writing in Catalonia. The anonymous author draws on earlier sources in the kabbalah and Ashkenazi spirituality. The article explores the wider connection between ecstasy and ritual, particularly prayer in the earlier stages of Judaism and its development in medieval theology and kabbalah. The anonymous author describes a (...) unique permutation technique capable of inducing ecstatic experiences as part of the liturgical ritual. (shrink)

How are permutation arguments for the inscrutability of reference to be formulated in the context of a Davidsonian truth-theoretic semantics? Davidson takes these arguments to establish that there are no grounds for favouring a reference scheme that assigns London to “Londres”, rather than one that assigns Sydney to that name. We shall see, however, that it is far from clear whether permutation arguments work when set out in the context of the kind of truth-theoretic semantics which Davidson favours. (...) The principle required to make the argument work allows us to resurrect Foster problems against the Davidsonian position. The Foster problems and the permutation inscrutability problems stand or fall together: they are one puzzle, not two. (shrink)

Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from (...) small time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

The current literature standardly conceives of voting power in terms of decisiveness: the ability to change the voting outcome by unilaterally changing one’s vote. I argue that this classic conception of voting power, which fails to account for partial decisiveness or efficacy, produces erroneous results because it saddles the concept of voting power with implausible microfoundations. This failure in the measure of voting power in turn reflects a philosophical mistake about the concept of social power in general: a failure to (...) recognize that an agent can exercise individual social power with others’ assistance, in virtue of the group’s collective power, sometimes even when she could not unilaterally scuttle the group’s collective power. I therefore develop a conception of efficacy that admits of degrees and defend a Recursive Measure of voting power that takes partial efficacy into account. (shrink)

Is there a nontrivial automorphism of the Turing degrees? It is a major open problem of computability theory. Past results have limited how nontrivial automorphisms could possibly be. Here we consider instead how an automorphism might be induced by a function on reals, or even by a function on integers. We show that a permutation of ω cannot induce any nontrivial automorphism of the Turing degrees of members of 2ω, and in fact any permutation that induces the trivial (...) automorphism must be computable.A main idea of the proof is to consider the members of 2ω to be probabilities, and use statistics: from random outcomes from a distribution we can compute that distribution, but not much more. (shrink)

Let M be a model of ZFAC (ZFC modified to allow a set of atoms), and let N be an inner model with the same set of atoms and the same pure sets (sets with no atoms in their transitive closure) as M. We show that N is a permutation submodel of M if and only if N satisfies the principle SVC (Small Violations of Choice), a weak form of the axiom of choice which says that in some sense, (...) all violations of choice are localized in a set. A special case is considered in which there exists an SVC witness which satisfies a certain homogeneity condition. (shrink)

We write and for the cardinalities of the set of permutations with n non‐fixed points and the set of subsets with n elements, respectively, of a set which is of cardinality, where n is a natural number greater than 1. With the Axiom of Choice, and are equal for all infinite cardinals. We show, in ZF, that if is assumed, then for any infinite cardinal. Moreover, the assumption cannot be removed for and the superscript cannot be replaced by n. We (...) also show under that for any infinite cardinal, implies is Dedekind‐infinite. (shrink)

It is shown that, according to NF, many of the assertions of ordinal arithmetic involving the T-function which is peculiar to NF turn out to be equivalent to the truth-in-certain-permutation-models of assertions which have perfectly sensible ZF-style meanings, such as: the existence of wellfounded sets of great size or rank, or the nonexistence of small counterexamples to the wellfoundedness of ∈. Everything here holds also for NFU if the permutations are taken to fix all urelemente.

This volume contains papers from the recursion theory session of the Kazan Workshop on Recursion and Complexity Theory. Recursion theory, the study of computability, is an area of mathematical logic that has traditionally been particularly strong in the United States and the former Soviet Union. This was the first workshop ever to bring together about 50 international experts in recursion theory from the United States, the former Soviet Union and Western Europe.

This graduate-level_text by a master in the field builds a function theory of the rational field that combines aspects of classical and intuitionist analysis. Topics include recursive convergence, recursive and relative continuity, recursive and relative differentiability, the relative integral, elementary functions, and transfinite ordinals. 1961 edition.

This volume presents the lecture notes of short courses given by three leading experts in mathematical logic at the 2012 Asian Initiative for Infinity Logic Summer School. The major topics cover set-theoretic forcing, higher recursion theory, and applications of set theory to C*-algebra. This volume offers a wide spectrum of ideas and techniques introduced in contemporary research in the field of mathematical logic to students, researchers and mathematicians.

In this article I expound an understanding of the quantum mechanics of so-called “indistinguishable” systems in which permutation invariance is taken as a symmetry of a special kind, namely the result of representational redundancy. This understand- ing has heterodox consequences for the understanding of the states of constituent systems in an assembly and for the notion of entanglement. It corrects widespread misconceptions about the inter-theoretic relations between quantum mechanics and both classical particle mechanics and quantum field theory. The most (...) striking of the heterodox consequences are: that fermionic states ought not always to be considered entangled; it is possible for two fermions or two bosons to be discerned using purely monadic quantities; and that fermions may always be so discerned. (shrink)

The paper exposes the relevance of permuting conversions (in natural-deduction systems) to the role of such systems in the theory of meaning known as proof-theoretic semantics, by relating permuting conversion to harmony, hitherto related to normalisation only. This is achieved by showing the connection of permuting conversion to the general notion of canonicity, once applied to arbitrary derivations from open assumption. In the course of exposing the relationship of permuting conversions to harmony, a general definition of the former is proposed, (...) generalising the specific cases of disjunction and existential quantifiers considered in the literature. (shrink)

Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

In mathematics, various representations of real numbers have been investigated. All these representations are mathematically equivalent because they lead to the same real structure - Dedekind-complete ordered field. Even the effective versions of these representations are equivalent in the sense that they define the same notion of computable real numbers. Although the computable real numbers can be defined in various equivalent ways, if computable is replaced by primitive recursive (p. r., for short), these definitions lead to a number of (...) different concepts, which we compare in this article. We summarize the known results and add new ones. In particular we show that there is a proper hierarchy among p. r. real numbers by nested interval representation, Cauchy representation, b -adic expansion representation, Dedekind cut representation, and continued fraction expansion representation. Our goal is to clarify systematically how the primitive recursiveness depends on the representations of the real numbers. (shrink)

A class of problems is called decidable if there is an algorithm which will give the answer to any problem of the class after a finite length of time. The purpose of this paper is to discuss the classes of problems that can be solved by infinitely long decision procedures in the following sense: An algorithm is given which, for any problem of the class, generates an infinitely long sequence of guesses. The problem will be said to be solved in (...) the limit if, after some finite point in the sequence, all the guesses are correct and the same. Functions, sets, and functionals which are decidable by such infinite algorithms will be calledlimiting recursive. These, together with classes of objects which can beidentified in the limit, are the subjects of this report.Without qualification,setwill mean set of numbers;functionwill mean number-theoretic function of 1 variable, possibly partial;functionalswill take numerical values and have any number of numerical and/or function variables, the latter ranging solely over total functions of 1 variable. Thus a function is a special case of a functional,xwill invariably stand for a numerical variable;φfor a function variable;gfor a guess ;nfor the numerical variable which indexes the guesses, referred to as thetime. (shrink)

It has been claimed that recursion is one of the properties that distinguishes human language from any other form of animal communication. Contrary to this claim, a recent study purports to demonstrate center‐embedded recursion in starlings. I show that the performance of the birds in this study can be explained by a counting strategy, without any appreciation of center‐embedding. To demonstrate that birds understand center‐embedding of sequences of the form AnBn (such as A1A2B2B1, or A3A4A5B5B4B3) would require not only that (...) they discriminate such patterns from other patterns, but that they appreciate that elements must be bound from the outside in (thus, in the above examples, A1B1, A2B2, A3B3, A4B4, A5B5 are bound pairs). This has not been shown in nonhuman species, and sentences with this structure are difficult even for humans to parse. There appears to be no evidence to date that nonhuman species understand recursion. (shrink)

This paper, a contribution to “micro set theory”, is the study promised by the first author in [M4], as improved and extended by work of the second. We use the rudimentarily recursive functions and the slightly larger collection of gentle functions to initiate the study of provident sets, which are transitive models of $\mathsf{PROVI}$, a subsystem of $\mathsf{KP}$ whose minimal model is Jensen’s $J_{\omega}$. $\mathsf{PROVI}$ supports familiar definitions, such as rank, transitive closure and ordinal addition—though not ordinal multiplication—and Shoenfield’s (...) unramified forcing. Providence is preserved under directed unions. An arbitrary set has a provident closure, and the extension of a provident $M$ by a set-generic $\mathcal{G}$ is the provident closure of $M\cup\{\mathcal{G}\}$. The improvidence of many models of $\mathsf{Z}$ is shown. The final section uses similar but simpler recursions to show, in the weak system $\mathsf{MW}$, that the truth predicate for $\dot{\varDelta}_{0}$ formulæ is $\Delta_{1}$. (shrink)

I offer a variant of Putnam’s “permutation argument,” originally an argument against metaphysical realism. This variant is called the “natural permutation argument.” I explain how the natural permutation argument generates a form of referential inscrutability which is not resolvable by consideration of “natural properties” in the sense of Lewis’s response to Putnam. However, unlike the classical permutation argument (which is applicable to nearly all interpretations of all first-order theories), the natural permutation argument only applies to (...) interpretations which have some special symmetries. I give an analysis of the interpretations to which the natural permutation argument does apply, and I explain how, when it fails to apply, the referential inscrutability generated by permutation arguments is resolvable by a Lewisian strategy. In order to demonstrate how these problems of referential inscrutability play out in an a priori setting relevant to philosophy, I discuss the applicability of the natural permutation argument in set-theoretic reasoning. I use the well-known Kunen inconsistency theorem to show that, in Zermelo–Fraenkel set theory, the Axiom of Choice is sufficient to resolve referential inscrutability. I then explain how, as a result of a recent theorem of Daghighi–Golshani–Hamkins–Jeřábek, in certain non-well-founded set theories the natural permutation argument does yield an intractable inscrutability of reference. (shrink)