bluuebunny/crossref_metadata_2025 huggingface dataset:
Universal recursion theoretic properties of r.e. preordered structures
Authors: Montagna Franco , Sorbi Andrea
Published: May 2006

When dealing with axiomatic theories from a recursion-theoretic point of view, the notion of r.e. preordering naturally arises. We agree that an r.e. preorder is a pair = 〈P, ≤P〉 such that P is an r.e. subset of the set of natural numbers (denoted by ω), ≤P is a preordering on P and the set {〈;x, y〉: x ≤Py} is r.e.. Indeed, if is an axiomatic theory, the provable implication of yields a preordering on the class of (Gödel numbers of) formulas of .

Of course, if ≤P is a preordering on P, then it yields an equivalence relation ~P on P, by simply letting x ~Py iff x ≤Py and y ≤Px. Hence, in the case of P = ω, any preordering yields an equivalence relation on ω and consequently a numeration in the sense of [4]. It is also clear that any equivalence relation on ω (hence any numeration) can be regarded as a preordering on ω. In view of this connection, we sometimes apply to the theory of preorders some of the concepts from the theory of numerations (see also Eršov [6]).

Our main concern will be in applications of these concepts to logic, in particular as regards sufficiently strong axiomatic theories (essentially the ones in which recursive functions are representable). From this point of view it seems to be of some interest to study some remarkable prelattices and Boolean prealgebras which arise from such theories. It turns out that these structures enjoy some rather surprising lattice-theoretic and universal recursion-theoretic properties.

After making our main definitions in §1, we examine universal recursion-theoretic properties of some r.e. prelattices in §2.
The uniqueness of envelopes in ℵ0-categorical, ℵ0-stable structures
Authors: Loveys James
Published: May 2006

The Classification Theorem for ℵ0-categorical strictly minimal sets says that if H is strictly minimal and ℵ0-categorical, either H has in effect no structure at all or is essentially an affine or projective space over a finite field. Zil′ber, in [Z2], showed that if H were a counterexample to this Classification Theorem it would interpret a rank 2, degree 1 pseudoplane. Cherlin later noticed (see [CHL, Appendices 2 and 3], for the proof) that the Classification Theorem is a consequence of the Classification Theorem for finite simple groups. In [Z4] and [Z5], Zil′ber found a quite different proof of the Classification Theorem using no deep group theory.

Meanwhile in [Z3], Zil′ber introduced the notion of envelope in an attempt to prove that no complete totally categorical theory T can be finitely axiomatizable. The idea of the proof was to show that if M is a model of such a T and H ⊆ M is strongly minimal, then an envelope of any sufficiently large finite subset of H is a finite model of any fixed finite subset of T. [Z3] contains an error, which Zil′ber has since corrected (in a nontrivial way).

In [CHL], Cherlin, Harrington and Lachlan used the Classification Theorem to expand and reorganize Zil′ber's work. In particular, they generalized most of his work to ℵ0-categorical, ℵ0-stable structures, proved the Morley rank is finite in these structures, and introduced the powerful Coordinatization Theorem (Theorem 3.1 of [CHL]; Proposition 1.14 of the present paper). They also showed that ℵ0-categorical, ℵ0-stable structures are not finitely axiomatizable using a notion of envelope that is the same as Zil′ber's except in one particularly perverse case; [CHL]'s notion of envelope is used throughout the current paper. Peretyat'kin [P] has found an example of an ℵ1-categorical finitely axiomatizable structure.
On the T-degrees of partial functions
Authors: Casalegno Paolo
Published: May 2006

Let 〈, ≤ 〉 be the usual structure of the degrees of unsolvability and 〈, ≤ 〉 the structure of the T-degrees of partial functions defined in [7]. We prove that every countable distributive lattice with a least element can be isomorphically embedded as an initial segment of 〈, ≤ 〉: as a corollary, the first order theory of 〈, ≤ 〉 is recursively isomorphic to that of 〈, ≤ 〉. We also show that 〈, ≤ 〉 and 〈, ≤ 〉 are not elementarily equivalent.
A theory of properties
Authors: Turner Ray
Published: May 2006

Frege's attempts to formulate a theory of properties to serve as a foundation for logic, mathematics and semantics all dissolved under the weight of the logicial paradoxes. The language of Frege's theory permitted the representation of the property which holds of everything which does not hold of itself. Minimal logic, plus Frege's principle of abstraction, leads immediately to a contradiction. The subsequent history of foundational studies was dominated by attempts to formulate theories of properties and sets which would not succumb to the Russell argument. Among such are Russell's simple theory of types and the development of various iterative conceptions of set. All of these theories ban, in one way or another, the self-reference responsible for the paradoxes; in this sense they are all “typed” theories. The semantical paradoxes, involving the concept of truth, induced similar nightmares among philosophers and logicians involved in semantic theory. The early work of Tarski demonstrated that no language that contained enough formal machinery to respresent the various versions of the Liar could contain a truth-predicate satisfying all the Tarski biconditionals. However, recent work in both disciplines has led to a re-evaluation of the limitations imposed by the paradoxes.

In the foundations of set theory, the work of Gilmore [1974], Feferman [1975], [1979], [1984], and Aczel [1980] has clearly demonstrated that elegant and useful type-free theories of classes are feasible. Work on the semantic paradoxes was given new life by Kripke's contribution (Kripke [1975]). This inspired the recent work of Gupta [1982] and Herzberger [1982]. These papers demonstrate that much room is available for the development of theories of truth which meet almost all of Tarski's desiderata.
The special model axiom in nonstandard analysis
Authors: Ross David
Published: May 2006

κ-saturation [SL] is probably the single most useful property of nonstandard models of analysis. For some applications, however, stronger saturation hypotheses seem necessary. Henson formulated his elegant κ-isomorphism property (see [H1], and §2 below) to address this need. This property, though well-suited to certain situations (notably those arising in Banach space theory), is often difficult to apply in practice (see [SL, §7.7]).

In this paper I describe an alternative to κ-isomorphism which is much easier to use; in particular, a proof which assumes that the nonstandard model is fully saturated can usually be converted directly to one using this special model axiom.

Precise definitions of both these axioms appear in §2. In §3 I prove some simple properties of the special model axiom, one of which is that it is at least as strong as κ-isomorphism. In §§4, 5, and 6 the axiom is used to construct a few examples, many of which are pathological, or at the very least counterintuitive. (These examples are given primarily to illustrate use of the axiom; the only one of independent interest is Theorem 5.5.) In §7 some alternative axioms and open problems are discussed.

Many of the results in this paper grew out of discussion and correspondence with C. Ward Henson, to whom I am consequently most grateful.
Large discrete parts of the E-tree
Authors: Simmons Harold
Published: May 2006

Let PA be first order Peano arithmetic, let Λ be the lattice of Π1 sentences modulo PA, and let S be the poset of prime filters of Λ ordered by reverse inclusion. We show there are large convex discrete parts of S; in particular there are convex parts which form a completed Baire tree or an Aronszajn tree.

The elements of S, which we call nodes, correspond to the extensions of PA which are complete for sentences. Equivalently, for each model of PA the Π1-theory ∀() of is a node, and every node occurs in this form. Note that the Π1-theory ∀() of the standard model (i.e. the filter of true Π1 sentences) is the unique root of S.

This poset S, which is sometimes called the E-tree, was first studied in [1] where it is shown that:

(1) The poset is tree-like, i.e. the set of predecessors of any node is linearly ordered.

(2) The poset has branches, each of which is closed under unions and intersections; in particular each branch has a maximum member.

(3) There are branches on which ∀() does not have an immediate successor. Further properties of the E-tree are given in [2]−[7]. In particular in [4] Misercque shows that:

(4) There are branches on which ∀() does have an immediate successor.

(5) There are nodes with both an immediate predecessor and an immediate successor.

The two results (3) and (4) show that there are fundamentally different branches of S, and (5) shows that parts of branches may be discrete.
Weakly semirecursive sets
Authors: Jockusch Carl G. , Owings James C.
Published: May 2006

We introduce the notion of “semi-r.e.” for subsets of ω, a generalization of “semirecursive” and of “r.e.”, and the notion of “weakly semirecursive”, a generalization of “semi-r.e.”. We show that A is weakly semirecursive iff, for any n numbers x1, …,xn, knowing how many of these numbers belong to A is equivalent to knowing which of these numbers belong to A. It is shown that there exist weakly semirecursive sets that are neither semi-r.e. nor co-semi-r.e. On the other hand, we exhibit nonzero Turing degrees in which every weakly semirecursive set is semirecursive. We characterize the notion “A is weakly semirecursive and recursive in K” in terms of recursive approximations to A. We also show that if a finite Boolean combination of r.e. sets is semirecursive then it must be r.e. or co-r.e. Several open questions are raised.
Relevance and paraconsistency—a new approach
Authors: Avron Arnon
Published: May 2006

In this work we describe a new approach to the notions of relevance and paraconsistency. Unlike the works of Anderson and Belnap or da Costa (see [2], [8] and [7]) we shall mainly be guided in it by semantical intuitions. In the first two sections we introduce and investigate the algebraic structures that reflect those intuitions. The corresponding formal systems are briefly described in the third section (a more detailed treatment of these systems, including full proofs, will be given in another paper).

Our basic intuitive idea is that of “domains of discourse” or “relevance domains”. Classical logic, so we think, is valid in as much as sentences get values inside one domain; limitations on its use can be imposed only with respect to inferences in which more than one domain is involved. There are two basic binary relations over the collection of domains. One is relevance. It is reflexive and symmetric (but not necessarily transitive). Under a given interpretation two sentences are relevant to each other when their values are in relevant domains. Another basic relation between domains, no less important, is that of grading according to “degrees of reality”. The idea behind it is not new. Gentzen, for example, divided in [9] the world of mathematics into three grades, representing three “levels of reality”. The elementary theory of numbers has the highest degree or level of reality; set theory has the smallest degree and mathematical analysis occupies the intermediate level. In the theory of types, or in the accumulative von Neumann universe for set theory, we can find indication of a richer hierarchy.
Corrigendum to “Taxonomies of model-theoretically defined topological properties”
Authors: Bankston Paul
Published: May 2006

An error has been found in the cited paper; namely, Theorem 3.1 is false.
The elementary theory of free pseudo p-adically closed fields of finite corank
Authors: Efrat Ido
Published: May 2006

Let be p-adic closures of a countable Hilbertian field K. The main result of [EJ] asserts that the field has the following properties for almost all σ1,…,σe + m ϵ G(K) (in the sense of the unique Haar measure on G(K)e+m):

(a) Kσ is pseudo p-adically closed (abbreviation: PpC), i.e., each nonempty absolutely irreducible variety defined over Kσ has a Kσ-rational point, provided that it has a simple rational point in each p-adic closure of Kσ.

(b) G(Kσ) ≅ De,m, where De,m is the free profinite product of e copies Γ1,…, Γe of G(ℚp) and a free profinite group of rank m.

(c) Kσ has exactly e nonequivalent p-adic valuation rings. They are the restrictions Oσ1,…, Oσe of the unique p-adic valuation rings on , respectively.

In this paper we show that this result is in a certain sense the best possible. More precisely, we first show that the class of fields which satisfy (a)–(c) above is elementary in the appropriate language e(K), which is the ordinary first-order language of rings augmented by constant symbols for the elements of K and by e new unary relation symbols (interpreted as e p-adic valuation rings).
Isols and the pigeonhole principle
Authors: Dekker J. C. E. , Ellentuck E.
Published: May 2006

In this paper we generalize the pigeonhole principle by using isols as our fundamental counting tool.
A limit on relative genericity in the recursively enumerable sets
Authors: Lempp Steffen , Slaman Theodore A.
Published: May 2006

Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X′, its Turing jump, is recursive in ∅′ and high if X′ computes ∅″. Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of A ⊕ W is recursive in the jump of A. We prove that there are no deep degrees other than the recursive one.

Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turing functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that (W ⊕ A)′ is forced to disagree with Φ(−;A′). The conversion has some ambiguity; in particular, A cannot be found uniformly from W.

We also show that there is a “moderately” deep degree: There is a low nonzero degree whose join with any other low degree is not high.
On recursion theory in IΣ1
Authors: Hájek Petr , Kučera Antonín
Published: May 2006

It is shown that the low basis theorem is meaningful and provable in IΣ1 and that the priority-free solution to Post's problem formalizes in this theory.
The structure of graphs all of whose Y-sections are internal sets
Authors: Živaljević Boško
Published: May 2006

The purpose of this paper is to give structural results on graphs lying in the product of two hyperfinite sets X and Y, whose Y-sections are either all internal sets or all of “small” cardinality with respect to the saturation assumption imposed on our nonstandard universe. These results generalize those of [KKML] and [HeRo]. In [KKML] Keisler, Kunen, Miller and Leth proved, among other results, that any countably determined function in the product of two internal sets X and Y can be covered by countably many internal functions provided that the nonstandard universe is at least ℵ-saturated. This shows that any countably determined function can be represented as a union of countably many restrictions of internal functions to countably determined sets. On the other hand, Henson and Ross use in [HeRo] Choquet's capacitability theorem to prove that any Souslin function in the product of two internal sets X and Y is a.e. equal to an internal function. (Here “a.e.” refers to an arbitrary but fixed bounded Loeb measure.) Therefore, in our terminology, every Souslin function possesses an internal a.e. lifting.

After the introductory §0, where all the necessary terminology is introduced, we continue by presenting the structural result for graphs all of whose Y-sections are of cardinality ≤κ (provided that the nonstandard universe is ≤κ+-saturated) in §1. We show that, under the above saturation assumption, a κ-determined graph with all of the Y-sections of cardinality ≤κ is covered by κ-many internal functions. Therefore, any such graph is a union of κ-many κ-determined functions. In particular if the graph in question is Borel, Souslin, κ-Borel or κ-Souslin (or a member of one of the Borel, κ-Borel or projective hierarchies) then the corresponding constituting functions are of the same “complexity”. Thus, any Borel graph all of whose Y-sections are at most countable is a union of countably many Borel functions and, consequently, has Borel domain. In the setting of Polish topological spaces this was proved by Novikov (see [De]).
Amenable equivalence relations and Turing degrees
Authors: Kechris Alexander S.
Published: May 2006

In [12] Slaman and Steel posed the following problem:

Assume ZF + DC + AD. Suppose we have a function assigning to each Turing degree d a linear order <d of d. Then must the rationals embed order preservingly in <d for a cone of d's?

They had already obtained a partial answer to this question by showing that there is no such d ↦ <d with <d of order type ζ = ω* + ω on a cone. Already the possibility that <d has order type ζ · ζ was left open.

We use here, ideas and methods associated with the concept of amenability (of groups, actions, equivalence relations, etc.) to prove some general results from which one can obtain a positive answer to the above problem.
End-extensions preserving power set
Authors: Forster Thomas , Kaye Richard
Published: May 2006

We consider the quantifier hierarchy of Takahashi [1972] and show how it gives rise to reflection theorems for some large cardinals in ZF, a new natural subtheory of Zermelo's set theory, a potentially useful new reduction of the consistency problem for Quine's NF, and a sharpening of another reduction of this problem due to Boffa.
A theory of formal truth arithmetically equivalent to ID1
Authors: Cantini Andrea
Published: May 2006

We present a theory VF of partial truth over Peano arithmetic and we prove that VF and ID1, have the same arithmetical content. The semantics of VF is inspired by van Fraassen's notion of supervaluation.
Models with second order properties in successors of singulars
Authors: Grossberg Rami
Published: May 2006

Let L(Q) be first order logic with Keisler's quantifier, in the λ+ interpretation (= the satisfaction is defined as follows: M ⊨ (Qx)φ(x) means there are λ+ many elements in M satisfying the formula φ(x)).

Theorem 1. Let λ be a singular cardinal; assume □λ and GCH. If T is a complete theory in L(Q) of cardinality at most λ, and p is an L(Q) 1-type so that T strongly omits p( = p has no support, to be defined in §1), then T has a model of cardinality λ+ in the λ+ interpretation which omits p.

Theorem 2. Let λ be a singular cardinal, and let T be a complete first order theory of cardinality λ at most. Assume □λ and GCH. If Γ is a smallness notion then T has a model of cardinality λ+ such that a formula φ(x) is realized by λ+ elements of M iff φ(x) is not Γ-small. The theorem is proved also when λ is regular assuming λ = λ<λ. It is new when λ is singular or when ∣T∣ = λ is regular.

Theorem 3. Let λ be singular. If Con(ZFC + GCH + ∃κ) [κ is a strongly compact cardinal]), then the following is consistent: ZFC + GCH + the conclusions of all above theorems are false.
Amoeba-absoluteness and projective measurability
Authors: Brendle Jörg
Published: May 2006

We show that -Amoeba-absoluteness implies that and, hence, measurability. This answers a question of Haim Judah (private communication).
S-homogeneity and automorphism groups
Authors: Bouscaren Elisabeth , Laskowski Michael C.
Published: May 2006

We consider the question of when, given a subset A of M, the setwise stabilizer of the group of automorphisms induces a closed subgroup on Sym(A). We define s-homogeneity to be the analogue of homogeneity relative to strong embeddings and show that any subset of a countable, s-homogeneous, ω-stable structure induces a closed subgroup and contrast this with a number of negative results. We also show that for ω-stable structures s-homogeneity is preserved under naming countably many constants, but under slightly weaker conditions it can be lost by naming a single point.
Hyper-regular lattice-ordered groups
Authors: Gluschankof Daniel , Lucas François
Published: May 2006

It is a well-known fact that the notion of an archimedean order cannot be formalized in the first-order calculus. In [12] and [18], A. Robinson and E. Zakon characterized the elementary class generated by all the archimedean, totally-ordered abelian groups (o-groups) in the language 〈+,<〉, calling it the class of regularly ordered or generalized archimedean abelian groups. Since difference (−) and 0 are definable in that language, it is immediate that in the expanded language 〈 +, −, 0, < 〉 the definable expansion of the class of regular groups is also the elementary class generated by the archimedean ones. In the more general context of lattice-ordered groups (l-groups), the notion of being archimedean splits into two different notions: a strong one (being hyperarchimedean) and a weak one (being archimedean). Using the representation theorem of K. Keimel for hyperarchimedean l-groups, we extend in this paper the Robinson and Zakon characterization to the elementary class generated by the prime-projectable, hyperarchimedean l-groups. This characterization is also extended here to the elementary class generated by the prime-projectable and projectable archimedean l-groups (including all complete l-groups). Finally, transferring a result of A. Touraille on the model theory of Boolean algebras with distinguished ideals, we give the classification up to elementary equivalence of the characterized class.

We recall that a lattice-ordered group, l-group for short, is a structure
Definability of models by means of existential formulas without identity
Authors: Pazdyka Paweł
Published: May 2006

The problem of coding relations by means of a single binary relation is well known in the mathematical literature. It was considered in interpretation theory, and also in connection with investigations of decidability of elementary theories. Using various constructions (see, e.g., [2,6], proofs of Theorem 11 in [7] and Theorem 16.51 in [3]), for any model for a countable language, one can construct a model for ℒp (a language with a single binary relation symbol ) in which is interpretable. Each of the mentioned constructions has the same weak point: the universe of is different than the universe of . In [4] we have shown that, in the infinite case, one can eliminate this defect, i.e., for any infinite , we have constructed a model , having the same universe as , in which is elementarily definable. In all constructions mentioned above, it appears that formulas, which define in ( in ), are very complicated. In the present paper, another construction of a model for ℒp is given.
Pointwise compact and stable sets of measurable functions
Authors: Shelah S. , Fremlin D. H.
Published: May 2006

In a series of papers culminating in [9], M. Talagrand, the second author, and others investigated at length the properties and structure of pointwise compact sets of measurable functions. A number of problems, interesting in themselves and important for the theory of Pettis integration, were solved subject to various special axioms. It was left unclear just how far the special axioms were necessary. In particular, several results depended on the fact that it is consistent to suppose that every countable relatively pointwise compact set of Lebesgue measurable functions is ‘stable’ in Talagrand's sense, the point being that stable sets are known to have a variety of properties not shared by all pointwise compact sets. In the present paper we present a model of set theory in which there is a countable relatively pointwise compact set of Lebesgue measurable functions which is not stable and discuss the significance of this model in relation to the original questions. A feature of our model which may be of independent interest is the following: in it, there is a closed negligible set Q ⊆ [0, 1]2 such that whenever D ⊆ [0,1] has outer measure 1, then

has inner measure 1 (see 2G below).

We embark immediately on the central ideas of this paper, setting out a construction of a partially ordered set which forces a fairly technical proposition in measure theory (IS below); the relevance of this proposition to pointwise compact sets will be discussed in §2.
On solvable centerless groups of Morley rank 3
Authors: Davis Mark Kelly , Nesin Ali
Published: May 2006

We know quite a lot about the general structure of ω-stable solvable centerless groups of finite Morley rank. Abelian groups of finite Morley rank are also well-understood. By comparison, nonabelian nilpotent groups are a mystery except for the following general results:

• An ω1-categorical torsion-free nonabelian nilpotent group is an algebraic group over an algebraically closed field of characteristic 0 [Z3].

• A nilpotent group of finite Morley rank is the central product of a definable subgroup of finite exponent and of a definable divisible subgroup [N3].

• A divisible nilpotent group of finite Morley rank is the direct product of its torsion part (which is central) and of a torsion-free subgroup [N3].

However, we do not understand nilpotent groups of bounded exponent. It seems that the classification of nilpotent (but nonabelian)p-groups of finite Morley rank is impossible. Even the nilpotent groups of Morley rank 2 contain insurmountable difficulties [C], [T] . At first glance, this may seem to be an obstacle to proving the Cherlin-Zil'ber conjecture (“simple groups of finite Morley rank are algebraic groups”). Our purpose in this article is to show that if such a group is a definable subgroup of a nonnilpotent group, then it is possible to obtain a classification within the boundaries of our present knowledge. In this respect, our article may be considered as a relief to those who are trying to classify simple groups of finite Morley rank.

Before explicitly stating our result, we need the following definition.
Lower bounds to the size of constant-depth propositional proofs
Authors: Krajíček Jan
Published: May 2006

LK is a natural modification of Gentzen sequent calculus for propositional logic with connectives ¬ and ∧,∨ (both of bounded arity). Then for every d ≥ 0 and n ≥ 2, there is a set of depth d sequents of total size O(n3+d) which are refutable in LK by depth d + 1 proof of size exp(O(log2n)) but such that every depth d refutation must have the size at least exp(nΩ(1)). The sets express a weaker form of the pigeonhole principle.
Nonarithmetical ℵ0-categorical theories with recursive models
Authors: Knight Julia F.
Published: May 2006

In what follows, L is a recursive language. The structures to be considered are L-structures with universe named by constants from ω. A structure is recursive A if the open diagram D() is recursive. Lerman and Schmerl [L-S] proved the following result.

Let T be an ℵ0-categorical elementary first-order theory. Suppose that for all n, , and T is arithmetical. Then T has a recursive model.

The aim of this paper is to extend Theorem 0.1. Stating the extension requires some terminology. Consider finitary formulas with symbols from L and sometimes extra constants from ω. For each n ∈ ω, the Σn and Πn formulas are as usual. Then Bnformulas are Boolean combinations of Σn formulas. For an L-structure , Dn() denotes the set of Bn sentences in the complete diagram Dc(). A complete Σn theory is a maximal consistent set of ΣnL-sentences. We may write φ(x), or Γ(x), to indicate that the free variables of the formula φ, or the set Γ, are among those in x. A complete Bn type for x is a maximal consistent set Γ(x) of Bn formulas with just the free variables x.

If T is ℵ0-categorical, then for each x only finitely many complete types Γ(x) are consistent with T. While Lerman and Schmerl stated their result just for ℵ0-categorical theories, essentially the same proof yields the following.

Theorem 0.2. Let T be a consistent, complete theory such that for all n andx, only finitely many complete Bn types Γ(x) are consistent with T.
Schur-Zassenhaus theorem revisited
Authors: Borovik Alexandre V. , Nesin Ali
Published: May 2006

One of the purposes of this paper is to prove a partial Schur-Zassenhaus Theorem for groups of finite Morley rank.

Theorem 2.Let G be a solvable group of finite Morley rank. Let π be a set of primes, and let H ⊲ G a normal π-Hall subgroup. Then H has a complement in G.

This result has been proved in [1] with the additional assumption thatGis connected, and thought to be generalized in [2] by the authors of the present article. Unfortunately in the last section of the latter paper there is an irrepairable mistake. Here we give a new proof of the Schur-Zassenhaus Theorem using the results of [2] up to the last section and a new result that we are going to state below.

The second author has shown in [11] that a nilpotentω-stable group is the central product of a divisible subgroup and a subgroup of bounded exponent, generalizing a well-known result of Angus Macintyre about abelian groups [8]. One could ask a similar question for solvable groups: are they a product of two subgroups, one divisible, one of bounded exponent? One is allowed to be hopeful because of the well-known decomposition of the connected solvable algebraic groups over algebraically closed fields as the product of the unipotent radical and a torus.
Theories of modules closed under direct products
Authors: Villemaire Roger
Published: May 2006

We generalize to theories of modules (complete or not) a result of U. Felgner stating that a complete theory of abelian groups is a Horn theory if and only if it is closed under products. To prove this we show that a reduced product of modules ΠFMi (i ϵ I) is elementarily equivalent to a direct product of ultraproducts of the modules Mi(i ϵ I).
U-Lusin sets in hyperfinite time lines
Authors: Jin Renling
Published: May 2006

In an ω-saturated nonstandard universe a cut is an initial segment of the hyperintegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ϵ O there is a y greater than all the elements in U such that the interval [x − y,x + y] ⊆ O. Let U be a cut in a hyperfinite time line , which is a hyperfinite initial segment of the hyperintegers. A subset B of is called a U-Lusin set in if B is uncountable and for any Loeb-Borel U-meager subset X of , B ⋂ X is countable. Here a Loeb-Borel set is an element of the σ-algebra generated by all internal subsets of : In this paper we answer some questions of Keisler and Leth about the existence of U-Lusin sets by proving the following facts. (1) If U = x/N = {y ϵ : ∀n ϵ ℕ(y < x/n)} for some x ϵ , then there exists a U-Lusin set of power κ if and only if there exists a Lusin set of the reals of power κ. (2) If U ≠ x/N but the coinitiality of U is ω, then there are no U-Lusin sets if CH fails. (3) Under ZFC there exists a nonstandard universe in which U-Lusin sets exist for every cut U with uncountable cofinality and coinitiality. (4) In any ω2-saturated nonstandard universe there are no U-Lusin sets for all cuts U except U = x/N.
-sets of reals
Authors: Judah Haim , Shelah Saharon
Published: May 2006

We build models where all -sets of reals are measurable and (or) have the property of Baire and (or) are Ramsey. We will show that there is no implication between any of these properties for -sets of reals.
Relation algebras of every dimension
Authors: Maddux Roger D.
Published: May 2006

Conjecture (1) of [Ma83] is confirmed here by the following result: if 3 ≤ α < ω, then there is a finite relation algebra of dimension α, which is not a relation algebra of dimension α + 1. A logical consequence of this theorem is that for every finite α ≥ 3 there is a formula of the form S ⊆ T (asserting that one binary relation is included in another), which is provable with α + 1 variables, but not provable with only α variables (using a special sequent calculus designed for deducing properties of binary relations).
On Boolean algebras and integrally closed commutative regular rings
Authors: Nagayama Misao
Published: May 2006

In this paper we consider properties, related to model-completeness, of the theory of integrally closed commutative regular rings. We obtain the main theorem claiming that in a Boolean algebra B, the truth of a prenex Σn-formula whose parameters ai, partition B, can be determined by finitely many conditions built from the first entry of Tarski invariant T(ai)'s, n-characteristic D(n, ai)'s and the quantities S(ai, l) and S′(ai, l) for l < n. Then we derive two important theorems. One claims that for any Boolean algebras A and B, an embedding of A into B preserving D(n, a) for all a ϵ A is a Σn-extension. The other claims that the theory of n-separable Boolean algebras admits elimination of quantifiers in a simple definitional extension of the language of Boolean algebras. Finally we translate these results into the language of commutative regular rings.
On the Schur-Zassenhaus theorem for groups of finite Morley rank
Authors: Borovik Alexandre V. , Nesin Ali
Published: May 2006

The Schur-Zassenhaus Theorem is one of the fundamental theorems of finite group theory. Here is its statement:

Fact1.1 (Schur-Zassenhaus Theorem). Let G be a finite group and let N be a normal subgroup of G. Assume that the order ∣N∣ is relatively prime to the index [G:N]. Then N has a complement in G and any two complements of N are conjugate in G.

The proof can be found in most standard books in group theory, e.g., in [S, Chapter 2, Theorem 8.10]. The original statement stipulated one ofNorG/Nto be solvable. Since then, the Feit-Thompson theorem [FT] has been proved and it forces eitherNorG/Nto be solvable. (The analogous Feit-Thompson theorem for groups of finite Morley rank is a long standing open problem).

The literal translation of the Schur-Zassenhaus theorem to the finite Morley rank context would state that in a groupGof finite Morley rank a normal π-Hall subgroup (if it exists at all) has a complement and all the complements are conjugate to each other. (Recall that a groupHis called aπ-group, where π is a set of prime numbers, if elements ofHhave finite orders whose prime divisors are from π. Maximal π-subgroups of a groupGare called π-Hall subgroups. They exist by Zorn's lemma. Since a normal π-subgroup ofGis in all the π-Hall subgroups, if a group has a normal π-Hall subgroup then this subgroup is unique.)

The second assertion of the Schur-Zassenhaus theorem about the conjugacy of complements is false in general. As a counterexample, consider the multiplicative group ℂ* of the complex number field ℂ and consider thep-Sylow for any primep, or even the torsion part of ℂ*. LetHbe this subgroup.Hhas a complement, but this complement is found by Zorn's Lemma (consider a maximal subgroup that intersectsHtrivially) and the use of Zorn's Lemma is essential. In fact, by Zorn's Lemma, any subgroup that has a trivial intersection withHcan be extended to a complement ofH. Since ℂ* is abelian, these complements cannot be conjugated to each other.
1-reducibility inside an m-degree with a maximal set
Authors: Herrmann E.
Published: May 2006

The structure of the 1-degrees included in an m-degree with a maximal set together with the 1-reducibility relation is characterized. For this a special sublattice of the lattice of recursively enumerable sets under the set-inclusion is used.
A characterization of Martin's axiom in terms of absoluteness
Authors: Bagaria Joan
Published: May 2006

Martin's axiom is equivalent to the statement that the universe is absolute under ccc forcing extensions for Σ1 sentences with a subset of κ, , as a parameter.
Product-free Lambek calculus and context-free grammars
Authors: Pentus Mati
Published: May 2006

In this paper we prove the Chomsky Conjecture (all languages recognized by the Lambek calculus are context-free) for both the full Lambek calculus and its product-free fragment. For the latter case we present a construction of context-free grammars involving only product-free types.
Precipitous towers of normal filters
Authors: Burke Douglas R.
Published: May 2006

In this paper we investigate towers of normal filters. These towers were first used by Woodin (see [15]). Woodin proved that if δ is a Woodin cardinal and P is the full stationary tower up to δ (P<δ) or the countable version (Q<δ), then the generic ultrapower is closed under < δ sequences (so the generic ultrapower is well-founded) ([14]). We show that if ℙ is a tower of height δ, δ supercompact, and the filters generating ℙ are the club filter restricted to a stationary set, then the generic ultrapower is well-founded (ℙ is precipitous). We also give some examples of non-precipitous towers. We also show that every normal filter can be extended to a V-ultrafilter with well-founded ultrapower in some generic extension of V (assuming large cardinals). Similarly for any tower of inaccessible height. This is accomplished by showing that there is a stationary set that projects to the filter or the tower and then forcing with P<δ below this stationary set.

An important idea in our proof of precipitousness (Theorem 6.4) has the following form in Woodin's proof. If are maximal antichains (i Є ω and δ Woodin) then there is a κ < δ such that each Ai ∩ Vκ is semiproper, i.e.,

contains a club (relative to ∣ a∣ < κ).
Two remarks on the Lifschitz realizability topos
Authors: Oosten Jaap Van
Published: May 2006

The purpose of this note is to clarify two points about the topos Lif, introduced in [13] as a generalization of Lifschitz' realizability ([9, 12]). Lif is a subtopos of Hyland's Effective topos ([1]). The points I want to make are:

Remark 1. Lif is the largest subtopos of satisfying the axiom (O):

where denotes partial recursive application, and “∈ Tot” means that e and f range over codes for total recursive functions. One may read (O) as the statement “The union of two -sets is again a -set”. That is, let be a subtopos of . Then (O) is true in for the standard interpretation (the variables range over the natural numbers object of , etc.) if and only if the inclusion ↣ factors through the inclusion Lif ↣ .

Remark 2. Like , Lif contains at least two weakly complete internal full subcategories, thus providing us with more models of polymorphism and other impredicative type theories.

The principle (O) has some standing in the history of constructive mathematics:

- H. Friedman has proved that (O) is equivalent to a formulation of intuitionistic completeness of the intuitionistic predicate calculus for Tarskian semantics; see [8]. This is not to imply that this result is of immediate relevance to Lif: Friedman works in a system of analysis, a theory of lawless sequences with an axiom of “open data” for arithmetical formulas, which at least for the domain of all functions from N to N fails in Lif. However, there might exist a “nonstandard model” of arithmetic and a corresponding system of analysis, in which we may be able to carry out his proof.

- Moreover, Remark 2 entails that Lif should provide us with models of synthetic domain theory (for an exposition, see [3]), and one with the nice property that the dual of one of the axioms (axiom 7 in [3]) comes for free, by (O).
Fluted formulas and the limits of decidability
Authors: Purdy William C.
Published: May 2006

In the predicate calculus, variables provide a flexible indexing service which selects the actual arguments to a predicate letter from among possible arguments that precede the predicate letter (in the parse of the formula). In the process of selection, the possible arguments can be permuted, repeated (used more than once), and skipped. If this service is withheld, so that arguments must be the immediately preceding ones, taken in the order in which they occur, the formula is said to be fluted. Quine showed that if a fluted formula contains only homogeneous conjunction (conjoins only subformulas of equal arity), then the satisfiability of the formula is decidable. It remained an open question whether the satisfiability of a fluted formula without this restriction is decidable. This paper answers that question.
On the incompleteness theorems
Authors: Kotlarski Henryk
Published: May 2006

We give new proofs of both incompleteness theorems. We do not use the diagonalization lemma, but work with some quickly growing functions instead.
Expressibility of properties of relations
Authors: Andréka Hajnal , Düntsch Ivo , Németi István
Published: May 2006

We investigate in an algebraic setting the question of which logical languages can express the properties integral, permutational, and rigid for algebras of relations.
Ultrafilters generated by a closed set of functions
Authors: Bishop Greg
Published: May 2006

Let κ and λ be infinite cardinals, a filter on κ and a set of functions from κ to κ. The filter is generated by if consists of those subsets of κ which contain the range of some element of . The set is <λ-closed if it is closed in the <λ-topology on κκ. (In general, the <λ-topology on IA has basic open sets all such that, for all i ∈ I, Ui ⊆ A and ∣{i ∈ I: Ui ≠ A} ∣<λ.) The primary question considered in this paper asks “Is there a uniform ultrafilter on κ which is generated by a closed set of functions?” (Closed means <ω-closed.) We also establish the independence of two related questions. One is due to Carlson: “Does there exist a regular cardinal κ and a subtree T of <κκ such that the set of branches of T generates a uniform ultrafilter on κ?”; and the other is due to Pouzet: “For all regular cardinals κ, is it true that no uniform ultrafilter on κ is it true that no uniform ultrafilter on κ analytic?”

We show that if κ is a singular, strong limit cardinal, then there is a uniform ultrafilter on κ which is generated by a closed set of increasing functions. Also, from the consistency of an almost huge cardinal, we get the consistency of CH + “There is a uniform ultrafilter on ℵ1 which is generated by a closed set of increasing functions”. In contrast with the above results, we show that if Κ is any cardinal, λ is a regular cardinal less than or equal to κ and ℙ is the forcing notion for adding at least (κ<λ)+ generic subsets of λ, then in VP, no uniform ultrafilter on κ is generated by a closed set of functions.
Comparing notions of similarity for uncountable models
Authors: Huuskonen Taneli
Published: May 2006

The present article, which is a revised version of part of [Hu1], deals with various relations between models which might serve as exact formulations for the vague concept “similar” or “almost isomorphic”. One natural class of such formulations is equivalence in a given logic. Another way to express similarity is by potential isomorphism, i.e., isomorphism in some extension of the set-theoretic universe. The class of extensions may be restricted to give different notions of potential isomorphism. A third method is to study the winning strategies for an Ehrenfeucht-Fraïssé-game played between the two models, and the properties of the resulting equivalence and nonequivalence trees.

The basic question studied here is whether one such notion of similarity implies another. Some implications and counterexamples listed in this part are previously known or trivial, but all are mentioned for completeness' sake. Only models of cardinality ℵ1 are considered. Some results are therefore connected with the Continuum Hypothesis.
Constructing strongly equivalent nonisomorphic models for unsuperstable theories. Part B
Authors: Hyttinen Tapani , Shelah Saharon
Published: May 2006

We study how equivalent nonisomorphic models of unsuperstable theories can be. We measure the equivalence by Ehrenfeucht-Fraïssé games. This paper continues [HS].
Jensen's Σ* theory and the combinatorial content of V = L
Authors: Friedman Sy D.
Published: May 2006

An awkward feature of the standard fine structure theory of the Jα's (see Jensen [72]) is that special parameters are required to make good sense of the notion of “Σn Skolem hull”, parameters which may not be preserved in condensation arguments.

The purpose of this article is to indicate how a reformulation of Jensen's Σ* theory (developed for the study of core models) can be used to provide a more satisfactory treatment of uniformization, hulls, and Skolem functions for the Jα's. Then we use this approach to fine structure to formulate a principle intended to capture the combinatorial content of the axiom V = L.
The liar paradox and fuzzy logic
Authors: Hájek Petr , Paris Jeff , Shepherdson John
Published: May 2006

Can one extend crisp Peano arithmetic PA by a possibly many-valued predicate Tr(x) saying “xis true” and satisfying the “dequotation schema”for all sentences φ? This problem is investigated in the frame of Łukasiewicz infinitely valued logic.
A free pseudospace
Authors: Baudisch Andreas , Pillay Anand
Published: May 2006

In this paper we construct a non-CM-trivial stable theory in which no infinite field is interpretable. In fact our theory will also be trivial and ω-stable, but of infinite Morley rank. A long term aim would be to find a nonCM-trivial theory which has finite Morley rank (or is even strongly minimal) and does not interpret a field. The construction in this paper is direct, and is a “3-dimensional” version of the free pseudoplane. In a sense we are cheating: the original point of the notion ofCM-triviality was to describe the geometry of a strongly minimal set, or even of a regular type. In our example, non-CM-triviality will come from the behaviour of three orthogonal regular types.

A stable theory is said to beCM-trivial if wheneverA⊆Band acl(Ac) ∩ acl(B) = acl(A) inTeq, then Cb(stp(c/A)) ⊆ Cb(stp(c/B)). ( An infinite stable field will not beCM-trivial.) The notion is due to Hrushovski [3], where he gave several equivalent definitions, as well as showing that his new strongly minimal sets constructed “ab ovo” wereCM-trivial. The notion was studied further in [6] where it was shown thatCM-trivial groups of finite Morley rank are nilpotent-by-finite. These results were generalized in various ways to the superstable case in [8].
Liftez les sylows! Une suite à “Sous-groupes périodiques d'un groupe stable”
Authors: Poizat Bruno , Wagner Frank O.
Published: May 2006

IfGis an omega-stable group with a normal definable subgroupH, then the Sylow-2-subgroupsG/Hare the images of the Sylow-2-subgroups ofG.

Zusammenfassung.SeiGeine omega-stabile Gruppe undHein definierbarer Normalteiler vonG. Dann sind die Sylow-2-Untergruppen von G/H Bilder der Sylow-2-Untergruppen vonG.
A weak Dodd-Jensen lemma
Authors: Neeman Itay , Steel John
Published: May 2006

We show that every sufficiently iterable countable mouse has a unique iteration strategy whose associated iteration maps are lexicographically minimal. This enables us to extend the results of [3] on the good behavior of the standard parameter from tame mice to arbitrary mice.
Filtral powers of structures
Authors: Ouwehand P. , Rose H.
Published: May 2006

Among the results of this paper are the following:

1. Every Boolean (ultra)power is the union of an updirected elementary family of direct ultrapowers.

2. Under certain conditions, a finitely iterated Boolean ultrapower is isomorphic to a single Boolean ultrapower.

3. A ω-bounded filtral power is an elementary substructure of a filtral power.

4. Let be an elementary class closed under updirected unions (e.g., if is an amalgamation class); then is closed under finite products if and only if is closed under reduced products if and only if is a Horn class.
The complexity of the core model
Authors: Mitchell William J.
Published: May 2006

If there is no inner model with a cardinal κ such that ο(κ) = κ++ then the set K ∩ Hω1 is definable over Hω1 by a Δ4 formula, and the set of countable initial segments of the core model is definable over Hω1 by a Π3 formula. We show that if there is an inner model with infinitely many measurable cardinals then there is a model in which is not definable Σ3 by any Σ3 formula, and K ∩ Hω1 is not definable by any boolean combination of Σ3 formulas.