In this note, we show that the theory of tracial von Neumann algebras does not have a model companion. This will follow from the fact that the theory of any locally universal, McDuff II1 factor does not have quantifier elimination. We also show how a positive solution to the Connes Embedding Problem implies that there can be no model-complete theory of II1 factors.

We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.

Computability logic (CL) is a recently launched program for redeveloping logic as a formal theory of computability, as opposed to the formal theory of truth that logic has more traditionally been. Formulas in it represent computational problems, “truth” means existence of an algorithmic solution, and proofs encode such solutions. Within the line of research devoted to finding axiomatizations for ever more expressive fragments of CL, the present paper introduces a new deductive system CL12 and proves its soundness and completeness with respect to the semantics of CL. Conservatively extending classical predicate calculus and offering considerable additional expressive and deductive power, CL12 presents a reasonable, computationally meaningful, constructive alternative to classical logic as a basis for applied theories. To obtain a model example of such theories, this paper rebuilds the traditional, classical-logicbased Peano arithmetic into a computability-logic-based counterpart. Among the purposes of the present contribution is to provide a starting point for what, as the author wishes to hope, might become a new line of research with a potential of interesting findings—an exploration of the presumably quite unusual metatheory of CL-based arithmetic and other CL-based applied systems.

Let ε and Λ denote the sets of all nonnegative integers and isols respectively. Let σ be any subset of ε. Following [6], we shall denote the recursive equivalence type of a by Req(σ) and write σ≃τ when Req(σ) = Req(τ).

There are several areas in recursive algebra and combinatorics in which bounded or recursively bounded -classes have arisen. For our purposes we may define a -class to be a set Path(T) of all infinite paths through a recursive tree T. Here a recursive tree T is just a recursive subset of ω<ω, the set of all finite sequences of the natural numbers ω = {0,1,2,…}, which is closed under initial segments. If the tree T is finitely branching, then we say the -class Path(T) is bounded. If T is highly recursive, i.e., if there exists a partial recursive function f: T→ω such that for each node ηЄ T, f(η) equals the number of immediate successors of η, then we say that the -class Path(T) is recursively bounded (r.b.). For example, Manaster and Rosenstein in [6] studied the effective version of the marriage problem and showed that the set of proper marriages for a recursive society S was always a bounded -class and the set of proper marriages for a highly recursive society was always an r.b. -class. Indeed, Manaster and Rosenstein showed that, in the case of the symmetric marriage problem, any r.b. -class could be represented as the set of symmetric marriages of a highly recursive society S in the sense that given any r.b. Π1-class C there is a society Sc such that there is a natural, effective, degree-preserving 1:1 correspondence between the elements of C and the symmetric marriages of Sc. Jockusch conjectured that the set of marriages of a recursive society can represent any bounded -class and the set of marriages of a highly recursive society can represent any r.b. -class. These conjectures remain open. However, Metakides and Nerode [7] showed that any r.b. -class could be represented by the set of total orderings of a recursive real field and vice versa that the set of total orderings of a recursive real field is always an r.b. -class.

In [10] we introduced a new first order language for valued fields. This language has three sorts of variables, namely variables for elements of the valued field, variables for elements of the residue field and variables for elements of the value group. contains symbols for the standard field, residue field, and value group operations and a function symbol for the valuation. Essential in our language is a function symbol for an angular component map modulo P, which is a map from the field to the residue field (see Definition 1.2).

For this language we proved a quantifier elimination theorem for Henselian valued fields of equicharacteristic zero which possess such an angular component map modulo P [10, Theorem 4.1]. In the first section of this paper we give some partial results on the existence of an angular component map modulo P on an arbitrary valued field.

By applying the above quantifier elimination theorem to ultraproducts ΠQp/D, we obtained a quantifier elimination, in the language , for the p-adic field Qp; and this elimination is uniform for almost all primes p [10, Corollary 4.3]. In §2 we prove that our language is essentially stronger than the natural language for p-adic fields in the sense that the angular component map modulo P cannot be defined, uniformly for almost all p, in terms of the natural language for p-adic fields.

We present a new proof for the standardization theorem in λ-calculus, which is largely built upon a structural induction on λ-terms. We then extract some bounds for the number of β-reduction steps in the standard β-reduction sequence obtained from transforming a given β-reduction sequence, sharpening the standardization theorem. As an application, we establish a super exponential bound for the lengths of β-reduction sequences from any given simply typed λ-terms.

We say that a first order theory T is locally finite if every finite part of T has a finite model. It is the purpose of this paper to construct in a uniform way for any consistent theory T a locally finite theory FIN(T) which is syntactically (in a sense) isomorphic to T.

Our construction draws upon the main idea of Paris and Harrington [6] (I have been influenced by some unpublished notes of Silver [7] on this subject) and generalizes the syntactic aspect of their result from arithmetic to arbitrary theories. (Our proof is syntactic, and it is simpler than the proofs of [5], [6] and [7]. This reminds me of the simple syntactic proofs of several variants of the Craig-Lyndon interpolation theorem, which seem more natural than the semantic proofs.)

The first mathematically strong locally finite theory, called FIN, was defined in [1] (see also [2]). Now we get much stronger ones, e.g. FIN(ZF).

From a physicalistic point of view the theorems of ZF and their FIN(ZF)-counterparts may have the same meaning. Therefore FIN(ZF) is a solution of Hilbert's second problem. It eliminates ideal (infinite) objects from the proofs of properties of concrete (finite) objects.

In [4] we will demonstrate that one can develop a direct finitistic intuition that FIN(ZF) is locally finite. We will also prove a variant of Gödel's second incompleteness theorem for the theory FIN and for all its primitively recursively axiomatizable consistent extensions.

The results of this paper were announced in [3].

We prove the independence of a strong partition relation on ℵω, answering a question of Erdös and Hajnal. We then give an almost complete answer to the free subset problem.

The results of the present paper were announced in [1]. The work is divided into our parts. In the first part we define relations (relations between relational struc tures) and we show their connection with the equivalence of the languages LΚ,λ (Theorem 1). The relations generalize the games Gn (n < ω) of Ehrenfeucht (see [2]) and the conditions (i)–(ii) which were used by Karp in [5].

We present a logical and algebraic description of right adjoint functors between generalized quasi-varieties, inspired by the work of McKenzie on category equivalence. This result is achieved by developing a correspondence between the concept of adjunction and a new notion of translation between relative equational consequences.

It was a fundamental insight of Shelah that the equivalence classes of a definable equivalence relation on a structure M often behave like (and indeed must be treated like) the elements of the structure itself, and that these so-called imaginary elements are both necessary and sufficient for developing many aspects of stability theory. The expanded structure Meq was introduced to make this insight explicit and manageable. In Meq we have “names” for all things (subsets, relations, functions, etc.) “definable” inside M. Recent results of Bruno Poizat allow a particularly simple and more or less algebraic modification of Meq in the case that M is a module. It is the purpose of this paper to describe this nearly algebraic structure in such a way as to make the usual algebraic tools of the model theory of modules readily available in this more general context. It should be pointed out that some of our discussion has been part of the “folklore” of the subject for some time; it is certainly time to make this “folklore” precise, correct, and readily available.

Modules have proved to be good examples of stable structures. Not, we mean, in the sense that they are well-behaved (which, in the main, they are), but in the sense that they are straightforward enough to provide comprehensible illustrations of concepts while, at the same time, they have turned out to be far less atypical than one might have supposed. Indeed, a major feature of recent stability theory has been the ubiquitous appearance of modules or more general “abelian structures” in abstract stable structures.

Tychonoff's theorem states that a product of compact spaces is compact. In [3], P. Johnstone presents a proof of Tychonoff's theorem in a “localic” framework. The surprise is that the point-free formulation of Tychonoff's theorem is provable without the axiom of choice, whereas in the usual formulation it is equivalent to the axiom of choice (see Kelley [5]).

The proof given in [3], however, is classical and seems to use the replacement axiom of Zermelo-Fraenkel. The aim of this paper is to present what we believe to be a more direct proof, which is intuitionistic and can be proved using as primitive only the notion of inductive definition, as it is for instance presented in Martin-Löf [6]. One main point of the paper is to show that the theory of locales can be developed rather naturally in the framework of inductive definitions. We think that our arguments can be presented in the constructive set theory of Aczel [2].

The paper is organized as follows. In §1 we show the argument in the case of a product of two spaces. This proof has a direct generalisation to the case of a product over a set with a decidable equality.

§1. Product of two spaces. We first recall a possible definition of a point-free space (see Johnstone [3] or Vickers [10]). It is a poset (X, ≤), together with a meet operation ab, written multiplicatively, and, for each a ∈ X, a set Cov(a) of subsets of {x ∈ X ∣ x ≤ a}. We ask that if M ∈ Cov(a) and b ≤ a, then {bs ∈ s ∈ M} ∈ Cov(b). This property of Cov will be called the axiom of covering. The elements of Cov(u) are called basic covers of u ∈ X.

Let ⊥, →, and □ be primitive, and let us have a countable supply of propositional letters. By a (modal) logic we understand a proper subset of the set of all formulas containing every tautology and being closed under modus ponens and substitution. A logic is regular if it contains every instance of □A ∧ □B ↔ □(A ∧ B) and is closed under the rule

A regular logic is normal if it contains □⊤. The smallest regular logic we denote by C (the same as Lemmon's C2), the smallest normal one by K. If L and L' are logics and L ⊆ L′, then L is a sublogic of L', and L' is an extension of L; properly so if L ≠ L'. A logic is quasi-regular (respectively, quasi-normal) if it is an extension of C (respectively, K).

A logic is Post complete if it has no proper extension. The Post number, denoted by p(L), is the number of Post complete extensions of L. Thanks to Lindenbaum, we know that

There is an obvious upper bound, too:

Furthermore,

.

Louveau and Rosendal [5] have shown that the relation of bi-embeddability for countable graphs as well as for many other natural classes of countable structures is complete under Borel reducibility for analytic equivalence relations. This is in strong contrast to the case of the isomorphism relation, which as an equivalence relation on graphs (or on any class of countable structures consisting of the models of a sentence of ) is far from complete (see [5, 2]).

In this article we strengthen the results of [5] by showing that not only does bi-embeddability give rise to analytic equivalence relations which are complete under Borel reducibility, but in fact any analytic equivalence relation is Borel equivalent to such a relation. This result and the techniques introduced answer questions raised in [5] about the comparison between isomorphism and bi-embeddability. Finally, as in [5] our results apply not only to classes of countable structures defined by sentences of , but also to discrete metric or ultrametric Polish spaces, compact metrizable topological spaces and separable Banach spaces, with various notions of embeddability appropriate for these classes, as well as to actions of Polish monoids.

In 1985 the second author showed that if there is a proper class of measurable Woodin cardinals and and are generic extensions of V satisfying CH then and agree on all Σ12-statements. In terms of the strong logic Ω-logic this can be reformulated by saying that under the above large cardinal assumption ZFC + CH is Ω-complete for Σ12. Moreover, CH is the unique Σ12-statement with this feature in the sense that any other Σ12-statement with this feature is Ω-equivalent to CH over ZFC. It is natural to look for other strengthenings of ZFC that have an even greater degree of Ω-completeness. For example, one can ask for recursively enumerable axioms A such that relative to large cardinal axioms ZFC + A is Ω-complete for all of third-order arithmetic. Going further, for each specifiable segment Vλ of the universe of sets (for example, one might take Vλ to be the least level that satisfies there is a proper class of huge cardinals), one can ask for recursively enumerable axioms A such that relative to large cardinal axioms ZFC + A is Ω-complete for the theory of Vλ. If such theories exist, extend one another, and are unique in the sense that any other such theory B with the same level of Ω-completeness as A is actually Ω-equivalent to A over ZFC, then this would show that there is a unique Ω-complete picture of the successive fragments of the universe of sets and it would make for a very strong case for axioms complementing large cardinal axioms. In this paper we show that uniqueness must fail. In particular, we show that if there is one such theory that Ω-implies CH then there is another that Ω-implies ¬-CH.

The Baire number of the real line (see 1.1(c)) has uncountable cofinality [Mi]. This number is equal to the Baire number of the space 2ω and also to the Baire number (1.1(d)) of every countable partial order. Our research is motivated by the following open question (1.13) (see also [BPS] and [Mi]): can the cofinality of nκ, the Baire number of the space (2κ)κ (1.1(b)), be less than or equal to κ? This question is nontrivial when κ is regular and 2κ = κ (1.3). A. Miller proved that the answer is “no” if κ is strongly inaccessible (see [Mi] and 1.11). Assuming CH, is equal to the Baire number of the Stone space of ℘(ω)/Fin.

In §1 we discuss , the Baire number of the space (2λ)κ. If κ is regular, then , and using 1.3 and 1.5, we may rule out the easy cases and restrict ourselves to cases where κ is regular with 2<κ = κ, and κ ≤ λ 2κ. If λ > κ, then it is consistent to have cof()=κ ([Mi] and 1.7). We do not know whether is consistent (1.9). Next, the cardinal number eκ is defined (1.10). It is easy to see that nκ ≤ eκ and that cof(eκ) > κ. If κ is strongly inaccessible (s.i.), then nκ = eκ ([Mil], [Bar], [MF] and 1.11). For κ accessible, the question of whether nκ = eκ is open.

Another open question (Fremlin) is stated as follows: assume W ⊇ V and f ∈ ωω ∩ W is such that, for every g ∈ ω ω ∩ V, ∣(f = g)∣ = ℵ0, does this imply that W contains sets which are ω-Cohen (1.1(a)) over V? If κ is accessible regular with 2<κ = κ, then the answer to the analog of Fremlin's question for κ is “no”. In fact, any κ-closed forcing that adds new subsets of κ, also adds a new function f ∈ κκ such that, for every g ∈ κκ ∩V, (f = g) is stationary (4.1(a)). On the other hand, perfect-set forcing on κ (see [Ka] and §5) adds a new subset of κ but produces a minimal extension (5.4(b)), and hence adds no sets which are κ-Cohen over V.

Given a finite relational language L is there an algorithm that, given two finite sets and of structures in the language, determines how many homogeneous L structures there are omitting every structure in and embedding every structure in ?

For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments Γ, determines whether Γ, the class of finite tournaments omitting every tournament in Γ. is well-quasi-order?

First, we give a nonconstructive proof of the existence of an algorithm for the case in which Γ consists of one tournament. Then we determine explicitly the set of tournaments each of which does not have an antichain omitting it. Two antichains are exhibited and a summary is given of two structure theorems which allow the application of Kruskal's Tree Theorem. Detailed proofs of these structure theorems will be given elsewhere.

The case in which Γ consists of two tournaments is also discussed.

Comparability of classes. Till now we tried to get along without the axioms Vc and Vd. We found that this is possible in number theory and analysis as well as in general set theory, even keeping in the main to the usual way of procedure.

For the considerations of the present section application of the axioms Vc, Vd is essential. Our axiomatic basis here consists of the axioms I—III, V*, Vc, and Vd. From V*, as we know, Va and Vb are derivable. We here take axiom V* in order to separate the arguments requiring the axiom of choice from the others. Instead of the two axioms V* and Vc, as was observed in Part II, V** may be taken as well.

We present a comparatively simple way to construct Martin-Löf random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of Gács and Kučera, for any given set X we construct a Martin-Löf random set from which X can be decoded effectively.

By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-Löf random sets that are computably enumerable self-reducible. The two latter results complement the known facts that no rec-random set is truth-table autoreducible and that no Martin-Löf random set is Turing-autoreducible [8, 24].