We define, in the spirit of Fenstad [2], a higher type computation theory, and show that countable recursion over the continuous functionals forms such a theory. We also discuss Hyland's proposal from [4] for a scheme with which to supplement S1–S9, and show that this augmented set of schemes fails to generate countable recursion. We make another proposal to which the methods of this section do not apply.

The main purpose of this paper is to show how partial recursive functions and isols can be used to generalize the following three well-known theorems of combinatorial theory.

(I) For every finite projective plane Π there is a unique number n such that Π has exactly n 2 + n + 1 points and exactly n 2 + n + 1 lines.

(II) Every finite projective plane of order n can be coordinatized by a finite planar ternary ring of order n. Conversely, every finite planar ternary ring of order n coordinatizes a finite projective plane of order n.

(III) There exists a finite projective plane of order n if and only if there exist n − 1 mutually orthogonal Latin squares of order n.

Let ZFB be ZF + “every set is the same size as a wellfounded set”. Then the following are true.

Every sentence true in every (Rieger-Bernays) permutation model of a model of ZF is a theorem of ZFB. (i.e., ZFB is the theory of Rieger-Bernays permutation models of models of ZF) ZF and ZFAFA are both extensions of ZFB conservative for stratified formulæ. The class of models of ZFB is closed under creation of Rieger-Bernays permutation models.

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.

Dowker [1] raised the question of the existence of filters such that for every coloring (partition) of the underlying index set I with two colors there is a relation R on I which (i) is fat (in the sense that sets of the form {y Є I∣xRy} are in the filter) and (ii) has no bichromatic symmetric pairs (i.e., distinct indices x and y such that x R y and y R x). Additionally, he required that the filter have no anti-symmetric fat relation, for such a relation would vacuously satisfy (i) and (ii). The question of the existence of Dowker filters has been studied more recently by Rudin [3], [4], who conjectures [3] that such filters do not exist.

For ZFC the problem remains open. However, Example 2 of this paper shows that one can construct a Dowker filter provided one drops the axiom of choice in favor of the Baire Property (BP) axiom which is known to be incompatible with ZFC but relatively consistent with ZF. In fact, the filter constructed is super-Dowker in the sense that (ii) can be replaced by the requirement that all components of all symmetric pairs have the same color. But, in ZFC the existence of a super-Dowker filter implies the existence of a measurable cardinal.

Let F be a filter on an index set I. A set will be called big, small, or medium depending on whether F contains that set, its compliment, or neither, respectively. We define five cardinals associated with F:

α denotes the smallest cardinal such that there is a family of α big sets whose intersection is not big.

ν denotes the smallest cardinal such that there is a family of ν big sets whose intersection is small.

It is known that the spectrum of a Boolean algebra cannot contain a low4 degree unless it also contains the degree 0; it remains open whether the same holds for low5 degrees. We address the question differently, by considering Boolean subalgebras of the computable atomless Boolean algebra . For such subalgebras , we show that it is possible for the spectrum of the unary relation on to contain a low5 degree without containing 0.

In attempting to reconstruct Rose's proof of Lemma 3.2 of [1], the present authors found what is apparently a different and simpler method, which moreover leads to a far stronger conclusion.

We are operating in the Heyting prepositional calculus as formulated on p. 3 of [1] or on pp. 82 and 101 of [2], and shall make use of relevant theorems on pp. 90, 113–119 of [2]. We shall use a, b, c, w, x, y, z as propositional variables.

We say that a conjunction is simple if each factor has one of the forms: (i) a, (ii) ¬a, (iii) a⊃b, (iv) a⊃(b∨c), (v) (a&b)⊃c, (vi) (a⊃b)⊃c.

With each projective geometry we can associate a Lyndon algebra. Such an algebra always satisfies Tarski's axioms for relation algebras and Lyndon algebras thus form an interesting connection between the fields of projective geometry and algebraic logic. In this paper we prove that if G is a class of projective geometries which contains an infinite projective geometry of dimension at least three, then the class L(G) of Lyndon algebras associated with projective geometries in G has an undecidable equational theory. In our proof we develop and use a connection between projective geometries and diagonal-free cylindric algebras.