We show that a set has an η-representation in a linear order if and only if it is the range of a 0′-computable limitwise monotonic function. We also construct a Δ3 Turing degree for which no set in that degree has a strong η-representation, answering a question posed by Downey.

In this article, we study some new characterizations of primitive recursive functions based on restricted forms of primitive recursion, improving the pioneering work of R. M. Robinson and M. D. Gladstone. We reduce certain recursion schemes (mixed/pure iteration without parameters) and we characterize one-argument primitive recursive functions as the closure under substitution and iteration of certain optimal sets.

We show that if add(null) = c, then the globally Baire and universally measurable chromatic numbers of the graph of any Borel function on a Polish space are equal and at most three. In particular, this holds for the graph of the unilateral shift on [ℕ]ℕ, although its Borel chromatic number is ℵ0. We also show that if add(null) = c, then the universally measurable chromatic number of every treeing of a measure amenable equivalence relation is at most three. In particular, this holds for “the” minimum analytic graph with uncountable Borel (and Baire measurable) chromatic number. In contrast, we show that for all κ Є6 (2, 3…..ℵ0, c), there is a treeing of E0 with Borel and Baire measurable chromatic number κ. Finally, we use a Glimm–Effros style dichotomy theorem to show that every basis for a non-empty initial segment of the class of graphs of Borel functions of Borel chromatic number at least three contains a copy of (ℝ<ℕ, ⊇).

If is an analytic family of pairwise eventually different functions then the following strong maximality condition fails: For any countable , no member of which is covered by finitely many functions from , there is such that for all there are infinitely many integers k such that f(k) = h(k). However if V = L then there exists a coanalytic family of pairwise eventually different functions satisfying this strong maximality condition.

We construct a non-discrete Polish group none of whose non-discrete subgroups admits a complete left-invariant metric.

Nous définissons une classe de suites de polynômes, calculés par des circuits de complexité polynomiale comprenant des additions, des soustractions. des multiplications et des sommations de Valiant. Nous montrons que cette classe est close pour la prise de la fonction-coefficient. définie au paragraphe 3 de cet article; nous en déduisons l'existence d'un circuit de complexité 72.n2, calculant le coefficient binomial de deux nombres de n chiffres, donnés en base 2. Il est par ailleurs facile de construire un circuit de complexité 17.n + 2 calculant la factorielle d'un nombre de n chiffres. La présence de 2.n sommations d'effet exponentiel dans chacun de ces circuits en affecte gravement l'intérêt pratique. II est peu probable, ou du moins peu souhaitable. qu'on puisse éliminer ces sommations sans explosion, car cela provoquerait la catastrophe cryptographique que redoutent tous les banquiers; néanmoins, nous ne savons pas séparer la classe définie ici de celle des suites de polynômes calculables en un nombre polynomial d'opérations arithmétiques. Cela n'a rien de surprenant, vu la très grande affinité qu'elle a avec la classe PSPACE: nous montrons en effet que cette classe est identique à la classe VPSPACE, définie antérieurement par Koiran et Perifel, qui apparaît ici sous une forme bien plus maniable que l'originale.

We classify ultrafilters on ω with respect to sequential contours (see [4]. [5]) of different ranks. In this way we obtain an ω1 sequence of disjoint classes. We prove that non-emptiness of for successor α ≥ 2 is equivalent to the existence of P-point. We investigate relations between P-hierarchy and ordinal ultrafilters (introduced by J. E. Baumgartner in [1]). we prove that it is relatively consistent with ZFC that the successor classes (for α ≥ 2) of P-hierarchy and ordinal ultrafilters intersect but are not the same.

I provide indestructibility results for large cardinals consistent with V = L, such as weakly compact, indescribable and strongly unfoldable cardinals. The Main Theorem shows that any strongly unfoldable cardinal κ can be made indestructible by <κ-closed, κ-proper forcing. This class of posets includes for instance all <κ-closed posets that are either κ−-c.c. or <κ-strategically closed as well as finite iterations of such posets. Since strongly unfoldable cardinals strengthen both indescribable and weakly compact cardinals, the Main Theorem therefore makes these two large cardinal notions similarly indestructible. Finally. I apply the Main Theorem to obtain a class forcing extension preserving all strongly unfoldable cardinals in which every strongly unfoldable cardinal κ is indestructible by <κ-closed, κ-proper forcing.

In Handbook of Philosophical Logic M. Dunn formulated a problem of describing pretabular extensions of relevant logics (cf. M. Dunn [1984], p. 211; M. Dunn, G. Restall [2002], p. 79). The main result of this paper is described in the title.

There is an ergodic, measure preserving, countable Borel equivalence relation E on a standard Borel probability space (X, μ) such that E∣c is not essentially free on any conull C ⊂ X.

Using a dictionary translating a variety of classical and modern covering properties into combinatorial properties of continuous images, we get a simple way to understand the interrelations between these properties in ZFC and in the realm of the trichotomy axiom for upward closed families of sets of natural numbers. While it is now known that the answer to the Hurewicz 1927 problem is positive, it is shown here that semifilter trichotomy implies a negative answer to a slightly stronger form of this problem.

Extending some results of Malykhin, we prove several independence results about base properties of βω / ω and its powers, especially the Noetherian type Nt(βω / ω), the least κ for which βω / ω has a base that is κ-like with respect to containment. For example, Nt(βω / ω) is at least s, but can consistently be ω1, c, c+, or strictly between ω1 and c. Nt(βω / ω) is also consistently less than the additivity of the meager ideal. Nt(βω / ω) is closely related to the existence of special kinds of splitting families.

We give upper and lower bounds for the consistency strength of the failure of a combinatorial principle introduced by Jensen. Square on singular cardinals.

We call a logic regular for a semantics when the satisfaction predicate for at least one of its nontheorems is closed under double negation. Such intuitionistic theories as second-order Heyting arithmetic HAS and the intuitionistic set theory IZF prove completeness for no regular logics, no matter how simple or complicated. Any extensions of those theories proving completeness for regular logics are classical, i.e., they derive the tertium non datur. When an intuitionistic metatheory features anticlassical principles or recognizes that a logic regular for a semantics is nonclassical, it proves explicitly that the logic is incomplete with respect to that semantics. Logics regular relative to Tarski, Beth and Kripke semantics form a large collection that includes propositional and predicate intuitionistic, intermediate and classical logics. These results are corollaries of a single theorem. A variant of its proof yields a generalization of the Gödel-Kreisel Theorem linking weak completeness for intuitionistic predicate logic to Markov's Principle.

In response to a question of Farah, “How many Boolean algebras are there?” [Far04], one of us (Oliver) proved that there are continuum-many nonisomorphic Boolean algebras of the form with I a Borel ideal on the natural numbers, and in fact that this result could be improved simultaneously in two directions:

(i) “Borel ideal” may be improved to “analytic P-ideal”

(ii) “continuum-many” may be improved to “E0-many”; that is, E0 is Borel reducible to the isomorphism relation on quotients by analytic P-ideals.

See [Oli04].

In [AdKechOO], Adams and Kechris showed that the relation of equality on Borel sets (and therefore, any Borel equivalence relation whatsoever) is Borel reducible to the equivalence relation of Borel bireducibility. (In somewhat finer terms, they showed that the partial order of inclusion on Borel sets is Borel reducible to the quasi-order of Borel reducibility.) Their technique was to find a collection of, in some sense, strongly mutually ergodic equivalence relations, indexed by reals, and then assign to each Borel set B a sort of “direct sum” of the equivalence relations corresponding to the reals in B. Then if B1, ⊆ B2 it was easy to see that the equivalence relation thus induced by B1 was Borel reducible to the one induced by B2, whereas in the opposite case, taking x to be some element of B / B2, it was possible to show that the equivalence relation corresponding to x, which was part of the equivalence relation induced by B1, was not Borel reducible to the equivalence relation corresponding to B2.

An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y ⊆ ω there is an X in P such that X ≥wttY. We show that this is also equivalent to the class's being large in some sense. We give an example of how this result can be used in the study of scattered linear orders.

We deal with a restricted form WC-N′ of the weak continuity principle, a version BT′ of Baire's theorem, and a boundedness principle BD-N. We show, in the spirit of constructive reverse mathematics, that WC-N′, BT′ + ¬LPO and BD-N + ¬LPO are equivalent in a constructive system, where LPO is the limited principle of omniscience.

Given a supercompact cardinal κ and a regular cardinal λ < κ, we describe a type of forcing such that in the generic extension the cofinality of κ is λ, there is a very good scale at κ, a bad scale at κ, and SCH at κ fails. When creating our model we have great freedom in assigning the value of 2κ, and so we can make SCH hold or fail arbitrarily badly.

We examine the computably enumerable (c.e.) degrees of prime models of complete atomic decidable (CAD) theories. A structure has degree d if d is the degree of its elementary diagram. We show that if a CAD theory T has a prime model of c.e. degree c, then T has a prime model of strictly lower c.e. degree b, where, in addition, b is low (b′ = 0′), This extends Csima's result that every CAD theory has a low prime model. We also prove a density result for c.e. degrees of prime models. In particular, if c and d are c.e. degrees with d < c and c not low2 (c″ > 0″), then for any CAD theory T, there exists a c.e. degree b with d < b < c such that T has a prime model of degree b, where b can be chosen so that b′ is any degree c.e. in c with d′ ≤ b′. As a corollary, we show that for any degree c with 0 < c < 0′, every CAD theory has a prime model of low c.e. degree incomparable with c. We show also that every CAD theory has prime models of low c.e. degree that form a minimal pair, extending another result of Csima. We then discuss how these results apply to homogeneous models.

We consider the problem whether the theorems of the fragments form a strictly increasing hierarchy. We shall show a link to some results about the lengths of proofs in predicate logic that supports the conjecture that the hierarchy is strictly increasing.