bluuebunny/crossref_metadata_2025_split huggingface dataset:
The model-companion of a class of structures
Authors: Cherlin G. L. 
Published: May 2006

If Σ is the class of all fields and Σ* is the class of all algebraically closed fields, then it is well known that Σ* is characterized by the following properties:(i) Σ* is the class of models of some first order theory K*.(ii) If m1m2 are in Σ* and m1 ⊆ m2 then m1 ≺ m2 (m1 is an elementary substructure of m2, i.e. any first order sentence true in m1 is true in m2).(iii) If m1 is in Σ then there is a structure m2 in Σ* such that m1 ⊆ m2.If Σ is some other class of models of a first order theory K and a subclass Σ* of Σ exists satisfying (i)–(iii) then Σ* is uniquely determined and K* (which is unique up to logical equivalence) is called the model-companion of K. This notion is a generalization of the fundamental notion of model-completion introduced and extensively studied by A. Robinson [6], When the model-companion exists it provides the basis for a satisfactory treatment of the notion of an algebraically closed model of K.Recently A. Robinson has developed a more general formulation of the notion of “algebraically closed” structures in Σ, which is applicable to any inductive elementary class Σ of structures (by elementary we always mean ECΔ). Condition (i) must be weakened to(i′) Σ* is closed under elementary substructure (i.e. if m1 is in Σ* and m2 ≺ m1 then m2 is in Σ*).
Some representations of Diophantine sets
Authors: Robinson Raphael M. 
Published: May 2006

A set D of natural numbers is called Diophantine if it can be defined in the formwhere P is a polynomial with integer coefficients. Recently, Ju. V. Matijasevič [2], [3] has shown that all recursively enumerable sets are Diophantine. From this, it follows that a bound for n may be given.We use throughout the logical symbols ∧ (and), ∨ (or), → (if … then …), ↔ (if and only if), ⋀ (for every), and ⋁ (there exists); negation does not occur explicitly. The variables range over the natural numbers 0,1,2,3, …, except as otherwise noted.It is the purpose of this paper to show that if we do not insist on prenex form, then every Diophantine set can be defined existentially by a formula in which not more than five existential quantifiers are nested. Besides existential quantifiers, only conjunctions are needed. By Matijasevič [2], [3], the representation extends to all recursively enumerable sets. Using this, we can find a bound for the number of conjuncts needed.Davis [1] proved that every recursively enumerable set of natural numbers can be represented in the formwhere P is a polynomial with integer coefficients. I showed in [5] that we can take λ = 4. (A minor error is corrected in an Appendix to this paper.) By the methods of the present paper, we can again obtain this result, and indeed in a stronger form, with the universal quantifier replaced by a conjunction.
Jump equivalence of the Δ20 hyperimmune sets
Authors: Cooper S. B. 
Published: May 2006

An infinite set A is said to be hyperhyperimmune (h.h.i.) if, for any collection of disjoint simultaneously recursively enumerable (r.e.) finite sets, A must fail to intersect with one of those sets. Thus the elements of an h.h.i. set are, in a sense, very elusive. D. A. Martin [3] showed that the degrees of h.h.i. sets with r.e. complements are exactly the r.e. degrees with jump 0″. More generally, C. G. Jockusch [2] found a′ ≥ 0″ to be a sufficient condition for a to be the degree of an h.h.i. set and found a′ ≥ 0′ to be necessary. However, it was also shown that in the degrees as a whole neither condition gave a characterization of the h.h.i. degrees. The purpose of this note is to prove that a′ = 0″does characterize the h.h.i. degrees below 0′.Theorem. The degrees below 0′ containing h.h.i. sets are exactly those degrees below 0′ with jump 0″.Proof. From [2], if a′ ≥ 0″, then a contains an h.h.i. set.Conversely, let A ∈ a where a′ < 0″ and a < 0′. Let {As ∣ s ≥ 0} be a recursive sequence of finite sets such that for each x, lims, Ax(x) exists and equals A(x).For a set B, let B[m] denote B ∩ [0, m], and (if B is finite) let ∣B∣ denote the cardinality of B.
Diagonalization in degree constructions
Authors: Posner D. , Epstein R. 
Published: May 2006

We present two theorems whose applications are to eliminate diagonalization arguments from a variety of constructions of degrees of unsolvability.All definitions and notations come from [1, Chapter 1]. We give a brief resumé of them here.We identify a set with its characteristic function. (A(x)= 1 if x ∈ A and A (x) = 0 if x ∉ A.) A string σ is the restriction of a characteristic function to a finite initial segment of natural numbers, lh(σ) = length of σ = n + 1 if σ = A[n] for some set A. (A [n] is the restriction of A to {m: m ≤ n}.) If i = 0 or 1, σ * i is defined as the string of length lh(σ) + 1 such that σ * i ⊇ σ and σ * i(lh(σ)) = i. We write σ ∣ τ if σ ⊉ τ and τ ⊉ σ.{Φn} is a listing of the partial recursive functionals. We write “A ≤TB” (“A is Turing reducible to B”) if ∃n∀xΦn(B)(x) = A(x).A partial function, T, from strings to strings is a tree if T is order preserving and for all strings, σ, if one of T(σ * 0), T(σ * 1) is defined then T(σ), T(σ * 0), T(σ * 1) are all defined and T(σ * 0)∣(σ * 1).
Syntactic characterisations of amalgamation, convexity and related properties
Authors: Bacsich Paul D. , Hughes Dafydd Rowlands 
Published: May 2006

We prove that certain syntactic conditions similar to separation principles on a theory are equivalent to semantic properties such as amalgamation and strong amalgamation, by showing that appropriate classes of structures are definable by Lω1ω-sentences. Then we characterise the elements of core models and thus give a natural proof of Rabin's characterisation of convex theories.The notion of a syntactic characterisation of a semantic property of a theory is by now fairly well known. The earliest such were the classical preservation theorems: For example, a theorem of Lyndon characterised the theories whose models were closed under homomorphic images as those with a set of positive axioms.Presumably the notion of syntactic characterisation can be made precise, but it is probably better at this stage to leave it vague. The general idea is that theories are “algebras” (cylindric algebras, or logical categories, with suitable extra structure) and that a semantic property P of theories is syntactically characterisable if the class of theories with P is an “elementary” class of “algebras.”When one codes countable theories as real numbers, a syntactically characterisable property will be arithmetical. The converse does not seem reasonable, especially as it is often fairly easy to prove a property arithmetical (using extra predicates, usually), when we may not be able to find a syntactic characterisation.
The characterization of monadic logic
Authors: Tharp Leslie H. 
Published: May 2006

The first section of this paper is concerned with the intrinsic properties of elementary monadic logic (EM), and characterizations in the spirit of Lindström [2] are given. His proofs do not apply to monadic logic since relations are used, and intrinsic properties of EM turn out to differ in certain ways from those of the elementary logic of relations (i.e., the predicate calculus), which we shall call EL. In the second section we investigate connections between higher-order monadic and polyadic logics.EM is the subsystem of EL which results by the restriction to one-place predicate letters. We omit constants (for simplicity) but take EM to contain identity. Let atypebe any finite sequence (possibly empty) of one-place predicate letters. A modelMof typehas a nonempty universe ∣M∣ and assigns to each predicate letterPofa subsetPMof ∣M∣.Let us take a monadic logicLto be any collection of classes of models, calledL-classes, satisfying the following:1. All models in a givenL-class are of the same type (called the type of the class).2. Isomorphic models lie in the sameL-classes.3. IfandareL-classes of the same type, thenandareL-classes.
Real-valued models with metric equality and uniformly continuous predicates
Authors: Katz Michael 
Published: May 2006

AbstractTwo real-valued deduction schemes are introduced, which agree on ⊢ ⊿ but not on Γ ⊢ ⊿, where Γ and ⊢ are finite sets of formulae. Using the first scheme we axiomatize real-valued equality so that it induces metrics on the domains of appropriate structures. We use the second scheme to reduce substitutivity of equals to uniform continuity, with respect to the metric equality, of interpretations of predicates in structures. This continuity extends from predicates to arbitrary formulae and the appropriate models have completions resembling analytic completions of metric spaces. We provide inference rules for the two deductions and discuss definability of each of them by means of the other.
A complete, decidable theory with two decidable models
Authors: Millar Terrence S. 
Published: May 2006

A well-known result of Vaught's is that no complete theory has exactly two nonisomorphic countable models. The main result of this paper is that there is a complete decidable theory with exactly two nonisomorphic decidable models.A model is decidable if it has a decidable satisfaction predicate. To be more precise, let T be a decidable theory, let {θn∣n < ω} be an effective enumeration of all formulas in L(T), and let be a countable model of T. For any indexing E = {ai∣ i < ω} of ∣∣, and any formula ϕ ∈ L(T), let ‘ϕE’ denote the result of substituting ‘ai’ for every free occurrence of ‘xi’ in ϕ, i < ω. Then is decidable just in case, for some indexing E of ∣∣, {n ∣ ⊨ θnE} is a recursive set of integers. It is easy to show that the decidability of a model does not depend on the choice of the effective enumeration of the formulas in L(T); we omit details. By a simple ‘effectivization’ of Henkin's proof of the completeness theorem (see Chang [1]) we haveFact 1. Every decidable consistent theory has a decidable model.Assume next that T is a complete decidable theory and {θn ∣ n < ω} is an effective enumeration of all formulas of L(T).
Logic in the twenties: the nature of the quantifier
Authors: Goldfarb Warren D. 
Published: May 2006

We are often told, correctly, that modern logic originated with Frege. For Frege clearly depicted polyadic predication, negation, the conditional, and the quantifier as the bases of logic; moreover, he introduced the idea of a formal system, and argued that mathematical demonstrations, to be fully precise, must be carried out within a formal language by means of explicitly formulated syntactic rules.Consequently Frege has often been read as providingallthe central notions that constitute our current understanding of quantification. For example, in his recent book on Frege [1973], Michael Dummett speaks of ”the semantics which [Frege] introduced for formulas of the language of predicate logic.” That is, “An interpretation of such a formula … is obtained by assigning entities of suitable kinds to the primitive nonlogical constants occurring in the formula … [T]his procedure is exactly the same as the modern semantic treatment of predicate logic” (pp. 89–90). Indeed, “Frege would therefore have had within his grasp the concepts necessary to frame the notion of the completeness of a formalization of logic as well as its soundness … but he did not do so” (p. 82).This common appraisal of Frege's work is, I think, quite misleading. Even given Frege's tremendous achievements, the road to an understanding of quantification theory was an arduous one. Obtaining such understanding and formulating those notions which are now common coin in the discussion of logical systems were the tasks of much of the work in logic during the nineteen-twenties.
An effective selection theorem
Authors: Maitra Ashok 
Published: May 2006

A recent result of J.P. Burgess [1] states:Theorem 0. Let F be a multifunction from an analytic subset T of a Polish space to a Polish space X. If F is Borel measurable, Graph(F) is coanalytic in T × X and F(t) is nonmeager in its closure for each t Є T, then F admits a Borel measurable selector.The above result unifies and significantly extends earlier results of H. Sarbadhikari [8], S.M. Srivastava [9] and G. Debs (unpublished). The reader is referred to [1] for details.The aim of this article is to give an effective version of Theorem 0. We do this by proving a basis theorem for Π11 sets which are nonmeager in their closure and satisfy a local version of the measurability condition in Theorem 0. Our basis theorem generalizes a well-known result of P.G. Hinman [4] and S.K. Thomason [10] (see also [5] and [7, 4F.20]). Our methods are similar to those used by A. Louveau to prove that a , σ-compact set is contained in a , σ-compact set (see [7, 4F.18]).The paper is organized as follows. §2 is devoted to preliminaries. In §3, we prove the basis theorem and deduce as a consequence an effective version of Theorem 0. We show in §4 how our methods can be used to give alternative proofs of some known results.Discussions with R. Barua, B.V. Rao and V.V. Srivatsa are gratefully acknowledged. I am indebted to J.P. Burgess for drawing my attention to an error in an earlier draft of this paper.
Recursion theory on orderings. II
Authors: Remmel J. B. 
Published: May 2006

In [6], G. Metakides and the author introduced a general model theoretic setting in which to study the lattice of r.e. substructures of a large class of recursively presented models . Examples included , the natural numbers with equality, 〈 Q, ≤ 〉, the rationals under the usual ordering, and a large class of n-dimensional partial orderings. In this setting, we were able to generalize many of the constructions of classical recursion theory so that the constructions yield the classical results when we specialize to the case of and new results when we specialize to other models. Constructions to generalize Myhill's Theorem on creative sets [8], Friedberg's Theorem on the existence of maximal sets [3], Dekker's Theorem on the degrees of hypersimple sets [2], and Martin's Theorem on the degrees of maximal sets [5] were produced in [6]. In this paper, we give constructions to generalize the Morley-Soare Splitting Theorem [7] and Lachlan's characterization of hyperhypersimple sets [4] in §2, constructions to generalize Lachlan's theorems on the existence of major subsets and r-maximal sets contained in maximal sets [4] in §3, and constructions to generalize Robinson's construction of r-maximal sets that are not contained in any maximal sets [11] and second-order maximal sets [12] in §4.In §1 of this paper, we give the precise definitions of our model theoretic setting and deal with other preliminaries. Also in §1, we define the notions of “uniformly nonrecursive”, “uniformly maximal”, etc. which are the key notions involved in the generalizations of the various theorems that occur in §§2, 3 and 4.
Sequential method in quantum logic
Authors: Nishimura Hirokazu 
Published: May 2006

Since Birkhoff and von Neumann [2] a new area of logical investigation has grown up under the name of quantum logic. However it seems to me that many authors have been inclined to discuss algebraic semantics as such (mainly lattices of a certain kind) almost directly without presenting any axiomatic system, far from developing any proof theory of quantum logic. See, e.g., Gunson [9], Jauch [10], Varadarajan [15], Zeirler [16], etc. In this sense many works presented under the name of quantum logic are algebraic in essence rather than genuinely logical, though it is absurd to doubt the close relationship between algebraic and logical study on quantum mechanics.The main purpose of this paper is to alter this situation by presenting an axiomatization of quantum logic as natural and as elegant as possible, which further proof-theoretical study is to be based on.It is true that several axiomatizations of quantum logic are present now. Several authors have investigated the so-called material implication α → β ( = ¬α∨(α ∧ β)) very closely with due regard to its importance. See, e.g., Finch [5], Piziak [11], etc. Indeed material implication plays a predominant role in any axiomatization of a logic in Hilbert-style. Clark [4] has presented an axiomatization of quantum logic with negation ¬ and material implication → as primitive connectives. In this paper we do not follow this approach. First of all, this approach is greatly complicated because orthomodular lattices are only locally distributive.
Determinateness and the separation property
Authors: Steel John R. 
Published: May 2006

A pointclass is a class of subsets of the Baire space (ωω) closed under inverse images by continuous functions. The dual of a pointclass Γ, denoted is {~A∣ A ∈ Γ}. (Complements are relative to ωω.) If Γ is nonselfdual, i.e. , then let . We say a nonselfdual pointclass Γ has the first separation property, and write Sep(Γ), iff (∀A, B ∈ Γ)(A ⋂ B = ∅ ⇒ (∃C ∈ Δ)(A ⊆ C ∧ B ⋂ = ∅)). The set C is said to separate A and B.Descriptive set theory abounds in nonselfdual pointclasses Γ, and for the more natural examples of such Γ one can always show by assuming enough determinateness that exactly one of Sep(Γ) and Sep() holds. Van Wesep [2] provides a partial explanation of this fact by showing that, assuming the full axiom of determinateness, one of Sep(Γ) and Sep() must fail for all nonselfdual pointclasses Γ. We shall complete the explanation by showing that one of Sep(Γ) and Sep() must hold.The axiom of determinateness has other interesting consequences in the general theory of pointclasses. See e.g. [3].
Locally countable models of Σ1-separation
Authors: Abramson Fred G. 
Published: May 2006

AbstractLet α be any countable admissible ordinal greater than ω. There is a transitive set A such that A is admissible, locally countable, OnA = α, and A satisfies Σ1-separation. In fact, if B is any nonstandard model of KP + ∀x ⊆ ω (the hyperjump of x exists), the ordinal standard part of B is greater than ω, and every standard ordinal in B is countable in B, then HCB ∩ (standard part of B) satisfies Σ-separation.
On the ultrafilter of closed, unbounded sets
Authors: Martin D. A. , Mitchell W. 
Published: May 2006

Solovay proved in 1967 that the axiom of determinateness implies that the filter C generated by closed and unbounded subsets of ω1 is an ultrafilter. It has long been conjectured that a significant part of the theory of the axiom of determinateness should be provable from the hypothesis that C is an ultrafilter, but even the first step of finding inner models with several measurable cardinals has proved elusive. In this paper we show that such models exist. Much of our proof is a modification of Kunen's proof in [3] of the same conclusion from the existence of a measurable cardinal κ such that 2κ > κ+.Since no proof of Solovay's result seems to have been published, we insert a proof here. We want to show that for any set x ⊂ ω1 there is a closed, unbounded set either contained in or disjoint from x. By the lemma of [4] there is a Turing degree d such that either ω1e Є x for all degrees e ≥T d or ω1e ∉ x for all degrees e ≥T d. By a theorem of Sacks [1], [5] every d-admissible is ω1e for some e ≥T d, so it is enough to show that there is a closed, unbounded set of d-admissibles. Let a ⊂ ω have degree d; then is such a set.
The optimality of induction as an axiomatization of arithmetic
Authors: Leivant Daniel 
Published: May 2006

By induction for a formula φ we mean the schema(where the terms in brackets are implicitly substituted for some fixed variable, with the usual restrictions). Let be the schema IAφ for φ in Πn (i.e. ); similarly for . Each instance of is Δn+2, and each instance of is Σn+1 Thus the universal closure of an instance α is Πn+2 in either case. Charles Parsons [72] proved that and are equivalent over Z0, where Z0 is essentially Primitive Recursive Arithmetic augmented by classical First Order Logic [Parsons 70].Theorem. For each n > 0 there is a Πn formula π for whichis not derivable in Z0from(i) true Πn+1sentences; nor even(ii) Πn+1sentences consistent withZ0.
Definability in models of set theory
Authors: Guaspari David 
Published: May 2006

Call a set A of ordinals “definable” over a theory T if T is some brand of set theory and whenever A appears in the standard part of a (not necessarily standard) model of T, A is “definable”. Two kinds of “definability” are considered, for each of which is provided a complete (or almost complete) characterization of the hereditarily countable sets of ordinals “definable” over true finitely axiomatizable set theories: (1) there is a single formula ϕ such that in any model of T containing A, A is the unique solution to ϕ; (2) the defining formula is allowed to vary from model to model. (Note. The restrictions “finitely axiomatizable”, and “true” are largely for the sake of convenience: such theories provably have lots of models.)There are few allusions to what a model theorist would regard as his subject—the methods coming from recursion theory and set theory; but the treatment is intended to be intelligible to nonspecialists. The referee's criticisms have greatly improved the exposition.I would like to thank Leo Harrington for several discussions, both helpful and hapless, and especially for a clever and timely proof which rescued this project from a moribund state. (Further thanks are due to the Movshon family, as a result of whose New Year's Eve party it became clear that the only really magic formulas are Σ1 formulas.)
Degree problems for modular machines
Authors: Cohen Daniel E. 
Published: May 2006

Modular machines were introduced in [1] and [2], where they were used to give simple proofs of various unsolvability results in group theory. Here we discuss the degrees of the halting, word, and confluence problems for modular machines, both for their own sake and in the hope that the results may be useful in group theory (see [4] for an application of a related result to group theory).In the course of the analysis, I found it convenient to compare degrees of these problems for a Turing machine T and for a Turing machine T1 obtained from T by enlarging the alphabet but retaining the same quintuples (or quadruples). The results were surprising. The degree for a problem of T1 depends not just on the corresponding degree for T, but also on the degrees of the corresponding problems when T is restricted to a semi-infinite tape (both semi-infinite to the right and semi-infinite to the left). For the halting and confluence problems, the Turing degrees of the problems for these three machines can be any r.e. degrees. In particular the halting problem of T can be solvable, while that of T1 has any r.e. degree.A machine M (in the general sense) consists of a countable set of configurations (together with a numbering, which we usually take for granted), a recursive subset of configurations called the terminal configurations, and a recursive function, written C ⇒ C′, on the set of configurations. If, for some n ≥ 0, we have C = C0 ⇒ C1 ⇒ … ⇒ Cn = C′, we write C → C′. We say M halts from C if C → C′ for some terminal C′.
The inverse of a regressive object
Authors: Gross W.F. 
Published: May 2006

AbstractIf C1, …, Ck are members of a certain class of suitable categories (which contains those arising from models with dimension), C = C1 × … × Ck, C′ is a suitable category, F: C → C′ is a partial recursive combinatorial functor satisfying a certain property (which, if C = C1, is that F is nonconstant) and ∈ C, then (1) if F is regressive so is as is each i, and (2) if F is Dedekind then each i is Dedekind.
Some results on measure independent Gödel speed-ups
Authors: Solomon Martin K. 
Published: May 2006

AbstractWe study the measure independent character of Gödel speed-up theorems, in particular, we strengthen Arbib's necessary condition for the occurrence of a Gödel speed-up [2, p. 13] to an equivalence result and generalize Di Paola's speed-up theorem [4]. We also characterize undecidable theories as precisely those theories which possess consistent measure independent Gödel speed-ups and show that a theory τ2 is a measure independent Gödel speed-up of a theory τ1 if and only if the set of undecidable sentences of τ1 which are provable in τ2 is not recursively enumerable.