bluuebunny/crossref_metadata_2025 huggingface dataset:
Abelian groups with modular generic
Authors: Loveys James
Published: May 2006

Let G be a stable abelian group with regular modular generic. We show that either

1. there is a definable nongeneric K ≤ G such that G/K has definable connected component and so strongly regular generics, or

2. distinct elements of the division ring yielding the dependence relation are represented by subgroups of G × G realizing distinct strong types (when regarded as elements of Geq).

In the latter case one can choose almost 0-definable subgroups representing the elements of the division ring. We find a bound ((G: G0)) for the size of the division ring in case G has no definable subgroup K so that G/K is infinite with definable connected component. We show in case (2) that the group G/H, where H consists of all nongeneric points of G, inherits a weakly minimal group structure from G naturally, and Th(G/H) is independent of the particular model G as long as G/H is infinite.
Admissible Suslin cardinals in L(R)
Authors: Jackson Steve
Published: May 2006

Assuming AD + (V = L(R)), it is shown that for κ an admissible Suslin cardinal, o(κ) (= the order type of the stationary subsets of κ) is “essentially” regular and closed under ultrapowers in a manner to be made precise. In particular, o(κ) ≫ κ+, κ++, etc. It is conjectured that this characterizes admissibility for L(R).
Generalizations of the Kruskal-Friedman theorems
Authors: Gordeev L.
Published: May 2006

Kruskal proved that finite trees are well-quasi-ordered by hom(e)omorphic embeddability. Friedman observed that this statement is not provable in predicative analysis. Friedman also proposed (see in [Simpson]) some stronger variants of the Kruskal theorem dealing with finite labeled trees under hom(e)omorphic embeddability with a certain gap-condition, where labels are arbitrary finite ordinals from a fixed initial segment of ω. The corresponding limit statement, expressing that for all initial segments of ω these labeled trees are well-quasi-ordered, is provable in -CA, but not in the analogous theory -CA0 with induction restricted to sets. Schütte and Simpson proved that the one-dimensional case of Friedman's limit statement dealing with finite labeled intervals is not provable in Peano arithmetic. However, Friedman's gap-condition fails for finite trees labeled with transfinite ordinals. In [Gordeev 1] I proposed another gap-condition and proved the resulting one-dimensional modified statements for all (countable) transfinite ordinal-labels. The corresponding universal modified one-dimensional statement UM1 is provable in (in fact, is equivalent to) the familiar theory ATR0 whose proof-theoretic ordinal is Γ0. In [Gordeev 1] I also announced that, in the general case of arbitrarily-branching finite trees labeled with transfinite ordinals, in the proof-theoretic sense the hierarchy of the limit modified statements M<λ (which are denoted by LMλ in the present note) is as strong as the hierarchy of the familiar theories of iterated inductive definitions (more precisely, see [Gordeev 1, Concluding Remark 3]). In this note I present a “positive” proof of the full universal modified statement UM, together with a short proof of the crucial “reverse” results which is based on Okada's interpretation of the well-established ordinal notations of Buchholz corresponding to the theories of iterated inductive definitions. Formally the results are summarized in §5 below.
On the strong Martin conjecture
Authors: Itai Masanori
Published: May 2006

We study the following conjecture.

Conjecture.Let T be an ω-stable theory with continuum many countable models. Then either i) T has continuum many complete extensions in L1(T), or ii) some complete extension of T in L1has continuum many L1-types without parameters.

By Shelah's proof of Vaught's conjecture for ω-stable theories, we know that there are seven types of ω-stable theory with continuum many countable models. We show that the conjecture is true for all but one of these seven cases. In the last case we show the existence of continuum many L2-types.
On maximal theories
Authors: Adamowicz Zofia
Published: May 2006

Let S be a recursive theory. Let a theory T* consisting of Σ1 sentences be called maximal (with respect to S) if T* is maximal consistent with S, i.e. there is no Σ1 sentence consistent with T* + S which is not in T*.

A maximal theory with respect to IΔ0 was considered by Wilkie and Paris in [WP] in connection with the end-extension problem.

Let us recall that IΔ0 is the fragment of Peano arithmetic consisting of the finite collection of algebraic axioms PA− together with the induction scheme restricted to bounded formulas.

The main open problem concerning the end-extendability of models of IΔ0 is the following:

(*) Does every model of IΔ0 + BΣ1 have a proper end-extension to a model of IΔ0?

Here BΣ1 is the following collection scheme:

where φ runs over bounded formulas and may contain parameters.

It is well known(see [KP]) that if I is a proper initial segment of a model M of IΔ0, then I satisfies IΔ0 + BΣ1.

For a wide discussion of the problem (*) see [WP]. Wilkie and Paris construct in [WP] a model M of IΔ0 + BΣ1 which has no proper end-extension to a model of IΔ0 under the assumption IΔ0 ⊢¬Δ0H (see [WP] for an explanation of this assumption). Their model M is a model of a maximal theory T* where S = IΔ0.

Moreover, T*, which is the set Σ1(M) of all Σ1 sentences true in M, is not codable in M.
Inductive inference and unsolvability
Authors: Adleman Leonard M. , Blum M.
Published: May 2006

Abtract

It is shown that many different problems have the same degree of unsolvability. Among these problems are:

The Inductive Inference Problem. Infer in the limit an index for a recursive function f presented as f(0), f(1),f(2),….

The Recursive Index Problem. Decide in the limit if i is the index of a total recursive function.

The Zero Nonvariant Problem. Decide in the limit if a recursive function f presented as f(0), f(1), f(2),… has value unequal to zero for infinitely many arguments.

Finally, it is shown that these unsolvable problems are strictly easier than the halting problem.
Axiomatizing universal properties of quantifiers
Authors: Doets Kees
Published: May 2006

Abtract

We axiomatize all quantifier properties which can be expressed by a universal condition on the class of algebras of sets.
On bad groups, bad fields, and pseudoplanes
Authors: Nesin Ali
Published: May 2006

Cherlin introduced the concept of bad groups (of finite Morley rank) in [Ch1]. The existence of such groups is an open question. If they exist, they will contradict the Cherlin-Zil'ber conjecture that states that an infinite simple group of finite Morley rank is a Chevalley group over an algebraically closed field. In this paper, we prove that bad groups of finite Morley rank 3 act on a natural geometry Γ (namely on a special pseudoplane; see Corollary 20) sharply flag-transitively.We show that Γ is not very far from being a projective plane and when it is so rk(Γ) = 2 and Γ is not Desarguesian (Theorem 2). Baldwin [Ba] recently discovered non-Desarguesian projective planes of Morley rank 2. This discovery, together with this paper, makes the existence of bad groups (also of bad fields) more plausible. A bad field is a pair (K, A) of finite Morley rank, where K is an algebraically closed field, A <≠K* and A is infinite. There existence is also unknown.

In this paper, we define the concept of a sharp-field as a pair (K, A), where K is a field, A < K*and

1. K = A − A,

2. If a + b − 1 ∈ A, a ∈ A, b ∈ A, then either a = 1 or b = 1.

If K is finite this is equivalent to 1 and

2.′ ∣K∣ = ∣A∣2 ∣A∣ + 1.

Finite sharp-fields are special cases of difference sets [De]
Extension of Lifschitz' realizability to higher order arithmetic,
and a solution to a problem of F. Richman
Authors: van Oosten Jaap
Published: May 2006

F. Richman raised the question of whether the following principle of second order arithmetic is valid in intuitionistic higher order arithmetic HAH:

and if not, whether assuming Church's Thesis CT and Markov's Principle MP would help. Blass and Scedrov gave models of HAH in which this principle, which we call RP, is not valid, but their models do not satisfy either CT or MP.

In this paper a realizability topos Lif is constructed in which CT and MP hold, but RP is false. (It is shown, however, that RP is derivable in HAH + CT + MP + ECT0, so RP holds in the effective topos.) Lif is a generalization of a realizability notion invented by V. Lifschitz. Furthermore, Lif is a subtopos of the effective topos.
Who were the American postulate theorists?
Authors: Scanlan Michael
Published: May 2006

Articles by two American mathematicians, E. V. Huntington and Oswald Veblen, are discussed as examples of a movement in foundational research in the period 1900–1930 called American postulate theory. This movement also included E. H. Moore, R. L. Moore, C. H. Langford, H. M. Sheffer, C. J. Keyser, and others. The articles discussed exemplify American postulate theorists' standards for axiomatizations of mathematical theories, and their investigations of such axiomatizations with respect to metatheoretic properties such as independence, completeness, and consistency.
A second order version of S2i and U21
Authors: Takeuti Gaisi
Published: May 2006

In [1] S. Buss introduced systems of bounded arithmetic , , , (i = 1, 2, 3, …). and are first order systems and and are second order systems. and are closely related to and respectively in the polynomial hierarchy, and and are closely related to PSPACE and EXPTIME respectively. One of the most important problems in bounded arithmetic is whether the hierarchy of bounded arithmetic collapses, i.e. whether = or = for some i, or whether = , or whether is a conservative extension of S2 = ⋃i. These problems are relevant to the problems whether the polynomial hierarchy PH collapses or whether PSPACE = PH or whether PSPACE = EXPTIME. It was shown in [4] that = implies and consequently the collapse of the polynomial hierarchy. We believe that the separation problems of bounded arithmetic and the separation problems of computational complexities are essentially the same problem, and the solution of one of them will lead to the solution of the other.
On the existence of atomic models
Authors: Laskowski M. C. , Shelah S.
Published: May 2006

We give an example of a countable theory T such that for every cardinal λ ≥ ℵ2 there is a fully indiscernible set A of power λ such that the principal types are dense over A, yet there is no atomic model of T over A. In particular, T(A) is a theory of size λ where the principal types are dense, yet T(A) has no atomic model.
Boolean universes above Boolean models
Authors: Wehrung Friedrich
Published: May 2006

We establish several first- or second-order properties of models of first-order theories by considering their elements as atoms of a new universe of set theory and by extending naturally any structure of Boolean model on the atoms to the whole universe. For example, completef-rings are “boundedly algebraically compact” in the language (+, −, ·, ∧, ∨, ≤), and the positive cone of a completel-group with infinity adjoined is algebraically compact in the language (+, ∨, ≤). We also give an example with any first-order language. The proofs can be translated into “naive set theory” in a uniform way.
The development of arithmetic in Frege'sGrundgesetze der arithmetik
Authors: Heck Richard G.
Published: May 2006

Frege's development of the theory of arithmetic in hisGrundgesetze der Arithmetikhas long been ignored, since the formal theory of theGrundgesetzeis inconsistent. His derivations of the axioms of arithmetic from what is known asHume's Principledo not, however, depend upon that axiom of the system—Axiom V—which is responsible for the inconsistency. On the contrary, Frege's proofs constitute a derivation of axioms for arithmetic from Hume's Principle, in (axiomatic) second-order logic. Moreover, though Frege does prove each of the now standard Dedekind-Peano axioms, his proofs are devoted primarily to the derivation of his own axioms for arithmetic, which are somewhat different (though of course equivalent). These axioms, which may be yet more intuitive than the Dedekind-Peano axioms, may be taken to be “TheBasic Laws of Cardinal Number”, as Frege understood them.

Though the axioms of arithmetic have been known to be derivable from Hume's Principle for about ten years now, it has not been widely recognized that Frege himself showed them so to be; nor has it been known that Frege made use of any axiomatization for arithmetic whatsoever.Grundgesetzeis thus a work of much greater significance than has often been thought. First, Frege's use of the inconsistent Axiom V may invalidate certain of his claims regarding the philosophical significance of his work (viz., the establish may invalidate certain of his claims regarding the philosophical significance of his work (viz., the establishment of Logicism), but it should not be allowed to obscure his mathematical accomplishments and his contribution to our understanding of arithmetic. Second, Frege's knowledge that arithmetic is derivable from Hume's Principle raises important sorts of questions about his philosophy of arithmetic. For example, “Why did Frege not simply abandon Axiom V and take Hume's Principle as an axiom?”
Every real closed field has an integer part
Authors: Mourgues M. H. , Ressayre J. P.
Published: May 2006

Let us call an integer part of an ordered field any subring such that every element of the field lies at distance less than I from a unique element of the ring. We show that every real closed field has an integer part.
The deduction rule and linear and near-linear proof simulations
Authors: Bonet Maria Luisa , Buss Samuel R.
Published: May 2006

We introduce new proof systems for propositional logic,simple deduction Frege systems, general deduction Frege systems, andnested deduction Frege systems, which augment Frege systems with variants of the deduction rule. We give upper bounds on the lengths of proofs in Frege proof systems compared to lengths in these new systems. As applications we give near-linear simulations of the propositional Gentzen sequent calculus and the natural deduction calculus by Frege proofs. The length of a proof is the number of lines (or formulas) in the proof.

A general deduction Frege proof system provides at most quadratic speedup over Frege proof systems. A nested deduction Frege proof system provides at most a nearly linear speedup over Frege system where by “nearly linear” is meant the ratio of proof lengths isO(α(n)) where α is the inverse Ackermann function. A nested deduction Frege system can linearly simulate the propositional sequent calculus, the tree-like general deduction Frege calculus, and the natural deduction calculus. Hence a Frege proof system can simulate all those proof systems with proof lengths bounded byO(n. α(n)). Also we show that a Frege proof ofnlines can be transformed into a tree-like Frege proof ofO(nlogn) lines and of heightO(logn). As a corollary of this fact we can prove that natural deduction and sequent calculus tree-like systems simulate Frege systems with proof lengths bounded byO(nlogn).
Provably total functions of intuitionistic bounded arithmetic
Authors: Harnik Victor
Published: May 2006

This note deals with a proof-theoretic characterisation of certain complexity classes of functions in fragments of intuitionistic bounded arithmetic. In this Introduction we survey the background and state our main result.

We follow Buss [B1] and consider a language for arithmetic whose nonlogical symbols are 0, S (the successor operation Sx = x + 1), +, ·, ∣ ∣ (∣x∣ being the number of digits in the binary notation for x), rounded down to the nearest integer), # (x#y = 2∣x∣∣y∣) and ≤. We define 1 = S0, 2 = S1, s0x = 2x and s1x = 2x + 1. In Buss's approach the functions s0 and s1 play a special role. Notice that six is the number obtained from x by suffixing the digit i to its binary representation, and thus the natural numbers are generated from 0 by repeated applications of the operations s0 and s1. This means that they satisfy the induction scheme

Using the fact that is x with its last binary digit deleted, this can be stated more compactly in the following form, called by Buss the polynomial induction or PIND schema:

Buss defined a theory S2 consisting of a finite set BASIC of open axioms and the PIND-schema restricted to bounded formulas ϕ. The topic of bounded arithmetic is concerned with S2 and its fragments.
Generalized reduction theorems for model-theoretic analogs of the class of coanalytic sets
Authors: Lavine Shaughan
Published: May 2006

Let be an admissible set. A sentence of the form is a sentence if φ ∈ (φ is ∨ Φ where Φ is an -r.e. set of sentences from ). A sentence of the form is an , sentence if φ is a sentence. A class of structures is, for example, a ∀1 class if it is the class of models of a ∀1() sentence. Thus ∀1() is a class of classes of structures, and so forth.

Let i, be the structure 〈i, <〉, for i > 0. Let Γ be a class of classes of structures. We say that a sequence J1, …, Ji,…, i < ω, of classes of structures is a Γ sequence if Ji ∈ Γ, i < ω, and there is I ∈ Γ such that ∈ Ji, if and only if [],i, where [,] is the disjoint sum. A class Γ of classes of structures has the easy uniformization property if for every Γ sequence J1,…, Ji,…, i < ω, there is a Γ sequence J′t, …, J′i, …, i < ω, such that J′i ⊆ Ji, i < ω, ⋃J′i = ⋃Ji, and the J′i are pairwise disjoint. The easy uniformization property is an effective version of Kuratowski's generalized reduction property that is closely related to Moschovakis's (topological) easy uniformization property.

We show over countable structures that ∀1() and ∃2() have the easy uniformization property if is a countable admissible set with an infinite member, that and have the easy uniformization property if α is countable, admissible, and not weakly stable, and that and have the easy uniformization properly. The results proved are more general. The result for answers a question of Vaught(1980).
Diophantine relations between rings of S-integers of fields of algebraic functions in one variable over constant fields of positive characteristic
Authors: Shlapentokh Alexandra
Published: May 2006

One of the main theorems of the paper states the following. Let R-K-M be finite extensions of a rational one variable function field R over a finite field of constants. Let S be a finite set of valuations of K. Then the ring of elements of K having no poles outside S has a Diophantine definition over its integral closure in M.
Undecidable semiassociative relation algebras
Authors: Maddux Roger D.
Published: May 2006

If K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism ℒw× is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in ℒw× forms a hereditarily undecidable theory in ℒw×. These results generalize similar theorems, due to Tarski, concerning relation algebras and the formalism ℒ×.
What is an inference rule?
Authors: Fagin Ronald , Halpern Joseph Y. , Vardi Moshe Y.
Published: May 2006

What is an inference rule? This question does not have a unique answer. One usually finds two distinct standard answers in the literature; validity inference (σ ⊦vφ for every substitution τ, the validity of τ[σ] entails the validity of τ[φ]), and truth inference (σ⊦l φ if for every substitution τ, the truth of τ[σ] entails the truth of τ[φ]). In this paper we introduce a general semantic framework that allows us to investigate the notion of inference more carefully. Validity inference and truth inference are in some sense the extremal points in our framework. We investigate the relationship between various types of inference in our general framework, and consider the complexity of deciding if an inference rule is sound, in the context of a number of logics of interest: classical propositional logic, a nonstandard propositional logic, various propositional modal logics, and first-order logic.
Abstract classes with few models have ‘homogeneous-universal’ models
Authors: Baldwin J. , Shelah S.
Published: May 2006

This paper is concerned with a class K of models and an abstract notion of submodel ≤. Experience in first order model theory has shown the desirability of finding a ‘monster model’ to serve as a universal domain for K. In the original constructions of Jónsson and Fraïssé, K was a universal class and ordinary substructure played the role of ≤. Working with a cardinal λ satisfying λ<λ = λ guarantees appropriate downward Löwenheim-Skolem theorems; the existence and uniqueness of a homogeneous-universal model appears to depend centrally on the amalgamation property. We make this apparent dependence more precise in this paper.

The major innovation of this paper is the introduction of a weaker notion (chain homogeneous-universal) to replace the natural notion of (K, <)-homogeneous-universal model. Modulo a weak extension of ZFC (provable if V = L), we show (Corollary 5.24) that a class K obeying certain minimal restrictions satisfies a fundamental dichotomy. For arbitrarily large λ, either K has the maximal number of models in power λ or K has a unique chain homogeneous-universal model of power λ. We show (5.25) in a class with amalgamation this dichotomy holds for the notion of K-homogeneous-universal model in the more normal sense.

The methods here allow us to improve our earlier results [5] in two other ways: certain requirements on all chains of a given length are replaced by requiring winning strategies in certain games; the notion of a canonically prime model is avoided. A full understanding of these extensions requires consideration of the earlier papers but we summarize them quickly here.
Counting finite models
Authors: Woods Alan R.
Published: May 2006

Letφbe a monadic second order sentence about a finite structure from a classwhich is closed under disjoint unions and has components. Compton has conjectured that if the number ofnelement structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilitiesν(φ)(μ(φ)respectively) forφalways exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number of single component-structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates.
Possible PCF algebras
Authors: Jech Thomas , Shelah Saharon
Published: May 2006

There exists a familyof sets of countable ordinals such that:

(1) maxBα=α,

(2) ifα∈BβthenBα⊆Bβ,

(3) ifλ≤αandλis a limit ordinal thenBα∩λis not in the ideal generated by theBβ,β<α, and by the bounded subsets ofλ,

(4) there is a partitionofω1such that for everyαand everyn,Bα∩Anis finite.
The entire NS ideal on can be precipitous
Authors: Goldring Noa
Published: May 2006

The main result of this note is showing that if γ and μ are regular uncountable cardinals with γ ≤ μ then the non-stationary ideal (henceforth the NS ideal) on can be precipitous. This strengthens a result of [1] showing, under the same hypotheses, that a restriction of this ideal can be precipitous. See [1, Theorem 29, p. 36]. In fact, we show that even the strongly NS ideal on is precipitous in our model (since the former ideal is a restriction of the latter, the latter's being precipitous is a stronger assertion).

More precisely, by starting with a model of “ZFC + ‘κ is a supercompact cardinal’ + ‘μ < κ is a regular uncountable cardinal’ ”, we generate a model of ZFC where all cardinals below and including μ are not collapsed and where the NS and strongly NS ideals on Pγμ are precipitous, for all regular uncountable γ which are less than or equal to μ.

As far as consistency strength, we can obtain the same result even if κ is only Woodin in the ground model. However, the proof of this result is more complicated than in the case when κ is a supercompact cardinal. Furthermore, there are essentially no new ideas in adapting the proof relative to a supercompact cardinal to that relative to a Woodin cardinal beyond what appears in, e.g., [2]. We therefore give the complete proof relative to the existence of a supercompact cardinal and then briefly sketch the proof relative to the existence of a Woodin cardinal, using [2] as a reference.
Variations on a game of Gale (III): remainder strategies
Authors: Scheepers Marion , Weiss William
Published: May 2006

An infinite set X is given. D. Gale, in correspondence with J. Mycielski, described the following game in which players one and two play an inning per positive integer: In the nth inning one chooses a finite subset Xn of X, and two chooses a point xn from (X1∪ … ∪Xn)\{x1,…,xn−1}. A play

is won by two if . Gale asked whether two could have a winning strategy which depends for each n on knowledge of only the contents of the set

In mathematical terms, is there a function F defined on the collection of finite subsets of X such that:

for every sequence X1, x1, …, Xn, xn,…. where each Xn is a finite subset

of X and for each n

we have

We shall call a strategy of this sort a remainder strategy for two. If there is some finite subset U of X such that F(U) ∉ U, then F cannot be a winning remainder strategy for two, because one can defeat F by choosing U each inning. So, when studying remainder strategies for two we may as well assume that for each finite set U ⊂ X, F(U) ∈ U.
On the number of models of uncountable theories
Authors: Chowdhury Ambar , Pillay Anand
Published: May 2006

In this paper we establish the following theorems.

Theorem A. Let T be a complete first-order theory which is uncountable, Then:

(i) I(∣T∣, T) ≥ ℵ0

(ii) If T is not unidimensional, then for any λ ≥ ∣T∣, I(λ, T) ≥ ℵ0.

Theorem B. Let T be superstable, not totally transcendental and nonmultidimensional. Let θ(x) be a formula of least R∞ rank which does not have Morley rank, and let p be any stationary completion of θ which also fails to have Morley rank. Then p is regular and locally modular.
A very weak square principle
Authors: Foreman Matthew , Magidor Menachem
Published: May 2006

In this paper we explicate a very weak version of the principle □ discovered by Jensen who proved it holds in the constructible universe L. This principle is strong enough to include many of the known applications of □, but weak enough that it is consistent with the existence of very large cardinals. In this section we show that this principle is equivalent to a common combinatorial device, which we call a Jensen matrix. In the second section we show that our principle is consistent with a supercompact cardinal. In the third section of this paper we show that this principle is exactly equivalent to the statement that every torsion free Abelian group has a filtration into σ-balanced subgroups. In the fourth section of this paper we show that this principle fails if you assume the Chang's Conjecture:

In the fifth section of the paper we review the proofs that the various weak squares we consider are strictly decreasing in strength. Section 6 was added in an ad hoc manner after the rest of the paper was written, because the subject matter of Theorem 6.1 fit well with the rest of the paper. It deals with a principle dubbed “Not So Very Weak Square”, which appears close to Very Weak Square but turns out not to be equivalent.
Asymptotic probabilities for second-order existential Kahr-Moore-Wang sentences
Authors: Vedø Anne
Published: May 2006

We show that the 0-1 law does not hold for the class(∀∃∀ without = ) by finding a sentence in this class which almost surely expresses parity. We also show that every recursive real in the unit interval is the asymptotic probability of a sentence in this class. This expands a result by Lidia Tendera, who in 1994 proved that everyrationalnumber in the unit interval is the asymptotic probability of a sentence in the class∀∃∀withequality.
On boolean subalgebras of (ω1)/ctble
Authors: Dow Alan
Published: May 2006

It is well known that every Boolean algebra of size ω1 can be embedded into (ω)/fin. E. van Douwen proved that if CH failed then there is a Boolean algebra of size ω2 which cannot be embedded into (ω1)/ctble. We show that ◇ is equivalent to the statement that a certain natural Boolean algebra of size embeds into (ω1)/ctble. I would like to thank B. Velickovic for many helpful conversations.
Ultrafilters on ω
Authors: Baumgartner James E.
Published: May 2006

We study the I-ultrafilters on ω, where I is a a collection of subsets of a set X, usually ℝ or ω1. The I-ultrafilters usually contain the P-points, often as a small proper subset. We study relations between I-ultrafilters for various I, and closure of I-ultrafilters under ultrafilter sums. We consider, but do not settle, the question whether I-ultrafilters always exist.
A dichotomy for the definable universe
Authors: Hjorth Greg
Published: May 2006

In the presence of large cardinals, or sufficient determinacy, every equivalence relation in either admits a wellordered separating family or continuously reduces E0.
The geometry of forking and groups of finite Morley rank
Authors: Pillay Anand
Published: May 2006

The notion of CM-triviality was introduced by Hrushovski, who showed that his new strongly minimal sets have this property. Recently Baudisch has shown that his new ω1-categorical group has this property. Here we show that any group of finite Morley rank definable in a CM-trivial theory is nilpotent-by-finite, or equivalently no simple group of finite Morley rank can be definable in a CM-trivial theory.
An analogue of Hilbert's tenth problem for p-adic entire functions
Authors: Lipshitz Leonard , Pheidas Thanases
Published: May 2006

Let p be a fixed prime integer, other than 2, Qp the field of p-adic numbers, and Ωp the completion of the algebraic closure of Qp. Let Rp be the ring of entire functions in one variable t over Ωp; that is, Rp is the ring of functions f: Ωp → Qp such that f(t) is given by a power series around 0, of infinite radius of convergence:

and where ∣a∣p is the p-adic norm of a in Ωp. We prove:

Theorem A. The positive existential theory of Rp in the language L = {0, 1, t, +, ·} is undecidable.

Theorem A gives a negative answer to the analogue of Hilbert's tenth problem for Rp in the language L. Related results include those of [2] where it is shown that the first-order theory of entire functions on the complex plane is undecidable and the similar result for analytic functions on the open unit disk (this is due to Denef and Gromov, communicated to us by Cherlin and is as of now unpublished).

It would be desirable to have a similar result in the language which, instead of the variable t, has a predicate for the transcendental (that is, nonconstant) elements of Rp. A related problem is the similar problem for meromorphic functions on the real or p-adic plane or on the unit open or closed disk. These problems seem for the moment rather hard in view of the fact that the analogue of Hilbert's Tenth Problem for the field of rational functions over the complex numbers (or any algebraically closed field of characteristic zero) is an open problem.
The topological Vaught's conjecture and minimal counterexamples
Authors: Becker Howard
Published: May 2006

Let G be a Polish topological group, let X be a Polish space, let J: G × X → X be a Borel-measurable action of G on X, and let A ⊂ X be a Borel set which is invariant with respect to J, i.e., a Borel set of orbits. The following statement, or various equivalent versions of it, is known as the Topological Vaught's Conjecture.

Let (G, X, J, A) be as above. Either A contains only countably many orbits, or else, A contains perfectly many orbits.

We say that A contains perfectly many orbits if there is a perfect set P ⊂ A such that no two elements of P are in the same orbit. (Assuming ¬CH, A contains perfectly many orbits iff it contains 2ℵ0 orbits.) The Topological Vaught's Conjecture implies the usual, model theoretic, Vaught's Conjecture for Lω1ω, since the isomorphism classes are the orbits of an action of the group of permutations of ω; we give details in §0. The “Borel” assumption cannot be weakened for either A or J.

Given a Borel-measurable Polish action (G,X,J) and an invariant Borel set B ⊂ X, we say that B is a minimal counterexample if (G,X,J,B) is a counterexample to the Topological Vaught's Conjecture and for every invariant Borel C ⊂ B, either C or B\C contains only countably many orbits. This paper is concerned with counterexamples to the Topological Vaught's Conjecture (of course, there may not be any), and in particular, with minimal counterexamples. First, there is a theorem on the existence of minimal counterexamples. This theorem was known for the model theoretic case (it is due to Harnik and Makkai), and is here generalized to arbitrary Borel-measurable Polish actions. Second, we study the properties of minimal counterexamples. We give two different necessary and sufficient conditions for a counterexample to be minimal, as well as some consequences of minimality. Some of these results are proved assuming determinacy axioms.This second part seems to be new even in the model theoretic case.
Bisimulations and predicate logic
Authors: Fernando Tim
Published: May 2006

Elementary (first-order) and nonelementary (set-theoretic) aspects of the largest bisimulation are considered with a view toward analyzing operational semantics from the perspective of predicate logic. The notion of a bisimulation is employed in two distinct ways: (i) as an extensional notion of equivalence on programs (or processes) generalizing input/output equivalence (at a cost exceedingover certain transition predicates computable in log space), and (ii) as a tool for analyzing the dependence of transitions on data (which can be shown to be elementary or nonelementary, depending on the formulation of the transitions).
Constructing strongly equivalent nonisomorphic models for unsuperstable theories, Part A
Authors: Hyttinen Tapani , Shelah Saharon
Published: May 2006

We study how equivalent nonisomorphic models an unsuperstable theory can have. We measure the equivalence by Ehrenfeucht-Fraisse games. This paper continues the work started in [HT].
The cupping theorem in R/M
Authors: Yuefei Sui , Zaiyue Zhang
Published: May 2006

It will be proved that the Shoenfield cupping conjecture holds in R/M, the quotient of the recursively enumerable degrees modulo the cappable r.e. degrees. Namely, for any [a], [b] ∈ R/M such that [0] ≺ [b] ≺ [a] there exists [c] ∈ R/M such that [c] ≺ [a] and [a] = [b] ∨ [c].
A decidable variety that is finitely undecidable
Authors: Jeong Joohee
Published: May 2006

We construct a decidable first-order theory T such that the theory of its finite models is undecidable. Moreover, T will be equationally axiomatizable and of finite type.
Common knowledge logic and game logic
Authors: Kaneko Mamoru
Published: May 2006

We show the faithful embedding of common knowledge logic CKL into game logic GL, that is, CKL is embedded into GL and GL is a conservative extension of the fragment obtained by this embedding. Then many results in GL are available in CKL, and vice versa. For example, an epistemic consideration of Nash equilibrium for a game with pure strategies in GL is carried over to CKL. Another important application is to obtain a Gentzen-style sequent calculus formulation of CKL and its cut-elimination. The faithful embedding theorem is proved for the KD4–type propositional CKL and GL, but it holds for some variants of them.
Separating stationary reflection principles
Authors: Larson Paul
Published: May 2006

We present a variety of (ω, ∞)-distributive forcings which when applied to models of Martin's Maximum separate certain well known reflection principles. In particular, we do this for the reflection principles SR, SRα (α ≤ ω1), and SRP.
Yet another hierarchy theorem
Authors: Kubierschky Max
Published: May 2006

n + 1 nested k-ary fixed point operators are more expressive than n. This holds on finite structures for all sublogics of partial fixed point logic PFP that can express conjunction, existential quantification and deterministic transitive closure of binary relations using at most k-ary fixed point operators and that are closed against subformulas. Among those are a lot of popular fixed point logics.
The ground-negative fragment of first-order logic is -complete
Authors: Voronkov Andrei
Published: May 2006

We prove that for a natural class of first-order formulas the validity problem is -complete.
Heights of models of ZFC and the existence of end elementary extensions II
Authors: Villaveces Andrés
Published: May 2006

The existence of End Elementary Extensions of modelsM of ZFC is related to the ordinal height of M, according to classical results due to Keisler, Morley and Silver. In this paper, we further investigate the connection between the height of M and the existence of End Elementary Extensions of M. In particular, we prove that the theory ‘ZFC + GCH + there exist measurable cardinals + all inaccessible non weakly compact cardinals are possible heights of models with no End Elementary Extensions’ is consistent relative to the theory ‘ZFC + GCH + there exist measurable cardinals + the weakly compact cardinals are cofinal in ON’. We also provide a simpler coding that destroys GCH but otherwise yields the same result.
Hyperfinite type structures
Authors: Normann Dag , Palmgren Erik , Stoltenberg-Hansen Viggo
Published: May 2006

The notion of a hyperfinite set comes from nonstandard analysis. Such a set has the internal cardinality of a nonstandard natural number. By a transfer principle such sets share many properties of finite sets. Here we apply this notion to give a hyperfinite model of the Kleene-Kreisel continuous functionals. We also extend the method to provide a hyperfinite characterisation of certain transfinite type structures, thus, through the work of Waagbø [14], constructing a hyperfinite model for Martin-Löf type theory.

This kind of application is not new. Normann [6] gave a characterisation of the Kleene-Kreisel continuous functionals using ‘hyperfinitary’ functionals. The novelty here is that we use a constructive version of hyperfinite functionals and also generalise the method to transfinite types. Many of the results of this paper are constructive, though not the characterisation theorems themselves.

Our characterisation of the Kleene-Kreisel continuous functionals is a supplement to a number of previous characterisations of topological and recursion-theoretical nature, see [6] for a brief survey. Altogether these characterisations show that the original concept of Kleene and Kreisel forms the correct mathematical model of the idea of finitely based functions of finite types.

There is, however, no a priori reason to believe that there is a canonical way to extend the continuous functionals to cover transfinite objects of transfinite type used in, e.g., type theory. Our characterisation of Waagbø's model indicates that the model is natural, not only seen from domain theory but from a higher perspective. Normann and Waagbø (unpublished) have subsequently obtained a limit-space characterisation that further supports this view.
Combinatorial properties of filters and open covers for sets of real numbers
Authors: Laflamme Claude , Scheepers Marion
Published: May 2006

We analyze combinatorial properties of open covers of sets of real numbers by using filters on the natural numbers. In fact, the goal of this paper is to characterize known properties related to ω-covers of the space in terms of combinatorial properties of filters associated with these ω-covers. As an example, we show that all finite powers of a setof real numbers have the covering property of Menger if, and only if, each filter on ω associated with its countable ω-cover is a P+filter.
The least measurable can be strongly compact and indestructible
Authors: Apter Arthur W. , Gitik Moti
Published: May 2006

We show the consistency, relative to a supercompact cardinal, of the least measurable cardinal being both strongly compact and fully Laver indestructible. We also show the consistency, relative to a supercompact cardinal, of the least strongly compact cardinal being somewhat supercompact yet not completely supercompact and having both its strong compactness and degree of supercompactness fully Laver indestructible.
Discretely ordered modules as a first-order extension of the cutting planes proof system
Authors: Krajíček Jan
Published: May 2006

We define a first-order extension LK(CP) of the cutting planes proof system CP as the first-order sequent calculus LK whose atomic formulas are CP-inequalities ∑i ai · xi ≥ b (xi's variables, ai's and b constants). We prove an interpolation theorem for LK(CP) yielding as a corollary a conditional lower bound for LK(CP)-proofs. For a subsystem R(CP) of LK(CP), essentially resolution working with clauses formed by CP-inequalities, we prove a monotone interpolation theorem obtaining thus an unconditional lower bound (depending on the maximum size of coefficients in proofs and on the maximum number of CP-inequalities in clauses). We also give an interpolation theorem for polynomial calculus working with sparse polynomials.

The proof relies on a universal interpolation theorem for semantic derivations [16, Theorem 5.1].

LK(CP) can be viewed as a two-sorted first-order theory of Z considered itself as a discretely ordered Z-module. One sort of variables are module elements, another sort are scalars. The quantification is allowed only over the former sort. We shall give a construction of a theory LK(M) for any discretely ordered module M (e.g., LK(Z) extends LK(CP)). The interpolation theorem generalizes to these theories obtained from discretely ordered Z-modules. We shall also discuss a connection to quantifier elimination for such theories.

We formulate a communication complexity problem whose (suitable) solution would allow to improve the monotone interpolation theorem and the lower bound for R(CP).
Topological completeness for higher-order logic
Authors: Awodey S. , Butz C.
Published: May 2006

Using recent results in topos theory, two systems of higher-order logic are shown to be complete with respect to sheaf models over topological spaces—so-called “topological semantics”. The first is classical higher-order logic, with relational quantification of finitely high type; the second system is a predicative fragment thereof with quantification over functions between types, but not over arbitrary relations. The second theorem applies to intuitionistic as well as classical logic.
A note on Lascar strong types in simple theories
Authors: Kim Byunghan
Published: May 2006

LetTbe a countable, small simple theory. In this paper, we prove that for suchT, the notion of Lascar strong type coincides with the notion of strong type, over an arbitrary set.
Proof systems for probabilistic uncertain reasoning
Authors: Paris J. , Vencovská A.
Published: May 2006

The paper describes and proves completeness theorems for a series of proof systems formalizing common sense reasoning about uncertain knowledge in the case where this consists of sets of linear constraints on a probability function.
Interpretability over peano arithmetic
Authors: Strannegård Claes
Published: May 2006

We investigate the modal logic of interpretability over Peano arithmetic. Our main result is a compactness theorem that extends the arithmetical completeness theorem for the interpretability logic ILMω. This extension concerns recursively enumerable sets of formulas of interpretability logic (rather than single formulas). As corollaries we obtain a uniform arithmetical completeness theorem for the interpretability logic ILM and a partial answer to a question of Orey from 1961. After some simplifications, we also obtain Shavrukov's embedding theorem for Magari algebras (a.k.a. diagonalizable algebras).
A hierarchy of maps between compacta
Authors: Bankston Paul
Published: May 2006

Let CH be the class of compacta (i.e., compact Hausdorff spaces), with BS the subclass of Boolean spaces. For each ordinal α and pair (K, L) of subclasses of CH, we define Lev≥α(K, L), the class of maps of level at least α from spaces in K to spaces in L, in such a way that, for finite α, Lev≥α(BS, BS) consists of the Stone duals of Boolean lattice embeddings that preserve all prenex first-order formulas of quantifier rank α. Maps of level ≥ 0 are just the continuous surjections, and the maps of level ≥ 1 are the co-existential maps introduced in [8]. Co-elementary maps are of level ≥ω a for all ordinals α: of course in the Boolean context, the co-elementary maps coincide with the maps of level ≥ ω. The results of this paper include:

(i) every map of level ≥ ωis co-elementary;

(ii) the limit maps of an co-indexed inverse system of maps of level ≥ α are also of level ≥ α; and

(iii) if K is a co-elementary class, k > ω and Lev≥k(K,K) = Lev≥k+1(K,K), then Lev≥1(K,K) = Lev≥(K,K).

A space X ∈ K is co-existentially closed inK if Lev≥0(K, X) = Lev≥1(K,X). Adapting the technique of “adding roots,” by which one builds algebraically closed extensions of fields (and, more generally, existentially closed extensions of models of universal-existential theories), we showed in [8] that every infinite member of a co-inductive co-elementary class (such as CH itself, BS, or the class CON of continua) is a continuous image of a space of the same weight that is co-existentially closed in that class. We show here that every compactum that is co-existentially closed in CON (a co-existentially closed continuum) is both indecomposable and of covering dimension one.
Strong axioms of infinity inNFU
Authors: Holmes M. Randall
Published: May 2006

This paper discusses a sequence of extensions ofNFU, Jensen's improvement of Quine's set theory “New Foundations” (NF) of [16].

The original theoryNFof Quine continues to present difficulties. After 60 years of intermittent investigation, it is still not known to be consistent relative to any set theory in which we have confidence. Specker showed in [20] thatNFdisproves Choice (and so proves Infinity). Even if one assumes the consistency ofNF, one is hampered by the lack of powerful methods for proofs of consistency and independence such as are available for use withZFC; very clever work has been done with permutation methods, starting with [18] and [5], and exemplified more recently by [14], but permutation methods can only be applied to show the consistency or independence of unstratified sentences (see the definition ofNFUbelow for a definition of stratification). For example, there is no method available to determine whether the assertion “the continuum can be well-ordered” is consistent with or independent ofNF. There is one substantial independence result for an assertion with nontrivial stratified consequences, using metamathematical methods: this is Orey's proof of the independence of the Axiom of Counting fromNF(see below for a statement of this axiom).

We mention these difficulties only to reassure the reader of their irrelevance to the present work. Jensen's modification of “New Foundations” (in [13]), which was to restrict extensionality to sets, allowing many non-sets (urelements) with no elements, has almost magical effects.