Some propositional logics (e.g. the classical system) can be characterized by a finite model, while others (e.g. Heyting's) which have the finite model property (FMP) can be characterized by an infinite set of finite models. Still others (e.g. certain extensions of Heyting's logic) which lack the FMP can only be characterized by a set of models, at least one of which is infinite. Yet all these logics admit finite models even though they may not be characterized by them. (For example, they all admit the 2-element Boolean algebra as a model in the sense that all their theorems are valid on that algebra when the propositional connectives are interpreted in the usual manner.) The object of the present paper is to give a (not too artificial) example of a propositional logic which is consistent and which admits only infinite models. It therefore lacks the FMP in a very strong sense. Such a propositional logic, I shall call hyperinfinite. The existence of hyperinfinite logics was already plausible from a result in abstract algebra which says that there are varieties of algebras of which the only finite element is the trivial algebra (see [3]).

I wish to thank Professor A. S. Troelstra, Amsterdam, for comments on an early version of this paper. The constructive criticism of two anonymous referees has also been useful.

The hyperinfinite propositional logic to be described is obtained from Positive Logic—the negative-free part of Heyting's logic—by adjoining certain axioms which govern the use of a unary modal connective.

We prove the hereditary undecidability of the Lt theories of:

(1) torsion-free Hausdorff topological abelian groups;

(2) locally pure Hausdorff topological abelian groups.

Let T be an inductive, first-order theory in a language L, let E(L) denote the set of existential L-formulas, and let E(T) denote the distributive lattice of equivalence-classes φT of formulas φ ∈ E(L) with respect to equivalence in T. We consider three types of ‘complements’ in E(T): Let φT, ψT ∈ E(T) and suppose φT ∏ ψT = 0. Then ψT is a complement of φT, if φT ∐ ψT = 1; ψT is a pseudo-complement of φT, if for all μT ∈ E(T), (φT ∐ ψT) = 0 implies μT ≤ ψT; ψT is a “weak complement of φT, if for all μT ∈ E(T), (φT ⋰ ψT) ∐ μT = 0 implies μT = 0. The following facts are obvious: A complement of φT is also a pseudo-complement of φT and a pseudo-complement of φT is also a weak complement of φT. Any φT has at most one pseudo-complement; it is denoted by φT*. The relations ‘ψT is the complement of φT’ and ‘ψT is a weak complement of φT’ are symmetrical. We call φT (weakly, pseudo-) complemented if φT has a (weak, pseudo-) complement, and we call E(T) (weakly, pseudo-) complemented if every φT is (weakly, pseudo-) complemented.

The object of this note is to characterize (weakly, pseudo-) complemented existential formulas in model-theoretic terms, and conversely to characterize some classical notions of Robinson style model theory in terms of these formulas. The following theorems illustrate the second approach.

Inasmuch as my discussion of the formal properties of “System L,” presented elsewhere, is substantially the same as that presented by Lewis in a previous issue of this Journal, I shall confine my remarks in this brief rejoinder to the problem of deducibility with respect to necessary and impossible propositions—since it is specifically the solution of this problem which will determine the adequacy of the calculus of logical implication as a canon and critique of deductive inference.

The problem, as originally presented, can be stated succinctly in the following inconsistent triad: (1) All necessarily true principles are logically dependent on or deducible from one another, i.e., are equivalent, (2) All principles of logic and mathematics are necessarily true, and (3) Some principles of logic and mathematics are not logically dependent on or deducible from one another, i.e., are independent. These three propositions are logically inconsistent in the sense that the conjunction of any two of them will logically imply the falsity of the third. Now if Lewis should affirm the first and third of these propositions, then he should concede the falsity of the second. This concession, it was believed, he was not likely to make, inasmuch as it would seem to involve a repudiation of a doctrine (the tautological character of every logical and mathematical truth) with which he has particularly identified himself. If, in view of this fact, he should accept, instead, the second and third of these propositions, then he should concede the falsity of the first.

It is known [4, Theorem 11-X(b)] that there is only one acceptable universal function up to recursive isomorphism. It follows from this that sets definable in terms of a universal function alone are specified uniquely up to recursive isomorphism. (An example is the set K, which consists of all n such that {n}(n) is defined, where λn, m{n}(m) is an acceptable universal function.) Many of the interesting sets constructed and studied by recursion theorists, however, have definitions which involve additional notions, such as a specific enumeration of the graph of a universal function. In particular, many of these definitions make use of the interplay between the purely number-theoretic properties of indices of partial recursive functions and their purely recursion-theoretic properties.

This paper concerns r.e. sets that can be defined using only a universal function and some purely number-theoretic concepts. In particular, we would like to know when certain recursion-theoretic properties of r.e. sets definable in this way are independent of the particular choice of universal function (equivalently, independent of the particular way in which godel numbers are identified with natural numbers).

We will first develop a suitable model-theoretic framework for discussing this question. This will enable us to classify the formulas defining r.e. sets by their logical complexity. (We use the number of alternations of quantifiers in the prenex form of a formula as a measure of logical complexity.) We will then be able to examine the question at each level.

This work is an approach to the question of when the recursion-theoretic properties of an r.e. set are independent of the particular parameters used in its construction. As such, it does not apply directly to the construction techniques most commonly used at this time for defining particular r.e. sets, e.g., the priority method. A more direct attack on this question for these techniques is represented by such works as [3] and [5]. However, the present work should be of independent interest to the logician interested in recursion theory.

Let = ⟨M, +, <, 0, S⟩ be a linear o-minimal expansion of an ordered group, and G = ⟨G, ⊕,eG ) an n-dimensional group definable in . We show that if G is definably connected with respect to the t-topology, then it is definably isomorphic to a definable quotient group U/L. for some convex ∨-definable subgroup U of ⟨Mn , +⟩ and a lattice L of rank equal to the dimension of the ‘compact part’ of G.

We shall prove the following theorem:

Theorem. For any finite lattice there is a model of ZF in which the partial ordering of the degrees of constructibility is isomorphic with the given lattice.

Let M be a standard countable model of ZF satisfying V = L. Let K be the given finite lattice. We shall extend M by forcing.

The paper is divided into two parts. The first part concerns the definition of the set of forcing conditions and some properties of this set expressible without the use of generic filters.

We define first a representation of a lattice and then the set of conditions. In Lemmas 1, 2 we show that there are some canonical isomorphisms between some conditions and that a single condition has some canonical automorphisms.

In Lemma 3 and Definition 7 we show some methods of defining conditions. We shall use those methods in the second part to define certain conditions with special properties.

Lemma 4 gives a connection between the sets P and Pk (see Definitions 4 and 5). It is next employed in the second part in Lemma 10 in an essential way.

Indeed, Lemma 10 is necessary for Lemma 13, which is the crucial point of the whole construction. Lemma 5 is also employed in Lemma 13 (exactly in its Corollary).

The second part of the paper is devoted to the examination of the structure of degrees of constructibility in a generic model. First, we show that degrees of some “sections” of a generic real (Definition 9) form a lattice isomorphic with K. Secondly, we show that there are no other degrees in the generic model; this is the most difficult property to obtain by forcing. We prove, in two stages, that it holds in our generic models. We first show, by using special properties of the forcing conditions, that sets of ordinal numbers have no other degrees. Then we show that the degrees of sets of ordinals already determine the degrees of other sets.

In a series of papers [K2], [K3], [K4], E. M. Kleinberg established the extensive properties of what are now called “strong partition cardinals”, cardinals satisfying for all λ < κ. The purpose of this note is to show that all these consequences and the results in [H] and [W] can be obtained from the weaker relation and many from .

We assume the reader is generally familiar with Kleinberg's machinery and with the definition of . We recall that a cardinal κ satisfies iff for every partition F: [κ]κ → A there is a p ∈ [κ]κ such that F″ [p]κ ≠ A. We take the liberty of regarding a p ∈ [κ]κ both as a subset of κ and as a function from κ to κ. We assume DC throughout.

§1. From. Our results stem from the observation that the proofs in the papers cited above only require homogeneous sets for certain classes of partitions.

Definition. A partition F: [κ]κ → λ, λ < λ, is called clopen if for all p ∈ [κ]κ there is an α < κ such that whenever -clopen is the assertion that all clopen partitions have homogeneous sets (Spector-Watro).