§1. Introduction. This paper considers several complexity questions regarding Borel automorphisms of a Polish space. Recall that a Borel automorphism is a bijection of the space with itself whose graph is a Borel set (equivalently, the inverse image of any Borel set is Borel). Since the inverse of a Borel automorphism is another Borel automorphism, as is the composition of two Borel automorphisms, the set of Borel automorphisms of a given Polish space forms a group under the operation of composition. We can also consider the class of automorphisms of all Polish spaces. We will be primarily concerned here with the following notion of equivalence:

Definition 1.1. Two Borel automorphisms f and g of the Polish spaces X and Y are said to be Borel isomorphic, f ≅ g, if they are conjugate, i.e. there is a Borel bijection φ: X → Y such that φ ∘ f = g ∘ φ.

We restrict ourselves to automorphisms of uncountable Polish spaces, as the Borel automorphisms of a countable space are simply the permutations of the space. Since any two uncountable Polish spaces are Borel isomorphic, any Borel automorphism is Borel isomorphic to some automorphism of a fixed space. Hence, up to Borel isomorphism we can fix a Polish space and represent any Borel automorphism as an automorphism of this space. We will use the Cantor space 2ω (with the product topology) as our representative space.

Let T be an infinite pseudo-tree. In [2], we showed that the cellularity of the pseudo-tree algebra Treealg(T) was the maximum of four cardinals cT, lT, ϕT, and μT: roughly, cT is the “tallness” of T: lT is the “width” of T, ϕ is the number of “points of finite branching” in T: and μ is the number of “sections of no branching” in T. Here we ask: which inequalities among these four cardinals may be satisfied, in some sense, by a pseudo-tree? We show that the possible inequalities among cT, lT, ϕT, and μT attained by pseudo-trees T are closely related to the existence of generalized Suslin trees.

Let M = 〈M, +, <, 0, {λ}λЄD〉 be an ordered vector space over an ordered division ring D, and G = 〈G, ⊕, eG〉 an n-dimensional group definable in M. We show that if G is definably compact and definably connected with respect to the t-topology, then it is definably isomorphic to a ‘definable quotient group’ U/L, for some convex V-definable subgroup U of 〈Mn, +〉 and a lattice L of rank n. As two consequences, we derive Pillay's conjecture for a saturated M as above and we show that the o-minimal fundamental group of G is isomorphic to L.

We revisit the foundations of positive model theory, introducing h-inductive sentences. These allow a considerably simplified presentation of positive model theory, as well as a characterisation of Hausdorffcats by an amalgamation property of their h-inductive theory.

An amalgamation base p in a simple theory is stably definable if its canonical base is interde-finable with the set of canonical parameters for the ϕ-definitions of p as ϕ ranges through all stable formulae. A necessary condition for stably definability is given and used to produce an example of a supersimple theory with stable forking having types that are not stably definable. This answers negatively a question posed in [8]. A criterion for and example of a stably definable amalgamation base whose restriction to the canonical base is not axiomatised by stable formulae are also given. The examples involve generic relations over non CM-trivial stable theories.

By recent work on some conjectures of Pillay, each definably compact group G in a saturated o-minimal expansion of an ordered field has a normal “infinitesimal subgroup” G00 such that the quotient G/G00, equipped with the “logic topology”, is a compact (real) Lie group. Our first result is that the functor G ↦ G/G00 sends exact sequences of definably compact groups into exact sequences of Lie groups. We then study the connections between the Lie group G/G00 and the o-minimal spectrum of G. We prove that G/G00 is a topological quotient of . We thus obtain a natural homomorphism Ψ* from the cohomology of G/G00 to the (Čech-)cohomology of . We show that if G00 satisfies a suitable contractibility conjecture then is acyclic in Čech cohomology and Ψ is an isomorphism. Finally we prove the conjecture in some special cases.

This addendum to [2] shows that the set of tautological quantum logical propositional formulas for a finite dimensional vector space ℂn is different for every n, affirmatively answering a question posed therein.

We consider three problems concerning alpha conversion of closed terms (combinators).

(1) Given a combinator M find the an alpha convert of M with a smallest number of distinct variables.

(2) Given two alpha convertible combinators M and N find a shortest alpha conversion of M to N.

(3) Given two alpha convertible combinators M and N find an alpha conversion of M to N which uses the smallest number of variables possible along the way.

We obtain the following results.

(1) There is a polynomial time algorithm for solving problem (1). It is reducible to vertex coloring of chordal graphs.

(2) Problem (2) is co-NP complete (in recognition form). The general feedback vertex set problem for digraphs is reducible to problem (2).

(3) At most one variable besides those occurring in both M and N is necessary. This appears to be the folklore but the proof is not familiar. A polynomial time algorithm for the alpha conversion of M to N using at most one extra variable is given.

There is a tradeoff between solutions to problem (2) and problem (3) which we do not fully understand.

In this paper we present two calculi for intuitionistic logic. The first one. IG, is characterized by the fact that every proof-search terminates and termination is reached without jeopardizing the subformula property. As to the second one, SIC, proof-search terminates, the subformula property is preserved and moreover proof-search is performed without any recourse to metarules, in particular there is no need to back-track. As a consequence, proof-search in the calculus SIC is accomplished by a single tree as in classical logic.

We study the problem of existence of maximal chains in the Turing degrees. We show that:

1. ZF + DC + “There exists no maximal chain in the Turing degrees” is equiconsistent with ZFC + “There exists an inaccessible cardinal”

2. For all a ∈ 2ω, (ω1)L[a] = ω1 if and only if there exists a [a] maximal chain in the Turing degrees. As a corollary, ZFC + “There exists an inaccessible cardinal” is equiconsistent with ZFC + “There is no (bold face) maximal chain of Turing degrees”.

We show that in the models of u < ∂ from [14] there are infinitely many near-coherence classes of ultrafilters, thus answering Banakh's and Blass' Question 30 of [3] negatively. By an unpublished result of Canjar, there are at least two classes in these models.

Asymptotic extremal combinatorics deals with questions that in the language of model theory can be re-stated as follows. For finite models M, N of an universal theory without constants and function symbols (like graphs, digraphs or hypergraphs), let p(M, N) be the probability that a randomly chosen sub-model of N with ∣M∣ elements is isomorphic to M. Which asymptotic relations exist between the quantities p(M1,N),…, p(Mh,N), where M1,…, M1, are fixed “template” models and ∣N∣ grows to infinity?

In this paper we develop a formal calculus that captures many standard arguments in the area, both previously known and apparently new. We give the first application of this formalism by presenting a new simple proof of a result by Fisher about the minimal possible density of triangles in a graph with given edge density.

We consider the notion of bounded m-ary patch-width defined in [9], and its very close relative m-constructibility defined below. We show that the notions of m-constructibility all coincide for m ≥ 3, while 1-constructibility is a weaker notion. The same holds for bounded m-ary patch-width. The case m = 2 is left open.

A new axiom is proposed, the Ground Axiom, asserting that the universe is not a nontrivial set forcing extension of any inner model. The Ground Axiom is first-order expressible, and any model of ZFC has a class forcing extension which satisfies it. The Ground Axiom is independent of many well-known set-theoretic assertions including the Generalized Continuum Hypothesis, the assertion V=HOD that every set is ordinal definable, and the existence of measurable and supercompact cardinals. The related Bedrock Axiom, asserting that the universe is a set forcing extension of a model satisfying the Ground Axiom, is also first-order expressible, and its negation is consistent.

We completely characterize the logical hierarchy of subsystems of open induction introduced by Boughattas [1].

Let S be the set of those α ∈ ω2 that have cofinality ω1. It is consistent relative to a measurable that the nonempty player wins the pressing down game of length ω1, but not the Banach-Mazur game of length ω + 1 (both games starting with S).

Resolution is the most widely studied approach to propositional theorem proving. In developing efficient resolution-based algorithms, dozens of variants and refinements of resolution have been studied from both the empirical and analytic sides. The most prominent of these refinements are: DP (ordered), DLL (tree), semantic, negative, linear and regular resolution. In this paper, we characterize and study these six refinements of resolution. We give a nearly complete characterization of the relative complexities of all six refinements. While many of the important separations and simulations were already known, many new ones are presented in this paper; in particular, we give the first separation of semantic resolution from general resolution. As a special case, we obtain the first exponential separation of negative resolution from general resolution. We also attempt to present a unifying framework for studying all of these refinements.

We prove the following results: (i) PV proves NP ⊆ P/poly iff PV proves coNP ⊆ NP/O(1). (ii) If PV proves NP ⊆ P/poly then PV proves that the Polynomial Hierarchy collapses to the Boolean Hierarchy, (iii) proves NP ⊆ P/poly iff proves coNP ⊆ NP/O(log n). (iv) If proves NP ⊆ P/poly then proves that the Polynomial Hierarchy collapses to PNP[log n]. (v) If proves NP ⊆ P/poly then proves that the Polynomial Hierarchy collapses to PNP.

Motivated by these results we introduce a new concept in proof complexity: proof systems with advice, and we make some initial observations about them.

We isolate a forcing which increases the value of while preserving ω1 under the assumption that there is a precipitous ideal on ω1 and a measurable cardinal.

We prove constructively that, in order to derive the uniform continuity theorem for pointwise continuous mappings from a compact metric space into a metric space, it is necessary and sufficient to prove any of a number of equivalent conditions, such as that every pointwise continuous mapping of [0, 1] into ℝ is bounded. The proofs are analytic, making no use of, for example, fan-theoretic ideas.