bluuebunny/crossref_metadata_2025_split huggingface dataset:
On partitions into stationary sets
Authors: Prikry Karel , Solovay Robert M. 
Published: May 2006

We shall apply some of the results of Jensen [4] to deduce new combinatorial consequences of the axiom of constructibility, V = L. We shall show, among other things, that if V = L then for each cardinal λ there is a set A ⊆ λ such that neither A nor λ – A contain a closed set of type ω1. This is an extension of a result of Silver who proved it for λ = ω2, providing a partial answer to Problem 68 of Friedman [2].The main results of this paper were obtained independently by both authors.If λ is an ordinal, E is said to be Mahlo (or stationary) in λ, if λ – E does not contain a closed cofinal subset of λ.Consider the statements:(J1) There is a class E of limit ordinals and a sequence Cλ defined on singular limit ordinals λ such that(i) E ⋂ μ is Mahlo in μ for all regular > ω;(ii) Cλ is closed and unbounded in λ;(iii) if γ < is a limit point of Cλ, then γ is singular, γ ∉ E and Cγ = γ ⋂ Cλ.For each infinite cardinal κ:(J2,κ) There is a set E ⊂ κ+ and a sequence Cλ(Lim(λ), λ < κ+) such that(i) E is Mahlo in κ+;(ii) Cλ is closed and unbounded in λ;(iii) if cf(λ) < κ, then card Cλ < κ;(iv) if γ < λ is a limit point of Cλ then γ ∉ E and Cγ = ϣ ⋂ Cλ.
Least upper bounds for minimal pairs of α-R.E. α-degrees
Authors: Lerman Manuel 
Published: May 2006

The application of priority arguments to study the structure of the upper semilattice of α-r.e. α-degrees for all admissible ordinals α was first done successfully by Sacks and Simpson [5] who proved that there exist incomparable α-r.e. α-degrees. Lerman and Sacks [3] studied the existence of minimal pairs of α-r.e. α-degrees, and proved their existence for all admissible ordinals α which are not refractory. We continue the study of the α-r.e. α-degrees, and prove that no minimal pair of α-r.e. α-degrees can have as least upper bound the complete α-r.e. α-degree.The above-mentioned theorem was first proven for α = ω by Lachlan [1]. Our proof for α = ω differs from Lachlan's in that we eliminate the use of the recursion theorem. The proofs are similar, however, and a knowledge of Lachlan's proof will be of considerable aid in reading this paper.We assume that the reader is familiar with the basic notions or α-recursion theory, which can be found in [2] or [5].Throughout the paper a will be an arbitrary admissible ordinal. We identify a set A ⊆ α with its characteristic function, A(x) = 1 if x ∈ A, and A(x) = 0 if x ∉ A.If A ⊆ α and B ⊆ α, then A ⊕ B will denote the set defined byA ⊕ B(x) = A(y) if x = λ + 2z, λ is a limit ordinal, z < ω and y = λ + z,= B(y) if x = λ + 2z + 1, λ is a limit ordinal, z < ω, and y = λ + z.
The center of an orthologic
Authors: Jeffcott Barbara 
Published: May 2006

Since 1933, when Kolmogorov laid the foundations for probability and statistics as we know them today [1], it has been recognized that propositions asserting that such and such an event occurred as a consequence of the execution of a particular random experiment tend to band together and form a Boolean algebra. In 1936, Birkhoff and von Neumann [2] suggested that the so-called logic of quantum mechanics should not be a Boolean algebra, but rather should form what is now called a modular ortholattice [3]. Presumably, the departure from Boolean algebras encountered in quantum mechanics can be attributed to the fact that in quantum mechanics, one must consider more than one physical experiment, e.g., an experiment measuring position, an experiment measuring charge, an experiment measuring momentum, etc., and, because of the uncertainty principle, these experiments need not admit a common refinement in terms of which the Kolmogorov theory is directly applicable.Mackey's Axioms I–VI for quantum mechanics [4] imply that the logic of quantum mechanics should be a σ-orthocomplete orthomodular poset [5]. Most contemporary practitioners of quantum logic seem to agree that a quantum logic is (at least) an orthomodular poset [6], [7], [8], [9], [10] or some variation thereof [11]. P. D. Finch [12] has shown that every completely orthomodular poset is the logic arising from sets of Boolean logics, where these sets have a structure similar to the structures generally given to quantum logic. In all of these versions of quantum logic, a fundamental relation, the relation of compatibility or commutativity, plays a decisive role.
Almost strongly minimal theories. II
Authors: Baldwin John T. 
Published: May 2006

The notion of an almost strongly minimal theory was introduced in [1]. Such a theory is a particularly simple sort of ℵ1-categorical theory. In [1] we characterized this simplicity in terms of the Stone space of models of T. Here, we characterize almost strongly minimal theories which are not ℵ0-categorical in terms of D. M. R. Park's notion [4] of a theory with the strong elementary intersection property. In addition we prove a useful sufficient condition for an elementary theory to be an almost strongly minimal theory. Our notation is from [1] but this paper is independent of the results proved there. We do assume familiarity with §1 and §2 of [2].In [4], Park defines a theory T to have the strong elementary intersection property (s.e.i.p.) if for each model C of T and each pair of elementary submodels of C either is an elementary submodel of C. T has the nontrivial strong elementary intersection property (n.s.e.i.p.) if for each triple C, as above Park proves the following two statements equivalent:
Addition in nonstandard models of arithmetic
Authors: Phillips R. 
Published: May 2006

In [3] Kemeny made the following conjecture: Suppose *Z is a nonstandard model of the ring of integers Z. Letand let F be the subgroup of those cosets ā which contain an element of infinite height in *Z. Kemeny then asked if the ring R = {a: ā ∈ F} is also a nonstandard model of Z. If so then Goldbach's conjecture is false because Kemeny also shows in [3] that Goldbach's conjecture fails in R.The papers [1] and [5] by Gandy and Mendelson show that R is not a nonstandard model of Z but we give here a simpler proof based on Mendelson's paper. Suppose R is a nonstandard model of Z. Then each positive number in R is a sum of four squares. Choose a in R so that a is a positive element of R of infinite height in *Z. Then since a is infinite in *Z, a − 1 is positive. Thus , xi ∈ R for i = 1, …, 4. Now each xi must be of the form ai + ni, where ai has infinite height in *Z and ni, ∈ Z.
Ideal models and some not so ideal problems in the model theory of L(Q)
Authors: Bruce Kim B. 
Published: May 2006

It is the purpose of this paper to investigate the model theory of logic with a generalized quantifier; in particular the logic L(Q1) where Q1xφ(x) has the intended meaning “there exist uncountably many x such that φ(x)”. We do this from the point of view that the best way to study what happens in the so-called “ω1-standard” models of L(Q1) is to examine the countable ideal models of L(Q) that satisfy all of the axioms for L(Q1) (see definitions of ω1-standard and ideal models in §1). We believe that this study can be as fruitful for L(Q1) as the study of countable models of ZF has been for set theory.A major problem is formulating an adequate definition of submodel for countable ideal models that is compatible with that for ω1-standard models. Thus we begin the paper by discussing several possible definitions of the notion of submodel. We then adopt a particular definition of submodel and investigate model-completeness in L(Q). We define model-completeness both for ω1-standard models and for countable ideal models and compare the two notions. We also examine elimination of quantifiers, as well as investigating formulas preserved under submodels, again both for ω1-standar d and countable ideal models.
Single premise Post canonical forms defined over one-letter alphabets
Authors: Hughes Charles E. 
Published: May 2006

AbstractIn this paper we investigate some families of decision problems associated with a restricted class of Post canonical forms, specifically, those defined over one-letter alphabets whose productions have single premises and contain only one variable. For brevity sake, we call any such form an RPCF (Restricted Post Canonical Form). Constructive proofs are given which show, for any prescribed nonrecursive r.e. many-one degree of unsolvability D, the existence of an RPCF whose word problem is of degree D and an RPCF with axiom whose-decision problem is also of degree D. Finally, we show that both of these results are best possible in that they do not hold for one-one degrees.
Note on the fan theorem
Authors: Troelstra A. S. 
Published: May 2006

The principal aim of this paper is to establish a theorem stating, roughly, that the addition of the fan theorem and the. continuity schema to an intuitionistic system of elementary analysis results in a conservative extension with respect to arithmetical statements.The result implies that the consistency of first order arithmetic cannot be proved by use of the fan theorem, in addition to standard elementary methods—although it was the opposite assumption which led Gentzen to withdraw the first version of his consistency proof for arithmetic (see [B]).We must presuppose acquaintance with notation and principal results of [K, T], and with §1.6, Chapter II, and Chapter III, §4-6 of [T1]. In one respect we shall deviate from the notation in [K, T]: We shall use (n)x (instead of g(n, x)) to indicate the xth component of the sequence coded by n, if x < lth(n), 0 otherwise.We also introduce abbreviations n ≤* m, a ≤ b which will be used frequently below:
Sufficient conditions for the undecidability of intuitionistic theories with applications
Authors: Gabbay Dov M. 
Published: May 2006

Let Δ be a set of axioms of a theory Tc(Δ) of classical predicate calculus (CPC); Δ may also be considered as a set of axioms of a theory TH(Δ) of Heyting's predicate calculus (HPC). Our aim is to investigate the decision problem of TH(Δ) in HPC for various known theories Δ of CPC.Theorem I(a) of §1 states that if Δ is a finitely axiomatizable and undecidable theory of CPC then TH(Δ) is undecidable in HPC. Furthermore, the relations between theorems of HPC are more complicated and so two CPC-equivalent axiomatizations of the same theory may give rise to two different HPC theories, in fact, one decidable and the other not.Semantically, the Kripke models (for which HPC is complete) are partially ordered families of classical models. Thus a formula expresses a property of a family of classical models (i.e. of a Kripke model). A theory Θ expresses a set of such properties. It may happen that a class of Kripke models defined by a set of formulas Θ is also definable in CPC (in a possibly richer language) by a CPC-theory Θ′! This establishes a connection between the decision problem of Θ in HPC and that of Θ′ in CPC. In particular if Θ′ is undecidable, so is Θ. Theorems II and III of §1 give sufficient conditions on Θ to be such that the corresponding Θ′ is undecidable. Θ′ is shown undecidable by interpreting the CPC theory of a reflexive and symmetric relation in Θ′.
Preservation of elementary equivalence under scalar extension
Authors: Rose Bruce I. 
Published: May 2006

In this note we show that taking a scalar extension of two elementarily equivalent finite-dimensional algebras over the same field preserves elementary equivalence. The general question of whether or not tensor product preserves elementary equivalence was originally raised in [4]. In [3] Feferman relates an example of Ersov which answers the question negatively. Eklof and Olin [7] also provide a counterexample to the general question in the context of two-sorted structures. Thus the result proved below is a partial positive answer to a general question whose status has been resolved negatively. From the viewpoint of applied model theory it seems desirable to find contexts in which positive statements of preservation can be obtained. Our result does have an application; a corollary to it increases our understanding of what it means for two division algebras to be elementarily equivalent.All algebras are finite-dimensional algebras over fields. All algebras contain an identity element, but are not necessarily associative.Recall that the center of a not necessarily associative algebra A is the set of elements which commute and “associate” with all elements of A. The notion of a scalar extension is an important one in algebra. If A is an algebra over F and G is an extension field of F, then the scalar extension of A by G is the algebra A ⊗F G.
On the role of Ramsey quantifiers in first order arithmetic
Authors: Schmerl James H. , Simpson Stephen G. 
Published: May 2006

The purpose of this paper is to study a formal system PA(Q2) of first order Peano arithmetic, PA, augmented by a Ramsey quantifier Q2 which binds two free variables. The intended meaning of Q2xx′φ(x, x′) is that there exists an infinite set X of natural numbers such that φ(a, a′) holds for all a, a′ Є X such that a ≠ a′. Such an X is called a witness set for Q2xx′φ(x, x′). Our results would not be affected by the addition of further Ramsey quantifiers Q3, Q4, …, Here of course the intended meaning of Qkx1 … xkφ(x1,…xk) is that there exists an infinite set X such that φ(a1…, ak) holds for all k-element subsets {a1, … ak} of X.Ramsey quantifiers were first introduced in a general model theoretic setting by Magidor and Malitz [13]. The system PA{Q2), or rather, a system essentially equivalent to it, was first defined and studied by Macintyre [12]. Some of Macintyre's results were obtained independently by Morgenstern [15]. The present paper is essentially self-contained, but all of our results have been directly inspired by those of Macintyre [12].After some preliminaries in §1, we begin in §2 by giving a new completeness proof for PA(Q2). A by-product of our proof is that for every regular uncountable cardinal k, every consistent extension of PA(Q2) has a k-like model in which all classes are definable. (By a class we mean a subset of the universe of the model, every initial segment of which is finite in the sense of the model.)
Some theories associated with algebraically closed fields
Authors: Ash Chris , Rosenthal John 
Published: May 2006

We consider the effect on decidability of adding, to the decidable theory of algebraically closed fields of characteristic zero, relation symbols for algebraic independence or function symbols for differentiation. Our results show that the corresponding theories are usually undeeidable.Let k and K be algebraically closed fields of characteristic zero. Let K be an extension of k of transcendence degree n over k. Since k has characteristic 0, we may assume that the rational field, Q, is a subfield of k.Let Indn be the n-ary relation on K which holds for exactly those n-tuples from K which are algebraically independent over k.Let x1, …, xn be a transcendence base for K over k. For i = 1, 2, …, n, let Di: K → K be the partial differentiation function with respect to xi and this base.Let KnInd = (K, +, ·, Indn), n ≤ 1 and let KnDiff = (K, +, ·, D1, …, Dn), n ≤ 1 where K has transcendence degree n over k.We show that the theories of these structures are independent of k when k has infinite transcendence degree over Q, that KnDiff has undeeidable theory for n ≤ 1 and that KnInd has undeeidable theory for n ≤ 2. The theory of K1Ind is decidable.
The model-theoretic significance of complemented existential formulas
Authors: Weispfenning Volker 
Published: May 2006

Let T be an inductive, first-order theory in a language L, let E(L) denote the set of existential L-formulas, and let E(T) denote the distributive lattice of equivalence-classes φT of formulas φ ∈ E(L) with respect to equivalence in T. We consider three types of ‘complements’ in E(T): Let φT, ψT ∈ E(T) and suppose φT ∏ ψT = 0. Then ψT is a complement of φT, if φT ∐ ψT = 1; ψT is a pseudo-complement of φT, if for all μT ∈ E(T), (φT ∐ ψT) = 0 implies μT ≤ ψT; ψT is a “weak complement of φT, if for all μT ∈ E(T), (φT ⋰ ψT) ∐ μT = 0 implies μT = 0. The following facts are obvious: A complement of φT is also a pseudo-complement of φT and a pseudo-complement of φT is also a weak complement of φT. Any φT has at most one pseudo-complement; it is denoted by φT*. The relations ‘ψT is the complement of φT’ and ‘ψT is a weak complement of φT’ are symmetrical. We call φT (weakly, pseudo-) complemented if φT has a (weak, pseudo-) complement, and we call E(T) (weakly, pseudo-) complemented if every φT is (weakly, pseudo-) complemented.The object of this note is to characterize (weakly, pseudo-) complemented existential formulas in model-theoretic terms, and conversely to characterize some classical notions of Robinson style model theory in terms of these formulas. The following theorems illustrate the second approach.
The consistency of system Q
Authors: Fitch Frederic B. 
Published: May 2006

It will be shown that system Q of [1], with minor corrections, is free from contradiction and can be strengthened in various ways without destroying its consistency.By the system C*A will be meant the system that results in place of CA if rule 3.4.10 is omitted in [2] from the rules 3.4 defining PA and RA for an arbitrary class A of equations. We let P*A be the theorems of C*A and R*A be the antitheorems of C*A, just as PA and RA are respectively the theorems and antitheorems of CA in [2]. Similarly Γ* is the class that is defined exactly like the class Γ in 4.18 of [2] except that systems of the form C*A replace those of the form CA. The terminology and conventions of [2] will be assumed in what follows.Using the methods that were used to show in 5.9 of [2] that CΓ is free from contradiction, it is easy to show that C*A is free from contradiction for every class A of equations. (The fact that rule 3.4.10 is omitted causes the proof of consistency to work even for cases where A is not systematically closed in the sense of 4.11 of [2].)Just as it was shown in 4.19 of [2] that Γ is systematically closed (in the sense of 4.11 of [2]), so also it clearly can be shown that Γ* is systematically closed. This means, in effect, that the rule of substitution of equals for equals holds in the system C*Γ*.
Some initial segments of the Rudin-Keisler ordering
Authors: Blass Andreas 
Published: May 2006

AbstractA 2-affable ultrafilter has only finitely many predecessors in the Rudin-Keisler ordering of isomorphism classes of ultrafilters over the natural numbers. If the continuum hypothesis is true, then there is an ℵ1-sequence of ultrafilters Dα such that the strict Rudin-Keisler predecessors of Dα are precisely the isomorphs of the Dβ's for β < α.
Algebraically closed groups of large cardinality
Authors: Shelah Saharon , Ziegler Martin 
Published: May 2006

Let M be a countable algebraically closed group, κ an uncountable cardinal. We will prove in this paper the following theorems.Theorem 1. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M.Theorem 2. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M, and contains a free abelian group of cardinality κ.Theorem 3. There are 2κ nonisomorphic algebraically closed groups of cardinality κ which are ∞ – ω-equivalent to M.Theorem 4. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M and satisfies: Every subgroup of N of uncountable reqular cardinality contains a free subgroup of the same cardinality.Theorems 2 and 4 illustrate Theorem 3 by exhibiting two groups N ≡ ∞ωM of cardinality κ which are nonisomorphic by obvious reasons. We state and prove Theorem 1 separately in order to give an easy example of our principal tool: the use of automorphisms instead of indiscernibles (see §2).
operators and alternating sentences in arithmetic
Authors: Manevitz Larry , Stavi Jonathan 
Published: May 2006

Determining the truth value of self-referential sentences is an interesting and often tricky problem. The Gödel sentence, asserting its own unprovability in P (Peano arithmetic), is clearly true in N(the standard model of P), and Löb showed that a sentence asserting its own provability in P is also true in N (see Smorynski [Sm, 4.1.1]). The problem is more difficult, and still unsolved, for sentences of the kind constructed by Kreisel [K1], which assert their own falsity in some model N* of P whose complete diagram is arithmetically defined. Such a sentence χ has the property that N ⊨ iff N* ⊭ χ (note that ¬χ has the same property).We show in §1 that the truth value in N of such a sentence χ, after a certain normalization that breaks the symmetry between it and its negation, is determined by the parity of a natural number, called the rank of N, for the particular construction of N* used. The rank is the number of times the construction can be iterated starting from N and is finite for all the usual constructions. We also show that modifications of, e.g., Henkin's construction (in his completeness proof of predicate calculus) allow arbitrary finite values for the rank of N. Thus, on the one hand the truth value of χ in N, for a given “nice” construction of N*, is independent of the particular (normalized) choice of χ, and we shall see that χ is unique up to (provable) equivalence in P. On the other hand, the truth value in question is sensitive to minor changes in the definition of N* and its determination seems to be largely a combinatorial problem.
Completeness, invariance and λ-definability
Authors: Statman R. 
Published: May 2006

In [4] Gordon Plotkin considers the problem of characterizing the λ-definable functionals in full type structures. A plausible, but, as we shall see, quite false, conjecture is that a functional is λ-definable ⇔ it is invariant in the sense of Fraenkel and Mostowski. A better guess might be that the set of λ-definable functionals of type σ has a uniform (in σ) definition in type theory over all full type structures (Plotkin explicitly considers a certain sort of definition by means of “logical relations”). More or less generally, one may ask if the following question is decidable.Given: a functional F in a full type structure over a finite ground domain.Question: is Fλ-definable?We call the statement that this question is decidable Plotkin's λ-definability conjecture. We do not know if Plotkin's conjecture is true.In this note we consider several questions which quickly arise from Plotkin's conjecture. In §1, we ask which type structures satisfy λ-definability = invariance. We construct for each consistent set of equations a model satisfying this equality. From consideration of these models we obtain a number of syntactic corollaries including a reduction of βη-conversion to βη-conversion at a single type (Theorem 3), an “ω-rule” for βη-conversion (Proposition 6) and consistency with βη-conversion (Proposition 8), definability and indefinability results for versions of Kronecker's δ (Propositions 10 and 11), and a decidability result for the problem of inter-definability among combinators.