Results for 'Friedberg‐Muchnik theorem'

964 found
Order:
  1.  16
    (1 other version)Topological framework for finite injury.Kyriakos Kontostathis - 1992 - Mathematical Logic Quarterly 38 (1):189-195.
    We formulate an abstract version of the finite injury method in the form of the Baire category theorem. The theorem has the following corollaries: The Friedberg-Muchnik pair of recursively enumerable degrees, the Sacks splitting theorem, the existence of a minimal degree below 0′ and the Shoenfield jump theorem.
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  28
    Possible degrees in recursive copies II.C. J. Ash & J. F. Knight - 1997 - Annals of Pure and Applied Logic 87 (2):151-165.
    We extend results of Harizanov and Barker. For a relation R on a recursive structure /oA, we give conditions guaranteeing that the image of R in a recursive copy of /oA can be made to have arbitrary ∑α0 degree over Δα0. We give stronger conditions under which the image of R can be made ∑α0 degree as well. The degrees over Δα0 can be replaced by certain more general classes. We also generalize the Friedberg-Muchnik Theorem, giving conditions on a (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  3.  23
    Fragments of Kripke–Platek set theory and the metamathematics of α\alpha α -recursion theory.Sy-David Friedman, Wei Li & Tin Lok Wong - 2016 - Archive for Mathematical Logic 55 (7-8):899-924.
    The foundation scheme in set theory asserts that every nonempty class has an ∈\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}\in \end{document}-minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set theory and α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}α\alpha \end{document}-recursion theory. We take KP set theory without foundation as the base theory. We show that KP-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}^-\end{document} + Π1\documentclass[12pt]{minimal} \usepackage{amsmath} (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  4.  98
    (1 other version)Three theorems on recursive enumeration. I. decomposition. II. maximal set. III. enumeration without duplication.Richard M. Friedberg - 1958 - Journal of Symbolic Logic 23 (3):309-316.
  5.  45
    What is Quantum Mechanics? A Minimal Formulation.R. Friedberg & P. C. Hohenberg - 2018 - Foundations of Physics 48 (3):295-332.
    This paper presents a minimal formulation of nonrelativistic quantum mechanics, by which is meant a formulation which describes the theory in a succinct, self-contained, clear, unambiguous and of course correct manner. The bulk of the presentation is the so-called “microscopic theory”, applicable to any closed system S of arbitrary size N, using concepts referring to S alone, without resort to external apparatus or external agents. An example of a similar minimal microscopic theory is the standard formulation of classical mechanics, which (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  38
    Game arguments in computability theory and algorithmic information theory.Alexander Shen - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 655--666.
    We provide some examples showing how game-theoretic arguments can be used in computability theory and algorithmic information theory: unique numbering theorem (Friedberg), the gap between conditional complexity and total conditional complexity, Epstein–Levin theorem and some (yet unpublished) result of Muchnik and Vyugin.
    Direct download  
     
    Export citation  
     
    Bookmark  
  7. Definability in the recursively enumerable degrees.André Nies, Richard A. Shore & Theodore A. Slaman - 1996 - Bulletin of Symbolic Logic 2 (4):392-404.
    §1. Introduction. Natural sets that can be enumerated by a computable function always seem to be either actually computable or of the same complexity as the Halting Problem, the complete r.e. set K. The obvious question, first posed in Post [1944] and since then called Post's Problem is then just whether there are r.e. sets which are neither computable nor complete, i.e., neither recursive nor of the same Turing degree as K?Let be the r.e. degrees, i.e., the r.e. sets modulo (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8.  44
    A splitting theorem for the Medvedev and Muchnik lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
    This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  9.  53
    A lift of a theorem of Friedberg: A Banach-Mazur functional that coincides with no α-recursive functional on the class of α-recursive functions.Robert A. di Paola - 1981 - Journal of Symbolic Logic 46 (2):216-232.
    R. M. Friedberg demonstrated the existence of a recursive functional that agrees with no Banach-Mazur functional on the class of recursive functions. In this paper Friedberg's result is generalized to both α-recursive functionals and weak α-recursive functionals for all admissible ordinals α such that $\lambda , where α * is the Σ 1 -projectum of α and λ is the Σ 2 -cofinality of α. The theorem is also established for the metarecursive case, α = ω 1 , where (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  10.  33
    A stronger form of a theorem of Friedberg.Kempachiro Ohashi - 1964 - Notre Dame Journal of Formal Logic 5 (1):10-12.
  11.  5
    On an extension of a theorem of Friedberg.Thomas C. Mclaughlin - 1962 - Notre Dame Journal of Formal Logic 3:270.
    Direct download  
     
    Export citation  
     
    Bookmark  
  12.  19
    On an extension of a theorem of Friedberg.Thomas G. McLaughlin - 1962 - Notre Dame Journal of Formal Logic 3 (4):270-273.
  13.  24
    Jump Theorems for REA Operators.Alistair H. Lachlan & Xiaoding Yi - 1993 - Mathematical Logic Quarterly 39 (1):1-6.
    In [2], Jockusch and Shore have introduced a new hierarchy of sets and operators called the REA hierarchy. In this note we prove analogues of the Friedberg Jump Theorem and the Sacks Jump Theorem for many REA operators. MSC: 03D25, 03D55.
    Direct download  
     
    Export citation  
     
    Bookmark  
  14.  45
    Finite injury and Σ1-induction.Michael Mytilinaios - 1989 - Journal of Symbolic Logic 54 (1):38 - 49.
    Working in the language of first-order arithmetic we consider models of the base theory P - . Suppose M is a model of P - and let M satisfy induction for σ 1 -formulas. First it is shown that the Friedberg-Muchnik finite injury argument can be performed inside M, and then, using a blocking method for the requirements, we prove that the Sacks splitting construction can be done in M. So, the "amount" of induction needed to perform the known finite (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  15.  49
    Implicit Definability in Arithmetic.Stephen G. Simpson - 2016 - Notre Dame Journal of Formal Logic 57 (3):329-339.
    We consider implicit definability over the natural number system $\mathbb{N},+,\times,=$. We present a new proof of two theorems of Leo Harrington. The first theorem says that there exist implicitly definable subsets of $\mathbb{N}$ which are not explicitly definable from each other. The second theorem says that there exists a subset of $\mathbb{N}$ which is not implicitly definable but belongs to a countable, explicitly definable set of subsets of $\mathbb{N}$. Previous proofs of these theorems have used finite- or infinite-injury (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  94
    A decomposition of the Rogers semilattice of a family of d.c.e. sets.Serikzhan A. Badaev & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (2):618-640.
    Khutoretskii's Theorem states that the Rogers semilattice of any family of c.e. sets has either at most one or infinitely many elements. A lemma in the inductive step of the proof shows that no Rogers semilattice can be partitioned into a principal ideal and a principal filter. We show that such a partitioning is possible for some family of d.c.e. sets. In fact, we construct a family of c.e. sets which, when viewed as a family of d.c.e. sets, has (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  17.  12
    Effective Concept Classes of PAC and PACi Incomparable Degrees, Joins and Embedding of Degrees.Dodamgodage Gihanee M. Senadheera - 2023 - Bulletin of Symbolic Logic 29 (2):298-299.
    The Probably Approximately Correct (PAC) learning is a machine learning model introduced by Leslie Valiant in 1984. The PACi reducibility refers to the PAC reducibility independent of size and computation time. This reducibility in PAC learning resembles the reducibility in Turing computability. The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples.Due to the resemblance to Turing Reducibility, we suspected that there could be incomparable PACi and PAC degrees for the PACi and PAC (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18.  55
    First-Order Logic in the Medvedev Lattice.Rutger Kuyper - 2015 - Studia Logica 103 (6):1185-1224.
    Kolmogorov introduced an informal calculus of problems in an attempt to provide a classical semantics for intuitionistic logic. This was later formalised by Medvedev and Muchnik as what has come to be called the Medvedev and Muchnik lattices. However, they only formalised this for propositional logic, while Kolmogorov also discussed the universal quantifier. We extend the work of Medvedev to first-order logic, using the notion of a first-order hyperdoctrine from categorical logic, to a structure which we will call the hyperdoctrine (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  19.  92
    Almost weakly 2-generic sets.Stephen A. Fenner - 1994 - Journal of Symbolic Logic 59 (3):868-887.
    There is a family of questions in relativized complexity theory--weak analogs of the Friedberg Jump-Inversion Theorem--that are resolved by 1-generic sets but which cannot be resolved by essentially any weaker notion of genericity. This paper defines aw2-generic sets. i.e., sets which meet every dense set of strings that is r.e. in some incomplete r.e. set. Aw2-generic sets are very close to 1-generic sets in strength, but are too weak to resolve these questions. In particular, it is shown that for (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark  
  20.  40
    Kolmogorov–Loveland randomness and stochasticity.Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan - 2006 - Annals of Pure and Applied Logic 138 (1):183-210.
    An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  21. Healing the Wound: Rossi on Kantian Critique, Community, and the Remedies to the “Dear Self”.Pablo Muchnik - 2021 - Philosophia 49 (5):1817-1835.
    The main purpose of these introductory remarks is to give the reader a sense of Philip Rossi’s philosophical project and its importance. I will then advance an interpretation of what motivates Kant’s commitment to community, and, on its basis, object to Rossi’s views on radical evil –a point which affects how one should conceive the moral vocation of humanity and the role that politics and religion play within it. My reconstruction concludes with a sketch of how the five contributions to (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  75
    Clipping our dogmatic wings: The role of religion’s Parerga in our moral education.Pablo Muchnik - 2019 - Educational Philosophy and Theory 51 (13):1381-1391.
    In a note introduced into the second edition of Religion within the Boundaries of Mere Reason (1794), Kant assigns a systematic role to the General Remarks at the end of each Part of his book. He calls those Remarks, “as it were, parerga to religion within the boundaries of pure reason; they do not belong within it yet border on it” (RGV 6:52). As Kant sees them, the parerga are only a “secondary occupation” that consists in removing transcendent obstacles. This (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  23. Caveat homo-sapiens-reason and unreason.F. Friedberg - 1981 - Journal of Thought 16 (1):73-82.
     
    Export citation  
     
    Bookmark  
  24.  49
    The Punishing Other.Anne Friedberg - 1990 - American Journal of Semiotics 7 (3):43-51.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  25.  22
    Competing Enlightenment Narratives: A Case Study Of Rorty’s Anti-Kantianism.Pablo Muchnik - 2008 - Cambridge Scholar Publishers.
    This paper provides a defense of the ethical/political dimensions of Kant’s liberalism by gauging the strength of the critique of one of its most acerbic contemporary critics, Richard Rorty. Rorty’s dissatisfaction with Kant’s position can be traced back to a narrative of the coming to age of our culture, which bears surprising similarities to Kant’s account of the Enlightenment. Yet, in Rorty’s version of the story, Kant’s philosophy is mistakenly assimilated to a form of “Platonism.” This is due, I argue, (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  26.  35
    Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets.Andrej Muchnik & Alexei Semenov - 2006 - Annals of Pure and Applied Logic 141 (3):437-441.
    Let μ be a universal lower enumerable semi-measure . Any computable upper bound for μ can be effectively separated from zero with a constant . Computable positive lower bounds for μ can be nontrivial and allow one to construct natural examples of hypersimple sets.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  27. Kant on the Sources of Evil.Pablo Muchnik - 2009 - Proceedings of the 10th International Kant Congress, Walter de Gruyter, Berlin:287-297.
  28. (1 other version)Review: Michalson (ed.), Kant’s Religious Constructivism.Pablo Muchnik (ed.) - 2014 - Cambridge University Press.
    This paper suggests a general interpretative strategy for reading Religion within the Boundaries of Mere Reason namely, as an attempt to find a middle ground between what Kant considers two forms of excess: the appeal to a transcendent conception of God and the denial of any claim that presupposes God’s existence. To make my case, I use the example of two contemporary thinkers (Wolterstorff and Rorty) and trace their dispute to the antinomic character of “religious reason.” Putting things this way (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  29.  54
    Reflections on Robert Louden's Kant's Human Being: Essays on His Theory of Human Nature.Pablo Muchnik - 2013 - Kantian Review 18 (3):461-471.
    Since his pioneering Kant’s Impure Ethics (Oxford University Press, 2000), Robert Louden has helped us put a human face to the abstract a priori principles of Kant’s pure practical philosophy. Through a continuous spate of publications, some of which are gathered in his latest book Kant’s Human Being, Louden has managed to show the importance of the empirical dimension of Kantian ethics—a dimension which had been ignored or dismissed for more than two hundred years by scholars obsessed with “keeping philosophy (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  30. “Substance and the Emergence of the Cogito in Meditation II”.Pablo Muchnik - 2003 - Review Journal of Philosophy and Social Science.
     
    Export citation  
     
    Bookmark  
  31. Review: Sasso, The Fragmented Will – Kant on Evil.Pablo Muchnik - 2004 - Review Journal of Philosophy and Social Science (unknown):unknown.
  32. Elias Canetti y la férrea pureza de un premio Nobel.Mario Muchnik - 2006 - Daimon: Revista Internacional de Filosofía 38:49-60.
    No categories
     
    Export citation  
     
    Bookmark  
  33.  26
    (2 other versions)Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
  34.  49
    The U.S. in the U.S.S.R.: American Literature through the Filter of Recent Soviet Publishing and Criticism.Maurice Friedberg - 1976 - Critical Inquiry 2 (3):519-583.
    The advent of the post-Stalin "thaw," particularly the period after 1956, was marked by a spectacular expansion in the publishing of translated Western writing and also, on occasion, of editions in the original languages: the virtual ban on import of Western books was, as of 1975, never relaxed. The more permissive political atmosphere favored the publication of a vastly larger variety of Western authors and titles and provision for the Soviet public of much larger quantities of such books in the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  35.  36
    (1 other version)A criterion for completeness of degrees of unsolvability.Richard Friedberg - 1957 - Journal of Symbolic Logic 22 (2):159-160.
  36. Caveat Homo Sapiens.F. Friedberg - 1999 - Journal of Thought 34 (4):73-82.
     
    Export citation  
     
    Bookmark  
  37.  11
    Calmodulin's warm embrace.F. Friedberg & A. R. Rhoads - 1994 - Bioessays: News and Reviews in Molecular, Cellular and Developmental Biology 16 (11):853.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  38. Immanuel Kant.Pablo Muchnik - 2011 - In Dale Southerton (ed.), Encyclopedia of Consumer Culture. Sage Publications. pp. 827-828.
    This article offers a short biography of Kant and explains why his work was so important.
     
    Export citation  
     
    Bookmark  
  39.  46
    Kant's Theory of Evil: An Essay on the Dangers of Self-Love and the Aprioricity of History.Pablo Muchnik - 2009 - Lexington Books.
    An Essay on Kant’s Theory of Evil shows the centrality of the doctrine of radical evil within Kant's critical philosophy. Combining textual accuracy with systematic ethical theory, it fills the gaps Kant left open in his own doctrine, and provides a non-mystifying account of human immorality, which shows the pertinence of the Kantian view to our moral concerns.
    Direct download  
     
    Export citation  
     
    Bookmark   14 citations  
  40. An alternative proof of the universal propensity to evil.Pablo Muchnik - 2009 - In Sharon Anderson-Gold & Pablo Muchnik (eds.), Kant's Anatomy of Evil. New York: Cambridge University Press.
    In this paper, I develop a quasi-transcendental argument to justify Kant’s infamous claim “man is evil by nature.” The cornerstone of my reconstruction lies in drawing a systematic distinction between the seemingly identical concepts of “evil disposition” (böseGesinnung) and “propensity to evil” (Hang zumBösen). The former, I argue, Kant reserves to describe the fundamental moral outlook of a single individual; the latter, the moral orientation of the whole species. Moreover, the appellative “evil” ranges over two different types of moral failure: (...)
    Direct download  
     
    Export citation  
     
    Bookmark   10 citations  
  41.  27
    More on revolutions in biology.Felix Friedberg & Jan A. Witkowski - 1997 - Bioessays 19 (2):181-182.
  42. Christliche Verantwortung und Soziale Marktwirtschaft aus katholischer Sicht.Walter Friedberger - 1983 - In Michael Bartelt & Rudolf Uertz (eds.), Kirche und Wirtschaft: Fachkonferenz der Politischen Akademie der Konrad-Adenauer-Stiftung e.V. vom 19. bis 21. Januar 1983 in Schloss Eichholz. Melle: E. Knoth.
    No categories
     
    Export citation  
     
    Bookmark  
  43.  14
    Gendering security: The substantive representation of women in the Israeli parliament.Chen Friedberg & Reut Itzkovitch-Malka - 2018 - European Journal of Women's Studies 25 (4):419-439.
    The study focuses on the links between gender and national security in the legislative arena in Israel, considering whether men and women legislators prioritize security differently, alongside other thematic policy areas. The centrality of national security issues in Israeli politics makes it a good case study for these questions, as it enhances existing gendered stereotypes. The article examines two competing hypotheses. The first suggests that Israeli female legislators will mostly refrain from addressing national security policy issues, focusing instead on softer (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  44.  23
    Hot news: temperature‐sensitive humans explain hereditary disease.Errol C. Friedberg - 2001 - Bioessays 23 (8):671-673.
    The skin‐cancer‐prone hereditary disease xeroderma pigmentosum is typically characterized by defective nucleotide excision repair (NER) of DNA. However, since all subunits of the core basal transcription factor TFIIH are required for both RNA polymerase II basal transcription and NER, some mutations affecting genes that encode TFIIH subunits can result in clinical phenotypes associated with defective basal transcription. Among these is a syndrome called trichothiodystrophy (TTD) in which the prominent features are brittle hair and nails, and dry scaly skin. A recent (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  45.  7
    Thoughts about life.Felix Friedberg - 1954 - New York,: Philosophical Library.
  46. Incompatibilism and Ontological Priority in Kant's Theory of Free Will.Pablo Muchnik (ed.) - 2008
  47.  91
    Kant's Anatomy of Evil.Sharon Anderson-Gold & Pablo Muchnik (eds.) - 2009 - New York: Cambridge University Press.
    Kant infamously claimed that all human beings, without exception, are evil by nature. This collection of essays critically examines and elucidates what he must have meant by this indictment. It shows the role which evil plays in his overall philosophical project and analyses its relation to individual autonomy. Furthermore, it explores the relevance of Kant's views for understanding contemporary questions such as crimes against humanity and moral reconstruction. Leading scholars in the field engage a wide range of sources from which (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  48.  40
    Rethinking Kant.Pablo Muchnik (ed.) - 2018 - Cambridge Scholars Publishing.
    The series Rethinking Kant, now in its fourth volume, has become a mirror of Kantian studies in North America. It gathers papers presented at the various study groups of the North American Kant Society, along with contributions from hosts, session chairs, and keynote speakers. Because of its broad and unique composition, it offers a sample of a whole generation of Kantian thought, ranging from recent PhDs, to up and coming young scholars, to some well-established and influential players in the field. (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  49. Rethinking Kant Vol.5.Pablo Muchnik & Oliver Thorndike (eds.) - 2018 - Cambridge Scholars Publishing.
    The series Rethinking Kant, now in its fifth volume, has become a mirror of Kantian studies in North America. It gathers papers presented at the various study groups of the North American Kant Society, along with contributions from hosts, session chairs, and keynote speakers. Because of its broad and unique composition, it offers a sample of a whole generation of Kantian thought, ranging from recent Ph.Ds, to up and coming young scholars, to some well-established and influential players in the field. (...)
     
    Export citation  
     
    Bookmark  
  50.  11
    Caveat Homo Sapiens: The Furtive Mind.Felix Friedberg - 2000 - Upa.
    Do we have free will? Can we trust our memories? How well do you know yourself? Felix Friedberg answers these questions in Caveat Homo Sapiens, arguing that humanity, while limited by the non-existence of free will, gains salvation in the ability to respond. Subjectivity, memory, psychotropic drugs, and the existence of the subconscious mind are explored, especially concerning their impact on self-knowledge and perception. Accessible to the general educated reader, the book will also be of interest to psychiatrists, sociologists and (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
1 — 50 / 964