For any countable transitive complete theory T with infinite models and the finite model property, we construct a minimal structure M such that the theory of M is small if and only if T is small, and is λ-stable if and only if T is λ-stable. This gives a series of new examples of minimal structures.

0# can be invisibly class generic.

It was conjectured by Halpern and Kapron (Annals of Pure and Applied Logic, vol. 69, 1994) that frame satisfiability of propositional modal formulas is incomparable in expressive power to both (Ackermann) and (Bernays-Schönfinkel). We prove this conjecture. Our results imply that (Ackermann) and (Bernays-Schönfinkel) are incomparable in expressive power, already on finite graphs. Moreover, we show that on ordered finite graphs, i.e., finite graphs with a successor, (Bernays-Schönfinkel) is strictly more expressive than (Ackermann).

Forcing method on Bounded Arithmetic was first introduced by J. B. Paris and A. Wilkie in [10]. Then in [1], [2] and [3], M. Ajtai used the method to get excellent results on the pigeon hole principle and the modulo p counting principle. The forcing method on Bounded arithmetic was further developed by P. Beame, J. Krajíček and S. Riis in [4], [7], [6], [8], [5], [12], [11], [13]. It should be noted that J. Krajíček and P. Pudlák used an idea of Boolean valued in [9] and also Boolean valued notion is efficiently used for model theoretic constructions in [7], [6], [8], [5].

In our previous paper [14], we developed a Boolean valued version of forcing on Bounded Arithmetic using Boolean algebra which is generated by polynomial size circuits from Boolean variables and discussed its relation with NP = co-NP problem and P = NP problem. Especially we proved the following theorem and related theorems as Theorems 2, 3 and 4 in Section 2.

Theorem. If M[G] is not a model of S2, then NP ≠ co-NP and therefore P ≠ NP.

However in the proof of the Theorem, we used a consequence of P = NP. More precisely we used the following as a consequence of NP = co-NP, though it is a consequence of P = NP but not a consequence of NP = co-NP.

Suppose that NP = co-NP holds. Then there exists an NP-complete predicate ∃x ≤ t(a) A(x,a) with sharply bounded A(x, a) and a sharply bounded B(y, a) such that ∃x ≤ t(a) A(x,a) ↔ ∀y ≤ s(a)B(y, a). Then there exists polynomial time computable functions f and g such that the following two sequents hold.

Let K be an algebraically closed field of any characteristic, complete with respect to the non-trivial ultrametric absolute value ∣·∣: K → ℝ+. By R denote the valuation ring of K, and by ℘ its maximal ideal. We work within the class of subanalytic sets defined in [5], but our results here also hold for the strongly subanalytic sets introduced in [11] as well as for those subanalytic sets considered in [6]. Let X ⊂ R1 be subanalytic. In [8], we showed that there is a decomposition of X as a union of a finite number of special sets U ⊂ R1 (see below). In this note, in Theorem 1.6, we obtain a version of this result which is uniform in parameters, thereby answering a question brought to our attention by Angus Macintyre. It follows immediately from Theorem 1.6 that the theory of K in the language (see [5] and [6]) is C-minimal in the sense of [3] and [9]. The analogous uniformity result in the p-adic case was recently proved in [12].

Definition 1.1. (i) A disc in R1 is a set of one of the two following forms:

A special set in R1 is a disc minus a finite union of discs.

(ii) R-domains u ⊂ Rm, and their associated rings of analytic functions, , are defined inductively as follows. Rm is an R-domain and , the ring of strictly convergent power series in X1,…, Xm over K. If u is an R-domain with associated ring , (where K 〈X, Y〉 〚ρ〛S is a ring of separated power series, see [5, §2] and [1, §1]) and f, have no common zero on u and ◸ ϵ {<, ≤}, then

is an R-domain and

where J is the ideal generated by I and f − gZ (Z is a new variable) if ◸ is ≤, and

where J is the ideal generated by I and f − gτ (τ a new variable) if ◸ is <. (See [8, Definition 2.2].) R-domains generalize the rational domains of [2, §7.2.3]. It is true, but not easy to prove, that only depends on u as a point set, and is independent of the particular representation of u.

In this paper, we prove that there exist computably enumerable degrees a and b such that a > b and for any degree x, if x ≤ a and x is a minimal degree, then x < b.

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. In a preceding paper, [2], we considered 4 systems of illative combinatory logic that are sound for first order intuitionistic propositional and predicate logic. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators, or in a more direct way, in which derivations are not translated. Both translations are closely related in a canonical way. In the cited paper we proved completeness of the two direct translations. In the present paper we prove that also the two indirect translations are complete. These proofs are direct whereas in another version, [3], we proved completeness by showing that the two corresponding illative systems are conservative over the two systems for the direct translations. Moreover we shall prove that one of the systems is also complete for predicate calculus with higher type functions.

We work throughout in a finite relational language L. This paper is built on [2] and [3]. We repeat some of the basic notions and results from these papers for the convenience of the reader but familiarity with the setup in the first few sections of [3] is needed to read this paper. Spencer and Shelah [6] constructed for each irrational α between 0 and 1 the theory Tα as the almost sure theory of random graphs with edge probability n−α. In [2] we proved that this was the same theory as the theory Tα built by constructing a generic model in [3]. In this paper we explore some of the more subtle model theoretic properties of this theory. We show that Tα has the dimensional order property and does not have the finite cover property.

We work in the framework of [3] so probability theory is not needed in this paper. This choice allows us to consider a wider class of theories than just the Tα. The basic facts cited from [3] were due to Hrushovski [4]; a full bibliography is in [3]. For general background in stability theory see [1] or [5].

We work at three levels of generality. The first is given by an axiomatic framework in Context 1.10. Section 2 is carried out in this generality. The main family of examples for this context is described in Example 1.3. Sections 3 and 4 depend on a function δ assigning a real number to each finite L-structure as in these examples. Some of the constructions in Section 3 (labeled at the time) use heavily the restriction of the class of examples to graphs. The first author acknowledges useful discussions on this paper with Sergei Starchenko.

Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε0-recursive function []0: T → ω so that a reduces to b implies [a]0 > [b]0. The construction of [ ]0 is based on a careful analysis of the Howard-Schütte treatment of Gödel's T and utilizes the collapsing function ψ: ε0 → ω which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of [ ]0 is also crucially based on ideas developed in the 1995 paper “A proof of strongly uniform termination for Gödel's T by the method of local predicativity” by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper.

Indeed, for given n let Tn be the subsystem of T in which the recursors have type level less than or equal to n + 2. (By definition, case distinction functionals for every type are also contained in Tn.) As a corollary of the main theorem of this paper we obtain (reobtain?) optimal bounds for the Tn-derivation lengths in terms of ω+2-descent recursive functions. The derivation lengths of type one functionals from Tn (hence also their computational complexities) are classified optimally in terms of <ωn+2 -descent recursive functions.

In particular we obtain (reobtain?) that the derivation lengths function of a type one functional a ∈ T0 is primitive recursive, thus any type one functional a in T0 defines a primitive recursive function. Similarly we also obtain (reobtain?) a full classification of T1 in terms of multiple recursion.

As proof-theoretic corollaries we reobtain the classification of the IΣn+1-provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Gödel's T we reobtain additionally (without employing continuous cut elimination techniques) that PRA + PRWO(ε0) ⊢ Π20 − Refl(PA) and PRA + PRWO(ωn+2) ⊢ Π20 − Refl(IΣn+1), hence PRA + PRWO(ε0) ⊢ Con(PA) and PRA + PRWO(ωn+2) ⊢ Con(IΣn+1).

For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity.

Let λ ≤ κ be infinite cardinals and let Ω be a set of cardinality κ. The bounded permutation group Bλ(Ω), or simply Bλ, is the group consisting of all permutations of Ω which move fewer than λ points in Ω. We say that a permutation group G acting on Ω is a supplement of Bλ if BλG is the full symmetric group on Ω.

In [7], Macpherson and Neumann claimed to have classified all supplements of bounded permutation groups. Specifically, they claimed to have proved that a group G acting on the set Ω is a supplement of Bλ if and only if there exists Δ ⊂ Ω with ∣Δ∣ < λ such that the setwise stabiliser G{Δ} acts as the full symmetric group on Ω ∖ Δ. However I have found a mistake in their proof. The aim of this paper is to examine conditions under which Macpherson and Neumann's claim holds, as well as conditions under which a counterexample can be constructed. In the process we will discover surprising links with cardinal arithmetic and Shelah's recently developed pcf theory.

Strengthening a theorem of D. W. Kueker, this paper completely charaterizes which countable structures do not admit uncountable Lω1ω-elementarily equivalent models. In particular, it is shown that if the automorphism group of a countable structure M is abelian, or even just solvable, then there is no uncountable model of the Scott sentence of M. These results arise as part of a study of Polish groups with compatible left-invariant complete metrics.

Two rings are elementarily equivalent if and only if they satisfy the same sentences in the language of rings. To some extent this is reflected in the representation theories of the two rings (one may see both positive and negative results along these lines in [5]). Here we concentrate on the case of a ring S and an elementary subring R of S.

We show that if R is an elementary subring of S then the lattice of pp formulas for R-modules embeds in that for S-modules. These lattices, moreover, have the same finite sub-posets. From this we derive some corollaries. Then we consider to what extent the compositions of induction and restriction between R- and S-modules preserve elementary equivalence.

We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in “propositional” fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The “pure,” propositional fragment FLR0 turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of models.

In this paper we show that the compactness of a Loeb space depends on its cardinality, the nonstandard universe it belongs to and the underlying model of set theory we live in. In §1 we prove that Loeb spaces are compact under various assumptions, and in §2 we prove that Loeb spaces are not compact under various other assumptions. The results in §1 and §2 give a quite complete answer to a question of D.Ross in [9], [11] and [12].

The monadic second-order theory of trees allows quantification over elements and over arbitrary subsets. We classify the class of trees with respect to the question: does a tree T have definable Skolem functions (by a monadic formula with parameters)? This continues [6] where the question was asked only with respect to choice functions. A natural subclass is defined and proved to be the class of trees with definable Skolem functions. Along the way we investigate the spectrum of definable well orderings of well ordered chains.

Weiermann [18] introduces a new method to generate fast growing functions in order to get an elegant and perspicuous proof of a bounding theorem for provably total recursive functions in a formal theory, e.g., in PA. His fast growing function θαη is described as follows. For each ordinal a and natural number n let denote a finitely branching, primitive recursive tree of ordinals, i.e., an ordinal as a label is attached to each node in the tree so that the labelling is compatible with the tree ordering. Then the tree is well founded and hence finite by König's lemma. Define θαηn =the depth of the tree =the length of the longest branch in .

We introduce new fast and slow growing functions in this mode of definitions and show that each of these majorizes provably total recursive functions in PA.

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.

Let I be an ideal of subsets of a Polish space X, containing all singletons and possessing a Borel basis. Assuming that I does not satisfy ccc, we consider the following conditions (B), (M) and (D). Condition (B) states that there is a disjoint family F ⊆ P(X) of size ϲ, consisting of Borel sets which are not in I. Condition (M) states that there is a Borel function f : X → X with f−1[{x}] ∉ I for each x ∈ X. Provided that X is a group and I is invariant, condition (D) states that there exist a Borel set B ∉ I and a perfect set P ⊆ X for which the family {B+x : x ∈ P} is disjoint. The aim of the paper is to study whether the reverse implications in the chain (D) ⇒ (M) ⇒ (B) ⇒ not-ccc can hold. We build a σ-ideal on the Cantor group witnessing (M) & ¬(D) (Section 2). A modified version of that σ-ideal contains the whole space (Section 3). Some consistency results on deriving (M) from (B) for “nicely” defined ideals are established (Sections 4 and 5). We show that both ccc and (M) can fail (Theorems 1.3 and 5.6). Finally, some sharp version's of (M) for invariant ideals on Polish groups are investigated (Section 6).

Let T be a countable, small simple theory. In this paper, we prove that for such T, the notion of Lascar strong type coincides with the notion of strong type, over an arbitrary set.

We investigate amalgamation properties of relational type algebras. Besides purely algebraic interest, amalgamation in a class of algebras is important because it leads to interpolation results for the logic corresponding to that class (cf. [15]). The multi-modal logic corresponding to relational type algebras became known under the name of “arrow logic” (cf. [18, 17]), and has been studied rather extensively lately (cf. [10]). Our research was inspired by the following result of Andréka et al. [1].

Let K be a class of relational type algebras such that

(i) composition is associative,

(ii) K is a class of boolean algebras with operators, and

(iii) K contains the representable relation algebras RRA.

Then the equational theory of K is undecidable.

On the other hand, there are several classes of relational type algebras (e.g., NA, WA denned below) whose equational (even universal) theories are decidable (cf. [13]). Composition is not associative in these classes. Theorem 5 indicates that also with respect to amalgamation (a very weak form of) associativity forms a borderline. We first recall the relevant definitions.