bluuebunny/crossref_metadata_2025_split huggingface dataset:
Two theorems on degrees of models of true arithmetic
Authors: Knight Julia , Lachlan Alistair H. , Soare Robert I. 
Published: May 2006

Let PA be the theory of first order Peano arithmetic, in the language L with binary operation symbols + and ·. Let N be the theory of the standard model of PA. We consider countable models M of PA such that the universe ∣M∣ is ω. The degree of such a model M, denoted by deg(M), is the (Turing) degree of the atomic diagram of M. The results of this paper concern the degrees of models of N, but here in the Introduction, we shall give a brief survey of results about degrees of models of PA.Let D0 denote the set of degrees d such that there is a nonstandard model of M of PA with deg(M) = d. Here are some of the more easily stated results about D0.(1) There is no recursive nonstandard model of PA; i.e., 0 ∈ D0.This is a result of Tennenbaum [T].(2) There existsd ∈ D0such thatd ≤ 0′.This follows from the standard Henkin argument.(3) There existsd ∈ D0such thatd < 0′.Shoenfield [Sh1] proved this, using the Kreisel-Shoenfield basis theorem.(4) There existsd ∈ D0such thatd′ = 0′.Jockusch and Soare [JS] improved the Kreisel-Shoenfield basis theorem and obtained (4).(5) D0 = Dc = De, where Dc denotes the set of degrees of completions of PA and De the set of degrees d such that d separates a pair of effectively inseparable r.e. sets.Solovay noted (5) in a letter to Soare in which in answer to a question posed in [JS] he showed that Dc is upward closed.
The definability of E(α)
Authors: Griffor E. R. , Normann D. 
Published: May 2006

The question of the limits of recursive enumerability was first formulated by Sacks (1980) and investigated further in Sacks (198?). E-recursion or “set recursion”, as a natural generalization of Kleene recursion in normal objects of finite type, was introduced by Normann (1978) in order to facilitate the study of the degrees of functionals. We shall extend the work of Sacks on the question of how definable is the E-closure of an ordinal α (written E(α)). We write gc(κ) to denote the largest τ < κ such that Lκ ⊨ “τ is a cardinal” and cf (τ) for τ ∈ ON to denote the cofinality of τ.In §1 we give the basic definitions and state the results of Silver and Friedman (1980) used by Sacks to show that if E(α) = Lκ and is not Σ1-admissible andthen P(gc(κ)) ∩ Lκ is indexical on Lκ and hence RE. We show in this case first that P(gc(κ)) ∩ Lκ indexical implies that Lκ is indexical (and hence RE).In §2 we introduce the notion of a “nonstandard stage comparison” and use it to extend the definability result of §1 to show that this Lκ is in fact REC. Finally we remark that E(α) is indexical if and only if E(α) is RE.
Algebraic theories with definable Skolem functions
Authors: van den Dries Lou 
Published: May 2006

(1.1) A well-known example of a theory with built-in Skolem functions is (first-order) Peano arithmetic (or rather a certain definitional extension of it). See [C-K, pp. 143, 162] for the notion of a theory with built-in Skolem functions, and for a treatment of the example just mentioned. This property of Peano arithmetic obviously comes from the fact that in each nonempty definable subset of a model we can definably choose an element, namely, its least member.(1.2) Consider now a real closed field R and a nonempty subset D of R which is definable (with parameters) in R. Again we can definably choose an element of D, as follows: D is a union of finitely many singletons and intervals (a, b) where – ∞ ≤ a < b ≤ + ∞; if D has a least element we choose that element; if not, D contains an interval (a, b) for which a ∈ R ∪ { − ∞}is minimal; for this a we choose b ∈ R ∪ {∞} maximal such that (a, b) ⊂ D. Four cases have to be distinguished:(i) a = − ∞ and b = + ∞; then we choose 0;(ii) a = − ∞ and b ∈ R; then we choose b − 1;(iii) a ∈ R and b ∈ = + ∞; then we choose a + 1;(iv) a ∈ R and b ∈ R; then we choose the midpoint (a + b)/2.It follows as in the case of Peano arithmetic that the theory RCF of real closed fields has a definitional extension with built-in Skolem functions.
On the structure of Ext(A,Z) in ZFC+
Authors: Sageev G. , Shelah S. 
Published: May 2006

A fundamental problem in the theory of abelian groups is to determine the structure of Ext(A, Z) for arbitrary abelian groups A. This problem was raised by L. Fuchs in 1958, and since then has been the center of considerable activity and progress.We briefly summarize the present state of this problem. It is a well-known fact thatwhere tA denotes the torsion subgroup of A. Thus the structure problem for Ext(A, Z) breakdown to the two distinct cases, torsion and torsion free groups. For a torsion group T,which is compact and reduced, and its structure is known explicitly [12].For torsion free A, Ext(A, Z) is divisible; hence it has a unique representationThus Ext(A, Z) is characterized by countably many cardinal numbers, which we denote as follows: ν0(A) is the rank of the torsion free part of Ext(A, Z), and νp(A) are the ranks of the p-primary parts of Ext(A, Z), Extp(A, Z).If A is free it is an elementary fact that Ext(A, Z) = 0. The second named author has shown [16] that in the presence of V = L the converse is also true. For countable torsion free, nonfree A, C. Jensen [13] has shown that νp(A) is either finite or and νp(A) ≤ ν0(A). Therefore, the case for uncountable, nonfree, torsion free groups A remains to be studied.
Cuts, consistency statements and interpretations
Authors: Pudlák Pavel 
Published: May 2006

Interpretability in reflexive theories, especially in PA, has been studied in many papers; see e.g. [3], [6], [7], [10], [11], [15], [26]. It has been shown that reflexive theories exhibit many nice properties, e.g. (1) if T, S are recursively enumerable reflexive, then T is interpretable in S iff every Π1 sentence provable in T is provable in S; and (2) if S is reflexive, T is recursively enumerable and locally interpretable in S (i.e. every finite part of T is interpretable in S), then T is globally interpretable in S (Orey's theorem, cf. [3]).In this paper we want to study such statements for nonreflexive theories, especially for finitely axiomatizable theories (which are never reflexive). These theories behave differently, although they may be quite close to reflexive theories, as e.g. GB to ZF. An important fact is that in such theories one can define proper cuts. By a cut we mean a formula with one free variable which defines a nonempty initial segment of natural numbers closed under the successor function. The importance of cuts for interpretations in GB was realized already by Vopěnka and Hájek in [30]. Pioneering work was done by Solovay in [24]. There he developed the method of “shortening of cuts”. Using this method it is possible to replace any cut by a cut which is contained in it and has some desirable additional properties; in particular it can be closed under + and ·. This introduces ambiguity in the concept of arithmetic in theories which admit proper cuts, namely, which cut (closed under + and ·) should be called the arithmetic of the theory? Cuts played the crucial role also in [20].
Decidable properties of finite sets of equations in trivial languages
Authors: Kalfa Cornelia 
Published: May 2006

In [4] I proved that in any nontrivial algebraic language there are no algorithms which enable us to decide whether a given finite set of equations Σ has each of the following properties except P2 (for which the problem is open):P0(Σ) = the equational theory of Σ is equationally complete.P1(Σ) = the first-order theory of Σ is complete.P2(Σ) = the first-order theory of Σ is model-complete.P3(Σ) = the first-order theory of the infinite models of Σ is complete.P4(Σ) = the first-order theory of the infinite models of Σ is model-complete.P5(Σ) = Σ has the joint embedding property.In this paper I prove that, in any finite trivial algebraic language, such algorithms exist for all the above Pi's. I make use of Ehrenfeucht's result [2]: The first-order theory generated by the logical axioms of any trivial algebraic language is decidable. The results proved here are part of my Ph.D. thesis [3]. I thank Wilfrid Hodges, who supervised it.Throughout the paper is a finite trivial algebraic language, i.e. a first-order language with equality, with one operation symbol f of rank 1 and at most finitely many constant symbols.
Well-behaved modal logics
Authors: Hodes Harold T. 
Published: May 2006

Much of the literature on the model theory of modal logics suffers from two weaknesses. Firstly, there is a lack of generality; theorems are proved piecemeal about this or that modal logic, or at best small classes of logics. Much of the literature, e.g. [1], [2], and [3], confines attention to structures with the expanding domain property (i.e., if wRu then Ā(w) ⊆ Ā(u)); the syntactic counterpart of this restriction is assumption of the converse Barcan scheme, a move which offers (in Russell's phrase) “all the advantages of theft over honest toil”. Secondly, I think there has been a failure to hit on the best ways of extending classical model theoretic notions to modal contexts. This weakness makes the literature boring, since a large part of the interest of modal model theory resides in the way in which classical model theoretic notions extend, and in some cases divide, in the modal setting. (The relation between α-recursion theory and classical recursion theory is analogous to that between modal model theory and classical model theory. Much of the work in α-recursion theory involved finding the right definitions (e.g., of recursive-in) and separating concepts which collapse in the classical case (e.g. of finiteness and boundedness).)The notion of a well-behaved modal logic is introduced in §3 to make possible rather general results; of course our attention will not be restricted to structures with the expanding domain property. Rather than prove piecemeal that familiar modal logics are well-behaved, in §4 we shall consider a class of “special” modal logics, which obviously includes many familiar logics and which is included in the class of well-behaved modal logics.
Monadic binary relations and the monad systems at near-standard points
Authors: Vakil Nader 
Published: May 2006

AbstractLet (*X, *T) be the nonstandard extension of a Hausdorff space (X, T). After Wattenberg [6], the monad m(x) of a near-standard point x in *X is defined as m{x) = μT(st(x)). Consider the relationFrank Wattenberg in [6] and [7] investigated the possibilities of extending the domain of Rns to the whole of *X. Wattenberg's extensions of Rns were required to be equivalence relations, among other things. Because the nontrivial ways of constructing such extensions usually produce monadic relations, the said condition practically limits (to completely regular spaces) the class of spaces for which such extensions are possible. Since symmetry and transitivity are not, after all, characteristics of the kind of nearness that is obtained in a general topological space, it may be expected that if these two requirements are relaxed, then a monadic extension of Rns to *X should be possible in any topological space. A study of such extensions of Rns is the purpose of the present paper. We call a binary relation W ⊆ *X × *X an infinitesimal on *X if it is monadic and reflexive on *X. We prove, among other things, that the existence of an infinitesimal on *X that extends Rns is equivalent to the condition that the space (X, T) be regular.
On partitions of the real line into compact sets
Authors: Newelski Ludomir 
Published: May 2006

The problem mentioned in the title has already been investigated by J. Baumgartner, J. Stern, A. Miller and many others (see [2] and [5]). We prove here some generalizations of theorems of Miller and Stern from [2] and [5]. We use standard set-theoretical notation. LetOne can check that in the above definition we can replace “compact subset of ωω” by “closed nowhere dense subset of ω2” or “Fσ and meager subset of ω2” (as any Fσ subset of ω2 can be presented as a disjoint countable union of compact sets).For functions f, g ϵ ωω we define f ≼ g if for all but finitely many n ϵ ω we have f(n) ≤ g(n). Let denote the least cardinality of a family A ⊆ ωω such that for any f ϵ ωω there is g ϵ A for which f ≼ g. It is easy to see that ≤ κω ≤ κ1. If f ϵ ωω then let ≼(f) = {h ϵωω: h ≼ f}.We find an axiom which implies = ω1 → κ1 = ω1, and which can be preserved by any ccc notion of forcing of “small cardinality”. We construct also in a generic model many partitions of ωω into compact sets preserved not only by any random real extension, but also by Sacks' notion of forcing. This shows that from some point of view Miller's modification of Sacks' forcing (from [2]) is the “minimal” one able to destroy a partition of ωω into compact sets.
Systematization of finite many-valued logics through the method of tableaux
Authors: Carnielli Walter A. 
Published: May 2006

AbstractThis paper presents a unified treatment of the propositional and first-order many-valued logics through the method of tableaux. It is shown that several important results on the proof theory and model theory of those logics can be obtained in a general way.We obtain, in this direction, abstract versions of the completeness theorem, model existence theorem (using a generalization of the classical analytic consistency properties), compactness theorem and Löwenheim-Skolem theorem.The paper is completely self-contained and includes examples of application to particular many-valued formal systems.
Definability in reducts of algebraically closed fields
Authors: Martin Gary A. 
Published: May 2006

LetKbe an algebraically closed field and letLbe itscanonical language; that is,Lconsists of all relations onKwhich are definable from addition, multiplication, and parameters fromK. Two sublanguagesL1andL2ofLaredefinably equivalentif each relation inL1can be defined by anL2-formula with parameters inK, and vice versa. The equivalence classes of sublanguages ofLform a quotient lattice of the power set ofLabout which very little is known. We will not distinguish between a sublanguage and its equivalence class.LetLmdenote the language of multiplication alone, and letLadenote the language of addition alone. Letf∈K[X, Y] and consider thealgebraic functiondefined byf(x, y) = 0 forx, y∈K. LetLfdenote the language consisting of the relation defined byf. The possibilities forLm∨Lfare examined in §2, and the possibilities forLa∨Lfare examined in §3. In fact the only comprehensive results known are under the additional hypothesis thatfactually defines a rational function (i.e., whenfis linear in one of the variables), and in positive characteristic, only expansions of addition by polynomials (i.e., whenfis linear and monic in one of the variables) are understood. It is hoped that these hypotheses will turn out to be unnecessary, so that reasonable generalizations of the theorems described below to algebraic functions will be true. The conjecture is thatLcoversLmand that the only languages betweenLaandLare expansions ofLaby scalar multiplications.
Decidable fragments of field theories
Authors: Tung Shih-Ping 
Published: May 2006

AbstractWe say φ is an ∀∃ sentence if and only if φ is logically equivalent to a sentence of the form ∀x∃yψ(x, y), where ψ(x, y) is a quantifier-free formula containing no variables except x and y. In this paper we show that there are algorithms to decide whether or not a given ∀∃ sentence is true in (1) an algebraic number field K, (2) a purely transcendental extension of an algebraic number field K, (3) every field with characteristic 0, (4) every algebraic number field, (5) every cyclic (abelian, radical) extension field over Q, and (6) every field.
Coinductive ℵ0-categorical theories
Authors: Schmerl James H. 
Published: May 2006

Let L be a countable language which contains only constant and relation symbols but no function symbols. All theories considered here will be L-theories. A theory is coinductive if it can be axiomatized by a set of ∃∀ sentences, and a structure is coinductive if its theory is.The object of this paper is to show that coinductive ℵ0-categorical structures are especially simple. First, they are ω-stable with Morley rank ≤ 1; and second, they have simple algebraic closures, by which is meant that the algebraic closure of the union of two sets is the union of their algebraic closures. While these two properties do not characterize coinductive ℵ0-categorical structures, they do characterize those structures which are cellular.We will say that a countable structure is cellular if there is a finite subset A0 ⊆ A and there are equivalence relations E and F on A∖A0 such that the following hold:(1) There are only finitely many E-classes.(2) If C is an E-class and D an F-class, then ∣C ∩ D ∣ = 1.(3) If a0, a1, …, ak − 1, b0, b1, …, bk − 1 Є A, then 〈a0, a1, …,ak − 1〉 and 〈b0,b1, …, bk − 1〉, satisfy the same quantifier-free formulas provided that:(a) if i < k and either ai Є A0 or bi Є A0, then ai = bi;(b) if i < k, then ai; and bi are E-equivalent; and(c) if i, j < k, then ai; is F-equivalent to aj if bj is F-equivalent to bj.The main result of this paper is the following theorem.Theorem 1. Ifis coinductive and ℵ0-categorical, thenis cellular.The results of this paper were obtained independently of similar results obtained by Lachlan which can be found in [4] and [5]. The proofs here are quite different.
Addendum to “The truth is never simple”
Authors: Burgess John P. 
Published: May 2006

The present note outlines an answer to a question listed as open in our recent survey article [1], familiarity with which is assumed.Let Γ be the class of all X ⊆ ω such that X is reducible to for some some arithmetical and some positive with Y ⊆ p(Y) for all Y.
Cardinality logics. Part II: Definability in languages based on ‘exactly’
Authors: Hodes Harold 
Published: May 2006

This paper continues the project initiated in [5]: a model-theoretic study of the concept of cardinality within certain higher-order logics. As recommended by an editor of this Journal, I will digress to say something about the project's motivation. Then I will review some of the basic definitions from [5]; for unexplained notation the reader should consult [5].The syntax of ordinary usage (with respect to the construction of arguments as well as the construction of individual sentences) makes it natural to classify numerals and expressions of the form ‘the number of F's’ as singular terms, expressions like ‘is prime’ or ‘is divisible by’ as predicates of what Frege called “level one”, and expressions like ‘for some natural number’ as first-order quantifier-phrases. From this syntatic classification, it is a short step—so short as to be frequently unnoticed—to a semantic thesis: that such expressions play the same sort of semantic role as is played by the paradigmatic (and nonmathematical) members of these lexical classes. Thus expressions of the first sort are supposed to designate objects (in post-Fregean terms, entities of type 0), those of the second sort to be true or false of tuples of objects, and those of the third sort to quantify over objects. All this may be summed up in Frege's dictum: “Numbers are objects.”
Definability and initial segments of c-degrees
Authors: Lubarsky Robert S. 
Published: May 2006

AbstractWe combine two techniques of set theory relating to mininal degrees of constructibility. Jensen constructed a minimal real which is additionally a singleton. Groszek built an initial segment of order type 1 + α*, for any ordinal α. This paper shows how to force a singleton such that the c-degrees beneath it, all represented by reals, are of type 1 + α*, for many ordinals α. We also examine the definability α needs to be so represented by a real.
Degree theoretical splitting properties of recursively enumerable sets
Authors: Ambos-Spies Klaus , Fejer Peter A. 
Published: May 2006

A recursively enumerable splitting of an r.e. set A is a pair of r.e. sets B and C such that A = B ∪ C and B ∩ C = ⊘. Since for such a splitting deg A = deg B ∪ deg C, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the degrees of r.e. splittings and the degree splittings of a set. We say a set A has the strong universal splitting property (SUSP) if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for deg A = b ∪ c there is an r.e. splitting B, C of A such that deg B = b and deg C = c. The goal of this paper is the study of this splitting property.In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP.
Weak cylindric set algebras and weak subdirect indecomposability
Authors: Andréka H. , Németi I. , Thompson R. J. 
Published: May 2006

AbstractIn this note we prove that the abstract property “weakly subdirectly indecomposable” does not characterize the class IWsα of weak cylindric set algebras. However, we give another (similar) abstract property characterizing IWsα. The original property does characterize the directed unions of members of IWsα iff α is countable. Free algebras will be shown to satisfy the original property.
Infinitary combinatorics and modal logic
Authors: Blass Andreas 
Published: May 2006

AbstractWe show that the modal propositional logic G, originally introduced to describe the modality “it is provable that”, is also sound for various interpretations using filters on ordinal numbers, for example the end-segment filters, the club filters, or the ineffable filters. We also prove that G is complete for the interpretation using end-segment filters. In the case of club filters, we show that G is complete if Jensen's principle □κ holds for all κ < ℵω; on the other hand, it is consistent relative to a Mahlo cardinal that G be incomplete for the club filter interpretation.
Saturating ultrafilters on N
Authors: Fremlin D. H. , Nyikos P. J. 
Published: May 2006

AbstractWe discuss saturating ultrafilters on N, relating them to other types of non-principal ultrafilter. (a) There is an (ω,c)-saturating ultrafllter on N iff 2λ≤ c for everyλ <c and there is no cover ofRby fewer than c nowhere dense sets, (b) Assume Martin's axiom. Then, for any cardinalκ, a nonprincipal ultrafllter on N is (ω, κ)-saturating iff it is almostκ-good. In particular, (i)p(κ)-point ultrafilters are (ω, κ)-saturating, and (ii) the set of (ω, κ)-saturating ultrafilters is invariant under homeomorphisms ofβN/N. (c) It is relatively consistent with ZFC to suppose that there is a Ramseyp(c)-point ultrafilter which is not (ω, c)-saturating.
Diverse classes
Authors: Baldwin John T. 
Published: May 2006

AbstractLet I(μ, Κ) denote the number of nonisomorphic models of power μ and IE(μ, Κ) the number of nonmutually embeddable models. We define in this paper the notion of a diverse class and use it to prove a number of results. The major result is Theorem B: For any diverse class Κ and μ greater than the cardinality of the language of Κ,From it we deduce both an old result of Shelah, Theorem C: If T is countable and λ0 > ℵ0 then for every μ > ℵ0, IE(μ, T) ≥ min(2μ, ⊐2), and an extension of that result to uncountable languages, Theorem D: If ∣T∣ < 2ωλ0 > ∣T∣, and ∣D(T)∣ = ∣T∣ then for μ > ∣T∣,
Uniformization principles
Authors: Mekler Alan H. , Shelah Saharon 
Published: May 2006

AbstractIt is consistent that for many cardinals λ there is a family of at least λ+ unbounded subsets of λ which have uniformization properties. In particular if it is consistent that a supercompact cardinal exists, then it is consistent that ℵω has such a family. We have applications to point set topology, Whitehead groups and reconstructing separable abelian p-groups from their socles.