<span class='Hi'>span><span class='Hi'>span><span class='Hi'>span><span class='Hi'>span><span class='Hi'>span><span class='Hi'>span><span class='Hi'>span> readers of Greek ethics tend to (...) class='Hi'> favour those accounts of the virtuous ideal according to which virtue involves the development of our non-rational—appetitive and emotional—<span class='Hi'>span> motivations as well as of our rational motivations.<span class='Hi'>span> So our contemporaries find much of interest and sympathy in Aristotle’s conception of virtue as a condition in which reason does not simply override our appetites and emotions,<span class='Hi'>span> but these non-rational motivations themselves <span class='Hi'>span>‘speak with the same voice as reason’<span class='Hi'>span>.2 By contrast,<span class='Hi'>span> the Stoic.<span class='Hi'>span>. (shrink)
Let T be a complete O-minimal theory in a language L. We first give an elementary proof of the result (due to Marker and Steinhorn) that (...) class='Hi'>all types over Dedekind complete models of T are definable. Let L * be L together with a unary predicate P. Let T * be the L * -theory of all pairs (N, M), where M is a Dedekind complete model of T and N is an |M| + -saturated elementary extension of N (and M is the interpretation of P). Using the definability of types result, we show that T * is complete and we give a simple set of axioms for T * . We also show that for every L * -formula φ(x) there is an L-formula ψ(x) such that $T^\ast \models (\forall \mathbf{x})(P(\mathbf{x}) \rightarrow (\phi(\mathbf{x}) \mapsto \psi (\mathbf{x}))$ . This yields the following result: Let M be a Dedekind complete model of T. Let φ(x, y) be an L-formula where l(y) = k. Let $\mathbf{X} = \{X \subset M^k$ : for some a in an elementary extension N of M, X = φ (a,y N ∩ M k }. Then there is a formula ψ(y, z) of L such that X = {ψ (y, b) M : b in M}. (shrink)
Let R be an o-minimal expansion of (R. <. +) and (ϕk)k∈N be a sequence of positive real numbers such that limk→+∝ ƒ(ϕk)/ϕk+1 = (...) class='Hi'>0 for every ƒ: R → R definable in R. (Such sequences always exist under some reasonable extra assumptions on R, in particular, if R is exponentially bounded or if the language is countable.) Then (R. (S)) is d-minimal, where S ranges over all subsets of cartesian powers of the range of ϕ. (shrink)
O'Donnell, J. R. Anton Charles Pegis on the occasion of his retirement.--Conlan, W. J. The definition of faith according to a question of MS. Assisi 138 (...) class='Hi'>: study and edition of text.--Spade, P. V. Five logical tracts by Richard Lavenham.--Maurer, A. Henry of Harclay's disputed question on the plurality of forms.--Brown, V. Giovanni Argiropulo on the agent intellect: an edition of Ms. Magliabecchi V 42.--Synan, E. A. The Exortacio against Peter Abelard's Dialogus inter philosophum, Iudaeum et Christianum.--Fitzgerald, W. Nugae Hyginianae.--Sheehan, M. M. Marriage and family in English conciliar and synodal legislation.--Shook, L. K. Riddles relating to the Anglo-Saxon scriptorium.--Boyle, L. E. The De regno and the two powers.--Colledge, E. A Middle English Christological poem.--Gough, M. R. E. Three forgotten martyrs of Anazarbus in Cilicia.--Häring, N. Chartres and Paris revisited.--Hayes, W. Greek recentiores, (Ps.) Basil, Adversus eunomium, IV-V.--Owens, J. The physical world of Parmenides. (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)
In this paper which consists of two parts (Teil I and Teil II) we champion Diophantus of Alexandria and Isabella BaÅ¡makova against Norbert Schappacher. In two (...) class='Hi'>publications ([Schappacher 1998a] and [Schappacher 1998b]) he puts forward inter alia two propositions: Questioning Diophantusâ originality he considers affirmatively the possibility that the Arithmetica are the joint work of a team of authors like Bourbaki. And he calls BaÅ¡makovaâs claim (in [BaÅ¡makova 1972]) that Diophantus uses negative numbers, a nonsense , reproaching her for her thoughtlessness . Teil I: First, we disprove Schappacherâs Bourbaki thesis. Second, we investigate the semantic meaning and historical significance of Diophantusâ keywords $ λvarepsilon tildeιψιζ and á½ÏαÏξιζ. Next, we discuss Schappacherâs epistemology of the history of mathematics and defend BaÅ¡makovaâs methods. Finally we analyse in detail three problems from Diophantusâ Arithmetica (and their solutions) given by Thomas Heath and Helmuth Gericke as proof of the their claim that Diophantus did not use negative numbers. Teil II: In this Part, we give 33 places where Diophantus uses negative quantities as intermediate results; they appear as differences a â b of positive rational numbers, the subtrahend b being bigger than the minuend a; they each represent the (negative) basis ( πλvarepsilonυρacuteα ) of a square number ( τvarepsilonτρacuteαγω ν o ζ ), which is afterwards computed by the formula (a - b) 2 = a 2 + b 2 - 2ab $ . Finally, we report how the topic Diophantus and the negative numbers has been dealt with by translators and commentators from Maximus Planudes onwards. Und er kommt zu dem Ergebnis: âªNur ein Traum war das Erlebnis. Weilâ«, so schlieβt er messerscharf, âªnicht sein k a n n, was nicht sein d a r f.â« CHRISTIAN MORGENSTERN: Palmstrm. (shrink)
We say that E is R-sparse if f(Ek) has no interior, for each k 2 N and f : Rk ! R de nable in R. (Throughout, (...) \de nable" means \de nable without parameters".) In this note, we consider the extent to which basic metric and topological properties of subsets of R de nable in (R;E)# are determined by the corresponding properties of subsets of R de nable in (R;E), when R is an o-minimal expansion of (R;<;+;0;1) and E is R-sparse. The precise statement of the main result is a bit complicated, but we can state some special cases now. (shrink)
Different researchers use "the philosophy of automated theorem p r o v i n g " t o cover d i f f e r e n t (...) class='Hi'> concepts, indeed, different levels of concepts. Some w o u l d count such issues as h o w to e f f i c i e n t l y i n d e x databases as part of the philosophy of automated theorem p r o v i n g . Others wonder about whether f o r m u l a s should be represented as strings or as trees or as lists, and call this part of the philosophy of automated theorem p r o v i n g . Yet others concern themselves w i t h what k i n d o f search should b e embodied i n a n y automated theorem prover, or to what degree any automated theorem prover should resemble Prolog. Still others debate whether natural deduction or semantic tableaux or resolution is " b e t t e r " , a n d c a l l t h i s a part of the p h i l o s o p h y of automated theorem p r o v i n g . Some people wonder whether automated theorem p r o v i n g should be " h u m a n oriented" or "machine o r i e n t e d " — sometimes arguing about whether the internal p r o o f methods should be " h u m a n - I i k e " or not, sometimes arguing about whether the generated proof should be output in a f o r m u n d e r s t a n d a b l e by p e o p l e , and sometimes a r g u i n g a b o u t the d e s i r a b i l i t y o f h u m a n intervention in the process of constructing a proof. There are also those w h o ask such questions as whether we s h o u l d even be concerned w i t h completeness or w i t h soundness of a system, or perhaps we should instead look at very efficient (but i n c o m p l e t e ) subsystems or look at methods of generating models w h i c h might nevertheless validate invalid arguments. A n d a l l of these have been v i e w e d as issues in the philosophy of automated theorem proving. Here, I w o u l d l i k e to step back from such i m p l e m e n t - ation issues and ask: " W h a t do we really think we are doing when we w r i t e an automated theorem prover?" My reflections are perhaps idiosyncratic, but I do think that they put the different researchers* efforts into a broader perspective, and give us some k i n d of handle on w h i c h directions we ourselves m i g h t w i s h to pursue when constructing (or extending) an automated theorem proving system. A logic is defined to be (i) a vocabulary and formation rules ( w h i c h tells us w h a t strings of symbols are w e l l - formed formulas in the logic), and ( i i ) a definition of ' p r o o f in that system ( w h i c h tells us the conditions under which an arrangement of formulas in the system constitutes a proof). Historically speaking, definitions of ' p r o o f have been given in various different manners: the most c o m m o n have been H i l b e r t - s t y l e ( a x i o m a t i c ) , Gentzen-style (consecution, or sequent), F i t c h - s t y l e (natural deduction), and Beth-style (tableaux).. (shrink)
Are there, in addition to the various actual objects that make up the world, various possible objects? Are there merely possible people, for example, or merely possible (...) electrons, or even merely possible kinds? We certainly talk as if there were such things. Given a particular sperm and egg, I may wonder whether that particular child which would result from their union would have blue eyes. But if the sperm and egg are never in fact brought together, then there is no actual object that my thought is about.1 Or again, in the semanti cs for modal logic we presuppose an ontology of possibilia twice over.2 For first, we coutenance various possible worlds, in addition to the actual world; and second, each of these worlds is taken to be endowed with its own domai n of objects. These will be the actual objects of the world in question, but they need not be actual simpliciter, i.e., actual objects of our world. W ha t a r e w e t o m a k e o f such discourse? There are four options: (i) the discourse is taken to be unintelligible; (ii) it is taken to be intelligible but nonfactual, i.e. as not in the business of stating facts; (iii) it is taken to be factual but reducible to discourse involving no reference to possibilia; (iv) it is taken to be both factual and irreducible.3 These options range from a fullblooded form of actualism at one extreme to a full-blooded form of possibilism at the other. The two intermediate positions are possibilist in that they accept the intelligibility of possibilist discourse but actualist in that they attempt to dispense with its prima facie commitment to possibilia. All four positions have found advocates in the literature. Quine, in his less irenic moments, favours option (i); Forbes ([85], p. 94) advocates option (ii), at least for certain parts of possibilist discourse; many philosophers, including Adams [74] and myself, opt for (iii); while Lewis [86] and Stalnaker [75] have endorsed versions of (iv), that differ in how full-blooded they take the possible objects to be.. (shrink)
The symbolism introduced earlier provides a convenient vehicle for examining the status and consistency of Aristotle's three diverse justifications and for explaining how he means to (...) class='Hi'>avoid Protagorean relativism without embracing Platonic absolutism. When the variables ‘ x ’ and ‘ y ’ are allowed to range over the groups of free men in a given polis as well as over individual free men, the formula for the Aristotelian conception of justice expresses the major premiss of Aristotle's three justifications: (1) (∀ x )(∀ y ) (P(x)·W(x)/P(y)·W(y)=V(T(x))/V(T(y)))Democracy is justified by adding a minor premiss to the effect that as a group the many ( m ) are superior (>) in virtue and wealth to the few best men ( f ): 85 (2 d ) (P(m) · W(m)) > (P(f) · W(f)) (3 d ) V(T(m))>V(T(f))Absolute kingship is justified when a godlike man ( g ) appears in a polis who is incommensurably superior (≫) in virtue and wealth to all the remaining free men ( r ): (2 k ) (P(g) · W(g)) ≫ (P(r) · W(r)) (3 k ) V(T(g)) ≫ V(T(r))True aristocracy requires a more complex justification, which was symbolized in Section 4. These justifications are compatible with each other since they apply to different situations. The polises where democracy and true aristocracy are justified contain no godlike men, and the polis in which democracy is justified differs from that in which true aristocracy is justified in containing a large group of free men who individually have little virtue ( Pol. III.11.1281b23-25, 1282a25-26). Each of the justifications is a valid deductive argument. Aristotle affirms the major premiss they share on the basis of a twofold appeal to nature. The principle of distributive justice, the concept as distinguished from the various conceptions of distributive justice, is itself according to nature ( Pol. VII.3.1325b7-10) and so too is one particular standard of worth, the standard of the best polis. Consequently, the question of the status of these three justifications, whether they are purely hypothetical or not, is a question about the minor premiss or premisses of each. In the case of the democratic premiss Aristotle's answer is straightforward: it is sometimes but not always true ( Pol. III.11.1281bl5-21). Hence the justification of democracy is not purely hypothetical. Nor is the justification of absolute kingship. The man who is “like a god among men” ( Pol. III.13.1284a10-11) would be a man of heroic virtue (see VII.14.1332bl6-27); and such a man, Aristotle says, is “rare” ( σπávιoη ) (not nonexistent) ( E.N. VII.1.1145a27-28). The minor premisses of the aristocratic argument describe a situation where all of the free men in a given polis have sufficient wealth for the exercise of the moral and intellectual virtues and where all of the older free men of the polis are men of practical wisdom. In the Politics Aristotle makes only the modest claim that such a situation is possible: It is not possible for the best constitution to come into being without appropriate equipment [that is, the appropriate quality and quantity of territory and of citizens and noncitizens]. Hence one must presuppose many things as one would wish them to be, though none of them must be impossible ( Pol. VII.4.1325b37-38; see also II.6.1265al7-18). But Aristotle appears to subscribe to the principle that every possibility is realized at some moment of time ( Top. 11.11.115bl7-18, Met. Θ.4.1047b3-6, N.2.1088b23-25). This principle together with the claim that the situation described is possible entails that the situation sometimes occurs. Thus even Aristotle's justification of true aristocracy is not purely hypothetical. The final question is Aristotle's way of avoiding Protagorean relativism without embracing Platonic absolutism. The relativist, along with everyone else ( E.N. V.3.1131a13-14, Pol. III.12.1282bl8), can accept the principle of distributive justice: Q(x)/Q(y) = V(T(x))/V(T(y)) And he can concede that particular instances of this principle, particular conceptions of justice, accurately describe the modes of distributing political authority that appear just to particular polises and to particular philosophers. What he denies is that there is any basis for ranking these various conceptions of justice or for singling one out as the best (Plato, Theaet. 172A-B). Aristotle, following in Plato's track ( Laws X.888D7-890D8), maintains against the relativist that nature provides such a basis. But he departs from Plato in his conception of nature. For Plato “the just by nature” ( τó ρυσει δίκ↑oν }) ( Rep. VI.501B2) is the Form of justice, an incorporeal entity ( Phdo. 65D4-5, Soph. 246B8) that exists beyond time and space ( Tim. 37C6-38C3, 51E6-52B2), whereas for Aristotle the sensible world is the realm of nature ( Met. A.1.1069a30-b2). Thus in appealing to nature Aristotle does not appeal to a transcendent standard. Nor does he appeal to his main criterion of the natural, namely, happening always or for the most part. Aristotle's theory of justice is anchored to nature by means of the polis described in Politics VII and VIII, and he regards this polis as natural because it fosters the true end of human life and because its social and political structure reflects the natural hierarchy of human beings and the natural stages of life. Thus the nature that Aristotle's theory of justice is ultimately founded on is human nature. (shrink)
Are there, in addition to the various actual objects that make up the world, various possible objects? Are there merely possible people, for example, or merely possible (...) electrons, or even merely possible kinds? We certainly talk as if there were such things. Given a particular sperm and egg, I may wonder whether that particular child which would result from their union would have blue eyes. But if the sperm and egg are never in fact brought together, then there is no actual object that my thought is about.1 Or again, in the semanti cs for modal logic we presuppose an ontology of possibilia twice over.2 For first, we coutenance various possible worlds, in addition to the actual world; and second, each of these worlds is taken to be endowed with its own domai n of objects. These will be the actual objects of the world in question, but they need not be actual simpliciter, i.e., actual objects of our world. W ha t a r e w e t o m a k e o f such discourse? There are four options: (i) the discourse is taken to be unintelligible; (ii) it is taken to be intelligible but nonfactual, i.e. as not in the business of stating facts; (iii) it is taken to be factual but reducible to discourse involving no reference to possibilia; (iv) it is taken to be both factual and irreducible.3 These options range from a fullblooded form of actualism at one extreme to a full-blooded form of possibilism at the other. The two intermediate positions are possibilist in that they accept the intelligibility of possibilist discourse but actualist in that they attempt to dispense with its prima facie commitment to possibilia. All four positions have found advocates in the literature. Quine, in his less irenic moments, favours option (i); Forbes ([85], p. 94) advocates option (ii), at least for certain parts of possibilist discourse; many philosophers, including Adams [74] and myself, opt for (iii); while Lewis [86] and Stalnaker [75] have endorsed versions of (iv), that differ in how full-blooded they take the possible objects to be. My focus in the present article is on the third option.. (shrink)
A is for Alice and astronomers arguing about acceleration -- B is for Bernard's body-exchange machine -- C is for the Catholic cannibal -- D is for Maxwell (...) class='Hi'>'s demon -- E is for evolution (and an embarrassing problem with it) -- F is for the forms lost forever to the prisoners of the cave -- G is for Galileo's gravitational balls -- H is for Hume's shades -- I is for the identity of indiscernibles -- J is for Henri Poincaré and alternative geometries -- K is for the Kritik and Kant's kind of thought experiments -- L is for Lucretius' spear -- M is for Mach's motionless chain -- N is for Newton's bucket -- O is for Olbers' paradox -- P is for Parfit's person -- Q is for the questions raised by thought experiments quotidiennes -- R is for the rule-ruled room -- S is for Salvatius' ship, sailing along its own space-time line -- T is for the time-travelling twins -- U is for the universe, and Einstein's attempts to understand it -- V is for the vexed case of the violinist -- W is for Wittgenstein's beetle -- X is for xenophanes and thinking by examples -- Y is for counterfactuals and a backwards approach to history -- Z is for Zeno and the mysteries of infinity. (shrink)
In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can …nd a single marked object in a database of size (...) N by using only O(pN ) queries of the oracle that identi…es the object. His result was generalized to the case of …nding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either M or K, M < K, our task is to determine which is the case. We show how to solve this problem with a high probability of success using only iterations of Grover’s basic step (and no other algorithm). Let m be the required number of iterations; we prove that under certain restrictions on the sizes of M and K the estimation.. (shrink)
Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space (...) class='Hi'>of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of homology n-spheres {P k e } k ∈ ω which are also hypersurfaces, such that P k e is diffeomorphic to the standard n-sphere S n (denoted P k e ≈ diff S n ) iff T e halts on input k, and in this case the connected sum N k e =M ♯ P k e ≈ diff M , so N k e ∈ Met(M), and N k e is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time σ e (k) of T e on inputs y i } ∈ ω of c.e. sets so that for all i the settling time of the associated Turing machine for A i dominates that for A i + 1 , even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization." From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {A i } i ∈ ω above, not merely G öodel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T 5 (see §). (shrink)
A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n (...) class='Hi'>)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP. (shrink)
A nonnegative interger is called a number, a collection of numbers a set and a collection of sets a class. We write ε for the set of (...) all numbers, o for the empty set, N(α) for the cardinality of $\alpha, \subset$ for inclusion and $\subset_+$ for proper inclusion. Let α, β 1 ,...,β k be subsets of some set ρ. Then α' stands for ρ-α and β 1 ⋯ β k for β 1 ∩ ⋯ ∩ β k . For subsets α 1 ,..., α r of ρ we write: $\alpha_\sigma - \{x \in v \ (\nabla i) \lbrack i \in \sigma \Rightarrow x \in \alpha_i\rbrack\} \text{for} \sigma \subset (1, \ldots, r),\\ s_i = \sum \{N(\alpha_\sigma) \mid \sigma \subset (1,\ldots, r) \& N(\sigma) = i\}, \text{for} 0 \leqq i \leqq r$ . Note that α 0 = v, hence s 0 = N(v). If the set v is finite, the classical inclusion-exclusion principle (abbreviated IEP) states $(a) N(\alpha_1 \cup \cdots \cup \alpha_r) = \sum^r_{t=1} (-1)^{t-1} s_t = \sum_{o \subset_+\sigma \subset (1,\ldots,r)}$ (b) N(α' 1 ⋯ α' r ) = ∑ r t=0 (-1) t s t = ∑ (-1) N(σ) N (α σ ). In this paper we generalize (a) and (b) to the case where α 1 ,⋯, α r are subsets of some countable but isolated set v. Then the role of the cardinality N(α) of the set α is played by the RET (recursive equivalence type) Req α of α. These generalization of (a) and (b) are proved in § 3. Since they involve recursive distinctness, this notion is discussed in § 2. In § 4l we consider a natural extension of "the sum of the elements of a finite set σ" to the case where σ is countable. § 5 deals with valuations, i.e., certain mappings μ from classes of isolated sets into the collection λ of all isols which permit us to further generalize IEP by substituting μ(α) for $\operatorname{Req} \alpha$. (shrink)
Let g E(m, n)=o mean that n is the Gödel-number of the shortest derivation from E of an equation of the form (m)=k. Hao (...) class='Hi'>Wang suggests that the condition for general recursiveness mn(g E(m, n)=o) can be proved constructively if one can find a speedfunction s s, with s(m) bounding the number of steps for getting a value of (m), such that mn s(m) s.t. g E(m, n)=o. This idea, he thinks, yields a constructivist notion of an effectively computable function, one that doesn't get us into a vicious circle since we intuitively know, to begin with, that certain proofs are constructive and certain functions effectively computable. This paper gives a broad possibility proof for the existence of such classes of effectively computable functions, with Wang's idea of effective computability generalized along a number of dimensions. (shrink)
The logical flow graphs of sequent calculus proofs might contain oriented cycles. For the predicate calculus the elimination of cycles might be non-elementary and this was (...) class='Hi'>shown in [Car96]. For the propositional calculus, we prove that if a proof of k lines contains n cycles then there exists an acyclic proof with O(k n+l ) lines. In particular, there is a polynomial time algorithm which eliminates cycles from a proof. These results are motivated by the search for general methods on proving lower bounds on proof size and by the design of more efficient heuristic algorithms for proof search. (shrink)
We say that a first order formula ϕ distinguishes a structure M over a vocabulary L from another structure M′ over the same vocabulary if ϕ is (...) true on M but false on M′. A formula ϕ defines an L-structure M if ϕ distinguishes M from any other non-isomorphic L-structure M′. A formula ϕ identifies an n-element L-structure M if ϕ distinguishes M from any other non-isomorphic n-element L-structure M′. We prove that every n-element structure M is identifiable by a formula with quantifier rank less than (1 − 1/2k)n + k2 − k + 4 and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than $(1-\frac{1}{2k})n+k^{2}-k+4$ quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than $n-\sqrt{n}+k^{2}+k$ quantifiers suffice to identify M and, as long as we keep the number of universal quantifiers bounded by a constant, at total $n-O(\sqrt{n})$ quantifiers are necessary. (shrink)
Metaphysics and language: Quine, W. V. O. On the individuation of attributes. Körner, S. On some relations between logic and metaphysics. Marcus, R. B. Does the principle (...) of substitutivity rest on a mistake? Van Fraassen, B. C. Platonism's pyrrhic victory. Martin, R. M. On some prepositional relations. Kearns, J. T. Sentences and propositions.--Basic and combinatorial logic: Orgass, R. J. Extended basic logic and ordinal numbers. Curry, H. B. Representation of Markov algorithms by combinators.--Implication and consistency: Anderson, A. R. Fitch on consistency. Belnap, N. D., Jr. Grammatical propaedeutic. Thomason, R. H. Decidability in the logic of conditionals. Myhill, J. Levels of implication.--Deontic, epistemic, and erotetic logic: Bacon, J. Belief as relative knowledge. Wu, K. J. Believing and disbelieving. Kordig, C. R. Relativized deontic modalities. Harrah, D. A system for erotetic sentences. (shrink)
Let R Õ [1,n]3k ¥ [1,n]k. We define R = {y Œ [1,n]k:($xŒA3)(R(x,y))}. We say that R is strictly dominating if and (...) class='Hi'> only if for all x,yŒ[1,n]k, if R(x,y) then max(x) < max(y). (shrink)
Let K be a function field of one variable over a constant field C of finite transcendence degree over C. Let M/K be a finite extension (...) class='Hi'>and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K. Then there exists a set W' of K-primes such that Hilbert's Tenth Problem is not decidable over $O_{K,W'} = \{x \in K\mid ord_\mathfrak{p} x \geq 0, \forall\mathfrak{p} \notin W'\}$ , and the set (W' $\backslash$ W) ∪ (W $\backslash$ W') is finite. Let K be a function field of one variable over a constant field C finitely generated over Q. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K and the degree of all the primes in W is bounded by b ∈ N. Then there exists a set W' of K-primes such that Z has a Diophantine definition over O K ,W', and the set (W' $\backslash$ W) ∪ (W $\backslash$ W') is finite. (shrink)
High-spin states in the odd-odd N = Z nucleus Co-54 have been investigated by the fusion-evaporation reaction Si-28(S-32,1 alpha 1p1n)Co-54. Gamma- (...) class='Hi'>ray information gathered with the Ge detector array Gammasphere was correlated with evaporated particles detected in the charged particle detector system Microball and a 1 pi neutron detector array. A significantly extended excitation scheme of Co-54 is presented, which includes a candidate for the isospin T = 1, 6(+) state of the 1f(7/2)(-2) multiplet. The results are compared to large-scale shell-model calculations in the fp shell. Effective interactions with and without isospin-breaking terms have been used to probe isospin symmetry and isospin mixing. A quest for deformed high-spin rotational cascades proved negative. This feature is discussed by means of cranking calculations. (shrink)
Theorists of the Russian conservatism have made a considerable contribution to the development of axiology, the philosophy of history and comparativistics. In their studies of the local (...) civilisations existing at different times and at different places they have focused on the dynamics of their origin, development, collapse or transformation into new civilisational forms. The best known slavophiles such as A. Khomyakov, K. Axakov, I. Kireyevskiy saw the mission of the Russian civilisation in synthesising Europe and Russia which has preserved the true Christianity – the Orthodoxy. According to N. Danilevskiy, the founder of the culturohistorical school of thought, Europe has an irreconcilable hostility towards Russia. He proves that Europe and Russia are two different culturohistoricaltypes (local civilisations). He understood Russia’s mission as that of unification of Slavic peoples. K. Leontiev develops the so-called theory of Byzantism, according to which the West is doomed and Russia will be saved thanks to its Orthodoxy and the oriental despotism underlying its statehood. He advocates a merger between Russian and oriental traditions. From the point of view of the proponents of the Eurasian theory such as P. Savitskiy, N. Trubetskoy, etc., the merger has already occurred, so Russians should be viewed as Eurasians and Russia as a Eurasian civilisation. Russian thinkers were criticising the so-called Eurocentrism in their efforts to prove that progress should be measured not only by the accumulation of material wealth, but also by the development of various spiritual aspects of human beings. The anthroposociogenesis does not have any predetermined patterns, its development is of co-evolutionary, often broken, discrete nature. (shrink)
We define in precise terms the basic properties that an ‘ideal propositional paraconsistent logic’ is expected to have, and investigate the relations between them. This leads to (...) a precise characterization of ideal propositional paraconsistent logics. We show that every three-valued paraconsistent logic which is contained in classical logic, and has a proper implication connective, is ideal. Then we show that for every n > 2 there exists an extensive family of ideal n -valued logics, each one of which is not equivalent to any k -valued logic with k < n. (shrink)
