bluuebunny/crossref_metadata_2025_split huggingface dataset:
Why some people are excited by Vaught's conjecture
Authors: Lascar Daniel 
Published: May 2006

§I. In 1961, R. L. Vaught ([V]) asked if one could prove, without the continuum hypothesis, that there exists a countable complete theory with exactly ℵ1 isomorphism types of countable models. The following statement is known as Vaught conjecture:Let T be a countable theory. If T has uncountably many countable models, then T hascountable models.More than twenty years later, this question is still open. Many papers have been written on the question: see for example [HM], [M1], [M2] and [St]. In the opinion of many people, it is a major problem in model theory.Of course, I cannot say what Vaught had in mind when he asked the question. I just want to explain here what meaning I personally see to this problem. In particular, I will not speak about the topological Vaught conjecture, which is quite another issue.I suppose that the first question I shall have to face is the following: “Why on earth are you interested in the number of countable models—particularly since the whole question disappears if we assume the continuum hypothesis?” The answer is simply that I am not interested in the number of countable models, nor in the number of models in any cardinality, as a matter of fact. An explanation is due here; it will be a little technical and it will rest upon two names: Scott (sentences) and Morley (theorem).
Pκλ combinatorics II: The RK ordering beneath a supercompact measure
Authors: Zwicker William S. 
Published: May 2006

AbstractWe characterize some large cardinal properties, such as μ-measurability and P2(κ)-measurability, in terms of ultrafilters, and then explore the Rudin-Keisler (RK) relations between these ultrafilters and supercompact measures on Pκ(2κ). This leads to the characterization of 2κ-supercompactness in terms of a measure on measure sequences, and also to the study of a certain natural subset, Fullκ, of Pκ(2κ) whose elements code measures on cardinals less than κ. The hypothesis that Fullκ is stationary (a weaker assumption than 2κ-supercompactness) is equivalent to a higher order Löwenheim-Skolem property, and settles a question about directed versus chain-type unions on Pκλ.
À l'ouest d'Éden
Authors: Poizat Bruno 
Published: May 2006

Le prophète des Crétois, nous le savions depuis longtemps, n'était qu'un menteur; pourtant, à l'aube de ce siècle, quand nous avons voulu traduire nos mathématiques en termes d'ensembles, notre conscience s'est troublée de la découverte de paradoxes.“Si R est une relation binaire entre éléments d'un ensemble (sic) E, il n'existe pas d'élément a de E, tel que pour tout x de E (a, x) satisfasse R si et seulement si (x, x) ne satisfait pas R.” Voilà un résultat bien banal! Quel est cet assaisonement fondationnel qui a le pouvoir de lui donner une saveur si troublante? C'est, sans doute, qu'il manifeste de façon brutale la contradiction d'un système d'axiomes auquel nous sommes viscéralement attachés, la “théorie des ensembles”, composée de l'axiome d'extensionalité (sans influence sur les paradoxes), et du schéma de compréhension (car nous avons d'excellentes raisons de vouloir rester dans le premier ordre, et d'éviter, à l'encontre de Zermelo, un axiome du second ordre).Nous croyons en premier lieu que la théorie des ensembles est vraie. C'est un peu délicat de préciser ce qu'on entend par là: quand on formalise l'arithmétique, il n'y a pas de confusion possible sur la structure de référence qu'on veut décrire; mais le modèle naturel, le “modèle standard” de la théorie des ensembles, le connait-on vraiment? L'auteur de ces lignes est incapable d'en décider: cela ne l'empêchera pas de faire appel à l'intuition ensembliste la plus débridée, ce qui montre qu'il n'est pas rebuté par l'incohérence plus que par la contradiction!
On the number of nonisomorphic models of an infinitary theory which has the infinitary order property. Part A
Authors: Grossberg Rami , Shelah Saharon 
Published: May 2006

AbstractLet κ and λ be infinite cardinals such that λ ≤ λ (we have new information for the case when κ ≤ λ). Let T be a theory in Lκ +, ω of cardinality at most κ, let . Now defineOur main concept in this paper is is a theory in Lκ +, ω of cardinality κ at most, and φ(x, y) ϵ Lκ +, ω}. This concept is interesting because ofTheorem 1. Let T ⊆ Lκ +, ω of cardinality ≤ κ, and. Ifthen (∀χ > κ)I(χ, T) = 2χ (where I(χ, T) stands for the number of isomorphism types of models of T of cardinality χ).Many years ago the second author proved that . Here we continue that work by provingTheorem 2. .Theorem 3. For everyκ ≤ λwe have.For some κ or λ we have better bounds than in Theorem 3, and this is proved via a new two cardinal theorem.Theorem 4. For every T ⊆ Lκ +, ω, and any set of formulas ⊆ Lκ +, ω such thatT ⊇ Lκ +, ω, if T is (, μ)-unstable for μ satisfyingμμ*(λ,κ) = μ then T is-unstable (i.e. for every χ ≥ λ, T is (, χ)-unstable). Moreover, T is Lκ +, ω-unstable.In the second part of the paper, we show that always in the applications it is possible to replace the function I(χ, T) by the function IE(χ, T), and we give an application of the theorems to Boolean powers.
Some properties of invariant sets
Authors: Byerly Robert E. 
Published: May 2006

In [1] two interesting invariance notions were introduced: the notions of a set of godel numbers being invariant to automorphisms of the structures (ω, ·) and (ω, E) respectively. Here, · and E are defined by n · m ≃ φn (m) and nEm if and only if n Є Wm, where {φn} and {Wn} are acceptable enumerations of the partial recursive functions and r.e. sets respectively. In this paper we continue the study of the invariant sets, and especially the invariant r.e. sets, of gödel numbers.We start off with an easy result which characterizes the Turing degrees containing invariant sets. We then take a closer look at r.e. sets invariant with respect to automorphisms of (ω,E). Using the characterization [1, Theorem 4.2] of such sets, we will derive a somewhat different characterization (which was stated, but not proved, in [1, Proposition 4.4]) and, using it as a tool for constructing invariant sets, prove that the r.e. sets invariant with respect to automorphisms of (ω, E) cannot be effectively enumerated.We will next discuss representations of r.e. sets invariant with respect to automorphisms of (ω, ·). Although these sets do not have as nice a characterization as the r.e. sets invariant with respect to automorphisms of (ω, E) do, the techniques of [1] can still profitably be used to investigate their structure. In particular, if f is a partial recursive function whose graph is invariant with respect to automorphisms of (ω, ·), then for every a in the domain of f, there is a term t(a) built up from a and · only such that f(a) ≃ t(a). This is an analog to [1, Corollary 4.3]. We will also prove an analog to a result mentioned in the previous paragraph: the r.e. sets invariant with respect to automorphisms of (ω, ·) cannot be effectively enumerated.
On modal systems having arithmetical interpretations
Authors: Avron Arnon 
Published: May 2006

We deal here with two modal logics, GL and Grz, that are known to have interesting arithmetical interpretations connected with the notion of provability. GL is the extensiom of K (or K4) by the schema □(□ A → A) → □ A, and Grz is the extension of S4 by □(□(A → □A) →A) → □A. GL is also known to be sound and complete with respect to the class of all Kripke models that are transitive, irreflexive and well founded. Grz bears the same relation to the corresponding reflexive models. We refer the reader to [1] for a full exposition of the subject. (See also [4], [2], [6].)In §I we develop a sequential calculus for both GL and Grz and give a semantical proof that both systems admit cut-elimination. (Incidentally, this provides an easy proof of the semantical completeness of the two systems.) With respect to GL this yields a correction of an error in [2].In §II we show that cut-elimination fails for QGL (the extension of GL to a language with quantifiers). We further show that, despite this failure, QGL still has some of GL's interesting properties (e.g., the disjunction property). We also show, using fixed-point techniques, that similar properties obtain if we take as semantics for QGL the arithmetical interpretation extended in the obvious way.We want to thank Professor H. Gaifman for his help while working on the subject.
On supervaluations in free logic
Authors: Woodruff Peter W. 
Published: May 2006

The concepts “classical valuation” and “supervaluation” were introduced by van Fraassen around 1966, to provide a semantic analysis of the then extant axiomatic systems of free logic. Consider an atomic sentenceand a “partial” model which fails to interpret c. Then (1) has no truth value in , nor doesWhile the valuelessness of (1) was found intuitively acceptable, that of (2) was not. Indeed, (2) and all other tautologies are theorems of free logic.Van Fraassen found a way to accommodate both intuitions. He interprets the unproblematic atomic sentences as usual, while “interpreting” those like (1) by simply assigning them a truth-value in arbitrary fashion. Then a truth-value for every sentence can be defined in the usual way; the result van Fraassen calls a “classical valuation” of the language. The arbitrary element in any given classical valuation is then eliminated by passage to the “supervaluation” over , which agrees with the classical valuations where they agree among themselves, and otherwise is undefined. In the supervaluation over , (1) is valueless but (2) true (since true on all classical valuations), as was required.There is a slight, but crucial oversimplification in the preceding account. Evaluation of the sentencerequires prior evaluation of the open formulaBut here mere assignment of truth-value is not enough; a whole set must be arbitrarily assigned as extension. The quantification over classical valuations involved in passage to the supervaluation thus involves an implicit quantification over subsets of the domain of : supervaluations are second order.
Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
Authors: Cooper S. B. 
Published: May 2006

As in Rogers [3], we treat the partial degrees as notational variants of the enumeration degrees (that is, the partial degree of a function is identified with the enumeration degree of its graph). We showed in [1] that there are no minimal partial degrees. The purpose of this paper is to show that the partial degrees below 0′ (that is, the partial degrees of the Σ2 partial functions) are dense. From this we see that the Σ2 sets play an analagous role within the enumeration degrees to that played by the recursively enumerable sets within the Turing degrees. The techniques, of course, are very different to those required to prove the Sacks Density Theorem (see [4, p. 20]) for the recursively enumerable Turing degrees.Notation and terminology are similar to those of [1]. In particular, We, Dx, 〈m, n〉, ψe are, respectively, notations for the e th r.e. set in a given standard listing of the r.e. sets, the finite set whose canonical index is x, the recursive code for (m, n) and the e th enumeration operator (derived from We). Recursive approximations etc. are also defined as in [1].Theorem 1. If B and C are Σ2sets of numbers, and B ≰e C, then there is an e-operator Θ withProof. We enumerate an e-operator Θ so as to satisfy the list of conditions:Let {Bs ∣ s ≥ 0}, {Cs ∣ s ≥ 0} be recursive sequences of approximations to B, C respectively, for which, for each х, х ∈ B ⇔ (∃s*)(∀s ≥ s*)(х ∈ Bs) and х ∈ C ⇔ (∃s*)(∀s ≥ s*)(х ∈ Cs).
The consistency of the axiom of universality for the ordering of cardinalities
Authors: Forti Marco , Honsell Furio 
Published: May 2006

T. Jech [4] and M. Takahashi [7] proved that given any partial ordering R in a model of ZFC there is a symmetric submodel of a generic extension of where R is isomorphic to the injective ordering on a set of cardinals.The authors raised the question whether the injective ordering of cardinals can be universal, i.e. whether the following axiom of “cardinal universality” is consistent:CU. For any partially ordered set (X, ≼) there is a bijection f:X → Y such that(i.e. x ≼ y iff ∃g: f(x) → f(y) injective). (See [1].)The consistency of CU relative to ZF0 (Zermelo-Fraenkel set theory without foundation) is proved in [2], but the transfer method of Jech-Sochor-Pincus cannot be applied to obtain consistency with full ZF (including foundation), since CU apparently is not boundable.In this paper the authors define a model of ZF + CU as a symmetric submodel of a generic extension obtained by forcing “à la Easton” with a class of conditions which add κ generic subsets to any regular cardinal κ of a ground model satisfying ZF + V = L.
Decidable subspaces and recursively enumerable subspaces
Authors: Ash C. J. , Downey R. G. 
Published: May 2006

AbstractA subspace V of an infinite dimensional fully effective vector space V∞ is called decidable if V is r.e. and there exists an r.e. W such that V ⊕ W = V∞. These subspaces of V∞ are natural analogues of recursive subsets of ω. The set of r.e. subspaces forms a lattice L(V∞) and the set of decidable subspaces forms a lower semilattice S(V∞). We analyse S(V∞) and its relationship with L(V∞). We show:Proposition. Let U, V, W ∈ L(V∞) where U is infinite dimensional andU ⊕ V = W. Then there exists a decidable subspace D such that U ⊕ D = W.Corollary. Any r.e. subspace can be expressed as the direct sum of two decidable subspaces.These results allow us to show:Proposition. The first order theory of the lower semilattice of decidable subspaces, Th(S(V∞), is undecidable.This contrasts sharply with the result for recursive sets.Finally we examine various generalizations of our results. In particular we analyse S*(V∞), that is, S(V∞) modulo finite dimensional subspaces. We show S*(V∞) is not a lattice.
A decidable subclass of the minimal Gödel class with identity
Authors: Goldfarb Warren D. , Gurevich Yuri , Shelah Saharon 
Published: May 2006

The minimal Gödel class with identity (MGCI) is the class of closed, prenex quantificational formulas whose prefixes have the form ∀x1∀x2∃x3 and whose matrices contain arbitrary predicate letters and the identity sign “=”, but contain no function signs or individual constants. The MGCI was shown undecidable (for satisfiability) in 1983 [Go2]; this both refutes a claim of Gödel's [Gö, p. 443] and settles the decision problem for all prefix-classes of quantification theory with identity.In this paper, we show the decidability of a natural subclass of the MGCI. The formulas in this subclass can be thought of as exploiting only half of the power of the existential quantifier. That is, since an MGCI formula has prefix ∀x1∀x2∃x3, in general its truth in a model requires for any elements a and b, the existence of both a witness for and a witness for . The formulas we consider demand less: they require, for any elements a and b, a witness for the unordered pair {a, b}, that is, a witness either for or for .
Cylindric-relativised set algebras have strong amalgamation
Authors: Németi I. 
Published: May 2006

In algebra, the properties of having the (strong) amalgamation property and epis being surjective are well investigated; see the survey [10]. In algebraic logic it is shown that to these algebraic properties there correspond interesting logical properties, see e.g. [15], [12], [4], and [8, p. 311, Problem 10 and the remark below it]. In the present paper we show that the varieties Crsα (of cylindric-relativised set algebras) and Boα (of Boolean algebras with operators) have the strong amalgamation property. These contrast to the following result proved in Pigozzi [15]: No class K with Gsα ⊆ K ⊆ CAα has amalgamation property. Note that Gsα ⊆ Crsα ⊆ Boα and CAα ⊆ Boα. For related results see [3], [1], [16], [11]. For more connections with logic and abstract model theory see [14] and §4.3 of [9].BA denotes the class of all Boolean algebras. Let α be any ordinal. From now on, throughout in the paper, α is an arbitrary but fixed ordinal. Recall from [7, p. 430, Definition 2.7.1] that an α-dimensional BA with operators, a Boα, is an algebra = 〈A, + −, ci, dij〉i, j ∈ α of the same similarity type as CAα's such that , is a BA and the operations ci (i ∈ α) are additive, i.e., ⊨ ci(x + y) = cix + ciy for all i ⊨ α. If ⊨ Boα then I is called the Boolean reduct of . Note that BA = Bo0. A Boα is said to be normal if {ci 0 = 0: i ∈ α} is valid in it, and a Boα is said to be extensive if {x ≤ cix: i ∈ α} is valid in it. Boα's were introduced in [17].The class Crsα of all cylindric-relativised set algebras is defined in Definition 1.1.1 (iii) of [8, p. 4]. We give a definition in the present paper, too—see Definition 5 below. It is shown in [13] that ICrsα is a variety.Our main result is (i) of Theorem 1 below, but we obtain (ii)–(vi), too, as a byproduct from the proof.
A probabilistic interpolation theorem
Authors: Hoover Douglas N. 
Published: May 2006

The probability logic is a logic with a natural interpretation on probability spaces (thus, a logic whose model theory is part of probability theory rather than a system for putting probabilities on formulas of first order logic). Its exact definition and basic development are contained in the paper [3] of H. J. Keisler and the papers [1] and [2] of the author. Building on work in [2], we prove in this paper the following probabilistic interpolation theorem for .Let L be a countable relational language, and let A be a countable admissible set with ω ∈ A (in this paper some probabilistic notation will be used, but ω will always mean the least infinite ordinal). is the admissible fragment of corresponding to A. We will assume that L is a countable set in A, as is usual in practice, though all that is in fact needed for our proof is that L be a set in A which is wellordered in A.Theorem. Let ϕ(x) and ψ(x) be formulas of LAP such thatwhere ε ∈ [0, 1) is a real in A (reals may be defined in the usual way as Dedekind cuts in the rationals). Then for any real d > ε¼, there is a formula θ(x) of (L(ϕ) ∩ L(ψ))AP such thatand
Decision problems concerning S-arithmetic groups
Authors: Grunewald Fritz , Segal Daniel 
Published: May 2006

This paper is a continuation of our previous work in [12]. The results, and some applications, have been described in the announcement [13]; it may be useful to discuss here, a little more fully, the nature and purpose of this work.We are concerned basically with three kinds of algorithmic problem: (1) isomorphism problems, (2) “orbit problems”, and (3) “effective generation”.(1) Isomorphism problems. Here we have a class of algebraic objects of some kind, and ask: is there a uniform algorithm for deciding whether two arbitrary members of are isomorphic? In most cases, the answer is no: no such algorithm exists. Indeed this has been one of the most notable applications of methods of mathematical logic in algebra (see [26, Chapter IV, §4] for the case where is the class of all finitely presented groups). It turns out, however, that when consists of objects which are in a certain sense “finite-dimensional”, then the isomorphism problem is indeed algorithmically soluble. We gave such algorithms in [12] for the following cases: = {finitely generated nilpotent groups}; = {(not necessarily associative) rings whose additive group is finitely generated}; = {finitely Z-generated modules over a fixed finitely generated ring}.Combining the methods of [12] with his own earlier work, Sarkisian has obtained analogous results with the integers replaced by the rationals: in [20] and [21] he solves the isomorphism problem for radicable torsion-free nilpotent groups of finite rank and for finite-dimensional Q-algebras.
Complete theories with only universal and existential axioms
Authors: Lachlan A. H. 
Published: May 2006

AbstractLet T be a complete first-order theory over a finite relational language which is axiomatized by universal and existential sentences. It is shown that T is almost trivial in the sense that the universe of any model of T can be written . where F is finite and I1, I2, …, In are mutually indiscernible over F. Some results about complete theories with ∃∀-axioms over a finite relational language are also mentioned.
Nonstandard characterizations of recursive saturation and resplendency
Authors: Smith Stuart T. 
Published: May 2006

AbstractWe prove results about nonstandard formulas in models of Peano arithmetic which complement those of Kotlarski, Krajewski, and Lachlan in [KKL] and [L]. This enables us to characterize both recursive saturation and resplendency in terms of statements about nonstandard sentences. Specifically, a model of PA is recursively saturated iff is nonstandard and -logic is consistent. is resplendent iff is nonstandard, -logic is consistent, and every sentence φ which is consistent in -logic is contained in a full satisfaction class for . Thus, for models of PA, recursive saturation can be expressed by a (standard) -sentence and resplendency by a -sentence.
Tarski on truth and logical consequence
Authors: Etchemendy John 
Published: May 2006

Tarski's writings on the concepts of truth and logical consequence rank among the most influential works in both logic and philosophy of the twentieth century. Because of this, it would be impossible to give a careful and accurate account of how far that influence reaches and of the complex route by which it spread. In logic, Tarski's methods of defining satisfaction and truth, as well as his work pioneering general model-theoretic techniques, have been entirely absorbed into the way the subject is presently done; they have become part of the fabric of contemporary logic, material presented in the initial pages of every modern textbook on the subject. In philosophy, the influence has been equally pervasive, extending not only to work in semantics and the philosophies of logic and language, but to less obviously allied areas such as epistemology and the philosophy of science as well.Rather than try to chart the wide-ranging influence of these writings or catalog the important research they have inspired, I will concentrate on various confusions and misunderstandings that continue to surround this work. For in spite of the extensive attention the work has received in the past fifty years, especially in the philosophical literature, misunderstandings of both conceptual and historical sorts are still remarkably widespread. Indeed in the philosophical community, recent reactions to Tarski's work on truth range from Karl Popper's “intense joy and relief” at Tarski's “legitimation” of the notion [1974, p. 399], to Hilary Putnam's assessment that “as a philosophical account of truth, Tarski's theory fails as badly as it is possible for an account to fail” [1985, p. 64]. Opinions have not exactly converged.