bluuebunny/crossref_metadata_2025_split huggingface dataset:
R. e. presented linear orders
Authors: Roy Dev Kumar 
Published: May 2006

This paper looks at linear orders in the following way. A preordering is given, which is linear and recursively enumerable. By performing the natural identification, one obtains a linear order for which equality is not necessarily recursive. A format similar to Metakides and Nerode's [3] is used to study these linear orders. In effective studies of linear orders thus far, the law of antisymmetry (x ≦ y ∧ y ≦ x ⇒ y) has been assumed, so that if the order relation x ≦ y is r.e. then x < y is also r.e. Here the assumption is dropped, so that x < y may not be r.e. and the equality relation may not be recursive; the possibility that equality is not recursive leads to new twists which sometimes lead to negative results.Reported here are some interesting preliminary results with simple proofs, which are obtained if one looks at these objects with a view to doing recursion theory in the style of Metakides and Nerode. (This style, set in [3], is seen in many subsequent papers by Metakides and Nerode, Kalantari, Remmel, Retzlaff, Shore, and others, e.g. [1], [4], [6], [7], [8], [11]. In a sequel, further investigations will be reported which look at r.e. presented linear orders in this fashion and in the context of Rosenstein's comprehensive work [10].Obviously, only countable linear orders are under consideration here. For recursion-theoretic notation and terminology see Rogers [9].
Some contributions to definability theory for languages with generalized quantifiers
Authors: Baldwin John T. , Miller Douglas E. 
Published: May 2006

One of the first results in model theory [12] asserts that a first-order sentence is preserved in extensions if and only if it is equivalent to an existential sentence.In the first section of this paper, we analyze a natural program for extending this result to a class of languages extending first-order logic, notably including L(Q) and L(aa), respectively the languages with the quantifiers “there exist un-countably many” and “for almost all countable subsets”.In the second section we answer a question of Bruce [3] by showing that this program cannot resolve the question for L(Q). We also consider whether the natural class of “generalized Σ-sentences” in L(Q) characterizes the class of sentences preserved in extensions, refuting the relativized version but leaving the unrestricted question open.In the third section we show that the analogous class of L(aa)-sentences preserved in extensions does not include (up to elementary equivalence) all such sentences. This particular candidate class was nominated, rather tentatively, by Bruce [3].In the fourth section we show that under rather general conditions, if L is a countably compact extension of first-order logic and T is an ℵ1-categorical first-order theory, then L is trivial relative to T.
Calculating self-referential statements: Guaspari sentences of the first kind
Authors: Smoryński C. 
Published: May 2006

Beginning in 1960, and continuing for about a decade and a half, Shepherdson's self-referential formulae dominated the applications of diagonalization in metamathematics. In 1976, it was doubly toppled from its position of supremacy by two demonstrably more powerful such sentences introduced by D. Guaspari. The goal of the present note is to understand and explain the first (and, for the time being, more important) of Guaspari's self-referential sentences, which we dub “Guaspari sentences of the first kind”, or, less poetically, “Guaspari fixed points”.Both Shepherdson's and Guaspari's fixed points are generalizations of the Rosser sentence. But, where Shepherdson merely tacks on side-formulae, Guaspari takes a more revolutionary step: He views the basic components, PrT(⌈¬φ⌉) and PrT(⌈φ⌉), of the Rosser sentence as attempts to refute something and replaces them by refutations of something else. Ignoring their Shepherdsonesque side-formulae (tacked on for the sake of more esoteric applications), our analysis of Guaspari fixed points can be viewed as merely the isolation of those properties whose refutations can be used in this context.In §1 we offer the outcome of this analysis—i.e. a delineation of properties whose refutations can so be used. Some simple examples are cited and the Guaspari fixed points are defined. The main theorem—a master Fixed Point Calculation—is proven in §2.
Characterizing the continuous functionals
Authors: Normann Dag 
Published: May 2006

One of the objectives of mathematics is to construct suitable models for practical or theoretical phenomena and to explore the mathematical richness of such models. This enables other scientists to obtain a better understanding of such phenomena. As an example we will mention the real line and related structures. The line can be used profitably in the study of discrete phenomena like population growth, chemical reactions, etc.Today's version of the real line is a topological completion of the rational numbers. This is so because then mathematicians have been able to work out a powerful analysis of the line. By using the real line to construct models for finitary phenomena we are more able to study those phenomena than we would have been sticking only to true-to-nature but finite structures.So we may say that the line is a mathematical model for certain finite structures. This motivates us to seek natural models for other types of finite structures, and it is natural to look for models that in some sense are complete.In this paper our starting point will be finite systems of finite operators. For the sake of simplicity we assume that they all are operators of one variable and that all the values are natural numbers. There is a natural extension of the systems such that they accept several variables and give finite operators as values, but the notational complexity will then obscure the idea of the construction.
Indecomposable ultrafilters over small large cardinals
Authors: Sheard Michael 
Published: May 2006

Indecomposability of ultrafilters was introduced by Keisler as a natural weakening of the concept of measurability. The property was first studied in depth by Chudnovsky and Chudnovsky, Prikry, and Silver (see [4] and [5]). One intriguing result of this early work was the following theorem: if κ is an inaccessible cardinal and there is an indecomposable ultrafilter over κ, then κ is in fact ω-Mahlo. Silver asked whether this result could be strengthened to say that an inaccessible cardinal carrying an indecomposable ultrafilter must be measurable. We prove in this paper that this is not the case; we construct a model where κ is inaccessible and carries an indecomposable ultrafilter but κ is not even weakly compact.The results in this paper form part of the research for my doctoral dissertation at the University of California, Berkeley. I would like to thank my thesis advisor, Robert Solovay, for his patient guidance during this endeavor.
A Baire-type theorem for cardinals
Authors: Wolfsdorf Kurt 
Published: May 2006

AbstractWe shall prove the following theorem: If κ is an infinite cardinal and Γ: P(κ) → cf κ a partition of the power-set of κ then we can find a homogeneous ⊿-system of size κ such that the kernel of the ⊿-system is in the same partition class as all the members of the ⊿-system.
Downward transfer of satisfiability for sentences of L1,1
Authors: Malitz Jerome 
Published: May 2006

AbstractThe quantifier Qm,n binds m + n variables. In the κ-interpretation M ⊨ means that there is a κ-powered proper subset X of ∣M∣ such that whenever ā ∈ mX and then M ⊨ ϕā, . If σ ∈ Lm, n has a model in the κ-interpretation does it have a model in the λ-interpretation? For σ ∈ L1, 1, κ regular and uncountable, and λ = ω1 the answer is yes.
Reflection principles and iterated consistency assertions
Authors: Boolos George 
Published: May 2006

This paper compares the strength of two sorts of sentences of PA (classical first-order arithmetic with induction): reflection principles and sentences that may be called iterated consistency assertions.Let Bew(x) be the standard provability predicate for PA, and for any sentence S of PA, let ⌈S⌉ be the numeral for the Gödel number of S. The reflection principle for S is the sentence Bew(⌈S⌉) → S, and a reflection principle is simply the reflection principle for some sentence. Nothing false (in the standard model for PA) is provable in PA, and therefore every reflection principle is true. Löb's theorem asserts that S is provable (in PA) if the reflection principle for S is provable.We shall suppose that the 0-ary propositional connectives ⊤ and ⊥ are taken as primitives in the formulation of PA. We define the iterated consistency assertions Conm by: Con0 = ⊤; Conm−1 = − Bew(⌈ − Conm⌉). Con1 may be taken to be the sentence of PA that expresses the consistency of PA; Conn−1, the sentence that expresses the consistency of PA ⋃ {Conn}.Our starting point is the observation that Con1 is equivalent (in PA) to the reflection principle for ⊥. (The second incompleteness theorem thus follows in a well-known way from Löb's theorem: if PA is consistent, then ⊥ is not provable, the reflection principle for ⊥ is not provable, and the consistency of PA is not provable either.)
HC of an admissible set
Authors: Friedman Sy D. 
Published: May 2006

AbstractIf A is an admissible set, let HC(A) = {x∣x ∈ A and x is hereditarily countable in A}. Then HC(A) is admissible. Corollaries are drawn characterizing the “real parts” of admissible sets and the analytical consequences of admissible set theory.
Preservation of saturation and stability in a variety of nilpotent groups
Authors: Rogers Pat 
Published: May 2006

This paper is a contribution to the growing literature on the model theory of nilpotent groups. (See Baumslag and Levin [2]; Eršov [5]; Hodges [9], [10]; Mal′cev [14]; Olin [16] and Saracino [19], [20].) In it we investigate the conditions under which the free product in the variety of all nilpotent of class 2 (nil-2) groups preserves saturation and stability.It is well known that the direct product preserves both saturation (see Waszkiewicz and Wȩglorz [23]) and stability (see Wierzejewski [24]; Macintyre [13]; Eklof and Fisher [4]). On the other hand it is easy to show that the full free product of groups preserves neither property; indeed, in the case of saturation this failure is extremely bad since no free product of nontrivial groups is even 2-saturated. Our results show that the nil-2 free product falls between these two extremes.Our proofs are mainly model-theoretic with a smattering of elementary algebra and rely heavily upon the unique normal form for the elements of a nil-2 free product given by MacHenry in [12]. (This normal form and some of its consequences are discussed in §1.) We assume familiarity with the basic ideas of saturation (see Chapter 5 of [3]) and Shelah's treatment of stability in [22].We prove two main theorems in §3 each giving a necessary and sufficient condition in separate situations for the preservation of saturation. In the first (Theorem 3.1) we allow one finite factor, while in the second (Theorem 3.10) we deal solely with torsion groups. Our motivation for the proof of sufficiency was the paper of Waszkiewicz and Wȩglorz [23] and the principal tool is a “Feferman-Vaught” Theorem for the nil-2 free product which we prove in §2. We also show that if both factors in a nil-2 free product are nontorsion and one factor has a nil-2 basis, then the group is not even 3-saturated. We leave open the case where both factors are infinite but only one is torsion.
An algebraic result about soft model theoretical equivalence relations with an application to H. Friedman's fourth problem
Authors: Mundici Daniele 
Published: May 2006

AbstractWe prove the following algebraic characterization of elementary equivalence: ≡ restricted to countable structures of finite type is minimal among the equivalence relations, other than isomorphism, which are preserved under reduct and renaming and which have the Robinson property; the latter is a faithful adaptation for equivalence relations of the familiar model theoretical notion. We apply this result to Friedman's fourth problem by proving that if is an (ω1, ω)-compact logic satisfying both the Robinson consistency theorem on countable structures of finite type and the Löwenheim-Skolem theorem for some λ < ωω for theories having ω1 many sentences, then ≡L = ≡ on such structures.
Explicit Henkin sentences
Authors: Solovay Robert M. 
Published: May 2006

AbstractHofstadter has introduced the notion of an explicit Henkin sentence. Roughly speaking, an explicit Henkin sentence not only asserts its own provability, as ordinary Henkin sentences do, but explicitly provides a detailed description of a proof. We provide, in this paper, a precise formalization of Hofstadter's notion and then show that true explicit Henkin sentences exist.
Classifying the computational complexity of problems
Authors: Stockmeyer Larry 
Published: May 2006

One of the more significant achievements of twentieth century mathematics, especially from the viewpoints of logic and computer science, was the work of Church, Gödel and Turing in the 1930's which provided a precise and robust definition of what it means for a problem to be computationally solvable, or decidable, and which showed that there are undecidable problems which arise naturally in logic and computer science. Indeed, when one is faced with a new computational problem, one of the first questions to be answered is whether the problem is decidable or undecidable. A problem is usually defined to be decidable if and only if it can be solved by some Turing machine, and the class of decidable problems defined in this way remains unchanged if “Turing machine” is replaced by any of a variety of other formal models of computation. The division of all problems into two classes, decidable or undecidable, is very coarse, and refinements have been made on both sides of the boundary. On the undecidable side, work in recursive function theory, using tools such as effective reducibility, has exposed much additional structure such as degrees of unsolvability. The main purpose of this survey article is to describe a branch of computational complexity theory which attempts to expose more structure within the decidable side of the boundary.Motivated in part by practical considerations, the additional structure is obtained by placing upper bounds on the amounts of computational resources which are needed to solve the problem. Two common measures of the computational resources used by an algorithm are time, the number of steps executed by the algorithm, and space, the amount of memory used by the algorithm.
The completeness of a predicate-functor logic
Authors: Bacon John 
Published: May 2006

Predicate-functor logic, as founded by W. V. Quine ([1960], [1971], [1976], [1981]), is first-order predicate logic without individual variables. Instead, adverbs or predicate functors make explicit the permutations and replications of argument-places familiarly indicated by shifting variables about. For the history of this approach, see Quine [1971, 309ff.]. With the evaporation of variables, individual constants naturally assimilate to singleton predicates or adverbs, leaving no logical subjects whatever of type 0. The orphaned “predicates” may then be taken simply as terms in the sense of traditional logic: class and relational terms on model-theoretic semantics, schematic terms on Quine's denotational or truth-of semantics. Predicate-functor logic thus stands forth as the pre-eminent first-order term logic, as distinct from propositional-quantificational logic. By the same token, it might with some justification qualify as “first-order combinatory logic”, with allowance for some categorization of the sort eschewed in general combinatory logic, the ultimate term logic.Over the years, Quine has put forward various choices of primitive predicate functors for first-order logic with or without the full theory of identity. Moreover, he has provided translations of quantificational into predicate-functor notation and vice versa ([1971, 312f.], [1981, 651]). Such a translation does not of itself establish semantic completeness, however, in the absence of a proof that it preserves deducibility.An axiomatization of predicate-functor logic was first published by Kuhn [1980], using primitives rather like Quine's. As Kuhn noted, “The axioms and rules have been chosen to facilitate the completeness proof” [1980, 153]. While this expedient simplifies the proof, however, it limits the depth of analysis afforded by the axioms and rules. Mindful of this problem, Kuhn ([1981] and [1983]) boils his axiom system down considerably, correcting certain minor slips in the original paper.
Some remarks on definable equivalence relations in O-minimal structures
Authors: Pillay Anand 
Published: May 2006

Let M be an O-minimal structure. We use our understanding, acquired in [KPS], of the structure of definable sets of n-tuples in M, to study definable (in M) equivalence relations on Mn. In particular, we show that if E is an A-definable equivalence relation on Mn (A ⊂ M) then E has only finitely many classes with nonempty interior in Mn, each such class being moreover also A-definable. As a consequence, we are able to give some conditions under which an O-minimal theory T eliminates imaginaries (in the sense of Poizat [P]).If L is a first order language and M an L-structure, then by a definable set in M, we mean something of the form X ⊂ Mn, n ≥ 1, where X = {(a1…,an) ∈ Mn: M ⊨ϕ(ā)} for some formula ∈ L(M). (Here L(M) means L together with names for the elements of M.) If the parameters from come from a subset A of M, we say that X is A-definable.M is said to be O-minimal if M = (M, <,…), where < is a dense linear order with no first or last element, and every definable set X ⊂ M is a finite union of points, and intervals (a, b) (where a, b ∈ M ∪ {± ∞}). (This notion is as in [PS] except here we demand the underlying order be dense.) The complete theory T is said to be O-minimal if every model of T is O-minimal. (Note that in [KPS] it is proved that if M is O-minimal, then T = Th(M) is O-minimal.) In the remainder of this section and in §2, M will denote a fixed but arbitrary O-minimal structure. A,B,C,… will denote subsets of M.
Correction to a definition of negation
Authors: Fitch Frederic B. 
Published: May 2006

In [3] a definition of negation was presented for the system K′ of extended basic logic [1], but it has since been shown by Peter Päppinghaus (personal communication) that this definition fails to give rise to the law of double negation as I claimed it did. The purpose of this note is to revise this defective definition in such a way that it clearly does give rise to the law of double negation, as well as to the other negation rules of K′.Although Päppinghaus's original letter to me was dated September 19, 1972, the matter has remained unresolved all this time. Only recently have I seen that there is a simple way to correct the definition. I am of course very grateful to Päppinghaus for pointing out my error in claiming to be able to derive the rule of double negation from the original form of the definition.The corrected definition will, as before, use fixed-point operators to give the effect of the required kind of transfinite induction, but this time a double transfinite induction will be used, somewhat like the double transfinite induction used in [5] to define simultaneously the theorems and antitheorems of system CΓ.
The universal splitting property. II
Authors: Lerman M. , Remmel J. B. 
Published: May 2006

We say that a pair of r.e. sets B and C split an r.e. set A if B ∩ C = ∅ and B ∪ C = A. Friedberg [F] was the first to study the degrees of splittings of r.e. sets. He showed that every nonrecursive r.e. set A has a splitting into nonrecursive sets. Generalizations and strengthenings of Friedberg's result were obtained by Sacks [Sa2], Owings [O], and Morley and Soare [MS].The question which motivated both [LR] and this paper is the determination of possible degrees of splittings of A. It is easy to see that if B and C split A, then both B and C are Turing reducible to A (written B ≤TA and C ≤TA). The Sacks splitting theorem [Sa2] is a result in this direction, as are results by Lachlan and Ladner on mitotic and nonmitotic sets. Call an r.e. set A mitotic if there is a splitting B and C of A such that both B and C have the same Turing degree as A; A is nonmitotic otherwise. Lachlan [Lac] showed that nonmitotic sets exist, and Ladner [Lad1], [Lad2] carried out an exhaustive study of the degrees of mitotic sets.The Sacks splitting theorem [Sa2] shows that if A is r.e. and nonrecursive, then there are r.e. sets B and C splitting A such that B <TA and C <TA. Since B is r.e. and nonrecursive, we can now split B and continue in this manner to produce infinitely many r.e. degrees below the degree of A which are degrees of sets forming part of a splitting of A. We say that an r.e. set A has the universal splitting property (USP) if for any r.e. set D ≤T A, there is a splitting B and C of A such that B and D are Turing equivalent (written B ≡TD).
Filter Logics on ω
Authors: Kaufmann Matt 
Published: May 2006

AbstractLogics LF(M) are considered, in which M (“most”) is a new first-order quantifier whose interpretation depends on a given filter F of subsets of ω. It is proved that countable compactness and axiomatizability are each equivalent to the assertion that F is not of the form {(⋂F) ∪ X: ∣ω − X∣ < ω} with ∣ω − ⋂F∣ = ω. Moreover the set of validities of LF (M) and even of depends only on a few basic properties of F. Similar characterizations are given of the class of filters F for which LF (M) has the interpolation or Robinson properties. An omitting types theorem is also proved. These results sharpen the corresponding known theorems on weak models (, where the collection q is allowed to vary. In addition they provide extensions of first-order logic which possess some nice properties, thus escaping from contradicting Lindström's Theorem [1969] only because satisfaction is not isomorphism-invariant (as it is tied to the filter F). However, Lindström's argument is applied to characterize the invariant sentences as just those of first-order logic.
On the period of sequences (An(p)) in intuitionistic propositional calculus
Authors: Ruitenburg Wim 
Published: May 2006

In classical prepositional calculus for each proposition A(p) the following holds: ⊢A(p) ↔ A3(p). In this paper we consider what remains of this in the intuitionistic case. It turns out that for each proposition A(p) the following holds: there is an n ∈ N such thatAs a byproduct of the proof we give some theorems which may be useful elsewhere in propositional calculus.