In the design of multiple input-output logical systems, the authors have previously formulated and proved a computer program for obtaining optimal system representations satisfying three optimality criteria [1]. In that program, the need for obtaining prime implicants occurred. Two algorithms for this purpose are available in the literature; one due to Quine [2] and one due to Nelson [3], [4]. Nelson's, briefly, is to express the function (whose prime implicants are desired) as a product of sums of literals, multiply out, and discard repeated literals save one and proper multiples. (To obtain the function in the initial form, one can start with the complement of the function expressed as a sum of products and complement it using De Morgan's theorem.) In using these algorithms, it became apparent to us that in certain cases one of these two algorithms required less computer time than the other one. In particular, if the given system has a large number of don't cares then the Nelson algorithm seemed to be preferred [5]. Also in the case of a single function, if there are few zeroes in the truth table representation for the function, then Nelson's algorithm is preferable. It also became apparent to us that in certain situations one needs a generalized version of the Nelson algorithm.

We show that IE1 proves that every element greater than 1 has a unique factorization into prime powers, although we have no way of recovering the exponents from the prime powers which appear. The situation is radically different in Bézout models of open induction. To facilitate the construction of counterexamples, we describe a method of changing irreducibles into powers of irreducibles, and we define the notion of a frugal homomorphism into , the product of the p-adic integers for each prime p.

L'objet de ce texte est de montrer que des fonctions qui appartiennent à une famille vérifiant une propriété de finitude a priori non uniforme sont en fait définissables dans une structure o-minimale.

Although a variety of proofs are available for the Craig-Lyndon Interpolation Lemma, they all seem to make essential use of negation, with the result that they are inapplicable to deductive theories in which negation cannot be expressed. It is here shown that this use of negation can be avoided by extending the Interpolation Lemma to the pure implicational calculus PCI.

Determinate Parameter Lemma. For each formula A, ⊨PA ⊃ A for some sentence parameter PA occurring in A.

Proof. By induction on the construction of A.

Interpolation Lemma For PCI. Let Γ be the set of sentence parameters common to A and C.If ⊨A ⊃ and C is not valid, then there is a formula B containing no sentence parameter not in Y such that ⊨A ⊃ B and ⊨B ⊃ C.

Proof. Since ⊨PA ⊃ A by the Determinate Parameter Lemma and ⊨A ⊃ C, ⊨PA ⊃ C. But C is by hypothesis an invalid formula, so PA must occur in C as well as in A. Thus PA Є Γ.

An Ax-Kochen-Ershov principle for intermediate structures between valued groups and valued fields.

We will consider structures that we call valued B-groups and which are of the form 〈G, B, *, υ〉 where

– G is an abelian group,

– B is an ordered group,

– υ is a valuation denned on G taking its values in B,

– * is an action of B on G satisfying: ∀x ϵ G ∀ b ∈ B υ(x * b) = ν(x) · b.

The analysis of Kaplanski for valued fields can be adapted to our context and allows us to formulate an Ax-Kochen-Ershov principle for valued B-groups: we axiomatise those which are in some sense existentially closed and also obtain many of their model-theoretical properties. Let us mention some applications:

1. Assume that υ(x) = υ(nx) for every integer n ≠ 0 and x ϵ G, B is solvable and acts on G in such a way that, for the induced action, Z[B] ∖ {0} embeds in the automorphism group of G. Then 〈G, B, *, υ〉 is decidable if and only if B is decidable as an ordered group.

2. Given a field k and an ordered group B, we consider the generalised power series field k((B)) endowed with its canonical valuation. We consider also the following structure:

where k((B))+ is the additive group of k((B)), S is a unary predicate interpreting {Tb ∣ b ϵB}, and ×↾k((B))×S is the multiplication restricted to k((B)) × S, structure which is a reduct of the valued field k((B)) with its canonical cross section. Then our result implies that if B is solvable and decidable as an ordered group, then M is decidable.

3. A valued B–group has a residual group and our Ax-Kochen-Ershov principle remains valid in the context of expansions of residual group and value group. In particular, by adding a residual order we obtain new examples of solvable ordered groups having a decidable theory.

We consider arbitrary stratified languages. We study structures which satisfy the same stratified sentences and we obtain an extension of Keisler's Isomorphism Theorem to this situation. Then we consider operations which are definable by a stratified formula and modify the ‘type’ of their argument by one; we prove that for such an operation F the sentence c = F(c) and the scheme φ(c) ↔ (F(c)), where ↔(x) varies among all the stratified formulas with no variable other than x free, imply the same stratified {c}-sentences.

In [7] we proved that (I) if T is a countable ℵ0-categorical theory without finite models then T has a model companion; and several people have observed that (II) if T is a countable theory without finite models which is ℵ1-categorical and forcingcomplete for infinite forcing (i.e., T= TF) then T is model-complete. It is natural to ask (1) whether in (I) we can replace ℵ0 by ℵ1; (2) whether in (II) we can replace TF by Tf; and (3) in connection with (II), whether the categoricity of the class of infinitely generic structures for a theory K in some or all infinite powers implies the existence of a model companion for K. The purpose of this note is to provide negative answers to (1), (2), and (3). Specifically, we will prove:

Theorem. There exists a countable theory T such that

(i) T has no finite models and is ℵ-categorical;

(ii) T is forcing-complete for finite forcing, i.e., T = Tf;

(iii) T has no model companion (i.e., in light of (ii), T is not model-complete);

(iv) the class of infinitely generic structures for T is categorical in every infinite power;

(v) every uncountable existentially complete structure for T is infinitely generic;

(vi) there is, up to isomorphism, precisely one countable existentially complete model of Tf, and there are no uncountable e.c. models of Tf (in particular, there is just one countable finitely generic structure and there are no uncountable ones);

(vii) there are precisely ℵ0isomorphism types of countable existentially complete structures for T.

Let L be one of the topological languages Lt, (L∞ω)t and (Lκω)t. We characterize the topological spaces which are models of the L-theory of the class of ordinals equipped with the order topology. The results show that the role played in classical model theory by the property of being well-ordered is taken over in the topological context by the property of being locally compact and scattered.

In this paper we characterize the well-known computational complexity classes of the polynomial time hierarchy as classes of provably recursive functions (with graphs of suitable bounded complexity) of some second order theories with weak comprehension axiom schemas but without any induction schemas (Theorem 6). We also find a natural relationship between our theories and the theories of bounded arithmetic (Lemmas 4 and 5). Our proofs use a technique which enables us to “speed up” induction without increasing the bounded complexity of the induction formulas. This technique is also used to obtain an interpretability result for the theories of bounded arithmetic (Theorem 4).

The general theory developed by Ben Yaacov for metric structures provides Fraïssé limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an extra condition that guarantees exact ultrahomogenous limits. The condition is quite general. We apply it to stochastic processes, the class of diversities, and its subclass of $L_1$ diversities.

The $\Omega $ numbers—the halting probabilities of universal prefix-free machines—are known to be exactly the Martin-Löf random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-Löf random left-c.e. real $\alpha $ , a universal prefix-free machine U whose halting probability is $\alpha $ . We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real $\alpha $ , one cannot uniformly produce a left-c.e. real $\beta $ such that $\alpha - \beta $ is neither left-c.e. nor right-c.e.