bluuebunny/crossref_metadata_2025_split huggingface dataset:
Abelian groups with modular generic
Authors: Loveys James 
Published: May 2006

AbstractLet G be a stable abelian group with regular modular generic. We show that either1. there is a definable nongeneric K ≤ G such that G/K has definable connected component and so strongly regular generics, or2. distinct elements of the division ring yielding the dependence relation are represented by subgroups of G × G realizing distinct strong types (when regarded as elements of Geq).In the latter case one can choose almost 0-definable subgroups representing the elements of the division ring. We find a bound ((G: G0)) for the size of the division ring in case G has no definable subgroup K so that G/K is infinite with definable connected component. We show in case (2) that the group G/H, where H consists of all nongeneric points of G, inherits a weakly minimal group structure from G naturally, and Th(G/H) is independent of the particular model G as long as G/H is infinite.
Admissible Suslin cardinals in L(R)
Authors: Jackson Steve 
Published: May 2006

AbstractAssuming AD + (V = L(R)), it is shown that for κ an admissible Suslin cardinal, o(κ) (= the order type of the stationary subsets of κ) is “essentially” regular and closed under ultrapowers in a manner to be made precise. In particular, o(κ) ≫ κ+, κ++, etc. It is conjectured that this characterizes admissibility for L(R).
Generalizations of the Kruskal-Friedman theorems
Authors: Gordeev L. 
Published: May 2006

AbstractKruskal proved that finite trees are well-quasi-ordered by hom(e)omorphic embeddability. Friedman observed that this statement is not provable in predicative analysis. Friedman also proposed (see in [Simpson]) some stronger variants of the Kruskal theorem dealing with finite labeled trees under hom(e)omorphic embeddability with a certain gap-condition, where labels are arbitrary finite ordinals from a fixed initial segment of ω. The corresponding limit statement, expressing that for all initial segments of ω these labeled trees are well-quasi-ordered, is provable in -CA, but not in the analogous theory -CA0 with induction restricted to sets. Schütte and Simpson proved that the one-dimensional case of Friedman's limit statement dealing with finite labeled intervals is not provable in Peano arithmetic. However, Friedman's gap-condition fails for finite trees labeled with transfinite ordinals. In [Gordeev 1] I proposed another gap-condition and proved the resulting one-dimensional modified statements for all (countable) transfinite ordinal-labels. The corresponding universal modified one-dimensional statement UM1 is provable in (in fact, is equivalent to) the familiar theory ATR0 whose proof-theoretic ordinal is Γ0. In [Gordeev 1] I also announced that, in the general case of arbitrarily-branching finite trees labeled with transfinite ordinals, in the proof-theoretic sense the hierarchy of the limit modified statements M<λ (which are denoted by LMλ in the present note) is as strong as the hierarchy of the familiar theories of iterated inductive definitions (more precisely, see [Gordeev 1, Concluding Remark 3]). In this note I present a “positive” proof of the full universal modified statement UM, together with a short proof of the crucial “reverse” results which is based on Okada's interpretation of the well-established ordinal notations of Buchholz corresponding to the theories of iterated inductive definitions. Formally the results are summarized in §5 below.
On the strong Martin conjecture
Authors: Itai Masanori 
Published: May 2006

AbstractWe study the following conjecture.Conjecture.Let T be an ω-stable theory with continuum many countable models. Then either i) T has continuum many complete extensions in L1(T), or ii) some complete extension of T in L1has continuum many L1-types without parameters.By Shelah's proof of Vaught's conjecture for ω-stable theories, we know that there are seven types of ω-stable theory with continuum many countable models. We show that the conjecture is true for all but one of these seven cases. In the last case we show the existence of continuum many L2-types.
On maximal theories
Authors: Adamowicz Zofia 
Published: May 2006

Let S be a recursive theory. Let a theory T* consisting of Σ1 sentences be called maximal (with respect to S) if T* is maximal consistent with S, i.e. there is no Σ1 sentence consistent with T* + S which is not in T*.A maximal theory with respect to IΔ0 was considered by Wilkie and Paris in [WP] in connection with the end-extension problem.Let us recall that IΔ0 is the fragment of Peano arithmetic consisting of the finite collection of algebraic axioms PA− together with the induction scheme restricted to bounded formulas.The main open problem concerning the end-extendability of models of IΔ0 is the following:(*) Does every model of IΔ0 + BΣ1 have a proper end-extension to a model of IΔ0?Here BΣ1 is the following collection scheme:where φ runs over bounded formulas and may contain parameters.It is well known(see [KP]) that if I is a proper initial segment of a model M of IΔ0, then I satisfies IΔ0 + BΣ1.For a wide discussion of the problem (*) see [WP]. Wilkie and Paris construct in [WP] a model M of IΔ0 + BΣ1 which has no proper end-extension to a model of IΔ0 under the assumption IΔ0 ⊢¬Δ0H (see [WP] for an explanation of this assumption). Their model M is a model of a maximal theory T* where S = IΔ0.Moreover, T*, which is the set Σ1(M) of all Σ1 sentences true in M, is not codable in M.
Inductive inference and unsolvability
Authors: Adleman Leonard M. , Blum M. 
Published: May 2006

AbtractIt is shown that many different problems have the same degree of unsolvability. Among these problems are:The Inductive Inference Problem. Infer in the limit an index for a recursive function f presented as f(0), f(1),f(2),….The Recursive Index Problem. Decide in the limit if i is the index of a total recursive function.The Zero Nonvariant Problem. Decide in the limit if a recursive function f presented as f(0), f(1), f(2),… has value unequal to zero for infinitely many arguments.Finally, it is shown that these unsolvable problems are strictly easier than the halting problem.
On bad groups, bad fields, and pseudoplanes
Authors: Nesin Ali 
Published: May 2006

Cherlin introduced the concept of bad groups (of finite Morley rank) in [Ch1]. The existence of such groups is an open question. If they exist, they will contradict the Cherlin-Zil'ber conjecture that states that an infinite simple group of finite Morley rank is a Chevalley group over an algebraically closed field. In this paper, we prove that bad groups of finite Morley rank 3 act on a natural geometry Γ (namely on a special pseudoplane; see Corollary 20) sharply flag-transitively.We show that Γ is not very far from being a projective plane and when it is so rk(Γ) = 2 and Γ is not Desarguesian (Theorem 2). Baldwin [Ba] recently discovered non-Desarguesian projective planes of Morley rank 2. This discovery, together with this paper, makes the existence of bad groups (also of bad fields) more plausible. A bad field is a pair (K, A) of finite Morley rank, where K is an algebraically closed field, A <≠K* and A is infinite. There existence is also unknown.In this paper, we define the concept of a sharp-field as a pair (K, A), where K is a field, A < K*and1. K = A − A,2. If a + b − 1 ∈ A, a ∈ A, b ∈ A, then either a = 1 or b = 1.If K is finite this is equivalent to 1 and2.′ ∣K∣ = ∣A∣2 ∣A∣ + 1.Finite sharp-fields are special cases of difference sets [De]
Extension of Lifschitz' realizability to higher order arithmetic,
and a solution to a problem of F. Richman
Authors: van Oosten Jaap 
Published: May 2006

AbstractF. Richman raised the question of whether the following principle of second order arithmetic is valid in intuitionistic higher order arithmetic HAH:and if not, whether assuming Church's Thesis CT and Markov's Principle MP would help. Blass and Scedrov gave models of HAH in which this principle, which we call RP, is not valid, but their models do not satisfy either CT or MP.In this paper a realizability topos Lif is constructed in which CT and MP hold, but RP is false. (It is shown, however, that RP is derivable in HAH + CT + MP + ECT0, so RP holds in the effective topos.) Lif is a generalization of a realizability notion invented by V. Lifschitz. Furthermore, Lif is a subtopos of the effective topos.
Who were the American postulate theorists?
Authors: Scanlan Michael 
Published: May 2006

AbstractArticles by two American mathematicians, E. V. Huntington and Oswald Veblen, are discussed as examples of a movement in foundational research in the period 1900–1930 called American postulate theory. This movement also included E. H. Moore, R. L. Moore, C. H. Langford, H. M. Sheffer, C. J. Keyser, and others. The articles discussed exemplify American postulate theorists' standards for axiomatizations of mathematical theories, and their investigations of such axiomatizations with respect to metatheoretic properties such as independence, completeness, and consistency.
On the existence of atomic models
Authors: Laskowski M. C. , Shelah S. 
Published: May 2006

AbstractWe give an example of a countable theory T such that for every cardinal λ ≥ ℵ2 there is a fully indiscernible set A of power λ such that the principal types are dense over A, yet there is no atomic model of T over A. In particular, T(A) is a theory of size λ where the principal types are dense, yet T(A) has no atomic model.
Boolean universes above Boolean models
Authors: Wehrung Friedrich 
Published: May 2006

AbstractWe establish several first- or second-order properties of models of first-order theories by considering their elements as atoms of a new universe of set theory and by extending naturally any structure of Boolean model on the atoms to the whole universe. For example, completef-rings are “boundedly algebraically compact” in the language (+, −, ·, ∧, ∨, ≤), and the positive cone of a completel-group with infinity adjoined is algebraically compact in the language (+, ∨, ≤). We also give an example with any first-order language. The proofs can be translated into “naive set theory” in a uniform way.
The development of arithmetic in Frege'sGrundgesetze der arithmetik
Authors: Heck Richard G. 
Published: May 2006

AbstractFrege's development of the theory of arithmetic in hisGrundgesetze der Arithmetikhas long been ignored, since the formal theory of theGrundgesetzeis inconsistent. His derivations of the axioms of arithmetic from what is known asHume's Principledo not, however, depend upon that axiom of the system—Axiom V—which is responsible for the inconsistency. On the contrary, Frege's proofs constitute a derivation of axioms for arithmetic from Hume's Principle, in (axiomatic) second-order logic. Moreover, though Frege does prove each of the now standard Dedekind-Peano axioms, his proofs are devoted primarily to the derivation of his own axioms for arithmetic, which are somewhat different (though of course equivalent). These axioms, which may be yet more intuitive than the Dedekind-Peano axioms, may be taken to be “TheBasic Laws of Cardinal Number”, as Frege understood them.Though the axioms of arithmetic have been known to be derivable from Hume's Principle for about ten years now, it has not been widely recognized that Frege himself showed them so to be; nor has it been known that Frege made use of any axiomatization for arithmetic whatsoever.Grundgesetzeis thus a work of much greater significance than has often been thought. First, Frege's use of the inconsistent Axiom V may invalidate certain of his claims regarding the philosophical significance of his work (viz., the establish may invalidate certain of his claims regarding the philosophical significance of his work (viz., the establishment of Logicism), but it should not be allowed to obscure his mathematical accomplishments and his contribution to our understanding of arithmetic. Second, Frege's knowledge that arithmetic is derivable from Hume's Principle raises important sorts of questions about his philosophy of arithmetic. For example, “Why did Frege not simply abandon Axiom V and take Hume's Principle as an axiom?”
The deduction rule and linear and near-linear proof simulations
Authors: Bonet Maria Luisa , Buss Samuel R. 
Published: May 2006

AbstractWe introduce new proof systems for propositional logic,simple deduction Frege systems, general deduction Frege systems, andnested deduction Frege systems, which augment Frege systems with variants of the deduction rule. We give upper bounds on the lengths of proofs in Frege proof systems compared to lengths in these new systems. As applications we give near-linear simulations of the propositional Gentzen sequent calculus and the natural deduction calculus by Frege proofs. The length of a proof is the number of lines (or formulas) in the proof.A general deduction Frege proof system provides at most quadratic speedup over Frege proof systems. A nested deduction Frege proof system provides at most a nearly linear speedup over Frege system where by “nearly linear” is meant the ratio of proof lengths isO(α(n)) where α is the inverse Ackermann function. A nested deduction Frege system can linearly simulate the propositional sequent calculus, the tree-like general deduction Frege calculus, and the natural deduction calculus. Hence a Frege proof system can simulate all those proof systems with proof lengths bounded byO(n. α(n)). Also we show that a Frege proof ofnlines can be transformed into a tree-like Frege proof ofO(nlogn) lines and of heightO(logn). As a corollary of this fact we can prove that natural deduction and sequent calculus tree-like systems simulate Frege systems with proof lengths bounded byO(nlogn).
Provably total functions of intuitionistic bounded arithmetic
Authors: Harnik Victor 
Published: May 2006

This note deals with a proof-theoretic characterisation of certain complexity classes of functions in fragments of intuitionistic bounded arithmetic. In this Introduction we survey the background and state our main result.We follow Buss [B1] and consider a language for arithmetic whose nonlogical symbols are 0, S (the successor operation Sx = x + 1), +, ·, ∣ ∣ (∣x∣ being the number of digits in the binary notation for x), rounded down to the nearest integer), # (x#y = 2∣x∣∣y∣) and ≤. We define 1 = S0, 2 = S1, s0x = 2x and s1x = 2x + 1. In Buss's approach the functions s0 and s1 play a special role. Notice that six is the number obtained from x by suffixing the digit i to its binary representation, and thus the natural numbers are generated from 0 by repeated applications of the operations s0 and s1. This means that they satisfy the induction schemeUsing the fact that is x with its last binary digit deleted, this can be stated more compactly in the following form, called by Buss the polynomial induction or PIND schema:Buss defined a theory S2 consisting of a finite set BASIC of open axioms and the PIND-schema restricted to bounded formulas ϕ. The topic of bounded arithmetic is concerned with S2 and its fragments.
Generalized reduction theorems for model-theoretic analogs of the class of coanalytic sets
Authors: Lavine Shaughan 
Published: May 2006

AbstractLet be an admissible set. A sentence of the form is a sentence if φ ∈ (φ is ∨ Φ where Φ is an -r.e. set of sentences from ). A sentence of the form is an , sentence if φ is a sentence. A class of structures is, for example, a ∀1 class if it is the class of models of a ∀1() sentence. Thus ∀1() is a class of classes of structures, and so forth.Let i, be the structure 〈i, <〉, for i > 0. Let Γ be a class of classes of structures. We say that a sequence J1, …, Ji,…, i < ω, of classes of structures is a Γ sequence if Ji ∈ Γ, i < ω, and there is I ∈ Γ such that ∈ Ji, if and only if [],i, where [,] is the disjoint sum. A class Γ of classes of structures has the easy uniformization property if for every Γ sequence J1,…, Ji,…, i < ω, there is a Γ sequence J′t, …, J′i, …, i < ω, such that J′i ⊆ Ji, i < ω, ⋃J′i = ⋃Ji, and the J′i are pairwise disjoint. The easy uniformization property is an effective version of Kuratowski's generalized reduction property that is closely related to Moschovakis's (topological) easy uniformization property.We show over countable structures that ∀1() and ∃2() have the easy uniformization property if is a countable admissible set with an infinite member, that and have the easy uniformization property if α is countable, admissible, and not weakly stable, and that and have the easy uniformization properly. The results proved are more general. The result for answers a question of Vaught(1980).
Diophantine relations between rings of S-integers of fields of algebraic functions in one variable over constant fields of positive characteristic
Authors: Shlapentokh Alexandra 
Published: May 2006

AbstractOne of the main theorems of the paper states the following. Let R-K-M be finite extensions of a rational one variable function field R over a finite field of constants. Let S be a finite set of valuations of K. Then the ring of elements of K having no poles outside S has a Diophantine definition over its integral closure in M.
Undecidable semiassociative relation algebras
Authors: Maddux Roger D. 
Published: May 2006

AbstractIf K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism ℒw× is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in ℒw× forms a hereditarily undecidable theory in ℒw×. These results generalize similar theorems, due to Tarski, concerning relation algebras and the formalism ℒ×.
What is an inference rule?
Authors: Fagin Ronald , Halpern Joseph Y. , Vardi Moshe Y. 
Published: May 2006

AbstractWhat is an inference rule? This question does not have a unique answer. One usually finds two distinct standard answers in the literature; validity inference (σ ⊦vφ for every substitution τ, the validity of τ[σ] entails the validity of τ[φ]), and truth inference (σ⊦l φ if for every substitution τ, the truth of τ[σ] entails the truth of τ[φ]). In this paper we introduce a general semantic framework that allows us to investigate the notion of inference more carefully. Validity inference and truth inference are in some sense the extremal points in our framework. We investigate the relationship between various types of inference in our general framework, and consider the complexity of deciding if an inference rule is sound, in the context of a number of logics of interest: classical propositional logic, a nonstandard propositional logic, various propositional modal logics, and first-order logic.
Abstract classes with few models have ‘homogeneous-universal’ models
Authors: Baldwin J. , Shelah S. 
Published: May 2006

This paper is concerned with a class K of models and an abstract notion of submodel ≤. Experience in first order model theory has shown the desirability of finding a ‘monster model’ to serve as a universal domain for K. In the original constructions of Jónsson and Fraïssé, K was a universal class and ordinary substructure played the role of ≤. Working with a cardinal λ satisfying λ<λ = λ guarantees appropriate downward Löwenheim-Skolem theorems; the existence and uniqueness of a homogeneous-universal model appears to depend centrally on the amalgamation property. We make this apparent dependence more precise in this paper.The major innovation of this paper is the introduction of a weaker notion (chain homogeneous-universal) to replace the natural notion of (K, <)-homogeneous-universal model. Modulo a weak extension of ZFC (provable if V = L), we show (Corollary 5.24) that a class K obeying certain minimal restrictions satisfies a fundamental dichotomy. For arbitrarily large λ, either K has the maximal number of models in power λ or K has a unique chain homogeneous-universal model of power λ. We show (5.25) in a class with amalgamation this dichotomy holds for the notion of K-homogeneous-universal model in the more normal sense.The methods here allow us to improve our earlier results [5] in two other ways: certain requirements on all chains of a given length are replaced by requiring winning strategies in certain games; the notion of a canonically prime model is avoided. A full understanding of these extensions requires consideration of the earlier papers but we summarize them quickly here.
Counting finite models
Authors: Woods Alan R. 
Published: May 2006

AbstractLetφbe a monadic second order sentence about a finite structure from a classwhich is closed under disjoint unions and has components. Compton has conjectured that if the number ofnelement structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilitiesν(φ)(μ(φ)respectively) forφalways exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number of single component-structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates.
Possible PCF algebras
Authors: Jech Thomas , Shelah Saharon 
Published: May 2006

AbstractThere exists a familyof sets of countable ordinals such that:(1) maxBα=α,(2) ifα∈BβthenBα⊆Bβ,(3) ifλ≤αandλis a limit ordinal thenBα∩λis not in the ideal generated by theBβ,β<α, and by the bounded subsets ofλ,(4) there is a partitionofω1such that for everyαand everyn,Bα∩Anis finite.
The entire NS ideal on can be precipitous
Authors: Goldring Noa 
Published: May 2006

The main result of this note is showing that if γ and μ are regular uncountable cardinals with γ ≤ μ then the non-stationary ideal (henceforth the NS ideal) on can be precipitous. This strengthens a result of [1] showing, under the same hypotheses, that a restriction of this ideal can be precipitous. See [1, Theorem 29, p. 36]. In fact, we show that even the strongly NS ideal on is precipitous in our model (since the former ideal is a restriction of the latter, the latter's being precipitous is a stronger assertion).More precisely, by starting with a model of “ZFC + ‘κ is a supercompact cardinal’ + ‘μ < κ is a regular uncountable cardinal’ ”, we generate a model of ZFC where all cardinals below and including μ are not collapsed and where the NS and strongly NS ideals on Pγμ are precipitous, for all regular uncountable γ which are less than or equal to μ.As far as consistency strength, we can obtain the same result even if κ is only Woodin in the ground model. However, the proof of this result is more complicated than in the case when κ is a supercompact cardinal. Furthermore, there are essentially no new ideas in adapting the proof relative to a supercompact cardinal to that relative to a Woodin cardinal beyond what appears in, e.g., [2]. We therefore give the complete proof relative to the existence of a supercompact cardinal and then briefly sketch the proof relative to the existence of a Woodin cardinal, using [2] as a reference.
Variations on a game of Gale (III): remainder strategies
Authors: Scheepers Marion , Weiss William 
Published: May 2006

An infinite set X is given. D. Gale, in correspondence with J. Mycielski, described the following game in which players one and two play an inning per positive integer: In the nth inning one chooses a finite subset Xn of X, and two chooses a point xn from (X1∪ … ∪Xn)\{x1,…,xn−1}. A playis won by two if . Gale asked whether two could have a winning strategy which depends for each n on knowledge of only the contents of the setIn mathematical terms, is there a function F defined on the collection of finite subsets of X such that:for every sequence X1, x1, …, Xn, xn,…. where each Xn is a finite subsetof X and for each nwe have We shall call a strategy of this sort a remainder strategy for two. If there is some finite subset U of X such that F(U) ∉ U, then F cannot be a winning remainder strategy for two, because one can defeat F by choosing U each inning. So, when studying remainder strategies for two we may as well assume that for each finite set U ⊂ X, F(U) ∈ U.