We give examples of calculi that extend Gentzen’s sequent calculus LK by unsound quantifier inferences in such a way that (i) derivations lead only to true sequents, and (ii) proofs therein are nonelementarily shorter than LK-proofs.

We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV1 + dWPHP(PV).

The standard classes of a first-order theory T are certain classes of prenex T-sentences defined by restrictions on prefix, number of monadic, dyadic, etc. predicate variables, and number of monadic, dyadic, etc. operation variables. In [3] it is shown that, for any theory T, (1) the decision problem for any class of prenex T-sentences specified by such restrictions reduces to that for the standard classes, and (2) there are finitely many standard classes K 1, …, Kn such that any undecidable standard class contains one of K 1, …, Kn . These results give direction to the study of the decision problem.

Below T is predicate logic with identity and operation variables. The Main Theorem solves the decision problem for the standard classes admitting at least one operation variable.

The current paper proves the results announced in [5].

We isolate a new large cardinal concept, “remarkability.” Consistencywise, remarkable cardinals are between ineffable and ω-Erdös cardinals. They are characterized by the existence of “0#-like” embeddings; however, they relativize down to L. It turns out that the existence of a remarkable cardinal is equiconsistent with L(ℝ) absoluteness for proper forcings. In particular, said absoluteness does not imply determinacy.

Traditional combinatory logic uses combinators S and K to represent all Turing-computable functions on natural numbers, but there are Turing-computable functions on the combinators themselves that cannot be so represented, because they access internal structure in ways that S and K cannot. Much of this expressive power is captured by adding a factorisation combinator F. The resulting SF-calculus is structure complete, in that it supports all pattern-matching functions whose patterns are in normal form, including a function that decides structural equality of arbitrary normal forms. A general characterisation of the structure complete, confluent combinatory calculi is given along with some examples. These are able to represent all their Turing-computable functions whose domain is limited to normal forms. The combinator F can be typed using an existential type to represent internal type information.

In this paper we consider the special case of the Banach-Mazur game played on a topological space when the space also has an underlying Boolean Algebra structure. This case was first studied by Jech [2]. The version of the Banach-Mazur game we will play is the following game played on the Boolean algebra:

Players I and II alternate moves playing a descending sequence of elements of a Boolean algebra ℬ.

Player II wins the game iff Πi∈ωbi ≠ 0. Jech first considered these games and showed:

Theorem (Jech [2]). ℬ is (ω1, ∞)-distributive iff player I does not have a winning strategy in the game played on ℬ.

If ℬ has a dense ω-closed subset then it is easy to see that player II has a winning strategy in this game. This paper establishes a partial converse to this, namely it gives cardinality conditions on ℬ under which II having a winning strategy implies ω-closure.

In the course of proving the converse, we consider games of length > ω and generalize Jech's theorem to these games. Finally we present an example due to C. Gray that stands in counterpoint to the theorems in this paper.

In this section we give a few basis definitions and explain our notation. These definitions are all standard.

In part I of this paper it is shown that if the simple theory of types (with an axiom of infinity) is consistent, then so is the system obtained by adjoining axioms of extensionality; in part II a similar metatheorem for Gödel-Bernays set theory will be proved. The first of these results is of particular interest because type theory without the axioms of extensionality is fundamentally rather a simple system, and it should, I believe, be possible to prove that it is consistent.

Let us consider — in some unspecified formal system — a typical expression of the axiom of extensionality; for example:

where A(h) is a formula, and A(f), A(g) are the results of substituting in it the predicate variagles f, g for the free variable h. Evidently, if the system considered contains the predicate calculus, and if h occurs in A(h) only in parts of the form h(t) where t is a term which lies within the range of the quantifier (x), then 1.1 will be provable. But this will not be so in general; indeed, by introducing into the system an intensional predicate of predicates we can make 1.1 false. For example, Myhill introduces a constant S, where ‘Sϕψχω’ means that (the expression) ϕ is the result of substituting ψ for χ in ω.

We show, roughly speaking, that it requires ω iterations of the Turing jump to decode nontrivial information from Boolean algebras in an isomorphism invariant fashion. More precisely, if α is a recursive ordinal, is a countable structure with finite signature, and d is a degree, we say that has αth-jump degreed if d is the least degree which is the αth jump of some degree c such there is an isomorphic copy of with universe ω in which the functions and relations have degree at most c. We show that every degree d ≥ 0(ω) is the ωth jump degree of a Boolean algebra, but that for n < ω no Boolean algebra has nth-jump degree d < 0(n). The former result follows easily from work of L. Feiner. The proof of the latter result uses the forcing methods of J. Knight together with an analysis of various equivalences between Boolean algebras based on a study of their Stone spaces. A byproduct of the proof is a method for constructing Stone spaces with various prescribed properties.

We present a variety of (ω, ∞)-distributive forcings which when applied to models of Martin's Maximum separate certain well known reflection principles. In particular, we do this for the reflection principles SR, SRα (α ≤ ω1), and SRP.

The material presented here belongs to the model theory of the Lκ, λ languages. Our results are either infinitary analogs of important theorems in finitary model theory, or else show that such analogs do not exist.

For example, it is well known that whenever i, and , have the same true Lω, ω sentences (i.e., are elementarily equivalent) for i = 1, 2, then the cardinal sums 1 + 2 and + have the same true Lω, ω sentences, and the direct products 1 · 2 and · have the same true Lω, ω sentences [3]. We show that this is true when ‘Lω, ω’ is replaced by ‘Lκ, λ’ if and only if κ is strongly inaccessible. For Lω1, ω this settles a question, posed by Lopez-Escobar [7].

In §3 we give a complete description of the expressive power of those sentences of Lκ, λ in which the identity symbol is the only relation symbol which occurs. This extends a result by Hanf [4].

Let ‘ϕ’, ‘χ’, and ‘ψ’ be variables ranging over functions from the sentence letters P0, P1, … Pn, … of (propositional) modal logic to sentences of P(eano) Arithmetic), and for each sentence A of modal logic, inductively define Aϕ by

[and similarly for other nonmodal propositional connectives]; and

where Bew(x) is the standard provability predicate for PA and ⌈F⌉ is the PA numeral for the Gödel number of the formula F of PA. Then for any ϕ, (−□⊥)ϕ = −Bew(⌈⊥⌉), which is the consistency assertion for PA; a sentence S is undecidable in PA iff both and , where ϕ(p0) = S. If ψ(p0) is the undecidable sentence constructed by Gödel, then ⊬PA (−□⊥→ −□p0 & − □ − p0)ψ and ⊢PA(P0 ↔ −□⊥)ψ. However, if ψ(p0) is the undecidable sentence constructed by Rosser, then the situation is the other way around: ⊬PA(P0 ↔ −□⊥)ψ and ⊢PA (−□⊥→ −□−p0 & −□−p0)ψ. We call a sentence S of PA extremely undecidable if for all modal sentences A containing no sentence letter other than p0, if for some ψ, ⊬PAAψ, then ⊬PAAϕ, where ϕ(p0) = S. (So, roughly speaking, a sentence is extremely undecidable if it can be proved to have only those modal-logically characterizable properties that every sentence can be proved to have.) Thus extremely undecidable sentences are undecidable, but neither the Godel nor the Rosser sentence is extremely undecidable. It will follow at once from the main theorem of this paper that there are infinitely many inequivalent extremely undecidable sentences.

Partial degrees are equivalence classes of partial natural number functions under some suitable extension of relative recursiveness to partial functions. The usual definitions of relative recursiveness, equivalent in the context of total functions, are distinct when extended to partial functions. The purpose of this paper is to compare the upper semilattice structures of the resulting degrees.

Relative partial recursiveness of partial functions was first introduced in Kleene [2] as an extension of the definition by means of systems of equations of relative recursiveness of total functions. Kleene's relative partial recursiveness is equivalent to the relation between the graphs of partial functions induced by Rogers' [10] relation of relative enumerability (called enumeration reducibility) between sets. The resulting degrees are hence called enumeration degrees. In [2] Davis introduces completely computable or compact functionals of partial functions and uses these to define relative partial recursiveness of partial functions. Davis' functionals are equivalent to the recursive operators introduced in Rogers [10] where a theorem of Myhill and Shepherdson is used to show that the resulting reducibility, here called weak Turing reducibility, is stronger than (i.e., implies, but is not implied by) enumeration reducibility. As in Davis [2], relative recursiveness of total functions with range ⊆{0, 1} may be defined by means of Turing machines with oracles or equivalently as the closure of initial functions under composition, primitive re-cursion, and minimalization (i.e., relative μ-recursiveness). Extending either of these definitions yields a relation between partial functions, here called Turing reducibility, which is stronger still.

Let U and U′ be measures on a cardinal κ: that is, normal κ-complete ultrafilters on κ. The partial ordering ⊲ was defined in [M74]: we say U ⊲ U′ if U ∈ Vκ/U′. A model L(ℱ) was constructed in which this ordering was a well ordering, and it was shown that under proper assumptions the length of this well ordering could be any ordinal up to κ++L(ℱ). In this paper we will revisit this material and show that the coherence required in the construction of ℱ can be greatly weakened. This change simplifies some proofs, weakens the assumption needed for the results stated above (Theorem 1, below), and proves one new result (Theorem 5, below) which is suggestive although its significance is not clear.

We have tried to make this paper self-contained and to that end have repeated some material from [M74]. We begin with some definitions before stating Theorem 1.

The ordering ⊲ is well founded. This may be seen by assuming that it is not and letting κ be least such that ⊲ is not well founded on measures on κ. If U is a measure on κ with an infinite descending chain below it, then the measures on κ in VκU are still not well founded by ⊲, contradicting the fact that iU(κ) is the least cardinal in Vκ/U such that ⊲ is not well founded. Since ⊲ is well founded, we can define O(U) to be the rank of U in the partial ordering ⊲ of measures on κ, and O(κ) to be the rank of this partial ordering.

We present a canonical form for definable subsets of algebraically closed valued fields by means of decompositions into sets of a simple form, and do the same for definable subsets of real closed valued fields. Both cases involve discs, forming “Swiss cheeses” in the algebraically closed case, and cuts in the real closed case. As a step in the development, we give a proof for the fact that in “most” valued fields F, if f(x), g(x) ∈ F[x] and v is the valuation map, then the set {x: v(f(x)) ≤ v(g(x))} is a Boolean combination of discs; in fact, it is a finite union of Swiss cheeses. The development also depends on the introduction of “valued trees”, which we define formally.

Let K be an algebraically closed field of any characteristic, complete with respect to the non-trivial ultrametric absolute value ∣·∣: K → ℝ+. By R denote the valuation ring of K, and by ℘ its maximal ideal. We work within the class of subanalytic sets defined in [5], but our results here also hold for the strongly subanalytic sets introduced in [11] as well as for those subanalytic sets considered in [6]. Let X ⊂ R1 be subanalytic. In [8], we showed that there is a decomposition of X as a union of a finite number of special sets U ⊂ R1 (see below). In this note, in Theorem 1.6, we obtain a version of this result which is uniform in parameters, thereby answering a question brought to our attention by Angus Macintyre. It follows immediately from Theorem 1.6 that the theory of K in the language (see [5] and [6]) is C-minimal in the sense of [3] and [9]. The analogous uniformity result in the p-adic case was recently proved in [12].

Definition 1.1. (i) A disc in R1 is a set of one of the two following forms:

A special set in R1 is a disc minus a finite union of discs.

(ii) R-domains u ⊂ Rm, and their associated rings of analytic functions, , are defined inductively as follows. Rm is an R-domain and , the ring of strictly convergent power series in X1,…, Xm over K. If u is an R-domain with associated ring , (where K 〈X, Y〉 〚ρ〛S is a ring of separated power series, see [5, §2] and [1, §1]) and f, have no common zero on u and ◸ ϵ {<, ≤}, then

is an R-domain and

where J is the ideal generated by I and f − gZ (Z is a new variable) if ◸ is ≤, and

where J is the ideal generated by I and f − gτ (τ a new variable) if ◸ is <. (See [8, Definition 2.2].) R-domains generalize the rational domains of [2, §7.2.3]. It is true, but not easy to prove, that only depends on u as a point set, and is independent of the particular representation of u.

As is well-known, the Bernays-Schönfinkel-Ramsey class of all prenex ∃*∀*-sentences which are valid in classical first-order logic is decidable. This paper paves the way to an analogous result which the authors deem to hold when the only available predicate symbols are ∈ and =, no constants or function symbols are present, and one moves inside a (rather generic) Set Theory whose axioms yield the well-foundedness of membership and the existence of infinite sets. Here semi-decidability of the satisfiability problem for the BSR class is proved by following a purely semantic approach, the remaining part of the decidability result being postponed to a forthcoming paper.

In this paper we introduce the notion of a first order topological structure, and consider various possible conditions on the complexity of the definable sets in such a structure, drawing several consequences thereof.

Our aim is to develop, for a restricted class of unstable theories, results analogous to those for stable theories. The “material basis” for such an endeavor is the analogy between the field of real numbers and the field of complex numbers, the former being a “nicely behaved” unstable structure and the latter the archetypal stable structure. In this sense we try here to situate our work on o-minimal structures [PS] in a general topological context. Note, however, that the p-adic numbers, and structures definable therein, will also fit into our analysis.

In the remainder of this section we discuss several ways of studying topological structures model-theoretically. Eventually we fix on the notion of a structure in which the topology is “explicitly definable” in the sense of Flum and Ziegler [FZ]. In §2 we introduce the hypothesis that every definable set is a Boolean combination of definable open sets. In §3 we introduce a “dimension rank” on (closed) definable sets. In §4 we consider structures on which this rank is defined, and for which also every definable set has a finite number of definably connected definable components. We show that prime models over sets exist under such conditions.

Our main goal in this paper is to establish a Glimm-Effros type dichotomy for arbitrary analytic equivalence relations.

The original Glimm-Effros dichotomy, established by Effros [Ef], [Ef1], who generalized work of Glimm [G1], asserts that if an Fσ equivalence relation on a Polish space X is induced by the continuous action of a Polish group G on X, then exactly one of the following alternatives holds:

(I) Elements of X can be classified up to E-equivalence by “concrete invariants” computable in a reasonably definable way, i.e., there is a Borel function f: X → Y, Y a Polish space, such that xEy ⇔ f(x) = f(y), or else

(II) E contains a copy of a canonical equivalence relation which fails to have such a classification, namely the relation xE0y ⇔ ∃n∀m ≥ n(x(n) = y(n)) on the Cantor space 2ω (ω = {0,1,2, …}), i.e., there is a continuous embedding g: 2ω → X such that xE0y ⇔ g(x)Eg(y).

Moreover, alternative (II) is equivalent to:

(II)′ There exists an E-ergodic, nonatomic probability Borel measure on X, where E-ergodic means that every E-invariant Borel set has measure 0 or 1 and E-nonatomic means that every E-equivalence class has measure 0.

Under a weak set-theoretic assumption we interpret second-order logic in the monadic theory of order.

It is well known that every field (formally, real field ) has an algebraic closure (real-closure ). This is to say is an algebraic extension of which is algebraically closed (real-closed). Of course, certain properties of carry over to . In particular, M. O. Rabin has proved in [3] that the algebraic closure—which is of course unique up to isomorphism—of a computable field is computable. The purpose of this note is to establish an analogue of Rabin's theorem for formally real fields. It is clear that a direct analogue can be formulated only in the case of ordered fields, for otherwise there may be many (nonisomorphic) such .