Dans [2], Salma et Franz Viktor Kuhlmann définissent plu-sieurs notions d'espace vectoriel valué et démontrent un principe d'Ax-Kochen pour celles de ces structures dans lesquelles la multiplication par un scalaire du corps préserve la valuation. Nous travaillons ici avec des conditions plus faibles. On va définir en premier lieu la notion d'espace vectoriel valué sur un corps K, et associer canoniquement à un tel espace une valuation sur K, notée w, compatible en un sens à préciser avec celle de l'espace vectoriel. Ceci va nous permettre de parler de (K, w)-espaces vectoriels valués pour tout corps valué (K, w) (definition 24). Le cas où (K, w) est trivialement valué correspond exactement à la condition de [2] de préservation de la valuation par la multiplication par un scalaire. On fixe un corps K. Les espaces vectoriels valués sur le corps K vont être traités comme des structures à deux sortes: la sorte de l'espace vectoriel et celle de l'espace des valuations. Le langage LE de la sorte de l'espace vectoriel contient le symbole de la somme, celui de l'élément neutre, et un symbole de fonction unaire pour chaque scalaire de K. Le langage LV de l'espace des valuations contient une relation d'ordre total, un symbole de fonction unaire pour la multiplication par chaque scalaire de K, et pour tout n ∈ ℕ*, un symbole de prédicat Rn contrôlant la cardinalité résiduelle. LV contient aussi un symbole de fonction unaire s qui sera la fonction successeur quand elle est définie et l'identité sinon.

We study genericity and randomness with respect to ITTMs, continuing the work initiated by Carl and Schlicht. To do so, we develop a framework to study randomness in the constructible hierarchy. We then answer several of Carl and Schlicht’s question. We also ask a new question one the equality of two classes of randoms. Although the natural intuition would dictate that the two classes are distinct, we show that things are not as simple as they seem. In particular we show that the categorical analogues of these two classes coincide, in contradiction with the natural intuition. Even though we are not able to answer the question for randomness in this article, we delineate and sharpen its contour and outline.

The Rice-Shapiro Theorem [4] says that the index set of a class of recursively enumerable (r.e.) sets is r.e. if and only if consists of all sets which extend an element of a canonically enumerable sequence of finite sets. If an index of a difference of r.e. (d.r.e.) sets is defined to be the pair of indices of the r.e. sets of which it is the difference, then the following generalization due to Hay [3] is obtained: The index set of a class of d.r.e. sets is d.r.e. if and only if is empty or consists of all sets which extend a single fixed finite set. In that paper Hay also classifies index sets of classes consisting of d.r.e. sets which extend one of a finite collection of finite sets. These sets turn out to be finite Boolean combinations of r.e. sets. The question then arises “What about the classification of the index set of a class consisting of d.r.e. sets which extend an element of a canonically enumerable sequence of finite sets?” The results in this paper come from an attempt to answer this question.

Since classes of sets which are Boolean combinations of r.e. sets form a hierarchy (the finite Ershov hierarchy, see Ershov [1]) with the r.e. and d.r.e. sets respectively levels 1 and 2 of this hierarchy, we may define index sets of classes of level n sets. If is a class of level n sets which extend some element of a canonically enumerable sequence of finite sets and if we let co-, then we extend the original classification question to the classification of the index sets of the classes and co-.

Now if the sequence of finite sets enumerates only finitely many sets or if only finitely many of the finite sets are minimal under inclusion, then it is a routine computation to verify that the index sets of and co- are in the finite Ershov hierarchy. Thus we are interested in the case in which infinitely many of the sequence of finite sets are minimal under inclusion. However if the infinite sequence is fairly simple, for instance{0}, {1}, {2}, … then the r.e. index set of co- is Σ20-complete as well as the index sets of and co- for all levels n > 2. Since the finite Ershov hierarchy does not exhaust ⊿20 there is a lot of “room” between these two extreme cases.

In the framework of Bishop’s constructive mathematics we introduce co-convexity as a property of subsets B of ${\left\{ {0,1} \right\}^{\rm{*}}}$, the set of finite binary sequences, and prove that co-convex bars are uniform. Moreover, we establish a canonical correspondence between detachable subsets B of ${\left\{ {0,1} \right\}^{\rm{*}}}$ and uniformly continuous functions f defined on the unit interval such that B is a bar if and only if the corresponding function f is positive-valued, B is a uniform bar if and only if f has positive infimum, and B is co-convex if and only if f satisfies a weak convexity condition.

In [14] J. Hirschfeld established the close connection of models of the true AE sentences of Peano Arithmetic and homomorphic images of the semiring of recursive functions. This fragment of Arithmetic includes most of the familiar results of classical number theory. There are two nice ways that such models appear in the isols. One way was introduced by A. Nerode in [20] and is referred to in the literature as Nerode Semirings. The other way is called a tame model. It is very similar to a Nerode Semiring and was introduced in [6]. The model theoretic properties of Nerode Semirings and tame models have been widely studied by T. G. McLaughlin ([16], [17], and [18]).

In this paper we introduce a new variety of tame model called a torre model. It has as a generator an infinite regressive isol with a nice structural property relative to recursively enumerable sets and their extensions to the isols. What is then obtained is a nonstandard model in the isols of the fragment of Peano Arithmetic with the following property: Let T be a torre model. Let f be any recursive function, and let fΛ be its extension to the isols. If there is an isol A with fΛ(A) ϵ T, then there is also an isol B ϵ T with fΛ(B) = fΛ(A).

We will study some aspects of the local structure of models of certain C-minimal theories. We will prove (theorem 19) that, in a sufficiently saturated C-minimal structure in which the algebraic closure has the exchange property and which is locally modular, we can construct an infinite type-definable group around any non trivial point (a term to be defined later).

By inequation is meant an expression of the form,

where a, b are terms taken from any first-order formal language. An inequation is consistent iff it cannot be brought to the form,

by substitution.

Analysability of finite U-rank types are explored both in general and in the theory ${\rm{DC}}{{\rm{F}}_0}$. The well-known fact that the equation $\delta \left( {{\rm{log}}\,\delta x} \right) = 0$ is analysable in but not almost internal to the constants is generalized to show that $\underbrace {{\rm{log}}\,\delta \cdots {\rm{log}}\,\delta }_nx = 0$ is not analysable in the constants in $\left( {n - 1} \right)$-steps. The notion of a canonical analysis is introduced–-namely an analysis that is of minimal length and interalgebraic with every other analysis of that length. Not every analysable type admits a canonical analysis. Using properties of reductions and coreductions in theories with the canonical base property, it is constructed, for any sequence of positive integers $\left( {{n_1}, \ldots ,{n_\ell }} \right)$, a type in ${\rm{DC}}{{\rm{F}}_0}$ that admits a canonical analysis with the property that the ith step has U-rank ${n_i}$.

Let ƒ be a real number. It is well known [7] that the set of rational numbers which are less than ƒ is a recursive set if and only if ƒ is representable as the limit of a recursive, recursively convergent sequence of rational numbers. In this paper we replace the condition that the set of rational numbers less than ƒ is recursive by the condition that this set is at various points in the Kleene hierarchy, and we replace the recursive, recursively convergent limit by a variety of other recursive limiting processes.

In a previous article, the author introduced the idea of intrinsic density—a restriction of asymptotic density to sets whose density is invariant under computable permutation. We prove that sets with well-defined intrinsic density (and particularly intrinsic density 0) exist only in Turing degrees that are either high (${\bf{a}}\prime { \ge _{\rm{T}}}\emptyset \prime \prime$) or compute a diagonally noncomputable function. By contrast, a classic construction of an immune set in every noncomputable degree actually yields a set with intrinsic lower density 0 in every noncomputable degree.

We also show that the former result holds in the sense of reverse mathematics, in that (over RCA0) the existence of a dominating or diagonally noncomputable function is equivalent to the existence of a set with intrinsic density 0.

There are two main axiomatic extensions of Zermelo-Fraenkel set theory without the axiom of choice, that associated with the axiom of determinateness, and that associated with infinite exponent partition relations. Initially, the axiom of determinateness, henceforth AD, was the sole tool available. Using it, set theorists in the late 1960s produced many remarkable results in pure set theory (e.g. the measurability of ℵ1) as well as in projective set theory (e.g. reduction principles for ). Infinite exponent partition relations were first studied successfully soon after these early consequences of AD. They too produced measurable cardinals and not only were the constructions here easier than those from AD—the results gave a far clearer picture of the measures involved than had been offered by AD. In general, the techniques offered by infinite exponent partition relations became so attractive that a great deal of the subsequent work from AD involved an initial derivation from AD of the appropriate infinite exponent partition relation and then the derivation from the partition relation of the desired result.

Since the early 1970s work on choiceless extensions of ZF + DC has split mainly between AD and its applications to projective set theory, and infinite exponent partition relations and their applications to pure set theory. There has certainly been a fair amount of interplay between the two, but for the most part the theories have been pursued independently.

Unlike AD, infinite exponent partition relations have shown themselves amenable to nontrivial forcing arguments. For example, Spector has constructed models for interesting partition relations, consequences of AD, in which AD is false. Thus AD is a strictly stronger assumption than are various infinite exponent partition relations. Furthermore, Woodin has recently proved the consistency of infinite exponent partition relations relative to assumptions consistent with the axiom of choice, in particular, relative to the existence of a supercompact cardinal. The notion of doing this for AD is not even considered.

The game is played on a complete Boolean algebra , by two players. White and Black, in κ-many moves (where κ is an infinite cardinal). At the beginning White chooses a non-zero element p ∈ . In the α-th move White chooses pα ∈ (0, p) and Black responds choosing iα ∈{0, 1}. White winsthe play iff . where and .

The corresponding game theoretic properties of c.B.a.'s are investigated. So, Black has a winning strategy (w.s.) if κ ≥ π() or if contains a κ-closed dense subset. On the other hand, if White has a w.s., then κ ∈ . The existence of w.s. is characterized in a combinatorial way and in terms of forcing. In particular, if 2<κ = κ ∈ Reg and forcing by preserves the regularity of κ, then White has a w.s. iff the power 2κ is collapsed to κ in some extension. It is shown that, under the GCH, for each set S ⊆ Reg there is a c.B.a. such that White (respectively. Black) has a w.s. for each infinite cardinal κ ∈ S (resp. κ ∉ S). Also it is shown consistent that for each κ ∈ Reg there is a c.B.a. on which the game is undetermined.