A nonstandard set theory *ZFC is proposed that axiomatizes the nonstandard embedding *. Besides the usual principles of nonstandard analysis, all axioms of ZFC except regularity are assumed. A strong form of saturation is also postulated. *ZFC is a conservative extension of ZFC.

We show that equational independence in the sense of Srour equals local non-forking. We then examine so-called almost equational theories where equational independence is a symmetric relation.

Spaces of orderings provide an abstract framework in which to study spaces of orderings of formally real fields. Spaces of orderings of finite chain length are well understood [9, 11]. The Isotropy Theorem [11] and the extension of the Isotropy Theorem given in [13] are the main tools for reducing questions to the finite case, and these are quite effective. At the same time, there are many questions which do not appear to reduce in this way. In this paper we consider four such questions, for a space of orderings (X, G).

1. Is it true that every positive primitive formula P(a) with parameters a in G which holds in every finite subspace of (X, G) necessarily holds in (X, G)?

2. If f: X → ℤ is continuous and Σx∈Vf(x) ≡ 0 mod ∣V∣ holds for all fans V in X with ∣V∣ ≤ 2n, does there exist a form ϕ with entries in G such that mod Cont(X, 2nℤ)?

3. Is it true that Cont(X, 2nℤ) ∩ Witt(X, G) = In(X, G), where I(X, G) denotes the fundamental ideal?

4. Is the separating depth of a constructible set C in X necessarily bounded by the stability index of (X, G)?

The unexplained terminology and notation is explained later in the main body of the paper. In a certain sense Question 1 is the main question. At the same time, Questions 2, 3 and 4 are of considerable interest, both from the point of view of quadratic form theory and from the point of view of real algebraic geometry.

The first system of intersection types. Coppo and Dezani [3], extended simple types to include intersections and added intersection introduction and elimination rules ((ΛI ) and (ΛE) ) to the type assignment system. The major advantage of these new types was that they were invariant under β-equality, later work by Barendregt, Coppo and Dezani [1], extended this to include an (η) rule which gave types invariant under βη-reduction.

Urzyczyn proved in [6] that for both these systems it is undecidable whether a given intersection type is empty. Kurata and Takahashi however have shown in [5] that this emptiness problem is decidable for the sytem including (η). but without (ΛI).

The aim of this paper is to classify intersection type systems lacking some of (ΛI), (ΛE) and (η), into equivalence classes according to their strength in typing λ-terms and also according to their strength in possessing inhabitants.

This classification is used in a later paper to extend the above (un)decidability results to two of the five inhabitation-equivalence classes. This later paper also shows that the systems in two more of these classes have decidable inhabitation problems and develops algorithms to find such inhabitants.

Let B be a superatomic Boolean algebra (BA). The rank of B (rk(B)). is defined to be the Cantor Bendixon rank of the Stone space of B. If a ∈ B − {0}, then the rank of a in B (rk(a)). is defined to be the rank of the Boolean algebra . The rank of 0B is defined to be −1. An element a ∈ B − {0} is a generalized atom , if the last nonzero cardinal in the cardinal sequence of B ↾ a is 1. Let a, b ∈ . We denote a ˜ b, if rk(a) = rk(b) = rk(a · b). A subset H ⊆ is a complete set of representatives (CSR) for B, if for every a there is a unique h ∈ H such that h ~ a. Any CSR for B generates B. We say that B is canonically well-generated (CWG), if it has a CSR H such that the sublattice of B generated by H is well-founded. We say that B is well-generated, if it has a well-founded sublattice L such that L generates B.

Theorem 1. Let B be a Boolean algebra with cardinal sequence . If B is CWG, then every subalgebra of B is CWG.

A superatomic Boolean algebra B is essentially low (ESL), if it has a countable ideal I such that rk(B/I) ≤ 1.

Theorem 1 follows from Theorem 2.9. which is the main result of this work. For an ESL BA B we define a set FB of partial functions from a certain countably infinite set to ω (Definition 2.8). Theorem 2.9 says that if B is an ESL Boolean algebra, then the following are equivalent.

(1) Every subalgebra of B is CWG: and

(2) FB is bounded.

Theorem 2. If an ESL Boolean algebra is not CWG, then it has a subalgebra which is not well-generated.

We consider the problem of recognizing important properties of logical calculi and find complexity bounds for some decidable properties. For a given logical system L, a property P of logical calculi is called decidable over L if there is an algorithm which for any finite set Ax of new axiom schemes decides whether the calculus L + Ax has the property P or not. In [11] the complexity of tabularity, pre-tabularity. and interpolation problems over the intuitionistic logic Int and over modal logic S4 was studied, also we found the complexity of amalgamation problems in varieties of Heyting algebras and closure algebras.

In the present paper we deal with positive calculi. We prove NP-completeness of tabularity, DP-hardness of pretabularity and PSPACE-completeness of interpolation problem over Int+. In addition to above-mentioned properties, we consider Beth's definability properties. Also we improve some complexity bounds for properties of superintuitionistic calculi.

A computably enumerable (c.e.) degree is a maximal contiguous degree if it is contiguous and no c.e. degree strictly above it is contiguous. We show that there are infinitely many maximal contiguous degrees. Since the contiguous degrees are definable, the class of maximal contiguous degrees provides the first example of a definable infinite anti-chain in the c.e. degrees. In addition, we show that the class of maximal contiguous degrees forms an automorphism base for the c.e. degrees and therefore for the Turing degrees in general. Finally we note that the construction of a maximal contiguous degree can be modified to answer a question of Walk about the array computable degrees and a question of Li about isolated formulas.

In this paper, we continue investigations into the asymptotic behavior of solutions of differential equations over o-minimal structures.

Let ℜ be an expansion of the real field (ℝ, +, ·).

A differentiable map F = (F1,…, F1): (a, b) → ℝi is ℜ-Pfaffian if there exists G: ℝ1+l → ℝl definable in ℜ such that F′(t) = G(t, F(t)) for all t ∈ (a, b) and each component function Gi: ℝ1+l → ℝ is independent of the last l − i variables (i = 1, …, l). If ℜ is o-minimal and F: (a, b) → ℝl is ℜ-Pfaffian, then (ℜ, F) is o-minimal (Proposition 7). We say that F: ℝ → ℝl is ultimately ℜ-Pfaffian if there exists r ∈ ℝ such that the restriction F ↾(r, ∞) is ℜ-Pfaffian. (In general, ultimately abbreviates “for all sufficiently large positive arguments”.)

The structure ℜ is closed under asymptotic integration if for each ultimately non-zero unary (that is, ℝ → ℝ) function f definable in ℜ there is an ultimately differentiable unary function g definable in ℜ such that limt→+∞[g′(t)/f(t)] = 1- If ℜ is closed under asymptotic integration, then ℜ is o-minimal and defines ex: ℝ → ℝ (Proposition 2).

Note that the above definitions make sense for expansions of arbitrary ordered fields.

We investigate the effect of a variant of Matet forcing on ultrafilters in the ground model and give a characterization of those P–points that survive such forcing, answering a question left open by Blass [4]. We investigate the question of when this variant of Matet forcing can be used to diagonalize small filters without destroying P–points in the ground model. We also deal with the question of generic existence of stable ordered-union ultrafilters.

Let us recall that Raphael Robinson's Arithmetic Q is an axiom system that differs from Peano Arithmetic essentially by containing no Induction axioms [13], [18]. We will generalize the semantic-tableaux version of the Second Incompleteness Theorem almost to the level of System Q. We will prove that there exists a single rather long Π1 sentence, valid in the standard model of the Natural Numbers and denoted as V. such that if α is any finite consistent extension of Q + V then α will be unable to prove its Semantic Tableaux consistency. The same result will also apply to axiom systems α with infinite cardinality when these infinite-sized axiom systems satisfy a minor additional constraint, called the Conventional Encoding Property.

Our formalism will also imply that the semantic-tableaux version of the Second Incompleteness Theorem generalizes for the axiom system IΣ0, as well as for all its natural extensions. (This answers an open question raised twenty years ago by Paris and Wilkie [15].)