bluuebunny/crossref_metadata_2025 huggingface dataset:
Colimit completions and the effective topos
Authors: Robinson Edmund , Rosolini Giuseppe
Published: May 2006

The family of readability toposes, of which the effective topos is the best known, was discovered by Martin Hyland in the late 1970's. Since then these toposes have been used for several purposes. The effective topos itself was originally intended as a category in which various recursion-theoretic or effective constructions would live as natural parts of the higher-order type structure. For example the hereditary effective operators become the higher types over N (Hyland [1982]), and effective domains become the countably-based domains in the topos (McCarty [1984], Rosolini [1986]). However, following the discovery by Moggi and Hyland that it contained nontrivial small complete categories, the effective topos has also been used to provide natural models of polymorphic type theories, up to and including the theory of constructions (Hyland [1987], Hyland, Robinson and Rosolini [1987], Scedrov [1987], Bainbridge et al. [1987]).

Over the years there have also been several different constructions of the topos. The original approach, as in Hyland [1982], was to construct the topos by first giving a notion of Pω-valued set. A Pω-valued set is a set X together with a function =x: X × X → Pω. The elements of X are to be thought of as codes, or as expressions denoting elements of some “real underlying” set in the topos. Given a pair (x,x′) of elements of X, the set =x (x,x′) (generally written ) is the set of codes of proofs that the element denoted by x is equal to the element denoted by x′.
Anneaux p-adiquement clos et anneaux de fonctions définissables
Authors: Bélair Luc
Published: May 2006

Nous considérons des théories d'anneaux locaux reliées aux corps p-adiques, p un nombre premier. Dans le §1 nous établissons les axiomatisations données dans [B1], ainsi qu'une autre axiomatisation des anneaux apparaissant dans [R1]. Il s'agit d'anneaux locaux henséliens dont le corps résiduel est élémentairement équivalent à une extension finie d'un corps p-adique. Nous les appelons anneaux locaux p-adiquement clos. Dans le contexte de [R1] et [B1] ils apparaissent comme fibres du faisceau structural (aussi appelé faisceau de Nash dans [BS]) accompagnant les spectres p-adiques. L'intérêt de nos axiomatisations provient de la simplicité des axiomes qui rendent compte des propriétés henséliennes. Dans le §2 nous donnons une axiomatisation d'une théorie d'anneaux locaux qui apparaît naturellement dans le contexte de la théorie des modèles des corps valués, et se trouve être une complétion d'une théorie du §1. Nous appelons ces anneaux, anneaux intègres p-adiquement clos.

Dans le §3 nous utilisons §2 pour montrer que les anneaux intègres p-adiquement clos apparaissent aussi comme anneaux quotients d'anneaux de fonctions continues définissables sur les courbes affines p-adiques. Nous représentons alors un idéal premier comme le noyau d'un morphisme d'évaluation en un point non-standard de la courbe. Le spectre p-adique fournit un outil commode qui permet de décrire la situation de façon concise.
On generic elementary embeddings
Authors: Gitik Moti
Published: May 2006

Suppose that I is a precipitous ideal over a cardinal κ and j is a generic embedding of I. What is the nature of j? If we assume the existence of a supercompact cardinal then, by Foreman, Magidor and Shelah [FMS], it is quite unclear where some of such j's are coming from. On the other hand, if ¬∃κ0(κ) = κ++, then, by Mitchell [Mi], the restriction of j to the core model is its iterated ultrapower by measures of it. A natural question arising here is if each iterated ultrapower of can be obtained as the restriction of a generic embedding of a precipitous ideal. Notice that there are obvious limitations. Thus the ultrapower of by a measure over λ cannot be obtained as a generic embedding by a precipitous ideal over κ ≠ λ. But if we fix κ and use iterated ultrapowers of which are based on κ, then the answer is positive. Namely a stronger statement is true:

Theorem. Let τ be an ordinal and κ a measurable cardinal. There exists a generic extension V* of V so that NSℵ1 (the nonstationary ideal on ℵ1) is precipitous and, for every iterated ultrapower i of V of length ≤ τ by measures of V based on κ, there exists a stationary set forcing “the generic ultrapower restricted to V is i”.

Our aim will be to prove this theorem. We assume that the reader is familiar with the paper [JMMiP] by Jech, Magidor, Mitchell and Prikry. We shall use the method of that paper for constructing precipitous ideals. Ideas of Levinski [L] for blowing up 2ℵ1 preserving precipitousness and of our own earlier paper [Gi] for linking together indiscernibles will be used also.
Two results on borel orders
Authors: Louveau Alain
Published: May 2006

We prove two results about the embeddability relation between Borel linear orders: For η a countable ordinal, let 2η (resp. 2< η) be the set of sequences of zeros and ones of length η (resp. < η), equipped with the lexicographic ordering. Given a Borel linear order X and a countable ordinal ξ, we prove the following two facts.

(a) Either X can be embedded (in a (X, ξ) way) in 2ωξ or 2ωξ + 1 continuously embeds in X.

(b) Either X can embedded (in a (X, ξ) way) in 2<ωξ or 2ωξ continuously embeds in X. These results extend previous work of Harrington, Shelah and Marker.
Digital simulation of analog computation and Church's thesis
Authors: Rubel Lee A.
Published: May 2006

Church's thesis, that all reasonable definitions of “computability” are equivalent, is not usually thought of in terms of computability by acontinuouscomputer, of which the general-purpose analog computer (GPAC) is a prototype. Here we prove, under a hypothesis of determinism, that the analytic outputs of aC∞GPAC are computable by a digital computer.

In [POE, Theorems 5, 6, 7, and 8], Pour-El obtained some related results. (The proof there of Theorem 7 depends on her Theorem 2, for which the proof in [POE] is incorrect, but for which a correct proof is given in [LIR]. Also, the proof in [POE] of Theorem 8 depends on the unproved assertion that a solution of an algebraic differential equation must be analytic on an open subset of its domain. However, this assertion was later proved in [BRR].) As in [POE], we reduce the problem to a problem about solutions of certain systems of algebraic differential equations (ADE's). If such a system is nonsingular (i.e. if the “separant” does not vanish along the given solution), then the argument is very easy (see [VSD] for an even simpler situation), so that the essential difficulties arise fromsingularsystems. Our main tools in handling these difficulties are drawn from the excellent (and difficult) paper [DEL] by Denef and Lipshitz. The author especially wants to thank Leonard Lipshitz for his kind help in the preparation of the present paper.

We emphasize here that our proof of the simulation result applies only to the GPAC as described below. The GPAC's form a natural subclass of the class of all analog computers, and are based on certain idealized components (“black boxes”), mostly associated with the technology of past decades. One can easily envisage other kinds of black boxes of an input-output character that would lead to different kinds of analog computers. (For example, one could incorporate delays, or spatial integrators in addition to the present temporal integrators, etc.) Whether digital simulation is possible for these “extended” analog computers poses a rich and challenging set of research questions.
A first approach to abstract modal logics
Authors: Font Josep M. , Verdú Ventura
Published: May 2006

The object of this paper is to make a study of four systems of modal logic (S4, S5, and their intuitionistic analogues IM4 and IM5) with the techniques of the theory of abstract logics set up by Suszko, Bloom, Brown, Verdú and others. The abstract concepts corresponding to such systems are defined as generalizations of the logics naturally associated to their algebraic models (topological Boolean or Heyting algebras, general or semisimple). By considering new suitably defined connectives and by distinguishing between having the rule of necessitation only for theorems or as a full inference rule (which amounts to dealing with all filters or with open filters of the algebras) we are able to reduce the study of a modal (abstract) logic L to that of two nonmodal logics L− and L+ associated with L. We find that L is “of IM4 type” if and only if L− and L+ are both intuitionistic and have the same theorems, and logics of type S4, IM5 or S5 are obtained from those of type IM4 simply by making classical L−, L+ or both. We compare this situation with that found in recent approaches to intuitionistic modal logic using birelational models or using higher-level sequent-systems. The treatment of modal systems with abstract logics is rather new, and in our way to it we find several general constructions and results which can also be applied to other modal systems weaker than those we study in detail.
Groups of finite Morley rank with transitive group automorphisms
Authors: Nesin Ali
Published: May 2006

The aim of this short note is to prove the following result:

Theorem. Let G be a group of finite Morley rank with Aut G acting transitively on G/{1}. Then G is either abelian or a bad group.

Bad groups were first defined by Cherlin [Ch]: these are groups of finite Morley rank without solvable and nonnilpotent connected subgroups. They have been investigated by the author [Ne 1], Borovik [Bo], Corredor [Co], and Poizat and Borovik [Bo-Po]. They are not supposed to exist, but we are far from proving their nonexistence. This is one of the major obstacles to proving Cherlin's conjecture: infinite simple groups of finite Morley rank are algebraic groups.

If the group G of the theorem is finite, then it is well known that G ≈ ⊕Zp for some prime p: clearly all elements of G have the same order, say p, a prime. Thus G is a finite p-group, so has a nontrivial center. But Aut G acts transitively; thus G is abelian. Since it has exponent p, G ≈ ⊕Zp.

The same proof for infinite G does not work even if it has finite Morley rank, for the following reasons:

1) G may not contain an element of finite order.

2) Even if G does contain an element of finite order, i.e. if G has exponent p, we do not know if G must have a nontrivial center.
Near-equational and equational systems of logic for partial functions. II
Authors: Craig William
Published: May 2006

For the reader's convenience, we begin Part II by restating the rules for constructing Sq derivations given in §2:

We let R be the set of 14 rules for Sq, R* the set of pure *-rules in R, R≃ the set of pure ≃-rules in R, and R− the set R ∩ − {Exs≃}. The closure of any F ⊆ Sq under R will be denoted by csRF, and the direct image of F under Cut*, for example, by Cut*(F).
Definability in terms of the successor function and the coprimeness predicate in the set of arbitrary integers
Authors: Richard Denis
Published: May 2006

Using coding devices based on a theorem due to Zsigmondy, Birkhoff and Vandiver, we first define in terms of successor S and coprimeness predicate ⊥ a full arithmetic over the set of powers of some fixed prime, then we define in the same terms a restriction of the exponentiation. Hence we prove the main result insuring that all arithmetical relations and functions over prime powers and their opposite are {S, ⊥}-definable over Z. Applications to definability over Z and N are stated as corollaries of the main theorem.
Slow growing versus fast growing
Authors: Wainer S. S.
Published: May 2006

I falsely claimed, as an aside remark in [8] and also implicitly in the abstract [9], that the slow-growing hierarchy

“catches up” with the fast-growing hierarchy

at level Γ0, i.e. that, for all x > 0,

where x′ is some simple (even linear) function of x.

Girard [4] gave the first correct analysis of the deep relationship which exists between G and F, based on his extensive category-theoretic framework for -logic. This analysis indicates that the first point at which G catches up with F is the ordinal of the theory ID<ω(0 of arbitrary finite iterations of an inductive definition. This is very far beyond Γ0! In particular, in order to capture F at level ∣IDn∣ the slow-growing hierarchy must be generated up to ∣IDn+1∣, i.e. one extra iteration of an inductive definition is needed in order to generate sufficient new ordinals.
Ramsey cardinals, α-Erdös cardinals, and the core model
Authors: Schlingmann Dirk R. H.
Published: May 2006

The core model K was introduced by R. B. Jensen and A. J. Dodd [DoJ]. K is the union of Gödel's constructible universe L together with all mice, i.e., , and K is a transitive model of ZFC + (V = K) + GCH (see [DoJ]). V = K is consistent with the existence of Ramsey cardinals [M], and if cf(α) > ω, V = K is consistent with the existence of α-Erdös cardinals [J]. Let K be Ramsey. Then there is a smallest inner model Wκ of ZFC in which κ is Ramsey. We have Wκ ⊨ V = K and Wκ ⊆ K [M]. The existence of Wκ with is equivalent to the existence of a sharplike mouse on N ⊨ K with N ⊨ κ Ramsey. (A mouse N on is called sharplike provided .) We have , where is the mouse iteration of N. N is the oleast mouse not in Wκ (see [J] and [DJKo]). Here < denotes the mouse order. The context always clarifies whether the mouse order or the usual <-relation is meant.

The main result of §1 is that Wκ ⊨ κ is the only Ramsey cardinal. A similar result has been found true in the smallest inner model L[U] of ZFC + “κ is measurable” if U is a normal measure on κ: L[U] ⊨ κ is the only measurable cardinal [Ku].
On analytic filters and prefilters
Authors: Zafrany Samy
Published: May 2006

We show that every analytic filter is generated by a prefilter, every filter is generated by a prefilter, and if is a prefilter then the filter generated by it is also . The last result is unique for the Borel classes, as there is a -complete prefilter P such that the filter generated by it is -complete. Also, no complete coanalytic filter is generated by an analytic prefilter. The proofs use König's infinity lemma, a normal form theorem for monotone analytic sets, and Wadge reductions.
Ultrafilters of character ω1
Authors: Hart Klaas Pieter
Published: May 2006

Using side-by-side Sacks forcing, it is shown that it is consistent that 2ω be large and that there be many types of ultrafilters of character ω1.
Finite extensions and the number of countable models
Authors: Millar Terrence
Published: May 2006

An Ehrenfeucht theory is a complete first order theory with exactly n countable models up to isomorphism, 1 < n < ω. Numerous results have emerged regarding these theories ([1]–[15]). A general question in model theory is whether or not the number of countable models of a complete theory can be different than the number of countable models of a complete consistent extension of the theory by finitely many constant symbols. Examples are known of Ehrenfeucht theories that have complete extensions by finitely many constant symbols such that the extensions fail to be Ehrenfeucht ([4], [8], [13]). These examples are easily modified to allow finite increases in the number of countable models.

This paper contains examples in the other direction—complete theories that have consistent extensions by finitely many constant symbols such that the extensions have fewer countable models. This answers affirmatively a question raised by, among others, Peretyat'kin [8]. The first example will be an Ehrenfeucht theory with exactly four countable models with an extension by a constant symbol that has only three countable models. The second example will be a complete theory that is not Ehrenfeucht, but which has an extension by a constant symbol that is Ehrenfeucht. The notational conventions for this paper are standard.

Peretyat'kin introduced the theory of a dense binary branching tree with a meet operator [7]. Dense ω-branching trees have also proven useful [5], [11]. Both of the Theories that will be constructed make use of dense ω-branching trees.
Relative recursive enumerability of generic degrees
Authors: Kumabe Masahiro
Published: May 2006

Let ω be the set of natural numbers, i.e. {0, 1, 2, 3, …}. A string is a mapping from an initial segment of ω into {0, 1}. We identify a set A ≤ ω with its characteristic function. A set A ≤ ω is called n-generic if it is Cohen-generic for n-quantifier arithmetic. This is equivalent to saying that for every set of strings S, there is a σ < A such that σ ∈ S or (∀ν ≥ σ)(ν ∉ S). By degree we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. For a degree a, D(≤ a) denotes the set of degrees recursive in a.

The relation between generic degrees and minimal degrees has been widely studied. Spector [9] proved the existence of minimal degrees. Shoenfield [8] simplified the proof by using trees. In the construction of a minimal degree, given σ we extend σ to ν so that ν is in the (splitting or nonsplitting) subtree of a given tree. But in the construction of a generic set, given σ we extend σ to ν to meet the given dense set. So these two constructions are quite different. Jockusch [5] showed that any 2-generic degree bounds no minimal degree. Chong and Jockusch [3] showed that any 1-generic degree below 0′ bounds no minimal degree.
Uniqueness of normal proofs of minimal formulas
Authors: Tatsuta Makoto
Published: May 2006

A minimal formula is a formula which is minimal in provable formulas with respect to the substitution relation. This paper shows the following: (1) A β-normal proof of a minimal formula of depth 2 is unique in NJ. (2) There exists a minimal formula of depth 3 whose βη-normal proof is not unique in NJ. (3) There exists a minimal formula of depth 3 whose βη-normal proof is not unique in NK.
-stability
Authors: Ben-Arié Dror , Judah Haim
Published: May 2006

We investigate the connection between -stability for random and Cohen forcing notions and the measurability and categoricity of the -sets. We show that Shelah's model for -measurability and categoricity satisfies -random-stability while it does not satisfy -Cohen-stability. This gives an example of measure-category asymmetry. We also present a result concerning finite support iterations of Suslin forcing.
Counting the maximal intermediate constructive logics
Authors: Ferrari Mauro , Miglioli Pierangelo
Published: May 2006

A proof is given that the set of maximal intermediate propositional logics with the disjunction property and the set of maximal intermediate predicate logics with the disjunction property and the explicit definability property have the power of continuum. To prove our results, we introduce various notions which might be interesting by themselves. In particular, we illustrate a method to generate wide sets of pairwise “constructively incompatible constructive logics”. We use a notion of “semiconstructive” logic and define wide sets of “constructive” logics by representing the “constructive” logics as “limits” of decreasing sequences of “semiconstructive” logics. Also, we introduce some generalizations of the usual filtration techniques for propositional logics. For instance, “fitrations over rank formulas” are used to show that any two different logics belonging to a suitable uncountable set of “constructive” logics are “constructively incompatible”.
Learning via queries in [+, <]
Authors: Gasarch William I. , Pleszkoch Mark G. , Solovay Robert
Published: May 2006

We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols [+ , <]. The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in [+, <]. Additionally, we resolve an open question in [7] about passive versus active learning.
Automorphism properties of stationary logic
Authors: Otto Martin
Published: May 2006

By means of an Ehrenfeucht-Mostowski construction we obtain an automorphism theorem for a syntactically characterized class of Laa-theories comprising in particular the finitely determinate ones. Examples of Laa-theories with only rigid models show this result to be optimal with respect to a classification in terms of prenex quantifier type: Rigidity is seen to hinge on quantification of type … ∀ … stat … permitting of the parametrization of families of disjoint stationary systems by the elements of the universe.
Extending the first-order theory of combinators with self-referential truth
Authors: Cantini Andrea
Published: May 2006

The aim of this paper is to introduce a formal system STW of self-referential truth, which extends the classical first-order theory of pure combinators with a truth predicate and certain approximation axioms. STW naturally embodies the mechanisms of generalpredicate application/abstractionona par withfunction application/abstraction; in addition, it allows non-trivial constructions, inspired by generalized recursion theory. As a consequence, STW provides a smooth inner model for Myhill's systems with levels of implication.
Theory contraction and base contraction unified
Authors: Hansson Sven Ove
Published: May 2006

One way to construct a contraction operator for a theory (belief set) is to assign to it a base (belief base) and an operator of partial meet contraction for that base. Axiomatic characterizations are given of the theory contractions that are generated in this way by (various types of) partial meet base contractions.
The number of proofs for a BCK-formula
Authors: Komori Yuichi , Hirokawa Sachio
Published: May 2006

In this note, we give a necessary and sufficient condition for a BCK-formula to have the unique normal form proof.

We call implicational propositional formulas formulas for short. BCK-formulas are the formulas which are derivable from axioms B = (a → b) → (c → a) → c → b, C = (a→b→c)→b→a→c, and K = a→b→a by substitution and modus ponens. It is known that the property of being a BCK-formula is decidable (Jaskowski [11, Theorem 6.5], Ben-Yelles [3, Chapter 3, Theorem 3.22], Komori [12, Corollary 6]). The set of BCK-formulas is identical to the set of provable formulas in the natural deduction system with the following two inference rules.

Here γ occurs at most once in (→I). By the formulae-as-types correspondence [10], this set is identical to the set of type-schemes of closed BCK-λ-terms. (See [5].) A BCK-λ-term is a λ-term in which no variable occurs twice. Basic notion concerning the type assignment system can be found [4]. Uniqueness of normal form proofs has been known for balanced formulas. (See [2,14].) It is related to the coherence theorem in cartesian closed categories. A formula is balanced when no variable occurs more than twice in it. It was shown in [8] that the proofs of balanced formulas are BCK-proofs. Relevantly balanced formulas were defined in [9], and it was proved that such formulas have unique normal form proofs. Balanced formulas are included in the set of relevantly balanced formulas.
Bounds for the closure ordinals of essentially monotonic increasing functions
Authors: Weiermann Andreas
Published: May 2006

Let Ω ≔ ℵ1. For any α< εΩ + 1 ≔ min {ξ > Ω: ξ = ωξ} let EΩ(α) be the finite set of ε-numbers below Ω which are needed for the unique representation of α in Cantor-normal form using 0, Ω, +, and ω. Let α* ≔ max(EΩ(α) ∪ {0}). A function f: εΩ + 1 → Ω is called essentially increasing, if for any α < εΩ + 1; f(α) ≥ α*: f is called essentially monotonic, if for any α, β<εΩ + 1;

Let be the least set of ordinals which contains 0 as an element and which satisfies the following two conditions:

(a)

(b)

Let be the Howard-Bachmann ordinal, which is, for example, defined in [3]. The following theorem is shown: If f: εΩ + 1 → Ω is essentially monotonic and essentially increasing, then the order type of is less than or equal to .
À propos d'équations génériques
Authors: Wagner Frank O.
Published: May 2006

We prove that a stable solvable group G which satisfies xn = 1 generically is of finite exponent dividing some power of n. Furthermore, G is nilpotent-by-finile.

A second result is that in a stable group of finite exponent, involutions either have big centralisers, or invert a subgroup of finite index (which hence has to be abelian).
The modal logic of inequality
Authors: de Rijke Maarten
Published: May 2006

We consider some modal languages with a modal operator D whose semantics is based on the relation of inequality. Basic logical properties such as definability, expressive power and completeness are studied. Also, some connections with a number of other recent proposals to extend the standard modal language are pointed at.
Constructive set theoretic models of typed combinatory logic
Authors: Knobel Andreas
Published: May 2006

We shall present two novel ways of deriving simply typed combinatory models. These are of interest in a constructive setting. First we look at extension models, which are certain subalgebras of full function space models. Then we shall show how the space of singletons of a combinatory model can itself be made into one. The two and the algebras in between will have many common features. We use these two constructions in proving:

There is a model of constructive set theory in which every closed extensional theory of simply typed combinatory logic is the theory of a full function space model.
Effective bounds from ineffective proofs in analysis: An application of functional interpretation and majorization
Authors: Kohlenbach Ulrich
Published: May 2006

We show how to extract effective bounds Φ for ⋀u1⋀v ≤ytu⋁wηG0-sentences which depend on u only (i.e. ⋀u⋀v ≤y, tu⋁w ≤η ΦuG0) from arithmetical proofs which use analytical assumptions of the form

(ϒ, δ, ρ, and τ are arbitrary finite types, η ≤ 2, G0 and F0 are quantifier-free, and s and t are closed terms). If τ ≤ 2, (*) can be weakened to

This is used to establish new conservation results about weak Konig's lemma. Applications to proofs in classical analysis, especially uniqueness proofs in approximation theory, will be given in subsequent papers.
Relational proof system for relevant logics
Authors: Orlowska Ewa
Published: May 2006

A method is presented for constructing natural deduction-style systems for propositional relevant logics. The method consists in first translating formulas of relevant logics into ternary relations, and then defining deduction rules for a corresponding logic of ternary relations. Proof systems of that form are given for various relevant logics. A class of algebras of ternary relations is introduced that provides a relation-algebraic semantics for relevant logics.
Normality of a filter over a space of partitions
Authors: Fuller Mark
Published: May 2006

In this paper we investigate the closure of certain filters under different definitions of diagonal intersection. The space of partitions over which filters concern us is Qκ(λ), the set of partitions of λ into fewer than κ pieces, invented by Henle and Zwicker [4] in the spirit of Pκ(λ). Various notions of normality for filters over Qκ(λ) have been introduced in [4] and [7]. Our objective is to find a notion of normality in terms of a tractable diagonal intersection which also in some sense reflects the construction of a partition. Extending the parallels between Pκ(λ) and Qκ(λ) we define two diagonal intersections, Δ1 and Δ2, under which the club filter is closed.
The genericity conjecture
Authors: Friedman Sy D.
Published: May 2006

The Genericity Conjecture, as stated in Beller-Jensen-Welch [1], is the following:

(*) If O# ∉ L[R], R ⊆ ω, then R is generic over L.

We must be precise about what is meant by “generic”.

Definition (Stated in Class Theory). A generic extension of an inner model M is an inner model M[G] such that for some forcing notion ⊆ M:

(a) 〈M, 〉 is amenable and ⊩ is 〈M, 〉-definable for sentences.

(b) G ⊆ is compatible, closed upwards, and intersects every 〈M, 〉-definable dense D ⊆ .

A set x is generic over M if it is an element of a generic extension of M. And x is strictly generic over M if M[x] is a generic extension of M.

Though the above definition quantifies over classes, in the special case where M = L and O# exists, these notions are in fact first order, as all L-amenable classes are definable over L[O#]. From now on assume that O# exists.

Theorem A. The Genericity Conjecture is false.

The proof is based upon the fact that every real generic over L obeys a certain definability property, expressed as follows.

Fact. If R is generic over L, then for some L-amenable class A, Sat〈L, A〉 is not definable over 〈L[R],A〉, where Sat〈L,A〉 is the canonical satisfaction predicate for 〈L,A〉.
The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility
Authors: Lempp Steffen , Lerman Manuel
Published: May 2006

We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.
Independence and consistency proofs in quadratic form theory
Authors: Baumgartner James E. , Spinas Otmar
Published: May 2006

We consider the following properties of uncountable-dimensional quadratic spaces (E, Φ):

(*) For all subspaces U ⊆ E of infinite dimension: dim U˔ < dim E.

(**) For all subspaces U ⊆ E of infinite dimension: dim U˔ < ℵ0.

Spaces of countable dimension are the orthogonal sum of straight lines and planes, so they cannot have (*), but (**) is trivially satisfied.

These properties have been considered first in [G/O] in the process of investigating the orthogonal group of quadratic spaces. It has been shown there (in ZFC) that over arbitrary uncountable fields (**)-spaces of uncountable dimension exist.

In [B/G], (**)-spaces of dimension ℵ1 (so (*) = (**)) have been constructed over arbitrary finite or countable fields. But this could be done only under the assumption that the continuum hypothesis (CH) holds in the underlying set theory.
Type reducing correspondences and well-orderings: Frege's and Zermelo's constructions re-examined
Authors: Bell J. L.
Published: May 2006

A key idea in both Frege's development of arithmetic in theGrundlagen[7] and Zermelo's 1904 proof [10] of the well-ordering theorem is that of a “type reducing” correspondence between second-level and first-level entities. In Frege's construction, the correspondence obtains betweenconceptandnumber, in Zermelo's (through the axiom of choice), betweensetandmember. In this paper, a formulation is given and a detailed investigation undertaken of a system ℱ of many-sorted first-order logic (first outlined in the Appendix to [6]) in which this notion of type reducing correspondence is accorded a central role and which enables Frege's and Zermelo's constructions to be presented in such a way as to reveal their essential similarity. By adapting Bourbaki's version of Zermelo's proof of the well-ordering theorem, we show that, within ℱ, any correspondencecbetween second-level entities (here calledconcepts) and first-level ones (here calledobjects) induces a well-ordering relationW(c) in a canonical manner. We shall see that, whencis the “Fregean” correspondence between concepts and cardinal numbers,W(c) is (the well-ordering of) the ordinalω+ 1, and whencis a “Zermelian” choice function on concepts,W(c) is a well-ordering of the universal concept embracing all objects.

In ℱ an important role is played by the notion ofextensionof a concept. To each conceptXwe assume there is assigned an objecte(X) in such a way that, for any conceptsX, Ysatisfying a certain predicateE, we havee(X) =e(Y) iff the same objects fall underXandY.
Remarks on Galois cohomology and definability
Authors: Pillay Anand
Published: May 2006

In this paper we develop some basic features of Galois cohomology, specifically the connection between first Galois cohomology groups and principal homogeneous spaces, in a model-theoretic context. “Descent theory” also fits into our approach.

The model theory involved is elementary, and the reader is referred to [2]. It should be said that we make crucial use of Meq in our analysis. The reader is also referred to Poizat's seminal paper “Une theorie de Galois imaginaire” ([6]). Although our results do not depend on Poizat's work, it is in his paper that the model-theoretic context is suggested for a generalised treatment of Galois theory.

Nothing in this paper is particularly deep. We are concerned mainly with translating between the Galois cohomological language and the language of definable sets and definable families of definable sets. We will introduce (in a suitable context) the notion of a definable cocycle (from an automorphism group to a definable group G). The (classical) situation of profinite and continuous cocycles will be a special case. Kolchin's theory of constrained cohomology will be another special case, and our results yield a substantially simpler proof of his Theorem 5 from Chapter VII of [4]. In any case model-theorists will see that definable cocycles correspond to objects with which they are already quite familiar—commuting families of definable bijections.
Complete representations in algebraic logic
Authors: Hirsch Robin , Hodkinson Ian
Published: May 2006

A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.
The forth part of the back and forth map in countable homogeneous structures
Authors: McLeish S. J.
Published: May 2006

The model theoretic ‘back and forth’ construction of isomorphisms and automorphisms is based on the proof by Cantor that the theory of dense linear orderings without endpoints is ℵ0-categorical. However, Cantor's method is slightly different and for many other structures it yields an injection which is not surjective. The purpose here is to examine Cantor's method (here called ‘going forth’) and to determine when it works and when it fails. Partial answers to this question are found, extending those earlier given by Cameron. We also give fuller characterisations of when forth suffices for model theoretic classes such as structures containing Jordan sets for the automorphism group, and ℵ0-categorical ω-stable structures. The work is based on the author's Ph.D. thesis.
The expressive power of fixed-point logic with counting
Authors: Otto Martin
Published: May 2006

We study the expressive power in the finite of the logic Fixed-Point+Counting, the extension of first-order logic which is obtained through adding both the fixed-point constructor and the ability to count.

To this end an isomorphism preserving (‘generic’) model of computation is introduced whose PTime restriction exactly corresponds to this level of expressive power, while its PSpace restriction corresponds to While+Counting. From this model we obtain a normal form which shows a rather clear separation of the relational vs. the arithmetical side of the algorithms involved.

In parallel, we study the relations of Fixed-Point+Counting with the infinitary logicsand the corresponding pebble games.

The main result, however, involves the concept of anarithmetical invariant. By this we mean a functor taking every finite relational structure to an expansion of (an initial segment of) the standard arithmetical structure. In particular its values are linearly ordered structures. We establish the existence of a family of arithmetical invariantswith the following properties:

• The invariants themselves can be evaluated in polynomial time.

• A class of finite relational structures is definable in Fixed-Point+Counting if and only if membership can be decided in polynomial time on the basis of the values of one of the invariants.

• The invariantrclassifies all finite relational structures exactly up to equivalence with respect to the logic

We also give a characterization of Fixed-Point+Counting in terms of sequences of formulae in the: It corresponds exactly to the polynomial time computable families (φn)n∈ωin these logics.

Towards a positive assessment of the expressive power of Fixed-Point+Counting, it is shown that the natural extension of fixed-point logic by Lindström quantifiers, which capture all the PTime computable properties of cardinalities of definable predicates, is strictly weaker than what we get here. This implies in particular that every extension of fixed-point logic by means of monadic Lindström quantifiers, which stays within PTime, must be strictly contained in Fixed-Point+Counting.
Existentially closed models via constructible sets: There are 2ℵ0 existentially closed pairwise non elementarily equivalent existentially closed ordered groups
Authors: Khelif Anatole
Published: May 2006

We prove that there are 2χ0 pairwise non elementarily equivalent existentially closed ordered groups, which solve the main open problem in this area (cf. [3, 10]).

A simple direct proof is given of the weaker fact that the theory of ordered groups has no model companion; the case of the ordered division rings over a field k is also investigated.

Our main result uses constructible sets and can be put in an abstract general framework.

Comparison with the standard methods which use forcing (cf. [4]) is sketched.
On atomic or saturated sets
Authors: Newelski Ludomir
Published: May 2006

Assume T is stable, small and Φ(x) is a formula of L(T). We study the impact on T⌈Φ of naming finitely many elements of a model of T. We consider the cases of T⌈Φ which is ω-stable or superstable of finite rank. In these cases we prove that if T has countable models and Q = Φ(M) is countable and atomic or saturated, then any good type in S(Q) is τ-stable. If T⌈Φ is ω-stable and (bounded, 1-based or of finite rank) with , then we prove that every good p ∈ S(Q) is τ-stable for any countable Q. The proofs of these results lead to several new properties of small stable theories, particularly of types of finite weight in such theories.
Zorn's lemma and complete Boolean algebras in intuitionistic type theories
Authors: Bell J. L.
Published: May 2006

We analyze Zorn's Lemma and some of its consequences for Boolean algebras in a constructive setting. We show that Zorn's Lemma is persistent in the sense that, if it holds in the underlying set theory, in a properly stated form it continues to hold in all intuitionistic type theories of a certain natural kind. (Observe that the axiom of choice cannot be persistent in this sense since it implies the law of excluded middle.) We also establish the persistence of some familiar results in the theory of (complete) Boolean algebras—notably, the proposition that every complete Boolean algebra is an absolute subretract. This (almost) resolves a question of Banaschewski and Bhutani as to whether the Sikorski extension theorem for Boolean algebras is persistent.
Simple forcing notions and forcing axioms
Authors: Rosłanowski Andrzej , Shelah Saharon
Published: May 2006

In the present paper we are interested in simple forcing notions and Forcing Axioms. A starting point for our investigations was the article [4] in which several problems were posed. We answer some of those problems here.

In the first section we deal with the problem of adding Cohen reals by simple forcing notions. Here we interpret simple as of small size. We try to establish as weak as possible versions of Martin Axiom sufficient to conclude that some forcing notions of size less than the continuum add a Cohen real. For example we show that MA(σ-centered) is enough to cause that every small σ-linked forcing notion adds a Cohen real (see Theorem 1.2) and MA(Cohen) implies that every small forcing notion adding an unbounded real adds a Cohen real (see Theorem 1.6). A new almost ωω-bounding σ-centered forcing notion ℚ⊚ appears naturally here. This forcing notion is responsible for adding unbounded reals in this sense, that MA(ℚ⊚) implies that every small forcing notion adding a new real adds an unbounded real (see Theorem 1.13).

In the second section we are interested in Anti-Martin Axioms for simple forcing notions. Here we interpret simple as nicely definable. Our aim is to show the consistency of AMA for as large as possible class of ccc forcing notions with large continuum. It has been known that AMA(ccc) implies CH, but it has been (rightly) expected that restrictions to regular (simple) forcing notions might help.
On first-order theories with provability operator
Authors: Artëmov Sergei , Montagna Franco
Published: May 2006

In this paper the modal operator “x is provable in Peano Arithmetic” is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.
The consistency strength of an infinitary Ramsey property
Authors: Kafkoulis George
Published: May 2006

In this paper we study the consistency strength of the theory

and we prove the consistency of this theory relative to the consistency of the existence of a supercompact cardinal and an inaccessible above it.
Effective versions of Ramsey's Theorem: Avoiding the cone above 0′
Authors: Hummel Tamara Lakins
Published: May 2006

Ramsey's Theorem states that if P is a partition of [ω]k into finitely many partition classes, then there exists an infinite set of natural numbers which is homogeneous for P. We consider the degrees of unsolvability and arithmetical definability properties of infinite homogeneous sets for recursive partitions. We give Jockusch's proof of Seetapun's recent theorem that for all recursive partitions of [ω]2 into finitely many pieces, there exists an infinite homogeneous set A such that ∅′ ≰TA. Two technical extensions of this result are given, establishing arithmetical bounds for such a set A. Applications to reverse mathematics and introreducible sets are discussed.
Defining multiplication in o-minimal expansions of the additive reals
Authors: Poston Robert J.
Published: May 2006

This paper considers o-minimal expansions of the structure —the ordered additive reals. More particularly we consider the case when the expansions are “eventually nonlinear” (see below), and find that multiplication is actually definable in all cases except when the structure is “eventually almost linear”, which is a rare special case in which multiplication is obviously not definable. Thus the main theorem established is:

Theorem 1.1. For an o-minimal expansion of , if is eventually non-almost-linear then multiplication is definable in.

(A structure is eventually almost linear iff every definable function f is of the form f(x) = λx + c + ε(x) on some interval (K, ∞), where λ, c Є ℝ and ε is a function of x which tends to 0 faster than any negative power of x as x → +∞. Otherwise, i.e. if there is a definable function which is not of this form, it is eventually non-almost-linear.)

This is proved in §4.1, after §§2 and 3 have established technology concerning the rate of growth of functions and approximating derivatives.

In §4.2 an analogy is made with the result of exponentiation being definable in a polynomially unbounded o-minimal expansion of ℝ as an ordered field (see [Mi]). In fact, by means of the isomorphism x ↦ ln(x) we see that Theorem 1.1 also implies this latter result.

Unless otherwise stated, all structures considered in the paper have ℝ as their universe and all functions are real functions.
A recursive nonstandard model of normal open induction
Authors: Berarducci Alessandro , Otero Margarita
Published: May 2006

Models of normal open induction are those normal discretely ordered rings whose nonnegative part satisfy Peano's axioms for open formulas in the language of ordered semirings. (Where normal means integrally closed in its fraction field.)

In 1964 Shepherdson gave a recursive nonstandard model of open induction. His model is not normal and does not have any infinite prime elements.

In this paper we present a recursive nonstandard model of normal open induction with an unbounded set of infinite prime elements.
Martin's axiom and the continuum
Authors: Judah Haim , Rosłanowski Andrzej
Published: May 2006

Since Georg Cantor discovered set theory the main problem in this area of mathematical research has been to discover what is the size of the continuum. The continuum hypothesis (CH) says that every infinite set of reals either has the same cardinality as the set of all reals or has the cardinality of the set of natural numbers, namely

In 1939 Kurt Gödel discovered the Constructible Universe and proved that CH holds in it. In the early sixties Paul Cohen proved that every universe of set theory can be extended to a bigger universe of set theory where CH fails. Moreover, given any reasonable cardinal κ, it is possible to build a model where the continuum size is κ. The new technique discovered by Cohen is called forcing and is being used successfully in other branches of mathematics (analysis, algebra, graph theory, etc.).

In the light of these two stupendous works the experts (especially the platonists) were forced to conclude that from the point of view of the classical axiomatization of set theory (called ZFC) it is impossible to give any answer to the continuum size problem: everything is possible!

In private communications Gödel suggested that the continuum size from a platonistic point of view should be ω2, the second uncountable cardinal. As this is not provable in ZFC, Gödel suggested that a new axiom should be added to ZFC to decide that the cardinality of the continuum is ω2.
Anneaux de fonctions p-adiques
Authors: Bélair Luc
Published: May 2006

We study first-order properties of the quotient rings (V)/ by a prime ideal where (V) is the ring of p-adic valued continuous definable functions on some affine p-adic variety V. We show that they are integrally closed Henselian local rings, with a p-adically closed residue field and field of fractions, and they are not valuation rings in general but always satisfy ∀ x, y(x∣y2 ∨ y∣x2).
The decidability of dependency in intuitionistic propositional logic
Authors: de Jongh Dick , Chagrova L. A.
Published: May 2006

A definition is given for formulae A1, …, An in some theory T which is formalized in a propositional calculus S to be (in)dependent with respect to S. It is shown that, for intuitionistic propositional logic IPC, dependency (with respect to IPC itself) is decidable. This is an almost immediate consequence of Pitts’ uniform interpolation theorem for IPC. A reasonably simple infinite sequence of IPC-formulae Fn (p, q) is given such that IPC-formulae A and B are dependent if and only if at least on of the Fn (A, B) is provable.
The isomorphism property for nonstandard universes
Authors: Schmerl James H.
Published: May 2006

The κ-isomorphism property (IPκ) for nonstandard universes was introduced by Henson in [4]. There has been some recent effort aimed at more fully understanding this property. Jin and Shelah in [7] have shown that for κ < ⊐ω, IPκ is equivalent to what we will refer to as the κ-resplendence property. Earlier, in [6], Jin asked if IPκ is equivalent to IPℵ0 plus κ-saturation. He answered this question positively for κ = ℵ1. In this note we extend this answer to all κ. We also extend the result of Jin and Shelah to all κ. (Jin also observed this could be done.)

In order to strike a balance between the generalities of model theory and the specifics of nonstandard analysis, we will consider models of Zermelo set theory with the Axiom of Choice; we denote this theory by ZC. The axioms of ZC are just those of ZFC but without the replacement scheme. Thus, among the axioms of ZC are the power set axiom, the infinity axiom, the separation axioms and the axiom of choice.

Let(V, E) ⊨ ZC. If a ∈ V, we let *a = {x ∈ V: (V,E) ⊨ x ∈ a}. In particular, i ∈ *ω iff i ∈ V and (V,E) ⊨ (i is a natural number). A subset A ⊆ V is internal if A = *a for some a ∈ V.

The standard model of ZC consists of those sets of rank at most ω + ω. In other words, if we let V0 be the set of hereditarily finite sets and for n < ω, then (Vω, ∈) is the standard model of ZC, where Vω = ⋃n<ω. Vn.