It is shown that the so called slow growing hierarchy depends non trivially on the choice of its underlying structure of ordinals. To this end we investigate the growth rate behaviour of the slow growing hierarchy along natural subsets of notations for Γ0. Let T be the set-theoretic ordinal notation system for Γ0 and Ttree the tree ordinal representation for Γ0. It is shown in this paper that (Gα)α∈T matches up with the class of functions which are elementary recursive in the Ackermann function as does (by folklore). By thinning out terms in which the addition function symbol occurs we single out subsystems T* ⊆ T and Ttree* ⊆ Ttree (both of order type not exceeding ε0) and prove that still matches up with but now consists of elementary recursive functions only. We discuss the relationship between these results and the Γ0-based termination proof for the standard rewrite system for the Ackermann function.

Let L be a first-order language and Φ and Ψ two L-sentences that cannot be satisfied simultaneously in any finite L-structure. Then obviously the following principle ChainL,Φ,Ψ(n, m) holds: For any chain of finite L-structures C1, …, Cm with the universe [n] one of the following conditions must fail:

For each fixed L and parameters n, m the principle ChainL,Φ,Ψ(n,m) can be encoded into a propositional DNF formula of size polynomial in n, m.

For any language L containing only constants and unary predicates we show that there is a constant CL such that the following holds: If a constant depth Frege system in DeMorgan language proves ChainL,Φ,Ψ(n, cL . n) by a size s proof then the class of finite L-structures with universe [n] satisfying Φ can be separated from the class of those L-structures on [n] satisfying ψ by a depth 3 formula of size 2log(S)O(1) and with bottom fan-in log(S)O(1).

Section 1 is devoted to the study of countable recursively saturated models with an automorphism moving every non-algebraic point. We show that every countable theory has such a model and exhibit necessary and sufficient conditions for the existence of automorphisms moving all non-algebraic points. Furthermore we show that there are many complete theories with the property that every countable recursively saturated model has such an automorphism.

In Section 2 we apply our main theorem from Section 1 to models of Quine's set theory New Foundations (NF) to answer an old consistency question. If NF is consistent, then it has a model in which the standard natural numbers are a definable subclass ℕ of the model's set of internal natural numbers Nn. In addition, in this model the class of wellfounded sets is exactly .

Theorem. Assume that there exists a standard model of ZFC + V = L. Then there is a model of ZFC in which the partial ordering of the degrees of constructibility of reals is isomorphic with a given finite lattice.

The proof of the theorem uses forcing. The definition of the forcing conditions and the proofs of some of the lemmas are connected with Lerman's paper on initial segments of the upper semilattice of the Turing degrees [2]. As an auxiliary notion we shall introduce the notion of a sequential representation of a lattice, which slightly differs from Lerman's representation.

Let K be a given finite lattice. Assume that the universe of K is an integer l. Let ≤ K be the ordering in K. A sequential representation of K is a sequence Ui ⊆ Ui+1 of finite subsets of ω i such that the following holds:

(1) For any s, s′ Є Ui , i Є ω, k, m Є l, k ≤ K m & s(m) = s′(m) → s(k) = s′(k).

(2) For any s Є Ui , i Є ω, s(0) = 0 where 0 is the least element of K.

(3) For any s, s′ Є i Є ω, k,j Є l, if k y Kj = m and s(k) = s′(k) & s(j) = s′(j) → s(m) = s′(m), where v K denotes the join in K.

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

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

We call v ∈ P2 a numbering of P1 iff {λx.v(i, x)}i ∈ ω = P1; we denote λx.v(i, x) by vi. Let v and γ be numberings of P1. A total function g: ω → ω is called a translator from v into γ iff ∀i: vi = γg(i).

Levin and Schnorr (independently) introduced the monotone complexity, Km (α), of a binary string α. We use monotone complexity to define the relative complexity (or relative randomness) of reals. We define a partial ordering ≤Km on 2ω by α ≤Km β iff there is a constant c such that Km(α | n) ≤ Km(β | n)+ c for all n. The monotone degree of α is the set of all β such that α Km β and β Km α. We show the monotone degrees contain an antichain of size , a countable dense linear ordering (of degrees of cardinality ), and a minimal pair.

Downey, Hirschfeldt, LaForte, Nies and others have studied a similar structure, the K-degrees, where K is the prefix-free Kolmogorov complexity. A minimal pair of K-degrees was constructed by Csima and Montalban. Of particular interest are the noncomputable trivial reals, first constructed by Solovay. We defineareal to be (Km,K)-trivial if for some constant c, Km(α | n) ≤ K(n) + c for all n. It is not known whether there is a Km-minimal real, but we show that any such real must be (Km,K)-trivial.

Finally, we consider the monotone degrees of the computably enumerable (c.e.) and strongly computably enumerable (s.c.e.) reals. We show there is no minimal c.e. monotone degree and that Solovay reducibility does not imply monotone reducibility on the c.e. reals. We also show the s.c.e. monotone degrees contain an infinite antichain and a countable dense linear ordering.

Let be an o-minimal structure over a real closed field R. Given a simplicial complex K and some definable subsets S 1, …, Sl of its realization ∣K∣ in R we prove that there exist a subdivision K′ of K and a definable triangulation φ′: ∣K′∣ → ∣K∣ of ∣K∣ partitioning S 1, …, Sl with φ′ definably homotopic to id ∣K∣. As an application of this result we obtain the semialgebraic Hauptvermutung.

We present definitions of homology groups Hn (p), n ≥ 0, associated to a complete type p. We show that if the generalized amalgamation properties hold, then the homology groups are trivial. We compute the group H2(p) for strong types in stable theories and show that any profinite abelian group can occur as the group H2 (p).

The principal aim of this paper is to present a construction method for nontotal extensional combinatory algebras. This is done in §2. In §0 we give definitions of some basic notions for partial combinatory algebras from which the corresponding notions for (total) combinatory algebras are obtained as specializations. In §1 we discuss some properties of nontotal extensional combinatory algebras in general. §2 describes a “partial” variant of reflexive complete partial orders yielding nontotal extensional combinatory algebras. Finally, §3 deals with properties of the models constructed in §2, such as incompletability, having no total submodel and the pathological behaviour with respect to the interpretation of unsolvable λ-terms.

We analyse the Mitchell ordering in a model where κ is -hypermeasurable and > .

Quine remarked that the system of his book exclusive of *200 is a completely safe basal logic. Axioms of this basal logic are given by *100-*105 and *201-*202 in the book. For relation theory and number theory, we need some further axioms to guarantee elementhood of certain entities. In the article, Quine proposed to adopt as axioms f610 and the following two statements:

An Ehrenfeucht theory is a complete first order theory with exactly n countable models up to isomorphism, 1 < n < ω. Numerous results have emerged regarding these theories ([1]–[15]). A general question in model theory is whether or not the number of countable models of a complete theory can be different than the number of countable models of a complete consistent extension of the theory by finitely many constant symbols. Examples are known of Ehrenfeucht theories that have complete extensions by finitely many constant symbols such that the extensions fail to be Ehrenfeucht ([4], [8], [13]). These examples are easily modified to allow finite increases in the number of countable models.

This paper contains examples in the other direction—complete theories that have consistent extensions by finitely many constant symbols such that the extensions have fewer countable models. This answers affirmatively a question raised by, among others, Peretyat'kin [8]. The first example will be an Ehrenfeucht theory with exactly four countable models with an extension by a constant symbol that has only three countable models. The second example will be a complete theory that is not Ehrenfeucht, but which has an extension by a constant symbol that is Ehrenfeucht. The notational conventions for this paper are standard.

Peretyat'kin introduced the theory of a dense binary branching tree with a meet operator [7]. Dense ω-branching trees have also proven useful [5], [11]. Both of the Theories that will be constructed make use of dense ω-branching trees.

The Wadge hierarchy was originally defined and studied only in the Baire space (and some other zero-dimensional spaces). Here we extend the Wadge hierarchy of Borel sets to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g., several Hausdorff–Kuratowski (HK)-type theorems in quasi-Polish spaces. In fact, many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q.

Keisler, in [1], defined a set F(D) of infinite cardinals for every ultrafilter D on a set I, and, assuming GCH, gave a sufficient condition for a set C of infinite cardinals to have the form F(D) for suitable D and I. In this paper we prove a similar theorem (Theorem 1) under considerably weaker assumptions. Our main tool is a construction of elementary end extensions of Boolean ultrapowers of ω outlined by Shelah in [6, Exercise VI.3.35]. Hence this paper will mostly be concerned with Boolean ultrapowers of ω.

This paper explores algebraic aspects of two modifications of the usual account of first-order quantifiers.

Standard first-order quantificational logic is modelled algebraically by cylindric algebras. Prime examples of these are algebras whose members are sets of sequences: given a first-order model U for a language that is based on the set {υκ: κ < α} of variables, each formula φ is represented by the set

of all those α-length sequences x = 〈xκ: κ < α〉 that satisfy φ in U. Such a sequence provides a value-assignment to the variables (υκ is assigned value xκ), but it may also be viewed geometrically as a point in the α-dimensional Cartesian spaceαU of all α-length sequences whose terms come from the underlying set U of U. Then existential quantification is represented by the operation of cylindrification. To explain this, define a binary relation Tκ on sequences by putting xTκy if and only if x and y differ at most at their κth coordinate, i.e.,

Then for any set X ⊆ αU, the set

is the “cylinder” generated by translation of X parallel to the κth coordinate axis in αU. Given the standard semantics for the existential quantifier ∃υκ as

it is evident that

In [3], Todorčević showed that ω1 ⇸ [ω1]ω12. In this paper we use similar methods to prove an analogous partition theorem for Pω1(λ), for certain uncountable cardinals λ.

Recall that ω1 → [ω1]ω12, means that for every function f: [ω1]2 → ω1 there is a set A ∈ [ω1]ω1 such that f“[A]2 ≠ ω1, and of course ω1 ⇸ [ω1]ω12, is the negation of this statement. For partition relations on Pω1(→) it is customary to partition only those pairs of sets in which the first set is a subset of the second. Thus for A ⊆ Pω1(λ) we define

We will write Pω1(λ) → [unbdd]λ2 to mean that for every function f: [Pω1(λ)]⊂2 → λ there is an unbounded set A ⊆ Pω1(λ) such that f“[A]⊂2 ≠ λ, and again Pω1(λ) ⇸ [unbdd]λ2 is the negation of this statement.

It is a theorem of Prikry [7] that if κ carries a uniform η-descendingly complete ultrafilter then the stationary reflection property fails. 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), and I will denote an ideal on κ, by which we mean a set I ⊆ P(κ) such that (i) I is closed under taking subsets and finite unions and (ii) αЄ I for each α < κ, but κ ∉ I. I is said to be μ-complete if it is closed under taking unions of size < μ, I* = {X ⊆ κ ∣ κ − X Є I} is the filter dual to I and if A Є I+ (= P(κ) − I), then I∣A is the ideal on κ given by I ∣ A = {X ⊆ κ ∣ X ∩ A Є I}. If h: A → κ then h is said to be (i) unbounded mod I if for each α < κ, h−1(α) = {ξ Є A ∣ h(ξ) < α} Є I and (ii) a least function for I if h is unbounded mod I and whenever g: A → κ is a function, unbounded mod I, then {ξ Є A ∣ g{ξ) < h{ξ)} Є I.

We establish a coloring theorem for successors of singular cardinals, and use it prove that for any such cardinal μ, we have if and only if for arbitrarily large θ < μ.