A logic is said to admit an equational completeness theorem when it can be interpreted into the equational consequence relative to some class of algebras. We characterize logics admitting an equational completeness theorem that are either locally tabular or have some tautology. In particular, it is shown that a protoalgebraic logic admits an equational completeness theorem precisely when it has two distinct logically equivalent formulas. While the problem of determining whether a logic admits an equational completeness theorem is shown to be decidable both for logics presented by a finite set of finite matrices and for locally tabular logics presented by a finite Hilbert calculus, it becomes undecidable for arbitrary logics presented by finite Hilbert calculi.

Working in ZFC, we show that for any infinite cardinal k and ordinal y < (2<k)+ the polarized partition relation

holds. Our proof of this relation involves the use of elementary substructures of set models of large fragments of ZFC.

Being able to state the principles which lie deepest in the foundations of mathematics by sentences in three variables is crucially important for a satisfactory equational rendering of set theories along the lines proposed by Alfred Tarski and Steven Givant in their monograph of 1987.

The main achievement of this paper is the proof that the ‘kernel’ set theory whose postulates are extensionality. (E), and single-element adjunction and removal. (W) and (L), cannot be axiomatized by means of three-variable sentences. This highlights a sharp edge to be crossed in order to attain an ‘algebraization’ of Set Theory. Indeed, one easily shows that the theory which results from the said kernel by addition of the null set axiom, (N), is in its entirety expressible in three variables.

We show that a Kueker simple theory eliminates ∃∞ and densely interprets weakly minimal formulas. As part of the proof we generalize Hrushovski's dichotomy for almost complete formulas to simple theories. We conclude that in a unidimensional simple theory an almost-complete formula is either weakly minimal or trivially-almost-complete. We also observe that a small unidimensional simple theory is supersimple of finite SU-rank.

Soare [20] proved that the maximal sets form an orbit in ${\cal E}$. We consider here ${\cal D}$-maximal sets, generalizations of maximal sets introduced by Herrmann and Kummer [12]. Some orbits of ${\cal D}$-maximal sets are well understood, e.g., hemimaximal sets [8], but many are not. The goal of this paper is to define new invariants on computably enumerable sets and to use them to give a complete nontrivial classification of the ${\cal D}$-maximal sets. Although these invariants help us to better understand the ${\cal D}$-maximal sets, we use them to show that several classes of ${\cal D}$-maximal sets break into infinitely many orbits.

Tarski [5] showed that for any set X, its set ω(X) of well-orderable subsets has cardinality strictly greater than that of X, even in the absence of the axiom of choice. We construct a Fraenkel-Mostowski model in which there is an infinite strictly descending sequence under the relation ∣ω(X)∣ = ∣Y∣. This contrasts with the corresponding situation for power sets, where use of Hartogs' ℵ-function easily establishes that there can be no infinite descending sequence under the relation .

We introduce the Hausdorff measure for definable sets in an o-minimal structure, and prove the Cauchy–Crofton and co-area formulae for the o-minimal Hausdorff measure. We also prove that every definable set can be partitioned into “basic rectifiable sets”, and that the Whitney arc property holds for basic rectifiable sets.

It is a celebrated result of McKinsey and Tarski [28] that S4 is the logic of the closure algebra Χ+ over any dense-in-itself separable metrizable space. In particular, S4 is the logic of the closure algebra over the reals R, the rationals Q, or the Cantor space C. By [5], each logic above S4 that has the finite model property is the logic of a subalgebra of Q+, as well as the logic of a subalgebra of C+. This is no longer true for R, and the main result of [5] states that each connected logic above S4 with the finite model property is the logic of a subalgebra of the closure algebra R+.

In this paper we extend these results to all logics above S4. Namely, for a normal modal logic L, we prove that the following conditions are equivalent: (i) L is above S4, (ii) L is the logic of a subalgebra of Q+, (iii) L is the logic of a subalgebra of C+. We introduce the concept of a well-connected logic above S4 and prove that the following conditions are equivalent: (i) L is a well-connected logic, (ii) L is the logic of a subalgebra of the closure algebra $\xi _2^ + $ over the infinite binary tree, (iii) L is the logic of a subalgebra of the closure algebra ${\bf{L}}_2^ + $ over the infinite binary tree with limits equipped with the Scott topology. Finally, we prove that a logic L above S4 is connected iff L is the logic of a subalgebra of R+, and transfer our results to the setting of intermediate logics.

Proving these general completeness results requires new tools. We introduce the countable general frame property (CGFP) and prove that each normal modal logic has the CGFP. We introduce general topological semantics for S4, which generalizes topological semantics the same way general frame semantics generalizes Kripke semantics. We prove that the categories of descriptive frames for S4 and descriptive spaces are isomorphic. It follows that every logic above S4 is complete with respect to the corresponding class of descriptive spaces. We provide several ways of realizing the infinite binary tree with limits, and prove that when equipped with the Scott topology, it is an interior image of both C and R. Finally, we introduce gluing of general spaces and prove that the space obtained by appropriate gluing involving certain quotients of L2 is an interior image of R.

We study the following classes:

● Q* (r1A1…..rkAk) which is defined to be the collection of all sets that can be computed by a Turing machine that on any input makes a total of ri, queries to Ai, for all i ∈ {1..… k}.

● Q(r1A1…..rkAk) which is defined like Q* (r1A1….. rkAk) except that queries to Ai, must be made before queries to Ai+1 for all i ∈ {1….. k – 1}.

● QC(r1A1….. rkAk) which is defined like Q{r1A1….. rkAk) except that the Turing machine must halt even if given incorrect answers to some of its queries.

We show that if A1 ….. Ak are jumps that are not too close together, then all three of these classes are identical and are not changed if we permute (r1…..rkAk). This extends a result of Beigel's [1]. Since the second class is not affected by permutations, we say that these sets commute with each other. We also show that jumps that are too close together may not commute. We also characterize the commutative sequences of sets obtained by iterating the jump operation through an ordinal notation.

A Krom formula of pure quantification theory is a formula in conjunctive normal form such that each conjunct is a disjunction of at most two atomic formulas or negations of atomic formulas. Every class of Krom formulas that is determined by the form of their quantifier prefixes and which is known to have an unsolvable decision problem for satisfiability is here shown to be a conservative reduction class. Therefore both the general satisfiability problem, and the problem of satisfiability in finite models, can be effectively reduced from arbitrary formulas to Krom formulas of these several prefix types.

At the Princeton Bicentennial in 1946 Tarski posed the question as to whether or not certain problems connected with partial propositional calculi were recursively solvable. Since that time the specific problems mentioned by Tarski as well as a number of related problems have been shown to be recursively unsolvable. Such results are due to Post and Linial [5], Yntema [9], Gladstone [2], Ihrig [3] and Singletary [7], [8].

We consider equational theories for functions denned via recursion involving equations between closed terms with natural rules based on recursive definitions of the function symbols. We show that consistency of such equational theories can be proved in the weak fragment of arithmetic S21. In particular this solves an open problem formulated by Takeuti (c.f. [5, p.5 problem 9.]).

This paper refines some results of Barwise [1] as well as answering the open question posed at the end of [1] about the Hanf number of positively. We conclude by showing that the existence of a Hanf bound for cannot be proved in the natural formally intuitionistic set theories with bounded predicates decidable of [3], [4] and [5].

All notation not explained below is taken from [1]. In the Appendix, we give the axioms of ZF0, ZF1, and T in full. We remark that an important point about the axiom of foundation was not emphasized in [1]. This axiom was intended to be the axiom scheme (∀x)((∀y ∈ x)(A(y)) → A(x)) → (∀x)(A(x)), where y does not occur in A = A(x), instead of the more customary (∀x)(∀y)(y ∈ x → (∃z ∈ x)(∀w ∈ z) (w ∉ x)). This is of no consequence in the presence of full separation, but is vital when considering ZF0 and the T below, for with the customary form of foundation, these cannot even prove the existence of Rω+ω .

In [1], a proof of the following is sketched.

We show that it is consistent with ZFC (relative to large cardinals) that every infinite Boolean algebra B has an irredundant subset A such that 2∣A∣ = 2∣B∣. This implies in particular that B has 2∣B∣ subalgebras. We also discuss some more general problems about subalgebras and free subsets of an algebra.

The result on the number of subalgebras in a Boolean algebra solves a question of Monk from [6]. The paper is intended to be accessible as far as possible to a general audience, in particular we have confined the more technical material to a “black box” at the end. The proof involves a variation on Foreman and Woodin's model in which GCH fails everywhere.

Theorem A. Let M be a left R-module such that Th(M) is small and weakly minimal, but does not have Morley rank 1. Let A = acl(∅) ⋂ M and I = {r ∈ R: rM ⊂ A}. Notice that I is an ideal.

(i) F = R/Iis a finite field.

(ii) Suppose that a, b0,…,bn, ∈ M and . Then there are s, ri ∈ R, i ≤ n, such that sa + Σi≤nribi ∈ A and s ∉ I.

It follows from Theorem A that algebraic closure in M is modular. Using this and results in [B1] and [B2], we obtain

Theorem B. Let M be as in Theorem A. Then Vaught's conjecture holds for Th(M).