bluuebunny/crossref_metadata_2025_split huggingface dataset:
Uncountable models and infinitary elementary extensions
Authors: Gregory John 
Published: May 2006

Let A be a countable admissible set (as defined in [1], [3]). The language LA consists of all infinitary finite-quantifier formulas (identified with sets, as in [1]) that are elements of A. Notationally, LA = A ∩ Lω1ω. Then LA is a countable subset of Lω1ω, the language of all infinitary finite-quantifier formulas with all conjunctions countable. The set is the set of Lω1ω sentences defined in 2.2 below. The following theorem characterizes those A-Σ1 sets Φ of LA sentences that have uncountable models.Main Theorem (3.1.). If Φ is an A-Σ1set of LA sentences, then the following are equivalent:(a) Φ has an uncountable model,(b) Φ has a model with a proper LA-elementary extension,(c) for every , ⋀Φ → C is not valid.This theorem was announced in [2] and is proved in §§3, 4, 5. Makkai's earlier [4, Theorem 1] implies that, if Φ determines countable structure up to Lω1ω-elementary equivalence, then (a) is equivalent to (c′) for all , ⋀Φ → C is not valid.The requirement in 3.1 that Φ is A-Σ1 is essential when the set ω of all natural numbers is an element of A. For by the example of [2], then there is a set Φ LA sentences such that (b) holds and (a) fails; it is easier to show that, if ω ϵ A, there is a set Φ of LA sentences such that (c) holds and (b) fails.
A topological analog to the Rice-Shapiro index theorem
Authors: Hay Louise , Miller Douglas 
Published: May 2006

Ever since Craig-Beth and Addison-Kleene proved their versions of the Lusin-Suslin theorem, work in model theory and recursion theory has demonstrated the value of classical descriptive set theory as a source of ideas and inspirations. During the sixties in particular, J.W. Addison refined the technique of “conjecture by analogy” and used it to generate a substantial number of results in both model theory and recursion theory (see, e.g., Addison [1], [2], [3]).During the past 15 years, techniques and results from recursion theory and model theory have played an important role in the development of descriptive set theory. (Moschovakis's book [6] is an excellent reference, particularly for the use of recursion-theoretic tools.) The use of “conjecture by analogy” as a means of transferring ideas from model theory and recursion theory to descriptive set theory has developed more slowly. Some notable recent examples of this phenomenon are in Vaught [9], where some results in invariant descriptive set theory reflecting and extending model-theoretic results are obtained and others are left as conjectures (including a version of the well-known conjecture on the number of countable models) and in Hrbacek and Simpson [4], where a notion analogous to that of Turing reducibility is used to study Borel isomorphism types. Moschovakis [6] describes in detail an effective descriptive set theory based in large part on classical recursion theory.
Analytic sets having incomparable kleene degrees
Authors: Weitkamp Galen 
Published: May 2006

One concern of descriptive set theory is the classification of definable sets of reals. Taken loosely ‘definable’ can mean anything from projective to formally describable in the language of Zermelo-Fraenkel set theory (ZF). Recursiveness, in the case of Kleene recursion, can be a particularly informative notion of definability. Sets of integers, for example, are categorized by their positions in the upper semilattice of Turing degrees, and the algorithms for computing their characteristic functions may be taken as their defining presentations. In turn it is interesting to position the common fauna of descriptive set theory in the upper semilattice of Kleene degrees. In so doing not only do we gain a perspective on the complexity of those sets common to the study of descriptive set theory but also a refinement of the theory of analytic sets of reals. The primary concern of this paper is to calculate the relative complexity of several notable coanalytic sets of reals and display (under suitable set theoretic hypothesis) several natural solutions to Post's problem for Kleene recursion.For sets of reals A and B one says A is Kleene recursive in B (written A ≤KB) iff there is a real y so that the characteristic function XA of A is recursive (in the sense of Kleene [1959]) in y, XB and the existential integer quantifier ∃; i.e. there is an integer e so that XA(x) ≃ {e}(x, y, XB, ≃). Intuitively, membership of a real x ϵ ωω in A can be decided from an oracle for x, y and B using a computing machine with a countably infinite memory and an ability to search and manipulate that memory in finite time. A set is Kleene semirecursive in B if it is the domain of an integer valued partial function recursive in y, XB and ≃ for some real y.
A combinatorial property of the homomorphism relation between countable order types
Authors: Landraitis Charles 
Published: May 2006

The relation ≪ (is a homomorphic image of) between (linear) order types has properties similar to those of the better known relation ≤ (is embeddable in). For example, the order type η of the rationals not only embeds every countable order type but also maps homomorphically onto . If is scattered, then can be embedded in (ω* + ω)α for some α < ω1. In that case, is also a homomorphic image of (ω* + ω)α [Lan 2]. If is uncountable, then for some uncountable ordinal α, α ≪, α* ≪, or η ≪. Proofs of these facts are much the same for ≤ and ≪.The main theorem of [Lav 1] implies that the embedding relation better-quasiorders the set of countable order types. Our main theorem (§3) states the analogous result for the homomorphism relation. As a consequence, if 0, 1, … is an infinite sequence of countable order types, then there are i, j, i < j, such that i, is a homomorphic image of j. We observed in [Lan 1] that if this is true, then for each countable order type there is a sentence of Lω1ω such that if is a countable order type, then satisfies if and only if is a homomorphic image of . In fact, the motivation for the work leading to this paper came from this observation.On the negative side, it is pointed out (§3) that our theorem cannot be extended as far as that of [Lav 1].
Index sets and degrees of unsolvability
Authors: Stob Michael 
Published: May 2006

The characterization of classes of r.e. sets by their index sets has proved valuable in producing new results about the r.e. sets and degrees. The classic example is Yates' proof [5, Theorem 7] of Sacks' density theorem for r.e. degrees using his classification of {e: We ≤TD) as Σ3(D) whenever D is r.e. Theorem 1 of this paper is a refinement of this index set theorem of Yates which has already proved to have interesting consequences about the r.e. degrees. This theorem was originally announced by Kallibekov [1, Theorem 1]. Kallibekov there proposed a new and ingenious method for doing priority arguments which has also since been used by Kinber [2]. Unfortunately his proof to this particular theorem contains an error. We have a totally different proof using standard techniques which is of independent interest.The proof to Theorem 1 is an infinite injury priority argument. In §1 therefore we give a short summary of the infinite injury priority method. We draw heavily on the exposition of Soare [4] where a complete description of the method is given along with many examples. In §2 we prove the main theorem and also give what we think are the most interesting corollaries to this theorem announced by Kallibekov. In §3 we prove a theorem about Σ3 sets of indices of r.e. sets. This theorem is a strengthening of a theorem of Kinber [2, Theorem 1] which was proved using a modification of Kallibekov's technique. As application, we use our theorem to show that an r.e. set A has supersets of every r.e. degree iff A is not simple.
Equivalence between semantics for intuitionism. I
Authors: López-Escobar E. G. K. 
Published: May 2006

It is probably because intuitionism is founded on the concept of (abstract) proof that it has been possible to develop various kinds of models. The following is but a partial list: Gabbay [5], Beth [2], Kripke [8], Kleene [7], Läuchli [9], McKinsey and Tarski [10], Rasiowa and Sikorski [14], Scott [15], de Swart [16], and Veldman [17].The original purpose for having the models appears to have been for obtaining independence or consistency results for certain formalizations of intuitionism [see Beth [2], Prawitz [13]]; of course, if the models could be also justified as being plausible interpretations of intuitionistic thinking, so much the better. In fact, having some kind of plausible interpretation makes it much easier to work with the models. Occasionally the models were used to suggest possible extensions of the formal systems; for example, the Kripke models with constant domains have motivated interest in the formal logic CD which extends the Intuitionistic Predicate Calculus (IPC) by having the axiom schema
Ordinal analysis of simple cases of bar recursion
Authors: Howard W. A. 
Published: May 2006

The purpose of the following is to give an ordinal analysis of bar recursion of type 0 for the cases in which the bar recursion operator has type level 3 or 4. We show that the associated ordinals are the ε0th epsilon number and the first ε0-critical number, respectively. Also we analyze a restricted bar recursion operator of level 3 which provides the Gödel functional interpretation of an intuitionistic form of König's lemma. The ordinal in this case is ε0.Let + BR0 be Gödel's theory of primitive recursive functional of finite type extended by functors Φ for bar recursion of type zero. To make bar recursion resemble transfinite recursion more closely, and thereby facilitate the ordinal analysis, we extend + BR0 to a system of terms . By Theorem 1.1a term of + BR0 which is computable by the rules of is already computable by the rules of + BR0, so it is sufficient to give an ordinal analysis of the terms of .A term H of is said to be semi-closed if its free variables have level not exceeding 1. If, in addition, H has level not exceeding 2, then an ordinal measure for H is given by a length for one of its computation trees. We call this a computation size for H. Let F(X) be a term whose free variables have level not exceeding 2, and suppose the variable X of type 2 is the only free variable of level 2.
The κ-closed unbounded filter and supercpmpact cardinals
Authors: Spector Mitchell 
Published: May 2006

The consistency of the Axiom of Determinateness (AD) poses a somewhat problematic question for set theorists. On the one hand, many mathematicians have studied AD, and none has yet derived a contradiction. Moreover, the consequences of AD which have been proven form an extensive and beautiful theory. (See [5] and [6], for example.) On the other hand, many extremely weird propositions follow from AD; these results indicate that AD is not an axiom which we can justify as intuitively true, a priori or by reason of its consequences, and we thus cannot add it to our set theory (as an accepted axiom, evidently true in the cumulative hierarchy of sets). Moreover, these results place doubt on the very consistency of AD. The failure of set theorists to show AD inconsistent over as short a time period as fifteen years can only be regarded as inconclusive, although encouraging, evidence.On the contrary, there is a great deal of rather convincing evidence that the existence of various large cardinals is not only consistent but actually true in the universe of all sets. Thus it becomes of interest to see which consequences of AD can be proven consistent relative to the consistency of ZFC + the existence of some large cardinal. Earlier theorems with this motivation are those of Bull and Kleinberg [2] and Spector ([14]; see also [12], [13]).
A generalized model companion for a theory of partially ordered fields
Authors: Stegbauer Werner 
Published: May 2006

The notion of a model companion for a first-order theory T was introduced and discussed in [1] and [2] as a generalization of the concept of a model completion of a theory. Both concepts reflect, on a general model theoretic level, properties of the theory of algebraically closed fields. The literature provides many examples of first-order theories with and without model companions—see [3] for a survey of these results. In this paper, we give a further generalization of the notion of a model companion.Roughly speaking, we allow instead of embeddings more general classes of maps (e.g. homomorphisms) and we allow any set of formulas which is preserved by these maps instead of existential formulas. This plan is worked out in detail in [5], where we discuss also several examples. One of these examples is given in this paper.In order to clarify the model theoretic background, we now introduce the relevant concepts and theorems from [5].
Martin's axiom in the model theory of LA
Authors: Stark W. Richard 
Published: May 2006

Working in ZFC + Martin's Axiom we develop a generalization of the Barwise Compactness Theorem which holds in languages of cardinality less than . Next, using this compactness theorem, an omitting types theorem for fewer than types is proved. Finally, in ZFC, we prove that this compactness result implies Martin's Axiom (the Equivalence Theorem). Our compactness theorem applies to a new class of theories—ccΣ-theories—which generalize the countable Σ-theories of Barwise's theorem. The Omitting Types Theorem and the Equivalence Theorem serve as examples illustrating the use of ccΣ-theories.Assume = (A, ε) or = (A, ε R1,…,Rm) where is admissible. L() is the first-order language with constants for elements of A and relation symbols for relations in . LA is A ⋂ L∞ω where the L of L∞ω is any language in A. A theory T in LA is consistent if there is no derivation in A of a contradiction from T. is LA with new constants ca for each a and A. The basic terms of consist of the constants of and the terms f(ca1,…,cam) built directly from constants using functions f of . The symbol t is used for basic terms. A theory T in LA is Σ if it is defined by a formula of L(). The formula φ⌝ is a logical equivalent of ¬φ defined by: (1) φ⌝ = ¬φ if φ is atomic; (2) (¬φ)⌝ = φ (3) (⋁φ∈Φ φ)⌝ = ⋀φ∈Φ φ⌝; (4) (⋀φ∈Φ φ) ⋁φ∈Φ φ⌝; (5) (∃χφ(x))⌝ ∀χφ⌝(x); ∀χφ(x))⌝ = ∃χφ⌝(x).
Splitting theorems for speed-up related to order of enumeration
Authors: Dawes A. M. 
Published: May 2006

AbstractIt is known from work of P. Young that there are recursively enumerable sets which have optimal orders for enumeration, and also that there are sets which fail to have such orders in a strong sense. It is shown that both these properties are widespread in the class of recursively enumerable sets. In fact, any infinite recursively enumerable set can be split into two sets each of which has the property under consideration. A corollary to this result is that there are recursive sets with no optimal order of enumeration.
Supercompact cardinals and trees of normal ultrafilters
Authors: Barbanel Julius B. 
Published: May 2006

Supercompact cardinals are usually defined in terms of the existence of certain normal ultrafilters. It is well known that there is a natural partial ordering on the collection of all normal ultrafilters associated with a super-compact cardinal, that of normal ultrafilter restriction. Using this notion, we define a tree structure T on the collection of normal ultrafilters associated with a fixed supercompact cardinal. Many results already appearing in the literature can be conveniently phrased in terms of structural properties of T (see, e.g. [4] or [6]). In this paper, we establish additional structural facts concerning T.In §1 we standardize our notation and review some of the basic facts and methods that will be used throughout. §2 begins with a presentation of an important technique, due to Solovay, which will be an important tool for us. Also in §2, we begin a detailed study of the structure of T in terms of branching and the existence of many successors to branches at limit levels. §3 contains results proving the existence of many nodes of T which do not have successors above certain levels of T. This complements work of Magidor [6] who established the existence of many nodes which have successors at all higher levels of T.
On the number of countable homogeneous models
Authors: Lo Libo 
Published: May 2006

The number of homogeneous models has been studied in [1] and other papers. But the number of countable homogeneous models of a countable theory T is not determined when dropping the GCH. Morley in [2] proves that if a countable theory T has more than ℵ1 nonisomorphic countable models, then it has such models. He conjectures that if a countable theory T has more than ℵ0 nonisomorphic countable models, then it has such models. In this paper we show that if a countable theory T has more than ℵ0 nonisomorphic countable homogeneous models, then it has such models.We adopt the conventions in [1]–[3]. Throughout the paper T is a theory and the language of T is denoted by L which is countable.Lemma 1. If a theory T has more than ℵ0types, then T hasnonisomorphic countable homogeneous models.Proof. Suppose that T has more than ℵ0 types. From [2, Corollary 2.4] T has types. Let σ be a Ttype with n variables, and T′ = T ⋃ {σ(c1, …, cn)}, where c1, …, cn are new constants. T′ is consistent and has a countable model (, a1, …, an). From [3, Theorem 3.2.8] the reduced model has a countable homogeneous elementary extension . σ is realized in . This shows that every type σ is realized in at least one countable homogeneous model of T. But each countable model can realize at most ℵ0 types. Hence T has at least countable homogeneous models. On the other hand, a countable theory can have at most nonisomorphic countable models. Hence the number of nonisomorphic countable homogeneous models of T is .In the following, we shall use the languages Lα (α = 0, 1, 2) defined in [2]. We give a brief description of them. For a countable theory T, let K be the class of all models of T. L = L0 is countable.
Games played on Boolean algebras
Authors: Foreman Matthew 
Published: May 2006

In this paper we consider the special case of the Banach-Mazur game played on a topological space when the space also has an underlying Boolean Algebra structure. This case was first studied by Jech [2]. The version of the Banach-Mazur game we will play is the following game played on the Boolean algebra:Players I and II alternate moves playing a descending sequence of elements of a Boolean algebra ℬ.Player II wins the game iff Πi∈ωbi ≠ 0. Jech first considered these games and showed:Theorem (Jech [2]). ℬ is (ω1, ∞)-distributive iff player I does not have a winning strategy in the game played on ℬ.If ℬ has a dense ω-closed subset then it is easy to see that player II has a winning strategy in this game. This paper establishes a partial converse to this, namely it gives cardinality conditions on ℬ under which II having a winning strategy implies ω-closure.In the course of proving the converse, we consider games of length > ω and generalize Jech's theorem to these games. Finally we present an example due to C. Gray that stands in counterpoint to the theorems in this paper.In this section we give a few basis definitions and explain our notation. These definitions are all standard.
Classifications of generalized index sets of open classes
Authors: Johnson Nancy 
Published: May 2006

The Rice-Shapiro Theorem [4] says that the index set of a class of recursively enumerable (r.e.) sets is r.e. if and only if consists of all sets which extend an element of a canonically enumerable sequence of finite sets. If an index of a difference of r.e. (d.r.e.) sets is defined to be the pair of indices of the r.e. sets of which it is the difference, then the following generalization due to Hay [3] is obtained: The index set of a class of d.r.e. sets is d.r.e. if and only if is empty or consists of all sets which extend a single fixed finite set. In that paper Hay also classifies index sets of classes consisting of d.r.e. sets which extend one of a finite collection of finite sets. These sets turn out to be finite Boolean combinations of r.e. sets. The question then arises “What about the classification of the index set of a class consisting of d.r.e. sets which extend an element of a canonically enumerable sequence of finite sets?” The results in this paper come from an attempt to answer this question.Since classes of sets which are Boolean combinations of r.e. sets form a hierarchy (the finite Ershov hierarchy, see Ershov [1]) with the r.e. and d.r.e. sets respectively levels 1 and 2 of this hierarchy, we may define index sets of classes of level n sets. If is a class of level n sets which extend some element of a canonically enumerable sequence of finite sets and if we let co-, then we extend the original classification question to the classification of the index sets of the classes and co-.Now if the sequence of finite sets enumerates only finitely many sets or if only finitely many of the finite sets are minimal under inclusion, then it is a routine computation to verify that the index sets of and co- are in the finite Ershov hierarchy. Thus we are interested in the case in which infinitely many of the sequence of finite sets are minimal under inclusion. However if the infinite sequence is fairly simple, for instance{0}, {1}, {2}, … then the r.e. index set of co- is Σ20-complete as well as the index sets of and co- for all levels n > 2. Since the finite Ershov hierarchy does not exhaust ⊿20 there is a lot of “room” between these two extreme cases.
Number of countable models
Authors: Pillay Anand 
Published: May 2006

We prove that a countable complete theory whose prime model has an infinite definable subset, all of whose elements are named, has at least four countable models up to isomorphism. The motivation for this is the conjecture that a countable theory with a minimal model has infinitely many countable models. In this connection we first prove that a minimal prime model A has an expansion by a finite number of constants A′ such that the set of algebraic elements of A′ contains an infinite definable subset.We note that our main conjecture strengthens the Baldwin–Lachlan theorem. We also note that due to Vaught's result that a countable theory cannot have exactly two countable models, the weakest possible nontrivial result for a non-ℵ0-categorical theory is that it has at least four countable models.§1. Notation and preliminaries. Our notation follows Chang and Keisler [1], except that we denote models by A, B, etc. We use the same symbol to refer to the universe of a model. Models we refer to are always in a countable language. For T a countable complete theory we let n(T) be the number of countable models of T up to isomorphism. ∃n means ‘there are exactly n’.
Paires de structures stables
Authors: Poizat Bruno 
Published: May 2006

Le paradigme de théorie stable est la théorie T d'un corps algébriquement clos; une autre théorie stable T′ est celle de la structure formée d'un corps algébriquement clos, avec en outre un symbole relationnel unaire interprétant un de ses sous-corps propres algébriquement clos. C'est à l'éclaircissement des rapports de T et de T′ qu'est consacré cet article.J'y considère une théorie complète T stable, et les structures formées d'un modèle N de T, avec en outre un symbole relationnel unaire (x) interprétant une restriction élémentaire M de N; j'appelle ces structures paires de modèles de T.Et je dis que la paire (N, M) est belle si d'une part M est ∣T∣+-saturé, et d'autre part pour tout n-uplet ā d'éléments de N, tout type, au sens de T, sur M ⋃ {α} est réalisé dans N.Le premier résultat (Théorème 4) est que deux belles paires sont élémentairement équivalentes. Plus précisément, si (N1, M1) et (N2, M2) sont deux belles paires, et si ā est dans la première, b¯ dans la seconde, le fait que le type de ā sur M1 et celui de b¯ sur M2 soient équivalents dans l'ordre fondamental au sens de T suffit (et est bien sûr nécessaire) pour que ā at b¯ aient même type (sur ⊘) au sens de la théorie T′ des belles paires.