We prove that in a continuous ℵ0-stable theory every type-definable group is definable. The two main ingredients in the proof are:

(i) Results concerning Morley ranks (i.e., Cantor-Bendixson ranks) from [Ben08], allowing us to prove the theorem in case the metric is invariant under the group action; and

(ii) Results concerning the existence of translation-invariant definable metrics on type-definable groups and the extension of partial definable metrics to total ones.

Dp-minimality is a common generalization of weak minimality and weak o-minimality. If T is a weakly o-minimal theory then it is dp-minimal (Fact 2.2), but there are dp-minimal densely ordered groups that are not weakly o-minimal. We introduce the even more general notion of inp-minimality and prove that in an inp-minimal densely ordered group, every definable unary function is a union of finitely many continuous locally monotonic functions (Theorem 3.2).

We provide a general theorem implying that for a (strongly) dependent theory T the theory of sufficiently well-behaved pairs of models of T is again (strongly) dependent. We apply the theorem to the case of lovely pairs of thorn-rank one theories as well as to a setting of dense pairs of first-order topological theories.

In this paper we study a certain class of Lie algebras over commutative von Neumann algebras satisfying a certain finiteness condition. By using Boolean valued methods developed by Takeuti [8]−[11], we will establish the basic structure and representation theorems.

In this paper we consider classes of quantificational formulas specified by restrictions on the number of atomic subformulas appearing in a formula. Little seems to be known about the decision problem for such classes, except that the class whose members contain at most two distinct atomic subformulas is decidable [2]. (We use “decidable” and “undecidable” throughout with respect to satisfiability rather than validity. All undecidable problems to which we refer are of maximal r.e. degree.) The principal result of this paper is the undecidability of the class of those formulas containing five atomic subformulas and with prefixes of the form ∀∃∀…∀. In fact, we show the undecidability of two sub-classes of this class: one (Theorem 1) consists of formulas whose matrices are in disjunctive normal form with two disjuncts; the other (Corollary 1) consists of formulas whose matrices are in conjunctive normal form with three conjuncts. (Theorem 1 sharpens Orevkov's result [8] that the class of formulas in disjunctive normal form with two disjuncts is undecidable.) A second corollary of Theorem 1 shows the undecidability of the class of formulas with prefixes of the form ∀…∀∃, containing six atomic subformulas, and in conjunctive normal form with three conjuncts. These restrictions to prefixes ∀∃∀…∀ and ∀…∀∃ are optimal. For by a result of the first author [5], any class of prenex formulas obtained by restricting both the number of atomic formulas and the number of universal quantifiers is reducible to a finite class of formulas, and so each such class is decidable; and the class of formulas with prefixes ∃…∃∀…∀ is, of course, decidable.

In this paper we prove that the word problem for division rings is recursively unsolvable. Our proof relies on the corresponding result for groups [7], [28], and makes essential use of P. M. Cohn's recent work [11], [13], [15], [16] on division rings.

The word problem for groups is usually formulated in terms of group presentations or finitely presented groups, as in [7], [24], [28], [30]. An equivalent formulation, in terms of the universal Horn sentences of group theory, is mentioned in [32]. This formulation makes sense for arbitrary first-order theories, and it is with respect to this formulation that we show that the word problem for division rings has degree 0′.

With PC understood to be the propositional calculus of [3], call a binary function Pr from the wffs of PC to the reals a Carnap (probability) function if it meets requirements A1—A5 in Table I (with ‘⊢…’ short in A3—A4 for ‘… is a tautology’), and call the function a Popper (probability) function if it meets requirements Bl—B6 there:

Leblanc established in [3] that every Carnap function is a Popper one, and he tendered proof of the converse. As reported by Stalnaker in [5], the proof unfortunately was incomplete, a mishap due to Leblanc's abbreviating ‘Pr(A, ∼ A) = 1’ as ‘⊢ A’ when Pr is a Popper function. Borrowing from [4], Leblanc did show, as Harper notes in [2, footnote 17], that

(1) If Pr is a Popper function and A is a tautology, then Pr(A, ∼ A) = 1. He did not, however, show that

(2) If Pr is a Popper function and Pr(A, ∼ A) = 1, then A is a tautology.

Nor could he have done so: (2) is false, as the simplest of counterexamples shows. Denied (2), Leblanc had no hope of proving that every Popper function is a Carnap one: of a Popper function Pr it is easily ascertained that Pr meets requirement A4 if and only if Pr(A, ∼ A) = 1 just in case A is a tautology.

When analyzing database query languages a roperty, of theories, the pseudo-finite homogeneity property, has been introduced and applied (cf. [3]). We show that a stable theory has the pseudo-finite homogeneity property just in case its expressive power for finite states is bounded. Moreover, we introduce the corresponding pseudo-finite saturation property and show that a theory fails to have the finite cover property if and only if it has the pseudo-finite saturation property.

Un espace ultramétrique est un ensemble muni d'une distance à valeurs dans un ordre total avec premier élément et pour laquelle tout triangle est isocèle avex deux grands côtés égaux. Les deux cas importants d'espaces ultramétriques sont:

(1) les corps valués lorsqu'on ne considère que leur structure métrique, et

(2) les ensembles Aλ, où λ est un ensemble bien ordonné, munis de la distance d(α, β) = inf {γ ∈ λ; α(γ) ≠ β(γ)} si α ≠ β et d(α, β) = 0 sinon; distance à valeurs dans l'ordre inverse de λ enrichi d'un premier élément 0.

Nous étudions ces structures dans un langage comportant un seul type de variables, les points de l'espace, et un prédicat à quatre places traduisant l'ordre sur les distances

Nous définissons la notion d'espace riche, qui est la modèle-complétion relative à un ensemble des distances fixé: un espace est riche si et seulement s'il est existentiellement clos dans toute extension qui n'ajoute pas de nouvelle distance. Les deux exemples précédemment donnés, espaces Aλ et corps valués, fournissent des espaces riches. La suite de l'article s'attache à la description des espaces riches.

Theorem. There is an effective procedure to decide whether the set of tautologies determined by a given truth-table with a finite number of elements is empty or not.

Proof. Let W(P) be a w.f.f. with a single variable P and n a given n-valued truth-table with elements (values)

Substitute 1, 2, 3, …, n in succession for P. By the usual contraction process let W(P) assume the truth-values w1, w2, w3, …, wn respectively. The sequence

will be called the value sequence of W(P).

Value sequences consisting of designated elements of exclusively will be called designated; others will be called undesignated.

All the W(P)'s will be classified in the following way:

(a) to the first class CL1 of W(P)'s there belongs the one element P,

(b) to the (t + 1)th class CLt + 1 belong all the w.f.f. which can be built up by means of one generating connective from constituent w.f.f. of which one is an element of CLt and all the others (if any) are elements of CLn ≤ t.

For example, if N and C are the connectives described by a truth-table

etc.

Let ∣CLn∣ stand for the set of value sequences of the elements of CLn.

Une bijection p de M 2 dans M est dite sans cycles, ou encore localement libre, si pour tout terme t(x 1,…,xn ) formé à partir de p, et qui n'est pas une simple variable, on a, pour tous a 1,…,an de M, t(a 1,… an ) ≠ a 1; toutes ces “fonctions-paires” sont élémentairement équivalentes, à condition, bien sûr, que l'ensemble M soit non vide, et leur théorie (parfois traduite dans un autre langage) a été considérée par divers auteurs.

Ainsi, A. Mal'cev [Mal'cev 1962] a décrit toutes les théories d'algèbre localement libres, associées à un langage fonctionnel arbitraire; O. Belegradek [Belegradek] a étudié dans le détail leurs propriétés de stabilité; F. Lucas [Lucas 1978] avait également considéré des fonctions-paires localement libres; c'est encore une fonction-paire qui a été utilisée par J. F. Pabion [Pabion 1982], pour ω1-saturer, mais pas davantage, les modèles de l'Arithmétique; il a été remarqué, dans [Poizat 1984], combien il était utile pour cela de disposer d'une théorie non superstable sans propriété de recouvrement fini; dans un tout autre contexte, et pour de tout autres raisons, cette théorie de fonctions-paires a également été utilisée dans [Poizat 1986]; tous ces emplois supposent qu'on y maîtrise bien l'élimination des quanteurs.

We prove that the strong polarized relation is consistent with ZFC, for a singular μ which is a limit of measurable cardinals.

It is shown that the many-dimensional modal logic Kn, determined by products of n-many Kripke frames, is not finitely axiomatisable in the n-modal language, for any n > 2. On the other hand, Kn is determined by a class of frames satisfying a single first-order sentence.

We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows:

• ΩU[X] is random whenever X is Σn0-complete or Πn0-complete for some n ≥ 2.

• However, for n ≥ 2, ΩU[X] is not n-random when X is Σn0 or Πn0. Nevertheless, there exists Δn+10 sets such that ΩU[X] is n-random.

• There are Δ20 sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is Δn+10 and Σn0-hard such that ΩU[X] is not random.

We also look at the range of ΩU as an operator. We prove that the set {ΩU[X]: X ⊆ 2≤ω} is a finite union of closed intervals. It follows that for any optimal machine U and any sufficiently small real r, there is a set X ⊆ 2≤ω recursive in ∅′ ⊕ r, such that ΩU[X] = r.

The same questions are also considered in the context of infinite computations, and lead to similar results.

It is shown constructively that a strongly extensional function of bounded variation on an interval is regulated, in a sequential sense that is classically equivalent to the usual one.

It is well known that the following features hold of AR + T under the strong Kleene scheme, regardless of the way the language is Gödel numbered:

1. There exist sentences that are neither paradoxical nor grounded.

2. There are fixed points.

3. In the minimal fixed point the weakly definable sets (i.e., sets definable as {n ∣ A(n) is true in the minimal fixed point}, where A(x) is a formula of AR + T) are precisely the sets.

4. In the minimal fixed point the totally defined sets (sets weakly defined by formulae all of whose instances are true or false) are precisely the sets.

5. The closure ordinal for Kripke's construction of the minimal fixed point is .

In contrast, we show that under the weak Kleene scheme, depending on the way the Gödel numbering is chosen:

1. There may or may not exist nonparadoxical, ungrounded sentences.

2. The number of fixed points may be any positive finite number, ℵ0, or .

3. In the minimal fixed point, the sets that are weakly definable may range from a subclass of the sets 1-1 reducible to the truth set of AR to the sets, including intermediate cases.

4. Similarly, the totally definable sets in the minimal fixed point range from precisely the arithmetical sets up to precisely the sets.

5. The closure ordinal for the construction of the minimal fixed point may be ω, , or any successor limit ordinal in between.

In addition we suggest how one may supplement AR + T with a function symbol interpreted by a certain primitive recursive function so that, irrespective of the choice of the Gödel numbering, the resulting language based on the weak Kleene scheme has the five features noted above for the strong Kleene language.

In the system presented by Quine in his book Mathematical logic, one can derive the Burali-Forti Paradox. It is the purpose of this paper to present the details of this derivation. For the derivation, only familiarity with Quine's book is assumed.

The present derivation is based on the derivations given by Hobson and by Whitehead and Russell.

In both these sources, the primary interest is the theory of ordinals, and the Burali-Forti Paradox is of interest only as something to be avoided. In the present paper the primary interest is the Burali-Forti Paradox, so that much of the theory of ordinals is absent from this paper and only those details remain which are relevant to the derivation of the paradox.

It has been known for six years that the restriction of Girard's polymorphic system F to atomic universal instantiations interprets the full fragment of the intuitionistic propositional calculus. We firstly observe that Tait's method of “convertibility” applies quite naturally to the proof of strong normalization of the restricted Girard system. We then show that each β-reduction step of the full intuitionistic propositional calculus translates into one or more βη-reduction steps in the restricted Girard system. As a consequence, we obtain a novel and perspicuous proof of the strong normalization property for the full intuitionistic propositional calculus. It is noticed that this novel proof bestows a crucial role to η-conversions.

The elementary calculus of binary relations as developed by Tarski in [5] may be thought of as a certain part of the first-order predicate calculus. Though less expressive, its theory (i.e. the set of its valid sentences) was shown to be undecidable by Tarski in [6]. Translated into algebraic logic this means that the equational theory of the class of relation algebras is undecidable. Similarly it can be proved that the same holds for the (sub-) class of proper relation algebras.

The idea in Tarski's proof is to describe a pairing function by which any quantifier prefix may be contracted. In this note we apply a different method to treat the case of finite structures. We prove the

Theorem. The equational theory of the class of finite proper relation algebras is undecidable.

This result was announced in [4]. The main tool is representing the graph of primitive recursive functions via the cardinalities in finite simple models of equations.