bluuebunny/crossref_metadata_2025 huggingface dataset:
On the Philosophical Development of Kurt Gödel
Authors: Atten Mark van , Kennedy Juliette
Published: March 2005

It is by now well known that Gödel first advocated the philosophy of Leibniz and then, since 1959, that of Husserl. This raises three questions:

1.

How is this turn to Husserl to be interpreted? Is it a dismissal of the Leibnizian philosophy, or a different way to achieve similar goals?

2.

Why did Gödel turn specifically to the later Husserl's transcendental idealism?

3.

Is there any detectable influence from Husserl on Gödel's writings?

Regarding the first question, Wang [96, p.165] reports that Gödel ‘[saw] in Husserl's work a method of refining and consolidating Leibniz' monadology’. But what does this mean? In what for Gödel relevant sense is Husserl's work a refinement and consolidation of Leibniz' monadology?

The second question is particularly pressing, given that Gödel was, by his own admission, a realist in mathematics since 1925. Wouldn't the uncompromising realism of the early Husserl's Logical investigations have been a more obvious choice for a Platonist like Gödel?

The third question can only be approached when an answer to the second has been given, and we want to suggest that the answer to the first question follows from the answer to the second. We begin, therefore, with a closer look at the actual turn towards phenomenology.

Some 30 years before his serious study of Husserl began, Gödel was well aware of the existence of phenomenology. Apart from its likely appearance in the philosophy courses that Gödel took, it reached him from various directions.
Identity of Proofs Based on Normalization and Generality
Authors: Došen Kosta
Published: March 2005

Some thirty years ago, two proposals were made concerning criteria for identity of proofs. Prawitz proposed to analyze identity of proofs in terms of the equivalence relation based on reduction to normal formin natural deduction. Lambek worked on a normalization proposal analogous to Prawitz's, based on reduction to cut-free form in sequent systems, but he also suggested understanding identity of proofs in terms of an equivalence relation based on generality, two derivations having the same generality if after generalizing maximally the rules involved in them they yield the same premises and conclusions up to a renaming of variables. These two proposals proved to be extensionally equivalent only for limited fragments of logic.

The normalization proposal stands behind very successful applications of the typed lambda calculus and of category theory in the proof theory of intuitionistic logic. In classical logic, however, it did not fare well.

The generality proposal was rather neglected in logic, though related matters were much studied in pure category theory in connection with coherence problems, and there are also links to low-dimensional topology and linear algebra. This proposal seems more promising than the other one for the general proof theory of classical logic.
Barwise: Infinitary Logic and Admissible Sets
Authors: Keisler H. Jerome , Knight Julia F.
Published: March 2005

§0. Introduction. In [16], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [46] (see also the papers [47], [48]), and that of Platek [58], at Stanford, on admissible sets.

Barwise's work on infinitary logic and admissible sets is described in his thesis [4], the book [13], and papers [5]—[16]. We do not try to give a systematic review of these papers. Instead, our goal is to give a coherent introduction to infinitary logic and admissible sets. We describe results of Barwise, of course, because he did so much. In addition, we mention some more recent work, to indicate the current importance of Barwise's ideas. Many of the central results are stated without proof, but occasionally we sketch a proof, to indicate how the ideas fit together.

Chapters 1 and 2 describe infinitary logic and admissible sets at the time Barwise began his work, circa 1965. From Chapter 3 on, we survey the developments that took place after Barwise appeared on the scene.

§1. Background on infinitary logic. In this chapter, we describe the situation in infinitary logic at the time that Barwise began his work. We need some terminology. By a vocabulary, we mean a set L of constant symbols, and relation and operation symbols with finitely many argument places. As usual, by an L-structureM, we mean a universe set M with an interpretation for each symbol of L.
Barwise: Abstract Model Theory and Generalized Quantifiers
Authors: Väänänen Jouko
Published: March 2005

§1. Introduction. After the pioneering work of Mostowski [29] and Lindström [23] it was Jon Barwise's papers [2] and [3] that brought abstract model theory and generalized quantifiers to the attention of logicians in the early seventies. These papers were greeted with enthusiasm at the prospect that model theory could be developed by introducing a multitude of extensions of first order logic, and by proving abstract results about relationships holding between properties of these logics. Examples of such properties are

κ-compactness.Any set of sentences of cardinality ≤ κ, every finite subset of which has a model, has itself a model.Löwenheim-Skolem Theorem down toκ.If a sentence of the logic has a model, it has a model of cardinality at most κ.Interpolation Property.If ϕ and ψ are sentences such that ⊨ ϕ → Ψ, then there is θ such that ⊨ ϕ → θ, ⊨ θ → Ψ and the vocabulary of θ is the intersection of the vocabularies of ϕ and Ψ.

Lindstrom's famous theorem characterized first order logic as the maximal ℵ0-compact logic with Downward Löwenheim-Skolem Theorem down to ℵ0. With his new concept of absolute logics Barwise was able to get similar characterizations of infinitary languagesLκω. But hopes were quickly frustrated by difficulties arising left and right, and other areas of model theory came into focus, mainly stability theory. No new characterizations of logics comparable to the early characterization of first order logic given by Lindström and of infinitary logic by Barwise emerged. What was first called soft model theory turned out to be as hard as hard model theory.
Jon Barwise's Papers on Natural Language Semantics
Authors: Devlin Keith
Published: March 2005

For most of the 1980s, Jon Barwise focused much of his research in the area of natural language semantics. This article surveys his research publications in that area.

Most, but not all, of those publications were in the area of situation semantics, a new approach to natural language semantics Barwise developed jointly with his colleague John Perry in the first half of the 1980s. That work was both blessed, and cursed, by becoming closely identified in academic circles with the award of a $23 million gift to Stanford from the System Development Foundation for the establishment in 1983 of its Center for the Study of Language and Information (CSLI). The development of situation semantics, and in due course its underlying mathematical foundation Situation Theory, carried out for the most part within the framework of CSLI's STASS research group (Situation Theory and Situation Semantics), was actually a relatively small part of the overall research program at CSLI. But because Barwise and Perry were leading figures at CSLI, were centrally involved in securing the SDF gift, and were respectively the first and second directors of CSLI, a general impression sprung up that the two of them had been awarded millions of dollars to develop situation semantics.

A major consequence of this false impression was that from the theory's early days, a great deal of interest was shown in the project. With so many accomplished scholars pouring over the work while the ink was still wet on the manuscript pages, Barwise and Perry were able to take advantage of a broad range of helpful criticism (even if it was not always given with a view to being helpful). This meant that they were able to develop the new theory much more rapidly than would otherwise have been the case.
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

Frege 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

We 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

Paul 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

This 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.
Transfinite Progressions: A Second Look at Completeness
Authors: Franzén Torkel
Published: March 2005

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that initiated by Turing in his “ordinal logics” (see Gandy and Yates [2001]) and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach.
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 program

where 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 that

Much 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).
Zermelo and Set Theory
Authors: Akihiro Kanamori
Published: March 2005

Ernst Friedrich Ferdinand Zermelo (1871–1953) transformed the set theory of Cantor and Dedekind in the first decade of the 20th century by incorporating the Axiom of Choice and providing a simple and workable axiomatization setting out generative set-existence principles. Zermelo thereby tempered the ontological thrust of early set theory, initiated the delineation of what is to be regarded as set-theoretic, drawing out the combinatorial aspects from the logical, and established the basic conceptual framework for the development of modern set theory. Two decades later Zermelo promoted a distinctive cumulative hierarchy view of models of set theory and championed the use of infinitary logic, anticipating broad modern developments. In this paper Zermelo's published mathematical work in set theory is described and analyzed in its historical context, with the hindsight afforded by the awareness of what has endured in the subsequent development of set theory. Elaborating formulations and results are provided, and special emphasis is placed on the to and fro surrounding the Schröder-Bernstein Theorem and the correspondence and comparative approaches of Zermelo and Gödel. Much can be and has been written about philosophical and biographical issues and about the reception of the Axiom of Choice, and we will refer and defer to others, staying the course through the decidedly mathematical themes and details.
Mass Problems and Randomness
Authors: Simpson Stephen G.
Published: March 2005

A 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

This 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

In 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

Let 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

We 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

Let (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

In “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

This 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

Dual 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

We 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

Kaneko-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

Given 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.
Q-pointness, P-pointness and feebleness of ideals
Authors: Matet Pierre , Pawlikowski Janusz
Published: March 2005

We study the degree of (weak) (Q-pointness, and that of (weak) P-pointness, of ideals on a regular infinite cardinal.
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

In [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

We 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.
The theory of Liouville functions
Authors: Koiran Pascal
Published: March 2005

A Liouville function is an analytic function H: ℂ → ℂ with a Taylor series such the an's form a “very fast growing” sequence of integers. In this paper we exhibit the complete first-order theory of the complex field expanded with H.
Universal graphs at the successor of a singular cardinal
Authors: Džamonja Mirna , Shelah Saharon
Published: March 2005

The 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].
Simulating polyadic modal logics by monadic ones
Authors: Goguadze George , Piazza Carla , Venema Yde
Published: March 2005

We define an interpretation of modal languages with polyadic operators in modal languages that use monadic operators (diamonds) only. We also define a simulation operator which associates a logic Λsim in the diamond language with each logic Λ in the language with polyadic modal connectives. We prove that this simulation operator transfers several useful properties of modal logics, such as finite/recursive axiomatizability, frame completeness and the finite model property, canonicity and first-order definability.
Constructive interpolation in hybrid logic
Authors: Blackburn Patrick , Marx Maarten
Published: March 2005

Craig's interpolation lemma (if φ → ψ is valid, then φ → θ and θ → ψ are valid, for θ a formula constructed using only primitive symbols which occur both in φ and ψ) fails for many propositional and first order modal logics. The interpolation property is often regarded as a sign of well-matched syntax and semantics. Hybrid logicians claim that modal logic is missing important syntactic machinery, namely tools for referring to worlds, and that adding such machinery solves many technical problems. The paper presents strong evidence for this claim by defining interpolation algorithms for both propositional and first order hybrid logic. These algorithms produce interpolants for the hybrid logic of every elementary class of frames satisfying the property that a frame is in the class if and only if all its point-generated subframes are in the class. In addition, on the class of all frames, the basic algorithm is conservative: on purely modal input it computes interpolants in which the hybrid syntactic machinery does not occur.
A Gitik iteration with nearly Easton factoring
Authors: Mitchell William J.
Published: March 2005

We reprove Gitik's theorem that if the GCH holds and o(κ) = κ + 1 then there is a generic extension in which κ is still measurable and there is a closed unbounded subset C of κ such that every ν ∈ C is inaccessible in the ground model.

Unlike the forcing used by Gitik, the iterated forcing ℛλ+1 used in this paper has the property that if λ is a cardinal less then κ then ℛλ+1 can be factored in V as ℛκ+1 = ℛλ+1 × ℛλ+1,κ where ∣ℛλ+1∣ ≤ λ+ and ℛλ+1,κ does not add any new subsets of λ.
The laws of integer divisibility, and solution sets of linear divisibility conditions
Authors: van den Dries L. , Wilkie A. J.
Published: March 2005

We prove linear and polynomial growth properties of sets and functions that are existentially definable in the ordered group of integers with divisibility. We determine the laws of addition with order and divisibility.
A simple maximality principle
Authors: Hamkins Joel David
Published: March 2005

In this paper, following an idea of Christophe Chalons, I propose a new kind of forcing axiom, the Maximality Principle, which asserts that any sentence φ holding in some forcing extension Vℙ and all subsequent extensions Vℙ*ℚ holds already in V. It follows, in fact, that such sentences must also hold in all forcing extensions of V. In modal terms, therefore, the Maximality Principle is expressed by the scheme (◊ □ φ) ⇒ □ φ, and is equivalent to the modal theory S5. In this article, I prove that the Maximality Principle is relatively consistent with ZFC. A boldface version of the Maximality Principle, obtained by allowing real parameters to appear in φ, is equiconsistent with the scheme asserting that Vδ ≺ V for an inaccessible cardinal δ, which in turn is equiconsistent with the scheme asserting that ORD is Mahlo. The strongest principle along these lines is □ , which asserts that holds in V and all forcing extensions. From this, it follows that 0# exists, that x# exists for every set x, that projective truth is invariant by forcing, that Woodin cardinals are consistent and much more. Many open questions remain.
Classification theory and 0#
Authors: Friedman Sy D. , Hyttinen Tapani , Rautila Mika
Published: March 2005

We characterize the classifiability of a countable first-order theory T in terms of the solvability (in the sense of [2]) of the potential-isomorphism problem for models of T.
Approachability and Games on Posets
Authors: Yoshinobu Yasuo
Published: March 2005

We show that for any infinite cardinal κ, every strongly (κ + 1 )-strategically closed poset is strongly κ+-strategically closed if and only if APκ (the approachability property) holds, answering the question asked in [5]. We also give a complete classification of strengths of strategic closure properties and that of strong strategic closure properties respectively.
Atomless varieties
Authors: Venema Yde
Published: March 2005

We define a nontrivial variety of boolean algebras with operators such that every member of the variety is atomless. This shows that not every variety of boolean algebras with operators is generated by its atomic members, and thus establishes a strong incompleteness result in (multi-)modal logic.
The Strength of Blackwell determinacy
Authors: Martin Donald A. , Neeman Itay , Vervoort Marco
Published: March 2005

We show that Blackwell determinacy in L(ℝ) implies determinacy in L(ℝ).
The non-compactness of square
Authors: Cummings James , Foreman Matthew , Magidor Menachem
Published: March 2005

This note proves two theorems. The first is that it is consistent to have for every n, but not have . This is done by carefully collapsing a supercompact cardinal and adding square sequences to each ωn. The crux of the proof is that in the resulting model every stationary subset of ℵω+1 ⋂ cof(ω) reflects to an ordinal of cofinality ω1, that is to say it has stationary intersection with such an ordinal.

This result contrasts with compactness properties of square shown in [3]. In that paper it is shown that if one has square at every ωn, then there is a square type sequence on the points of cofinality ωk, k > 1 in ℵω+1. In particular at points of cofinality greater than ω1 there is a strongly non-reflecting stationary set of points of countable cofinality.

The second result answers a question of Džamonja, by showing that there can be no squarelike sequence above a supercompact cardinal, where “squarelike” means that one replaces the requirement that the cofinal sets be closed and unbounded by the requirement that they be stationary at all points of uncountable cofinality.
Automorphism groups of trivial strongly minimal structures
Authors: Blossier Thomas
Published: March 2005

We study automorphism groups of trivial strongly minimal structures. First we give a characterization of structures of bounded valency through their groups of automorphisms. Then we characterize the triplets of groups which can be realized as the automorphism group of a non algebraic component, the subgroup stabilizer of a point and the subgroup of strong automorphisms in a trivial strongly minimal structure, and also we give a reconstruction result. Finally, using HNN extensions we show that any profinite group can be realized as the stabilizer of a point in a strongly minimal structure of bounded valency.
Exactly controlling the non-supercompact strongly compact cardinals
Authors: Apter Arthur W. , Hamkins Joel David
Published: March 2005

We summarize the known methods of producing a non-supercompact strongly compact cardinal and describe some new variants. Our Main Theorem shows how to apply these methods to many cardinals simultaneously and exactly control which cardinals are supercompact and which are only strongly compact in a forcing extension. Depending upon the method, the surviving non-supercompact strongly compact cardinals can be strong cardinals, have trivial Mitchell rank or even contain a club disjoint from the set of measurable cardinals. These results improve and unify Theorems 1 and 2 of [5], due to the first author.
On revision operators
Authors: Welch P. D.
Published: March 2005

We look at various notions of a class of definability operations that generalise inductive operations, and are characterised as “revision operations”. More particularly we: (i) characterise therevision theoretically definablesubsets of a countable acceptable structure; (ii) show that the categorical truth set of Belnap and Gupta's theory of truth over arithmetic usingfullyvaried revision sequences yields a complete Σ31set of integers; (iii) the set ofstably categoricalsentences using their revision operator Ψ is similarly Σ31and which is complete in GÖdel's universe of constructive setsL; (iv) give an alternative account of a theory of truth—realistic variancethat simplifies full variance, whilst at the same time arriving at Kripkean fixed points.
Canonical functions, non-regular ultrafilters and Ulam's problem on ω1
Authors: Deiser Oliver , Donder Dieter
Published: March 2005

Our main results are:

Theorem 1. Con(ZFC + “every function f: ω1 → ω1 is dominated by a canonical function”) implies Con(ZFC + “there exists an inaccessible limit of measurable cardinals”). [In fact equiconsistency holds.]

Theorem 3. Con(ZFC + “there exists a non-regular uniform ultrafilter on ω1”) implies Con(ZFC + “there exists an inaccessible stationary limit of measurable cardinals”).

Theorem 5. Con (ZFC + “there exists an ω1-sequence of ω1-complete uniform filters on ω1 s.t. every A ⊆ ω1 is measurable w.r.t. a filter in (Ulam property)”) implies Con(ZFC + “there exists an inaccessible stationary limit of measurable cardinals”).

We start with a discussion of the canonical functions and look at some combinatorial principles. Assuming the domination property of Theorem 1, we use the Ketonen diagram to show that ω2V is a limit of measurable cardinals in Jensen's core model KMO for measures of order zero. Using related arguments we show that ω2V is a stationary limit of measurable cardinals in KMO, if there exists a weakly normal ultrafilter on ω1. The proof yields some other results, e.g., on the consistency strength of weak*-saturated filters on ω1, which are of interest in view of the classical Ulam problem.
Generality of proofs and its Brauerian representation
Authors: Došen Kosta , Petrić Zoran
Published: March 2005

The generality of a derivation is an equivalence relation on the set of occurrences of variables in its premises and conclusion such that two occurrences of the same variable are in this relation if and only if they must remain occurrences of the same variable in every generalization of the derivation. The variables in question are propositional or of another type. A generalization of the derivation consists in diversifying variables without changing the rules of inference.

This paper examines in the setting of categorial proof theory the conjecture that two derivations with the same premises and conclusions stand for the same proof if and only if they have the same generality. For that purpose generality is defined within a category whose arrows are equivalence relations on finite ordinals, where composition is rather complicated. Several examples are given of deductive systems of derivations covering fragments of logic, with the associated map into the category of equivalence relations of generality.

This category is isomorphically represented in the category whose arrows are binary relations between finite ordinals, where composition is the usual simple composition of relations. This representation is related to a classical representation result of Richard Brauer.
The completeness of Heyting first-order logic
Authors: Tait W. W.
Published: March 2005

Restricted to first-order formulas, the rules of inference in the Curry-Howard type theory are equivalent to those of first-order predicate logic as formalized by Heyting, with one exception: ∃-elimination in the Curry-Howard theory, where ∃x:A,F(x) is understood as disjoint union, are the projections, and these do not preserve first-orderedness. This note shows, however, that the Curry-Howard theory is conservative over Heyting's system.