On the observational equivalence of continuous-time deterministic and indeterministic descriptions Content Type Journal Article Pages 193-225 DOI 10.1007/s13194-010-0011-5 Authors Charlotte Werndl, Department of Philosophy, Logic and Scientific Method, London School of Economics, Houghton Street, London, WC2A 2AE UK Journal European Journal for Philosophy of Science Online ISSN 1879-4920 Print ISSN 1879-4912 Journal Volume Volume 1 Journal Issue Volume 1, Number 2.

Recently some results have been presented which show that certain kinds of deterministic descriptions and indeterministic descriptions are observationally equivalent (Werndl 2009a, 2010). This paper focuses on some philosophical questions prompted by these results. More specifically, first, I will discuss the philosophical comments made by mathematicians about observational equivalence, in particular Ornstein and Weiss (1991). Their comments are vague, and I will argue that, according to a reasonable interpretation, they are misguided. Second, the results on observational equivalence (...) raise the question of whether the deterministic or indeterministic description is preferable relative to all evidence. If none of them is preferable, there is underdetermination. I will criticize Winnie's (1998) argument that, by appealing to different observations, one finds that the deterministic description is preferable. In particular, I will clarify a confusion in this argument. Furthermore, I will argue that if the concern is a strong kind of underdetermination, the argument delivers the desired conclusion but this conclusion is trivial; and for other kinds of underdetermination of interest the argument fails. (shrink)

The central question of this paper is: are deterministic and indeterministic descriptions observationally equivalent in the sense that they give the same predictions? I tackle this question for measure-theoretic deterministic systems and stochastic processes, both of which are ubiquitous in science. I first show that for many measure-theoretic deterministic systems there is a stochastic process which is observationally equivalent to the deterministic system. Conversely, I show that for all stochastic processes there is a measure-theoretic deterministic system which (...) is observationally equivalent to the stochastic process. Still, one might guess that the measure-theoretic deterministic systems which are observationally equivalent to stochastic processes used in science do not include any deterministic systems used in science. I argue that this is not so because deterministic systems used in science even give rise to Bernoulli processes. Despite this, one might guess that measure-theoretic deterministic systems used in science cannot give the same predictions at every observation level as stochastic processes used in science. By proving results in ergodic theory, I show that also this guess is misguided: there are several deterministic systems used in science which give the same predictions at every observation level as Markov processes. All these results show that measure-theoretic deterministic systems and stochastic processes are observationally equivalent more often than one might perhaps expect. Furthermore, I criticise the claims of the previous philosophy papers Suppes (1993, 1999), Suppes and de Barros (1996) and Winnie (1998) on observational equivalence. (shrink)

Revolves around the matter of whether the stronger results that W. V. Quine and Donald Davidson were attempting to derive from slingshot arguments over facts might be forthcoming if other theories of descriptions were assumed. This also provides an opportunity to evaluate various theories as potential competitors to Bertrand Russell's theory. The four sections of the chapter are: Introductory Remarks; Hilbert and Bernays ; Fregean Theories ; and Strawsonian Theories.

The paper is devoted to applications of algebraic logic to databases. In databases a query is represented by a formula of first order logic. The same query can be associated with different formulas. Thus, a query is a class of equivalent formulae: equivalence here being similar to that in the transition to the Lindenbaum-Tarski algebra. An algebra of queries is identified with the corresponding algebra of logic. An algebra of replies to the queries is also associated with algebraic logic. (...) These relations lie at the core of the applications.In this paper it is shown how the theory of Halmos (polyadic) algebras (a notion introduced by Halmos as a tool in the algebraization of the first order predicate calculus) is used to create the algebraic model of a relational data base. The model allows us, in particular, to solve the problem of databases equivalence as well as develop a formal algebraic definition of a database's state description. In this paper we use the term "state description" for the logical description of the model. This description is based on the notion of filters in Halmos algebras. When speaking of a state description, we mean the description of a function which realizes the symbols of relations as real relations in the given system of data. (shrink)

Chs. 9 convert the two basic forms of slingshot argument—one used by Alonzo Church, W. V. Quine, and Donald Davidson, the other by Kurt Gödel—into knock‐down deductive proofs that Donald Davidson's and Richard Rorty's cases against facts and the representation of facts are unfounded, and their slingshot arguments for discrediting the existence of facts unsatisfactory. The proofs are agnostic on key semantic issues; in particular, they assume no particular account of reference and do not even assume that sentences have references. (...) Using the same procedure as in Chs. 8 and 9 shows that a slingshot argument engendered by Gödel's suggestions can be converted into a proof that delivers an exacting constraint on non‐extensional discourse—the Descriptive Constraint—and that is more general than anything Gödel appears to have had in mind. The proof of this constraint is constructed without appeal to logical equivalences, without assuming that a semantic theory must treat sentences as having references, without presupposing anything contentious about the semantics of singular terms, and without commitment to any particular semantics for definite descriptions. A constraint on facts, situations, states of affairs, and propositions—indeed on anything that is expressed or represented sententially—drops out as a trivial consequence of a constraint on non‐extensional discourse. The three sections of the chapter are: Principles of Conversion for Descriptions; Gödel's Proof in Quinean Format; and A Stronger Slingshot? (shrink)

Let E be a Σ1 1 equivalence relation for which there does not exist a perfect set of inequivalent reals. If 0# exists or if V is a forcing extension of L, then there is a good ▵1 2 well-ordering of the equivalence classes.

This article refines a foundational tenet of rational choice theory known as the principle of description invariance. Attempts to apply this principle to human agents with imperfect knowledge have paid insufficient attention to two aspects: first, agents’ epistemic situations, i.e. whether and when they recognize alternative descriptions of an object to be equivalent; and second, the individuation of objects of description, i.e. whether and when objects count as the same or different. An important consequence is that many apparent (...) ‘framing effects’ may not violate the principle of description invariance, and the subjects of these effects may not be irrational. (shrink)

We consider Borel equivalence relations E induced by actions of the infinite symmetric group, or equivalently the isomorphism relation on classes of countable models of bounded Scott rank. We relate the descriptive complexity of the equivalence relation to the nature of its complete invariants. A typical theorem is that E is potentially Π03 iff the invariants are countable sets of reals, it is potentially Π04 iff the invariants are countable sets of countable sets of reals, and so on. The proofs (...) use various techniques, including Vaught transforms, changing topologies, and the Scott analysis of countable models. (shrink)

We introduce the notion of -determinacy for Γ a pointclass and E an equivalence relation on a Polish space X. A case of particular interest is the case when E = EG is the shift-action o...

The hidden strength of Goodman's ingenious "new riddle of induction" lies in the perfect symmetry of grue/bleen and green/blue. The very same sentence forms used to define grue/bleen in terms of green/blue can be used to define green/blue in terms of grue/bleen by permutation of terms. Therein lies its undoing. In the artificially restricted case in which there are no additional facts that can break the symmetry, grue/bleen and green/blue are merely notational variants of the same facts; or, if they (...) represent different facts, the differences are ineffable, and no account of induction should be expected to pick between them. This still obtains in the more interesting case in which we embed grue/bleen in a grue-ified total science; the grue-ified and regular total sciences are merely equivalent descriptions of the same facts. In the most realistic case, we allow additional facts that break the symmetry and then we can also evade Goodman's new riddle by employing an account of induction rich enough to exploit these facts. Unaugmented enumerative induction is not such an account and it is the primary casualty of Goodman's new riddle. (shrink)

In this paper the descriptions of the relation semi-algebra generated by an equivalence element and the relation algebra generated by an equivalence element are unified by functorial constructions. Here the developed techniques and ideas lead to a more manageable conceptual construction of universal objects for the functors of squares and special congruences.

This paper develops the foundations of the descriptive set theory of countable Borel equivalence relations on Polish spaces with particular emphasis on the study of hyperfinite, amenable, treeable and universal equivalence relations.

Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative complexity of notions that are of interest in descriptive set theory. (...) In particular, we examine the perfect set property, determinacy, the Baire property, and Lebesgue measurability. We demonstrate that there is a separation of descriptive complexity between the perfect set property and determinacy for analytic sets of reals; we also show that the Baire property and Lebesgue measurability are both equivalent in complexity to the property of simply being a Borel set, for $\boldsymbol {\Sigma ^{1}_{2}}$ sets of reals. (shrink)

This paper addresses a certain objection to the quantificational theory of definite descriptions. According to this objection, the quantificational account cannot provide correct interpretations of definite descriptions embedded in the non-doxastic attitude ascriptions and therefore ought to be rejected. In brief, the objection says that the quantificational theory is committed to the view that a sentence of the form “The F is G” is equivalent to the claim that there is a unique F and it is G, (...) while the ascription such as, e.g., “S wants the F to be G” is not equivalent to the statement that S wants there to be a F and for it to be G. I argue that this objection is invalid as it rests on a false assumption concerning the substitutivity of the relative clauses in the non-doxastic attitude ascriptions. (shrink)

Sentences containing definite descriptions, expressions of the form ‘The F’, can be formalised using a binary quantifier ι that forms a formula out of two predicates, where ιx[F, G] is read as ‘The F is G’. This is an innovation over the usual formalisation of definite descriptions with a term forming operator. The present paper compares the two approaches. After a brief overview of the system INFι of intuitionist negative free logic extended by such a quantifier, which was (...) presented in (Kürbis 2019), INFι is first compared to a system of Tennant’s and an axiomatic treatment of a term forming ι operator within intuitionist negative free logic. Both systems are shown to be equivalent to the subsystem of INFι in which the G of ιx[F, G] is restricted to identity. INFι is then compared to an intuitionist version of a system of Lambert’s which in addition to the term forming operator has an operator for predicate abstraction for indicating scope distinctions. The two systems will be shown to be equivalent through a translation between their respective languages. Advantages of the present approach over the alternatives are indicated in the discussion. (shrink)

We show that it is impossible in quantum mechanics to describe two separated physical systems. This is due to the mathematical structure of quantum mechanics. It is possible to give a description of two separated systems in a theory which is a generalization of quantum mechanics and of classical mechanics, in the sense that this theory contains both theories as special cases. We identify the axioms of quantum mechanics that make it impossible to describe separated systems. One of these axioms (...) is equivalent to the superposition principle. We show how these findings throw a different light on the paradox of Einstein, Podolsky, and Rosen. (shrink)

In Book 1 of the Principia, Newton presented two different descriptions of orbital motion under the action of a central force. In Prop. 1, he described this motion as a limit of the action of a sequence of periodic force impulses, while in Prop. 6, he described it by the deviation from inertial motion due to a continuous force. From the start, however, the equivalence of these two descriptions has been the subject of controversies. Perhaps the earliest one (...) was the famous discussion from December 1704 to 1706 between Leibniz and the French mathematician Pierre Varignon. But confusion about this subject has remained up to the present time. Recently, Pourciau has rekindled these controversies in an article in this journal, by arguing that “Newton never tested the validity of the equivalency of his two descriptions because he does not see that his assumption could be questioned. And yet the validity of this unseen and untested equivalence assumption is crucial to Newton’s most basic conclusions concerning one-body motion” (Pourciau in Arch Hist Exact Sci 58:283–321, 2004, 295). But several revisions of Props. 1 and 6 that Newton made after the publication in 1687 of the first edition of the Principia reveal that he did become concerned to provide mathematical proof for the equivalence of his seemingly different descriptions of orbital motion in these two propositions. In this article, we present the evidence that in the second and third edition of the Principia, Newton gave valid demonstrations of this equivalence that are encapsulated in a novel diagram discussed in Sect. 4. (shrink)

We introduce an analogue of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time generalization of the (...) countable Borel equivalence relations, a key subclass of the Borel equivalence relations, and again show that several key properties carry over to the larger class. Lastly, we collect together several results from the literature regarding Borel reducibility which apply also to absolutely $\Delta^1_2$ reductions, and hence to the infinite time computable reductions. (shrink)

In a seminal paper, Aumann (1987, Econometrica 55, 1–18) showed how the choices of rational players could be analyzed in a unified state space framework. His innovation was to include the choices of the players in the description of the states, thus abolishing Savage’s (1954, The Foundations of Statistics. Wiley, New York) distinction between acts and consequences. But this simplification comes at a price: Aumann’s notion of Bayes rationality does not allow players to evaluate what would happen were they to (...) deviate from their actual choices. We show how the addition of a causal structure to the framework enables us to analyze such counterfactual statements, and use it to introduce a notion of causal rationality. Under a plausible causal independence condition, the two notions are shown to be equivalent. If we are prepared to accept this condition we can dispense with the causal apparatus and retain Aumann’s original framework. (shrink)

We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L ′ are two logics and μ is an asymptotic measure on finite structures, then $\scr{L}\equiv _{\text{a.e.}}\scr{L}^{\prime}(\mu)$ means that there is a class C of finite structures with μ (C)=1 (...) and such that L and L ′ define the same queries on C. We carry out a systematic investigation of $\equiv _{\text{a.e.}}$ with respect to the uniform measure and analyze the $\equiv _{\text{a.e.}}$ -equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework. (shrink)

We construct two Borel equivalence relations on the generalized Baire space κκ, κ ω, with the property that neither of them is Borel reducible to the other. A small modification of the construction shows that the straightforward generalization of the Glimm-Effros dichotomy fails.

Explicit description of maps definable by formulæ of the second order intuitionistic propositional calculus is given on two classes of linear Heyting algebras—the dense ones and the ones which possess successors. As a consequence, it is shown that over these classes every formula is equivalent to a quantifier free formula in the dense case, and to a formula with quantifiers confined to the applications of the successor in the second case.

Logics designed to deal with vague statements typically allow algebraic semantics such that propositions are interpreted by elements of residuated lattices. The structure of these algebras is in general still unknown, and in the cases that a detailed description is available, to understand its significance for logics can be difficult. So the question seems interesting under which circumstances residuated lattices arise from simpler algebras in some natural way. A possible construction is described in this paper.Namely, we consider pairs consisting of (...) a Brouwerian algebra and an equivalence relation. The latter is assumed to be in a certain sense compatible with the partial order, with the formation of differences, and with the formation of suprema of pseudoorthogonal elements; we then call it an s-equivalence relation. We consider operations which, under a suitable additional assumption, naturally arise on the quotient set. The result is that the quotient set bears the structure of a residuated lattice. Further postulates lead to dual BL-algebras. In the case that we begin with Boolean algebras instead, we arrive at dual MV-algebras. (shrink)

Chs. 8 and 9 convert the two basic forms of slingshot argument—one used by Alonzo Church, W. V. Quine, and Donald Davidson, the other by Kurt Gödel—into knock‐down deductive proofs that Donald Davidson's and Richard Rorty's cases against facts and the representation of facts are unfounded, and their slingshot arguments for discrediting the existence of facts unsatisfactory. The proofs are agnostic on key semantic issues; in particular, they assume no particular account of reference and do not even assume that sentences (...) have references. Using this procedure, Ch. 8 shows that cleaned‐up versions of the slingshot arguments used by Davidson, Church, and Quine demonstrate theses weaker than those their authors were seeking—the impossibility of facts and non‐truth‐functional connectives. This is primarily because the arguments depend upon logical equivalences and theories of definite descriptions that must satisfy certain semantic conditions if the aforementioned logical equivalences are to obtain. The four sections of the chapter are: Introductory Remarks; The Quinean Strategy; An Incomplete Connective Proof; and A Complete Connective Proof. (shrink)

The thesis of 3D/4D equivalence states that every three-dimensional description of the world is translatable without remainder into a four-dimensional description, and vice versa. In representing an object in 3D or in 4D terms we are giving alternative descriptions of one and the same thing, and debates over whether the ontology of the physical world is "really" 3D or 4D are pointless. The twins paradox is shown to rest, in relativistic 4D geometry, on a reversed law of triangle inequality. (...) But considering the twins as 3D beings who age through time, the paradox implies that time passes at different rates in different reference frames, and therefore that the concept of a single global or Absolute time is unsustainable. (shrink)

Let E be an equivalence relation on the powerset of an uncountable set, which is reasonably definable. We assume that any two subsets with symmetric difference of size exactly 1 are not equivalent. We investigate whether for E there are many pairwise non equivalent sets.

We study a new formal logic LD introduced by Prof. Grzegorczyk. The logic is based on so-called descriptive equivalence, corresponding to the idea of shared meaning rather than shared truth value. We construct a semantics for LD based on a new type of algebras and prove its soundness and completeness. We further show several examples of classical laws that hold for LD as well as laws that fail. Finally, we list a number of open problems. -/- .

The "space" of Lascar strong types, on some sort and relative to a given complete theory T, is in general not a compact Hausdorff topological space. We have at least three aims in this paper. The first is to show that spaces of Lascar strong types, as well as other related spaces and objects such as the Lascar group Gal L of T, have well-defined Borel cardinalities. The second is to compute the Borel cardinalities of the known examples as well (...) as of some new examples that we give. The third is to explore notions of definable map, embedding, and isomorphism, between these and related quotient objects. We also make some conjectures, the main one being roughly "smooth if and only if trivial". The possibility of a descriptive set-theoretic account of the complexity of spaces of Lascar strong types was touched on in the paper [E. Casanovas, D. Lascar, A. Pillay and M. Ziegler, Galois groups of first order theories, J. Math. Logic1 305–319], where the first example of a "non-G-compact theory" was given. The motivation for writing this paper is partly the discovery of new examples via definable groups, in [A. Conversano and A. Pillay, Connected components of definable groups and o-minimality I, Adv. Math.231 605–623; Connected components of definable groups and o-minimality II, to appear in Ann. Pure Appl. Logic] and the generalizations in [J. Gismatullin and K. Krupiński, On model-theoretic connected components in some group extensions, preprint, arXiv:1201.5221v1]. (shrink)

Available from UMI in association with The British Library. ;A form of metaphysical inquiry is in this thesis both illustrated in detail and defended against the charge of issuing in statements which lack cognitive content. 'Categorial description' concerns the fundamental features of our conceptual scheme: the categories described are those of substance, accident, cause, space and time. ;Following Aristotle's distinction between primary and secondary substances, these two notions are addressed as equivalent to those individual or particular things and their (...) kinds. A particular thing is characterised as not being capable of occuring in the predicate position in a proposition; and as having criteria or principles of individuation and reidentification. Accidents or properties can appear in the predicate position and do not have criteria of identity. ;Secondary substances, or natural kinds, being a species of property, also fail to have criteria for individuation and reidentification. It follows that the recently revived Aristotelian essentialism, as exhibited in particular in the work of Kripke, fails to correctly characterise the category of natural kinds: in that theory, natural kinds have essential properties which enable individuation and reidentification across possible worlds. ;Efficient causation is described, against the background of the Locke-Hume dispute, as involving the concept of necessary connection between cause and effect. Rejecting the theory of Harre and Madden on causal powers, an approach by Mackie is defended whereby this connection is a reflection of our counterfactual thinking. The possible worlds essentialist approach of Lewis to counterfactuals is rejected too, as inadequate. ;Space and time, spatial and temporal relations, and places and moments in time are approached in terms of the other categories of particular and property. The obscurity of fit between these categories is identified as responsible for many philosophical puzzles concerning space and time: for example, McTaggart's 'proof' of the unreality of time; and the recent debate on the possibility of multiple times and multiple spaces. ;In the final chapter, the logical commitments of categorial description concerning conceptual relativism and the nature of reality in itself are explored. It is argued that, since categories are in large part responsible for the kinds of acts there are, a description of our categories is a description of reality itself. Since our categories do not involve the machinery of possible worlds offered by contemporary essentialist theories, those theories fail to describe reality. (shrink)

Abstract.As an undergraduate at Cambridge, Newton entered into his ‘Waste Book’ an assumption that we have named the Equivalence Assumption (The Younger): ‘‘ If a body move progressively in some crooked line [about a center of motion]..., [then this] crooked line may bee conceived to consist of an infinite number of streight lines. Or else in any point of the croked line the motion may bee conceived to be on in the tangent.’’ In this assumption, Newton somewhat imprecisely describes two (...) mathematical models, a ‘‘polygonal limit model’’ and a ‘‘tangent deflected model,’’ for ‘‘one-body motion,’’ that is, for the motion of a ‘‘body in orbit about a fixed center,’’ and then claims that these two models are equivalent. In the first part of this paper, we study the Principia to determine how the elder Newton would more carefully describe the polygonal limit and tangent deflected models. From these more careful descriptions, we then create Equivalence Assumption (The Elder), a precise interpretation of Equivalence Assumption (The Younger) as it might have been restated by Newton, after say 1687. We then review certain portions of the Waste Book and the Principia to make the case that, although Newton never restates nor even alludes to the Equivalence Assumption after his youthful Waste Book entry, still the polygonal limit and tangent deflected models, as well as an unspoken belief in their equivalence, infuse Newton’s work on orbital motion. In particular, we show that the persuasiveness of the argument for the Area Property in Proposition 1 of the Principia depends crucially on the validity of Equivalence Assumption (The Elder). After this case is made, we present the mathematical analysis required to establish the validity of the Equivalence Assumption (The Elder). Finally, to illustrate the fundamental nature of the resulting theorem, the Equivalence Theorem as we call it, we present three significant applications: we use the Equivalence Theorem first to clarify and resolve questions related to Leibniz’s ‘‘polygonal model’’ of one-body motion; then to repair Newton’s argument for the Area Property in Proposition 1; and finally to clarify and resolve questions related to the transition from impulsive to continuous forces in ‘‘De motu’’ and the Principia. (shrink)

A Cantor series expansion for a real number x with respect to a basic sequence $Q=(q_1,q_2,\dots )$, where $q_i \geq 2$, is a generalization of the base b expansion to an infinite sequence of bases. Ki and Linton in 1994 showed that for ordinary base b expansions the set of normal numbers is a $\boldsymbol {\Pi }^0_3$ -complete set, establishing the exact complexity of this set. In the case of Cantor series there are three natural notions of normality: normality, ratio (...) normality, and distribution normality. These notions are equivalent for base b expansions, but not for more general Cantor series expansions. We show that for any basic sequence the set of distribution normal numbers is $\boldsymbol {\Pi }^0_3$ -complete, and if Q is $1$ -divergent then the sets of normal and ratio normal numbers are $\boldsymbol {\Pi }^0_3$ -complete. We further show that all five non-trivial differences of these sets are $D_2(\boldsymbol {\Pi }^0_3)$ -complete if $\lim _i q_i=\infty $ and Q is $1$ -divergent. This shows that except for the trivial containment that every normal number is ratio normal, these three notions are as independent as possible. (shrink)

To describe simultaneous knowledge updates for different subgroups we propose anepistemic language with dynamic operators for actions. The language is interpreted onequivalence states (S5 states). The actions are interpreted as state transformers. Two crucial action constructors are learning and local choice. Learning isthe dynamic equivalent of common knowledge. Local choice aids in constraining theinterpretation of an action to a functional interpretation (state transformer).Bisimilarity is preserved under execution of actions. The language is applied todescribe various actions in card games.

In this paper, we give a complete algebraic description of groups elementarily equivalent to the P. Hall completion of a given free nilpotent group of finite rank over an arbitrary binomial domain. In particular, we characterize all groups elementarily equivalent to a free nilpotent group of finite rank.

A unitary transformation replaces the given description of a quantum system by an equivalent one. It is observed, however, that not all members of a set of unitarily equivalent Hamilton operators are equally well suited for identifying the corresponding classical systems. A criterion is proposed for recognizing the privileged representatives of the set. A few explicit examples are reported that show the criterion at work.

The paper provides a proof theoretic characterization of the Russellian theory of definite descriptions (RDD) as characterized by Kalish, Montague and Mar (KMM). To this effect three sequent calculi are introduced: LKID0, LKID1 and LKID2. LKID0 is an auxiliary system which is easily shown to be equivalent to KMM. The main research is devoted to LKID1 and LKID2. The former is simpler in the sense of having smaller number of rules and, after small change, satisfies cut elimination but (...) fails to satisfy the subformula property. In LKID2 an additional analysis of different kinds of identities leads to proliferation of rules but yields the subformula property. This refined proof theoretic analysis leading to fully analytic calculus with constructive proof of cut elimination is the main contribution of the paper. (shrink)

The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on , the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on . In this article we examine the effective (...) content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington establishing for any recursive ordinal α the existence of singletons whose α-jumps are Turing incomparable. (shrink)

We generalize the notion of analytic/Borel equivalence relations, orbit equivalence relations, and Borel reductions between them to their continuous and quantitative counterparts: analytic/Borel pseudometrics, orbit pseudometrics, and Borel reductions between them. We motivate these concepts on examples and we set some basic general theory. We illustrate the new notion of reduction by showing that the Gromov–Hausdorff distance maintains the same complexity if it is defined on the class of all Polish metric spaces, spaces bounded from below, from above, and from (...) both below and above. Then we show that [Formula: see text] is not reducible to equivalences induced by orbit pseudometrics, generalizing the seminal result of Kechris and Louveau. We answer in negative a question of Ben Yaacov, Doucha, Nies, and Tsankov on whether balls in the Gromov–Hausdorff and Kadets distances are Borel. In appendix, we provide new methods using games showing that the distance-zero classes in certain pseudometrics are Borel, extending the results of Ben Yaacov, Doucha, Nies, and Tsankov. There is a complementary paper of the authors where reductions between the most common pseudometrics from functional analysis and metric geometry are provided. (shrink)

That past patterns may continue in many different ways has long been identified as a problem for accounts of induction. The novelty of Goodman’s ”new riddle of induction” lies in a meta-argument that purports to show that no account of induction can discriminate between incompatible continuations. That meta-argument depends on the perfect symmetry of the definitions of grue/bleen and green/blue, so that any evidence that favors the ordinary continuation must equally favor the grue-ified continuation. I argue that this very dependence (...) on the perfect symmetry defeats the novelty of the new riddle. The symmetry can be obtained in contrived circumstances, such as when we grue-ify our total science. However, in all such cases, we cannot preclude the possibility that the original and grue-ified descriptions are merely notationally variant descriptions of the same physical facts; or if there are facts that separate them, these facts are ineffable, so that no account of induction should be expected to pick between them. In ordinary circumstances, there are facts that distinguish the regular and grue-ified descriptions. Since accounts of induction can and do call upon these facts, Goodman’s meta-argument cannot provide principled grounds for the failure of all accounts of induction. It assures us only of the failure of accounts of induction, such as unaugmented enumerative induction, that cannot exploit these symmetry breaking facts. (shrink)

As a reply to the commentary (Humphreys in Found Sci, 2012), we explore the methodological implications of seeing artificial neural networks as generic classification tools, we show in which sense the use of descriptions and models in data analysis is not equivalent to the original empirical use of epicycles in describing planetary motion, and we argue that agnostic science is essentially related to the type of problems we ask about a phenomenon and to the processes used to find (...) answers. (shrink)

It is widely accepted that EinstcinRi7;s general theory of relativity is an satisfactory description of gravity 0nly in the macroscopic limit, where quantum eiTcc1;s may be neglected. Presumably this theory is inapplicable at the Planck length, but recently much attention has been devoted to gravitational theory at intermediate length scales where quantum affects 0f matter are inescapable, but where there is an general assumption that the gravitational Held may bc treated as a classical background, augmented if necessary by quamtizcd linearized (...) pertur-. (shrink)

Checking the equivalence of two Boolean functions, or combinational circuits modeled as Boolean functions, is often desired when reliable and correct hardware components are required. The most common approaches to equivalence checking are based on simulation and model checking, which are constrained due to the popular memory and state explosion problems. Furthermore, such tools are often not user-friendly, thereby making it tedious to check the equivalence of large formulas or circuits. An alternative is to use mathematical tools, called interactive theorem (...) provers, to prove the equivalence of two circuits; however, this requires human effort and expertise to write multiple output functions and carry out interactive proof of their equivalence. In this paper, we define two simple, one formal and the other informal, gate-level hardware description languages, design and develop a formal automatic combinational circuit equivalence checker tool, and test and evaluate our tool. The tool CoCEC is based on human-assisted theorem prover Coq, yet it checks the equivalence of circuit descriptions purely automatically through a human-friendly user interface. It either returns a machine-readable proof of circuits’ equivalence or a counterexample of their inequality. The interface enables users to enter or load two circuit descriptions written in an easy and natural style. It automatically proves, in few seconds, the equivalence of circuits with as many as 45 variables. CoCEC has a mathematical foundation, and it is reliable, quick, and easy to use. The tool is intended to be used by digital logic circuit designers, logicians, students, and faculty during the digital logic design course. (shrink)

Descriptions are predicates. Here, I'll take this to mean either of two basically equivalent things: that they have extensions as their semantic values, sets of entities, in the broadest sense; or that they have type-〈e,t〉 functions as their semantic values, functions from entities, in the broadest sense, to truth values. An entity in the broadest sense is anything that can be the subject of a first-order predication. Examples are individuals, pluralities, masses, and kinds. Here I'm including entities in (...) this broadest sense because my thesis that descriptions are predicates applies to all sorts of descriptions: singular descriptions, plural definite descriptions, mass descriptions, kind descriptions, and indefinite descriptions as well. (shrink)

It can be shown that certain kinds of classical deterministic and indeterministic descriptions are observationally equivalent. Then the question arises: which description is preferable relative to evidence? This paper looks at the main argument in the literature for the deterministic description by Winnie (The cosmos of science—essays of exploration. Pittsburgh University Press, Pittsburgh, pp 299–324, 1998). It is shown that this argument yields the desired conclusion relative to in principle possible observations where there are no limits, in principle, (...) on observational accuracy. Yet relative to the currently possible observations (of relevance in practice), relative to the actual observations, or relative to in principle observations where there are limits, in principle, on observational accuracy the argument fails. Then Winnie’s analogy between his argument for the deterministic description and his argument against the prevalence of Bernoulli randomness in deterministic descriptions is considered. It is argued that while the arguments are indeed analogous, it is also important to see they are disanalogous in another sense. (shrink)

We prove that the set of properties describable by a uniform sequence of first-order sentences using at most k + 1 distinct variables is exactly equal to the set of properties checkable by a Turing machine in DSPACE[n k ] (where n is the size of the universe). This set is also equal to the set of properties describable using an iterative definition for a finite set of relations of arity k. This is a refinement of the theorem PSPACE = (...) VAR[O[1]] [8]. We suggest some directions for exploiting this result to derive trade-offs between the number of variables and the quantifier depth in descriptive complexity. (shrink)

Spatial communications are essential to the survival and social interaction of human beings. In science fiction and the near future, robots are supposed to be able to understand spatial languages to collaborate and cooperate with humans. However, it remains unknown whether human speakers regard robots as human-like social partners. In this study, human speakers describe target locations to an imaginary human or robot addressee under various scenarios varying in relative speaker–addressee cognitive burden. Speakers made equivalent perspective choices to human (...) and robot addressees, which consistently shifted according to the relative speaker–addressee cognitive burden. However, speakers’ perspective choice was only significantly correlated to their social skills when the addressees were humans but not robots. These results suggested that people generally assume robots and humans with equal capabilities in understanding spatial descriptions but do not regard robots as human-like social partners. (shrink)

In an earlier article on this journal I argued that the problem of empirical underdetermination can for the largest part be solved by theoretical virtues, and for the remaining part it can be tolerated. Here I confront two further challenges to scientific realism based on underdetermination. First, there are four classes of theories which may seem to be underdetermined even by theoretical virtues. Concerning them I argue that (i) theories produced by trivial permutations and (ii) “equivalent descriptions” are (...) compatible with the truth of standard theories; instead (iii) “as if” versions of standard theories are much worse from the point of view of theoretical virtues; finally (iv) mathematically intertranslatable theories either may become empirically decidable in the future, or can be discriminated by theoretical virtues, or realists may simply plead ignorance about their claims. Secondly, I consider Stanford’s underdetermination with respect unconceived alternatives, arguing that it essentially relies on the pessimistic meta-induction from the falsity of all past theories. Therefore, it can be resisted by (a) considering the radical advancement of present with respect to past science, and (b) arguing with selective realism that past successful theories, even if false, always included some true components. (shrink)