The lattice of r.e. equivalence relations has not been carefully examined even though r.e. equivalence relations have proved useful in logic. A maximal r.e. equivalence relation has the expected lattice theoretic definition. It is proved that, in every pair of r.e. nonrecursive Turing degrees, there exist maximal r.e. equivalence relations which intersect trivially. This is, so far, unique among r.e. submodel lattices.

Kruskal proved that finite trees are well-quasi-ordered by hom(e)omorphic embeddability. Friedman observed that this statement is not provable in predicative analysis. Friedman also proposed (see in [Simpson]) some stronger variants of the Kruskal theorem dealing with finite labeled trees under hom(e)omorphic embeddability with a certain gap-condition, where labels are arbitrary finite ordinals from a fixed initial segment of ω. The corresponding limit statement, expressing that for all initial segments of ω these labeled trees are well-quasi-ordered, is provable in -CA, but not in the analogous theory -CA0 with induction restricted to sets. Schütte and Simpson proved that the one-dimensional case of Friedman's limit statement dealing with finite labeled intervals is not provable in Peano arithmetic. However, Friedman's gap-condition fails for finite trees labeled with transfinite ordinals. In [Gordeev 1] I proposed another gap-condition and proved the resulting one-dimensional modified statements for all (countable) transfinite ordinal-labels. The corresponding universal modified one-dimensional statement UM1 is provable in (in fact, is equivalent to) the familiar theory ATR0 whose proof-theoretic ordinal is Γ0. In [Gordeev 1] I also announced that, in the general case of arbitrarily-branching finite trees labeled with transfinite ordinals, in the proof-theoretic sense the hierarchy of the limit modified statements M<λ (which are denoted by LMλ in the present note) is as strong as the hierarchy of the familiar theories of iterated inductive definitions (more precisely, see [Gordeev 1, Concluding Remark 3]). In this note I present a “positive” proof of the full universal modified statement UM, together with a short proof of the crucial “reverse” results which is based on Okada's interpretation of the well-established ordinal notations of Buchholz corresponding to the theories of iterated inductive definitions. Formally the results are summarized in §5 below.

A topological classification scheme consists of two ingredients: (1) an abstract class of topological spaces; and (2) a “taxonomy”, i.e. a list of first order sentences, together with a way of assigning an abstract class of spaces to each sentence of the list so that logically equivalent sentences are assigned the same class. is then endowed with an equivalence relation, two spaces belonging to the same equivalence class if and only if they lie in the same classes prescribed by the taxonomy. A space X in is characterized within the classification scheme if whenever Y ∊ and Y is equivalent to X, then Y is homeomorphic to X. As prime example, the closed set taxonomy assigns to each sentence in the first order language of bounded lattices the class of topological spaces whose lattices of closed sets satisfy that sentence. It turns out that every compact two-complex is characterized via this taxonomy in the class of metrizable spaces, but that no infinite discrete space is so characterized. We investigate various natural classification schemes, compare them, and look into the question of which spaces can and cannot be characterized within them.

Mathematics is a natural science whose great generality makes many philosophers think of it as a supernatural science, consisting of truths derived independently of experience about objects not given in experience. Some mathematicians, like Simpson [16], try to defend mathematics from the resulting objection that it is merely a mental game by first conceding that most of it is meaningless and then trying to save what is left by some technical tour de force. Some physicists, like Wigner [20], admit that mathematics is applicable to the world, but declare themselves unable to understand what makes its applications possible. Both Simpson's worries and Wigner's puzzlement can be relieved if we assimilate mathematics more closely to the other natural sciences.

PA is Peano arithmetic. The formula InterpPA(α, β) is a formalization of the assertion that the theory PA + α interprets the theory PA + β (the variables α and β are intended to range over codes of sentences of PA). We extend Solovay's modal analysis of the formalized provability predicate of PA, PrPA(x), to the case of the formalized interpretability relation InterpPA(x, y). The relevant modal logic, in addition to the usual provability operator ‘□’, has a binary operator ‘⊳’ to be interpreted as the formalized interpretability relation. We give an axiomatization and a decision procedure for the class of those modal formulas that express valid interpretability principles (for every assignment of the atomic modal formulas to sentences of PA). Our results continue to hold if we replace the base theory PA with Zermelo-Fraenkel set theory, but not with Gödel-Bernays set theory. This sensitivity to the base theory shows that the language is quite expressive. Our proof uses in an essential way earlier work done by A. Visser, D. de Jongh, and F. Veltman on this problem.

The paper proves a predicate version of Solovay's well-known theorem on provability interpretations of modal logic:

If a closed modal predicate-logical formula R is not valid in some finite Kripke model, then there exists an arithmetical interpretation f such that PA ⊬ fR.

This result implies the arithmetical completeness of arithmetically correct modal predicate logics with the finite model property (including the one-variable fragments of QGL and QS). The proof was obtained by adding “the predicate part” as a specific addition to the standard Solovay construction.

A remarkable result of Henson and Ross [HR] states that if a function whose graph is Souslin in the product of two hyperfinite sets in an ℵ1 saturated nonstandard universe possesses a certain nice property (capacity) then there exists an internal subfunction of the given one possessing the same property. In particular, they prove that every 1-1 Souslin function preserves any internal counting measure, and show that every two internal sets A and B with ∣A∣/∣B∣ ≈ 1 are Borel bijective. As a supplement to the last-mentioned result of Henson and Ross, Keisler, Kunen, Miller and Leth showed [KKML] that two internal sets A and B are bijective by a countably determined bijection if and only if ∣A∣/∣B∣ is finite and not infinitesimal.

In this paper we first show that injective Borel functions map Borel sets into Borel sets, a fact well known in classical descriptive set theory. Then, we extend the result of Henson and Ross concerning the Borel bijectivity of internal sets whose quotient of cardinalities is infinitely closed to 1. We prove that two Borel sets, to which we may assign a counting measure not equal to 0 or ∞, are Borel bijective if and only if they have the same counting measure ≠0, ∞. This, together with the similar characterization for Souslin and measurable countably determined sets, extends the above-mentioned results from [HR] and [KKML].

The program of reverse mathematics has usually been to find which parts of set theory, often used as a base for other mathematics, are actually necessary for some particular mathematical theory. In recent years, Slaman, Groszek, et al, have given the approach a new twist. The priority arguments of recursion theory do not naturally or necessarily lead to a foundation involving any set theory; rather, Peano Arithmetic (PA) in the language of arithmetic suffices. From this point, the appropriate subsystems to consider are fragments of PA with limited induction. A theorem in this area would then have the form that certain induction axioms are independent of, necessary for, or even equivalent to a theorem about the Turing degrees. (See, for examples, [C], [GS], [M], [MS], and [SW].)

As go the integers so go the ordinals. One motivation of α-recursion theory (recursion on admissible ordinals) is to generalize classical recursion theory. Since induction in arithmetic is meant to capture the well-foundedness of ω, the corresponding axiom in set theory is foundation. So reverse mathematics, even in the context of a set theory (admissibility), can be changed by the influence of reverse recursion theory. We ask not which set existence axioms, but which foundation axioms, are necessary for the theorems of α-recursion theory.

When working in the theory KP – Foundation Schema (hereinafter called KP−), one should really not call it α-recursion theory, which refers implicitly to the full set of axioms KP. Just as the name β-recursion theory refers to what would be α-recursion theory only it includes also inadmissible ordinals, we call the subject of study here γ-recursion theory. This answers a question by Sacks and S. Friedman, “What is γ-recursion theory?”

In the last years several research projects have been motivated by the problem of constructing the usual geometrical spaces by admitting “regions” and “inclusion” between regions as primitives and by defining the points as suitable sequences or classes of regions (for references see [2]).

In this paper we propose and examine a system of axioms for the pointless space theory in which “regions”, “inclusion”, “distance” and “diameter” are assumed as primitives and the concept of point is derived. Such a system extends a system proposed by K. Weihrauch and U. Schreiber in [5].

In the sequel R and N denote the set of real numbers and the set of natural numbers, and E is a Euclidean metric space. Moreover, if X is a subset of R, then ⋁X is the least upper bound and ⋀X the greatest lower bound of X.

For each ordinal α > 0, L(α) is the intermediate predicate logic characterized by the class of all Kripke frames with the poset α and with constant domain. This paper will be devoted to a study of logics of the form L(α). It will be shown that for each uncountable ordinal of the form α + η with a finite or a countable η(> 0), there exists a countable ordinal of the form β + η such that L(α + η) = L(β + η). On the other hand, such a reduction of ordinals to countable ones is impossible for a logic L(α) if α is an uncountable regular ordinal. Moreover, it will be proved that the mapping L is injective if it is restricted to ordinals less than ωω, i.e. α ≠ β implies L(α) ≠ L(β) for each ordinal α, β ≤ ωω.

We prove that no logic (i.e. consequence operation) determined by any class of orthomodular lattices admits the deduction theorem (Theorem 2.7). We extend those results to some broader class of logics determined by ortholattices (Corollary 2.6).

This paper discusses six formalization techniques, of varying strengths, for extending a formal system based on traditional mathematical logic. The purpose of these formalization techniques is to simulate the introduction of new syntactic constructs, along with associated semantics for them. We show that certain techniques (among the six) subsume others. To illustrate sharpness, we also consider a selection of constructs and show which techniques can and cannot be used to introduce them. The six studied techniques were selected on the basis of actual practice in logic and computing. They do not form an exhaustive list.

In [10] we introduced a new first order language for valued fields. This language has three sorts of variables, namely variables for elements of the valued field, variables for elements of the residue field and variables for elements of the value group. contains symbols for the standard field, residue field, and value group operations and a function symbol for the valuation. Essential in our language is a function symbol for an angular component map modulo P, which is a map from the field to the residue field (see Definition 1.2).

For this language we proved a quantifier elimination theorem for Henselian valued fields of equicharacteristic zero which possess such an angular component map modulo P [10, Theorem 4.1]. In the first section of this paper we give some partial results on the existence of an angular component map modulo P on an arbitrary valued field.

By applying the above quantifier elimination theorem to ultraproducts ΠQp/D, we obtained a quantifier elimination, in the language , for the p-adic field Qp; and this elimination is uniform for almost all primes p [10, Corollary 4.3]. In §2 we prove that our language is essentially stronger than the natural language for p-adic fields in the sense that the angular component map modulo P cannot be defined, uniformly for almost all p, in terms of the natural language for p-adic fields.

Let T be a complete countable first order theory and λ an uncountable cardinal. Theorem 1. If T is not superstable, T has 2λ resplendent models of power λ. Theorem 2. If T is strictly superstable, then T has at least min(2λ, ℶ2) resplendent models of power λ. Theorem 3. If T is not superstable or is small and strictly superstable, then every resplendent homogeneous model of T is saturated. Theorem 4 (with Knight). For each μ ∈ ω ∪ {ω, 2ω} there is a recursive theory in a finite language which has μ resplendent models of power κ for every infinite κ.

Let L be a countable language which contains only constant and relation symbols but no function symbols. All theories considered here will be L-theories. A theory is coinductive if it can be axiomatized by a set of ∃∀ sentences, and a structure is coinductive if its theory is.

The object of this paper is to show that coinductive ℵ0-categorical structures are especially simple. First, they are ω-stable with Morley rank ≤ 1; and second, they have simple algebraic closures, by which is meant that the algebraic closure of the union of two sets is the union of their algebraic closures. While these two properties do not characterize coinductive ℵ0-categorical structures, they do characterize those structures which are cellular.

We will say that a countable structure is cellular if there is a finite subset A0 ⊆ A and there are equivalence relations E and F on A∖A0 such that the following hold:

(1) There are only finitely many E-classes.

(2) If C is an E-class and D an F-class, then ∣C ∩ D ∣ = 1.

(3) If a0, a1, …, ak − 1, b0, b1, …, bk − 1 Є A, then 〈a0, a1, …,ak − 1〉 and 〈b0,b1, …, bk − 1〉, satisfy the same quantifier-free formulas provided that:

(a) if i < k and either ai Є A0 or bi Є A0, then ai = bi;

(b) if i < k, then ai; and bi are E-equivalent; and

(c) if i, j < k, then ai; is F-equivalent to aj if bj is F-equivalent to bj.

The main result of this paper is the following theorem.

Theorem 1. Ifis coinductive and ℵ0-categorical, thenis cellular.

The results of this paper were obtained independently of similar results obtained by Lachlan which can be found in [4] and [5]. The proofs here are quite different.

We introduce the notion of “semi-r.e.” for subsets of ω, a generalization of “semirecursive” and of “r.e.”, and the notion of “weakly semirecursive”, a generalization of “semi-r.e.”. We show that A is weakly semirecursive iff, for any n numbers x1, …,xn, knowing how many of these numbers belong to A is equivalent to knowing which of these numbers belong to A. It is shown that there exist weakly semirecursive sets that are neither semi-r.e. nor co-semi-r.e. On the other hand, we exhibit nonzero Turing degrees in which every weakly semirecursive set is semirecursive. We characterize the notion “A is weakly semirecursive and recursive in K” in terms of recursive approximations to A. We also show that if a finite Boolean combination of r.e. sets is semirecursive then it must be r.e. or co-r.e. Several open questions are raised.

We present a theory VF of partial truth over Peano arithmetic and we prove that VF and ID1, have the same arithmetical content. The semantics of VF is inspired by van Fraassen's notion of supervaluation.

This paper is a contribution to the following natural problem in complexity theory:

(*) Is there a complexity theory for isomorphism types of recursive countable relational structures? I.e. given a recursive relational structure ℛ over the set N of nonnegative integers, is there a nontrivial lower bound for the time-space complexity of recursive structures isomorphic (resp. recursively isomorphic) to ℛ?

For unary recursive relations R, the answer is trivially negative: either R is finite or coinfinite or 〈N, R〉 is recursively isomorphic to 〈N, {x ϵ N: x is even}〉.

The general problem for relations with arity 2 (or greater) is open.

Related to this problem, a classical result (going back to S. C. Kleene [4], 1955) states that every recursive ordinal is in fact primitive recursive.

In [3] Patrick Dehornoy, using methods relevant to computer science, improves this result, showing that every recursive ordinal can be represented by a recursive total ordering over N which has linear deterministic time complexity relative to the binary representation of integers. As he notices, his proof applies to every recursive total order type α such that the isomorphism type of α is not changed if points are replaced by arbitrary finite nonempty subsets of consecutive points.

In this paper we extend Dehornoy's result to all recursive total orderings over N and get minimal complexity for both time and space simultaneously.

Several definitions of “compact” for topological spaces have appeared in the literature (see [5]). We will consider the following:

Definition. A topological space X is

1. Compact(1) if every open cover of X has a finite subcover.

2. Compact(2) if every infinite subset E of X has a complete accumulation point (i.e., a point x0 ∈ X such that for every neighborhood U of x0, |E ∩ U| = |E|).

3. Compact(3) if there is a subbase S for the topology on X such that every cover of X by members of S has a finite subcover.

4. Compact(4) if each nest of closed, nonempty sets has a nonempty intersection.

5. Compact(5) if every family of closed sets in X which has the finite intersection property (every finite subfamily has a nonempty intersection) has a nonempty intersection.

6. Compact(6) if each net in X has a cluster point.

7. Compact(7) if each net in X has a convergent subnet.

This work was motivated primarily by consideration of various proofs that the Tychonoff theorem, T (“the product of compact topological spaces is compact”) is equivalent to the Axiom of Choice, AC. Tychonoff's original proof that AC implies T used Definition 2 [13]. Other proofs have used Definitions 3 and 5; see [5]. The proof by Kelley that T implies AC uses Definition 5 [6].

We point out that a group first order definable in a differentially closed field K of characteristic 0 can be definably equipped with the structure of a differentially algebraic group over K. This is a translation into the framework of differentially closed fields of what is known for groups definable in algebraically closed fields (Weil's theorem).

I restrict myself here to showing (Theorem 20) how one can find a large “differentially algebraic group chunk” inside a group defined in a differentially closed field. The rest of the translation (Theorem 21) follows routinely, as in [B].

What is, perhaps, of interest is that the proof proceeds at a completely general (soft) model theoretic level, once Facts 1–4 below are known.

Fact 1. The theory of differentially closed fields of characteristic 0 is complete and has quantifier elimination in the language of differential fields (+, ·,0,1, −1,d).

Fact 2. Affine n-space over a differentially closed field is a Noetherian space when equipped with the differential Zariski topology.

Fact 3. If K is a differentially closed field, k ⊆ K a differential field, and a and are in k, then a is in the definable closure of k ◡ iff a ∈ ‹› (where k ‹› denotes the differential field generated by k and).

Fact 4. The theory of differentially closed fields of characteristic zero is totally transcendental (in particular, stable).