bluuebunny/crossref_metadata_2025 huggingface dataset:
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

We 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

The 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

If 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

We 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

Hofstadter 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 index set {e: We ≡1X}.
Authors: Herrmann E.
Published: May 2006

Let X be any infinite, coinfinite r.e. set. We show that the index set {e: We ≡1X) is -complete, answering a question posed by Odifreddi in [2].
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.
Some elementary degree-theoretic reasons why structures need similarity types
Authors: McLaughlin T. G.
Published: May 2006

By a “partly numerical structure” (p.n.s.) we shall here mean a quadruple , where M is a set, ω = the natural numbers, ω ⊆ M, and are disjoint sets, is a set of relations (of various positive integral arities) on M, and is a set of functions (of various positive integral arities) with arguments and values in M. Thus, in calculated disharmony with common practice, we do not (except as noted below, in connection with naming the elements of ω) fix a similarity type as part of our notion of a “structure”. Suppose a finitary first-order language (with identity) has been specified, with constant symbols , n ∈ ω, and with exactly enough relation and function symbols of each arity to enable us to interpret in . We wish to consider the variation in the degree (relative to a fixed Gödel-numbering of ) of the complete -theory of as we vary the way in which elements of ∪ are assigned as interpretations to the relation and function symbols of . We shall in fact, therefore, be concerned exclusively with p.n.s.'s for which ∪ is countable. More: we assume to be such that we can effectively tell, uniformly in n > 0, exactly how many n-ary relations has and exactly how many n-ary functions has.
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

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

As a byproduct of the proof we give some theorems which may be useful elsewhere in propositional calculus.
On partitioning the infinite subsets of large cardinals
Authors: Watro R. J.
Published: May 2006

Let λ be an ordinal less than or equal to an infinite cardinal κ. For S ⊂ κ, [S]λ denotes the collection of all order type λ subsets of S. A set X ⊂ [κ]λ will be called Ramsey iff there exists p ∈ [κ]κ such that either [p]λ ⊂ X or [p]λ ∩ X = ∅. The set p is called homogeneous for X.

The infinite Ramsey theorem implies that all subsets of [ω]n are Ramsey for n < ω. Using the axiom of choice, one can define a non-Ramsey subset of [ω]ω. In [GP], Galvin and Prikry showed that all Borel subsets of [ω]ω are Ramsey, where one topologizes [ω]ω as a subspace of Baire space. Silver [S] proved that analytic sets are Ramsey, and observed that this is best possible in ZFC.

When κ > ω, the assertion that all subsets of [κ]n are Ramsey is a large cardinal hypothesis equivalent to κ being weakly compact (and strongly inaccessible). Again, is not possible in ZFC to have all subsets of [κ]ω Ramsey. The analogy to the Galvin-Prikry theorem mentioned above was established by Kleinberg, extending work by Kleinberg and Shore in [KS]. The set [κ]ω is given a topology as a subspace of κω, which has the usual product topology, κ taken as discrete. It was shown that all open subsets of [κ]ω are Ramsey iff κ is a Ramsey cardinal (that is, κ → (κ)<ω).

In this note we examine the spaces [κ]λ for κ ≥ λ ≥ ω. We show that κ Ramsey implies all open subsets of [κ]λ are Ramsey for λ < κ, and that if κ is measurable, then all open subsets of [κ]κ are Ramsey. Let us remark here that we can with the same methods prove these results with “κ-Borel” in the place of “open”, where the κ-Borel sets are the smallest collection containing the opens and closed under complementation and intersections of length less than κ. Also, although here we consider just subsets of [κ]λ, it is no more difficult to show that partitions of [κ]λ into less than κ many κ-Borel sets have, under the appropriate hypothesis, size κ homogeneous sets.
Propositional logic based on the dynamics of belief
Authors: Gärdenfors Peter
Published: May 2006

In this article propositions will be identified with a certain kind of changes of belief. The intended interpretation is that a proposition is characterised by the change it would induce if added to a state of belief. Propositions will thus be defined as functions from states of belief to states of belief. A set of postulates concerning the properties and existence of propositions will be formulated. A proposition will be said to be a tautology iff it is the identity function on states of belief. The main result is that the logic determined by the set of postulates is intuitionistic propositional logic.

The basic epistemic concept is that of a belief model, which is defined as a pair 〈, 〉, where is a nonempty set and is a class of functions from to . The elements in will be called states of belief and they will be denoted K, K′,…. A discussion of the epistemological interpretation of the states of belief can be found in Gärdenfors [2]. Here, no assumptions about the structure of the elements in will be made.

The elements in will be called propositions, and A, B, C, … will be used as variables over . Functions from states of belief to states of belief can be characterised as epistemic inputs. The intended interpretation of the functions in is that they correspond to changes of belief where the new evidence is accepted as “certain” or “known” in the resulting state of belief. This means that not all functions defined on can properly be called propositions.
The strength of nonstandard methods in arithmetic
Authors: Henson C. Ward , Kaufmann Matt , Keisler H. Jerome
Published: May 2006

We consider extensions of Peano arithmetic suitable for doing some of nonstandard analysis, in which there is a predicate N(x) for an elementary initial segment, along with axiom schemes approximating ω1-saturation. We prove that such systems have the same proof-theoretic strength as their natural analogues in second order arithmetic. We close by presenting an even stronger extension of Peano arithmetic, which is equivalent to ZF for arithmetic statements.
How to glue analysis models
Authors: Van Dalen D.
Published: May 2006

Among the more traditional semantics for intuitionistic logic the Beth and the Kripke semantics seem well-suited for direct manipulations required for the derivation of metamathematical results. In particular Smoryński demonstrated the usefulness of Kripke models for the purpose of obtaining closure properties for first-order arithmetic, [S], and second-order arithmetic, [J-S]. Weinstein used similar techniques to handle intuitionistic analysis, [W]. Since, however, Beth-models seem to lend themselves better for dealing with analysis, cf. [D], we have developed a somewhat more liberal semantics, that shares the features of both Kripke and Beth semantics, in order to obtain analogues of Smoryński's collecting operations, which we will call Smoryński-glueing, in line with the categorical tradition.
Closed sets and chain conditions in stable theories
Authors: Pillay Anand , Srour Gabriel
Published: May 2006

An impressive theory has been developed, largely by Shelah, around the notion of a stable theory. This includes detailed structure theorems for the models of such theories as well as a generalized notion of independence. The various stability properties can be defined in terms of the numbers of types over sets, or in terms of the complexity of definable sets. In the concrete examples of stable theories, however, one finds an important distinction between “positive” and “negative” information, such a distinction not being an a priori consequence of the general definitions. In the naive examples this may take the form of distinguishing between say a class of a definable equivalence relation and the complement of a class. In the more algebraic examples, this distinction may have a “topological” significance, for example with the Zariski topology on (the set of n-tuples of) an algebraically closed field, the “closed” sets being those given by sets of polynomial equalities. Note that in the latter case, every definable set is a Boolean combination of such closed sets (the definable sets are precisely the constructible sets). Similarly, stability conditions in practice reduce to chain conditions on certain “special” definable sets (e.g. in modules, stable groups). The aim here is to develop and present such notions in the general (model-theoretic) context. The basic notion is that of an “equation”. Given a complete theory T in a language L, an L-formula φ(x̄, ȳ) is said to be an equation (in x̄) if any collection Φ of instances of φ(i.e. of formulae φ(x̄, ā)) is equivalent to a finite subset Φ′ ⊂ Φ.
Generalisation of first-order logic to nonatomic domains
Authors: Roeper P.
Published: May 2006

The quantifiers of standard predicate logic are interpreted as ranging over domains of individuals, and interpreted formulae beginning with a quantifier make claims to the effect that something is true of every individual, i.e. of the whole domain, or of some individuals, i.e. of part of the domain. To state that something is true of all or part of a totality seems to be the basic significance of universal and existential quantification, and this by itself does not involve a specification of the structure of the totality. This means that the notion of quantification by itself does not demand totalities of individuals, i.e. atomic totalities, as domains of quantification. Nonatomic domains, such as volumes of space, or surfaces, are equally in order. So one might say that a certain predicate applies “everywhere” or “somewhere” in such a domain. All that the concept of quantification requires is a totality which is structured in terms of a part-to-whole relation, and appropriate properties that apply to part or all of the totality. Quantification does not demand that the totality have smallest parts, or atoms. There is no conflict with the sense of universal or existential quantification if the domain is nonatomic, if every one of its parts has itself proper parts.

The most general kind of quantification theory must then deal with totalities of any kind, atomic or not. The relationships among the parts of a domain are described by the theory of Boolean algebras, which we can regard as the most general characterisation of a totality, of a domain of quantification.

In this paper I shall be concerned with this generalised theory of quantification, which encompasses nonatomic domains as well as atomic and mixed domains, i.e. totalities consisting entirely or partly of individuals.
Dominical categories: recursion theory without elements
Authors: di Paola Robert A. , Heller Alex
Published: May 2006

Dominical categories are categories in which the notions of partial morphisms and their domains become explicit, with the latter being endomorphisms rather than subobjects of their sources. These categories form the basis for a novel abstract formulation of recursion theory, to which the present paper is devoted. The abstractness has of course its usual concomitant advantage of generality: it is interesting to see that many of the fundamental results of recursion theory remain valid in contexts far removed from their classic manifestations. A principal reason for introducing this new formulation is to achieve an algebraization of the generalized incompleteness theorem, by providing a category-theoretic development of the concepts and tools of elementary recursion theory that are inherent in demonstrating the theorem.

Dominical recursion theory avoids the commitment to sets and partial functions which is characteristic of other formulations, and thus allows for an intrinsic recursion theory within such structures as polyadic algebras. It is worthy of notice that much of elementary recursion theory can be developed without reference to elements.

By Gödel's generalized incompleteness theorem for consistent arithmetical system T we mean any statement of the following sort:

(1) if every recursive set is definable in T, then T is essentially undecidable [41]; or

(2) if all recursive functions are definable in T, then T is essentially undecidable [41]; or

(3) if every recursive set is definable in T, then T0 and R0 (the sets of Gödel numbers of the theorems and refutables of T) are recursively inseparable [39]; or

(4) if all re sets are representable in T, then T0 is creative [28], [39]; or

(5) if T is a Rosser theory (i.e., all disjoint re sets are strongly separable in T), then T0 and R0 are effectively inseparable [39].
Semiproper forcing axiom implies Martin maximum but not PFA+
Authors: Shelah Saharon
Published: May 2006

We prove that MM (Martin maximum) is equivalent (in ZFC) to the older axiom SPFA (semiproper forcing axiom). We also prove that SPFA does not imply SPFA+ or even PFA+ (using the consistency of a large cardinal).
On nontrivial types of U-rank 1
Authors: Buechler Steven
Published: May 2006

Theorem A. Suppose that T is superstable and p is a nontrivial type of U-rank 1. Then R(p, L, ∞)= 1.

Theorem B. Suppose that T is totally transcendental and p is a nontrivial type of U-rank 1. Then p has Morley rank 1.
Reducts of (C, +, ·) which contain +
Authors: Marker D. , Pillay A.
Published: May 2006

We show that the structure (C, +, ·) has no proper non locally modular reducts which contain +. In other words, if X ⊂ Cn is constructible and not definable in the module structure (C, +, λa)a Є C (where λa denotes multiplication by a) then multiplication is definable in (C, +, X).
Full reflection of stationary sets below ℵω
Authors: Jech Thomas , Shelah Saharon
Published: May 2006

It is consistent that, for every n ≥ 2, every stationary subset of ωn consisting of ordinals of cofinality ωκ, where κ = 0 or κ ≤ n − 3, reflects fully in the set of ordinals of cofinality ωn−1. We also show that this result is best possible.
Decision problems for differential equations
Authors: Denef J. , Lipshitz L.
Published: May 2006

In this paper we shall consider some decision problems for ordinary differential equations. All differential equations will be algebraic differential equations, i.e. equations of the form P(x, y, y′, …, y(n)) = 0 (or P(x, y1, …, ym, y′1 …, y′m, …) = 0 in the case of several dependent variables), where P is a polynomial in all its variables with rational coefficients. (We call P a differential polynomial.)

Jáskowski [6] showed that there is no algorithm to determine if a system of algebraic differential equations (in several dependent variables) has a solution on [0, 1]. An easier proof of this using results on Hilbert's tenth problem is given in [2]. It is natural to restrict the problem in the hope of finding something which is decidable. Two ways to do this are the following: (a) One can ask only for the existence of solutions locally, say around x = 0. Here solution may mean (i) analytic functions, (ii) germs of C∞ functions, or (iii) formal power series, (b) One can consider only one equation in one dependent variable, but ask for the existence of a solution on an interval. In [4] we gave an algorithm for deciding (a)(ii) and (a)(iii) and showed that (a)(i) is undecidable. In §4 (Theorem 4.1) we shall show that (b) (for real analytic solutions) is undecidable. This partially answers Problem 9 of Rubel [13], which stimulated this investigation. We shall also prove (Theorem 4.2) that, given an analytic function f(x) which is the solution of an algebraic differential equation, determined by some initial conditions at x = 0, one cannot in general determine if the radius of convergence of f is < 1 or ≥ 1.
An ideal characterization of Mahlo cardinals
Authors: Feng Qi
Published: May 2006

We show that a cardinal κ is a (strongly) Mahlo cardinal if and only if there exists a nontrivial κ-complete κ-normal ideal on κ. Also we show that if κ is Mahlo and λ ≧ κ and λ<κ = λ then there is a nontrivial κ-complete κ-normal fine ideal on Pκ(λ). If κ is the successor of a cardinal, we consider weak κ-normality and prove that if κ = μ+ and μ is a regular cardinal then (1) μ< μ = μ if and only if there is a nontrivial κ-complete weakly κ-normal ideal on κ, and (2) if μ< μ = μ < λ<μ = λ then there is a nontrivial κ-complete weakly κ-normal fine ideal on Pκ(λ).
On chains of relatively saturated submodels of a model without the order property
Authors: Grossberg Rami
Published: May 2006

Let M be a given model with similarity type L = L(M), and let L′ be any fragment of L∣L(M∣+,ω of cardinality ∣L(M)∣. We call N ≺ ML′-relatively saturated iff for every B ⊆ N of cardinality less than ∥N∥ every L′-type over B which is realized in M is realized in N. We discuss the existence of such submodels.

The following are corollaries of the existence theorems.

(1) If M is of cardinality at least ℶω1, and fails to have the ω order property, then there exists N ≺ M which is relatively saturated in M of cardinality ℶω1.

(2) Assume GCH. Let ψ ∈ Lω1, ω, and let L′ ⊆ Lω1, ω be a countable fragment containing ψ. If ∃χ > ℵ0 such that I(χ, ψ) < 2χ, then for every M ⊨ ψ and every cardinal λ < ∥M∥ of uncountable cofinality, M has an L′-relatively saturated submodel of cardinality λ.
Reachability is harder for directed than for undirected finite graphs
Authors: Ajtai Miklos , Fagin Ronald
Published: May 2006

Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain “built-in” relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraïssé games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at mostk, reachability is expressible by an existential monadic second-order sentence.
Patching ideal families and enforcing reflection
Authors: Leary Christopher C.
Published: May 2006

For several years much research has been directed at ideals associated with large cardinals. In this paper we discuss ideal families and use this tool to investigate the saturation properties of various large cardinal ideals.

Much of the work in this paper is a direct outgrowth of material presented in my doctoral dissertation written at the University of Michigan under the patient guidance of Andreas Blass. I would also like to thank the referee for several helpful questions and comments on the original version of this paper.
A construction of non-well-founded sets within Martin-Löf's type theory
Authors: Lindström Ingrid
Published: May 2006

In this paper, we show that non-well-founded sets can be defined constructively by formalizing Hallnäs' limit definition of these within Martin-Löfs theory of types. A system is a type W together with an assignment of and to each ∝ ∈ W. We show that for any system W we can define an equivalence relation =w such that ∝ =w ß ∈ U and =w is the maximal bisimulation. Aczel's proof that CZF can be interpreted in the type V of iterative sets shows that if the system W satisfies an additional condition (*), then we can interpret CZF minus the set induction scheme in W. W is then extended to a complete system W* by taking limits of approximation chains. We show that in W* the antifoundation axiom AFA holds as well as the axioms of CFZ−.
Kueker's conjecture for stable theories
Authors: Hrushovski Ehud
Published: May 2006

Kueker's conjecture is proved for stable theories, for theories that interpret a linear ordering, and for theories with Skolem functions. The proof of the stable case involves certain results on coordinatization that are of independent interest.
Compact and majorizable functionals of finite type
Authors: Bezem Marc
Published: May 2006

The main result of this paper will be that various notions of majorizability and compactness coincide in the full typestructure over the natural numbers. Moreover we shall show that the extensional typestructure of strongly majorizable functionals can be obtained by applying Zucker's construction ( )E to any of these coinciding intensional typestructures. A different result is proved in the typestructure of effective operations, where not every majorizable functional is compact. Finally we shall introduce the concept of relative compactness in the full typestructure and prove that there are just two degrees of compactness.
Trees and -subsets of ω1ω1
Authors: Mekler Alan , Väänänen Jouko
Published: May 2006

We study descriptive set theory in the space by letting trees with no uncountable branches play a similar role as countable ordinals in traditional descriptive set theory. By using such trees, we get, for example, a covering property for the class of -sets of .

We call a family of trees universal for a class of trees if ⊆ and every tree in can be order-preservingly mapped into a tree in . It is well known that the class of countable trees with no infinite branches has a universal family of size ℵ1. We shall study the smallest cardinality of a universal family for the class of trees of cardinality ≤ ℵ1 with no uncountable branches. We prove that this cardinality can be 1 (under ¬CH) and any regular cardinal κ which satisfies (under CH). This bears immediately on the covering property of the -subsets of the space .

We also study the possible cardinalities of definable subsets of . We show that the statement that every definable subset of has cardinality <ωn or cardinality is equiconsistent with ZFC (if n ≥ 3) and with ZFC plus an inaccessible (if n = 2).

Finally, we define an analogue of the notion of a Borel set for the space and prove a Souslin-Kleene type theorem for this notion.
On the number of automorphisms of uncountable models
Authors: Shelah Saharon , Tuuri Heikki , Väänänen Jouko
Published: May 2006

Let σ() denote the number of automorphisms of a model of power ω1. We derive a necessary and sufficient condition in terms of trees for the existence of an with . We study the sufficiency of some conditions for . These conditions are analogous to conditions studied by D. Kueker in connection with countable models.
Sous-groupes periodiques d'un groupe stable
Authors: Poizat Bruno , Wagner Frank
Published: May 2006

We develop a Sylow theory for stable groups satisfying certain additional conditions (2- finiteness, solvability or smallness) and show that their maximal p-subgroups are locally finite and conjugate. Furthermore, we generalize a theorem of Baer-Suzuki on subgroups generated by a conjugacy class of p-elements.
Consistency of Suslin's hypothesis, a nonspecial Aronszajn tree, and GCH
Authors: Schlindwein Chaz
Published: May 2006

Introduction. In [Sh, Chapter IX], Shelah constructs a model of set theory in which Suslin's hypothesis is true, yet there is an Aronszajn tree which is not special. In his model, we have . He asks whether the same result could be obtained consistently with CH. In this paper, we answer his question in the affirmative.

Let us say that a tree T is S-st-special iff there is a function ƒ with dom(f) = {t ∈ T: rank(t) ∈ S} and for every t1 < t2 both in dom(t) we have f(t2) ≠ f(t1) < rank(t1). In Shelah's model, every tree is S-st-special for some fixed stationary costationary set S. Also, there is some tree T such that T is not S′-st-special whenever S′ – S is stationary. These properties, which are sufficient to ensure that Suslin's hypothesis holds and that T is not special, also hold in the model constructed in this paper. These properties also ensure that every Aronszajn tree has a stationary antichain (i.e., an antichain A such that {rank(t): t ∈ A} is stationary). Hence, it is natural to ask whether there is a model of Suslin's hypothesis in which some Aronszajn tree has no stationary antichain. We answer in the affirmative in [S].

The construction we use owes much to Shelah's approach to the theorem, due to Jensen (see [DJ]), that CH is consistent with Suslin's hypothesis. This is given in [Sh, Chapter V].
Stratified languages
Authors: Pétry A.
Published: May 2006

We consider arbitrary stratified languages. We study structures which satisfy the same stratified sentences and we obtain an extension of Keisler's Isomorphism Theorem to this situation. Then we consider operations which are definable by a stratified formula and modify the ‘type’ of their argument by one; we prove that for such an operationFthe sentencec=F(c)and the schemeφ(c) ↔ (F(c)), where↔(x) varies among all the stratified formulas with no variable other thanxfree, imply the same stratified {c}-sentences.
Abacus logic: The lattice of quantum propositions as the poset of a theory
Authors: Malhas Othman Qasim
Published: May 2006

With a certain graphic interpretation in mind, we say that a function whose value at every point in its domain is a nonempty set of real numbers is an Abacus. It is shown that to every collection C of abaci there corresponds a logic, called an abacus logic, i.e.. a certain set of propositions partially ordered by generalized implication. It is also shown that to every collection C of abaci there corresponds a theory Jc in a classical propositional calculus such that the abacus logic determined by C is isomorphic to the poset of Jc. Two examples are given. In both examples abacus logic is a lattice in which there happens to be an operation of orthocomplementation. In the first example abacus logic turns out to be the Lindenbaum algebra of Jc. In the second example abacus logic is a lattice isomorphic to the ortholattice of subspaces of a Hilbert space. Thus quantum logic can be regarded as an abacus logic. Without suggesting “hidden variables” it is finally shown that the Lindenbaum algebra of the theory in the second example is a subalgebra of the abacus logic B of the kind studied in example 1. It turns out that the “classical observables” associated with B and the “quantum observables” associated with quantum logic are not unrelated. The value of a classical observable contains, in coded form, information about the “uncertainty” of a quantum observable. This information is retrieved by decoding the value of the corresponding classical observable.
A note on defining groups in stable structures
Authors: Wagner Frank O.
Published: May 2006

If * is a binary partial function which happens to be a group law on some infinite subset of some model of a stable theory, then this subset can be embedded into a definable group such that * becomes the group operation.
Équivalence élémentaire et isomorphisme des corps de courbe sur un corps algébriquement clos
Authors: Duret Jean-Louis
Published: May 2006

Cet article fait suite à [D] dont il utilise les résultats.

Soit if ℒ langage constitué de deux constantes 0 et 1, et de deux fonctions + et ·; si A est un sous-ensemble d'une structure de ℒ, nous noterons if ℒ (A) le langage obtenu en ajoutant à ℒ if les éléments de A comme constantes.

Tous les corps considérés seront commutatifs. Nous appellerons corps de courbe sur un corps k une extension K de k finiment engendrée de degré de transcendance 1 sur k telle que k soit relativement algébriquement clos dans K.

Nous appellerons ensemble de coefficients d'une courbe sur un corps k un sous-ensemble A de K tel qu'il existe un système de générateurs de l'idéal de cette courbe dont les coefficient sont des éléments de A.

Nous nous proposons d'étudier les conjectures suivantes:

1. Conjecture. Si K est un corps de courbe sur un corps algébriquement clos k, il existe un sous-ensemble fini A de k tel que tout corps de courbe sur kélémentairement équivalent à K dans le langage ℒ (A), lui est k-isomorphe.

2. Conjecture. Deux corps de courbe sur un corps algébriquement clos K élémentairement équivalents dans le langage ℒ sont isomorphes.

Nous démontrerons ces conjectures lorsque le genre est différent de 1, et si le genre est 1, lorsque la caractéristique est nulle et le corps de courbe sans multiplication complexe.

Une version plus simple de cet article est parue dans [D′].
The theory of the recursively enumerable weak truth-table degrees is undecidable
Authors: Ambos-Spies Klaus , Nies André , Shore Richard A.
Published: May 2006

We show that the partial order of -sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.
Saturated ideals and the singular cardinal hypothesis
Authors: Matsubara Yo
Published: May 2006

The large cardinal-like properties of saturated ideals have been investigated by various authors, including Foreman [F], and Jech and Prikry [JP], among others. One of the most interesting consequences of a strongly compact cardinal is the following theorem of Solovay [So2]: if a strongly compact cardinal exists then the singular cardinal hypothesis holds above it. In this paper we discuss the question of relating the existence of saturated ideals and the singular cardinal hypothesis. We will show that the existence of “strongly” saturated ideals implies the singular cardinal hypothesis. As a biproduct we will present a proof of the above mentioned theorem of Solovay using generic ultrapowers. See Jech and Prikry [JP] for a nice exposition of generic ultrapowers. We owe a lot to the work of Foreman [F]. We would like to express our gratitude to Noa Goldring for many helpful comments and discussions.

Throughout this paper we assume that κ is a strongly inaccessible cardinal and λ is a cardinal >κ. By an ideal on κλ we mean a κ-complete fine ideal on Pκλ. For I an ideal on κλ let PI denote the poset of I-positive subsets of κλ.

Definition. Let I be an ideal on κλ. We say that I is a bounding ideal if 1 ⊩-PI “δ(δ is regular cardinal ”.

We can show that if a normal ideal is “strongly” saturated then it is bounding.

Theorem 1. If 1 is an η-saturated normal ideal onκλ, where η is a cardinal <λsuch that there are fewer thanκmany cardinals betweenκand η (i.e. η < κ+κ), then I is bounding.

Proof. Let I be such an ideal on κλ. By the work of Foreman [F] and others, we know that every λ+-saturated normal ideal is precipitous. Suppose G is a generic filter for our PI. Let j: V → M be the corresponding generic elementary embedding. By a theorem of Foreman [F, Lemma 10], we know that Mλ ⊂ M in V[G]. By η-saturation, cofinalities ≥η are preserved; that is, if cfvα ≥ η, then cfvα = cfv[G]α. From j ↾ Vκ being the identity on Vκ and M being λ-closed in V[G], we conclude that cofinalities <κ are preserved. Therefore if cfvα ≠ cfv[G]α then κ ≤ cfvα < η.