bluuebunny/crossref_metadata_2025_split huggingface dataset:
Eventually infinite time Turing machine degrees: infinite time decidable reals
Authors: Welch P.D. 
Published: May 2006

AbstractWe characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the Lζ-stables. It also implies that the machines devised are “Σ2 Complete” amongst all such other possible machines. It is shown that least upper bounds of an “eventual jump” hierarchy exist on an initial segment.
Model companions of theories with an automorphism
Authors: Kikyo Hirotaka 
Published: May 2006

AbstractFor a theory T in L, Tσ is the theory of the models of T with an automorphism σ. If T is an unstable model complete theory without the independence property, then Tσ has no model companion. If T is an unstable model complete theory and Tσ has the amalgamation property, then Tσ has no model companion. If T is model complete and has the fcp, then Tσ has no model completion.
Nowhere precipitousness of some ideals
Authors: Matsubara Yo , Shioya Masahiro 
Published: May 2006

In this paper we will present a simple condition for an ideal to be nowhere precipitous. Through this condition we show nowhere precipitousness of fundamental ideals onPkλ, in particular the non-stationary idealNSkλunder cardinal arithmetic assumptions.In this sectionIdenotes a non-principal ideal on an infinite setA. LetI+=PA/I(ordered by inclusion as a forcing notion) andI∣X= {Y⊂A:Y⋂X∈I}, which is also an ideal onAforX∈I+. We refer the reader to [8, Section 35] for the general theory of generic ultrapowers associated with an ideal. We recallIis said to be precipitous if ⊨I+“Ult(V, Ġ) is well-founded” [9].The central notion of this paper is a strong negation of precipitousness [1]:Definition.Iis nowhere precipitous ifI∣Xis not precipitous for everyX∈ I+i.e., ⊨I+“Ult(V, Ġ) is ill-founded.”It is useful to characterize nowhere precipitousness in terms of infinite games (see [11, Section 27]). Consider the following gameG(I) between two players, Nonempty and Empty [5]. Nonempty and Empty alternately chooseXn∈I+andYn∈I+respectively so thatXn⊃Yn⊃n+1. After ω moves, Empty wins the game if⋂n<ωXn=⋂n<ωYn= Ø.See [5, Theorem 2] for a proof of the following characterization.Proposition.I is nowhere precipitous if and only if Empty has a winning strategy in G(I).
Ordre fondamental d'une théorie 1-basée
Authors: Bagheri Seyyed Mohammad 
Published: May 2006

D'après Lascar et Poizat [10], la déviation pour une théorie stable est associée à un préordre partiel sur l'ensemble des types. L'ordre induit a été nommé par Poizat ordre fondamental. Il mesure combien un type est loin d'être réalisé et il donne un certain nombre d'informations sur la théorie. Une question naturelle, est de décrire completément tous les ordres fondamentaux [13]. Il semble que cela soit difficile. Un problème moins ambitieux est de trouver des conditions pour qu'un ordre soit l'ordre fondamental d'une théorie, ou bien de trouver des exemples.Le but de cet article est de trouver de nouveaux exemples d'ordres fondamentaux. Nous nous concentrons principalement sur les théories stables et 1-basées car, comme nous allons voir dans la Section 2, avec cette hypothèse, il y a une représentation simple de l'ordre fondamental grâce aux ensembles algébriquement clos d'éléments des modèles de la thé;orie considégrée. Dans la Section 3, nous généralisons une idée de Baldwin et Berman [2] pour construire de “nouveaux” exemples d'ordres fondamentaux. En combinant cette construction avec les résultats de la Section 2, on caractérise de manière complete les ordres fondamentaux de theories triviales et 1-basées: les blocs des ordres fondamentaux d'une théorie triviale et 1-basée sont les inverses des posets de la forme I(L)/G où L est un treillis distributif borné et G un groupe compact d'automorphismes localement fini de L. De plus, tout ordre partiel de cette forme est l'ordre fondamental d'une théorie triviale et 1-basá. En particulier, l'ordre fondamental n'est pas toujours un treillis.
Notions of locality and their logical characterizations over finite models
Authors: Hella Lauri , Libkin Leonid , Nurmonen Juha 
Published: May 2006

AbstractMany known tools for proving expressibility bounds for first-ordér logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree.
Initial segments of the lattice of Π10 classes
Authors: Cenzer Douglas , Nies Andre 
Published: May 2006

Abstract.We show that in the lattice of classes there are initial segments [∅, P] = (P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a class P such that L is isomorphic to the lattice (P)*, which is (P). modulo finite differences. For the 2-element lattice, we obtain a minimal class, first constructed by Cenzer, Downey, Jockusch and Shore in 1993. For the simplest new class P constructed, P has a single, non-computable limit point and (P)* has three elements, corresponding to ∅, P and a minimal class P0 ⊂ P, The element corresponding to P0 has no complement in the lattice. On the other hand, the theory of (P) is shown to be decidable.A class P is said to be decidable if it is the set of paths through a computable tree with no dead ends. We show that if P is decidable and has only finitely many limit points, then (P)* is always a Boolean algebra. We show that if P is a decidable class and (P) is not a Boolean algebra, then the theory of (P) interprets the theory of arithmetic and is therefore undecidable.
Partitioning subsets of stable models
Authors: Bays Timothy 
Published: May 2006

Abstract.This paper discusses two combinatorial problems in stability theory. First we prove a partition result for subsets of stable models: for any A and B, we can partition A into ∣B∣<κ(T) pieces. 〈Ai ∣ i < ∣B∣<κ(T)〉. such that for each Ai there is a Bi ⊆ B where ∣Bi∣ < κ(T) and , Second, if A and B are as above and ∣A∣ > ∣B∣, then we try to find A′ ⊂ A and B′ ⊂ B such that ∣A′∣ is as large as possible. ∣B′∣ is as small as possible, and . We prove some positive results in this direction, and we discuss the optimality of these results under ZFC + GCH.
Elementary properties of power series fields over finite fields
Authors: Kuhlmann Franz-Viktor 
Published: May 2006

AbstractIn spite of the analogies between ℚp and which became evident through the work of Ax and Kochen, an adaptation of the complete recursive axiom system given by them for ℚp, to the case of does not render a complete axiom system. We show the independence of elementary properties which express the action of additive polynomials as maps on . We formulate an elementary property expressing this action and show that it holds for all maximal valued fields. We also derive an example of a rather simple immediate valued function field over a henselian defectless ground field which is not a henselian rational function field. This example is of special interest in connection with the open problem of local uniformization in positive characteristic.
Epsilon-logic is more expressive than first-order logic over finite structures
Authors: Otto Martin 
Published: May 2006

AbstractThere are properties of finite structures that are expressible with the use of Hilbert's ∈-operator in a manner that does not depend on the actual interpretation for ∈-terms. but not expressible in plain first-order. This observation strengthens a corresponding result of Gurevich, concerning the invariant use of an auxiliary ordering in first-order logic over finite structures. The present result also implies that certain non-deterministic choice constructs, which have been considered in database theory, properly enhance the expressive power of first-order logic even as far as deterministic queries are concerned, thereby answering a question raised by Abiteboul and Vianu.
Recursive inseparability for residual bounds of finite algebras
Authors: McKenzie Ralph 
Published: May 2006

AbstractWe exhibit a construction which produces for every Turing machine T with two halting states μ0 and μ−1, an algebra B(T) (finite and of finite type) with the property that the variety generated by B(T) is residually large if T halts in state μ−1, while if T halts in state μ0 then this variety is residually bounded by a finite cardinal.
An intuitionistic version of Zermelo's proof that every choice set can be well-ordered
Authors: Wilson J. Todd 
Published: May 2006

AbstractWe give a proof, valid in any elementary topos, of the theorem of Zermelo that any set possessing a choice function for its set of inhabited subsets can be well-ordered. Our proof is considerably simpler than existing proofs in the literature and moreover can be seen as a direct generalization of Zermelo's own 1908 proof of his theorem.
An axiomatics for nonstandard set theory, based on von Neumann–Bernays–Gödel Theory
Authors: Andreev P. V. , Gordon E. I. 
Published: May 2006

AbstractWe present an axiomatic framework for nonstandard analysis—the Nonstandard Class Theory (NCT) which extends von Neumann–Gödel–Bernays Set Theory (NBG) by adding a unary predicate symbol St to the language of NBG (St(X) means that the class X is standard) and axioms—related to it—analogs of Nelson's idealization, standardization and transfer principles. Those principles are formulated as axioms, rather than axiom schemes, so that NCT is finitely axiomatizable. NCT can be considered as a theory of definable classes of Bounded Set Theory by V. Kanovei and M. Reeken. In many aspects NCT resembles the Alternative Set Theory by P. Vopenka. For example there exist semisets (proper subclasses of sets) in NCT and it can be proved that a set has a standard finite cardinality iff it does not contain any proper subsemiset. Semisets can be considered as external classes in NCT. Thus the saturation principle can be formalized in NCT.
The mean value theorem in second order arithmetic
Authors: Hardin Christopher S. , Velleman Daniel J. 
Published: May 2006

This paper is a contribution to the project of determining which set existence axioms are needed to prove various theorems of analysis. For more on this project and its history we refer the reader to [1] and [2].We work in a weak subsystem of second order arithmetic. The language of second order arithmetic includes the symbols 0, 1, =, <, +, ·, and ∈, together with number variables x, y, z, … (which are intended to stand for natural numbers), set variables X, Y, Z, … (which are intended to stand for sets of natural numbers), and the usual quantifiers (which can be applied to both kinds of variables) and logical connectives. We write ∀x < t φ and ∃x < t φ as abbreviations for ∀x(x < t → φ) and ∃x{x < t ∧ φ) respectively; these are called bounded quantifiers. A formula is said to be if it has no quantifiers applied to set variables, and all quantifiers applied to number variables are bounded. It is if it has the form ∃xθ and it is if it has the form ∀xθ, where in both cases θ is .The theory RCA0 has as axioms the usual Peano axioms, with the induction scheme restricted to formulas, and in addition the comprehension scheme, which consists of all formulas of the formwhere φ is , ψ is , and X does not occur free in φ(n). (“RCA” stands for “Recursive Comprehension Axiom.” The reason for the name is that the comprehension scheme is only strong enough to prove the existence of recursive sets.) It is known that this theory is strong enough to allow the development of many of the basic properties of the real numbers, but that certain theorems of elementary analysis are not provable in this theory. Most relevant for our purposes is the fact that it is impossible to prove in RCA0 that every continuous function on the closed interval [0, 1] attains maximum and minimum values (see [1]).Since the most common proof of the Mean Value Theorem makes use of this theorem, it might be thought that the Mean Value Theorem would also not be provable in RCA0. However, we show in this paper that the Mean Value Theorem can be proven in RCA0. All theorems stated in this paper are theorems of RCA0, and all of our reasoning will take place in RCA0.
Proper forcing and remarkable cardinals II
Authors: Schindler Ralf-Dieter 
Published: May 2006

AbstractThe current paper proves the results announced in [5].We isolate a new large cardinal concept, “remarkability.” Consistencywise, remarkable cardinals are between ineffable and ω-Erdös cardinals. They are characterized by the existence of “0#-like” embeddings; however, they relativize down to L. It turns out that the existence of a remarkable cardinal is equiconsistent with L(ℝ) absoluteness for proper forcings. In particular, said absoluteness does not imply determinacy.
The Civil Service in the Modern State
Authors: Finer Herman 
Published: May 2006

“I'd give them th' votes,” said Mr. Dooley. “But,” he added significantly, “I'd do the countin'!” These words symbolise, in a crude way, the direction of political inquiry in the century prior to the year 1880. Until about that time political scientists were concerned mainly with the processes of policy and law-making. Incident to this were studied things like the nature of public opinion and the electorate, political parties, representative assemblies and their relation to the executive. But the problem of the civil service in the modern state emerged in its full importance not longer than some four decades ago; and indeed, today, we are only in the stage of discovering the questions yet to be explored.The centre of gravity in political science has plainly shifted from the field of electioneering to that of the civil service. In our own day that machinery serves two purposes of high importance. Firstly, it furnishes the expert knowledge without which parliaments can not, in any adequate fashion, create and enact policies. Secondly, it carries out the commands of the policymaking body. The experience of the United States, of Great Britain, of France, Germany, Canada, Australia and South Africa, shows conclusively that to perform the first of these two functions the members of the representative assemblies have neither the time, the ability, the inclination, nor the machinery. They must come to the permanent office-holders for expert knowledge. And as to the second, a variety of reasons forces them to legislate in general terms and leave the civil servants to draw up statutory rules and orders—to create “secondary legislation,” the enormous and increasing mass of which gives the civil service in the modern state a vast power.
Schémas pour le calcul des propositions fondé sur la conjonction et la négation
Authors: Porte Jean 
Published: May 2006

On sait que la conjonction et la négation constituent un système de connecteurs suffisant pour formuler le calcul des propositions classiques. Un certain intêrêt s'attache à ces formulations par suite des faits suivants: – les thèses du calcul intuitioniste qui ne comprennent pas d'autres connecteurs que la conjonction et la négation sont identiques aux thèses classiques;– Lewis ayant formulé ses calculs modaux en prenant la conjonction, la négation et la possibilité comme connecteurs primitifs (voir Lewis-Langford 1932, ch. VI) et ayant été suivi par beaucoup de chercheurs s'occupant de modalités, le calcul classique fondé sur la conjonction et la négation est contenu dans la plupart des systèmes modaux que l'on trouve dans la littérature.Un système logistique pour le calcul classique fondé sur la conjonction et la négation a été étudié par Rosser (voir Rosser 1953, ch. 4; aussi Copi 1954, ch. 7).Dans cet article je vais définir cinq autres systèmes logistiques fondés sur les mêmes connecteurs, démontrer leur suffisance (en utilisant les résultats publiés de Rosser et de Copi), et — sauf un cas — démontrer l'indépendance des axiomes de chacun de ces systèmes.
Two theories with axioms built by means of pleonasms
Authors: Ehrenfeucht Andrzej 
Published: May 2006

This paper contains examples T1 and T2 of theories which answer the following questions:(1) Does there exist an essentially undecidable theory with a finite number of non-logical constants which contains a decidable, finitely axiomatizable subtheory?(2) Does there exist an undecidable theory categorical in an infinite power which has a recursive set of axioms? (Cf. [2] and [3].)The theory T1 represents a modification of a theory described by Myhill [7]. The common feature of theories T1 and T2 is that in both of them pleonasms are essential in the construction of the axioms.Let T1 be a theory with identity = which contains one binary predicate R(x, y) and is based on the axioms A1, A2, A3, B1, B2, B3, B4, Cnm which follow.A1: x = x. A2: x = y ⊃ y = x. A3: x = y ∧ y = z ⊃ x = z.(Axioms of identity.)B1: R(x, x). B2: R(x, y) ⊃ R(y, x). B3: R (x, y) ∧ R(y, z) ⊃ R(x, z).(Axioms of equivalence.)B4: x = y ⊃ [R(z, x) ≡ R(z,y)].Let φn be the formulawhich express that there is an abstraction class of the relation R which has exactly n elements.Let f(n) and g(n) be two recursive functions which enumerate two recursively inseparable sets [5], and call these sets X1 and X2.We now specify the axioms Cmm.It is obvious that the set composed of the formulas A1−A3, B1−B4, Cnm (n,m = 1,2, …) is recursive.The theory T1 is essentially undecidable; for if there were a complete and decidable extension T′1 (of it, then the recursive sets Z = {n: φn is provable in T′1} and Z′ = {n: ∼φn is provable in T′1} would separate the sets X1 and X2.
A problem of Rosser and Turquette
Authors: Margaris Angelo 
Published: May 2006

In this paper an affirmative solution is given for the following problem in many-valued logic posed by Rosser and Turquette in [6] p. 110:For every triple ‹s, t, m› with 1 ≤ s < t < m, is it possible to define a system of m-valued logic which satisfies the following conditions? I. Every statement which always takes values ≦ s is provable. II. No statement which ever takes a value > t is provable. III. Of those statements which always take values ≤ t and sometimes take a value > s, some are provable and some are not.We state now, temporarily deferring comment, a more demanding alternative to Condition III: III′. For every truth value k such that s < k ≦ t, there are statements P and Q such that each takes the value k at least once, but never takes a value > k, and P is provable and Q is not.In § 2 a solution is given on the level of the statement calculus. The remainder of the present section is devoted to some negative results which serve to clarify the problem, and one positive result which shall cause us to replace Condition III by III′. We confine our attention to the statement calculus.
Economic Organization for War
Authors: Bogart Ernest L. 
Published: May 2006

As shown in the struggle recently ended, modern war means “a nation in arms.” The old-time distinction between fighters and workers was almost obliterated, and there was an industrial army as well as an army in the field. The labors of the men and women behind the lines were essential to the effective operations of the men in arms. That this condition was recognized by the governments themselves is shown by the classifications of workers, according to which those whose special skill or ability was essential to the conduct of war industries were taken out or kept out of the army and retained in the factories, mines, workshops, and fields. In various ways the old lines between soldier and civilian, between war operations and the work of production, were broken down. The Germans made no distinction between war vessels and merchantmen. They deliberately destroyed coal mines and factories, growing crops and cattle; this was done with a military purpose, for the sake of lessening the military strength of the enemy. So, too, the former distinction between contraband and free goods was obliterated. Whole nations were in arms, and all their resources were mobilized to carry on the titanic struggle.This world conflict has taught us that war is not waged altogether by armies in the field. It is a contest between the industrial organization and technique of the opposing nations. It is not carried on by money alone, but by the total resources, material and human, that can be concentrated in a combined, productive effort. The World War gave the first opportunity for a complete application of the modern factory system of production in warfare.
The Luxemburg Chamber of Deputies
Authors: Putnam Ruth 
Published: May 2006

Why should legislative proceedings in the grand duchy of Luxemburg be given consideration? It is a country with an area less than that of Rhode Island and with a population (260,000) which would barely fill a second class city—a mere atom in the world's history. Nor has it played an heroic part in the great crisis. Here is the excuse. The discussions in the chamber of deputies have reflected, not in their depths but in their shallows, nearly all the phases of the seething unrest which agitates larger nations, and therein lies the reason for offering a few pictures drawn from the official records of the grand ducal chamber— the German reports as they are sent out daily, translated from the proceedings in French, and the final French comptes-rendus. They are miniatures of the processes of readjustment in progress across the Atlantic.The Luxemburg chamber of deputies is a legislative body that has been evolved by a series of still visible leaps and jumps from the simplest feudal conditions to the assembly recently elected by universal adult suffrage on a basis of proportional party representation according to the system of the scrutin de liste. Its modernity is so complete that a Socialist woman has obtained a seat, yet the conservative character of the forbears of the body is not entirely lost to view in the mists of the past.The old duchy of Luxemburg—a countship until raised to higher dignity by an imperial brother of its count (1354)—lost its early independence in the fifteenth century (1441), and thenceforth shared the political lot of the Belgic provinces under Burgundian, Spanish and Austrian rule.