Search results for 'Reducibility' (try it on Scholar)

1000+ found
Sort by:
  1. John Bacon (1986). Supervenience, Necessary Coextensions, and Reducibility. Philosophical Studies 49 (March):163-76.score: 24.0
    Supervenience in most of its guises entails necessary coextension. Thus theoretical supervenience entails nomically necessary coextension. Kim's result, thus strengthened, has yet to hit home. I suspect that many supervenience enthusiasts would cool at necessary coextension: they didn't mean to be saying anything quite so strong. Furthermore, nomically necessary coextension can be a good reason for property identification, leading to reducibility in principle. This again is more than many supervenience theorists bargained for. They wanted supervenience without reducibility. It (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. Martin Koerwien (2009). Comparing Borel Reducibility and Depth of an Ω-Stable Theory. Notre Dame Journal of Formal Logic 50 (4):365-380.score: 24.0
    In "A proof of Vaught's conjecture for ω-stable theories," the notions of ENI-NDOP and eni-depth have been introduced, which are variants of the notions of NDOP and depth known from Shelah's classification theory. First, we show that for an ω-stable first-order complete theory, ENI-NDOP allows tree decompositions of countable models. Then we discuss the relationship between eni-depth and the complexity of the isomorphism relation for countable models of such a theory in terms of Borel reducibility as introduced by Friedman (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  3. Dieter Spreen (2005). Strong Reducibility of Partial Numberings. Archive for Mathematical Logic 44 (2):209-217.score: 24.0
    A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice.In addition, Ershov’s completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Daniele Marsibilio & Andrea Sorbi (2012). Bounded Enumeration Reducibility and its Degree Structure. Archive for Mathematical Logic 51 (1-2):163-186.score: 24.0
    We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by ≤be, which is a natural extension of s-reducibility ≤s. We show that ≤s, ≤be, and enumeration reducibility do not coincide on the ${\Pi^0_1}$ –sets, and the structure ${\boldsymbol{\mathcal{D}_{\rm be}}}$ of the be-degrees is not elementarily equivalent to the structure of the s-degrees. We show also that the first order theory of ${\boldsymbol{\mathcal{D}_{\rm be}}}$ is computably isomorphic to true second order arithmetic: this answers an (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Quinn Culver (2014). Polynomial Clone Reducibility. Archive for Mathematical Logic 53 (1-2):1-10.score: 22.0
    Polynomial clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone ${\fancyscript{C}}$ , a sequence ${B\in X^{\omega}}$ is ${\fancyscript{C}}$ -reducible to ${A \in {X}^{\omega}}$ if there is an algorithm that computes B from A using only effectively selected functions from ${\fancyscript{C}}$ . We show that if A is Kurtz random and ${\fancyscript{C}_{1} (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  6. B. R. George (2013). Knowing‐'Wh', Mention‐Some Readings, and Non‐Reducibility. Thought: A Journal of Philosophy 2 (2):166-177.score: 21.0
    This article presents a new criticisms of reductive approaches to knowledge-‘wh’ (i.e., those approaches on which whether one stands in the knowledge-‘wh’ relation to a question is determined by whether one stands in the knowledge-‘that’ relation to some answer(s) to the question). It argues in particular that the truth of a knowledge-‘wh’ attribution like ‘Janna knows where she can buy an Italian newspaper’ depends not only on what Janna knows about the availability of Italian newspapers, but on what she believes (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Kate Copestake (1997). On Nondeterminism, Enumeration Reducibility and Polynomial Bounds. Mathematical Logic Quarterly 43 (3):287-310.score: 21.0
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  8. Karol Habart & K. Habart (1992). Bounds in the Turing Reducibility of Functions. Mathematical Logic Quarterly 38 (1):423-430.score: 21.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  9. Sui Yuefei (1994). A New Reducibility Between Turing‐ and Wtt‐Reducibility. Mathematical Logic Quarterly 40 (1):106-110.score: 21.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  10. Fuad Aleskerov & Yetkin Çinar (2008). 'Q-Pareto-Scalar' Two-Stage Extremization Model and its Reducibility to One-Stage Model. Theory and Decision 65 (4):325-338.score: 21.0
    A two-stage sequential choice model is studied, the first stage being defined by q-Pareto multicriterial choice rule, and the second stage being defined by scalar extremization model. In this model, at the first stage the q-Pareto rule choses alternatives which are not only undominated in terms of Pareto comparison, but also includes into choice the alternatives which are dominated by no more than q alternatives. Since the choice set of the first-stage usually contains too many elements, obtained set is used (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Karl-Georg Niebergall (2000). On the Logic of Reducibility: Axioms and Examples. [REVIEW] Erkenntnis 53 (1-2):27-61.score: 18.0
    This paper is an investigation into what could be a goodexplication of ``theory S is reducible to theory T''''. Ipresent an axiomatic approach to reducibility, which is developedmetamathematically and used to evaluate most of the definitionsof ``reducible'''' found in the relevant literature. Among these,relative interpretability turns out to be most convincing as ageneral reducibility concept, proof-theoreticalreducibility being its only serious competitor left. Thisrelation is analyzed in some detail, both from the point of viewof the reducibility axioms and (...)
    No categories
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  12. Pierdaniele Giaretta (1998). Liar, Reducibility and Language. Synthese 117 (3):355-374.score: 18.0
    First, language and axioms of Church's paper 'Comparison of Russell's Resolution of the Semantical Antinomies with that of Tarski' are slightly modified and a version of the Liar paradox tentatively reconstructed. An obvious natural solution of the paradox leads to a hierarchy of truth predicates which is of a different kind from the one defined by Church: it depends on the enlargement of the semantical vocabulary and its levels do not differ in the ramified-type-theoretical sense. Second, two attempts are made (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  13. Harvey Friedman & Lee Stanley (1989). A Borel Reducibility Theory for Classes of Countable Structures. Journal of Symbolic Logic 54 (3):894-914.score: 18.0
    We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought of (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  14. E. Hermann (1992). 1-Reducibility Inside an M-Degree with Maximal Set. Journal of Symbolic Logic 57 (3):1046-1056.score: 18.0
    The structure of the l-degrees included in an m-degree with a maximal set together with the l-reducibility relation is characterized. For this a special sublattice of the lattice of recursively enumerable sets under the set-inclusion is used.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  15. Douglas Cenzer (1984). Monotone Reducibility and the Family of Infinite Sets. Journal of Symbolic Logic 49 (3):774-782.score: 18.0
    Let A and B be subsets of the space 2 N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2 N into 2 N such that A = Φ -1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, $a \subset b$ implies $\Phi (a) \subset \Phi(b)$ . The set A is said to be monotone (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Harvey Friedman, Borel and Baire Reducibility.score: 18.0
    The Borel reducibility theory of Polish equivalence relations, at least in its present form, was initiated independently in [FS89] and [HKL90]. There is now an extensive literature on this topic, including fundamental work on the Glimm-Effros dichotomy in [HKL90], on countable Borel equivalence relations in [DJK94], and on Polish group actions in [BK96].
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  17. John T. Gill Iii & Paul H. Morris (1974). On Subcreative Sets and S-Reducibility. Journal of Symbolic Logic 39 (4):669 - 677.score: 18.0
    Subcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets with (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  18. Edwin D. Mares (2007). The Fact Semantics for Ramified Type Theory and the Axiom of Reducibility. Notre Dame Journal of Formal Logic 48 (2):237-251.score: 18.0
    This paper uses an atomistic ontology of universals, individuals, and facts to provide a semantics for ramified type theory. It is shown that with some natural constraints on the sort of universals and facts admitted into a model, the axiom of reducibility is made valid.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  19. Steffen Lempp & Manuel Lerman (1992). The Existential Theory of the Poset of R.E. Degrees with a Predicate for Single Jump Reducibility. Journal of Symbolic Logic 57 (3):1120-1130.score: 18.0
    We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  20. Román Sasyk & Asger Törnquist (2009). Borel Reducibility and Classification of von Neumann Algebras. Bulletin of Symbolic Logic 15 (2):169-183.score: 18.0
    We announce some new results regarding the classification problem for separable von Neumann algebras. Our results are obtained by applying the notion of Borel reducibility and Hjorth's theory of turbulence to the isomorphism relation for separable von Neumann algebras.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  21. Longyun Ding (2012). Borel Reducibility and Hölder(Α) Embeddability Between Banach Spaces. Journal of Symbolic Logic 77 (1):224-244.score: 18.0
    We investigate Borel reducibility between equivalence relations $E(X;p)=X^{\mathbb{N}}/\ell_{p}(X)'s$ where X is a separable Banach space. We show that this reducibility is related to the so called Hölder(α) embeddability between Banach spaces. By using the notions of type and cotype of Banach spaces, we present many results on reducibility and unreducibility between E(L r ; p)'s and E(c 0 ; p)'s for r, p ∈ [1, +∞). We also answer a problem presented by Kanovei in the affirmative by (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  22. D. A. Bočvar (1979). Measures of Kearnels of Reducibility Axioms and Singlets. Studia Logica 38 (4):393 - 400.score: 18.0
    The present paper is a generalization and further development of the theory of Kernel measures of reducibility axioms formulated in [1], [2], [3] in. the years 1969–1973. In this paper logical connections of Kernel measures with some set-theoretical notions are studied and some suggestions related to these connections are formulated.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  23. Johanna N. Y. Franklin & Frank Stephan (2010). Schnorr Trivial Sets and Truth-Table Reducibility. Journal of Symbolic Logic 75 (2):501-521.score: 18.0
    We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  24. Ernst Kleinert (2007). On the Reducibility of Relations: Variations on a Theme of Peirce. Transactions of the Charles S. Peirce Society 43 (3):509 - 520.score: 18.0
    : The paper presents some mathematical aspects of the question of reducibility of relations. After giving a formal definition of reducibility we present the basic result (due to Herzberger) to the effect that relations of valency at least 3 are always reducible if the cardinality of the relation is at most equal to the cardinality of the underlying set (which is automatically the case if this set is infinite). In contrast to this, if the term "reduction" is given (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  25. René David (2001). Normalization Without Reducibility. Annals of Pure and Applied Logic 107 (1-3):121-130.score: 18.0
    In [gallier], general results (due to Coppo, Dezani and Veneri) relating properties of pure lambda terms and their typability in some systems with conjunctive types are proved in a uniform way by using the reducibility method.This paper gives a very short proof of the same results (actually, one of them is a bit stronger) using purely arithmetical methods.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  26. Edward L. Keenan (1993). Natural Language, Sortal Reducibility and Generalized Quantifiers. Journal of Symbolic Logic 58 (1):314-325.score: 16.0
    Recent work in natural language semantics leads to some new observations on generalized quantifiers. In § 1 we show that English quantifiers of type $ $ are booleanly generated by their generalized universal and generalized existential members. These two classes also constitute the sortally reducible members of this type. Section 2 presents our main result--the Generalized Prefix Theorem (GPT). This theorem characterizes the conditions under which formulas of the form Q1x 1⋯ Qnx nRx 1⋯ xn and q1x 1⋯ qnx nRx (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  27. Hermann Weidemann (2004). Aristotle on the Reducibility of All Valid Syllogistic Moods to the Two Universal Moods of the First Figure (APrA7, 29b1–25). [REVIEW] History and Philosophy of Logic 25 (1):73-78.score: 16.0
    In Prior Analytics A7 Aristotle points out that all valid syllogistic moods of the second and third figures as well as the two particular moods of the first figure can be reduced to the two universal first-figure moods Barbara and Celarent. As far as the third figure is concerned, it is argued that Aristotle does not want to say, as the transmitted text suggests, that only those two valid moods of this figure whose premisses are both universal statements are directly (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  28. Andrzej Wiśniewski (1994). On the Reducibility of Questions. Erkenntnis 40 (2):265-284.score: 16.0
    The concepta question is reducible to a non-empty set of questions is defined and examined. The basic results are: (1) each question which is sound relative to some of its presuppositions is reducible to some set of binary (i.e. having exactly two direct answers) questions; (b) each question which has a finite number of direct answers is reducible to some finite set of binary questions; (c) if entailment is compact, then each normal question (i.e. sound relative to its presuppositions) is (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  29. Gert-Jan C. Lokhorst (forthcoming). Mally's Deontic Logic: Reducibility and Semantics. Journal of Philosophical Logic:1-11.score: 16.0
    We discuss three aspects of the intuitionistic reformulation of Mally’s deontic logic that was recently proposed (Journal of Philosophical Logic 42, 635–641, (2013)). First, this reformulation is more similar to Standard Deontic Logic than appears at first sight: like Standard Deontic Logic, it is Kanger reducible and Anderson reducible to alethic logic and it has a semantical interpretation that can be read in deontic terms. Second, this reformulation has an extension that provides 100% of the theorems stated by Mally himself (...)
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  30. Andrzej Wisniewski (1994). On the Reducibility of Questions. Erkenntnis 40 (2):265 - 284.score: 16.0
    The concept a question is reducible to a non-empty set of questions is defined and examined. The basic results are: (1) each question which is sound relative to some of its presuppositions is reducible to some set of binary (i.e. having exactly two direct answers) questions; (b) each question which has a finite number of direct answers is reducible to some finite set of binary questions; (c) if entailment is compact, then each normal question (i.e. sound relative to its presuppositions) (...)
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  31. William E. Seager (2006). Rosenberg, Reducibility and Consciousness. Psyche.score: 15.0
    Rosenberg’s general argumentative strategy in favour of panpsychism is an extension of a traditional pattern. Although his argument is complex and intricate, I think a model that is historically significant and fundamentally similar to the position Rosenberg advances might help us understand the case for panpsychism. Thus I want to begin by considering a Leibnizian argument for panpsychism.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  32. W. V. Quine (1936). On the Axiom of Reducibility. Mind 45 (180):498-500.score: 15.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  33. Carlo Cellucci (1974). On the Role of Reducibility Principles. Synthese 27 (1-2):93 - 110.score: 15.0
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  34. J. M. Shorter (1962). Facts, Logical Atomism and Reducibility. Australasian Journal of Philosophy 40 (3):283 – 302.score: 15.0
    In the first part of the article the author discusses the use of the word 'fact'. In the second he uses his conclusions to "throw light on some of the discussions of the logical atomists." he discusses austin, Russell, And strawson. The author concludes that it a mistake to identify questions of ontology with questions of language, Which arises because of a confusion with the term 'fact'. (staff).
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  35. Ausonio Marras (1993). Supervenience and Reducibility: An Odd Couple. Philosophical Quarterly 44 (171):215-222.score: 15.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  36. Harvey Friedman, Axiomatization of Set Theory by Extensionality, Separation, and Reducibility.score: 15.0
    We discuss several axiomatizations of set theory in first order predicate calculus with epsilon and a constant symbol W, starting with the simple system K(W) which has a strong equivalence with ZF without Foundation. The other systems correspond to various extensions of ZF by certain large cardinal hypotheses. These axiomatizations are unusually simple and uncluttered, and are highly suggestive of underlying philosophical principles that generate higher set theory.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  37. Harold Kincaid (1987). Supervenience Doesn't Entail Reducibility. Southern Journal of Philosophy 25 (3):343-56.score: 15.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  38. John Myhill (1951). Report on Some Investigations Concerning the Consistency of the Axiom of Reducibility. Journal of Symbolic Logic 16 (1):35-42.score: 15.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  39. Philip Nochlin (1953). Reducibility and Intentional Words. Journal of Philosophy 50 (October):625-637.score: 15.0
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  40. Greg Hjorth (2005). Bi-Borel Reducibility of Essentially Countable Borel Equivalence Relations. Journal of Symbolic Logic 70 (3):979 - 992.score: 15.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  41. G. Glas (2002). Churchland, Kandel, and Dooyeweerd on the Reducibility of Mind States. Philosophia Reformata 67 (2):148-172.score: 15.0
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  42. Barbara F. Csima & Richard A. Shore (2007). The Settling-Time Reducibility Ordering. Journal of Symbolic Logic 72 (3):1055 - 1071.score: 15.0
    To each computable enumerable (c.e.) set A with a particular enumeration {As}s∈ω, there is associated a settling function mA(x), where mA(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >st A) if for every computable function f, for all but finitely many x, mB(x) > f(m₄(x)). This settling-time ordering, which is a natural extension to an ordering of the (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  43. I. I. I. Gill & Paul H. Morris (1974). On Subcreative Sets and s-Reducibility. Journal of Symbolic Logic 39 (4):669-677.score: 15.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  44. Kwangho Hyun (2014). Additive Property and the Physical Reducibility of the Mind. Open Journal of Philosophy 4 (2):91-95.score: 15.0
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  45. Shih-Chao Liu (1963). A Note on Many-One Reducibility. Journal of Symbolic Logic 28 (1):35-42.score: 15.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  46. Ronald V. Book (1975). Review: Richard M. Karp, Raymond E. Miller, James W. Thatcher, Reducibility Among Combinatorial Problems. [REVIEW] Journal of Symbolic Logic 40 (4):618-619.score: 15.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  47. Philippe de Rouilhan (1996). Towards Finishing Off the Axiom of Reducibility. Philosophia Scientiae 1 (3):17-35.score: 15.0
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  48. Karol Habart (1991). Bounds in Weak Truth-Table Reducibility. Notre Dame Journal of Formal Logic 32 (2):233-241.score: 15.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  49. Mariya I. Soskova & S. Barry Cooper (2008). How Enumeration Reducibility Yields Extended Harrington Non-Splitting. Journal of Symbolic Logic 73 (2):634 - 655.score: 15.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  50. Donald A. Martin (1970). Review: Paul R. Young, A Note on Pseudo-Creative Sets and Cylinders; Paul R. Young, On Semi-Cylinders, Splinters, and Bounded Truth-Table Reducibility; Paul R. Young, On Pseudo-Creative Sets, Splinters, and Bounded-Truth-Table Reducibility. [REVIEW] Journal of Symbolic Logic 35 (2):335-335.score: 15.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 1000