bluuebunny/crossref_metadata_2025_split huggingface dataset:
Partitioning large vector spaces
Authors: Schmerl James H. 
Published: March 2005

The theme of this paper is the generalization of theorems about partitions of the sets of points and lines of finite-dimensional Euclidean spaces ℝdto vector spaces over ℝ of arbitrary dimension and, more generally still, to arbitrary vector spaces over other fields so long as these fields are not too big. These theorems have their origins in the following striking theorem of Sierpiński [12] which appeared a half century ago.Sierpiński's Theorem.The Continuum Hypothesis is equivalent to: There is a partition{X, Y, Z}ofℝ3such that if ℓ is a line parallel to the x-axis[respectively:y-axis, z-axis]then X∩ℓ[respectively:Y∩ℓ, Z∩ℓ]is finite.The history of this theorem and some of its subsequent developments are discussed in the very interesting article by Simms [13]. Sierpiński's Theorem was generalized by Kuratowski [9] to partitions of ℝn+2inton+ 2 sets obtaining an equivalence with. The geometric character that Sierpiński's Theorem and its generalization by Kuratowski appear to have is bogus, since the lines parallel to coordinate axes are essentially combinatorial, rather than geometric, objects. The following version of Kuratowski's theorem emphasizes its combinatorial character.Kuratowski's Theorem.Let n < ω and A be any set. Then∣A∣ ≤ ℵnif and only if there is a partition P:An+2→n+ 2such that if i≤n+ 1and ℓ is a line parallel to the i-th coordinate axis, then{x∈ℓ:P(x) =i}is finite.
Recovering ordered structures from quotients of their automorphism groups
Authors: Giraudet M. , Truss J. K. 
Published: March 2005

AbstractWe show that the ‘tail’ of a doubly homogeneous chain of countable cofinality can be recognized in the quotient of its automorphism group by the subgroup consisting of those elements whose support is bounded above. This extends the authors' earlier result establishing this for the rationals and reals. We deduce that any group is isomorphic to the outer automorphism group of some simple lattice-ordered group.
A computably categorical structure whose expansion by a constant has infinite computable dimension
Authors: Hirschfeldt Denis R. , Khoussainov Bakhadyr , Shore Richard A. 
Published: March 2005

AbstractCholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.
Parallel strategies
Authors: Pudlák Pavel 
Published: March 2005

AbstractWe consider combinatorial principles based on playing several two person games simultaneously. We call strategies for playing two or more games simultaneously parallel. The principles are easy consequences of the determinacy of games, in particular they are true for all finite games. We shall show that the principles fail for infinite games. The statements of these principles are of lower logical complexity than the sentence expressing the determinacy of games, therefore, they can be studied in weak axiomatic systems for arithmetic (Bounded Arithmetic). We pose several open problems about the provability of these statements in Bounded Arithmetic and related computational problems.
Categoricity and U-rank in excellent classes
Authors: Lessmann Olivier 
Published: March 2005

AbstractLet be the class of atomic models of a countable first order theory. We prove that if is excellent and categorical in some uncountable cardinal, then each model is prime and minimal over the basis of a definable pregeometry given by a quasiminimal set. This implies that is categorical in all uncountable cardinals. We also introduce a U-rank to measure the complexity of complete types over models. We prove that the U-rank has the usual additivity properties, that quasiminimal types have U-rank 1, and that the U-rank of any type is finite in the uncountably categorical, excellent case. However, in contrast to the first order case, the supremum of the U-rank over all types may be ω (and is not achieved). We illustrate the theory with the example of free groups, and Zilber's pseudo analytic structures.
Ordering MAD families a la Katětov
Authors: Hrušák Michael , Ferreira Salvador García 
Published: March 2005

AbstractAn ordering (≤K) on maximal almost disjoint (MAD) families closely related to destructibility of MAD families by forcing is introduced and studied. It is shown that the order has antichains of size c and decreasing chains of length c+ bellow every element. Assuming t = c a MAD family equivalent to all of its restrictions is constructed. It is also shown here that the Continuum Hypothesis implies that for every ωω-bounding forcing ℙ of size c there is a Cohen-destructible, ℙ-indestructible MAD family. Finally, two other orderings on MAD families are suggested and an old construction of Mrówka is revisited.
The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
Authors: Merkle Wolfgang 
Published: March 2005

AbstractIt is shown that the class of Kolmogorov-Loveland stochastic sequences is not closed under selecting subsequences by monotonic computable selection rules. This result gives a strong negative answer to the question whether the Kolmogorov-Loveland stochastic sequences are closed under selecting sequences by Kolmogorov-Loveland selection rules, i.e., by not necessarily monotonic, partial computable selection rules. The following previously known results are obtained as corollaries. The Mises-Wald-Church stochastic sequences are not closed under computable permutations, hence in particular they form a strict superclass of the class of Kolmogorov-Loveland stochastic sequences. The Kolmogorov-Loveland selection rules are not closed under composition.
A proof-theoretic study of the correspondence of classical logic and modal logic
Authors: Kushida H. , Okada M. 
Published: March 2005

AbstractIt is well known that the modal logic S5 can be embedded in the classical predicate logic by interpreting the modal operator in terms of a quantifier. Wajsberg [10] proved this fact in a syntactic way. Mints [7] extended this result to the quantified version of S5; using a purely proof-theoretic method he showed that the quantified S5 corresponds to the classical predicate logic with one-sorted variable. In this paper we extend Mints' result to the basic modal logic S4; we investigate the correspondence between the quantified versions of S4 (with and without the Barcan formula) and the classical predicate logic (with one-sorted variable). We present a purely proof-theoretic proof-transformation method, reducing an LK-proof of an interpreted formula to a modal proof.
Arithmetical independence results using higher recursion theory
Authors: Arana Andrew 
Published: March 2005

AbstractWe extend an independence result proved in [1]. We show that for alln, there is a special set of Πnsentences {φa}a ∈ Hcorresponding to elements of a linear ordering (H, <H) of order type. These sentences allow us to build completions {Ta}a ∈ Hof PA such that fora <Hb, Ta∩ Σn⊂Tb∩ Σn, withφa∈Ta, ¬φa∈Th. Our method uses the Barwise-Kreisel Compactness Theorem.
Construction of saturated quasi-minimal structure
Authors: Itai Masanori , Tsuboi Akito , Wakai Kentaro 
Published: March 2005

AbstractThe notion of quasi-minimal structures was denned by B. Zil'ber as a natural generalization of minimal structures. Inspired by his work, we study here basic model theoretic properties of quasi-minimal structures. Main result is the construction of ω-saturated quasi-minimal models under ω-stability assumption.
Sous-groupes de Carter dans les groupes de rang de Morley fini
Authors: Frécon Olivier 
Published: March 2005

RésuméACarter subgroupis a self-normalizing locally nilpotent subgroup. For studying these subgroups in groups of finite Morley rank, we introduce the new notion of alocally closed subgroup. We show that every solvable group of finite Morley rank has a unique conjugacy class of Carter subgroups.
P versus NP and computability theoretic constructions in complexity theory over algebraic structures
Authors: Mainhardt Gunther 
Published: March 2005

AbstractWe show that there is a structure of countably infinite signature with P = N2P and a structure of finite signature with P = N1P and N1P ≠ N2P. We give a further example of a structure of finite signature with P ≠ N1P and N1P ≠ N1P. Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for some finite the class of -structures with P = N1P is not closed under ultraproducts and obtain as corollaries that this class is not ∆-elementary and that the class of -structures with P ≠ N1P is not elementary. Finally we prove that for all ƒ dominating all polynomials there is a structure of finite signature with the following properties: P ≠ N1P, N1P ≠ N2P, the levels N2TIME(ni) of N2P and the levels N1TIME(ni) of N1P are different for different i, indeed DTIME(ni′) ⊈ N2TIME(ni) if i ′ > i; DTIME(ƒ) ⊈ N2P, and N2P ⊈ DEC. DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of N2P is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts.
Hindman's theorem, ultrafilters, and reverse mathematics
Authors: Hirst Jeffry L. 
Published: March 2005

AbstractAssuming CH. Hindman [2] showed that the existence of certain ultrafilters on the power set of the natural numbers is equivalent to Hindman's Theorem. Adapting this work to a countable setting formalized in RCA0, this article proves the equivalence of the existence of certain ultrafilters on countable Boolean algebras and an iterated form of Hindman's Theorem, which is closely related to Milliken's Theorem. A computable restriction of Hindman's Theorem follows as a corollary.
Generic Σ31 absoluteness
Authors: Friedman Sy D. 
Published: March 2005

In this article we study the strength of absoluteness (with real parameters) in various types of generic extensions, correcting and improving some results from [3]. (In particular, see Theorem 3 below.) We shall also make some comments relating this work to the bounded forcing axioms BMM, BPFA and BSPFA.The statement “ absoluteness holds for ccc forcing” means that if a formula with real parameters has a solution in a ccc set-forcing extension of the universe V, then it already has a solution in V. The analogous definition applies when ccc is replaced by other set-forcing notions, or by class-forcing.Theorem 1. [1] absoluteness for ccc has no strength; i.e., if ZFC is consistent then so is ZFC + absoluteness for ccc.The following results concerning (arbitrary) set-forcing and class-forcing can be found in [3].Theorem 2 (Feng-Magidor-Woodin). (a) absoluteness for arbitrary set-forcing is equiconsistent with the existence of a reflecting cardinal, i.e., a regular cardinal κ such that H(κ) is ∑2-elementary in V.(b) absoluteness for class-forcing is inconsistent.We consider next the following set-forcing notions, which lie strictly between ccc and arbitrary set-forcing: proper, semiproper, stationary-preserving and ω1-preserving. We refer the reader to [8] for the definitions of these forcing notions.Using a variant of an argument due to Goldstern-Shelah (see [6]), we show the following. This result corrects Theorem 2 of [3] (whose proof only shows that if absoluteness holds in a certain proper forcing extension, then in L either ω1 is Mahlo or ω2 is inaccessible).
Valuation theoretic content of the Marker-Steinhorn theorem
Authors: Tressl Marcus 
Published: March 2005

The Marker-Steinhorn Theorem (cf. [2] and [3]), says the following. If T is an o-minimal theory and M ≺ N is an elementary extension of models of T such that M is Dedekind complete in N, then for every N-definable subset X of Nk, the trace X ∩ Mk is M-definable. The original proof in [2] gives an explicit method how to construct a defining formula of X ∩ Mk out of a defining formula of X. A geometric reformulation of the Marker-Steinhorn Theorem is the definability of Hausdorff limits of families of definable sets. An explicit construction of these Hausdorff limits for expansions of the real field has recently been achieved in [1]. Both proofs and also the treatment [3] are technically involved.Here we give a short algebraic, but not constructive proof, if T is an expansion of real closed fields. In fact we'll identify the statement of the Theorem with a valuation theoretic property of models of T (namely condition (†) below). Therefore our proof might be applicable to other elementary classes which expand fields, if a notion of dimension and a reasonable valuation theory are available.From now on, let T be an o-minimal expansion of real closed fields. We have to show the following (cf. [2], Th. 2.1. for this formulation). If M is a model of T and p is a tame n-type over M (i.e., M is Dedekind complete in M ⟨ᾱ⟩ := dcl(Mᾱ) for some realization ᾱ of p), then p is a definable type (cf. [4], 11 .b).
Analytic countably splitting families
Authors: Spinas Otmar 
Published: March 2005

AbstractA family A ⊆ (ω) is called countably splitting if for every countable F ⊆ [ω]ω, some element of A splits every member of F. We define a notion of a splitting tree, by means of which we prove that every analytic countably splitting family contains a closed countably splitting family. An application of this notion solves a problem of Blass. On the other hand we show that there exists an Fσ splitting family that does not contain a closed splitting family.
First order quantifiers in monadic second order logic
Authors: Keisler H. Jerome , Lotfallah Wafik Boulos 
Published: March 2005

AbstractThis paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].We introduce an operation existsn (S) on properties S that says “there are n components having S”. We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.We introduce another operation alt(S) on properties which has the same relationship with the Circuit Value Problem as reach(S) (defined in [JM01]) has with the Directed Reachability Problem. We use alt(S) to show that Πn ⊈ FO(Σn), Σn ⊈ FO(∆n). and ∆n+1 ⊈ FOB(Σn), solving some open problems raised in [Mat98].
Model theory of comodules
Authors: Crivei Septimiu , Prest Mike , Reynders Geert 
Published: March 2005

The purpose of this paper is to establish some basic points in the model theory of comodules over a coalgebra. It is not even immediately apparent that there is a model theory of comodules since these are not structures in the usual sense of model theory. Let us give the definitions right away so that the reader can see what we mean.Fix a field k. A k-coalgebra C is a k-vector space equipped with a k-linear map Δ: C → C ⊗ C, called the comultiplication (by ⊗ we always mean tensor product over k), and a k-linear map ε: C → k, called the counit, such that Δ⊗1C = 1C ⊗ Δ (coassociativity) and (1C ⊗ ε)Δ = 1C = (ε ⊗ 1C)Δ, where we identify C with both k ⊗ C and C ⊗ k. These definitions are literally the duals of those for a k-algebra: express the axioms for C′ to be a k-algebra in terms of the multiplication map μ: C′ ⊗ C′ → C′ and the “unit” (embedding of k into C′), δ: k → C′ in the form that certain diagrams commute and then just turn round all the arrows. See [5] or more recent references such as [7] for more.
Splittings of effectively speedable sets and effectively levelable sets
Authors: Omanadze Roland SH. 
Published: March 2005

AbstractWe prove that a computably enumerable set A is effectively speedable (effectively levelable) if and only if there exists a splitting (A0, A1) of A such that both A0 and A1 are effectively speedable (effectively levelable). These results answer two questions raised by J. B. Remmel.
Standard sets in nonstandard set theory
Authors: Andreev Petr , Hrbacek Karel 
Published: March 2005

AbstractWe prove that Standardization fails in every nontrivial universe definable in the nonstandard set theory BST, and that a natural characterization of the standard universe is both consistent with and independent of BST. As a consequence we obtain a formulation of nonstandard class theory in the ∈-language.
Truth definitions in finite models
Authors: Kołodziejczyk Leszek Aleksander 
Published: March 2005

AbstractThe paper discusses the notion of finite model truth definitions (or FM-truth definitions), introduced by M. Mostowski as a finite model analogue of Tarski's classical notion of truth definition.We compare FM-truth definitions with Vardi's concept of the combined complexity of logics, noting an important difference: the difficulty of defining FM-truth for a logic does not depend on the syntax of , as long as it is decidable. It follows that for a natural there exist FM-truth definitions whose evaluation is much easier than the combined complexly of would suggest.We apply the general theory to give a complexity-theoretical characterization of the logics for which the classes (prenex classes of higher order logics) define FM-truth. For any d ≥ 2, m ≥ 1 we construct a family of syntactically defined fragments of which satisfy this characterization. We also use the classes to give a refinement of known results on the complexity classes captured by .We close with a few simple corollaries, one of which gives a sufficient condition for the existence, given a vocabulary σ, of a fixed number k such that model checking for all first order sentences over σ can be done in deterministic time nk.
Approximate Euler characteristic, dimension, and weak pigeonhole principles
Authors: Krajíček Jan 
Published: March 2005

AbstractWe define the notion of approximate Euler characteristic of definable sets of a first order structure. We show that a structure admits a non-trivial approximate Euler characteristic if it satisfies weak pigeonhole principle : two disjoint copies of a non-empty definable set A cannot be definably embedded into A, and principle CC of comparing cardinalities: for any two definable sets A, B either A definably embeds in B or vice versa. Also, a structure admitting a non-trivial approximate Euler characteristic must satisfy .Further we show that a structure admits a non-trivial dimension function on definable sets if and only if it satisfies weak pigeonhole principle : for no definable set A with more than one element can A2 definably embed into A.
A definability result for compact complex spaces
Authors: Radin Dale 
Published: March 2005

AbstractA compact complex space X is viewed as a 1-st order structure by taking predicates for analytic subsets of X, X x X, … as basic relations. Let f: X → Y be a proper surjective holomorphic map between complex spaces and set Xy ≔ f−1(y). We show that the setis analytically constructible, i.e.. is a definable set when X and Y are compact complex spaces and f: X → Y is a holomorphic map. The analogous result in the context of algebraic geometry gives rise to the definability of Morley degree.
Wild edge colourings of graphs
Authors: Džamonja Mirna , Komjáth Péter , Morgan Charles 
Published: March 2005

AbstractWe prove consistent, assuming there is a supercompact cardinal, that there is a singular strong limit cardinalμ, of cofinalityω, such that everyμ+-chromatic graphXonμ+has an edge colouringcofXintoμcolours for which every vertex colouringgofXinto at mostμmany colours has ag-colour class on whichctakes every value.The paper also contains some generalisations of the above statement in whichμ+is replaced by other cardinals >μ.
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
Authors: Krajíček Jan 
Published: March 2005

AbstractThis article is a continuation of our search for tautologies that are hard even for strong propositional proof systems like EF. cf. [14, 15]. The particular tautologies we study, the τ-formulas. are obtained from any /poly map g; they express that a string is outside of the range of g, Maps g considered here are particular pseudorandom generators. The ultimate goal is to deduce the hardness of the τ-formulas for at least EF from some general, plausible computational hardness hypothesis.In this paper we introduce the notions of pseudo-surjective and iterable functions (related to free functions of [15]). These two properties imply the hardness of the τ-formulas from the function but unlike the hardness they are preserved under composition and iteration. We link the existence of maps with these two properties to the provability of circuit lower bounds, and we characterize maps g yielding hard τ-formulas in terms of a hitting set type property (all relative to a propositional proof system). We show that a proof system containing EF admits a pseudo-surjective function unless it simulates a proof system WF introduced by Jeřábek [11]. an extension of EF.We propose a concrete map g as a candidate function possibly pseudo-surjective or free for strong proof systems. The map is defined as a Nisan-Wigderson generator based on a random function and on a random sparse matrix. We prove that it is iterable in a particular way in resolution, yielding the output/input ratio n3 −ε (that improves upon a direct construction of Alekhnovich et al. [2]).
Parsimony hierarchies for inductive inference
Authors: Ambainis Andris , Case John , Jain Sanjay , Suraj Mandayam 
Published: March 2005

AbstractFreivalds defined an acceptable programming system independent criterion for learning programs for functions in which the final programs were required to be both correct and “nearly” minimal size. i.e.. within a computable function of being purely minimal size. Kinber showed that this parsimony requirement on final programs limits learning power. However, in scientific inference, parsimony is considered highly desirable. Alim-computable functionis (by definition) one calculable by a total procedure allowed to change its mind finitely many times about its output. Investigated is the possibility of assuaging somewhat the limitation on learning power resulting from requiring parsimonious final programs by use of criteria which require the final, correct programs to be “not-so-nearly” minimal size, e.g., to be within a lim-computable function of actual minimal size. It is shown that some parsimony in the final program is thereby retained, yet learning power strictly increases. Considered, then, are lim-computable functions as above but for whichnotations forconstructive ordinals are used to bound the number of mind changes allowed regarding the output. This is a variant of an idea introduced by Freivalds and Smith. For this ordinal notation complexity bounded version of lim-computability, the power of the resultant learning criteria form finely graded, infinitely ramifying, infinite hierarchies intermediate between the computable and the lim-computable cases. Some of these hierarchies, for the natural notations determining them, are shown to be optimally tight.