bluuebunny/crossref_metadata_2025 huggingface dataset:
The hereditary partial effective functionals and recursion theory in higher types
Authors: Longo G. , Moggi E.
Published: May 2006

A type-structure of partial effective functionals over the natural numbers, based on a canonical enumeration of the partial recursive functions, is developed. These partial functionals, defined by a direct elementary technique, turn out to be the computable elements of the hereditary continuous partial objects; moreover, there is a commutative system of enumerations of any given type by any type below (relative numberings).

By this and by results in [1] and [2], the Kleene-Kreisel countable functionals and the hereditary effective operations (HEO) are easily characterized.
Two weak consequences of 0#
Authors: Gitik M. , Magidor M. , Woodin H.
Published: May 2006

It is proven that the following statement:

“there exists a club C ⊆ κ such that every α ∈ C is an inaccessible cardinal in L and, for every δ a limit point of C, C ∩ δ is almost contained in every club of δ of L”

is equiconsistent with a weakly compact cardinal if δ = ℵ1, and with a weakly compact cardinal of order 1 if δ = ℵ2.
On Π1-automorphisms of recursive linear orders
Authors: Kierstead Henry A.
Published: May 2006

If σ is the order type of a recursive linear order which has a nontrivial automorphism, we let denote the least complexity in the arithmetical hierarchy such that every recursive order of type σ has a nontrivial automorphism of complexity . In Chapter 16 of his book Linear orderings [R], Rosenstein discussed the problem of determining for certain order types σ. For example Rosenstein proved that , where ζ is the order type of the integers, by constructing a recursive linear order of type ζ which has no nontrivial Σ1-automorphism and showing that every recursive linear order of type ζ has a nontrivial Π1-automorphism. Rosenstein also considered linear orders of order type 2 · η, where 2 is the order type of a two-element chain and η is the order type of the rational numbers. It is easily seen that any recursive linear order of type 2 · η has a nontrivial ⊿2-automorphism; he showed that there is a recursive linear order of type 2 · η that has no nontrivial Σ1-automorphism. This left the question, posed in [R] and also by Lerman and Rosenstein in [LR], of whether or ⊿2. The main result of this article is that :
Limit ultrapowers and abstract logics
Authors: Lipparini Paolo
Published: May 2006

We associate with any abstract logic L a family F(L) consisting, intuitively, of the limit ultrapowers which are complete extensions in the sense of L.

For every countably generated [ω, ω]-compact logic L, our main applications are:

(i) Elementary classes of L can be characterized in terms of ≡L only.

(ii) If and are countable models of a countable superstable theory without the finite cover property, then .

(iii) There exists the “largest” logic M such that complete extensions in the sense of M and L are the same; moreover M is still [ω, ω]-compact and satisfies an interpolation property stronger than unrelativized ⊿-closure.

(iv) If L = Lωω(Qx), then cf(ωx) > ω and λω < ωx, for all λ < ωx.

We also prove that no proper extension of Lωω generated by monadic quantifiers is compact. This strengthens a theorem of Makowsky and Shelah. We solve a problem of Makowsky concerning Lκλ-compact cardinals. We partially solve a problem of Makowsky and Shelah concerning the union of compact logics.
Compact numeral representation with combinators
Authors: Krishnamurthy E. V. , Vickers B. P.
Published: May 2006

This paper is concerned with the combinator representation of numeral systems with logarithmic space complexity of symbols. The principle used is based on the lexicographic ordering of words over a finite alphabet.
Complete Boolean ultraproducts
Authors: Canjar R. Michael
Published: May 2006

Throughout this paper, B will always be a Boolean algebra and Γ an ultrafilter on B. We use + and Σ for the Boolean join operation and · and Π for the Boolean meet.

κ is always a regular cardinal. C(κ) is the full structure of κ, the structure with universe κ and whose functions and relations consist of all unitary functions and relations on κ. κB is the collection of all B-valued names for elements of κ. We use symbols f, g, h for members of κB. Formally an element f ∈ κB is a mapping κ → B with the properties that Σα∈κf(α) = 1B and that f(α) · f(β) = 0B whenever α ≠ β. We view f(α) as the Boolean-truth value indicating the extent to which the name f is equal to α, and we will hereafter write ∥f = α∥ for f(α). For every α ∈ κ there is a canonical name fα ∈ κB which has the property that ∥fα = α∥ = 1. Hereafter we identify α and fα.

If B is a κ+-complete Boolean algebra and Γ is an ultrafilter on B, then we may define the Boolean ultraproduct C(κ)B/Γ in the following manner. If ϕ(x0, x1, …, xn) is a formula of Lκ, the language for C(κ) (which has symbols for all finitary functions and relations on κ), and f0, f1, …, fn−1 are elements of κB then we define the Boolean-truth value of ϕ(f0, f1, …, fn−1) as
Correction to “Simple r. e. degree structures”
Authors: Lubarsky Robert S.
Published: May 2006

In the paper mentioned in the title (this Journal, vol. 52 (1987), pp. 208–213), it is shown that if ⊨ “V = HC is recursively inaccessible” is ω-standard -nonstandard, then = s.p.() has at most four r. e. degrees. They are 0 = deg(∅), = deg{e ∣ We is a recursive well-ordering of ω}, = deg{R ∣ ⊨ “R codes a well-ordering”}, and ∨ . Furthermore, 0 < < ∨ and 0 < . Then it is claimed that < < ∨ and = ∨ if are each possible. In fact, < < ∨ always.

The mistake in the argument is that the model ≤T is really a structure on a set, which we may as well take as ω: there is an R ⊆ ω × ω, R ≤T, and ‹ω, R› ≃ . So a copy of coded as a relation on ω is ≤ over . But there is no reason to think that the restriction of the isomorphism of and ‹ω, R› to is Σ1().
Differentially algebraic group chunks
Authors: Pillay Anand
Published: May 2006

We point out that a group first order definable in a differentially closed field K of characteristic 0 can be definably equipped with the structure of a differentially algebraic group over K. This is a translation into the framework of differentially closed fields of what is known for groups definable in algebraically closed fields (Weil's theorem).

I restrict myself here to showing (Theorem 20) how one can find a large “differentially algebraic group chunk” inside a group defined in a differentially closed field. The rest of the translation (Theorem 21) follows routinely, as in [B].

What is, perhaps, of interest is that the proof proceeds at a completely general (soft) model theoretic level, once Facts 1–4 below are known.

Fact 1. The theory of differentially closed fields of characteristic 0 is complete and has quantifier elimination in the language of differential fields (+, ·,0,1, −1,d).

Fact 2. Affine n-space over a differentially closed field is a Noetherian space when equipped with the differential Zariski topology.

Fact 3. If K is a differentially closed field, k ⊆ K a differential field, and a and are in k, then a is in the definable closure of k ◡ iff a ∈ ‹› (where k ‹› denotes the differential field generated by k and).

Fact 4. The theory of differentially closed fields of characteristic zero is totally transcendental (in particular, stable).
The classification of small weakly minimal sets. III: Modules
Authors: Buechler Steven
Published: May 2006

Theorem A. Let M be a left R-module such that Th(M) is small and weakly minimal, but does not have Morley rank 1. Let A = acl(∅) ⋂ M and I = {r ∈ R: rM ⊂ A}. Notice that I is an ideal.

(i) F = R/Iis a finite field.

(ii) Suppose that a, b0,…,bn, ∈ M and . Then there are s, ri ∈ R, i ≤ n, such that sa + Σi≤nribi ∈ A and s ∉ I.

It follows from Theorem A that algebraic closure in M is modular. Using this and results in [B1] and [B2], we obtain

Theorem B. Let M be as in Theorem A. Then Vaught's conjecture holds for Th(M).
Cylindric algebras with terms
Authors: Feldman Norman
Published: May 2006

In this paper we discuss cylindric algebras with terms. The setting is two—sorted algebras—one sort for terms and one for Boolean elements. As with cylindric algebras, a cylindric algebra with terms has its roots in first order predicate logic [HMT1].

Let Σ be a set of sentences in a first order language with terms, equality and variables u0,u1,u2, …, Define a relation ≡Σ on Fm, the set of formulas, by φ ≡Σθ if and only if Σ ⊢ φ ↔ θ, and on Tm, the set of terms, by τ ≡Σσ if and only if Σ ⊢ τ ≈ σ. The operations +, ·, cκ, 0, 1 are defined as usual on equivalence classes. Define , where is σ with τ substituted for all occurrences of uκ. That the operation *κ, for κ < α, is well defined follows from the first order axioms of equality. Let vκ = [uκ]. To establish the link between terms and Booleans, define operations oκ as follows: , where φ' is a variant of φ such that uκ is free for τ in φ′ and is φ′ with τ substituted for all free occurrences of uκ in φ′. From the first order axioms it follows that oκ, for κ < α, is well defined. Finally, instead of diagonal elements, we define a Boolean-valued operation on terms as follows: [τ] e [σ] = [τ ≈ σ].
Poly-separated and ω-stable nilpotent groups
Authors: Nesin Ali
Published: May 2006

Let π be a set of primes. We will call a group π-separated if it can be decomposed as a central product of a π-torsion group of bounded exponent and a π-radicable group. It is easy to see that an abelian π-separated group can in fact be decomposed as a direct product of bounded and π-radicable factors (Lemma 1.1 below). A poly-π-separated group is one which can be obtained from π-separated groups by forming a finite series of group extensions. We will show here:

Theorem 1. Every poly-π-separated nilpotent group is π-separated.

The need for such a result arises in model theory in the case that π is the set of all primes, in which case we refer simply to separated and poly-separated groups. In connection with the conjecture that ω-stable simple groups are algebraic, it is useful to have a structure theory for solvable ω-stable groups analogous to the theory available in the algebraic case over algebraically closed fields. In particular the structure of nilpotent ω-stable groups is of interest, for example in connection with the known result [Zi1], [Ne] that the derived subgroup of a connected solvable ω-stable group of finite Morley rank is nilpotent.

As a model-theoretic application of Theorem 1 we obtain:

Theorem 2. If G is an ω-stable nilpotent group then G may be decomposed as a central product B * D with B and D 0-definable subgroups, B torsion of bounded exponent, and D radicable. In particular, B and D are ω-stable. Furthermore, ω · rk(B ∩ D) ≤ rk D.

Corollary. The ω-stable groups of finite Morley rank are exactly the central products B * D of ω-stable nilpotent groups of finite Morley rank with B torsion of bounded exponent, D radicable, and B ∩ D finite.

In addition to the purely algebraic Theorem 1, these results depend on Macintyre's characterization [Mac] of the ω-stable abelian groups as exactly the separated ones.
Lattice embeddings into the recursively enumerable degrees. II
Authors: Ambos-Spies K. , Lerman M.
Published: May 2006

The problem of characterizing the finite lattices which can be embedded into the recursively enumerable degrees has a long history, which is summarized in [AL]. This problem is an important one, as its solution is necessary if a decision procedure for the ∀∃-theory of the poset of recursively emumerable degrees is to be found. A recursive nonembeddability condition, NEC, which subsumes all known nonembeddability conditions was presented in [AL]. This paper focuses on embeddability. An embeddability condition, EC, is introduced, and we prove that every finite lattice having EC can be embedded (as a lattice) into . EC subsumes all known embeddability conditions.

EC is a Π3 condition which states that certain obstructions to proving embeddability do not exist. It seems likely that the recursive labeled trees used in EC can be replaced with trees which are effectively generated from uniformly defined finite trees, in which case EC would be equivalent to a recursive condition. We do not know whether EC and NEC are complementary. This problem seems to be combinatorial, rather than recursion-theoretic in nature. Our efforts to find a finite lattice satisfying neither EC nor NEC have, to this point, been unsuccessful. It is the second author's conjecture that the techniques for proving embeddability which are used in this paper cannot be refined very much to obtain new embeddability results.

EC is introduced in §2, and the various conditions and definitions are motivated by presenting examples of embeddable lattices and indicating how the embedding proof works in those particular cases. The embedding construction is presented in §3, and the proof in §4.
Definable equivalence relations on algebraically closed fields
Authors: van den Dries Lou , Marker David , Martin Gary
Published: May 2006

This article was inspired by the question: is there a definable equivalence relation on the field of complex numbers, each of whose equivalence classes has exactly two elements? The answer turned out to be no, as we now explain in greater detail.

Let Κ be an algebraically closed field and let E be a definable equivalence relation on Κ. [Note: By “definable” we will always mean “definable with parameters”.] Either E has one cofinite class, or all classes are finite and there is a number d such that all but a finite set of classes have cardinality d. In the latter case let B be the finite set of elements of Κ which are not in a class of size d. We prove the following result.

Theorem 1. a) If char(Κ) = 0 or char(Κ) = p > d, then ∣B∣ ≡ 1 (mod d).

b) If char(Κ) = 2 and d = 2, then ∣B∣ ≡ 0 (mod 2).

c) If char(Κ) = p > 2 and d = p + s, where 1 ≤ s ≤ p/2, then ∣B∣ ≡ p + 1 (mod d).

Furthermore, a)−c) are the only restrictions on ≡B≡.

If one is in the right mood, one can view this theorem as saying that the “algebraic cardinality” of the complex numbers is congruent to 1 (mod n) for every n.

§1 contains a reduction of the problem to the special case where E is induced by a rational function in one variable. §2 contains the main calculations and the proofs of a)−c). §3 contains eight families of examples showing that all else is possible. In §4 we prove an analogous result for real closed fields.
Creativeness and completeness in recursion categories of partial recursive operators
Authors: Montagna Franco , Sorbi Andrea
Published: May 2006

Recursion categories have been proposed by Di Paola and Heller in [DPH] as the basis for a category-theoretic approach to recursion theory, in the context of a more general and ambitious project of a purely algebraic treatment of incompleteness phenomena. The way in which the classical notion of creative set is rendered in this new category-theoretic framework plays, therefore, a central role. This is done in [DPH] (Definition 8.1) by defining the notion of creative domains or, rather, domains which are creative relative to some criterion: thus, in a recursion category, every criterion provides a notion of creativeness.

A basic result on creative domains (cf. [DPH, Theorem 8.13]) is that, under certain assumptions, a version of the classical result, due to Myhill [MYH], stating that every creative set is complete, holds: in a recursion category with equality (i.e. exists for every object X) and having enough atoms, every domain which is creative with respect to atoms is also complete.
The number of pairwise non-elementarily-embeddable models
Authors: Shelah Saharon
Published: May 2006

We get consistency results on I(λ, T, T) under the assumption that D(T) has cardinality > ∣T∣. We get positive results and consistency results on IE(λ, T1, T).

The interest is model-theoretic, but the content is mostly set-theoretic: in Theorems 1–3, combinatorial; in Theorems 4–7 and 11(2), to prove consistency of counterexamples we concentrate on forcing arguments; and in Theorems 8–10 and 11(1), combinatorics for counterexamples; the rest are discussion and problems. In particular:

(A) By Theorems 1 and 2, if T ⊆ T1 are first order countable, T complete stable but ℵ0-unstable, λ > ℵ0, and ∣D(T)∣ > ℵ0, then IE(λ, T1, T) > Min{2λ, ℶ2}.

(B) By Theorems 4,5,6 of this paper, if e.g. V = L, then in some generic extension of V not collapsing cardinals, for some first order T ⊆ T1, ∣T∣ = ℵ0, ∣T1∣ = ℵ1, ∣D(T)∣ = ℵ2 and IE(ℵ2, T1, T) = 1.

This paper (specifically the ZFC results) is continued in the very interesting work of Baldwin on diversity classes [Bl]. Some more advances can be found in the new version of [Sh300] (see Chapter III, mainly §7); they confirm 0.1, 0.2 and 14(1), 14(2).
On ideals and stationary reflection
Authors: Johnson C. A.
Published: May 2006

It is a theorem of Prikry [7] that ifκcarries a uniformη-descendingly complete ultrafilter then the stationary reflection propertyfails. In this paper we will derive similar results, but here from properties of filters (or ideals) rather than ultrafilters.

Throughoutκandηwill denote regular cardinals withη<κ(in particularκwill be uncountable), andIwill denote an ideal onκ, by which we mean a setI⊆P(κ) such that (i)Iis closed under taking subsets and finite unions and (ii)αЄIfor eachα<κ, butκ∉I.Iis said to beμ-complete if it is closed under taking unions of size <μ,I* = {X⊆κ∣κ−XЄI} is the filter dual toIand ifAЄI+(=P(κ) −I), thenI∣Ais the ideal onκgiven byI∣A= {X⊆κ∣X∩AЄI}. Ifh: A→κthenhis said to be (i) unbounded modIif for eachα<κ,h−1(α) = {ξЄA∣h(ξ)<α} ЄIand (ii) a least function forIifhis unbounded modIand wheneverg: A→κis a function, unbounded modI, then {ξЄA∣g{ξ) <h{ξ)} ЄI.
Some uses of dilators in combinatorial problems. II
Authors: Abrusci V. Michele , Girard Jean-Yves , van de Wiele Jacques
Published: May 2006

We study increasing F-sequences, where F is a dilator: an increasing F-sequence is a sequence (indexed by ordinal numbers) of ordinal numbers, starting with 0 and terminating at the first step x where F(x) is reached (at every step x + 1 we use the same process as in decreasing F-sequences, cf. [2], but with “+ 1” instead of “−1”). By induction on dilators, we shall prove that every increasing F-sequence terminates and moreover we can determine for every dilator F the point where the increasing F-sequence terminates.

We apply these results to inverse Goodstein sequences, i.e. increasing (1 + Id)(ω)-sequences. We show that the theorem

every inverse Goodstein sequence terminates

(a combinatorial theorem about ordinal numbers) is not provable in ID1.

For a general presentation of the results stated in this paper, see [1].

We use notions and results concerning the category ON (ordinal numbers), dilators and bilators, summarized in [2, pp. 25–31].
L'axiome de normalité pour les espaces totalement ordonnés
Authors: Haddad Labib , Morillon Marianne
Published: May 2006

We show that the following property (LN) holds in the basic Cohen model as sketched by Jech: The order topology of any linearly ordered set is normal. This proves the independence of the axiom of choice from LN in ZF, and thus settles a question raised by G. Birkhoff (1940) which was partly answered by van Douwen (1985).
Abstract hierarchies and degrees
Authors: Ivanov Ljubomir L.
Published: May 2006

The aim of this paper is to enrich the algebraic-axiomatic approach to recursion theory developed in [1] by an analogue to the classical arithmetical hierarchy and an abstract notion of degree. The results presented here are rather initial and elementary; indeed, the main problem was the very choice of right abstract concepts.
Sequential theories and infinite distributivity in the lattice of chapters
Authors: Stern Alan S.
Published: May 2006

We introduce a notion of complexity for interpretations, which is used to prove some new results about interpretations of sequential theories. In particular, we give a new, elementary proof of Pudlák's theorem that sequential theories are connected. We also demonstrate a counterexample to the infinitary distributive law

in the lattice of chapters, in which the chapters a and bi are compact. (Counterexamples in which a is not compact have been found previously.)
Positive ∑ operations on ordinals and normal filters on greatly mahlo cardinals
Authors: Jech Thomas
Published: May 2006

If ℱ is a normal filter on a regular uncountable cardinal κ, let ║f║ be the ℱ-norm of an ordinal function f. We introduce the class of positive ordinal operations and prove that if F is a positive operation then ║F(f)║ ≥ F(║f║). For each η < κ+ let fη be the canonical ηth function. We show that if F is a ∑ operation then F(fη) = fF(η).

As an application we show that if κ is greatly Mahlo then there are normal filters on κ of order greater than κ+.
Normality and
Authors: Zrotowski R.
Published: May 2006

The main result of this paper is that if κ is not a weakly Mahlo cardinal, then the following two conditions are equivalent:

1. is κ+-complete.

2. is a prenormal ideal.

Our result is a generalization of an announcement made in [Z]. We say that is selective iff for every -function f: κ → κ there is a set X ∈ such that f∣(κ − X) is one-to-one. Our theorem provides a positive partial answer to a question of B. Wȩglorz from [BTW, p. 90], viz.: is every selective ideal with κ+-complete, isomorphic to a normal ideal?

The theorem is also true for fine ideals on [λ]<κ for any κ ≤ λ, i.e. if κ is not a weakly Mahlo cardinal then the Boolean algebra is λ+-complete iff is a prenormal ideal (in the sense of [λ/<κ).
Forcing isomorphism
Authors: Baldwin J. T. , Laskowski M. C. , Shelah S.
Published: May 2006

If two models of a first-order theory are isomorphic, then they remain isomorphic in any forcing extension of the universe of sets. In general however, such a forcing extension may create new isomorphisms. For example, any forcing that collapses cardinals may easily make formerly nonisomorphic models isomorphic. However, if we place restrictions on the partially-ordered set to ensure that the forcing extension preserves certain invariants, then the ability to force nonisomorphic models of some theory T to be isomorphic implies that the invariants are not sufficient to characterize the models of T.

A countable first-order theory is said to be classifiable if it is superstable and does not have either the dimensional order property (DOP) or the omitting types order property (OTOP). If T is not classifiable, Shelah has shown in [5] that sentences in L∞,λ do not characterize models of T of power λ. By contrast, in [8] Shelah showed that if a theory T is classifiable, then each model of cardinality λ is described by a sentence of L∞,λ. In fact, this sentence can be chosen in the . ( is the result of enriching the language by adding for each μ < λ a quantifier saying the dimension of a dependence structure is greater than μ) Further work ([3], [2]) shows that ⊐+ can be replaced by ℵ1.
An existence theorem for a special ultrafilter when 𝔡 = 𝔠
Authors: Moloney James J.
Published: May 2006

For an ultrafilter , consider the ultrapower NN/. 〈an〉/ is in the top sky of NN/ if there exists a sequence 〈bn〉 ∈ NN such that

and

In [M2] we showed, assuming the Continuum Hypothesis, that there are exactly 10 c/p's (where c is the ring of real convergent sequences and p is a prime ideal of c). To get the lower bound we showed that there will be at least 10 c/p's in any model of ZFC where there exist both of the following kinds of ultrafilter:

(i) nonprincipal P-points,

(ii) non-P-points such that when the top sky is removed from NN/, the remaining model has countable cofinality.

In [M2] we showed that the Continuum Hypothesis implies the existence of the ultrafilter in (ii). In this paper we show that its existence is implied by an axiom weaker than the Continuum Hypothesis, in fact weaker than Martin's Axiom, namely,

(*) If is a subset of NN such that for any f: N → N there exists g ∈ such that g(n) > f(n) for all n, then ∣∣ = .
On the number of nonisomorphic models of size |T|
Authors: Chowdhury Ambar
Published: May 2006

Let T be an uncountable, superstable theory. In this paper we prove

Theorem A. If T has finite rank, then I(|T|, T) ≥ ℵ0.

Theorem B. If T is trivial, then I(|T|, T) ≥ ℵ0.
The degrees of conditional problems
Authors: Gao Su
Published: May 2006

In this paper we define and study conditional problems and their degrees. The main result is that the class of conditional degrees is a lattice extending the ordinary Turing degrees and it is dense. These properties are not shared by ordinary Turing degrees. We show that the class of conditional many-one degrees is a distributive lattice. We also consider properties of semidecidable problems and their degrees, which are analogous to r.e. sets and degrees.
The Beth-closure of ℒ(Qα) is not finitely generated
Authors: Hella Lauri , Luosto Kerkko
Published: May 2006

We prove that if ℵα is uncountable and regular, then the Beth-closure of ℒωω(Qα) is not a sublogic of ℒαω(Qn), where Qn is the class of all n-ary generalized quantifiers. In particular, B(ℒωω(Qα)) is not a sublogic of any finitely generated logic; i.e., there does not exist a finite set Q of Lindström quantifiers such that B(ℒωω(Qα)) ≤ ℒωω(Q).
Adding dominating reals with ωω of bounding posets
Authors: Pawlikowski Janusz
Published: May 2006

Let B be the random real forcing. Miller [Mi] asked if there are ZFC models M ⊆ N such that forcing with BM over N adds a dominating real. A YES answer was provided by Judah and Shelah in [JS], where in a long and sophisticated construction they built such models. In this paper we prove that forcing with BV over VI, where I is the infinitely often equal real forcing of [Mi], adds a dominating real over VI. This greatly simplifies the YES answer to Miller's question. Moreover it turns out that B may be replaced here by E, the eventually different real forcing of [Mi]. This answers the second part of Miller's question. We also prove that both side by side products I × B and I × E add a Hechler dominating real over V.

In this section we establish the main result of the paper; namely, we prove that forcing over VI with either of the posets BV or EV adds a dominating real over VI.

First we recall the definitions of I and E from [Mi]. The infinitely often equal real forcing is the set

ordered by extension. Miller [Mi] proves that I is ωω bounding.
Four concepts from “geometrical” stability theory in modules
Authors: Kucera T. G. , Prest M.
Published: May 2006

In [H1] Hrushovski introduced a number of ideas concerning the relations between types which have proved to be of importance in stability theory. These relations allow the geometries associated to various types to be connected. In this paper we consider the meaning of these concepts in modules (and more generally in abelian structures). In particular, we provide algebraic characterisations of notions such as hereditary orthogonality, “p -internal” and “p-simple”. These characterisations are in the same spirit as the algebraic characterisations of such concepts as orthogonality and regularity, that have already proved so useful. Of the concepts that we consider, p-simplicity is dealt with in [H3] and the other three concepts in [H2].

The descriptions arose out of our desire to develop some intuition for these ideas. We think that our characterisations may well be useful in the same way to others, particularly since our examples are algebraically uncomplicated and so understanding them does not require expertise in the model theory of modules. Furthermore, in view of the increasing importance of these notions, the results themselves are likely to be directly useful in the model-theoretic study of modules and, via abelian structures, in more general stability-theoretic contexts. Finally, some of our characterisations suggest that these ideas may be relevant to the algebraic problem of understanding the structure of indecomposable injective modules.
Weakly normal closures of filters on Pκλ
Authors: Shioya Masahiro
Published: May 2006

The study of filters on Pκλ started by Jech [5] as a natural generalization of that of filters on an uncountable regular cardinal κ. Several notions including weak normality have been generalized. However, there are two versions proposed as weak normality for filters on Pκλ. One is due to Abe [1] as a straightforward generalization of weak normality for filters on κ due to Kanamori [6] and the other is due to Mignone [8]. While Mignone's version is weaker than normality, Kanamori-Abe's version is not in general. In fact, Abe [2] has proved, generalizing Kanamori [6], that a filter is weakly normal in the sense of Abe iff it is weakly normal in the sense of Mignone and there exists no disjoint family of cfλ-many positive sets. Therefore Kanamori-Abe's version is essentially a large cardinal property and Mignone's version seems to be the most natural formulation of “weak” normality.

In this paper, we study weak normality in the sense of Mignone. In [8], Mignone studies weak normality of canonically defined filters. We complement his chart and try to find the weakly normal closures of these filters (i.e., the minimal weakly normal filters extending them). Therefore our result is a natural refinement of Carr [4].

It is now well known that combinatorics on Pκλ is not a naive generalization of that on κ. For example, Menas [7] showed that stationarity on Pκλ can be characterized by 2-dimensional regressive functions, but not by 1-dimensional ones when λ is strictly larger than κ. We show in terms of weak normality that combinatorics on Pκλ vary drastically with respect to cfλ.
The McKinsey axiom is not compact
Authors: Wang Xiaoping
Published: May 2006

The canonicity and compactness of the KM system are problems historically important in the development of our understanding of intensional logic (as explained in Goldblatt's paper, The McKinsey axiom is not canonical). The problems, however, were unsolved for years in modal logic. In the beginning of 1990, Goldblatt showed that KM is not canonical in The McKinsey axiom is not canonical. The remaining task is to solve the problem of the compactness of KM. In this paper we present a proof showing that the KM system is not compact.

The symbols of the language of propositional modal logic are as follows:

1. A denumerably infinite set of sentence letters, for example, {p0, P1, p2, …};

2. The Boolean connectives &, ⋁, ¬, →, ↔ and parentheses;

3. The modal operators L and M where M is defined as ¬L¬.

The formation rules of well-formed propositional modal formulae are the formation rules of formulae in classic propositional logic plus the following rule:

If A is a well-formed formula, so is LA.

A normal modal system is a set of formulae that contains all tautologies and the formula

and is closed under the following transformation rules:

Uniform substitution. If A is a theorem, so is every substitution-instance of A.

Modus ponens. If A and A → B are theorems, so is B.

Necessitation. If A is a theorem, so is LA.

Let L be a normal system. Then a set S of formulae is L-consistent if and only if for any formula B, which is the conjunction of some formulae in S, B is not included in L. A set S of formulae is maximal if and only if for every formula A, S either contains A or contains ¬A. A set S of formulae is maximal L-consistent if and only if it is both maximal and L-consistent.
Natural internal forcing schemata extending ZFC: Truth in the universe?
Authors: Melles Garvin
Published: May 2006

Mathematicians have one over on the physicists in that they already have a unified theory of mathematics, namely, set theory. Unfortunately, the plethora of independence results since the invention of forcing has taken away some of the luster of set theory in the eyes of many mathematicians. Will man's knowledge of mathematical truth be forever limited to those theorems derivable from the standard axioms of set theory, ZFC? This author does not think so, he feels that set theorists' intuition about the universe of sets is stronger than ZFC. Here in this paper, using part of this intuition, we introduce some axiom schemata which we feel are very natural candidates for being considered as part of the axioms of set theory. These schemata assert the existence of many generics over simple inner models. The main purpose of this article is to present arguments for why the assertion of the existence of such generics belongs to the axioms of set theory.

Our central guiding principle in justifying the axioms is what Maddy called the rule of thumb maximize in her survey article on the axioms of set theory, [8] and [9]. More specifically, our intuition conforms with that expressed by Mathias in his articleWhat is Maclane Missing? challenging Mac Lane's view of set theory.
About some symmetries of negation
Authors: Hösli Brigitte , Jäger Gerhard
Published: May 2006

This paper deals with some structural properties of the sequent calculus and describes strong symmetries between cut-free derivations and derivations, which do not make use of identity axioms. Both of them are discussed from a semantic and syntactic point of view.

Identity axioms and cuts are closely related to the treatment of negation in the sequent calculus, so the results of this article explain some nice symmetries of negation.
A class of connected theories of order
Authors: Stern Alan S. , Świerczkowski Stanisław S.
Published: May 2006

In 1962 Jan Mycielski proposed a very general notion of interpretability [M1]. This led to the question whether a given theory could be interpreted in the disjoint union of two theories, without being interpretable in any of them. He argued that in such a case it would be presumably simpler to study each of these theories separately, and hence conjectured that this situation can never occur for any of the well-known theories of mathematics. This conjecture has now been verified for the following theories (see [MPS], [P], [S1, 2]): ELO (endless, i.e., without maximal element, linear order), Th(〈ℚ, ≤〉), Th(〈ω, ≤〉) and all sequential theories (those which can code finite sequences of elements of their models). The latter include PA, ZF, GB and Th(〈ω,+,·〉). In view of these confirmations it became ever more plausible that the conjecture is valid also for RCF (real closed fields), i.e., for Th(〈ℝ,≤,+,·,0,1〉). In the present paper we show that Mycielski's conjecture is valid for a class of theories which includes RCF and OF (ordered fields).

We consider only theories with equality and without function symbols. Interpretations will be meant local, multidimensional, and with parameters, as defined in [M1], [M2] and surveyed in [MPS] (for a recent definition see also [S2]). We shall write T0 ≪ T1 to say that T0 is interpretable in T1 (or that T1 interprets T0), and this will mean that for every theorem α of T0 there is an interpretation of α in T1.
A proof-theoretic characterization of the primitive recursive set functions
Authors: Rathjen Michael
Published: May 2006

Let KP− be the theory resulting from Kripke-Platek set theory by restricting Foundation to Set Foundation. Let G: V → V (V ≔ universe of sets) be a Δ0-definable set function, i.e. there is a Δ0-formula φ(x, y) such that φ(x, G(x)) is true for all sets x, and V ⊨ ∀x∃!yφ(x, y). In this paper we shall verify (by elementary proof-theoretic methods) that the collection of set functions primitive recursive in G coincides with the collection of those functions which are Σ1-definable in KP− + Σ1-Foundation + ∀x∃!yφ(x, y). Moreover, we show that this is still true if one adds Π1-Foundation or a weak version of Δ0-Dependent Choices to the latter theory.
Generalized Fitting subgroup of a group of finite Morley rank
Authors: Nesin Ali
Published: May 2006

We define a characteristic and definable subgroup F*(G) of any group G of finite Morley rank that behaves very much like the generalized Fitting subgroup of a finite group. We also prove that semisimple subnormal subgroups of G are all definable and that there are finitely many of them.
The order types of termination orderings on monadic terms, strings and multisets
Authors: Martin Ursula , Scott Elizabeth
Published: May 2006

We consider total well-founded orderings on monadic terms satisfying the replacement and full invariance properties. We show that any such ordering on monadic terms in one variable and two unary function symbols must have order typeω,ω2orωω. We show that a familiar construction gives rise to continuum many such orderings of order typeω. We construct a new family of such orderings of order typeω2, and show that there are continuum many of these. We show that there are only four such orderings of order typeωω, the two familiar recursive path orderings and two closely related orderings. We consider also total well-founded orderings onNnwhich are preserved under vector addition. We show that any such ordering must have order typeωkfor some 1 ≤k≤n. We show that ifk<nthere are continuum many such orderings, and ifk=nthere are onlyn!, then! lexicographic orderings.
Minimal invariant spaces in formal topology
Authors: Coquand Thierry
Published: May 2006

A standard result in topological dynamics is the existence of minimal subsystem. It is a direct consequence of Zorn's lemma: given a compact topological space X with a map f: X→X, the set of compact non empty subspaces K of X such that f(K) ⊆ K ordered by inclusion is inductive, and hence has minimal elements. It is natural to ask for a point-free (or formal) formulation of this statement. In a previous work [3], we gave such a formulation for a quite special instance of this statement, which is used in proving a purely combinatorial theorem (van de Waerden's theorem on arithmetical progression).

In this paper, we extend our analysis to the case where X is a boolean space, that is compact totally disconnected. In such a case, we give a point-free formulation of the existence of a minimal subspace for any continuous map f: X→X. We show that such minimal subspaces can be described as points of a suitable formal topology, and the “existence” of such points become the problem of the consistency of the theory describing a generic point of this space. We show the consistency of this theory by building effectively and algebraically a topological model. As an application, we get a new, purely algebraic proof, of the minimal property of [3]. We show then in detail how this property can be used to give a proof of (a special case of) van der Waerden's theorem on arithmetical progression, that is “similar in structure” to the topological proof [6, 8], but which uses a simple algebraic remark (Proposition 1) instead of Zorn's lemma. A last section tries to place this work in a wider context, as a reformulation of Hilbert's method of introduction/elimination of ideal elements.
AD and patterns of singular cardinals below Θ
Authors: Apter Arthur W.
Published: May 2006

Using Steel's recent result that assuming AD, in L[ℝ] below Θ, κ is regular iff κ is measurable, we mimic below Θ certain earlier results of Gitik. In particular, we construct via forcing a model in which all uncountable cardinals below Θ are singular and a model in which the only regular uncountable cardinal below Θ is ℵ1.
Omitting types in incomplete theories
Authors: Casanovas Enrique , Farré Rafel
Published: May 2006

We characterize omissibility of a type, or a family of types, in a countable theory in terms of non-existence of a certain tree of formulas. We extend results of L. Newelski on omitting < covK non-isolated types. As a consequence we prove that omissibility of a family of < covK types is equivalent to omissibility of each countable subfamily.
The consistency of ZFC + 2ℵ0 > ℵω + ℐ(ℵ2) = ℐ(ℵω)
Authors: Gilchrist Martin , Shelah Saharon
Published: May 2006

Let κ be an uncountable cardinal and the edges of a complete graph with κ vertices be colored with ℵ0 colors. For the Erdős-Rado theorem implies that there is an infinite monochromatic subgraph. However, if , then it may be impossible to find a monochromatic triangle. This paper is concerned with the latter situation. We consider the types of colorings of finite subgraphs that must occur when . In particular, we are concerned with the case ℵ1 ≤ κ ≤ ℵω.

The study of these color patterns (known as identities) has a history that involves the existence of compactness theorems for two cardinal models [4]. When the graph being colored has size ℵ1, the identities that must occur ((ℵ1)) have been classified by Shelah [6]. If the graph has size greater than or equal to ℵω the identities that must occur ((ℵω)) have also been classified in [5]. This leaves open the question of how the sets (ℵm) (2 ≤ m < ω) fit between (ℵ1) and ⊆ (ℵω). Some progress in this direction has been made in the paper [2]. It is there shown that if ZFC is consistent then so is for each m < ω. The number of colors is fixed at ℵ0 as it is the natural place to start and the results here can be generalized to more colors. We first give some definitions and establish some notation.
sets of reals
Authors: Bagaria Joan , Woodin W. Hugh
Published: May 2006

Some of the most striking results in modern set theory have emerged from the study of simply-definable sets of real numbers. Indeed, simple questions like: what are the posible cardinalities?, are they measurable?, do they have the property of Baire?, etc., cannot be answered in ZFC.

When one restricts the attention to the analytic sets, i.e., the continuous images of Borel sets, then ZFC does provide an answer to these questions. But this is no longer true for the projective sets, i.e., all the sets of reals that can be obtained from the Borel sets by taking continuous images and complements. In this paper we shall concentrate on particular projective classes, the , and using forcing constructions we will produce models of ZFC where, for some n, all , sets have some specified property. For the definition and basic facts about the projective classes , and , as well as the Kleene (or lightface) classes , and , we refer the reader to Moschovakis [19].

The first part of the paper is about measure and category. Early in this century, Luzin [16] and Luzin-Sierpiński [17] showed that all analytic (i.e., ) sets of reals are Lebesgue measurable and have the property of Baire.
The undecidability of second order linear logic without exponentials
Authors: Lafont Yves
Published: May 2006

Recently, Lincoln, Scedrov and Shankar showed that the multiplicative fragment of second order intuitionistic linear logic is undecidable, using an encoding of second order intuitionistic logic. Their argument applies to the multiplicative-additive fragment, but it does not work in the classical case, because second order classical logic is decidable. Here we show that the multiplicative-additive fragment of second order classical linear logic is also undecidable, using an encoding of two-counter machines originally due to Kanovich. The faithfulness of this encoding is proved by means of the phase semantics.
Grzegorcyk's hierarchy and IepΣ1
Authors: Takeuti Gaisi
Published: May 2006

A proof-theoretic characterization of the primitive recursive functions is the Σ1-definable functions in IΣ1 as is shown in Mints [4], Parsons [5], and [8].

Then what is a proof-theoretic characterization of Grzegorzyk's hierarchy? First we discuss a related previous work. In Clote and Takeuti [2], we introduced a theory TAC that corresponds to the computational complexity class AC. TAC has a very weak form of induction. We assign a rank to a proof in TAC in the following way. The rank of a proof P in TAC is the nesting number of inductions used in P. Then TACi is defined to be the subtheory of TAC whose proof has a rank ≤ i. We proved that TACi corresponds to the class ACi.

In this paper we introduce a theory IepΣ1 which is equivalent to IΣ1. Then we define the rank of a proof in IepΣ1 as the nesting number of inductions in the proof and prove that the proofs with rank ≤ i correspond to Grzegorcyk's hierarchy for i > 0.

We also prove that the system that has proofs with rank 0 is actually equivalent to I Δ0. These facts are interesting since it is proved in [10] that the theory isomorphic to TAC∘ by RSUV isomorphism is a conservative extension of I Δo. Therefore there is some analogy between the class AC and the primitive recursive functions.
Mixed systems
Authors: Ash C. J. , Knight J. F.
Published: May 2006

In [A1]–[A4] there is an abstract description, in terms of “α-systems”, of the object of a nested priority construction, and there is a metatheorem listing conditions which guarantee the success of the construction. The metatheorem has different versions, with later versions becoming simpler and more general. The information needed to meet the requirements is enumerated by a function, where α is an arbitrary recursive ordinal. All other objects associated with the α-system are r.e. In the basic metatheorem, the requirements must all be at level α, although there is a special result, for limit α, which allows one requirement at each level in an increasing sequence with limit α. There are other abstract descriptions of nested priority arguments in [K1], [K2], [K3], and [L-L].

A typical use of α-systems is that in [B], where it is shown that, for a relation R on a recursive structure , under suitable assumptions, if R does not have a “recursive Σα” definition in , then there is a recursive isomorphic copy of in which the image of R is not . There is no difficulty in generalizing this to make each of infinitely many relations not , when the assumptions are uniformly satisfied and each relation has no recursive Σα definition. However, the metatheorems for α-systems do not apply to the situation where we have several (even two) relations Ri, which do not have recursive Σβi definitions and whose images we wish to make not for distinct βi. An even more basic problem is to construct a recursive copy of a recursive structure via an isomorphism whose restriction to various sets Ui, is not If βi, = α for all i, then we can use an (α + 1)-system; otherwise, the old metatheorems do not apply.
A solution to the completeness problem for weakly aggregative modal logic
Authors: Apostoli Peter , Brown Bryson
Published: May 2006

We are accustomed to regardingKas the weakest modal logic admitting of a relational semantics in the style made popular by Kripke. However, in a series of papers which demonstrates a startling connection between modal logic and the theory of paraconsistent inference, Ray Jennings and Peter Schotch have developed a generalized relational frame theory which articulates an infinite hierarchy of sublogics ofK, each expressing a species of “weakly aggregative necessity”. Recall thatKis axiomatized, in the presence ofNandRM, by the schema of “binary aggregation”

For eachn≥ 1, the weakly aggregative modal logicKnis axiomatized by replacingKwith the schema of “n-ary aggregation”

which is ann-ary relaxation, or weakening, ofK. Note thatK1=K.

In [3], the authors claim without proof thatKnis determined by the class of framesF= (W, R), whereWis a nonempty set andRis an (n+ 1)-ary relation onW, under the generalization of Kriple's truth condition according to which □αis true at a pointwinWif and only ifαis true at one ofx1,…,xnfor allx1,…,xninWsuch thatRw, x1,…,xn.
Some questions concerning the cofinality of Sym(κ)
Authors: Sharp James D. , Thomas Simon
Published: May 2006

Suppose thatGis a group that is not finitely generated. Then the cofinality ofG, writtenc(G), is denned to be the least cardinalλsuch thatGcan be expressed as the union of a chain ofλproper subgroups. Ifκis an infinite cardinal, then Sym(κ) denotes the group of all permutations of the setκ= {α∣α<κ}. In [1], Macpherson and Neumann proved thatc(Sym(κ)) >κfor all infinite cardinalsκ. In [4], we proved that it is consistent thatc(Sym(ω)) and 2ωcan be any two prescribed regular cardinals, subject only to the obvious requirement thatc(Sym(ω)) ≤ 2ω. Our first result in this paper is the analogous result for regular uncountable cardinalsκ.

Theorem 1.1.Let V ⊨ GCH. Let κ, θ, λ ∈ V be cardinals such that

(i) κ and θ are regular uncountable, and

(ii)κ < θ ≤cf(λ).

Then there exists a notion of forcingℙ,which preserves cofinalities and cardinalities, such that if G isℙ-generic then V[G] ⊨c(Sym(κ)) = θ ≤λ= 2κ.

Theorem 1.1 will be proved in §2. Our proof is based on a very powerful uniformization principle, which was shown to be consistent for regular uncountable cardinals in [2].