This paper is a continuation of [27], where we provide the background and the basic tools for studying the structural properties of classes of models over languages without equality. In the context of such languages, it is natural to make distinction between two kinds of classes, the so-called abstruct classes, which correspond to those closed under isomorphic copies in the presence of equality, and the reduced classes, i.e., those obtained by factoring structures by their largest congruences. The generic problem described in [27] is to investigate under what conditions this reduction process does not alter the metatheory of a class.

Here we focus our attention on a concrete aspect of this generic problem that we import from universal algebra, namely the existence and description of free models. As in [27], we can find here again the basic notion of protoalgebraicity, which was originally introduced in [7] as the weakest condition to guarantee that the reduction process behaves reasonably well from an algebraic point of view. Our concern, however, takes us to handle a further notion, that of semialgebraicity, which corresponds to the notion of equivalential logic of [18]; semialgebraicity turns out to be the property which ensures that freeness is fully preserved by the reduction process.

The Jordan decomposition theorem states that every function $f \colon \, [0,1] \to \mathbb {R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $\mathsf {RCA}_{0}$ , a stronger version of Jordan’s result where all functions are continuous is equivalent to $\mathsf {ACA}_0$ , while the version stated is equivalent to ${\textsf {WKL}}_{0}$ . The result that every function on $[0,1]$ of bounded variation is almost everywhere differentiable is equivalent to ${\textsf {WWKL}}_{0}$ . To state this equivalence in a meaningful way, we develop a theory of Martin–Löf randomness over $\mathsf {RCA}_0$ .

We study local strengthenings of the simplicity condition. In particular, we define and study a local Lascar rank, as well as short, low. supershort and superlow theories. An example of a low non supershort theory is given.

Let K be a function field of one variable over a constant field C of finite transcendence degree over ℂ. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K. Then there exists a set W′ of K-primes such that Hilbert's Tenth Problem is not decidable over OK,W′ = {x ϵ K∣ordþx ≥ 0, ∀þ ∉ W′}, and the set (W′ ∖ W)∪{W ∖ W′) is finite.

Let K be a function field of one variable over a constant field C finitely generated over ℚ. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K and the degree of all the primes in W is bounded by b ϵ ℕ. Then there exists a set W′ of K-primes such that ℤ has a Diophantine definition over OK,W′, and the set (W′ ∖ W)∪(W ∖ W′) is finite.

We introduce the notion of finitary computable reducibility on equivalence relations on the domain ω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be ${\rm{\Pi }}_{n + 2}^0$ -complete under computable reducibility, we show that, for every n, there does exist a natural equivalence relation which is ${\rm{\Pi }}_{n + 2}^0$ -complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy.

In [1], various formal proof systems for infinitary formulas were defined. The formal proof system is the result of extending the basic predicate calculus by adding a collection Σ of axiom schemes and a collection Ω of rules of inference. Let Taut be the collection of all infinitary prepositional tautologies, considered as axiom schemes. Let ΩI consist of all the quantificational rules of independent choices. We will show, in §2 (see Theorem 2.1), that (Taut; 0) is not complete for L∞ω (i.e., infinitary finite-quantifier) sentences; that is, we will exhibit an L∞ω sentence ϕ such that ¬ϕ is true in all models, but ¬ϕ is not provable in (Taut; 0). (The unprovability is shown by a weak forcing version of Boolean general models.) This answers a question of Karp in [1,12.1(i)]. In §4, we will show that our ϕ is “ complete for L∞ω ) sentences.”

Elimination of imaginaries for 1-variable definable equivalence relations is proved for a theory of algebraically closed valued fields with new sorts for the disc spaces. The proof is constructive, and is based upon a new framework for proving elimination of imaginaries, in terms of prototypes which form a canonical family of formulas for defining each set that is definable with parameters. The proof also depends upon the formal development of the tree-like structure of valued fields, in terms of valued trees, and a decomposition of valued trees which is used in the coding of certain sets of discs.

The logical flow graphs of sequent calculus proofs might contain oriented cycles. For the predicate calculus the elimination of cycles might be non-elementary and this was shown in [Car96]. For the propositional calculus, we prove that if a proof of k lines contains n cycles then there exists an acyclic proof with (kn+1) lines. In particular, there is a polynomial time algorithm which eliminates cycles from a proof. These results are motivated by the search for general methods on proving lower bounds on proof size and by the design of more efficient heuristic algorithms for proof search.

We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$ , $\Pi _{\alpha }$ , or $\mathrm {d-}\Sigma _{\alpha }$ . We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit ordinal. This answers a question left open by A. Miller.

We also construct examples of computable structures of high Scott rank with Scott complexities $\Sigma _{\omega _1^{CK}+1}$ and $\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$ . There are three other possible Scott complexities for a computable structure of high Scott rank: $\Pi _{\omega _1^{CK}}$ , $\Pi _{\omega _1^{CK}+1}$ , $\Sigma _{\omega _1^{CK}+1}$ . Examples of these were already known. Our examples are computable structures of Scott rank $\omega _1^{CK}+1$ which, after naming finitely many constants, have Scott rank $\omega _1^{CK}$ . The existence of such structures was an open question.

Let K be an algebraically closed field and let L be its canonical language; that is, L consists of all relations on K which are definable from addition, multiplication, and parameters from K. Two sublanguages L 1 and L 2 of L are definably equivalent if each relation in L 1 can be defined by an L 2-formula with parameters in K, and vice versa. The equivalence classes of sublanguages of L form a quotient lattice of the power set of L about which very little is known. We will not distinguish between a sublanguage and its equivalence class.

Let L m denote the language of multiplication alone, and let L a denote the language of addition alone. Let f ∈ K [X, Y] and consider the algebraic function defined by f (x, y) = 0 for x, y ∈ K. Let L f denote the language consisting of the relation defined by f. The possibilities for L m ∨ L f are examined in §2, and the possibilities for L a ∨ L f are examined in §3. In fact the only comprehensive results known are under the additional hypothesis that f actually defines a rational function (i.e., when f is linear in one of the variables), and in positive characteristic, only expansions of addition by polynomials (i.e., when f is linear and monic in one of the variables) are understood. It is hoped that these hypotheses will turn out to be unnecessary, so that reasonable generalizations of the theorems described below to algebraic functions will be true. The conjecture is that L covers L m and that the only languages between L a and L are expansions of L a by scalar multiplications.

We note here, in answer to a question of Poizat, that the Morley and Lascar ranks need not coincide in differentially closed fields. We will approach this through the (perhaps) more fundamental issue of the variation of Morley rank in families. We will be interested here only in sets of finite Morley rank. Section 1 consists of some general lemmas relating the above issues. Section 2 points out a family of sets of finite Morley rank, whose Morley rank exhibits discontinuous upward jumps. To make the base of the family itself have finite Morley rank, we use a theorem of Buium.

We prove that Rado's Conjecture implies that the nonstationary ideal on ω1 is presaturated.

Let L be a finite relational language. The age of a structure over L is the set of isomorphism types of finite substructures of . We classify those ages for which there are less than 2ω countably infinite pairwise nonisomorphic L-structures of age .

A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a $\mathbf {0}'$-computable low$_3$ compact Polish space which is not homeomorphic to a computable one, and that, for any natural number $n\geq 2$, there exists a Polish space $X_n$ such that exactly the high$_{n}$-degrees are required to present the homeomorphism type of $X_n$. Along the way we investigate the computable aspects of Čech homology groups. We also show that no compact Polish space has a least presentation with respect to Turing reducibility.

A series of investigations started by H. Friedman ([5], [6]) and pursued by him, by S. Simpson, and by others (see [7], [16] and the references there) had the objective of determining what are precisely the set existence axioms needed for proving theorems of “ordinary” mathematics. The study centered around -CA0 (for “-Comprehension Axiom”), a fragment of second order arithmetic in which the main body of “ordinary” mathematics can be comfortably developed (of course, after a suitable encoding of the various concepts into numbers and sets of numbers). The main question is always this: given a theorem τ provable in -CA0, do we need all of -CA0, or, maybe, is τ provable in a weaker subsystem? A surprisingly simple pattern emerged: there seem to be just five important systems, denoted (in order of increasing strength) RCA0, WKL0, ACA0, ATR0 and -CA0, such that in most cases, whenever an ordinary mathematical theorem τ is provable in -CA0, it is either provable in RCA0 or it is equivalent to one, call it S, of the other four systems, the proof of the equivalence being done in one of the systems which is weaker than S (most typically, RCA0 or ACA0). This very interesting phenomenon—or “theme” as it was called by Friedman—has been verified for many instances in the realm of analysis and algebra (cf. the references above and the forthcoming book [17]). It is the purpose of this paper to do the same for a particular branch of model theory, namely stability theory.

This addendum to [2] shows that the set of tautological quantum logical propositional formulas for a finite dimensional vector space ℂn is different for every n, affirmatively answering a question posed therein.

Let G be a stable abelian group with regular modular generic. We show that either

1. there is a definable nongeneric K ≤ G such that G/K has definable connected component and so strongly regular generics, or

2. distinct elements of the division ring yielding the dependence relation are represented by subgroups of G × G realizing distinct strong types (when regarded as elements of Geq).

In the latter case one can choose almost 0-definable subgroups representing the elements of the division ring. We find a bound ((G: G0)) for the size of the division ring in case G has no definable subgroup K so that G/K is infinite with definable connected component. We show in case (2) that the group G/H, where H consists of all nongeneric points of G, inherits a weakly minimal group structure from G naturally, and Th(G/H) is independent of the particular model G as long as G/H is infinite.

Hofstadter has introduced the notion of an explicit Henkin sentence. Roughly speaking, an explicit Henkin sentence not only asserts its own provability, as ordinary Henkin sentences do, but explicitly provides a detailed description of a proof. We provide, in this paper, a precise formalization of Hofstadter's notion and then show that true explicit Henkin sentences exist.