Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results (...) for any ideal of the r.e. degrees. (shrink)

We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.

A recursively enumerable splitting of an r.e. setAis a pair of r.e. setsBandCsuch thatA=B∪CandB∩C= ⊘. Since for such a splitting degA= degB∪ degC, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the degrees of (...) r.e. splittings and the degree splittings of a set. We say a setAhas thestrong universal splitting property if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for degA=b∪cthere is an r.e. splittingB, CofAsuch that degB=band degC=c. The goal of this paper is the study of this splitting property.In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP. (shrink)

We prove that every Turing degree a bounding some non-GL₂ degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.

It is shown that, if a, b are recursively enumerable degrees such that 0

Logic and Philosophy of Logic

Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic

Model Theory in Logic and Philosophy of Logic

Direct download (4 more)  

 

Export citation  

 

Bookmark   6 citations  

In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0.

We give a simple structural property which characterizes the r.e. sets whose (Turing) degrees are cappable. Since cappable degrees are incomplete, this may be viewed as a solution of Post's program, which asks for a simple structural property of nonrecursive r.e. sets which ensures incompleteness.

Downey and Lempp 1215–1240) have shown that the contiguous computably enumerable degrees, i.e. the c.e. Turing degrees containing only one c.e. weak truth-table degree, can be characterized by a local distributivity property. Here we extend their result by showing that a c.e. degree a is noncontiguous if and only if there is an embedding of the nonmodular 5-element lattice N5 into the c.e. degrees which maps the top to the degree a. In particular, this shows that local nondistributivity coincides with (...) local nonmodularity in the computably enumerable degrees. (shrink)

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...) disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)

We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset.

We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$ -c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $ -c.a. as shown in [9]. We also show that if cone avoidance is added then there (...) is no level below $\varepsilon _0$ which can be used to characterize the complexity of $A_1$ and $A_2$. (shrink)

We show that, in the partial ordering of the computably enumerable computable Lipschitz degrees, there is a degree a>0a>0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Since Ambos-Spies [1] has shown that, in the partial ordering of the c.e. identity-bounded Turing degrees, for any degree a>0a>0 the degrees which do not cup to a are bounded by the 1-shift a+1a+1 of a where a+1 (...) it follows that the elementary theories of the partial orderings and differ. (shrink)

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.

La puerta de entrada a la fenomenología es, según su fundador, Edmund Husserl, la "epojé", la suspensión de todas las proposiciones con las que se afirma ser a un evento en el mundo. Esta actitud es la que se presupone para abstenerse de prejuicios como lo procuran la filosofía y la ciencia desde sus inicios. Cuando se introdujo la actitud de la epojé en la época del helenismo por los escépticos y estoicos, ésta se basaba a su vez en un (...) prejuicio no controlado: en asumir que entre el ser de los sucesos y su aparecer al hombre hay un abismo que debe ser superado gracias a decisiones de la voluntad. De este voluntarismo se desarrolló más tarde el subjetivismo moderno, cuyas consecuencias ecológicas y políticas preocupan hoy en día a toda la humanidad. El pensamiento griego antes del helenismo se basaba en la equiparación de ser y aparecer sin que interviniera para nada la voluntad. Pero también esto era un prejuicio sin controlar. La nueva forma de epojé de la "fenomenología" ("doctrina del aparecer'') es la suspensión de ambos prejuicios acerca de la relación de ser y aparecer. Aparecer significa fenomenológicamente: manifestarse en el contexto de sentido de horizontes, de "mundos". Todos los mundos sean los horizontes de hombres singulares o de culturas globales pertenecen a un singular específico, el mundo en cuanto tal, lo que llamamos "el mundo-uno". El mundo-uno como horizonte universal es la dimensión del aparecer. Pero como se hizo claro en la continuación de la fenomenología por Martín Heidegger, la esencia del mundo no consiste en su carácter de horizonte. La fenomenología como apertura del camino de una filosofía después del subjetivismo tiene la tarea histórica de clarificar en qué sentido el mundo-uno es "más" que horizonte y qué significa esto para los muchos mundos. Sólo con esto se aclara la relación de ser y aparecer y el significado futuro de la voluntad para la posición del hombre en el mundo. (shrink)

Reviewed Works:Andrea Sorbi, Complexity, Logic, and Recursion Theory.Klaus Ambos-Spies, Elvira Mayordomo, Resource-Bounded Measure and Randomness.Marat Arslanov, Degree Structures in Local Degree Theory.Jose L. Balcazar, Ricard Gavalda, Montserrat Hermo, Compressibility of Infinite Binary Sequences.S. Barry Cooper, Beyond Godel's Theorem: The Failure to Capture Information Content.Robert A. Di Paola, Franco Montagna, Progressions of Theories of Bounded Arithmetic.Rodney G. Downey, On Presentations of Algebraic Structures.Sophie Fischer, Lane Hemaspaandra, Leen Torenvliet, Witness-Isomorphic Reductions and Local Search.William Gasarch, Carl H. Smith, A Survey (...) of Inductive Inference with an Emphasis on Queries.Andre Nies, A Uniformity of Degree Structures.Piergiorgio Odifreddi, Short Course on Logic, Algebra, and Topology.Andrea Sorbi, The Enumeration Degrees of the $\sigma^0_2$ Sets.Peter van Emde Boas, The Convenience of Tilings. (shrink)

La menzogna è irrinunciabile per vincere in politica? Davi ci spiega quali sono i meccanismi di persuasione a cui ricorrono taluni politici per farsi eleggere e quali le responsabilità di quegli elettori che scelgono comunque di votare chi sostiene anche ciò che non può essere vero. È indubbio che la comunicazione politica si rifaccia al simbolismo e al linguaggio delle favole; non necessariamente per occultare la realtà, ma più direttamente per esprimere con maggiore efficacia il suo messaggio. Alle celebri favole (...) di 'Biancaneve', 'Cenerentola', 'Il brutto anatroccolo' sono ricorsi infatti uomini politici del calibro di Berlusconi, Prodi, Nixon, Carter, Mitterrand e partiti quali la Democrazia Cristiana; l'hanno fatto per conquistare voti ma anche per attivare ampi meccanismi di consenso che attingessero direttamente dall'inconscio collettivo. Le conseguenze - ammonisce l'autore - possono essere molto serie, come nel caso dell'attuale politica americana che ha portato la manipolazione e l'inganno a essere riconosciuti come tratti identitari della presidenza di George W. Bush. (shrink)

I show that in his De motu animalium Aristoteles proposes a teleology of the practical on the most general zoological level, i.e. on the level common to humans and self-moving animals. A teleology of the practical is a teleological account of the highest practical goals of animal and human self-motion. I argue that Aristotle conceives of such highest practical goals as goals that are contingently related to their realizations. Animal and human self-motion is the kind of action in which certain (...) state of affairs that realize values are mechanized. (shrink)

Zusammenfassung Der Beitrag analysiert auf der Basis theoretischer Überlegungen sowie empirischer Ergebnisse Möglichkeiten und Grenzen einer „interkulturellen Öffnung“ von Sportvereinen, worunter Strukturanpassungen verstanden werden, die auf die Inklusion und Integration von Personen mit Migrationshintergrund zielen. Es wird gezeigt, inwiefern eine nachhaltige interkulturelle Öffnung der Vereine von der programmatischen Anbindung an den Vereinszweck, von der kontinuierlichen Behandlung in den Kommunikationswegen, von spezifischen Personalentscheidungen und der Kompatibilität mit der Organisationskultur abhängig ist.

This important and challenging book is the fruit of many years of engagement with Aristotle’s thinking about the soul-body relation by one of the most distingui.

This paper discusses Aristotle's notion of the practical syllogism. It is argued that the notion of ‘practical’ reasoning in the sense of reasoning which implies motion in one sense or the other is alien to Aristotle's philosophy of nature. All (at least in type) the relevant passages will be discussed. The outcome is that there are three different contexts in which it would be justified to speak of practical syllogisms: (i) human deliberation, (ii) the illustration of the triggering cause of (...) animal motion, and (iii) the teleological ex post explanationof human action. (i) is genuine, but non-deductive reasoning which does not immediately result in action/motion, whereas (ii) is not genuine reasoning, but an analogy with deductive reasoning. Finally, the relation between (i) and (ii) in Aristotle's theory of animal motion will be discussed. (shrink)

The goal of this paper is to propose a unified approach to the split scope readings of negative indefinites, comparative quantifiers, and numerals. There are two main observations that justify this approach. First, split scope shows the same kinds of restrictions across these different quantifiers. Second, split scope always involves low existential force. In our approach, following Sauerland, natural language determiner quantifiers are quantifiers over choice functions, of type <<,t>,t>. In split readings, the quantifier over choice functions scopes above other (...) operators (such as intensional verbs like must or can). Determiner quantifiers leave a choice-function trace when they move and this trace combines with the noun restriction, which is interpreted low. That split scope always involves low existential force is derived, without stipulation, from Kratzer’s idea that low existential force can be achieved via binding (into the noun restriction). (shrink)

The aim of this chapter is to explain Aristotle’s definition of the vegetative part of the soul in the De anima from a methodological point of view. I discuss Aristotle’s conception of the soul and his conception of “parts of the soul” before I turn to his definition of the vegetative part of the soul in De anima II 4. I argue that the definition of the vegetative capacity is deliberately abstract so as to cover its various activities under one (...) common heading. I also argue that the De anima deliberately avoids a positive and determinate description of the activity of the soul that is properly responsible for the vegetative functions, and that Aristotle offers such a positive and determinate description in his works dedicated to the actions and affections “common to body and soul”. (shrink)

Proceedings of the NATO Advanced Study Institute on Proof and Computation, held in Marktoberdorf, Germany, July 20 - August 1, 1993.