bluuebunny/crossref_metadata_2025_split huggingface dataset:
A new proof for Craig's theorem
Authors: Bellot P. 
Published: May 2006

Craig's theorem is a result about the cardinality of a proper basis for the theory of combinators. Its proof given in [3] was shown to be incomplete by André Chauvin [2]. By using a different approach, we give a very short proof of this theorem. We use the notation of [1].Definition 1. A combinator Q is proper if there exists a natural number n such that for arbitrary variables x1,…,xn we have the following contraction rule:where C is a pure combination of the variables x1,…,xn. Q is to be understood as an abstract symbol, not as a combination of S and K's. Therefore Q comes with a contraction rule.Definition 2. A set (Q1,…, Qm} of combinators is a basis for combinatory logic if for every finite set {x1,…, xk} of variables and every pure combination C of these variables, there exists a pure combination Q of Q1,…, Qm such that Qx1 … xk ↠ C.Craig's Theorem. Every basis for combinatory logic containing only proper combinators contains at least two elements.Proof. Let {Q} be a singleton basis for combinatory logic, and let us show that we cannot have combinatory completeness. This is an easy consequence of the next two lemmas.Lemma 1. Q is a projection. That is, Qx1 … xn ↠ xj, for some j.Proof. Let I be a proper combination of Q such that Ix ↠ x for a variable x, and let M be a term such that Ix ↠ M → x and M → x is a nontrivial contraction.
Subgroups of a free group and the axiom of choice
Authors: Howard Paul E. 
Published: May 2006

Nielsen [7] has proved that every subgroup of a free group of finite rank is free. The theorem was later strengthened by Schreier [8] by eliminating the finiteness restriction on the rank. Several proofs of this theorem (known as the Nielsen-Schreier theorem, henceforth denoted by NS) have appeared since Schreier's 1927 paper (see [1] and [2]). All proofs of NS use the axiom of choice (AC) and it is natural to ask whether NS is equivalent to AC. Läuchli has given a partial answer to this question by proving [6] that the negation of NS is consistent with ZFA (Zermelo-Fraenkel set theory weakened to permit the existence of atoms). By the Jech-Sochor embedding theorem (see [3] and [4]) ZFA can be replaced by ZF. Some form of AC, therefore, is needed to prove NS. The main purpose of this paper is to give a further answer to this question.In §2 we prove that NS implies ACffin (the axiom of choice for sets of finite sets). In §3 we show that a strengthened version of NS implies AC and in §4 we give a partial list of open problems.Let y be a set; ∣y∣ denotes the cardinal number of y and (y) is the power set of y. If p is a permutation of y and t ∈ y, the p-orbit of t is the set {pn(t): n is an integer}. Ifwe call p a cyclic permutation of y. If f is a function with domain y and x ⊆ y, f″x denotes the set {f(t):t ∈ x}. If A is a subset of a group (G, °) (sometimes (G, °) will be denoted by G) then A−1 = {x−1:x ∈ A} and [A] denotes the subgroup of G generated by A.
Decidable regularly closed fields of algebraic numbers
Authors: Dries Lou van den , Smith Rick L. 
Published: May 2006

A field K is regularly closed if every absolutely irreducible affine variety defined over K has K-rational points. This notion was first isolated by Ax [A] in his work on the elementary theory of finite fields. Later Jarden [J2] and Jarden and Kiehne [JK] extended this in different directions. One of the primary results in this area is that the elementary properties of a regularly closed field K with a free Galois group (on either finitely or countably many generators) are determined by the set of integer polynomials in one indeterminate with a zero in K. The method of proof employed in [J1], [J2] and [JK] is unusual for algebra since it is a measure-theoretic argument. In this brief summary we have not made any attempt at completeness. We refer the reader to the recent paper of Cherlin, van den Dries, and Macintyre [CDM] and to the forthcoming book by Fried and Jarden [FJ] for a more thorough discussion of the latest results. We would like to thank Moshe Jarden, Angus Macintyre, and Zoe Chatzidakis for their comments on an earlier version of this paper.A countable field K is ω-free if the absolute Galois group , where is the algebraic closure of K and is the free profinite group on ℵ0 generators.
The universal complementation property
Authors: Downey R.G. , Remmel J.B. 
Published: May 2006

Let V∞ be a fully effective infinite dimensional vector space over a recursive field F. That is, we assume that the universe of V∞ is a recursive set, the operations of addition and scalar multiplication are recursive, and there is a uniform effective procedure to decide whether any finite set {υ0, …, υn} of vectors from V∞ is independent. The lattice of recursively enumerable subspaces has been extensively studied since its introduction by Metakides and Nerode [MN1] (see for example, [Do2], [Gu], [KR], [Re1], [Re2], and [Sh]). For those unfamiliar with the literature on , we shall give a list of basic definitions required for this paper in §0.It is well known that complements in V∞ are not unique. For example, in [Re2] Remmel constructed r.e. spaces M1 and M2 and co-r.e. spaces Q1 and Q2 such that for all i, j ∈ {1, 2}, Mi ⊕ Qj = V∞ and M1 is supermaximal, M2 is not maximal, Q1 has a fully extendible basis, and Q2 has no extendible basis. We say a subspace Q of V∞ is fully co-r.e. if Q is generated by a co-r.e. subset of some recursive basis of V∞. Downey [Do2] has shown that every r.e. subspace of V∞ has a complement which is a fully co-r.e. subspace. Moreover suppose Q is any fully co-r.e. subspace, say Q = (C)* where C is a co-r.e. subset of a recursive basis B of V∞; if C is nonrecursive, then it is shown in [Do2] that Q has a decidable complement as well as a nondecidable nowhere simple complement.
Church-Rosser theorem for typed functional systems
Authors: Koletsos George 
Published: May 2006

Introduction. This paper contains a new proof of the Church-Rosser theorem for the typed λ-calculus, which also applies to systems with infinitely long terms.The ordinary proof of the Church-Rosser theorem for the general untyped calculus goes as follows (see [1]). If is the binary reduction relation between the terms we define the one-step reduction 1 in such a way that the following lemma is valid.Lemma. For all terms a and b we have: ab if and only if there is a sequence a = a0, …, an = b, n ≥ 0, such that aiiai + 1for 0 ≤ i < n.We then prove the Church-Rosser property for the relation 1 by induction on the length of the reductions. And by combining this result with the above lemma we obtain the Church-Rosser theorem for the relation .Unfortunately when we come to infinite terms the above lemma is not valid anymore. The difficulty is that, assuming the hypothesis for the infinitely many premises of the infinite rule, there may not exist an upper bound for the lengths n of the sequences ai = a0, …, an = bi (i < α); cf. the infinite rule (iv) in §6.A completely new idea in the case of the typed λ-calculus would be to exploit the type structure in the way Tait did in order to prove the normalization theorem. In this we succeed by defining a suitable predicate, the monovaluedness predicate, defined over the type structure and having some nice properties. The key notion permitting to define this predicate is the notion of I-form term (see below). This Tait-type proof has a merit, namely that it can be extended immediately to the case of infinite terms.
On the number of independent partitions
Authors: Tsuboi Akito 
Published: May 2006

In [3], Shelah defined the cardinals κn(T) and , for each theory T and n < ω. κn(T) is the least cardinal κ without a sequence (pi)i<κ of complete n-types such that pi is a forking extension of pj for all i < j < κ. It is essential in computing the stability spectrum of a stable theory. On the other hand is called the number of independent partitions of T. (See Definition 1.2 below.) Unfortunately this invariant has not been investigated deeply. In the author's opinion, this unfortunate situation of is partially due to the fact that its definition is complicated in expression. In this paper, we shall give equivalents of which can be easily handled.In §1 we shall state the definitions of κn(T) and . Some basic properties of forking will be stated in this section. We shall also show that if = ∞ then T has the independence property.In §2 we shall give some conditions on κ, n, and T which are equivalent to the statement . (See Theorem 2.1 below.) We shall show that does not depend on n. We introduce the cardinal ı(T), which is essential in computing the number of types over a set which is independent over some set, and show that ı(T) is closely related to . (See Theorems 2.5 and 2.6 below.) The author expects the reader will discover the importance of via these theorems.Some of our results are motivated by exercises and questions in [3, Chapter III, §7]. The author wishes to express his heartfelt thanks to the referee for a number of helpful suggestions.
Pas d'imaginaires dans l'infini!
Authors: Pillay Anand , Poizat Bruno 
Published: May 2006

Dans Poizat [1981], le second auteur a montré qu'un sous-groupe infiniment définissable d'un groupe stable était intersection de sous-groupes définissables; il a posé la question de savoir si une relation d'équivalence E, infiniment définissable dans un modèle M d'une théorie stable T, était conjonction de relations d'équivalence définissables. Nous allons voir ici que c'est presque exact: c'est vrai si T est totalement transcendante, et, dans le cas général de stabilité E a toujours un raffinement E1 (plus précisément, E1 est la conjonction de E et de la relation “x et y ont même type”) qui a cette propriété; cela montre que cette relation E n'introduit pas d'imaginaires d'une nature vraiment différente de celle des imaginaires de Shelah: dans une théorie stable, un imaginaire infinitaire n'est rien d'autre qu'un ensemble d'imaginaires finis.La démonstration du théorème principal de cette note s'appuie lourdement sur la construction Meq de Shelah, la machinerie de la déviation, les paramètres imaginaires canoniques pour la définition d'un type stable, etc…. Pour tout cela, les références adéquates sont Shelah [1978], Pillay [1983], et Poizat [1985, Chapitre 16].Nouscommençons par préciser ce que nous entendons par “relation d'équivalence infiniment définissable”: une collection de formules e(, ȳ), et ȳ étant de longueur n, telle que, pour tout modèle M de T, les couples (, ȳ) qui les satisfont toutes forment une rélation d'équivalence E.
Intermediate predicate logics determined by ordinals
Authors: Minari Pierluigi , Takano Mitio , Ono Hiroakira 
Published: May 2006

AbstractFor each ordinal α > 0, L(α) is the intermediate predicate logic characterized by the class of all Kripke frames with the poset α and with constant domain. This paper will be devoted to a study of logics of the form L(α). It will be shown that for each uncountable ordinal of the form α + η with a finite or a countable η(> 0), there exists a countable ordinal of the form β + η such that L(α + η) = L(β + η). On the other hand, such a reduction of ordinals to countable ones is impossible for a logic L(α) if α is an uncountable regular ordinal. Moreover, it will be proved that the mapping L is injective if it is restricted to ordinals less than ωω, i.e. α ≠ β implies L(α) ≠ L(β) for each ordinal α, β ≤ ωω.
On the angular component map modulo P
Authors: Pas Johan 
Published: May 2006

In [10] we introduced a new first order language for valued fields. This language has three sorts of variables, namely variables for elements of the valued field, variables for elements of the residue field and variables for elements of the value group. contains symbols for the standard field, residue field, and value group operations and a function symbol for the valuation. Essential in our language is a function symbol for an angular component map modulo P, which is a map from the field to the residue field (see Definition 1.2).For this language we proved a quantifier elimination theorem for Henselian valued fields of equicharacteristic zero which possess such an angular component map modulo P [10, Theorem 4.1]. In the first section of this paper we give some partial results on the existence of an angular component map modulo P on an arbitrary valued field.By applying the above quantifier elimination theorem to ultraproducts ΠQp/D, we obtained a quantifier elimination, in the language , for the p-adic field Qp; and this elimination is uniform for almost all primes p [10, Corollary 4.3]. In §2 we prove that our language is essentially stronger than the natural language for p-adic fields in the sense that the angular component map modulo P cannot be defined, uniformly for almost all p, in terms of the natural language for p-adic fields.
Rich models
Authors: Albert Michael H. , Grossberg Rami P. 
Published: May 2006

AbstractWe define a rich model to be one which contains a proper elementary substructure isomorphic to itself. Existence, nonstructure, and categoricity theorems for rich models are proved. A theory T which has fewer than min(2λ, ℶ2) rich models of cardinality λ (λ > ∣T∣) is totally transcendental. We show that a countable theory with a unique rich model in some uncountable cardinal is categorical in ℵ1 and also has a unique countable rich model. We also consider a stronger notion of richness, and use it to characterize superstable theories.
Backwards easton forcing and 0#
Authors: Stanley M. C. 
Published: May 2006

AbstractIt is shown that if κ is an uncountable successor cardinal in L[0#], then there is a normal tree T ϵ L[0#] of height κ such that 0# ∉ L[T], yet T is < κ-distributive in L[0#]. A proper class version of this theorem yields an analogous L[0#]-definable tree such that distinct branches in the presence of 0# collapse the universe. A heretofore unutilized method for constructing in L[0#] generic objects for certain L-definable forcings and “exotic sequences”, combinatorial principles introduced by C. Gray, are used in constructing these trees.
1-genericity in the enumeration degrees
Authors: Copestake Kate 
Published: May 2006

The structure of the Turing degrees of generic and n-generic sets has been studied fairly extensively, especially for n = 1 and n = 2. The original formulation of 1-generic set in terms of recursively enumerable sets of strings is due to D. Posner [11], and much work has since been done, particularly by C. G. Jockusch and C. T. Chong (see [5] and [6]).In the enumeration degrees (see definition below), attention has previously been restricted to generic sets and functions. J. Case used genericity for many of the results in his thesis [1]. In this paper we develop a notion of 1-generic partial function, and study the structure and characteristics of such functions in the enumeration degrees. We find that the e-degree of a 1-generic function is quasi-minimal. However, there are no e-degrees minimal in the 1-generic e-degrees, since if a 1-generic function is recursively split into finitely or infinitely many parts the resulting functions are e-independent (in the sense defined by K. McEvoy [8]) and 1-generic. This result also shows that any recursively enumerable partial ordering can be embedded below any 1-generic degree.Many results in the Turing degrees have direct parallels in the enumeration degrees. Applying the minimal Turing degree construction to the partial degrees (the e-degrees of partial functions) produces a total partial degree ae which is minimal-like; that is, all functions in degrees below ae have partial recursive extensions.
Coinductive formulas and a many-sorted interpolation theorem
Authors: Gropp Ursula 
Published: May 2006

AbstractWe use connections between conjunctive game formulas and the theory of inductive definitions to define the notions of a coinductive formula and its approximations. Corresponding to the theory of conjunctive game formulas we develop a theory of coinductive formulas, including a covering theorem and a normal form theorem for many sorted languages. Applying both theorems and the results on “model interpolation” obtained in this paper, we prove a many-sorted interpolation theorem for ω1ω-logic, which considers interpolation with respect to the language symbols, the quantifiers, the identity, and countably infinite conjunction and disjunction.
Some results on higher Suslin trees
Authors: David R. 
Published: May 2006

Higher Suslin trees have become a tool in some forcing constructions in set theory (see, for example, [D1] and [D2]). Most of the constructions using ω1 Suslin trees can be extended to κ+ Suslin trees for any regular cardinal κ. Some of these are given in §1.In many such constructions, sequences of Suslin trees are used. In §II we show, in various ways, that the generalization to sequences, even ω-sequences, of κ+ Suslin trees cannot be done.In these constructions the Suslin trees are used as forcing poset (the forcing adds a branch in the tree). There is another way to kill a Suslin tree, namely by adding a big antichain. Some results on this forcing are given in §III.Our notation is standard. If T is a tree and x ∈ T, then ∣x∣ is the height of x in T. We define Tα (or T(α)) = {x ∈ T: ∣x∣ = α} and T∣α = {x ∈ T: ∣x∣ < α}.If p and q are forcing conditions, p ≤ q means that p has more information than q.If (Tα: α ∈ I) is a sequence of trees, Π Tα will always mean the set of (xα: α ∈ I) such that xα ∈ Tα and ∣xα∣ = ∣xβ∣ for α, β ∈ I.For functions b, T,… we denote by b ∣α, T∣ α,… their restriction to α.If x is a sequence of ordinals and α is an ordinal, x∧α is the sequence obtained by concatenating α at the end of x.
The spectrum of resplendency
Authors: Baldwin John T. 
Published: May 2006

AbstractLet T be a complete countable first order theory and λ an uncountable cardinal. Theorem 1. If T is not superstable, T has 2λ resplendent models of power λ. Theorem 2. If T is strictly superstable, then T has at least min(2λ, ℶ2) resplendent models of power λ. Theorem 3. If T is not superstable or is small and strictly superstable, then every resplendent homogeneous model of T is saturated. Theorem 4 (with Knight). For each μ ∈ ω ∪ {ω, 2ω} there is a recursive theory in a finite language which has μ resplendent models of power κ for every infinite κ.
Extended ultrapowers and the Vopěnka-Hrbáček theorem without choice
Authors: Spector Mitchell 
Published: May 2006

AbstractWe generalize the ultrapower in a way suitable for choiceless set theory. Given an ultrafilter, forcing is used to construct an extended ultrapower of the universe, designed so that the fundamental theorem of ultrapowers holds even in the absence of the axiom of choice. If, in addition, we assume DC, then an extended ultrapower of the universe by a countably complete ultrafilter must be well-founded. As an application, we prove the Vopěnka-Hrbáček theorem from ZF + DC only (the proof of Vopěnka and Hrbáček used the full axiom of choice): if there exists a strongly compact cardinal, then the universe is not constructible from a set. The same method shows that, in L[2ω], there cannot exist a θ-compact cardinal less than θ (where θ is the least cardinal onto which the continuum cannot be mapped); a similar result can be proven for other models of the form L[A]. The result for L[2ω] is of particular interest in connection with the axiom of determinacy. The extended ultrapower construction of this paper is an improved version of the author's earlier pseudo-ultrapower method, making use of forcing rather than the omitting types theorem.
Extensions of arithmetic for proving termination of computations
Authors: Kent Clement F. , Hodgson Bernard R. 
Published: May 2006

AbstractKirby and Paris have exhibited combinatorial algorithms whose computations always terminate, but for which termination is not provable in elementary arithmetic. However, termination of these computations can be proved by adding an axiom first introduced by Goodstein in 1944. Our purpose is to investigate this axiom of Goodstein, and some of its variants, and to show that these are potentially adequate to prove termination of computations of a wide class of algorithms. We prove that many variations of Goodstein's axiom are equivalent, over elementary arithmetic, and contrast these results with those recently obtained for Kruskal's theorem.
Time polynomial in input or output
Authors: Gurevich Yuri , Shelah Saharon 
Published: May 2006

AbstractWe introduce the class PIO of functions computable in time that is polynomial in max {the length of input, the length of output}, observe that there is no notation system for total PIO functions but there are notation systems for partial PIO functions, and give an algebra of partial PIO functions from binary strings to binary strings.
Random models and the Maslov class
Authors: Goldfarb Warren 
Published: May 2006

In [GS] Gurevich and Shelah introduce a novel method for proving that every satisfiable formula in the Gödel class has a finite model (the Gödel class is the class of prenex formulas of pure quantification theory with prefixes ∀∀∃ … ∃). They dub their method “random models”: it proceeds by delineating, given any F in the Gödel class and any integer p, a set of structures for F with universe {1, …, p} that can be treated as a finite probability space S. They then show how to calculate an upper bound on the probability that a structure chosen at random from S makes F false; from this bound they are able to infer that if p is sufficiently large, that probability will be less than one, so that there will exist a structure in S that is a model for F. The Gurevich-Shelah proof is somewhat simpler than those known heretofore. In particular, there is no need for the combinatorial partitionings of finite universes that play a central role in the earlier proofs (see [G] and [DG, p. 86]). To be sure, Gurevich and Shelah obtain a larger bound on the size of the finite models, but this is relatively unimportant, since searching for finite models is not the most efficient method to decide satisfiability.Gurevich and Shelah note that the random model method can be used to treat the Gödel class extended by initial existential quantifiers, that is, the prefix-class ∀…∀∃…∃; but they do not investigate further its range of applicability to syntactically specified classes.
An expansion of F̃p
Authors: Chatzidakis Zoé 
Published: May 2006

Let K be a field of characteristic p. The map τ(X) = Xp − X is an additive endomorphism of K, with kernel Fp. The Galois extensions of K of order p are obtained by adjoining to K solutions to equations of the form Xp − X = a for some a in K. These extensions are called the Artin-Schreier extensions of K and have a cyclic Galois group.The study of Artin-Schreier extensions is very important for studying fields of characteristic p, in particular for studying valued fields of the form K((t)). An attempt at getting quantifier elimination for those fields would necessitate the adjunction to the language of fields of a cross-section for the function τ, i.e. a function σ such that τ ∘ σ is the identity on the image of τ. When K = Fp, such a cross-section is in fact definable in K((t)): it associates to τ(x) the element of {x, x + 1, …, x + p – 1} whose constant term is 0 (see [2]). When K is infinite, such a cross-section is usually not definable.The results presented in this paper originate from a question of L. van den Dries: is there a natural way of defining a cross-section σ for τ on F̃p, and is the theory of (F̃p, σ) decidable? (F̃p is the algebraic closure of Fp.)