bluuebunny/crossref_metadata_2025_split huggingface dataset:
New techniques and completeness results for preferential structures
Authors: Schlechta Karl 
Published: May 2006

AbstractPreferential structures are probably the best examined semantics for nonmonotonic and deontic logics: in a wider sense, they also provide semantical approaches to theory revision and update, and other fields where a preference relation between models is a natural approach. They have been widely used to differentiate the various systems of such logics, and their construction is one of the main subjects in the formal investigation of these logics. We introduce new techniques to construct preferential structures for completeness proofs. Since our main interest is to provide general techniques, which can be applied in various situations and for various base logics (propositional and other), we take a purely algebraic approach, which can be translated into logics by easy lemmata, in particular, we give a clean construction via indexing by trees for transitive structures, this allows us to simplify the proofs of earlier work by the author, and to extend the results given there.
Equivalence elementaire et decidabilite pour des structures du type groupe agissant sur un groupe abelien
Authors: Simonetta Patrick 
Published: May 2006

AbstractWe prove an Ax-Kochen-Ershov like transfer principle for groups acting on groups. The simplest case is the following: let B be a soluble group acting on an abelian group G so that G is a torsion-free divisible module over the group ring ℤ[B], then the theory of B determines the one of the two-sorted structure 〈G,B,*〉, where * is the action of B on C. More generally, we show a similar principle for structures 〈G,B,*〉, where G is a torsion-free divisible module over the quotient of ℤ[B] by the annulator of G.Two applications come immediately from this result:First, for not necessarily commutative domains, where we consider the action of a subgroup of the invertible elements on the additive group. We obtain then the decidability of a weakened structure of ring, with partial multiplication.The second application is to pure groups. The semi-direct product of G by B is bi-interpretable with our structure 〈G,B,*〉. Thus, we obtain stable decidable groups that are not linear over a field.
The determinacy of Blackwell games
Authors: Martin Donald A. 
Published: May 2006

Games of infinite length and perfect information have been studied for many years. There are numerous determinacy results for these games, and there is a wide body of work on consequences of their determinacy.Except for games with very special payoff functions, games of infinite length and imperfect information have been little studied. In 1969, David Blackwell [1] introduced a class of such games and proved a determinacy theorem for a subclass. During the intervening time, there has not been much progress in proving the determinacy of Blackwell's games. Orkin [17] extended Blackwell's result to a slightly wider class. Blackwell [2] found a new proof of his own result. Maitra and Sudderth [9, 10] improved Blackwell's result in a different direction from that of Orkin and also generalized to the case of stochastic games. Recently Vervoort [18] has obtained a substantial improvement. Nevertheless, almost all the basic questions have remained open.In this paper we associate with each Blackwell game a family of perfect information games, and we show that the (mixed strategy) determinacy of the former follows from the (pure strategy) determinacy of the latter. The complexity of the payoff function for the Blackwell game is approximately the same as the complexity of the payoff sets for the perfect information games. In particular, this means that the determinacy of Blackwell games with Borel measurable payoff functions follows from the known determinacy of perfect information games with Borel payoff sets.
Fragments of Heyting arithmetic
Authors: Burr Wolfgang 
Published: May 2006

AbstractWe define classes Φnof formulae of first-order arithmetic with the following properties:(i) Everyφϵ Φnis classically equivalent to a Πn-formula (n≠ 1, Φ1:= Σ1).(ii)(iii)IΠnandiΦn(i.e., Heyting arithmetic with induction schema restricted to Φn-formulae) prove the same Π2-formulae.We further generalize a result by Visser and Wehmeier. namely that prenex induction within intuitionistic arithmetic is rather weak: After closing Φnboth under existential and universal quantification (we call these classes Θn) the corresponding theoriesiΘnstill prove the same Π2-formulae. In a second part we consideriΔ0plus collection-principles. We show that both the provably recursive functions and the provably total functions ofare polynomially bounded. Furthermore we show that the contrapositive of the collection-schema gives rise to instances of the law of excluded middle and hence.
On decidable extensions of Presburger arithmetic: from A. Bertrand numeration sytems to Pisot numbers
Authors: Point Françoise 
Published: May 2006

AbstractWe study extensions of Presburger arithmetic with a unary predicate R and we show that under certain conditions on R, R is sparse (a notion introduced by A. L. Semënov) and the theory of 〈ℕ, +, R〉 is decidable. We axiomatize this theory and we show that in a reasonable language, it admits quantifier elimination. We obtain similar results for the structure 〈ℚ, +, R〉.
Forcing on bounded arithmetic II
Authors: Takeuti Gaisi , Yasumoto Masahiro 
Published: May 2006

Forcing method on Bounded Arithmetic was first introduced by J. B. Paris and A. Wilkie in [10]. Then in [1], [2] and [3], M. Ajtai used the method to get excellent results on the pigeon hole principle and the modulo p counting principle. The forcing method on Bounded arithmetic was further developed by P. Beame, J. Krajíček and S. Riis in [4], [7], [6], [8], [5], [12], [11], [13]. It should be noted that J. Krajíček and P. Pudlák used an idea of Boolean valued in [9] and also Boolean valued notion is efficiently used for model theoretic constructions in [7], [6], [8], [5].In our previous paper [14], we developed a Boolean valued version of forcing on Bounded Arithmetic using Boolean algebra which is generated by polynomial size circuits from Boolean variables and discussed its relation with NP = co-NP problem and P = NP problem. Especially we proved the following theorem and related theorems as Theorems 2, 3 and 4 in Section 2.Theorem. If M[G] is not a model of S2, then NP ≠ co-NP and therefore P ≠ NP.However in the proof of the Theorem, we used a consequence of P = NP. More precisely we used the following as a consequence of NP = co-NP, though it is a consequence of P = NP but not a consequence of NP = co-NP.Suppose that NP = co-NP holds. Then there exists an NP-complete predicate ∃x ≤ t(a) A(x,a) with sharply bounded A(x, a) and a sharply bounded B(y, a) such that ∃x ≤ t(a) A(x,a) ↔ ∀y ≤ s(a)B(y, a). Then there exists polynomial time computable functions f and g such that the following two sequents hold.
On automorphism groups of countable structures
Authors: Gao Su 
Published: May 2006

AbstractStrengthening a theorem of D. W. Kueker, this paper completely charaterizes which countable structures do not admit uncountable Lω1ω-elementarily equivalent models. In particular, it is shown that if the automorphism group of a countable structure M is abelian, or even just solvable, then there is no uncountable model of the Scott sentence of M. These results arise as part of a study of Polish groups with compatible left-invariant complete metrics.
Geometry of *-Finite Types
Authors: Newelski Ludomir 
Published: May 2006

AbstractAssumeTis a superstable theory with < 2ℵ0countable models. We prove that any *- algebraic type of-rank > 0 is m-nonorthogonal to a *-algebraic type of-rank 1. We study the geometry induced by m-dependence on a *-algebraic typep*of-rank 1. We prove that after some localization this geometry becomes projective over a division ring. Associated withp*is a meager typep. We prove thatpis determined byp*up to nonorthogonality and thatunderlies also the geometry induced by forking dependence on any stationarization ofp. Also we study some *-algebraic *-groups of-rank 1 and prove that any *-algebraic *-group of-rank 1 is abelian-by-finite.
Free set algebras satisfying systems of equations
Authors: Antonelli G. Aldo 
Published: May 2006

AbstractIn this paper we introduce the notion of a set algebra satisfying a system E of equations. After defining a notion of freeness for such algebras, we show that, for any system E of equations, set algebras that are free in the class of structures satisfying E exist and are unique up to a bisimulation. Along the way, analogues of classical set-theoretic and algebraic properties are investigated.
Pseudo-finite homogeneity and saturation
Authors: Flum Jörg , Ziegler Martin 
Published: May 2006

AbstractWhen analyzing database query languages a roperty, of theories, the pseudo-finite homogeneity property, has been introduced and applied (cf. [3]). We show that a stable theory has the pseudo-finite homogeneity property just in case its expressive power for finite states is bounded. Moreover, we introduce the corresponding pseudo-finite saturation property and show that a theory fails to have the finite cover property if and only if it has the pseudo-finite saturation property.
On the Restraining Power of Guards
Authors: Grädel Erich 
Published: May 2006

AbstractGuarded fragments of first-order logic were recently introduced by Andréka, van Benthem and Németi; they consist of relational first-order formulae whose quantifiers are appropriately relativized by atoms. These fragments are interesting because they extend in a natural way many propositional modal logics, because they have useful model-theoretic properties and especially because they are decidable classes that avoid the usual syntactic restrictions (on the arity of relation symbols, the quantifier pattern or the number of variables) of almost all other known decidable fragments of first-order logic.Here, we investigate the computational complexity of these fragments. We prove that the satisfiability problems for the guarded fragment (GF) and the loosely guarded fragment (LGF) of first-order logic are complete for deterministic double exponential time. For the subfragments that have only a bounded number of variables or only relation symbols of bounded arity, satisfiability is Exptime-complete. We further establish a tree model property for both the guarded fragment and the loosely guarded fragment, and give a proof of the finite model property of the guarded fragment.It is also shown that some natural, modest extensions of the guarded fragments are undecidable.
Undecidable extensions of Skolem arithmetic
Authors: Bès Alexis , Richard Denis 
Published: May 2006

AbstractLet be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of is undecidable. Now denote by <π the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure (ℕ; ⊥, <π). Furthermore, the structures (ℕ; ∣, <π) (ℕ; =, ×, <π) and (ℕ; =, +, ×) are interdefinable.
Explicit mathematics with the monotone fixed point principle
Authors: Rathjen Michael 
Published: May 2006

AbstractThe context for this paper is Feferman's theory of explicit mathematics, a formal framework serving many purposes. It is suitable for representing Bishop-style constructive mathematics as well as generalized recursion, including direct expression of structural concepts which admit self-application. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, the new axiom not merely postulates the existence of a least solution, but, by adjoining a new functional constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation.The upshot of the paper is that the latter extension of explicit mathematics (when based on classical logic) embodies considerable proof-theoretic strength. It is shown that it has at least the strength of the subsystem of second order arithmetic based on comprehension.
A note on valuation definable expansions of fields
Authors: Haskell Deirdre , Dugald Macpherson  
Published: May 2006

In this note, we consider models of the theories of valued algebraically closed fields and convexly valued real closed fields, their reducts to the pure field or ordered field language respectively, and expansions of these by predicates which are definable in the valued field. We show that, in terms of definability, there is no structure properly between the pure (ordered) field and the valued field. Our results are analogous to several other definability results for reducts of algebraically closed and real closed fields; see [9], [10], [11] and [12]. Throughout this paper, definable will mean definable with parameters.Theorem A. Let ℱ = (F, +, ×, V) be a valued, algebraically closed field, where V denotes the valuation ring. Let A be a subset ofFndefinable in ℱv. Then either A is definable in ℱ = (F, +, ×) or V is definable in.Theorem B. Let ℛv = (R, <, +, ×, V) be a convexly valued real closed field, where V denotes the valuation ring. Let Abe a subset ofRndefinable in ℛv. Then either A is definable in ℛ = (R, <, +, ×) or V is definable in.The proofs of Theorems A and B are quite similar. Both ℱv and ℛv admit quantifier elimination if we adjoin a definable binary predicate Div (interpreted by Div(x, y) if and only if v(x) ≤ v(y)). This is proved in [14] (extending [13]) in the algebraically closed case, and in [4] in the real closed case. We show by direct combinatorial arguments that if the valuation is not definable then the expanded structure is strongly minimal or o-minimal respectively. Then we call on known results about strongly minimal and o-minimal fields to show that the expansion is not proper.
Undecidable theories of Lyndon algebras
Authors: Stebletsova Vera , Venema Yde 
Published: May 2006

AbstractWith each projective geometry we can associate a Lyndon algebra. Such an algebra always satisfies Tarski's axioms for relation algebras and Lyndon algebras thus form an interesting connection between the fields of projective geometry and algebraic logic. In this paper we prove that if G is a class of projective geometries which contains an infinite projective geometry of dimension at least three, then the class L(G) of Lyndon algebras associated with projective geometries in G has an undecidable equational theory. In our proof we develop and use a connection between projective geometries and diagonal-free cylindric algebras.
Cohen reals from small forcings
Authors: Pawlikowski Janusz 
Published: May 2006

AbstractWe introduce a new cardinal characteristic r*. related to the reaping number r. and show that• posets of size < r* which add reals add unbounded reals;• posets of size < r which add unbounded reals add Cohen reals.We also show that add() ≤ min(r. r*). It follows that posets of size < add() which add reals add Cohen reals.This improves results of Roslanowski and Shelah [RS] and of Zapletal [Z].
Existentially closed structures and Gödel's second incompleteness theorem
Authors: Adamowicz Zofia , Bigorajska Teresa 
Published: May 2006

AbstractWe prove that any 1-closed (see def 1.1) model of the Π2 consequences of PA satisfies ¬Cons PA which gives a proof of the second Gödel incompleteness theorem without the use of the Gödel diagonal lemma. We prove a few other theorems by the same method.
Free ordered algebraic structures towards proof theory
Authors: Prijatelj Andreja 
Published: May 2006

AbstractIn this paper, constructions of free ordered algebras on one generator are given that correspond to some one-variable fragments of affine propositional classical logic and their extensions with n-contraction (n ≥ 2). Moreover, embeddings of the already known infinite free structures into the algebras introduced below are furnished with; thus, solving along the respective cardinality problems.
Simplicity, and stability in there
Authors: Kim Byunghan 
Published: May 2006

AbstractFirstly, in this paper, we prove that the equivalence of simplicity and the symmetry of forking. Secondly, we attempt to recover definability part of stability theory to simplicity theory. In particular, using elimination of hyperimaginaries we prove that for any supersimpleT. canonical base of an amalgamation classis the union of names ofψ-definitions of,ψranging over stationaryL-formulas in. Also, we prove that the same is true with stable formulas for an 1-based theory having elimination of hyperimaginaries. For such a theory, the stable forking property holds, too.
Ramsey's theorem for computably enumerable colorings
Authors: Hummel Tamara J. , Jockusch Carl G. 
Published: May 2006

AbstractIt is shown that for each computably enumerable set of n-element subsets of ω there is an infinite set A ⊆ ω such that either all n-element subsets of A are in or no n-element subsets of A are in . An analogous result is obtained with the requirement that A be replaced by the requirement that the jump of A be computable from 0(n). These results are best possible in various senses.
Identity crises and strong compactness
Authors: Apter Arthur W. , Cummings James 
Published: May 2006

AbstractCombining techniques of the first author and Shelah with ideas of Magidor, we show how to get a model in which, for fixed but arbitrary finite n, the first n strongly compact cardinals k1..…kn are so that ki; for i = 1..…n is both the ith measurable cardinal and supercompact. This generalizes an unpublished theorem of Magidor and answers a question of Apter and Shelah.
Existence of prime elements in rings of generalized power series
Authors: Pitteloud Daniel 
Published: May 2006

AbstractThe fieldK((G)) of generalized power series with coefficients in the fieldKof characteristic 0 and exponents in the ordered additive abelian groupGplays an important role in the study of real closed fields. Conway and Gonshor (see [2, 4]) considered the problem of existence of non-standard irreducible (respectively prime) elements in the huge “ring” of omnific integers, which is indeed equivalent to the existence of irreducible (respectively prime) elements in the ringK((G≤0)) of series with non-positive exponents. Berarducci (see [1]) proved thatK((G≤0)) does have irreducible elements, but it remained open whether the irreducibles are prime i.e., generate a prime ideal. In this paper we prove thatK((G≤0)) does have prime elements ifG= (ℝ, +) is the additive group of the reals, or more generally ifGcontains a maximal proper convex subgroup.
Political Science in Great Britain and France
Authors: Laski Harold J. , Caudel Maurice 
Published: May 2006

In response to requests for information concerning recent developments in political science in Great Britain and France, the following accounts were received from Professor Harold J. Laski, of the London School of Economics and Political Science, and M. Maurice Caudel, of L'École Libre des Sciences Politiques and editor of the Revue des Sciences Politiques:Great Britain. It will be well-known to American students of political science, especially since Professor Fairlie's very careful survey in a previous number of the Political Science Review, that there is practically no organized study of political science in Great Britain.
On the axioms of order and succession
Authors: Bing Kurt 
Published: May 2006

Hasenjaeger [2] has answered a question raised by Hilbert and Bernays [4] p. 279, by showing that the axiomwhich, within lower predicate calculus, is independent of the remaining axioms of the system (B) p. 273, is no longer independent if the axiom 0 ≡ 0 of (B) is replaced by a ≡ a. The axioms from which (Cov) can be proved form the following system (B1) (obtained from (B), of course, by dropping (Cov) and replacing 0 ≡ 0 by a ≡ a):In what follows we consider (B1) and also the systems (B′) and (B′1) which are obtained from (B) and (B1) respectively by dropping the induction axiom and which clarify the role of the induction axiom.1. (B1) is equivalent to (B). For (B) can be obtained from (B1) by Hasenjaeger's result. On the other hand, by pp. 263 and 261, the axioms (<1) and (J1) of (B1) can be proved from the axioms (<3) andwhich belong to the system (A) p. 263. Therefore (B1) can be obtained from (A) and the induction axiom, and hence from (B).
Foundational aspects of theories of measurement
Authors: Scott Dana , Suppes Patrick 
Published: May 2006

It is a scientific platitude that there can be neither precise control nor prediction of phenomena without measurement. Disciplines are diverse as cosmology and social psychology provide evidence that it is nearly useless to have an exactly formulated quantitative theory if empirically feasible methods of measurement cannot be developed for a substantial portion of the quantitative concepts of the theory. Given a physical concept like that of mass or a psychological concept like that of habit strength, the point of a theory of measurement is to lay bare the structure of a collection of empirical relations which may be used to measure the characteristic of empirical phenomena corresponding to the concept. Why a collection of relations? From an abstract standpoint a set of empirical data consists of a collection of relations between specified objects. For example, data on the relative weights of a set of physical objects are easily represented by an ordering relation on the set; additional data, and a fortiori an additional relation, are needed to yield a satisfactory quantitative measurement of the masses of the objects.The major source of difficulty in providing an adequate theory of measurement is to construct relations which have an exact and reasonable numerical interpretation and yet also have a technically practical empirical interpretation. The classical analyses of the measurement of mass, for instance, have the embarrassing consequence that the basic set of objects measured must be infinite. Here the relations postulated have acceptable numerical interpretations, but are utterly unsuitable empirically. Conversely, as we shall see in the last section of this paper, the structure of relations which have a sound empirical meaning often cannot be succinctly characterized so as to guarantee a desired numerical interpretation.