We investigate the modal logic of interpretability over Peano arithmetic. Our main result is a compactness theorem that extends the arithmetical completeness theorem for the interpretability logic ILMω. This extension concerns recursively enumerable sets of formulas of interpretability logic (rather than single formulas). As corollaries we obtain a uniform arithmetical completeness theorem for the interpretability logic ILM and a partial answer to a question of Orey from 1961. After some simplifications, we also obtain Shavrukov's embedding theorem for Magari algebras (a.k.a. diagonalizable algebras).

If θ is any singular cardinal of cofinality ω 1, we produce a forcing extension in which MA holds below θ but fails at θ. The failure is due to a partial order which splits a gap of size θ in .

The collection of branches (maximal linearly ordered sets of nodes) of the tree <ωω (ordered by inclusion) forms an almost disjoint family (of sets of nodes). This family is not maximal — for example, any level of the tree is almost disjoint from all of the branches. How many sets must be added to the family of branches to make it maximal? This question leads to a series of definitions and results: a set of nodes is off-branch if it is almost disjoint from every branch in the tree; an off-branch family is an almost disjoint family of off-branch sets; and is the minimum cardinality of a maximal off-branch family.

Results concerning include: (in ZFC) , and (consistent with ZFC) is not equal to any of the standard small cardinal invariants or = 2ω. Most of these consistency results use standard forcing notions—for example, in the Cohen model.

Many interesting open questions remain, though—for example, whether .

By functional equation we mean an equation of the form

(1)A1 … Aκ = B1 … B1.

Here the A's and B's are functions of one variable from and to the natural numbers and FG is the function obtained from F and G by composition, i.e. FG(x) = F(G(x)) for all natural numbers x. We wish to investigate finite systems of functional equations. Now if all the A's and B's of (1) are equal to the identity function I (or all equal to the zero function O), then the equation (1) is satisfied trivially. Thus, in order to make the problem of solvability of systems of equations interesting, we must have some function given which will be held fixed throughout. We take the successor function S to be this given function.

We prove that any countable simple unidimensional theory T is supersimple, under the additional assumptions that T eliminates hyperimaginaries and that the Dϕ-ranks are finite and definable.

The purpose of this paper is to investigate continuity properties arising in elementary (i.e., first-order) logic in the hope of illuminating the special status of this logic. The continuity properties turn out to be closely related to conditions which characterize elementary logic uniquely, and lead to various further questions.

The lexicographic power ΔΓ of chains Δ and Γ is, roughly, the Cartesian power ΠγЄΓΔ totally ordered lexicographically from the left. Here the focus is on certain powers in which either Δ = ℝ or ℚ = ℝ, with emphasis on when two such powers are isomorphic and on when ΔΓ is 2-homogeneous. The main results are:

(1) For a countably infinite ordinal

(2) ℝℝ ≄ ℝℚ.

(3) For Δ a countable ordinal ≥ 2, Δℝ with its smallest element deleted, is 2-homogeneous.

In this paper, we study finitely axiomatizable conservative extensions of a theory U in the case where U is recursively enumerable and not finitely axiomatizable. Stanisław Krajewski posed the question whether there are minimal conservative extensions of this sort. We answer this question negatively.

Consider a finite expansion of the signature of U that contains at least one predicate symbol of arity ≥ 2. We show that, for any finite extension α of U in the expanded language that is conservative over U, there is a conservative extension β of U in the expanded language, such that $\alpha \vdash \beta$ and $\beta \not \vdash \alpha$. The result is preserved when we consider either extensions or model-conservative extensions of U instead of conservative extensions. Moreover, the result is preserved when we replace $\dashv$ as ordering on the finitely axiomatized extensions in the expanded language by a relevant kind of interpretability, to wit interpretability that identically translates the symbols of the U-language.

We show that the result fails when we consider an expansion with only unary predicate symbols for conservative extensions of U ordered by interpretability that preserves the symbols of U.

There occurs in Aristotle a thesis which is symbolised in I. M. Bocheński's La Logique de Théophraste, Chapter V, by the formula EMpMNp. We might read this as “It is possible that P (Mp) if and only if (E) it is possible that not P (MNp).” But as Bocheński explains, Aristotle is here using the word “possible” to mean, not merely “not impossible”, but “neither necessary nor impossible”. And if we take “ It is impossible that P” to mean “It is necessary that not P”, Aristotle's thesis seems evidently true. For “It is neither necessary nor impossible that P” (Mp) amounts to “It is not necessary that P, and it is not necessary that not P” (KNSpNSNp, where S is the symbol for “It is necessary that”); and “It is neither necessary nor impossible that not P” (MNp) amounts to “It is not necessary that not P, and it is not necessary that not not P” (KNSNpNSNNp); and this reduces easily to the other by the law of double negation (ENNpp) and the commutativeness of conjunction (EKpqKqp).

Despite the apparently unexceptionable character of this thesis EMpMNp, when properly understood, Bocheński informs us, in paragraph 42 of this chapter, that Łukasiewicz has shown that it “implies a contradiction”. He goes on to explain that what he means by this is that it follows from this thesis, together with the assumption that some propositions are “possible” in the Aristotelian sense, that any proposition whatever is “possible” (in that sense). And this, when one thinks what it means, is a most extraordinary contention.

From large cardinals we show the consistency of normal, fine, κ-complete λ-dense ideals on ${{\cal P}_\kappa }\left( \lambda \right)$ for successor κ. We explore the interplay between dense ideals, cardinal arithmetic, and squares, answering some open questions of Foreman.

With quantifier elimination and restriction of language to a binary relation symbol and constant symbols it is shown that countable complete theories having three isomorphism types of countable models are “essentially” the Ehrenfeucht example [4, §6].

In [8], the third author defined a reducibility $\le _w^{\rm{*}}$ that lets us compare the computing power of structures of any cardinality. In [6], the first two authors showed that the ordered field of reals ${\cal R}$ lies strictly above certain related structures. In the present paper, we show that $\left( {{\cal R},exp} \right) \equiv _w^{\rm{*}}{\cal R}$ . More generally, for the weak-looking structure ${\cal R}$ ℚ consisting of the real numbers with just the ordering and constants naming the rationals, all o-minimal expansions of ${\cal R}$ ℚ are equivalent to ${\cal R}$ . Using this, we show that for any analytic function f, $\left( {{\cal R},f} \right) \equiv _w^{\rm{*}}{\cal R}$ . (This is so even if $\left( {{\cal R},f} \right)$ is not o-minimal.)

In this paper we continue the investigations begun in [2] of equivalence classes of (denumerable) well-orderings under one-one partial recursive, order-preserving maps (recursive isotonisms). The numbering and notation are continued from [2] except that we now use lower case Greek letters for classical ordinals and upper case Roman letters for sets and we slightly modify the definition of (see §IX.3).

In section IX, after proving some lemmata which we use repeatedly in this paper, we establish the existence of Cantor Normal Forms for all co-ordinals less than a co-ordinal of the form WA (a fortiori for all co-ordinals less than a principal number for exponentiation).

We prove constructively that the weak König lemma and quantifier-free number–number choice imply that every pointwise continuous function from Cantor space into Baire space has a modulus of uniform continuity.

A semantics for the lambda-calculus due to Friedman is used to describe a large and natural class of categorical recursion-theoretic notions. It is shown that if e1 and e2 are gödel numbers for partial recursive functions in two standard ω-URS's which both act like the same closed lambda-term, then there is an isomorphism of the two ω-URS's which carries e1 to e2.

The weak non-finite cover property (wnfcp) was introduced in [1] in connection with “axiomatizability” of lovely pairs of models of a simple theory. We find a combinatorial condition on a simple theory equivalent to the wnfcp, yielding a direct proof that the non-finite cover property implies the wnfcp, and that the wnfcp is preserved under reducts. We also study the question whether the wnfcp is preserved when passing from a simple theory T to the theory Tp of lovely pairs of models of T (true in the stable case). While the question remains open, we show, among other things, that if (for a T with the wnfcp) Tp is low, then TP has the wnfcp. To study this question, we describe “double lovely pairs”, and, along the way, we develop the notion of a “lovely n-tuple” of models of a simple theory, which is an analogue of the notion of a beautiful tuple of models of stable theories [2].

The application of priority arguments to study the structure of the upper semilattice of α-r.e. α-degrees for all admissible ordinals α was first done successfully by Sacks and Simpson [5] who proved that there exist incomparable α-r.e. α-degrees. Lerman and Sacks [3] studied the existence of minimal pairs of α-r.e. α-degrees, and proved their existence for all admissible ordinals α which are not refractory. We continue the study of the α-r.e. α-degrees, and prove that no minimal pair of α-r.e. α-degrees can have as least upper bound the complete α-r.e. α-degree.

The above-mentioned theorem was first proven for α = ω by Lachlan [1]. Our proof for α = ω differs from Lachlan's in that we eliminate the use of the recursion theorem. The proofs are similar, however, and a knowledge of Lachlan's proof will be of considerable aid in reading this paper.

We assume that the reader is familiar with the basic notions or α-recursion theory, which can be found in [2] or [5].

Throughout the paper a will be an arbitrary admissible ordinal. We identify a set A ⊆ α with its characteristic function, A(x) = 1 if x ∈ A, and A(x) = 0 if x ∉ A.

If A ⊆ α and B ⊆ α, then A ⊕ B will denote the set defined by

A ⊕ B(x) = A(y) if x = λ + 2z, λ is a limit ordinal, z < ω and y = λ + z,

= B(y) if x = λ + 2z + 1, λ is a limit ordinal, z < ω, and y = λ + z.

I will formulate in this paper three set-theoretic axioms, (A1), (A2), and (A3), which appear natural and settle some well-known questions, and I will give some metamathematical evidence supporting these axioms. I build upon a distinction between pure mathematics and applied metamathematics which views the first as an art dealing with imaginary objects, where following Poincaré we can say to exist is to be free of contradiction, and the second as a science describing the phenomenon of mathematics, where science means a description of some physical reality (in this case the reality of thoughts in our brains which underlie spoken or written mathematics). Of course this distinction is not new, but it has been disregarded by many mathematicians and philosophers who wrote about the nature of mathematics, e.g. by the Platonists, and even by some empiricists who thought that mathematics is a science. Since applied metamathematics is a science, unlike pure mathematics it has to be lean, i.e., to obey Ockham's principle of economy of concepts (entia non sunt multiplicanda praeter necessitatem).

In this lean metamathematics we describe pure mathematics as a finite structure of thoughts in our brains, and we think that written or spoken mathematics is an abstract description of this structure. (I think that this is the view which Poincaré expressed informally in his discussions with the logicians and set theorists of his times, although his idea has to be modified to some extent; see Remark 4 at the end of this paper.) We claim that all mathematical objects which are imagined when we develop a (first-order) theory T can be represented by means of terms of the language of a Skolemization of the set of sentences consisting of the axioms of T and of all theorems of logic.