bluuebunny/crossref_metadata_2025_split huggingface dataset:
On theories having a finite number of nonisomorphic countable models
Authors: Tsuboi Akito 
Published: May 2006

In this paper we shall state some interesting facts concerning non-ω-categorical theories which have only finitely many countable models. Although many examples of such theories are known, almost all of them are essentially the same in the following sense: they are obtained from ω-categorical theories, called base theories below, by adding axioms for infinitely many constant symbols. Moreover all known base theories have the (strict) order property in the sense of [6], and so they are unstable. For example, Ehrenfeucht's well-known example which has three countable models has the theory of dense linear order as its base theory.Many papers including [4] and [5] are motivated by the conjecture that every non-ω-categorical theory with a finite number of countable models has the (strict) order property, but this conjecture still remains open. (Of course there are partial positive solutions. For example, in [4], Pillay showed that if such a theory has few links (see [1]), then it has the strict order property.) In this paper we prove the instability of the base theory T0 of such a theory T rather that T itself. Our main theorem is a strengthening of the following which is also our result: if a theory T0 is stable and ω-categorical, then T0 cannot be extended to a theory T which has n countable models (1 < n < ω) by adding axioms for constant symbols.
Inconsistent nonstandard arithmetic
Authors: Mortensen Chris 
Published: May 2006

AbstractThis paper continues the investigation of inconsistent arithmetical structures. In §2 the basic notion of a model with identity is defined, and results needed from elsewhere are cited. In §3 several nonisomorphic inconsistent models with identity which extend the (=, <) theory of the usual classical denumerable nonstandard model of arithmetic are exhibited. In §4 inconsistent nonstandard models of the classical theory of finite rings and fields modulo m, i.e. Zm, are briefly considered. In §5 two models modulo an infinite nonstandard number are considered. In the first, it is shown how to model inconsistently the arithmetic of the rationals with all names included, a strengthening of earlier results. In the second, all inconsistency is confined to the nonstandard integers, and the effects on Fermat's Last Theorem are considered. It is concluded that the prospects for a good inconsistent theory of fields may be limited.
The Complexity of intrinsically r.e. subsets of existentially decidable models
Authors: Chisholm John 
Published: May 2006

Recursive model theory involves the study of relationships between recursion theory and model theory. One direction this often takes is to study the effectiveness of various aspects of model theory. This paper examines such questions by examining some properties of recursive models; that is, models whose basic relations, functions, and constants are all uniformly recursive (and whose universe is the set of natural numbers). Somewhat more precisely:Let be a model whose universe is N, and let (θ())i be an effective enumeration of all quantifier-free formulas of the language of . Then is recursive if {〈, i〉: satisfies (θ())i, in } is a recursive subset of N. (Here and throughout the paper, 〈 〉 denotes an effective pairing function, or an effective coding of sequences, as required.) Similarly, let (ϕ())i be an effective enumeration of all existential formulas of the language of . Then is existentially decidable if {〈, i〉: satisfies (ϕ())i in } is a recursive subset of N.It is clear that if is recursive and is a model isomorphic to , then may lose many of the recursive properties of . In the simplest example, could easily fail to be a recursive model. But even if we require that be a recursive model, it could still fail to retain other recursive properties of . An example of the sort of property which can be studied in this vein is the following notion, introduced by Ash and Nerode in [2].
Extensions séparées et immédiates de corps valués
Authors: Delon Françoise 
Published: May 2006

AbstractBaur a défini la notion d'extension séparée de corps valués et montré que toute extension d'un corps maximal est séparée. Nous prouvons que, si (K, υ) est henselien et de caractéristique résiduelle nulle, alors (K, υ) ⊂ (L, w) est séparée ssi L est linéairement disjoint sur K de toute extension immédiate de K.Separated and immediate extensions of valued fields. The notion of separated extension of valued fields was introduced by Baur. He showed that extensions of maximal fields are separated. We prove that, when (K, υ) is Henselian with residual characteristic 0, then (K, υ) ⊂ (L, w) is separated iff L is linearly disjoint over K from each immediate extension of K.
Uniqueness, definability and interpolation
Authors: Došen Kosta , Schroeder-Heister Peter 
Published: May 2006

This paper is meant to be a comment on Beth's definability theorem. In it we shall make the following points.Implicit definability as mentioned in Beth's theorem for first-order logic is a special case of a more general notion of uniqueness. If α is a nonlogical constant, Tα a set of sentences, α* an additional constant of the same syntactical category as α and Tα, a copy of Tα with α* instead of α, then for implicit definability of α in Tα one has, in the case of predicate constants, to derive α(x1,…,xn) ↔ α*(x1,…,xn) from Tα ∪ Tα*, and similarly for constants of other syntactical categories. For uniqueness one considers sets of schemata Sα and derivability from instances of Sα ∪ Sα* in the language with both α and α*, thus allowing mixing of α and α* not only in logical axioms and rules, but also in nonlogical assumptions. In the first case, but not necessarily in the second one, explicit definability follows. It is crucial for Beth's theorem that mixing of α and α* is allowed only inside logic, not outside. This topic will be treated in §1.Let the structural part of logic be understood roughly in the sense of Gentzen-style proof theory, i.e. as comprising only those rules which do not specifically involve logical constants. If we restrict mixing of α and α* to the structural part of logic which we shall specify precisely, we obtain a different notion of implicit definability for which we can demonstrate a general definability theorem, where a is not confined to the syntactical categories of nonlogical expressions of first-order logic. This definability theorem is a consequence of an equally general interpolation theorem. This topic will be treated in §§2, 3, and 4.
A characterization of jump operators
Authors: Becker Howard 
Published: May 2006

The topic of this paper is jump operators, a subject which originated with some questions of Martin and a partial answer to them obtained by Steel [18]. The topic of jump operators is a part of the general study of the structure of the Turing degrees, but it is concerned with an aspect of that structure which is different from the usual concerns of classical recursion theory. Specifically, it is concerned with studying functions on the degrees, such as the Turing jump operator, the hyperjump operator, and the sharp operator.Roughly speaking, a jump operator is a definable ≤T-increasing function on the Turing degrees. The purpose of this paper is to characterize the jump operators, in terms of concepts from descriptive set theory. Again roughly speaking, the main theorem states that all jump operators (other than the identity function) are obtained from pointclasses by the same process by which the hyperjump operator is obtained from the pointclass Π11; that is, if Γ is the pointclass, then the operator maps the real x to the universal Γ(x) subset of ω. This characterization theorem has some corollaries, one of which answers a question of Steel [18]. In §1 we give a brief introduction to this general topic, followed by a brief (and still somewhat imprecise) description of the results contained in this paper.
Believing the axioms. II
Authors: Maddy Penelope 
Published: May 2006

This is a continuation of Believing the axioms. I, in which nondemonstrative arguments for and against the axioms of ZFC, the continuum hypothesis, small large cardinals and measurable cardinals were discussed. I turn now to determinacy hypotheses and large large cardinals, and conclude with some philosophical remarks.Determinacy is a property of sets of reals. If A is such a set, we imagine an infinite game G(A) between two players I and II. The players take turns choosing natural numbers. In the end, they have generated a real number r (actually a member of the Baire space ωω). If r is in A, I wins; otherwise, II wins. The set A is said to be determined if one player or the other has a winning strategy (that is, a function from finite sequences of natural numbers to natural numbers that guarantees the player a win if he uses it to decide his moves).Determinacy is a “regularity” property (see Martin [1977, p. 807]), a property of well-behaved sets, that implies the more familiar regularity properties like Lebesgue measurability, the Baire property (see Mycielski [1964] and [1966], and Mycielski and Swierczkowski [1964]), and the perfect subset property (Davis [1964]). Infinitary games were first considered by the Polish descriptive set theorists Mazur and Banach in the mid-30s; Gale and Stewart [1953] introduced them into the literature, proving that open sets are determined and that the axiom of choice can be used to construct an undetermined set.
More on definable sets of p-adic numbers
Authors: Scowcroft Philip 
Published: May 2006

To eliminate quantifiers in the first-order theory of the p-adic field Qp, Ax and Kochen use a language containing a symbol for a cross-section map n → pn from the value group Z into Qp [1, pp. 48–49]. The primitive-recursive quantifier eliminations given by Cohen [2] and Weispfenning [10] also apply to a language mentioning the cross-section, but none of these authors seems entirely happy with his results. As Cohen says, “all the operations… introduced for our simple functions seem natural, with the possible exception of the map n → pn” [2, p. 146]. So all three authors show that various consequences of quantifier elimination—completeness, decidability, model-completeness—also hold for a theory of Qp not employing the cross-section [1, p. 453; 2, p. 146; 10, §4]. Macintyre directs a more specific complaint against the cross-section [5, p. 605]. Elementary formulae which use it can define infinite discrete subsets of Qp; yet infinite discrete subsets of R are not definable in the language of ordered fields, and so certain analogies between Qp and R suggested by previous model-theoretic work seem to break down.To avoid this problem, Macintyre gives up the cross-section and eliminates quantifiers in a theory of Qp written just in the usual language of fields supplemented by a predicate V for Qp's valuation ring and by predicates Pn for the sets of nth powers in Qp (for all n ≥ 2).
Universal structures in power ℵ1
Authors: Mekler Alan H. 
Published: May 2006

AbstractIt is consistent with ¬ CH that every universal theory of relational structures with the joint embedding property and amalgamation for -(3)-diagrams has a universal model of cardinality ℵ1. For classes with amalgamation for -(4)-diagrams it is consistent that and there is a universal model of cardinality ℵ2.
Taxonomies of model-theoretically defined topological properties
Authors: Bankston Paul 
Published: May 2006

AbstractAtopological classification schemeconsists of two ingredients: (1) an abstract classof topological spaces; and (2) a “taxonomy”, i.e. a list of first order sentences, together with a way of assigning an abstract class of spaces to each sentence of the list so that logically equivalent sentences are assigned the same class.is then endowed with an equivalence relation, two spaces belonging to the same equivalence class if and only if they lie in the same classes prescribed by the taxonomy. A spaceXinischaracterizedwithin the classification scheme if wheneverY∊andYis equivalent toX, thenYis homeomorphic toX. As prime example, theclosed set taxonomyassigns to each sentence in the first order language of bounded lattices the class of topological spaces whose lattices of closed sets satisfy that sentence. It turns out that every compact two-complex is characterized via this taxonomy in the class of metrizable spaces, but that no infinite discrete space is so characterized. We investigate various natural classification schemes, compare them, and look into the question of which spaces can and cannot be characterized within them.
Definitions of compact
Authors: Howard Paul E. 
Published: May 2006

Several definitions of “compact” for topological spaces have appeared in the literature (see [5]). We will consider the following:Definition. A topological space X is1. Compact(1) if every open cover of X has a finite subcover.2. Compact(2) if every infinite subset E of X has a complete accumulation point (i.e., a point x0 ∈ X such that for every neighborhood U of x0, |E ∩ U| = |E|).3. Compact(3) if there is a subbase S for the topology on X such that every cover of X by members of S has a finite subcover.4. Compact(4) if each nest of closed, nonempty sets has a nonempty intersection.5. Compact(5) if every family of closed sets in X which has the finite intersection property (every finite subfamily has a nonempty intersection) has a nonempty intersection.6. Compact(6) if each net in X has a cluster point.7. Compact(7) if each net in X has a convergent subnet.This work was motivated primarily by consideration of various proofs that the Tychonoff theorem, T (“the product of compact topological spaces is compact”) is equivalent to the Axiom of Choice, AC. Tychonoff's original proof that AC implies T used Definition 2 [13]. Other proofs have used Definitions 3 and 5; see [5]. The proof by Kelley that T implies AC uses Definition 5 [6].
Some improvements to Turner's algorithm for bracket abstraction
Authors: Bunder M. W. 
Published: May 2006

A computer handles λ-terms more easily if these are translated into combinatory terms. This translation process is called bracket abstraction. The simplest abstraction algorithm—the (fab) algorithm of Curry (see Curry and Feys [6])—is lengthy to implement and produces combinatory terms that increase rapidly in length as the number of variables to be abstracted increases.There are several ways in which these problems can be alleviated:(1) A change in order of the clauses in the algorithm so that (f) is performed as a last resort.(2) The use of an extra clause (c), appropriate to βη reduction.(3) The introduction of a finite number of extra combinators.The original 1924 form of bracket abstraction of Schönfinkel [17], which in fact predates λ-calculus, uses all three of these techniques; all are also mentioned in Curry and Feys [6].A technique employed by many computing scientists (Turner [20], Peyton Jones [16], Oberhauser [15]) is to use the (fab) algorithm followed by certain “optimizations” or simplifications involving extra combinators and sometimes special cases of (c).Another is either to allow a fixed infinite set of (super-) combinators (Abdali [1], Kennaway and Sleep [10], Krishnamurthy [12], Tonino [19]) or to allow new combinators to be defined one by one during the abstraction process (Hughes [7] and [8]).A final method encodes the variables to be abstracted as an n-tuple—this requires only a finite number of combinators (Curien [5], Statman [18]).
Proof theory in the USSR 1925–1969
Authors: Mints Grigori 
Published: May 2006

AbstractWe present a survey of proof theory in the USSR beginning with the paper by Kolmogorov [1925] and ending (mostly) in 1969; the last two sections deal with work done by A. A. Markov and N. A. Shanin in the early seventies, providing a kind of effective interpretation of negative arithmetic formulas. The material is arranged in chronological order and subdivided according to topics of investigation. The exposition is more detailed when the work is little known in the West or the original presentation can be improved using notions or results which appeared later. This includes such topics as Novikov's cut-elimination method (regular formulas) and Maslov's inverse method for the predicate logic.
Π11 Borel sets
Authors: Kechris Alexander S. , Marker David , Sami Ramez L. 
Published: May 2006

The results in this paper were motivated by the following question of Sacks. Suppose T is a recursive theory with countably many countable models. What can you say about the least ordinal α such that all models of T have Scott rank below α? If Martin's conjecture is true for T then α ≤ ω · 2.Our goal was to look at this problem in a more abstract setting. Let E be a equivalence relation on ωω with countably many classes each of which is Borel. What can you say about the least α such that each equivalence class is ? This problem is closely related to the following question. Suppose X ⊆ ωω is and Borel. What can you say about the least α such that X is ?In §1 we answer these questions in ZFC. In §2 we give more informative answers under the added assumptions V = L or -determinacy. The final section contains related results on the separation of sets by Borel sets.Our notation is standard. The reader may consult Moschovakis [5] for undefined terms.Some of these results were proved first by Sami and rediscovered by Kechris and Marker.
Nonstandard set theory
Authors: Fletcher Peter 
Published: May 2006

AbstractNonstandard set theory is an attempt to generalise nonstandard analysis to cover the whole of classical mathematics. Existing versions (Nelson, Hrbáček, Kawai) are unsatisfactory in that the unlimited idealisation principle conflicts with the wish to have a full theory of external sets.I re-analyse the underlying requirements of nonstandard set theory and give a new formal system, stratified nonstandard set theory, which seems to meet them better than the other versions.
The undecidability of the DA-unification problem
Authors: Siekmann J. , Szabó P. 
Published: May 2006

AbstractWe show that the DA-uniflcation problem is undecidable. That is, given two binary function symbols ⊕ and ⊗, variables and constants, it is undecidable if two terms built from these symbols can be unified provided the following DA-axioms hold:Two terms are DA-unifiable (i.e. an equation is solvable in DA) if there exist terms to be substituted for their variables such that the resulting terms are equal in the equational theory DA.This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which an undecidability result has been obtained.
Definability via enumerations
Authors: Soskov Ivan N. 
Published: May 2006

The notion of ∀-recursiviness, introduced by Lacombe [1], is intended to describe the effectively definable functions and predicates in abstract structures with equality and denumerable domains. The fact that on every such structure ∀-recursiviness and search computability are equivalent is proved by Moschovakis in [2].The definition of search computability [3] does not require the presence of the equality among the basic predicates of the structure. There exist abstract structures where the equality is not search-computable and even not semicomputable. On the other hand, in some structures the equality is not an “effective” predicate. Consider, for example, a structure whose domain consists of all partial recursive functions.A notion of relative computability in abstract structures with denumerable domains, which we shall call here ∀-admissibility, was introduced by D. Skordev in 1977. The notion of ∀-admissibility is a generalization of Lacombe's ∀-recursiviness and does not require the presence of the equality among the basic predicates. In 1977 Skordev conjectured that, in every partial structure with denumerable domain, ∀-admissibility and search computability are equivalent.Since 1977 some attempts have been made to establish Skordev's conjecture. It is proved in [4] for structures with total basic functions and without basic predicates, and in [5] for structures with finite domains. The proofs in [4] and [5] make use of the priority method and are very complicated.
On models of the elementary theory of (Z, +, 1)
Authors: Nadel Mark , Stavi Jonathan 
Published: May 2006

Let T1 be the complete first-order theory of the additive group of the integers with 1 as distinguished element (in symbols, T1 = Th(Z, +, 1)). In this paper we prove that all models of T1 are ℵ0-homogeneous (§2), classify them (and lists of elements in them) up to isomorphism or L∞κ-equivalence (§§3 and 4) and show that they may be as complex as arbitrary sets of real numbers from the point of view of admissible set theory (§5). The results of §§2 and 5 together show that while the Scott heights of all models of T1 are ≤ ω (by ℵ0-homogeneity) their HYP-heights form an unbounded subset of the cardinal .In addition to providing this unusual example of the relation between Scott heights and HYP-heights, the theory T1 has served (using the homogeneity results of §2) as an example for certain combinations of properties that people had looked for in stability theory (see end of §4). In §6 it is shown that not all models of T = Th(Z, +) are ℵ0-homogeneous, so that the availability of the constant for 1 is essential for the result of §2.The two main results of this paper (2.2 and essentially Theorem 5.3) were obtained in the summer of 1979. Later we learnt from Victor Harnik and Julia Knight that T1 is of some interest for stability theory, and were encouraged to write up our proofs.During 1982/3 we improved the proofs and added some results.
An introduction to γ-recursion theory (or what to do in KP – Foundation)
Authors: Lubarsky Robert S. 
Published: May 2006

The program of reverse mathematics has usually been to find which parts of set theory, often used as a base for other mathematics, are actually necessary for some particular mathematical theory. In recent years, Slaman, Groszek, et al, have given the approach a new twist. The priority arguments of recursion theory do not naturally or necessarily lead to a foundation involving any set theory; rather, Peano Arithmetic (PA) in the language of arithmetic suffices. From this point, the appropriate subsystems to consider are fragments of PA with limited induction. A theorem in this area would then have the form that certain induction axioms are independent of, necessary for, or even equivalent to a theorem about the Turing degrees. (See, for examples, [C], [GS], [M], [MS], and [SW].)As go the integers so go the ordinals. One motivation of α-recursion theory (recursion on admissible ordinals) is to generalize classical recursion theory. Since induction in arithmetic is meant to capture the well-foundedness of ω, the corresponding axiom in set theory is foundation. So reverse mathematics, even in the context of a set theory (admissibility), can be changed by the influence of reverse recursion theory. We ask not which set existence axioms, but which foundation axioms, are necessary for the theorems of α-recursion theory.When working in the theory KP – Foundation Schema (hereinafter called KP−), one should really not call it α-recursion theory, which refers implicitly to the full set of axioms KP. Just as the name β-recursion theory refers to what would be α-recursion theory only it includes also inadmissible ordinals, we call the subject of study here γ-recursion theory. This answers a question by Sacks and S. Friedman, “What is γ-recursion theory?”