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.

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.

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.

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.

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.

For any countable transitive complete theory T with infinite models and the finite model property, we construct a minimal structure M such that the theory of M is small if and only if T is small, and is λ-stable if and only if T is λ-stable. This gives a series of new examples of minimal structures.

We work throughout in a finite relational language L. This paper is built on [2] and [3]. We repeat some of the basic notions and results from these papers for the convenience of the reader but familiarity with the setup in the first few sections of [3] is needed to read this paper. Spencer and Shelah [6] constructed for each irrational α between 0 and 1 the theory Tα as the almost sure theory of random graphs with edge probability n−α. In [2] we proved that this was the same theory as the theory Tα built by constructing a generic model in [3]. In this paper we explore some of the more subtle model theoretic properties of this theory. We show that Tα has the dimensional order property and does not have the finite cover property.

We work in the framework of [3] so probability theory is not needed in this paper. This choice allows us to consider a wider class of theories than just the Tα. The basic facts cited from [3] were due to Hrushovski [4]; a full bibliography is in [3]. For general background in stability theory see [1] or [5].

We work at three levels of generality. The first is given by an axiomatic framework in Context 1.10. Section 2 is carried out in this generality. The main family of examples for this context is described in Example 1.3. Sections 3 and 4 depend on a function δ assigning a real number to each finite L-structure as in these examples. Some of the constructions in Section 3 (labeled at the time) use heavily the restriction of the class of examples to graphs. The first author acknowledges useful discussions on this paper with Sergei Starchenko.

Two rings are elementarily equivalent if and only if they satisfy the same sentences in the language of rings. To some extent this is reflected in the representation theories of the two rings (one may see both positive and negative results along these lines in [5]). Here we concentrate on the case of a ring S and an elementary subring R of S.

We show that if R is an elementary subring of S then the lattice of pp formulas for R-modules embeds in that for S-modules. These lattices, moreover, have the same finite sub-posets. From this we derive some corollaries. Then we consider to what extent the compositions of induction and restriction between R- and S-modules preserve elementary equivalence.

We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in “propositional” fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The “pure,” propositional fragment FLR0 turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of models.

We investigate amalgamation properties of relational type algebras. Besides purely algebraic interest, amalgamation in a class of algebras is important because it leads to interpolation results for the logic corresponding to that class (cf. [15]). The multi-modal logic corresponding to relational type algebras became known under the name of “arrow logic” (cf. [18, 17]), and has been studied rather extensively lately (cf. [10]). Our research was inspired by the following result of Andréka et al. [1].

Let K be a class of relational type algebras such that

(i) composition is associative,

(ii) K is a class of boolean algebras with operators, and

(iii) K contains the representable relation algebras RRA.

Then the equational theory of K is undecidable.

On the other hand, there are several classes of relational type algebras (e.g., NA, WA denned below) whose equational (even universal) theories are decidable (cf. [13]). Composition is not associative in these classes. Theorem 5 indicates that also with respect to amalgamation (a very weak form of) associativity forms a borderline. We first recall the relevant definitions.

Generalized n-gons are certain geometric structures (incidence geometries) that generalize the concept of projective planes (the nontrivial generalized 3-gons are exactly the projective planes).

In a simplified world, every generalized n-gon of finite Morley rank would be an algebraic one, i.e., one of the three families described in [9] for example. To our horror, John Baldwin [2], using methods discovered by Hrushovski [7], constructed ℵ1-categorical projective planes which are not algebraic. The projective planes that Baldwin constructed fail to be algebraic in a dramatic way.

Indeed, every algebraic projective plane over an algebraically closed field is Desarguesian [12]. In particular, an algebraically closed field (isomorphic to the base field) can be interpreted in every one of them. However, in the projective planes that Baldwin constructed, one cannot even interpret an infinite group.

In this article we show that the same phenomenon occurs for the generalized n-gons if n ≥ 3 is an odd integer. For each such n we construct many nonisomorphic generalized n-gons of finite Morley rank that do not interpret an infinite group. As one may expect, our method is inspired by Hrushovski and Baldwin, and we follow Baldwin's line of approach. Quite often our proofs are a verification of the fact that the proofs of Baldwin [2] for n = 3 carry over to an arbitrary positive odd integer n (which is sometimes far from being obvious). As in [2], we begin by defining a certain collection of finite graphs K* and a binary relation ≤ on these graphs. We show that (K*, ≤) satisfies the amalgamation property.

The context for this paper is Feferman's theory of explicit mathematics, a formal framework serving many purposes. It is suitable for representing Bishop-style constructive mathematics as well as generalized recursion, including direct expression of structural concepts which admit self-application. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, the new axiom not merely postulates the existence of a least solution, but, by adjoining a new functional constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation.

The upshot of the paper is that the latter extension of explicit mathematics (when based on classical logic) embodies considerable proof-theoretic strength. It is shown that it has at least the strength of the subsystem of second order arithmetic based on comprehension.

We examine two-cardinal problems for the class of O-minimal theories. We prove that an O-minimal theory which admits some (κ, λ) must admit every (κ′, λ′). We also prove that every “reasonable” variant of Chang's Conjecture is true for O-minimal structures. Finally, we generalize these results from the two-cardinal case to the δ-cardinal case for arbitrary ordinals δ.

After small forcing, any <κ-closed forcing will destroy the supercompactness and even the strong compactness of κ.

A version of Herbrand's theorem tells us that a universal sentence of a first-order language with at least one constant is satisfiable if and only if the conjunction of all its ground instances is. In general the set of such instances is infinite, and arbitrarily large finite subsets may have to be inspected in order to detect inconsistency. Essentially, the reason that every member of such an infinite set may potentially matter, can be traced back to sentences like

(1)

Loosely put, such sentences effectively sabotage any attempt to build a model from below in a finite number of steps, since new members of the Herbrand universe are constantly brought to attention. Since they cause an indefinite expansion of the relevant part of the Herbrand universe, such sentences could quite appropriately be called expanding.

When such sentences are banned, stronger versions of Herbrand's theorem can be stated. Define a clause (disjunction of literals) to be non-expanding if every non-ground term occurring in a positive literal also occurs (possibly as an embedded subterm) in a negative literal of the same clause. Written as a disjunction of literals, the matrix of (1) clearly fails this criterion. Moreover, say that a sentence is non-expanding if it is a universal sentence with a quantifier-free matrix that is a conjunction of non-expanding clauses. Such sentences do in a sense never reach out beyond themselves, and the relevant part of the Herbrand universe is therefore drastically reduced.

A mapping u: X → Y between metric spaces is sequentially continuous if for each sequence (xn) converging to x ∈ X, (u(xn)) converges to u(x). It is well known in classical mathematics that a sequentially continuous mapping between metric spaces is continuous; but, as all proofs of this result involve the law of excluded middle, there appears to be a constructive distinction between sequential continuity and continuity. Although this distinction is worth exploring in its own right, there is another reason why sequential continuity is interesting to the constructive mathematician: Ishihara [8] has a version of Banach's inverse mapping theorem in functional analysis that involves the sequential continuity, rather than continuity, of the linear mappings; if this result could be upgraded by deleting the word “sequential”, then we could prove constructively the standard versions of the inverse mapping theorem and the closed graph theorem.

Troelstra [9] showed that in Brouwer's intuitionistic mathematics (INT) a sequentially continuous mapping on a separable metric space is continuous. On the other hand, Ishihara [6, 7] proved constructively that the continuity of sequentially continuous mappings on a separable metric space is equivalent to a certain boundedness principle for subsets of ℕ; in the same paper, he showed that the latter principle holds within the recursive constructive mathematics (RUSS) of the Markov School. Since it is not known whether that principle holds within Bishop's constructive mathematics (BISH), of which INT and RUSS are models and which can be regarded as the constructive core of mathematics, the exploration of sequential continuity within BISH holds some interest.

We discuss the finite-to-one Rudin-Keisler ordering of ultrafilters on the natural numbers, which we baptize the Rudin-Blass ordering in honour of Professor Andreas Blass who worked extensively in the area.

We develop and summarize many of its properties in relation to its bounding and dominating numbers, directedness, and provide applications to continuum theory. In particular, we prove in ZFC alone that there exists an ultrafilter with no Q-point below in the Rudin-Blass ordering.

We show: The procedure mentioned in the title is often impossible. It requires at least an inner model with a measurable cardinal. The consistency strength of changing and from a regular κ to some regular δ < κ is a measurable of Mitchell order δ. There is an application to Cichoń's diagram.

We present a possible computational content of the negative translation of classical analysis with the Axiom of (countable) Choice. Interestingly, this interpretation uses a refinement of the realizability semantics of the absurdity proposition, which is not interpreted as the empty type here. We also show how to compute witnesses from proofs in classical analysis of ∃-statements and how to extract algorithms from proofs of ∀∃-statements. Our interpretation seems computationally more direct than the one based on Gödel's Dialectica interpretation.