bluuebunny/crossref_metadata_2025 huggingface dataset:
Determinacy of Banach games
Authors: Becker Howard
Published: May 2006

For any A ⊂ R, the Banach game B(A) is the following infinite game on reals: Players I and II alternately play positive real numbers a1; a2, a3, a4,… such that for n > 1, an < an−1. Player I wins iff ai exists and is in A.

This type of game was introduced by Banach in 1935 in the Scottish Book [15], Problem 43. The (rather vague) problem which Banach posed was to characterize those sets A for which I (II) has a winning strategy in B(A). (There are three parts to Problem 43. In the first, Mazur defined a game G**(A) for every set A ⊂ R and conjectured that II has a winning strategy in G**(A) iff A is meager and I has a winning strategy in G**(A) iff A is comeager in some neighborhood; this conjecture was proved by Banach. Presumably Banach had this result in mind when he asked the question about B(A), and hoped for a similar type of characterization.) Incidentally, Problem 43 of the Scottish Book appears to be the first time infinite games of any sort were studied by mathematicians.

This paper will not provide the reader with any answer to Banach's question. I know of no nontrivial way to characterize when player I (or II) wins, and I suspect there is none. This paper is concerned with a different (also rather vague) question: For which sets A is the Banach game B(A) determined? To say that B(A) is determined means, of course, that one of the players has a winning strategy for B(A).
Variations on promptly simple sets
Authors: Maass Wolfgang
Published: May 2006

In this paper we answer the question of whether all low sets with the splitting property are promptly simple. Further we try to make the role of lowness properties and prompt simplicity in the construction of automorphisms of the lattice of r.e. (recursively enumerable) sets more perspicuous. It turns out that two new properties of r.e. sets, which are dual to each other, are essential in this context: the prompt and the low shrinking property.

In an earlier paper [4] we had shown (using Soare's automorphism construction [10] and [12]) that all r.e. generic sets are automorphic in the lattice ℰ of r.e. sets under inclusion. We called a set A promptly simple if Ā is infinite and there is a recursive enumeration of A and the r.e. sets (We)e∈N such that if We is infinite then there is some element (or equivalently: infinitely many elements) x of We such that x gets into A “promptly” after its appearance in We (i.e. for some fixed total recursive function f we have x ∈ Af(s), where s is the stage at which x entered We). Prompt simplicity in combination with lowness turned out to capture those properties of r.e. generic sets that were used in the mentioned automorphism result. In a following paper with Shore and Stob [7] we studied an ℰ-definable consequence of prompt simplicity: the splitting property.
Remarks on weak notions of saturation in models of Peano arithmetic
Authors: Kaufmann Matt , Schmerl James H.
Published: May 2006

This paper is a sequel to our earlier paper [2] entitled Saturation and simple extensions of models of Peano arithmetic. Among other things, we will answer some of the questions that were left open there. In §1 we consider the question of whether there are lofty models of PA which have no recursively saturated, simple extensions. We are still unable to answer this question; but we do show in that section that these models are precisely the lofty models which are not recursively saturated and which are κ-like for some regular κ. In §2 we use diagonal methods to produce minimal models of PA in which the standard cut is recursively definable, and other minimal models in which the standard cut is not recursively definable. In §3 we answer two questions from [2] by exhibiting countable models of PA which, in the terminology of this paper, are uniformly ω-lofty but not continuously ω-lofty and others which are continuously ω-lofty but not recursively saturated. We also construct a model (assuming ◇) which is not recursively saturated but every proper, simple cofinal extension of which is ℵ1-saturated. Finally, in §4 we answer another question from [2] by proving that for regular κ ≥ ℵ1; every κ-saturated model of PA has a κ-saturated proper, simple extension which is not κ+-saturated.

Our notation and terminology are quite standard. Anything unfamiliar to the reader and not adequately denned here is probably defined in §1 of [2]. All models considered are models of Peano arithmetic.
Alfred Tarski's work in model theory
Authors: Vaught Robert L.
Published: May 2006

We will consider Tarski's work in pure model theory and classical logic. His work in applied model theory—the model theory of various special theories—is discussed by Doner and van den Dries [1987], and McNulty [1986]. (However, the separation of “pure” and “applied” only becomes natural as the subjects mature; so we shall discuss applied model theory at least to some extent in Tarski's earlier work.)

Alfred Tarski (1901–1983) was awarded a Ph.D. in mathematics at Warsaw University in 1924. His teachers included the two leaders of the renowned Polish logic school, the logician-philosophers L. Leśniewski and J. Łukasiewicz. (Very soon Tarski was recognized as the third leader of the school.) Another teacher was the philosopher T. Kotarbiński, to whom Tarski dedicated his collected papers [56m]. Leśniewski was Tarski's thesis advisor; he transmitted to Tarski his interests in the metalanguage and in the theory of definition. Tarski's thesis ([23a], [24]) was about protothetic—the sentential calculus augmented by quantifiable variables ranging over truth functions. Its main result was that all the connectives are definable using only ↔ and ∀. By the same year, 1924, Tarski also had begun his prolific writings in set theory, and had discovered together with S. Banach, the leader of the Polish mathematicians, their famous “paradox” [24d] in measure theory. (For details see Lévy [1987].)

In 1927-29 Tarski held a seminar at Warsaw University on results he obtained in 1926-28. The seminar lay at the heart of what is now called model theory. The brief history of model theory up to that time had begun with the paper of L. Löwenheim [1915].
Bad models in nice neighborhoods
Authors: Millar Terry
Published: May 2006

This paper contains an example of a decidable theory which has

1) only a countable number of countable models (up to isomorphism);

2) a decidable saturated model; and

3) a countable homogeneous model that is not decidable.

By the results in [1] and [2], this can happen if and only if the set of types realized by the homogeneous model (the type spectrum of the model) is not .

If Γ and Σ are types of a theory T, define Γ ◁ Σ to mean that any model of T realizing Γ must realize Σ. In [3] a decidable theory is constructed that has only countably many countable models, only recursive types, but whose countable saturated model is not decidable. This is easy to do if the restriction on the number of countable models is lifted; the difficulty arises because the set of types must be recursively complex, and yet sufficiently related to control the number of countable models. In [3] the desired theory T is such that

is a linear order with order type ω*. Also, the set of complete types of T is not . The last feature ensures that the countable saturated model is not decidable; the first feature allows the number of countable models to be controlled.
Nonsplitting subset of κ(κ+)
Authors: Gitik Moti
Published: May 2006

Assuming the existence of a supercompact cardinal, we construct a model of ZFC + (There exists a nonsplitting stationary subset of ). Answering a question of Uri Abraham [A], [A-S], we prove that adding a real to the world always makes stationary
Polynomial rings and weak second-order logic
Authors: Bauval Anne
Published: May 2006

This article is a rewriting of my Ph.D. Thesis, supervised by Professor G. Sabbagh, and incorporates a suggestion from Professor B. Poizat. My main result can be crudely summarized (but see below for detailed statements) by the equality: first-order theory of F[Xi]i∈I = weak second-order theory of F.

§I.1. Conventions. The letter F will always denote a commutative field, and I a nonempty set. A field or a ring (A; +, ·) will often be written A for short. We shall use symbols which are definable in all our models, and in the structure of natural numbers (N; +, ·):

— the constant 0, defined by the formula Z(x): ∀y (x + y = y);

— the constant 1, defined by the formula U(x): ∀y (x · y = y);

— the operation ∹ x − y = z ↔ x = y + z;

— the relation of division: x ∣ y ↔ ∃ z(x · z = y).

A domain is a commutative ring with unity and without any zero divisor.

By “… → …” we mean “… is definable in …, uniformly in any model M of L”.

All our constructions will be uniform, unless otherwise mentioned.

§I.2. Weak second-order models and languages. First of all, we have to define the models Pf(M), Sf(M), Sf′(M) and HF(M) associated to a model M = {A; ℐ) of a first-order language L [CK, pp. 18–20]. Let L1 be the extension of L obtained by adjunction of a second list of variables (denoted by capital letters), and of a membership symbol ∈. Pf(M) is the model (A, Pf(A); ℐ, ∈) of L1, (where Pf(A) is the set of finite subsets of A. Let L2 be the extension of L obtained by adjunction of a second list of variables, a membership symbol ∈, and a concatenation symbol ◠.
A note on nonmultidimensional superstable theories
Authors: Pillay Anand , Steinhorn Charles
Published: May 2006

In this paper we prove that if T is the complete elementary diagram of a countable structure and is a theory as in the title, then Vaught's conjecture holds for T. This result is Theorem 7, below. In the process of establishing this proposition, in Theorem 3 we give a sufficient condition for a superstable theory having only countably many types without parameters to be ω-stable. Familiarity with the rudiments of stability theory, as presented in [3] and [4], will be supposed throughout. The notation used is, by now, standard.

We begin by giving a new proof of a lemma due to J. Saffe in [6]. For T stable, recall that the multiplicity of a type p over a set A ⊆ ℳ ⊨ T is the cardinality of the collection of strong types over A extending p.

Lemma 1 (Saffe). Let T be stable, A ⊆ ℳ ⊨ T. If t(b̄, A) has infinite multiplicity and t(c̄, A) has finite multiplicity, then t(b̄, A ∪ {c̄}) has infinite multiplicity.

Proof. We suppose not and work for a contradiction. Let ‹b̄γ:γ ≤ α›, α ≥ ω, be a list of elements so that t(b̄γ, A) = t(b̄, A) for all γ ≤ α, and st(b̄γ, A) ≠ st(b̄δ, A) for γ ≠ δ. Furthermore, let c̄γ satisfy t(b̄γ∧c̄γ, A) = t(b̄ ∧ c̄, A) for each γ < α.

Since t(c̄, A) has finite multiplicity, we may assume for all γ, δ < α. that st(c̄γ, A) = st(c̄δ, A). For each γ < α there is an automorphism fγ of the so-called “monster model” of T (a sufficiently large, saturated model of T) that preserves strong types over A and is such that f(c̄γ) = c̄0.
One theorem of Zil′ber's on strongly minimal sets
Authors: Buechler Steven
Published: May 2006

Suppose D ⊂ M is a strongly minimal set definable in M with parameters from C. We say D is locally modular if for all X, Y ⊂ D, with X = acl(X ∪ C)∩D, Y = acl(Y ∪ C) ∩ D and X ∩ Y ≠ ∅,

We prove the following theorems.

Theorem 1. Suppose M is stable and D ⊂ M is strongly minimal. If D is not locally modular then inMeqthere is a definable pseudoplane.

(For a discussion of Meq see [M, §A].) This is the main part of Theorem 1 of [Z2] and the trichotomy theorem of [Z3].

Theorem 2. Suppose M is stable and D, D′ ⊂ M are strongly minimal and nonorthogonal. Then D is locally modular if and only if D′ is locally modular.
Périodicité des théories élémentaires des corps de séries formelles itérées
Authors: Delon Françoise
Published: May 2006

C. U. Jensen suggested the following construction, starting from a field K:

and asked when two fields Kα and Kβ are equivalent. We give a complete answer in the case of a field K of characteristic 0.
Some model theory of modules. III. On infiniteness of sets definable in modules
Authors: Rothmaler Philipp
Published: May 2006

This is the third and last part of an investigation in several topics of first order model theory of modules which I began in Some model theory of modules. I. On total transcendence of modules (this Journal, vol. 48 (1983), pp. 570–574) and continued in Some model theory of modules. II. On stability and categoricity of flat modules (this Journal, vol. 48 (1983), pp. 970–985). Throughout I refer to these papers as “Part I” and “Part II”.

Although these parts are only loosely connected, I will tacitly use the notation and preliminaries already introduced in the preceding ones. Further details are given in §0. Concerning Part II, the reader is assumed to be familiar with most of §1, a very small part of §4, and the criterion for elementary equivalence of modules over regular rings given in §3 (Lemma 20) of that part.

Using those tools in this paper I consider completeness of the (elementary) theory of all modules (and of some of its extensions) (§2), and eliminability of cardinality quantifiers in the elementary theories of modules (§3).

§2 is almost entirely devoted to a new short proof based on the technique developed in Part II of a theorem of Tukavkin which seems to be the first relevant result concerning the completeness of the theory of all modules (after the simple observation that any theory of infinite vector spaces is complete).
Some undecidability results in strong algebraic languages
Authors: Kalfa Cornelia
Published: May 2006

The recursively unsolvable halting problem for Turing machines is reduced to the problem of the existence or not of an algorithm for deciding whether a field is finite. The latter problem is further reduced to the decision problem of each of properties

for recursive sets Σ of equations of strong algebraic languages with infinitely many operation symbols.

Decision problems concerning properties of sets of equations were first raised by Tarski [9] and subsequently examined by Perkins [6], McKenzie [4], McNulty [5] and Pigozzi [7]. Perkins is the only one who studied recursive sets; the others investigated finite sets. Since the undecidability of properties Pi for recursive sets of equations does not imply any answer to the corresponding decision problems for finite sets, the latter problems remain open.

The work presented here is part of my Ph.D. thesis [2]. I thank Wilfrid Hodges, who supervised it.

An algebraic language is a first-order language with equality but without relation symbols. It is here denoted by , where Qi is an operation symbol and cj, is a constant symbol.
A recursion theoretic analysis of the clopen Ramsey theorem
Authors: Clote Peter
Published: May 2006

Solovay has shown that if F: [ω]ω → 2 is a clopen partition with recursive code, then there is an infinite homogeneous hyperarithmetic set for the partition (a basis result). Simpson has shown that for every 0α, where α is a recursive ordinal, there is a clopen partition F: [ω]ω → 2 such that every infinite homogeneous set is Turing above 0α (an anti-basis result). Here we refine these results, by associating the “order type” of a clopen set with the Turing complexity of the infinite homogeneous sets. We also consider the Nash-Williams barrier theorem and its relation to the clopen Ramsey theorem.
Questions about quantifiers
Authors: van Benthem Johan
Published: May 2006

The importance of the logical ‘generalized quantifiers’ (Mostowski [1957]) for the semantics of natural language was brought out clearly in Barwise & Cooper [1981]. Basically, the idea is that a quantifier phrase QA (such as “all women”, “most children”, “no men”) refers to a set of sets of individuals, viz. those B for which (QA)B holds. Thus, e.g., given a fixed model with universe E,

where ⟦A⟧ is the set of individuals forming the extension of the predicate “A” in the model. This point of view permits an elegant and uniform semantic treatment of the subject-predicate form that pervades natural language.

Such denotations of quantifier phrases exhibit familiar mathematical structures. Thus, for instance, all A produces filters, and no A produces ideals. The denotation of most A is neither; but it is still monotone, in the sense of being closed under supersets. Mere closure under subsets occurs too; witness a quantifier phrase like few A. These mathematical structures are at present being used in organizing linguistic observations and formulating hypotheses about them. In addition to the already mentioned paper of Barwise & Cooper, an interesting example is Zwarts [1981], containing applications to the phenomena of “negative polarity” and “conjunction reduction”. In the course of the latter investigation, several methodological issues of a wider logical interest arose, and these have inspired the present paper.

In order to present these issues, let us shift the above perspective, placing the emphasis on quantifier expressions per se (“all”, “most”, “no”, “some”, etcetera), viewed as denoting relations Q between sets of individuals.
Spector forcing
Authors: Henle J. M.
Published: May 2006

Forcing with [Κ]κ over a model of set theory with a strong partition cardinal, M. Spector produced a generic ultrafilter G on κ such that κκ/G is not well-founded.

Theorem. Let G be Spector-generic over a model M of , for all α < κ.

1) Every cardinal (well-ordered or not) of M is a cardinal of M[G].

2) If A ∈ M[G] is a well-ordered subset of M, then Ae M. Let Φ = Κκ/G.

3) There is an ultrafilter U on Φ such that every member of U has a subset of type Φ, and the intersection of any well-ordered subset of U is in U.

4) Φ satisfies for all α <ℵ1 and all ordinals β.

5) There is a linear order Φ′ with property 3) above which is not “weakly compact”, i.e., Φ′ ↛ (Φ′)2.
An extension of the nondiamond theorem in classical and α-recursion theory
Authors: Ambos-Spies Klaus
Published: May 2006

Lachlan's nondiamond theorem [7, Theorem 5] asserts that there is no embedding of the four-element Boolean algebra (diamond) in the recursively enumerable degrees which preserves infima, suprema, and least and greatest elements. Lachlan observed that, essentially by relativization, the theorem can be extended to

Using the Sacks splitting theorem he concluded that there exists a pair of r.e. degrees which does not have an infimum, thus showing that the r.e. degrees do not form a lattice.

We will first prove the following extension of (1):

where an r.e. degree a is non-b-cappable if . From (2) we obtain more information about pairs of r.e. degrees without infima: For every nonzero low r.e. degree there exists an incomparable one such that the two degrees do not have an infimum and there is an r.e. degree which is not half of a pair of incomparable r.e. degrees which has an infimum in the low r.e. degrees. Probably the most interesting corollary of (2) is that the join of any cappable r.e. degree (i.e. half of a minimal pair) and any low r.e. degree is incomplete. Consequently there is an incomplete noncappable degree above every incomplete r.e. degree. Cooper's result [3] that ascending sequences of uniformly r.e. degrees can have minimal upper bounds in the set R of r.e. degrees is another corollary of (2).
On Σ11 equivalence relations with Borel classes of bounded rank
Authors: Sami Ramez L.
Published: May 2006

In Baire space we define a sequence of equivalence relations ‹Ev ∣ v < , each Ev being with classes in + v + 1 and such that (i) Ev does not have perfectly many classes, and (ii) is countable iff < ω1. This construction can be extended cofinally in . A new proof is given of a theorem of Hausdorff on partitions of R into ω1 many sets.
Extension of relatively σ-additive probabilities on Boolean algebras of logic
Authors: Amer Mohamed A.
Published: May 2006

Contrary to what is stated in Lemma 7.1 of [8], it is shown that some Boolean algebras of finitary logic admit finitely additive probabilities that are not σ-additive. Consequences of Lemma 7.1 are reconsidered. The concept of a C-σ-additive probability ℬ (where ℬ and C are Boolean algebras, and ℬ ⊆ C) is introduced, and a generalization of Hahn's extension theorem is proved. This and other results are employed to show that every S̄(L)-σ-additive probability on s̄(L) can be extended (uniquely, under some conditions) to a σ-additive probability on S̄(L), where L belongs to a quite extensive family of first order languages, and S̄(L) and s̄(L) are, respectively, the Boolean algebras of sentences and quantifier free sentences of L.
Provability in finite subtheories of PA and relative interpretability: a modal investigation
Authors: Montagna Franco
Published: May 2006

By Solovay's theorem [16], the modal logic of provability GL gives a complete description of the propositional schemata involving the provability predicate PrPA(x) for Peano arithmetic PA, which are provable in PA. However, many important aspects of provability cannot be fully expressed in terms of PrPA(x). For this reason, many authors have introduced extensions of GL which take account either of Rosser constructions or of other important metamathematical formulas (see, for example, [5], [6], [14], [16], and [19]). In this paper, we concentrate on the modal logic of the provability predicate for finitely axiomatizable subtheories of PA; the interest of this modal logic is based on the following facts. First of all, it provides a modal translation of a very important property of PA, namely the essential reflexiveness. Secondly, in view of Orey's theorem [10] it constitutes a possible approach to the study of interpretability of finite extensions of PA. Indeed, by Orey's theorem PA + θ is interpretable in PA + θ′ iff for every n, and, therefore, relative interpretability of finitely axiomatizable extensions of PA can be expressed by means of the provability predicate for finitely axiomatizable subtheories of PA.

In §1, we introduce three modal logics extending GL and discuss their arithmetical interpretations; §2 deals with Kripke semantics for two of these logics. In §3, a theorem on arithmetical completeness is shown, which characterizes the logic of the provability predicate for finitely axiomatizable subtheories of PA; a uniform version of this theorem is proved in §4.
Finite automata, real time processes and counting problems in bounded arithmetics
Authors: Kutyłowski Mirosław
Published: May 2006

In this paper we present a negative solution of counting problems for some classes slightly different from bounded arithmetic (Δ0sets). To get the results we study properties of chains of finite automata.
Initial segments of Δ2n+11-degrees
Authors: Kastanas Ilias G.
Published: May 2006

A standard result about hyperdegrees is proved (under PD) for all Δ2n+11-degrees.
On ultracoproducts of compact hausdorff spaces
Authors: Gurevič R.
Published: May 2006

I present solutions to several questions of Paul Bankston [2] by means of another version of the ultracoproduct construction, and explain the relation of ultracoproduct of compact Hausdorff spaces to other constructions combining topology, algebra and logic.
Set theoretic properties of Loeb measure
Authors: Miller Arnold W.
Published: May 2006

In this paper we ask the question: to what extent do basic set theoretic properties of Loeb measure depend on the nonstandard universe and on properties of the model of set theory in which it lies? We show that, assuming Martin's axiom and κ-saturation, the smallest cover by Loeb measure zero sets must have cardinality less than κ. In contrast to this we show that the additivity of Loeb measure cannot be greater than ω1. Define cof(H) as the smallest cardinality of a family of Loeb measure zero sets which cover every other Loeb measure zero set. We show that card(⌊log2(H)⌋) ≤ cof (H) ≤ card(2H), where card is the external cardinality. We answer a question of Paris and Mills concerning cuts in nonstandard models of number theory. We also present a pair of nonstandard universes M ≼ N and hyperfinite integer H ∈ M such that H is not enlarged by N, 2H contains new elements, but every new subset of H has Loeb measure zero. We show that it is consistent that there exists a Sierpiński set in the reals but no Loeb-Sierpiński set in any nonstandard universe. We also show that it is consistent with the failure of the continuum hypothesis that Loeb-Sierpiński sets can exist in some nonstandard universes and even in an ultrapower of a standard universe.
On topological spaces equivalent to ordinals
Authors: Flum Jörg , Martinez Juan Carlos
Published: May 2006

Let L be one of the topological languages Lt, (L∞ω)t and (Lκω)t. We characterize the topological spaces which are models of the L-theory of the class of ordinals equipped with the order topology. The results show that the role played in classical model theory by the property of being well-ordered is taken over in the topological context by the property of being locally compact and scattered.
The independence of Peano's fourth axiom from Martin-Löf's type theory without universes
Authors: Smith Jan M.
Published: May 2006

In Hilbert and Ackermann [2] there is a simple proof of the consistency of first order predicate logic by reducing it to propositional logic. Intuitively, the proof is based on interpreting predicate logic in a domain with only one element. Tarski [7] and Gentzen [1] have extended this method to simple type theory by starting with an individual domain consisting of a single element and then interpreting a higher type by the set of truth valued functions on the previous type.

I will use the method of Hilbert and Ackermann on Martin-Löf's type theory without universes to show that ¬Eq(A, a, b) cannot be derived without universes for any type A and any objects a and b of type A. In particular, this proves the conjecture in Martin-Löf [5] that Peano's fourth axiom (∀x ϵ N)¬ Eq(N, 0, succ(x)) cannot be proved in type theory without universes. If by consistency we mean that there is no closed term of the empty type, then the construction will also give a consistency proof by finitary methods of Martin-Löf's type theory without universes. So, without universes, the logic obtained by interpreting propositions as types is surprisingly weak. This is in sharp contrast with type theory as a computational system, since, for instance, the proof that every object of a type can be computed to normal form cannot be formalized in first order arithmetic.
Isomorphic but not lower base-isomorphic cylindric set algebras
Authors: Biró B. , Shelah S.
Published: May 2006

This paper belongs to cylindric-algebraic model theory understood in the sense of algebraic logic. We show the existence of isomorphic but not lower base-isomorphic cylindric set algebras. These algebras are regular and locally finite. This solves a problem raised in [N 83] which was implicitly present also in [HMTAN 81]. This result implies that a theorem of Vaught for prime models of countable languages does not continue to hold for languages of any greater power.
On the transversal hypothesis and the weak kurepa hypothesis
Authors: Walker D. J.
Published: May 2006

In this paper the theory of the core model K is applied to study certain combinatorial principles. These principles concern the existence of families of almost disjoint functions. The first, the transversal hypothesis, is defined as follows.

Definition. The transversal hypothesis for κ, T(κ), is the following assertion:

There is a sequence 〈fν: ν < κ+〉 such that

(a) fν: κ → κ regressively for ν < κ+, and

(b) if ν < ξ < κ+, then there is γ < κ such that fν(α) ≠ fξ(α) whenever γ < α < κ.

T(κ) is a simple consequence of the Kurepa hypothesis for κ, i.e. the assertion, KH(κ), that there is a family F ⊂ P(κ) such that and card({X ∩ α: X ϵ F}) ≤ α for ω < α < κ.

The second principle to be studied, the weak Kurepa hypothesis, is a statement of strength intermediate between the Kurepa and transversal hypotheses.

Definition. The weak Kurepa hypothesis for κ, wKH(κ), is the following assertion:

There is a sequence 〈bν: ν < κ+〉 such that

(a) bν ⊂ κ for ν < κ+, and

(b) for each limit λ < κ there is Fλ: {bν ∩ λ: ν < κ+} → λ such that setting fν(λ) = Fλ(bν ∩ λ) for ν < κ+ and limit λ < κ, if ν < ξ < κ+ there is γ < κ such that fν(λ) ≠ fξ(λ) whenever γ < λ < κ and λ is a limit.
Indécidabilité de corps de séries formelles
Authors: Delon Françoise , Rouani Yamina
Published: May 2006

Consider k((G)) in the language of valued fields enriched with a unary predicate for the set of constants and another one for the cross-section. For perfect k, this structure is undecidable if it does not satisfy Kaplansky's conditions.
On the existence of large p-ideals
Authors: Just Winfried , Mathias A. R. D. , Prikry Karel , Simon Petr
Published: May 2006

We prove the existence of p-ideals that are nonmeagre subsets of (ω) under various set-theoretic assumptions.
Incompleteness results in Kripke semantics
Authors: Ghilardi Silvio
Published: May 2006

By means of models in toposes of C-sets (where C is a small category), necessary conditions are found for the minimum quantified extension of a propositional (intermediate, modal) logic to be complete with respect to Kripke semantics; in particular, many well-known systems turn out to be incomplete.
Jump embeddings in the Turing degrees
Authors: Hinman Peter G. , Slaman Theodore A.
Published: May 2006

Since its introduction in [K1-Po], the upper semilattice of Turing degrees has been an object of fascination to practitioners of the recursion-theoretic art. Starting from relatively simple concepts and definitions, it has turned out to be a structure of enormous complexity and richness. This paper is a contribution to the ongoing study of this structure.

Much of the work on Turing degrees may be formulated in terms of the embeddability of certain first-order structures in a structure whose universe is some set of degrees and whose relations, functions, and constants are natural degree-theoretic ones. Thus, for example, we know that if {P, ≤P) is a partial ordering of cardinality at most ℵ1 which is locally countable—each point has at most countably many predecessors—then there is an embedding

where D is the set of all Turing degrees and <T is Turing reducibility. If (P, ≤P) is a countable partial ordering, then the image of the embedding may be taken to be a subset of R, the set of recursively enumerable degrees. Without attempting to make the notion completely precise, we shall call embeddings of the first sort global, in contrast to local embeddings which impose some restrictions on the image set.
A universal inductive inference machine
Authors: Osherson Daniel N. , Stob Michael , Weinstein Scott
Published: May 2006

A paradigm of scientific discovery is defined within a first-order logical framework. It is shown that within this paradigm there exists a formal scientist that is Turing computable and universal in the sense that it solves every problem that any scientist can solve. It is also shown that universal scientists exist for no regular logics that extend first-order logic and satisfy the Löwenheim-Skolem condition.
Π01-classes and Rado's selection principle
Authors: Jockusch C. G. , Lewis A. , Remmel J. B.
Published: May 2006

There are several areas in recursive algebra and combinatorics in which bounded or recursively bounded -classes have arisen. For our purposes we may define a -class to be a set Path(T) of all infinite paths through a recursive tree T. Here a recursive tree T is just a recursive subset of ω<ω, the set of all finite sequences of the natural numbers ω = {0,1,2,…}, which is closed under initial segments. If the tree T is finitely branching, then we say the -class Path(T) is bounded. If T is highly recursive, i.e., if there exists a partial recursive function f: T→ω such that for each node ηЄ T, f(η) equals the number of immediate successors of η, then we say that the -class Path(T) is recursively bounded (r.b.). For example, Manaster and Rosenstein in [6] studied the effective version of the marriage problem and showed that the set of proper marriages for a recursive society S was always a bounded -class and the set of proper marriages for a highly recursive society was always an r.b. -class. Indeed, Manaster and Rosenstein showed that, in the case of the symmetric marriage problem, any r.b. -class could be represented as the set of symmetric marriages of a highly recursive society S in the sense that given any r.b. Π1-class C there is a society Sc such that there is a natural, effective, degree-preserving 1:1 correspondence between the elements of C and the symmetric marriages of Sc. Jockusch conjectured that the set of marriages of a recursive society can represent any bounded -class and the set of marriages of a highly recursive society can represent any r.b. -class. These conjectures remain open. However, Metakides and Nerode [7] showed that any r.b. -class could be represented by the set of total orderings of a recursive real field and vice versa that the set of total orderings of a recursive real field is always an r.b. -class.
A note on subgroups of the automorphism group of a saturated model, and regular types
Authors: Pillay A.
Published: May 2006

Let M be a saturated model of a superstable theory and let G = Aut(M). We study subgroups H of G which contain G(A), A the algebraic closure of a finite set, generalizing results of Lascar [L] as well as giving an alternative characterization of the simple superstable theories of [P]. We also make some observations about good, locally modular regular types p in the context of p-simple types.
A note on direct sums of Friedbergnumberings
Authors: Kummer Martin
Published: May 2006

We show that a translator ƒ: ω → ω from a Gödelnumbering φ into a direct sum η of a r.e. family of Friedbergnumberings satisfies ƒ ≰T0′. In particular, η cannot be a Gödelnumbering.

In the following we use standard notation (cf.[3]): for i ≥ 1, Pi (respectively, Ri) is the set of partial (total) recursive i-place functions; φ is a Gödel numbering of P1. By φi, s we denote a recursive standard approximation for φi, i.e., φi, s is a finite function, φi, s ⊆ φi, s + 1, φi, s ⊆ φi, φi = ⋃ {φi, s ∣ s ≥ 0}, and a canonical index for φi, s can be computed uniformly in i, s (cf.[3, p. 16 f]).

We call v ∈ P2 a numbering of P1 iff {λx.v(i, x)}i ∈ ω = P1; we denote λx.v(i, x) by vi. Let v and γ be numberings of P1. A total function g: ω → ω is called a translator from v into γ iff ∀i: vi = γg(i).
Equational logic of partial functions under Kleene equality: a complete and an incomplete set of rules
Authors: Robinson Anthony
Published: May 2006

When equational logic for partial functions is interpreted using Kleene equality as the predicate, the relation of logical consequence may be said to express what identities of partial functions follow from a given set of identities. In the analogous situation for total functions, there is a complete set of inference rules consisting of reflexivity, symmetry, transitivity, replacement, and substitution; in the case of partial functions, unrestricted substitution fails to be a valid inference rule, and there remains the question of how to obtain a complete set of rules. The first part of the present paper shows that completeness cannot be obtained by a mere restriction of the substitution rule, for a counterexample shows that even a rule allowing substitution in all consequentially valid instances fails, in conjunction with the other four rules, to yield a complete set of rules.

The second part of the paper defines a combined rule of transitivity-substitution which, in conjunction with reflexivity, symmetry, replacement, and substitution only of variables, yields a complete set of rules. The new rule is first stated in a form that allows an unbounded number of premises, and then is altered to a three-premise form. In both forms, the rule suffers from the shortcoming that in its formulation an auxiliary notion of conditional existence is involved, which is given by a recursive syntactic definition. As a result, the set of instantiations of the rule is recursively enumerable, but not (apparently) recursive (assuming a recursive set of premises).
Partially ordered sets and the independence property
Authors: Schmerl James H.
Published: May 2006

No theory of a partially ordered set of finite width has the independence property, generalizing Poizat's corresponding result for linearly ordered sets. In fact, a question of Poizat concerning linearly ordered sets is answered by showing, moreover, that no theory of a partially ordered set of finite width has the multi-order property. It then follows that a distributive lattice is not finite-dimensional iff its theory has the independence property iff its theory has the multi-order property.
Higher order reflection principles
Authors: Marshall R. M. Victoria
Published: May 2006

In [1] and [2] there is a development of a class theory, whose axioms were formulated by Bernays and based on a reflection principle. See [3]. These axioms are formulated in first order logic with ∈:

(A1)Extensionality.

(A2)Class specification. Ifϕis a formula andAis not free inϕ, then

Note that “xis a set“ can be written as “∃u(x∈u)”.

(A3)Subsets.

Note also that “B⊆A” can be written as “∀x(x∈B→x∈A)”.

(A4)Reflection principle. Ifϕ(x)is a formula, then

where “uis a transitive set” is the formula “∃v(u∈v) ∧ ∀x∀y(x∈y∧y∈u→x∈u)” andϕPuis the formulaϕrelativized to subsets ofu.

(A5)Foundation.

(A6)Choice for sets.

We denote byB1the theory with axioms (A1) to (A6).

The existence of weakly compact and-indescribable cardinals for everynis established inB1by the method of defining all metamathematical concepts forB1in a weaker theory of classes where the natural numbers can be defined and using the reflection principle to reflect the satisfaction relation; see [1]. There is a proof of the consistency ofB1assuming the existence of a measurable cardinal; see [4] and [5]. In [6] several set and class theories with reflection principles are developed. In them, the existence of inaccessible cardinals and some kinds of indescribable cardinals can be proved; and also there is a generalization of indescribability for higher-order languages using only class parameters.

The purpose of this work is to develop higher order reflection principles, including higher order parameters, in order to obtain other large cardinals.
U-meager sets when the cofinality and the coinitiality of U are uncountable
Authors: Živaljević Boško
Published: May 2006

Abtract

We prove that every countably determined set C is U-meager if and only if every internal subset A of C is U-meager, provided that the cofinality and coinitiality of the cut U are both uncountable. As a consequence we prove that for such cuts a countably determined set C which intersects every U-monad in at most countably many points is U-meager. That complements a similar result in [KL]. We also give some partial solutions to some open problems from [KL]. We prove that the set , where H is an infinite integer, cannot be expressed as a countable union of countably determined sets each of which is U-meager for some cut U with min{cf(U), ci(U)} ≥ ω1. Also, every Borel, or countably determined set C which is U-meager for every cut U is a countable union of Borel, or countably determined sets respectively, which are U-nowhere dense for every cut U. Further, the class of Borel U-meager sets for min{cf(U),ci(U)} ≥ ω1 coincides with the least family of sets containing internal U-meager sets and closed with respect to the operation of countable union and intersection. The same is true if the phrase “U-meager sets” is replaced by “U-meager for every cut U.”
Working below a high recursively enumerable degree
Authors: Shore Richard A. , Slaman Theodore A.
Published: May 2006

In recent work, Cooper [3, 1990] has extended results of Jockusch and Shore [6, 1984] to show that the Turing jump is definable in the structure given by the Turing degrees and the ordering of Turing reducibility. In his definition of x′ from x, Cooper identifies an order-theoretic property shared by all of the degrees that are recursively enumerable in x and above x. He then shows that x′ is the least upper bound of all the degrees with this property. Thus, the jump of x is identified by comparing the recursively enumerable degrees with other degrees which are not recursively enumerable. Of course, once the jump operator is known to be definable, the relation of jump equivalence x′ = y′ is also known to be a definable relation on x and y. If we consider how much of the global theory of the Turing degrees is sufficient for Cooper's methods, it is immediately clear that his methods can be implemented to show that the jump operator and its weakening to the relation of jump equivalence are definable in any ideal closed under the Turing jump. However, his methods do not localize to , the degrees, or to the recursively enumerable degrees.

This paper fits, as do Shore and Slaman [16, 1990] and [17, to appear], within the general project to develop an understanding of the relationship between the local degree-theoretic properties of a recursively enumerable set A and its jump class. For an analysis of the possibility of defining jump equivalence in , consult Shore [15, to appear] who shows that the relation x(3) = y(3) is definable. In this paper, we will restrict our attention to definitions expressed completely in ℛ (Note: All sets and degrees discussed for the remainder of this paper will be recursively enumerable.) Ultimately, one would like to find some degree-theoretic properties definable in terms of the ordering of Turing reducibility and quantifiers over the recursively enumerable degrees that would define the relation of jump equivalence or define one or more of the jump classes Hn = {w∣ wn = 0n+1} or Ln = {w ∣ wn = 0n}. Such a result could very likely then be used as a springboard to other general definability results for the recursively enumerable degrees. It would be especially interesting to know whether every recursively enumerable degree is definable and whether every arithmetical degree-invariant property of the recursively enumerable sets is definable in .
A transfer theorem for Henselian valued and ordered fields
Authors: Farré Rafel
Published: May 2006

In well-known papers ([A-K1], [A-K2], and [E]) J. Ax, S. Kochen, and J. Ershov prove a transfer theorem for henselian valued fields. Here we prove an analogue for henselian valued and ordered fields. The orders for which this result apply are the usual orders and also the higher level orders introduced by E. Becker in [Bl] and [B2]. With certain restrictions, two henselian valued and ordered fields are elementarily equivalent if and only if their value groups (with a little bit more structure) and their residually ordered residue fields (a henselian valued and ordered field induces in a natural way an order in its residue field) are elementarily equivalent. Similar results are proved for elementary embeddings and ∀-extensions (extensions where the structure is existentially closed).
The undecidability of the disjunction property of propositional logics and other related problems
Authors: Chagrov Alexander , Zakharyaschev Michael
Published: May 2006

‘How can we recognize, given axioms and inference rules of a calculus, whether the calculus has such-and-such property?’ A question of this kind arises whenever we deal with a new logic system. For large families of logics, this question may be considered as an algorithmic problem, and a property is called decidable in a given family if there exists an algorithm which is capable of deciding, for a finite axiomatics of a calculus in the family, whether or not it has the property.

In the class of intermediate propositional logics, for instance, nontrivial properties such as the tabularity, pretabularity, and interpolation property (Maksimova [1972, 1977]) are decidable. However, for many other important properties—decidability, finite model property, disjunction property, Halldén-completeness, etc.—effective criteria were not found in spite of considerable efforts.

In this paper we show that the difficulties in investigating these properties in the classes of intermediate logics and normal modal logics containing S4 are of principal nature, since all of them turn out to be algorithmically undecidable. In other words, there are no algorithms which, given a finite set of axioms of an intermediate or modal calculus, can recognize whether or not it is decidable, Halldén-complete, has the finite model or disjunction property.

The first results concerning the undecidability of properties of calculi seem to have been obtained by Linial and Post [1949], who proved the undecidability of the problem of equivalence to classical calculus in the class of all propositional calculi with the same language as the classical one and the two inference rules: modus ponens and substitution. Kuznetsov [1963] generalized this result having proved the undecidability of the problem of equivalence to any fixed intermediate calculus (for instance, to intuitionistic calculus or even the inconsistent one). However, these results will not hold if we confine ourselves only to the class of intermediate logics, though the problem of equivalence to the undecidable intermediate calculus of Shehtman [1978] is clearly undecidable in this class as well.
Nonisomorphism of lattices of recursively enumerable sets
Authors: Hammond John Todd
Published: May 2006

Let ω be the set of natural numbers, let be the lattice of recursively enumerable subsets of ω, and let A be the lattice of subsets of ω which are recursively enumerable in A. If U, V ⊆ ω, put U =* V if the symmetric difference of U and V is finite.

A natural and interesting question is then to discover what the relation is between the Turing degree of A and the isomorphism class of A. The first result of this form was by Lachlan, who proved [6] that there is a set A ⊆ ω such that A ≇ . He did this by finding a set A ⊆ ω and a set C ϵ A such that the structure ({W ϵ A∣W ⊇ C},∪,∩)/=* is a Boolean algebra and is not isomorphic to the structure ({W ϵ ∣W ⊇ D},∪,∩)/=* for any D ϵ . There is a nonrecursive ordinal which is recursive in the set A which he constructs, so his set A is not (see, for example, Shoenfield [11] for a definition of what it means for a set A ⊆ ω to be ). Feiner then improved this result substantially by proving [1] that for any B ⊆ ω, B′ ≇ B, where B′ is the Turing jump of B. To do this, he showed that for each X ⊆= ω there is a Boolean algebra which is but not and then applied a theorem of Lachlan [6] (definitions of and Boolean algebras will be given in §2). Feiner's result is of particular interest for the case B = ⊘, for it shows that the set A of Lachlan can actually be chosen to be arithmetical (in fact, ⊘′), answering a question that Lachlan posed in his paper. Little else has been known.
A recursion principle for linear orderings
Authors: Oikkonen Juha
Published: May 2006

The idea of this paper is to approach linear orderings as generalized ordinals and to study how they are made from their initial segments. First we look at how the equality of two linear orderings can be expressed in terms of equality of their initial segments. Then we shall use similar methods to define functions by recursion with respect to the initial segment relation. Our method is based on the use of a game where smaller and smaller initial segments of linear orderings are considered. The length of the game is assumed to exceed that of the descending sequences of elements of the linear orderings considered. By use of such game-theoretical methods we can for example extend the recursive definitions of the operations of sum, product and exponentiation of ordinals in a unique and natural way for arbitrary linear orderings. Extensions coming from direct limits do not satisfy our game-theoretic requirements in general. We also show how our recursive definitions allow very simple constructions for fixed points of functions, giving rise to certain interesting linear orderings.
The Cichoń diagram
Authors: Bartoszyński Tomek , Judah Haim , Shelah Saharon
Published: May 2006

We conclude the discussion of additivity, Baire number, uniformity, and covering for measure and category by constructing the remaining 5 models. Thus we complete the analysis of Cichoń's diagram.