bluuebunny/crossref_metadata_2025 huggingface dataset:
On the angular component map modulo P
Authors: Pas Johan
Published: May 2006

In [10] we introduced a new first order language for valued fields. This language has three sorts of variables, namely variables for elements of the valued field, variables for elements of the residue field and variables for elements of the value group. contains symbols for the standard field, residue field, and value group operations and a function symbol for the valuation. Essential in our language is a function symbol for an angular component map modulo P, which is a map from the field to the residue field (see Definition 1.2).

For this language we proved a quantifier elimination theorem for Henselian valued fields of equicharacteristic zero which possess such an angular component map modulo P [10, Theorem 4.1]. In the first section of this paper we give some partial results on the existence of an angular component map modulo P on an arbitrary valued field.

By applying the above quantifier elimination theorem to ultraproducts ΠQp/D, we obtained a quantifier elimination, in the language , for the p-adic field Qp; and this elimination is uniform for almost all primes p [10, Corollary 4.3]. In §2 we prove that our language is essentially stronger than the natural language for p-adic fields in the sense that the angular component map modulo P cannot be defined, uniformly for almost all p, in terms of the natural language for p-adic fields.
Rich models
Authors: Albert Michael H. , Grossberg Rami P.
Published: May 2006

We define a rich model to be one which contains a proper elementary substructure isomorphic to itself. Existence, nonstructure, and categoricity theorems for rich models are proved. A theory T which has fewer than min(2λ, ℶ2) rich models of cardinality λ (λ > ∣T∣) is totally transcendental. We show that a countable theory with a unique rich model in some uncountable cardinal is categorical in ℵ1 and also has a unique countable rich model. We also consider a stronger notion of richness, and use it to characterize superstable theories.
Backwards easton forcing and 0#
Authors: Stanley M. C.
Published: May 2006

It is shown that if κ is an uncountable successor cardinal in L[0#], then there is a normal tree T ϵ L[0#] of height κ such that 0# ∉ L[T], yet T is < κ-distributive in L[0#]. A proper class version of this theorem yields an analogous L[0#]-definable tree such that distinct branches in the presence of 0# collapse the universe. A heretofore unutilized method for constructing in L[0#] generic objects for certain L-definable forcings and “exotic sequences”, combinatorial principles introduced by C. Gray, are used in constructing these trees.
1-genericity in the enumeration degrees
Authors: Copestake Kate
Published: May 2006

The structure of the Turing degrees of generic and n-generic sets has been studied fairly extensively, especially for n = 1 and n = 2. The original formulation of 1-generic set in terms of recursively enumerable sets of strings is due to D. Posner [11], and much work has since been done, particularly by C. G. Jockusch and C. T. Chong (see [5] and [6]).

In the enumeration degrees (see definition below), attention has previously been restricted to generic sets and functions. J. Case used genericity for many of the results in his thesis [1]. In this paper we develop a notion of 1-generic partial function, and study the structure and characteristics of such functions in the enumeration degrees. We find that the e-degree of a 1-generic function is quasi-minimal. However, there are no e-degrees minimal in the 1-generic e-degrees, since if a 1-generic function is recursively split into finitely or infinitely many parts the resulting functions are e-independent (in the sense defined by K. McEvoy [8]) and 1-generic. This result also shows that any recursively enumerable partial ordering can be embedded below any 1-generic degree.

Many results in the Turing degrees have direct parallels in the enumeration degrees. Applying the minimal Turing degree construction to the partial degrees (the e-degrees of partial functions) produces a total partial degree ae which is minimal-like; that is, all functions in degrees below ae have partial recursive extensions.
Coinductive formulas and a many-sorted interpolation theorem
Authors: Gropp Ursula
Published: May 2006

We use connections between conjunctive game formulas and the theory of inductive definitions to define the notions of a coinductive formula and its approximations. Corresponding to the theory of conjunctive game formulas we develop a theory of coinductive formulas, including a covering theorem and a normal form theorem for many sorted languages. Applying both theorems and the results on “model interpolation” obtained in this paper, we prove a many-sorted interpolation theorem for ω1ω-logic, which considers interpolation with respect to the language symbols, the quantifiers, the identity, and countably infinite conjunction and disjunction.
Some results on higher Suslin trees
Authors: David R.
Published: May 2006

Higher Suslin trees have become a tool in some forcing constructions in set theory (see, for example, [D1] and [D2]). Most of the constructions using ω1 Suslin trees can be extended to κ+ Suslin trees for any regular cardinal κ. Some of these are given in §1.

In many such constructions, sequences of Suslin trees are used. In §II we show, in various ways, that the generalization to sequences, even ω-sequences, of κ+ Suslin trees cannot be done.

In these constructions the Suslin trees are used as forcing poset (the forcing adds a branch in the tree). There is another way to kill a Suslin tree, namely by adding a big antichain. Some results on this forcing are given in §III.

Our notation is standard. If T is a tree and x ∈ T, then ∣x∣ is the height of x in T. We define Tα (or T(α)) = {x ∈ T: ∣x∣ = α} and T∣α = {x ∈ T: ∣x∣ < α}.

If p and q are forcing conditions, p ≤ q means that p has more information than q.

If (Tα: α ∈ I) is a sequence of trees, Π Tα will always mean the set of (xα: α ∈ I) such that xα ∈ Tα and ∣xα∣ = ∣xβ∣ for α, β ∈ I.

For functions b, T,… we denote by b ∣α, T∣ α,… their restriction to α.

If x is a sequence of ordinals and α is an ordinal, x∧α is the sequence obtained by concatenating α at the end of x.
The spectrum of resplendency
Authors: Baldwin John T.
Published: May 2006

Let T be a complete countable first order theory and λ an uncountable cardinal. Theorem 1. If T is not superstable, T has 2λ resplendent models of power λ. Theorem 2. If T is strictly superstable, then T has at least min(2λ, ℶ2) resplendent models of power λ. Theorem 3. If T is not superstable or is small and strictly superstable, then every resplendent homogeneous model of T is saturated. Theorem 4 (with Knight). For each μ ∈ ω ∪ {ω, 2ω} there is a recursive theory in a finite language which has μ resplendent models of power κ for every infinite κ.
Finite support iteration and strong measure zero sets
Authors: Pawlikowski Janusz
Published: May 2006

Any finite support iteration of posets with precalibre ℵ1 which has the length of cofinahty greater than ω1 yields a model for the dual Borel conjecture in which the real line is covered by ℵ1 strong measure zero sets.
Extended ultrapowers and the Vopěnka-Hrbáček theorem without choice
Authors: Spector Mitchell
Published: May 2006

We generalize the ultrapower in a way suitable for choiceless set theory. Given an ultrafilter, forcing is used to construct an extended ultrapower of the universe, designed so that the fundamental theorem of ultrapowers holds even in the absence of the axiom of choice. If, in addition, we assume DC, then an extended ultrapower of the universe by a countably complete ultrafilter must be well-founded. As an application, we prove the Vopěnka-Hrbáček theorem from ZF + DC only (the proof of Vopěnka and Hrbáček used the full axiom of choice): if there exists a strongly compact cardinal, then the universe is not constructible from a set. The same method shows that, in L[2ω], there cannot exist a θ-compact cardinal less than θ (where θ is the least cardinal onto which the continuum cannot be mapped); a similar result can be proven for other models of the form L[A]. The result for L[2ω] is of particular interest in connection with the axiom of determinacy. The extended ultrapower construction of this paper is an improved version of the author's earlier pseudo-ultrapower method, making use of forcing rather than the omitting types theorem.
Extensions of arithmetic for proving termination of computations
Authors: Kent Clement F. , Hodgson Bernard R.
Published: May 2006

Kirby and Paris have exhibited combinatorial algorithms whose computations always terminate, but for which termination is not provable in elementary arithmetic. However, termination of these computations can be proved by adding an axiom first introduced by Goodstein in 1944. Our purpose is to investigate this axiom of Goodstein, and some of its variants, and to show that these are potentially adequate to prove termination of computations of a wide class of algorithms. We prove that many variations of Goodstein's axiom are equivalent, over elementary arithmetic, and contrast these results with those recently obtained for Kruskal's theorem.
Propositional proof systems, the consistency of first order theories and the complexity of computations
Authors: Krajíček Jan , Pudlák Pavel
Published: May 2006

We consider the problem about the length of proofs of the sentences saying that there is no proof of contradiction in S whose length is < n. We show the relation of this problem to some problems about propositional proof systems.
Time polynomial in input or output
Authors: Gurevich Yuri , Shelah Saharon
Published: May 2006

We introduce the class PIO of functions computable in time that is polynomial in max {the length of input, the length of output}, observe that there is no notation system for total PIO functions but there are notation systems for partial PIO functions, and give an algebra of partial PIO functions from binary strings to binary strings.
Random models and the Maslov class
Authors: Goldfarb Warren
Published: May 2006

In [GS] Gurevich and Shelah introduce a novel method for proving that every satisfiable formula in the Gödel class has a finite model (the Gödel class is the class of prenex formulas of pure quantification theory with prefixes ∀∀∃ … ∃). They dub their method “random models”: it proceeds by delineating, given any F in the Gödel class and any integer p, a set of structures for F with universe {1, …, p} that can be treated as a finite probability space S. They then show how to calculate an upper bound on the probability that a structure chosen at random from S makes F false; from this bound they are able to infer that if p is sufficiently large, that probability will be less than one, so that there will exist a structure in S that is a model for F. The Gurevich-Shelah proof is somewhat simpler than those known heretofore. In particular, there is no need for the combinatorial partitionings of finite universes that play a central role in the earlier proofs (see [G] and [DG, p. 86]). To be sure, Gurevich and Shelah obtain a larger bound on the size of the finite models, but this is relatively unimportant, since searching for finite models is not the most efficient method to decide satisfiability.

Gurevich and Shelah note that the random model method can be used to treat the Gödel class extended by initial existential quantifiers, that is, the prefix-class ∀…∀∃…∃; but they do not investigate further its range of applicability to syntactically specified classes.
An expansion of F̃p
Authors: Chatzidakis Zoé
Published: May 2006

Let K be a field of characteristic p. The map τ(X) = Xp − X is an additive endomorphism of K, with kernel Fp. The Galois extensions of K of order p are obtained by adjoining to K solutions to equations of the form Xp − X = a for some a in K. These extensions are called the Artin-Schreier extensions of K and have a cyclic Galois group.

The study of Artin-Schreier extensions is very important for studying fields of characteristic p, in particular for studying valued fields of the form K((t)). An attempt at getting quantifier elimination for those fields would necessitate the adjunction to the language of fields of a cross-section for the function τ, i.e. a function σ such that τ ∘ σ is the identity on the image of τ. When K = Fp, such a cross-section is in fact definable in K((t)): it associates to τ(x) the element of {x, x + 1, …, x + p – 1} whose constant term is 0 (see [2]). When K is infinite, such a cross-section is usually not definable.

The results presented in this paper originate from a question of L. van den Dries: is there a natural way of defining a cross-section σ for τ on F̃p, and is the theory of (F̃p, σ) decidable? (F̃p is the algebraic closure of Fp.)
Intensional logic and two-sorted type theory
Authors: Zimmermann Thomas Ede
Published: May 2006

Among the symbolic languages used most frequently in the indirect interpretation of natural language are Montague's Intensional Logic IL [5, 384ff.] and its extensional counterpart, the language Ty2 of two-sorted type theory. The question of which of these two formal languages is to be preferred has been obscured by lack of knowledge about the exact relation between them. The present paper is an attempt to clarify the situation by showing that, modulo a small, decidable class of formulas irrelevant to these applications, IL and Ty2 are equivalent in the strong sense that there exists a reversible translation between the terms of either language.

In [3, 6Iff.] Gallin has shown that there exists a simple and natural translation * of IL into Ty2. Following Gallin's translation procedure, it is even possible to conceive of IL as a highly restricted sublanguage of Ty2, viz. as that part which only contains expressions of certain intensional types plus one variable of the basic type of indices or worlds. In an obvious sense, this sublanguage has less expressive power than the whole of Ty2, where it is possible to express conditions on entities that do not even exist in IL's ontology. However, by a certain amount of coding, one can translate Ty2 into IL [3, 105]. Conditions on nonintensional entities then become conditions on corresponding intensional objects; and these paraphrases preserve (standard) validity and entailment. On the other hand, this retranslation of Ty2 into IL is not an inversion of *, as can be seen from a simple example.
Classification and interpretation
Authors: Baudisch Andreas
Published: May 2006

Let S and T be countable complete theories. We assume that T is superstable without the dimensional order property, and S is interpretable in T in such a way that every model of S is coded in a model of T. We show that S does not have the dimensional order property, and we discuss the question of whether Depth(S) ≤ Depth(T). For Mekler's uniform interpretation of arbitrary theories S of finite similarity type into suitable theories TS of groups we show that Depth(S) ≤ Depth(TS) ≤ 1 + Depth(S).
Plongement dense d'un corps ordonné dans sa clôture réelle
Authors: Delon Françoise
Published: May 2006

We study the structures (K ⊂ Kr), where K is an ordered field and Kr its real closure, in the language of ordered fields with an additional unary predicate for the subfield K. Two such structures (K ⊂ Kr) and (L ⊂ Lr) are not necessarily elementary equivalent when K and L are. But with some saturation assumption on K and L, then the two structures become equivalent, and we give a description of the complete theory.
Systems of illative combinatory logic complete for first-order propositional and predicate calculus
Authors: Barendregt Henk , Bunder Martin , Dekkers Wil
Published: May 2006

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators or, in a more direct way, in which derivations are not translated. Both translations are closely related in a canonical way. The two direct translations turn out to be complete. The paper fulfills the program of Church [1932], [1933] and Curry [1930] to base logic on a consistent system of λ-terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent).
Variations on a game of Gale (I): Coding strategies
Authors: Scheepers Marion
Published: May 2006

We consider an infinite two-person game. The second player has a winning perfect information strategy; we show that this player has a winning strategy which depends on substantially less information. The game studied here is a variation on a game of Gale.
Arithmetic definability by formulas with two quantifiers
Authors: Tung Shih Ping
Published: May 2006

We give necessary conditions for a set to be definable by a formula with a universal quantifier and an existential quantifier over algebraic integer rings or algebraic number fields. From these necessary conditions we obtain some undefinability results. For example, N is not definable by such a formula over Z. This extends a previous result of R. M. Robinson.
Local behaviour of the Chebyshev theorem in models of I⊿0
Authors: Paola D'Aquino
Published: May 2006

Let I⊿0 denote the fragment of Peano arithmetic where induction is restricted only to bounded formulas (⊿0-formulas), i.e. formulas where all the quantifiers are bounded. We will examine the behaviour in I⊿0 of Chebyshev's classical result on the distribution of primes. Chebyshev showed that each of the following functions on N is bounded by a polynomial in each of the others:

In his proof he used, as auxiliaries, factorials and binomial coefficients.

When we work in a weak system like I⊿0 we have to deal with two problems:

(i) There is not an immediate meaning for symbols like xy, Πp≤xp, and x!.

(ii) Some basic functions like exponentiation, factorial, and product of primes up to a certain element, are in general only partially definable.

The first problem is equivalent to finding ⊿0-formulas representing the relations z = xy, y = Πp≤xp, and y = x!. While we can easily express that y is the product of all primes less than or equal to x in a ⊿0-way, it requires a subtle argument to define z = xy by a ⊿0-formula. The most natural way of expressing it is via the formalization of the Chinese remainder theorem coding the recursion procedure used in the definition of xy. But this can be expressed only via a Σ1-formula. ⊿0-definitions of exponentiation were given by Paris and Bennett (see [GD] and [B]), and all sensible definitions of this type are equivalent (see Remark 1). Later we will examine properties of such a definition E0(x, y, z). The ⊿00-definition of y = Πp≤xp is much more straightforward, since both the relation of being a prime and the divisibility relation are ⊿0-definable. We will give an explicit definition of it and denote it by Ψ(x, y). In this way, by a ⊿0-induction, we will be able to prove the uniqueness of the elements y and z satisfying Ψ(x, y) and E0(x, y, z), respectively.
An intuitionistic proof of Tychonoff's theorem
Authors: Coquand Thierry
Published: May 2006

Tychonoff's theorem states that a product of compact spaces is compact. In [3], P. Johnstone presents a proof of Tychonoff's theorem in a “localic” framework. The surprise is that the point-free formulation of Tychonoff's theorem is provable without the axiom of choice, whereas in the usual formulation it is equivalent to the axiom of choice (see Kelley [5]).

The proof given in [3], however, is classical and seems to use the replacement axiom of Zermelo-Fraenkel. The aim of this paper is to present what we believe to be a more direct proof, which is intuitionistic and can be proved using as primitive only the notion of inductive definition, as it is for instance presented in Martin-Löf [6]. One main point of the paper is to show that the theory of locales can be developed rather naturally in the framework of inductive definitions. We think that our arguments can be presented in the constructive set theory of Aczel [2].

The paper is organized as follows. In §1 we show the argument in the case of a product of two spaces. This proof has a direct generalisation to the case of a product over a set with a decidable equality.

§1. Product of two spaces. We first recall a possible definition of a point-free space (see Johnstone [3] or Vickers [10]). It is a poset (X, ≤), together with a meet operation ab, written multiplicatively, and, for each a ∈ X, a set Cov(a) of subsets of {x ∈ X ∣ x ≤ a}. We ask that if M ∈ Cov(a) and b ≤ a, then {bs ∈ s ∈ M} ∈ Cov(b). This property of Cov will be called the axiom of covering. The elements of Cov(u) are called basic covers of u ∈ X.
Superstable differential fields
Authors: Pillay A. , Sokolović Ž.
Published: May 2006

In this paper we study differential fields of characteristic 0 (with perhaps additional structure) whose theory is superstable. Our main result is that such a differential field has no proper strongly normal extensions in the sense of Kolchin [K1]. This is an approximation to the conjecture that a superstable differential field is differentially closed (although we believe the full conjecture to be false). Our result improves earlier work of Michaux [Mi] who proved that a (plain) differential field with quantifier elimination has no proper Picard-Vessiot extension. Our result is a generalisation of Michaux's, due to the fact that any plain differential field K with quantifier elimination is ω-stable. (Any quantifier free type over K defines a unique type over K in the sense of dc(k), the differential closure of K, and as we mention below the theory of differentially closed fields is ω-stable.) The proof of our main result depends on (i) Kolchin's theory [K3] which states that any strongly normal extension L of an algebraically closed differential field K is generated over K by an element η of some algebraic group G defined over CK, the constants of K, where η satisfies some specific differential equations over K related to invariant differential forms on G (η is “G-primitive” over K), and (ii) the fact that a superstable field has a unique generic type which is semiregular.
Definable types in -minimal theories
Authors: Marker David , Steinhorn Charles I.
Published: May 2006

Let L be a first order language. If M is an L-structure, let LM be the expansion of L obtained by adding constants for the elements of M.

Definition. A type is definable if and only if for any L-formula , there is an LM-formula so that for all iff M ⊨ dθ(¯). The formula dθ is called the definition of θ.

Definable types play a central role in stability theory and have also proven useful in the study of models of arithmetic. We also remark that it is well known and easy to see that for M ≺ N, the property that every M-type realized in N is definable is equivalent to N being a conservative extension of M, where

Definition. If M ≺ N, we say that N is a conservative extension of M if for any n and any LN -definable S ⊂ Nn, S ∩ Mn is LM-definable in M.

Van den Dries [Dl] studied definable types over real closed fields and proved the following result.

0.1 (van den Dries), (i) Every type over (R, +, -,0,1) is definable.

(ii) Let F and K be real closed fields and F ⊂ K. Then, the following are equivalent:

(a) Every element of K that is bounded in absolute value by an element of F is infinitely close (in the sense of F) to an element of F.

(b) K is a conservative extension of F.
Fragile measurability
Authors: Hamkins Joel
Published: May 2006

Laver [L] and others [G-S] have shown how to make the supercompactness or strongness of κ indestructible by a wide class of forcing notions. We show, alternatively, how to make these properties fragile. Specifically, we prove that it is relatively consistent that any forcing which preserves κ<κ and κ+, but not P(κ), destroys the measurability of κ, even if κ is initially supercompact, strong, or if I1(κ) holds. Obtained as an application of some general lifting theorems, this result is an “inner model” type of theorem proved instead by forcing.
A note on a result of Kunen and Pelletier
Authors: Barbanel Julius B.
Published: May 2006

Suppose that U and U′ are normal ultrafilters associated with some supercompact cardinal. How may we compare U and U′? In what ways are they similar, and in what ways are they different? Partial answers are given in [1], [2], [3], [5], [6], and [7]. In this paper, we continue this study.

In [6], Menas introduced a combinatorial principle χ(U) of normal ultrafilters U associated with supercompact cardinals, and showed that normal ultrafilters satisfying this property also satisfy a partition property. In [5], Kunen and Pelletier showed that this partition property for U does not imply χ(U). Using results from [3], we present a different method of finding such normal ultrafilters which satisfy the partition property but do not satisfy χ(U). Our method yields a large collection of such normal ultrafilters.
Combinatorics on large cardinals
Authors: Montenegro E. Carlos H.
Published: May 2006

Our framework is ZFC, and we view cardinals as initial ordinals. Baumgartner ([Bal] and [Ba2]) studied properties of large cardinals by considering these properties as properties of normal ideals and not as properties of cardinals alone. In this paper we study these combinatorial properties by defining operations which take as input one or more ideals and give as output an ideal associated with a large cardinal property. We consider four operations T, P, S and C on ideals of a regular cardinal κ, and study the structure of the collection of subsets they give, and the relationships between them.

The operation T is defined using combinatorial properties based on trees 〈X, <T〉 on subsets X ⊆ κ (where α <T β → α < β). Given an ideal I, consider the property *: “every tree on κ with every branching set in I has a branch of size κ” (where a branching set is a maximal set with the same set of <T-predecessors, and a chain is a maximal <T-linearly ordered set; for definitions see §2). Now consider the collection T(I) of all subsets of κ that do not satisfy * (see Definition 2.2 and the introduction to §5). The operation T provides us with the large cardinal property (whether κ ∈ T(I) or not) and it also provides us with the ideal associated with this large cardinal property (namely T(I)); in general, we obtain different notions depending on the ideal I.
Singular σ-dense trees
Authors: Landver Avner
Published: May 2006

Let be the least cardinal θ such that MAθ fails, (i.e. MA) implies that is regular. Models for regular with are easy to get (see [Ku1]). Fremlin and Miller proved that cof() > ω [Fr, 41C(d)]. The question of whether it is consistent that be singular was solved, in the affirmative, by Kunen [Ku1]. Kunen used a (θ, θ) strong gap in (ω)/Fin, whose splitting partial order is c.c.c. He showed that if cof(θ) = ω1, and P is a c.c.c. partial order of cardinality < θ that may destroy the strong gap, then there exists another c.c.c. partial order Q, which does not destroy the strong gap, and such that ⊩Q “P is not c.c.c”. One then gets Kunen's model by iterating c.c.c. partial orders of cardinality < θ, without destroying the strong (θ, θ) gap. It is unknown whether it is consistent to have ω1 < cof() < .

Clearly, there exists a c.c.c. partial order Q with ∣Q∣ = , such that (Q) = (see (1.1)). A partial order P is σ-centered iff P is the union of countably many centered subsets, where a subset A ⊆ P is centered iff p ≤ q. Clearly, a σ-centered partial order is c.c.c. Bell and Szymański proved that (σ-centered) is regular (see [Be] or [Fr, 14C], and [Fr, 21K] or [vD, 3.1(e)]). This implies that if P is a σ-centered partial order, and is singular, then (P) > . In particular, if is singular, then Q is not σ-centered and all c.c.c. partial orders of cardinality < have a Baire number (1.1) strictly greater than . It was suggested in [Ku1] to try and use Q(T) (1.2), where T is a tree with no ω1-branches, to get models with singular . It is well known that when T is such a tree, the forcing Q(T) is c.c.c. [BMR], ∣Q(T)∣ = ∣T∣, and if T is not special, then n(Q(T)) ≤ ∣T∣.
The continuum and first-order intuitionistic logic
Authors: van Dalen D.
Published: May 2006

Ever since Cantor, we have known that the reals and the rationals are not isomorphic (as equality structures, i.e., sets). Logically speaking, however, they are not all that different; in first-order classical logic they are elementarily equivalent, since the theory of infinite sets is complete. The same holds for ℝ and ℚ as ordered sets; again the theory of dense linear order without end points is complete.

From an intuitionistic point of view these matters are more complicated; e.g., the theory of equality of ℚ is decidable, whereas the one of ℝ patently is not. This, in a roundabout way, shows that ℚ and ℝ are not isomorphic; of course, there is no need for such a detour, as Cantor's original proof [2] is intuitionistically correct, and Brouwer's new proof [1] is another alternative intuitionistic argument.

In view of the fact that ℚ and ℝ behave so strikingly differently with respect to first-order logic, one is easily tempted to look for elementary equivalences among the subsets of ℝ. Until quite recently most model theoretic investigations of intuitionistic theories made use of special (artificial) notions of “model”, e.g., Kripke models, sheaf models,…; but there is no prima facie reason why one should not practice model theory much the same way as traditional model theorists do. That is to say on the basis of a naive set theory, or, in our case, of naive intuitionistic mathematics.

This paper uses the method of (k, p)-isomorphisms of Fraïssé, and it is briefly shown that one half of the Fraïssé theorem holds intuitionistically.
Questions of decidability and undecidability in Number Theory
Authors: Mazur B.
Published: May 2006

Davis, Matijasevic, and Robinson, in their admirable survey article [D-M-R], interpret the negative solution of Hilbert's Tenth Problem as a resounding positive statement about the versatility of Diophantine equations (that any listable set can be coded as the set of parameter values for which a suitable polynomial possesses integral solutions).

One can also view the Matijasevic result as implying that there are families of Diophantine equations parametrized by a variable t, which have integral solutions for some integral values t = a > 0, and yet there is no computable function of t which provides an upper bound for the smallest integral solution for these values a. The smallest integral solutions of the Diophantine equation for these values are, at least sporadically, too large to be bounded by any computable function. This is somewhat difficult to visualize, since there is quite an array of computable functions. But let us take an explicit example. Consider the function

Matijasevic's result guarantees the existence of parametrized families of Diophantine equations such that even this function fails to yield an upper bound for its smallest integral solutions (for all values of the parameter t for which there are integral solutions).

Families of Diophantine equations in a parameter t, whose integral solutions for t = 1, 2, 3,… exhibit a certain arythmia in terms of their size, have fascinated mathematicians for centuries, and this phenomenon (the size of smallest integral solution varying wildly with the parameter-value) is surprising, even when the equations are perfectly “decidable”.
A structure theorem for semibounded sets in the reals
Authors: Peterzil Ya'acov
Published: May 2006

In [MPP] it was shown that in every reduct of = ‹ ℝ, +, ·, <› that properly expands ℳ = ‹ℝ, +, <, λa›a∈ℝ, all the bounded semi-algebraic (that is, -definable) sets are definable. Said differently, every such is an expansion of = ‹ℝ, +, <, λa, Bi›a∈ℝ, i∈I where {Bi}i∈I is the collection of all bounded semialgebraic sets and the λa's are scalar multiplication by a. In [PSS] (see Theorem 1.2 below) it was shown that the structure is a proper reduct of ; that is, one cannot define in it all the semialgebraic sets. In [Pe] we show that is the only reduct properly between ℳ and . As a first step towards this result, we investigate in this paper the definable sets in reducts such as . (We point out that ‘definable’ will always mean ‘definable with parameters’.)

Definition 1.1. Let X ⊆ ℝn. X is called semi-bounded if it is definable in the structure ‹ℝ, +, <, λa, B1, …, Bk›a∈ℝ, where the Bi's are bounded subsets of ℝn.

The main result of this paper (see Theorem 3.1) shows roughly that, in Ominimal expansions of that satisfy the partition condition (see Definition 2.3), every semibounded set can be partitioned into finitely many sets, each of which is of a form similar to a cylinder. Namely, these sets are obtained through the “stretching” of a bounded cell by finitely many linear vectors. As a corollary (see Theorem 1.4), we get different characterizations of semibounded sets, either in terms of their structure or in terms of their definability power.

The following result, by A. Pillay, P. Scowcroft and C. Steinhorn, was the main motivation for this paper. The theorem is formulated here in a slightly stronger form than originally, but the proof itself is essentially the original one. A short version of the proof is included in §4.
Whither relevant arithmetic?
Authors: Friedman Harvey , Meyer Robert K.
Published: May 2006

Based on the relevant logic R, the system R#was proposed as a relevant Peano arithmetic. R#has many nice properties: the most conspicuous theorems of classical Peano arithmetic PA are readily provable therein; it is readily and effectively shown to be nontrivial; it incorporates both intuitionist and classical proof methods. But it is shown here that R#is properly weaker than PA, in the sense that there is a strictly positive theorem QRF of PA which is unprovable in R#. The reason is interesting: if PA is slightly weakened to a subtheory P+, it admits the complex ring C as a model; thus QRF is chosen to be a theorem of PA but false in C. Inasmuch as all strictly positive theorems of R#are already theorems of P+, this nonconservativity result shows that QRF is also a nontheorem of R#. As a consequence, Ackermann's rule γ is inadmissible in R#. Accordingly, an extension of R#which retains its good features is desired. The system R##, got by adding an omega-rule, is such an extension. Central question: is there an effectively axiomatizable system intermediate between R#and R#, which does formalize arithmetic on relevant principles, but also admits γ in a natural way?
Non-finite-axiomatizability results in algebraic logic
Authors: Biró Balázs
Published: May 2006

This paper deals with relation, cylindric and polyadic equality algebras. First of all it addresses a problem of B. Jónsson. He asked whether relation set algebras can be expanded by finitely many new operations in a “reasonable” way so that the class of these expansions would possess a finite equational base. The present paper gives a negative answer to this problem: Our main theorem states that whenever Rs+ is a class that consists of expansions of relation set algebras such that each operation of Rs+ is logical in Jónsson's sense, i.e., is the algebraic counterpart of some (derived) connective of first-order logic, then the equational theory of Rs+ has no finite axiom systems. Similar results are stated for the other classes mentioned above. As a corollary to this theorem we can solve a problem of Tarski and Givant [87], Namely, we claim that the valid formulas of certain languages cannot be axiomatized by a finite set of logical axiom schemes. At the same time we give a negative solution for a version of a problem of Henkin and Monk [74] (cf. also Monk [70] and Németi [89]).

Throughout we use the terminology, notation and results of Henkin, Monk, Tarski [71] and [85]. We also use results of Maddux [89a].

Notation. RA denotes the class of relation algebras, Rs denotes the class of relation set algebras and RRA is the class of representable relation algebras, i.e. the class of subdirect products of relation set algebras. The symbols RA, Rs and RRA abbreviate also the expressions relation algebra, relation set algebra and representable relation algebra, respectively.

For any class C of similar algebras EqC is the set of identities that hold in C, while Eq1C is the set of those identities in EqC that contain at most one variable symbol. (We note that Henkin et al. [85] uses the symbol EqC in another sense.)
About the proof-theoretic ordinals of weak fixed point theories
Authors: Jäger Gerhard , Primo Barbara
Published: May 2006

This paper presents several proof-theoretic results concerning weak fixed point theories over second order number theory with arithmetic comprehension and full or restricted induction on the natural numbers. It is also shown that there are natural second order theories which are proof-theoretically equivalent but have different proof-theoretic ordinals.
Elementary embedding between countable Boolean algebras
Authors: Bonnet Robert , Rubin Matatyahu
Published: May 2006

For a complete theory of Boolean algebras T, let MT denote the class of countable models of T. For B1, B2 ∈ MT, let B1 ≤ B2 mean that B2 is elementarily embeddable in B2. Theorem 1. For every complete theory of Boolean algebras T, if T ≠ Tω, then ‹MT, ≤› is well-quasi-ordered. ∎ We define Tω. For a Boolean algebra B, let I(B) be the ideal of all elements of the form a + s such that B ↾ a is an atomic Boolean algebra and B ↾ s is an atomless Boolean algebra. The Tarski derivative of B is defined as follows: B(0) = B and B(n + 1) = B(n)/I(B(n)). Define Tω to be the theory of all Boolean algebras such that for every n ∈ ω, B(n) ≠ {0}. By Tarski [1949], Tω is complete. Recall that ‹A, < › is partial well-quasi-ordering, it is a partial quasi-ordering and for every {ai, ⃒ i ∈ ω} ⊆ A, there are i < j < ω such that ai ≤ aj. Theorem 2. contains a subset M such that the partial orderings ‹M, ≤ ↾ M› and are isomorphic. ∎ Let M′0 denote the class of all countable Boolean algebras. For B1, B2 ∈ M′0, let B1 ≤′ B2 mean that B1 is embeddable in B2. Remark. ‹M′0, ≤′› is well-quasi-ordered. ∎ This follows from Laver's theorem [1971] that the class of countable linear orderings with the embeddability relation is well-quasi-ordered and the fact that every countable Boolean algebra is isomorphic to a Boolean algebra of a linear ordering.
On a problem of C. H. Dowker
Authors: Balogh Z. , Gruenhage G.
Published: May 2006

It is shown that Con(ZF) implies Con(ZFC + there exists a Dowker filter on ω2). The problem is also considered on higher cardinals.
Properties of independently axiomatizable bimodal logics
Authors: Kracht Marcus , Wolter Frank
Published: May 2006

In monomodal logic there are a fair number of high-powered results on completeness covering large classes of modal systems; witness for example Fine [74], [85] and Sahlqvist [75]. Monomodal logic is therefore a well-understood subject in contrast to polymodal logic, where even the most elementary questions concerning completeness, decidability, etc. have been left unanswered. Given that in many applications of modal logic one modality is not sufficient, the lack of general results is acutely felt by the “users” of modal logics, contrary to logicians who might entertain the view that a deep understanding of one modality alone provides enough insight to be able to generalize the results to logics with several modalities. Although this view has its justification, the main results we are going to prove are certainly not of this type, for they require a fundamentally new technique. The results obtained are called transfer theorems in Fine and Schurz [91] and are of the following type. Let L ∌ ⊥ be an independently axiomatizable bimodal logic and L⎕ and L∎ its monomodal fragments. Then L has a property P iff L⎕ and L∎ have P. Properties which will be discussed are completeness, the finite model property, compactness, persistence, interpolation and Halldén-completeness. In our discussion we will prove transfer theorems for the simplest case when there are just two modal operators, but it will be clear that the proof works in the general case as well.
The consistency of one fixed omega
Authors: Henle J. M.
Published: May 2006

The paper “Partitions of Products” [DiPH] investigated the polarized partition relation

The relation is consistent relative to an inaccessible cardinal if every αi is finite, but inconsistent if two are infinite. We show here that it consistent (relative to an inaccessible) for one to be infinite.

Along the way, we prove an interesting proposition from ZFC concerning partitions of the finite subsets of ω.
The equivalence of NF-style set theories with “tangled” type theories; the construction of ω-models of predicative NF (and more)
Authors: Holmes M. Randall
Published: May 2006

An ω-model (a model in which all natural numbers are standard) of the predicative fragment of Quine's set theory “New Foundations” (NF) is constructed. Marcel Crabbé has shown that a theory NFI extending predicative NF is consistent, and the model constructed is actually a model of NFI as well. The construction follows the construction of ω-models of NFU (NF with urelements) by R. B. Jensen, and, like the construction of Jensen for NFU, it can be used to construct α-models for any ordinal α. The construction proceeds via a model of a type theory of a peculiar kind; we first discuss such “tangled type theories” in general, exhibiting a “tangled type theory” (and also an extension of Zermelo set theory with Δ0 comprehension) which is equiconsistent with NF (for which the consistency problem seems no easier than the corresponding problem for NF (still open)), and pointing out that “tangled type theory with urelements” has a quite natural interpretation, which seems to provide an explanation for the more natural behaviour of NFU relative to the other set theories of this kind, and can be seen anachronistically as underlying Jensen's consistency proof for NFU.
Some applications of coarse inner model theory
Authors: Hjorth Greg
Published: May 2006

The Martin-Steel coarse inner model theory is employed in obtaining new results in descriptive set theory. determinacy implies that for every thin equivalence relation there is a real, N, over which every equivalence class is generic—and hence there is a good (N#) wellordering of the equivalence classes. Analogous results are obtained for and quasilinear orderings and determinacy is shown to imply that every prewellorder has rank less than .
A logical presentation of the continuous functionals
Authors: Palmgren Erik , Stoltenberg-Hansen Viggo
Published: May 2006

The Kleene-Kreisel continuous functionals [6, 7] have been given several alternative characterisations: using Kuratowski's limit spaces (Scarpellini [20]), using their generalisation, filter spaces (Hyland [4]), via hyperfinite functionals (Normann [11]) and perhaps most elegantly using Scott-Ershov domains (Ershov [3], later generalised by Berger [1]). We propose to add yet another characterisation to this list, which may be called model-theoretic in contrast to the others, but which is in fact closely related to Ershov's approach.

We use the notion of logically presented domains developed in Palmgren and Stoltenberg-Hansen [17] (originating in the work of [15]). Certain logical types, i.e., finitely consistent sets of formulas, over the full type structure built from ℕ correspond to the continuous functionals in the sense of Kreisel, or to Kleene's associates, while the elements realising the types correspond to functionals having associates (cf. [6]). To define these—the total types—we make a nonstandard extension of the full type structure. The set of nonstandard elements is sufficiently rich to single out the total types. The nonstandard extension also makes it possible to relate the logical presentation to Ershov's approach. The logical form of the domain constructions allows us to use a (generalised) Fréchet power as a nonstandard extension. This extension is constructive, in the sense that it avoids the axiom of choice, as distinguished from the one employed in [11].
How to characterize provably total functions by local predicativity
Authors: Weiermann Andreas
Published: May 2006

Inspired by Pohlers' proof-theoretic analysis of KPω we give a straightforward non-metamathematical proof of the (well-known) classification of the provably total functions of PA, PA + TI(⊰ ↾) (where it is assumed that the well-ordering ⊰ has some reasonable closure properties) and KPω. Our method relies on a new approach to subrecursion due to Buchholz, Cichon and the author.
Self-commuting quantifiers
Authors: Westerståhl Dag
Published: May 2006

We characterize the generalized quantifiers Q which satisfy the scheme QxQyф ↔ QyQxф, the so-called self-commuting quantifiers, or quantifiers with the Fubini property.
Countable unions of simple sets in the core model
Authors: Welch P. D.
Published: May 2006

We follow [8] in asking when a set of ordinals X ⊆ α is a countable union of sets in K, the core model. We show that, analogously to L, an X closed under the canonical Σ1 Skolem function for Kα can be so decomposed provided K is such that no ω-closed filters are put on its measure sequence, but not otherwise. This proviso holds if there is no inner model of a weak Erdős-type property.
Prototypes for definable subsets of algebraically closed valued fields
Authors: Holly Jan E.
Published: May 2006

Elimination of imaginaries for 1-variable definable equivalence relations is proved for a theory of algebraically closed valued fields with new sorts for the disc spaces. The proof is constructive, and is based upon a new framework for proving elimination of imaginaries, in terms of prototypes which form a canonical family of formulas for defining each set that is definable with parameters. The proof also depends upon the formal development of the tree-like structure of valued fields, in terms of valued trees, and a decomposition of valued trees which is used in the coding of certain sets of discs.
Proofs of strong normalisation for second order classical natural deduction
Authors: Parigot Michel
Published: May 2006

We give two proofs of strong normalisation for second order classical natural deduction. The first one is an adaptation of the method of reducibility candidates introduced in [9] for second order intuitionistic natural deduction; the extension to the classical case requires in particular a simplification of the notion of reducibility candidate. The second one is a reduction to the intuitionistic case, using a Kolmogorov translation.
Definability of types, and pairs of O-minimal structures
Authors: Pillay Anand
Published: May 2006

Let T be a complete O-minimal theory in a language L. We first give an elementary proof of the result (due to Marker and Steinhorn) that all types over Dedekind complete models of T are definable. Let L* be L together with a unary predicate P. Let T* be the L*-theory of all pairs (N, M), where M is a Dedekind complete model of T and N is an ⅼMⅼ+-saturated elementary extension of N (and M is the interpretation of P). Using the definability of types result, we show that T* is complete and we give a simple set of axioms for T*. We also show that for every L*-formula ϕ(x) there is an L-formula ψ(x) such that T* ⊢ (∀x)(P(x) → (ϕ(x) ↔ ψ(x)). This yields the following result:

Let M be a Dedekind complete model of T. Let ϕ(x, y) be an L-formula where l(y) – k. Let X = {X ⊂ Mk: for some a in an elementary extension N of M, X = ϕ(a, y)N ∩ Mk}. Then there is a formula ψ(y, z) of L such that X = {ψ(y, b)M: b in M}.