We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ2–theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ1–theory of multiplication and order is decidable in finite models as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation.

We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication.

§1. Introduction. Let M be a totally ordered set. A (Dedekind) cut p of M is a couple (pL, pR) of subsets pL, pR of M such that pL ⋃ pR = M and pL < pR, i.e., a < b for all a ∈ pL, b ∈ pR. In this article we are looking for model completeness results of o-minimal structures M expanded by a set pL for a cut p of M. This means the following. Let M be an o-minimal structure in the language L and suppose M is model complete. Let D be a new unary predicate and let p be a cut of (the underlying ordered set of) M. Then we are looking for a natural, definable expansion of the L(D)-structure (M, pL) which is model complete.

The first result in this direction is a theorem of Cherlin and Dickmann (cf. [Ch-Dic]) which says that a real closed field expanded by a convex valuation ring has a model complete theory. This statement translates into the cuts language as follows. If Z is a subset of an ordered set M we write Z+ for the cut p with pR = {a ∈ M ∣ a > Z} and Z− for the cut q with qL = {a ∈ M ∣ a < Z}.

Up to equivalence, a substitution in propositional logic is an endomorphism of its free algebra. On the dual space, this results in a continuous function, and whenever the space carries a natural measure one may ask about the stochastic properties of the action. In classical logic there is a strong dichotomy: while over finitely many propositional variables everything is trivial, the study of the continuous transformations of the Cantor space is the subject of an extensive literature, and is far from being a completed task. In many-valued logic this dichotomy disappears: already in the finite-variable case many interesting phenomena occur, and the present paper aims at displaying some of these.

The logics considered here are the propositional Linear Logic and propositional Intuitionistic Linear Logic extended by a knotted structural rule: . It is proved that the class of algebraic models for such a logic has the finite embeddability property, meaning that every finite partial subalgebra of an algebra in the class can be embedded into a finite full algebra in the class. It follows that each such logic has the finite model property with respect to its algebraic semantics and hence that the logic is decidable.

We prove that the theory of fields with a derivation of Frobenius has the model companion which is stable and admits elimination of quantifiers up to the level of the λ-functions. Along the way, we give new geometric axioms of DCFp.

We prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.

Baizhanov and Baldwin [1] introduce the notions of benign and weakly benign sets to investigate the preservation of stability by naming arbitrary subsets of a stable structure. They connect the notion with work of Baldwin, Benedikt, Bouscaren, Casanovas, Poizat, and Ziegler. Stimulated by [1], we investigate here the existence of benign or weakly benign sets.

Definition 0.1. (1) The set A is benign in M if for every α, β ∊ M if p = tp(α/A) = tp(β/A) then tp*(α/A) = tp*(β/A) where the *-type is the type in the language L* with a new predicate P denoting A.

(2) The set A is weakly benign in M if for every α,β ∊ M if p = stp(α/A) = stp(β/A) then tp*(α/A) = tp*(β/A) where the *-type is the type in language with a new predicate P denoting A.

Conjecture 0.2 (too optimistic). If M is a model of stable theory T and A ⊆ M then A is benign.

Shelah observed, after learning of the Baizhanov-Baldwin reductions of the problem to equivalence relations, the following counterexample.

Lemma 0.3. There is an ω-stable rank 2 theory T with ndop which has a model M and set A such that A is not benign in M.

We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a -condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n ≥ 1 in ω, there exists a computable tree of finite height which is Σ30-categorical but not Δn3-categorical

We show that a Kueker simple theory eliminates ∃∞ and densely interprets weakly minimal formulas. As part of the proof we generalize Hrushovski's dichotomy for almost complete formulas to simple theories. We conclude that in a unidimensional simple theory an almost-complete formula is either weakly minimal or trivially-almost-complete. We also observe that a small unidimensional simple theory is supersimple of finite SU-rank.

Several extensions of the basic modal language are characterized in terms of interpolation. Our main results are of the following form: Language L′ is the least expressive extension of L with interpolation. For instance, let ℳ(D) be the extension of the basic modal language with a difference operator [7], First-order logic is the least expressive extension of ℳ(D) with interpolation. These characterizations are subsequently used to derive new results about hybrid logic, relation algebra and the guarded fragment.

The weak non-finite cover property (wnfcp) was introduced in [1] in connection with “axiomatizability” of lovely pairs of models of a simple theory. We find a combinatorial condition on a simple theory equivalent to the wnfcp, yielding a direct proof that the non-finite cover property implies the wnfcp, and that the wnfcp is preserved under reducts. We also study the question whether the wnfcp is preserved when passing from a simple theory T to the theory Tp of lovely pairs of models of T (true in the stable case). While the question remains open, we show, among other things, that if (for a T with the wnfcp) Tp is low, then TP has the wnfcp. To study this question, we describe “double lovely pairs”, and, along the way, we develop the notion of a “lovely n-tuple” of models of a simple theory, which is an analogue of the notion of a beautiful tuple of models of stable theories [2].

Let [NB]1 denote the ideal generated by nonbounding c.e. degrees and NCup the ideal of noncuppable c.e. degrees. We show that both [NB]1 ∩ NCup and the ideal generated by nonbounding and noncuppable degrees are new, in the sense that they are different from M, [NB]1 and NCup—the only three known definable ideals so far.

In this note I construct a proper o-minimal expansion of the ordered additive group of rationals.

The purpose of this paper is to present an algebraic generalization of the traditional two-valued logic. This involves introducing a theory of automorphism algebras, which is an algebraic theory of many-valued logic having a complete lattice as the set of truth values. Two generalizations of the two-valued case will be considered, viz., the finite chain and the Boolean lattice. In the case of the Boolean lattice, on choosing a designated lattice value, this algebra has binary retracts that have the usual axiomatic theory of the propositional calculus as suitable theory. This suitability applies to the Boolean algebra of formalized token models [2] where the truth values are, for example, vocabularies. Finally, as the actual motivation for this paper, we indicate how the theory of formalized token models [2] is an example of a many-valued predicate calculus.

We show that for any real number, the class of real numbers less random than it, in the sense of rK-reducibility, forms a countable real closed subfield of the real ordered field. This generalizes the well-known fact that the computable reals form a real closed field.

With the same technique we show that the class of differences of computably enumerable reals (d.c.e. reals) and the class of computably approximable reals (c.a. reals) form real closed fields. The d.c.e. result was also proved nearly simultaneously and independently by Ng (Keng Meng Ng, Master's Thesis, National University of Singapore, in preparation).

Lastly, we show that the class of d.c.e. reals is properly contained in the class or reals less random than Ω (the halting probability), which in turn is properly contained in the class of c.a. reals, and that neither the first nor last class is a randomness class (as captured by rK-reducibility).

Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples.

We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated.

Define to be the smallest cardinality of a function f: X→Y with I, X, Y, ⊆ 2ω such that there is no Borel function g ⊇ f. In this paper we prove that it is relatively consistent with ZFC to have b < where b is, as usual, smallest cardinality of an unbounded family in Ωω. This answers a question raised by Zapletal.

We also show that it is relatively consistent with ZFC that there exists X ⊆ 2ω such that the Borei order of X is bounded but there exists a relatively analytic subset of X which is not relatively coanalytic. This answers a question of Mauldin.