bluuebunny/crossref_metadata_2025_split huggingface dataset:
Heterogeneous Reasoning and Its Logic
Authors: shin Sun-Joo 
Published: March 2005

Let me start by saying that I had the privilege of witnessing the birth of Jon Barwise's new research on heterogeneous logic and its subsequent developments. I entered the Stanford philosophy graduate program in the Fall of 1987, became Barwise and Etchemendy's first research assistant on the project of diagrammatic/heterogeneous reasoning during summer of 1989, and under their guidance completed my thesis, “Valid reasoning and visual representation,” in August, 1991. With this experience I would like to focus on the more personal and informal aspects of Jon's research on heterogeneous logic which may not be conveyed by his articles. (Accordingly, I have written this paper without footnotes or other references except to Jon's work.) The present article can only hint at the depth and the influence of Jon's work in this area.In the first section, I single out an important feature of the project on heterogeneous logic Jon founded together with John Etchemendy about 15 years ago. I title it “resolving conflicts” since the research, I strongly believe, grew out of Jon's personal attitude toward how to resolve a tension between opposite extremes.The second section focuses on how teaching logic itself was shaped as part of Barwise and Etchemendy's research agenda. It is worthwhile noting that their textbookLanguage, Proof, and Logicconstitutes part of their research and, hence, the success of the book vindicates the goal of the overall project.
Predicative Fragments of Frege Arithmetic
Authors: Linnebo Øystein 
Published: March 2005

AbstractFrege Arithmetic (FA) is the second-order theory whose sole non-logical axiom is Hume's Principle, which says that the number ofFs is identical to the number ofGs if and only if theFs and theGs can be one-to-one correlated. According to Frege's Theorem, FA and some natural definitions imply all of second-order Peano Arithmetic. This paper distinguishes two dimensions of impredicativity involved in FA—one having to do with Hume's Principle, the other, with the underlying second-order logic—and investigates how much of Frege's Theorem goes through in various partially predicative fragments of FA. Theorem 1 shows that almost everything goes through, the most important exception being the axiom that every natural number has a successor. Theorem 2 shows that the Successor Axiom cannot be proved in the theories that are predicative in either dimension.
Asymptotic Cones and Ultrapowers of Lie Groups
Authors: Kramer Linus , Tent Katrin 
Published: March 2005

§1. Introduction. Asymptotic cones of metric spaces were first invented by Gromov. They are metric spaces which capture the ‘large-scale structure’ of the underlying metric space. Later, van den Dries and Wilkie gave a more general construction of asymptotic cones using ultrapowers. Certain facts about asymptotic cones, like the completeness of the metric space, now follow rather easily from saturation properties of ultrapowers, and in this survey, we want to present two applications of the van den Dries-Wilkie approach. Using ultrapowers we obtain an explicit description of the asymptotic cone of a semisimple Lie group. From this description, using semi-algebraic groups and non-standard methods, we can give a short proof of the Margulis Conjecture. In a second application, we use set theory to answer a question of Gromov.§2. Definitions. The intuitive idea behind Gromov's concept of an asymptotic cone was to look at a given metric space from an ‘infinite distance’, so that large-scale patterns should become visible. In his original definition this was done by gradually scaling down the metric by factors 1/nfornϵ ℕ. In the approach by van den Dries and Wilkie, this idea was captured by ultrapowers. Their construction is more general in the sense that the asymptotic cone exists for any metric space, whereas in Gromov's original definition, the asymptotic cone existed only for a rather restricted class of spaces.
Erdős Graphs Resolve Fine's Canonicity Problem
Authors: Goldblatt Robert , Hodkinson Ian , Venema Yde 
Published: March 2005

AbstractWe show that there exist 2ℵ0equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of Thomason). The constructions use the result of Erdos that there are finite graphs with arbitrarily large chromatic number and girth.
Forcing in Proof Theory
Authors: Avigad Jeremy 
Published: March 2005

AbstractPaul Cohen's method of forcing, together with Saul Kripke's related semantics for modal and intuitionistic logic, has had profound effects on a number of branches of mathematical logic, from set theory and model theory to constructive and categorical logic. Here, I argue that forcing also has a place in traditional Hilbert-style proof theory, where the goal is to formalize portions of ordinary mathematics in restricted axiomatic theories, and study those theories in constructive or syntactic terms. I will discuss the aspects of forcing that are useful in this respect, and some sample applications. The latter include ways of obtaining conservation results for classical and intuitionistic theories, interpreting classical theories in constructive ones, and constructivizing model-theoretic arguments.
Notes on Quasiminimality and Excellence
Authors: Baldwin John T. 
Published: March 2005

AbstractThis paper ties together much of the model theory of the last 50 years. Shelah's attempts to generalize the Morley theorem beyond first order logic led to the notion of excellence, which is a key to the structure theory of uncountable models. The notion of Abstract Elementary Class arose naturally in attempting to prove the categoricity theorem for Lω1,ω(Q). More recently, Zilber has attempted to identify canonical mathematical structures as those whose theory (in an appropriate logic) is categorical in all powers. Zilber's trichotomy conjecture for first order categorical structures was refuted by Hrushovski, by the introducion of a special kind of Abstract Elementary Class. Zilber uses a powerful and essentailly infinitary variant on these techniques to investigate complex exponentiation. This not only demonstrates the relevance of Shelah's model theoretic investigations to mainstream mathematics but produces new results and conjectures in algebraic geometry.
Is the Euclidean Algorithm Optimal Among its Peers?
Authors: Van Den Dries Lou , Moschovakis Yiannis N. 
Published: March 2005

The Euclidean algorithm on the natural numbers ℕ = {0,1,…} can be specified succinctly by the recursive programwhere rem(a, b) is the remainder in the division of a by b, the unique natural number r such that for some natural number q,It is an algorithm from (relative to) the remainder function rem, meaning that in computing its time complexity function cε (a, b), we assume that the values rem(x, y) are provided on demand by some “oracle” in one “time unit”. It is easy to prove thatMuch more is known about cε(a, b), but this simple-to-prove upper bound suggests the proper formulation of the Euclidean's (worst case) optimality among its peers—algorithms from rem:Conjecture. If an algorithm α computes gcd (x,y) from rem with time complexity cα (x,y), then there is a rational number r > 0 such that for infinitely many pairs a > b > 1, cα (a,b) > r log2a.
Computability Theory and Differential Geometry
Authors: Soare Robert I. 
Published: March 2005

Abstract. LetMbe a smooth, compact manifold of dimensionn≥ 5 and sectional curvature ∣K∣ ≤ 1. Let Met(M) = Riem(M)/Diff(M) be the space of Riemannian metrics onMmodulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met(M) such as the diameter. They showed that for every Turing machineTe,eϵ ω, there is a sequence (uniformly effective ine) of homologyn-sphereswhich are also hypersurfaces, such thatis diffeomorphic to the standardn-sphereSn(denoted)iffTehalts on inputk, and in this case the connected sum, so, andis associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time ae σe(k)ofTeon inputsy<k.At their request Soare constructed a particular infinite sequence {Ai}ϵωof c.e. sets so that for allithe settling time of the associated Turing machine forAidominates that forAi+1, even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a “fractal” like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as “the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization.” From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structuralcomplexityof the geometry and topology, not merelyundecidabilityresults as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they usenontrivialinformation about c.e. sets, the Soare sequence {Ai}iϵωabove, not merely Gödel's c.e. noncomputable set K of the 1930's; and (3)withoutusing computability theory there is no known proof that local minima exist even for simple manifolds like the torusT5(see §9.5).
Mass Problems and Randomness
Authors: Simpson Stephen G. 
Published: March 2005

AbstractA mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We focus on the countable distributive lattices ω and s of weak and strong degrees of mass problems given by nonempty subsets of 2ω. Using an abstract Gödel/Rosser incompleteness property, we characterize the subsets of 2ω whose associated mass problems are of top degree in ω and s, respectively Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within ω. Namely, we characterize r as the unique largest weak degree of a subset of 2ω of positive measure. Within ω we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect subsets of 2ω. In addition, we present other natural examples of intermediate degrees in ω. We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory.
Compactness and Independence in Non First Order Frameworks
Authors: Ben-Yaacov Itay 
Published: March 2005

AbstractThis communication deals with positive model theory, a non first order model theoretic setting which preserves compactness at the cost of giving up negation. Positive model theory deals transparently with hyperimaginaries, and accommodates various analytic structures which defy direct first order treatment. We describe the development of simplicity theory in this setting, and an application to the lovely pairs of models of simple theories without the weak non finite cover property.
Proper Forcing, Cardinal Arithmetic, and Uncountable Linear Orders
Authors: Moore Justin Tatch 
Published: March 2005

AbstractIn this paper I will communicate some new consequences of the Proper Forcing Axiom. First, the Bounded Proper Forcing Axiom implies that there is a well ordering of ℝ which is Σ1-definable in (H(ω2), ϵ). Second, the Proper Forcing Axiom implies that the class of uncountable linear orders has a five element basis. The elements areX, ω1,,C,C *whereXis any suborder of the reals of size ω1andCis any Countryman line. Third, the Proper Forcing Axiom implies the Singular Cardinals Hypothesis atkunless stationary subsets ofreflect. The techniques are expected to be applicable to other open problems concerning the theory ofH(ω2).
ZF + “Every set is the same size as a wellfounded set”
Authors: Forster Thomas 
Published: March 2005

AbstractLet ZFB be ZF + “every set is the same size as a wellfounded set”. Then the following are true.Every sentence true in every (Rieger-Bernays) permutation model of a model of ZF is a theorem of ZFB. (i.e., ZFB is the theory of Rieger-Bernays permutation models of models of ZF) ZF and ZFAFA are both extensions of ZFB conservative for stratified formulæ. The class of models of ZFB is closed under creation of Rieger-Bernays permutation models.
On the induction schema for decidable predicates
Authors: Beklemishev Lev D. 
Published: March 2005

AbstractWe study the fragment of Peano arithmetic formalizing the induction principle for the class of decidable predicates,IΔ1. We show thatIΔ1is independent from the set of all true arithmetical Π2-sentences. Moreover, we establish the connections between this theory and some classes of oracle computable functions with restrictions on the allowed number of queries. We also obtain some conservation and independence results for parameter free and inference rule forms of Δ1-induction.An open problem formulated by J. Paris (see [4, 5]) is whetherIΔ1proves the corresponding least element principle for decidable predicates,LΔ1(or, equivalently, the Σ1-collection principleBΣ1). We reduce this question to a purely computation-theoretic one.
Definable sets in boolean ordered o-minimal structures. II
Authors: Wencel Roman 
Published: March 2005

AbstractLet (M, ≤,…) denote a Boolean ordered o-minimal structure. We prove that a Boolean subalgebra of M determined by an algebraically closed subset contains no dense atoms. We show that Boolean algebras with finitely many atoms do not admit proper expansions with o-minimal theory. The proof involves decomposition of any definable set into finitely many pairwise disjoint cells, i.e., definable sets of an especially simple nature. This leads to the conclusion that Boolean ordered structures with o-minimal theories are essentially bidefinable with Boolean algebras with finitely many atoms, expanded by naming constants. We also discuss the problem of existence of proper o-minimal expansions of Boolean algebras.
On a problem of Cooper and Epstein
Authors: Ishmukhametov Shamil 
Published: March 2005

AbstractIn “Bounding minimal degrees by computably enumerable degrees” by A. Li and D. Yang, (this Journal, [1998]), the authors prove that there exist non-computable computably enumerable degrees c > a > 0 such that any minimal degree m being below c is also below a. We analyze the proof of their result and show that the proof contains a mistake. Instead we give a proof for the opposite result.
Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
Authors: Blass Andreas , Gurevich Yuri 
Published: March 2005

AbstractThis paper developed from Shelah's proof of a zero-one law for the complexity class “choiceless polynomial time,” defined by Shelah and the authors. We present a detailed proof of Shelah's result for graphs, and describe the extent of its generalizability to other sorts of structures. The extension axioms, which form the basis for earlier zero-one laws (for first-order logic, fixed-point logic, and finite-variable infinitary logic) are inadequate in the case of choiceless polynomial time; they must be replaced by what we call the strong extension axioms. We present an extensive discussion of these axioms and their role both in the zero-one law and in general.
The Church-Rosser property in dual combinatory logic
Authors: Bimbó Katalin 
Published: March 2005

AbstractDual combinatorsemerge from the aim of assigning formulas containing ← as types to combinators. This paper investigates formally some of the properties of combinatory systems that include both combinators and dual combinators. Although the addition of dual combinators to a combinatory system does not affect the unique decomposition of terms, it turns out that some terms might be redexes in two ways (with a combinator as its head, and with a dual combinator as its head). We prove a general theorem stating thatno dual combinatory system possesses the Church-Rosser property. Although the lack of confluence might be problematic in some cases, it is not a problemper se. In particular, we show that no damage is inflicted upon thestructurally free logics, the system in which dual combinators first appeared.
Presburger sets and p-minimal fields
Authors: Cluckers Raf 
Published: March 2005

AbstractWe prove a cell decomposition theorem for Presburger sets and introduce a dimension theory for Z-groups with the Presburger structure. Using the cell decomposition theorem we obtain a full classification of Presburger sets up to definable bijection. We also exhibit a tight connection between the definable sets in an arbitrary p-minimal field and Presburger sets in its value group. We give a negative result about expansions of Presburger structures and prove uniform elimination of imaginaries for Presburger structures within the Presburger language.
Epistemic models of shallow depths and decision making in games: Horticulture
Authors: Kaneko Mamoru , Suzuki Nobu-Yuki 
Published: March 2005

AbstractKaneko-Suzuki developed epistemic logics of shallow depths with multiple players for investigations of game theoretical problems. By shallow depth, we mean that nested occurrences of belief operators of players in formulae are restricted, typically to be of finite depths, by a givenepistemic structure. In this paper, we develop various methods of surgical operations (cut and paste) of epistemic world models. An example is a bouquet-making, i.e., tying several models into a bouquet. Another example is to engraft a model to some branches of another model. By these methods, we obtain various meta-theorems on semantics and syntax on epistemic logics. To illustrate possible uses of our meta-theorems, we present one game theoretical theorem, which is also a meta-theorem in the sense of logic.
The Steel hierarchy of ordinal valued Borel mappings
Authors: Duparc J. 
Published: March 2005

AbstractGiven well ordered countable sets of the form Λϕ, we consider Borel mappings from Λϕω with countable image inside the ordinals. The ordinals and Λϕω are respectively equipped with the discrete topology and the product of the discrete topology on Λϕ. The Steel well-ordering on such mappings is denned by ϕ ≤ ψ iff there exists a continuous function f such that ϕ(x) ≤ ψof(x) holds for any x ϵ Λϕω. It induces a hierarchy of mappings which we give a complete description of. We provide, for each ordinal α, a mapping whose rank is precisely α in this hierarchy and we also compute the height of the hierarchy restricted to mappings with image bounded by α. These mappings being viewed as partitions of the reals, there is, in most cases, a unique distinguished element of the partition. We analyze the relation between its topological complexity and the rank of the mapping in this hierarchy.
Some strongly undecidable natural arithmetical problems, with an application to intuitionistic theories
Authors: Raatikainen Panu 
Published: March 2005

Although Church and Turing presented their path-breaking undecidability results immediately after their explication of effective decidability in 1936, it has been generally felt that these results do not have any direct bearing on ordinary mathematics but only contribute to logic, metamathematics and the theory of computability. Therefore it was such a celebrated achievement when Yuri Matiyasevich in 1970 demonstrated that the problem of the solvability of Diophantine equations is undecidable. His work was building essentially on the earlier work by Julia Robinson, Martin Davis and Hilary Putnam (1961), who had showed that the problem of solvability of exponential Diophantine equations is undecidable. One should note, however, that although it was only Matiyasevich's result which finally solved Hilbert's tenth problem, already the earlier result had provided a perfectly natural problem of ordinary number theory which is undecidable.Nevertheless, both the set of Diophantine equations with solutions and the set of exponential Diophantine equations with solutions are still semi-decidable, that is, recursively enumerable (i.e., Σ10); if an equation in fact has a solution, this can be eventually verified. More generally, they are — as are their complements, the sets of equations with no solutions, which are Π10, — also Trial and Error decidable (Putnam [1965]), or decidable in the limit (Shoenfield [1959]), for every Δ20set is (and conversely). This last-mentioned natural “liberalized” notion of decidability has begun more recently to play an essential role e.g., in so-called Formal Learning Theory (see e.g., Osherson, Stob, and Weinstein [1986], Kelly [1996]).
Separably closed fields with Hasse derivations
Authors: Ziegler Martin 
Published: March 2005

AbstractIn [6] Messmer and Wood proved quantifier elimination for separably closed fields of finite Ershov invariant e equipped with a (certain) Hasse derivation. We propose a variant of their theory, using a sequence of e commuting Hasse derivations. In contrast to [6] our Hasse derivations are iterative.
Definability with a predicate for a semi-linear set
Authors: Benedikt Michael , Keisler H. Jerome 
Published: March 2005

AbstractWe settle a number of questions concerning definability in first order logic with an extra predicate symbol ranging over semi-linear sets. We give new results both on the positive and negative side: we show that in first-order logic one cannot query a semi-linear set as to whether or not it contains a line, or whether or not it contains the line segment between two given points. However, we show that some of these queries become definable if one makes small restrictions on the semi-linear sets considered.
Universal graphs at the successor of a singular cardinal
Authors: Džamonja Mirna , Shelah Saharon 
Published: March 2005

AbstractThe paper is concerned with the existence of a universal graph at the successor of a strong limit singular μ of cofinality ℵ0. Starting from the assumption of the existence of a supercompact cardinal, a model is built in which for some such μ there are μ++ graphs on μ+ that taken jointly are universal for the graphs on μ+, while .The paper also addresses the general problem of obtaining a framework for consistency results at the successor of a singular strong limit starting from the assumption that a supercompact cardinal κ exists. The result on the existence of universal graphs is obtained as a specific application of a more general method.
Outer models and genericity
Authors: Stanley M. C. 
Published: March 2005

Why is forcing the only known method for constructing outer models of set theory?If V is a standard transitive model of ZFC, then a standard transitive model W of ZFC is an outer model of V if V ⊆ W and V ∩ OR = W ∩ OR.Is every outer model of a given model a generic extension? At one point Solovay conjectured that if 0# exists, then every real that does not construct 0# lies in L[G], for some G that is generic for some forcing ℙ ∈ L. Famously, this was refuted by Jensen's coding theorem. He produced a real that is generic for an L-definable class forcing property, but does not lie in any set forcing extension of L.Beller, Jensen, and Welch in Coding the universe [BJW] revived Solovay's conjecture by asking the following question: Let a ⊆ ω be such that L[a] ⊨ “0# does not exist”. Is there ab∈ L[a] such that a ∉ L[b] and a is set generic over L[b].