This paper defines and explores the properties of several effectivizations of the structure of surreal numbers. The construction of one of previously investigated systems, the metadyadics, is shown to be effectively equivalent to the construction of the surreals in . This equivalence is used to answer several open questions concerning the metadyadics. Results obtained seem to indicate that the metadyadics best capture the notion of a recursive surreal number.

In this paper we consider the three-valued logic used by Kleene [6] in the theory of partial recursive functions. This logic has three truth values: true (T), false (F), and undefined (U). One interpretation of U is as follows: Suppose we have two partially recursive predicates P(x) and Q(x) and we want to know the truth value of P(x) ∧ Q(x) for a particular x0. If x0 is in the domain of definition of both P and Q, then P(x0) ∧ Q(x0) is true if both P(x0) and Q(x0) are true, and false otherwise. But what if x0 is not in the domain of definition of P, but is in the domain of definition of Q? There are several choices, but the one chosen by Kleene is that if Q(X0) is false, then P(x0) ∧ Q(x0) is also false and if Q(X0) is true, then P(x0) ∧ Q(X0) is undefined.

What arises is the question about knowledge of whether or not x0 is in the domain of definition of P. Is there an effective procedure to determine this? If not, then we can interpret U as being unknown. If there is an effective procedure, then our decision for the truth value for P(x) ∧ Q(x) is based on the knowledge that is not in the domain of definition of P. In this case, U can be interpreted as undefined. In either case, we base our truth value of P(x) ∧ Q(x) on the truth value of Q(X0).

This paper concerns the theory of morasses. In the early 1970s Jensen defined (k, α)-morasses for uncountable regular cardinals k and ordinals α < k. In the early 1980s Velleman defined (k, 1)-simplified morasses for all regular cardinals k. He showed that there is a (k, 1)-simplified morass if and only if there is (k, 1)-morass. More recently he defined (k, 2)-simplified morasses and Jensen was able to show that if there is a (k, 2)-morass then there is a (k, 2)-simplified morass.

In this paper we prove the converse of Jensen's result, i.e., that if there is a (k, 2)-simplified morass then there is a (k, 2)-morass.

A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, ε = ({We}eϵω,⊆). We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets).

Here we show first that Q(X) implies that X has a certain “slowness” property whereby the elements must enter X slowly (under a certain precise complexity measure of speed of computation) even though X may have high information content. Second we prove that every X with this slowness property is computable in some member of any nontrivial orbit, namely for any noncomputable A ϵ ε there exists B in the orbit of A such that X ≤TB under relative Turing computability (≤T). We produce B using the -automorphism method we introduced earlier.

In a previous paper [13] we introduced a hierarchy (GnAω)n∈ℕ of subsystems of classical arithmetic in all finite types where the growth of definable functions of GnAω corresponds to the well-known Grzegorczyk hierarchy. Let AC-qf denote the schema of quantifier-free choice.

[11], [13], [8] and [7] study various analytical principles Γ in the context of the theories GnAω + AC-qf (mainly for n = 2) and use proof-theoretic tools like, e.g., monotone functional interpretation (which was introduced in [12]) to determine their impact on the growth of uniform bounds Φ such that

which are extractable from given proofs (based on these principles Γ) of sentences

Here A0(u, k, v, w) is quantifier-free and contains only u, k, v, w as free variables; t is a closed term and ≤p is defined pointwise. The term ‘uniform bound’ refers to the fact that Φ does not depend on v ≤ptuk (see [12] for the relevance of such uniform bounds in numerical analysis and for concrete applications to approximation theory).

We continue the study of simple theories begun in [3] and [5]. We first find the right analogue of definability of types. We then develop the theory of generic types and stabilizers for groups definable in simple theories. The general ideology is that the role of formulas (or definability) in stable theories is replaced by partial types (or ∞-definability) in simple theories.

For x, y ϵ ℝω define the inner product

which may not be finite or even exist. We say that x and y are orthogonal if (x, y) converges and equals 0.

Define lp to be the set of all x ϵ ℝω such that

For Hilbert space, l2, any family of pairwise orthogonal sequences must be countable. For a good introduction to Hilbert space, see Retherford [4].

Theorem 1. There exists a pairwise orthogonal family F of size continuum such that F is a subset of lp for every p > 2.

It was already known that there exists a family of continuum many pairwise orthogonal elements of ℝω. A family F ⊆ ℝω∖0 of pairwise orthogonal sequences is orthogonally complete or a maximal orthogonal family iff the only element of ℝω orthogonal to every element of F is 0, the constant 0 sequence.

It is somewhat surprising that Kunen's perfect set of orthogonal elements is maximal (a fact first asserted by Abian). MAD families, nonprincipal ultrafilters, and many other such maximal objects cannot be even Borel.

Theorem 2. There exists a perfect maximal orthogonal family of elements of ℝω.

Abian raised the question of what are the possible cardinalities of maximal orthogonal families.

Theorem 3. In the Cohen real model there is a maximal orthogonal set in ℝω of cardinality ω1, but there is no maximal orthogonal set of cardinality κ with ω1 < κ < ϲ.

By the Cohen real model we mean any model obtained by forcing with finite partial functions from γ to 2, where the ground model satisfies GCH and γω = γ.

The present note offers a short argument for the descent theorems of Zawadowski [10] (originally [9]) and Makkai [6], which were conjectured by Pitts after the descent theorem of Joyal and Tierney [3] for open geometric morphisms of (Grothendieck) toposes. The original proofs, which involve variants of Makkai's [5] duality for first order logic, are rather involved and there has been considerable interest in locating simpler proofs. Viewed categorically, the descent theorems establish a bicategorical exactness property (conservative morphisms are effective descent) for pretop (the 2-category of small pretoposes, pretopos functors, and natural transformations), for exact (exact categories, exact functors, and natural transformations), and for bpretop* (Boolean pretoposes, pretopos functors, and natural isomorphisms). Viewed logically, they fragment into a familiar Beth/Tarski-type definability theorem and a covering theorem for certain functors on PCΔ-categories (groupoids, in the Boolean case); the latter (as the former) is a arithmetical statement about the syntax of first order logic ([6, §3])).

The argument here involves special models and, independently, a continuity lemma of Makkai. The use of special models is axiomatic in that only a few properties (listed below) are needed. The continuity lemma, 9.1 of [6], is established via forcing and can be read independently of the rest of that paper. Because of its interest to both the model theorist and the category theorist, the argument is first given as straight model theory and afterwards it is briefly indicated how the descent theorems follow.

Among the results of this paper are the following:

1. Every Boolean (ultra)power is the union of an updirected elementary family of direct ultrapowers.

2. Under certain conditions, a finitely iterated Boolean ultrapower is isomorphic to a single Boolean ultrapower.

3. A ω-bounded filtral power is an elementary substructure of a filtral power.

4. Let be an elementary class closed under updirected unions (e.g., if is an amalgamation class); then is closed under finite products if and only if is closed under reduced products if and only if is a Horn class.

Let be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of is undecidable. Now denote by <π the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure (ℕ; ⊥, <π). Furthermore, the structures (ℕ; ∣, <π) (ℕ; =, ×, <π) and (ℕ; =, +, ×) are interdefinable.

Let P be the set of prime numbers. Theorem 1 of [1] shows that the linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,P〉 and therefore that the first-order theory of this structure is undecidable. Let m be any fixed natural number >2, let R be the set of natural numbers <m which are prime to m, and let r be any fixed element of R. The set

is infinite (Dirichlet). Theorem 1 of [1] can be improved as follows:

Proposition. The linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,Pm,r〉 and therefore that the first-order theory of this structure is undecidable.

Proof. We follow [1] with the following new ingredients. Let k be the number of elements of R, i.e. k = ϕ(m) where ϕ is Euler's totient function. Since k is even, the polynomial g(n) = nk + n satisfies g(0) = g(−1) = 0, so (by Lemma 1 of [1]) it follows from the linear case of (H) that there are natural numbers al (l ϵ ω) such that al+g(0), al+g(1),…, al+g(l) are consecutive primes. Since R is finite, we may assume that all the al's have the same residue t in R, so that al+g(i) ≡ t+1+i (mod m) for i ϵ R. This implies that the function t+1+i (reduced mod m) gives a permutation of R, so we can find s ϵ R such that al+g(s) ≡ r (mod m). Consider the polynomial h(n) = g(s + mn) and let bl = as+ml. Then bl + h(0), bl + h(1),…, bl + h(l) are elements of Pm,r. They are not necessarily consecutive elements of Pm,r, but they are separated by a fixed number of elements of Pm,r. This implies that {h(n) ∣ n ϵ ω} is definable in 〈ω,+,Pm,r〉(by adapting the proof of Theorem 1 of [1]), and the result follows.

The study of recursion theory on models of fragments of Peano arithmetic has hitherto been concentrated on recursively enumerable (r.e.) sets and their degrees (with a few exceptions, such as that in [2] on minimal degrees). The reason for such a concerted effort is clear: priority arguments have occupied a central position in post Friedberg-Muchnik recursion theory, and after almost forty years of intensive development in the subject, they are still the essential tools on which investigations of r.e. sets and their degrees depend. There are two possible approaches to the study within fragments of arithmetic: To give a general analysis of strategies, and identify their proof-theoretic strengths (for example in [6] on infinite injury priority methods), or to consider specific theorems in recursion theory, and, if possible, pinpoint the exact levels of induction provably equivalent to the theorems. The work reported in this paper belongs to the second approach. More precisely, we single out two infinitary injury type constructions of r.e. sets—one concerning maximal sets and the other based on the notion of the jump operator—to be the topics of study.

Section 1 is devoted to the study of countable recursively saturated models with an automorphism moving every non-algebraic point. We show that every countable theory has such a model and exhibit necessary and sufficient conditions for the existence of automorphisms moving all non-algebraic points. Furthermore we show that there are many complete theories with the property that every countable recursively saturated model has such an automorphism.

In Section 2 we apply our main theorem from Section 1 to models of Quine's set theory New Foundations (NF) to answer an old consistency question. If NF is consistent, then it has a model in which the standard natural numbers are a definable subclass ℕ of the model's set of internal natural numbers Nn. In addition, in this model the class of wellfounded sets is exactly .

In [4] it is shown that only using exponentiation can one prove the existence of non trivial solutions of Pell equations in IΔ0. However, in this paper we will prove that any Pell equation has a non trivial solution modulo m for every m in IΔ0.

Small forcing always ruins the indestructibility of an indestructible supercompact cardinal. In fact, after small forcing, any cardinal κ becomes superdestructible—any further <κ-closed forcing which adds a subset to κ will destroy the measurability, even the weak compactness, of κ. Nevertheless, after small forcing indestructible cardinals remain resurrectible, but never strongly resurrectible.

We prove an Ax-Kochen-Ershov like transfer principle for groups acting on groups. The simplest case is the following: let B be a soluble group acting on an abelian group G so that G is a torsion-free divisible module over the group ring ℤ[B], then the theory of B determines the one of the two-sorted structure 〈G,B,*〉, where * is the action of B on C. More generally, we show a similar principle for structures 〈G,B,*〉, where G is a torsion-free divisible module over the quotient of ℤ[B] by the annulator of G.

Two applications come immediately from this result:

First, for not necessarily commutative domains, where we consider the action of a subgroup of the invertible elements on the additive group. We obtain then the decidability of a weakened structure of ring, with partial multiplication.

The second application is to pure groups. The semi-direct product of G by B is bi-interpretable with our structure 〈G,B,*〉. Thus, we obtain stable decidable groups that are not linear over a field.

We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.

We show that the elimination rule for the multiplicative (or intensional) conjunction Λ is admissible in many important multiplicative substructural logics. These include LLm (the multiplicative fragment of Linear Logic) and RMIm (the system obtained from LLm by adding the contraction axiom and its converse, the mingle axiom.) An exception is Rm (the intensional fragment of the relevance logic R, which is LLm together with the contraction axiom). Let SLLm and SRm be, respectively, the systems which are obtained from LLm and Rm by adding this rule as a new rule of inference. The set of theorems of SRm is a proper extension of that of Rm, but a proper subset of the set of theorems of RMIm. Hence it still has the variable-sharing property. SRm has also the interesting property that classical logic has a strong translation into it. We next introduce general algebraic structures, called strong multiplicative structures, and prove strong soundness and completeness of SLLm relative to them. We show that in the framework of these structures, the addition of the weakening axiom to SLLm corresponds to the condition that there will be exactly one designated element, while the addition of the contraction axiom corresponds to the condition that there will be exactly one nondesignated element (in the first case we get the system BCKm, in the second - the system SRm). Various other systems in which multiplicative conjunction functions as a true conjunction are studied, together with their algebraic counterparts.

It has been known for more than thirty years that the degree of a non-standard model of true arithmetic is a subuniform upper bound for the arithmetic sets (suub). Here a notion of generic enumeration is presented with the property that the degree of such an enumeration is an suub but not the degree of a non-standard model of true arithmetic. This answers a question posed in the literature.

The basic notions of the theory of term rewriting are defined for terms that may involve function letters of infinite arity. A sufficient condition for completeness is derived, and its use demonstrated by the example of abstract clones over infinitary signatures.