We study for each computably bounded $\Pi ^0_1$ class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect $\Pi ^0_1$ class where all c.e. members have degree a. We also show that every $\Pi ^0_1$ set of c.e. indices is realized in some perfect $\Pi ^0_1$ class, and classify the sets of c.e. degrees which can be realized in some $\Pi ^0_1$ class as exactly those with a computable representation.

We explore the possibilities for elementary embeddings $j : M \to N$ , where M and N are models of ZFC with the same ordinals, $M \subseteq N$ , and N has access to large pieces of j. We construct commuting systems of such maps between countable transitive models that are isomorphic to various canonical linear and partial orders, including the real line ${\mathbb R}$ .

In most published systems of modal logic only one or two modal operators occur as undefined constants alongside the primitives of non-modal logic. But in a single informal argument many non-interdefinable modal operators may occur. E.g. in philosophy we may have ‘it is logically true that’, ‘it is analytic that’, and ‘it is physically necessary that’; and in jurisprudence or private international law we may have statements about what it is obligatory or not obligatory to do under several different systems of rules. Moreover even if the contexts of such operators are all referentially opaque, in Quine's sense [1] of being exempt from the substitutivity of truth-functional biconditionals, some are, as it were, opaquer than others, in being exempt from the substitutivity of certain non-truth-functional biconditionals as well.

Let be a finite sequence of algebras of sets given on a set with more than pairwise disjoint sets not belonging to It was shown in [4] and [5] that in this case Let us consider, instead a finite sequence of algebras It turns out that if for each natural i ≤ l there exist no less than pairwise disjoint sets not belonging to then But if l ≥ 195 and if for each natural i ≤ l there exist no less than pairwise disjoint sets not belonging to then After consideration of finite sequences of algebras, it is natural to consider countable sequences of algebras. We obtained two essentially important theorems on a countable sequence of almost σ-algebras (the concept of almost σ-algebra was introduced in [4]).

A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that, for all x, x ∈ A if and only if f(x) ∈ B. Two sets are:

• 1-equivalent if and only if each is m-reducible to the other by one-one reductions;

• p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and

• p-isumorphic if and only if there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible.

In this paper we show the following characterization.

Theorem. The following are equivalent:

(a) P = PSPACE.

(b) Every two 1-equivalent sets are p-isomorphic.

(c) Every two p-invertible equivalent sets are p-isomorphic.

In the present paper we are interested in simple forcing notions and Forcing Axioms. A starting point for our investigations was the article [4] in which several problems were posed. We answer some of those problems here.

In the first section we deal with the problem of adding Cohen reals by simple forcing notions. Here we interpret simple as of small size. We try to establish as weak as possible versions of Martin Axiom sufficient to conclude that some forcing notions of size less than the continuum add a Cohen real. For example we show that MA(σ-centered) is enough to cause that every small σ-linked forcing notion adds a Cohen real (see Theorem 1.2) and MA(Cohen) implies that every small forcing notion adding an unbounded real adds a Cohen real (see Theorem 1.6). A new almost ωω-bounding σ-centered forcing notion ℚ⊚ appears naturally here. This forcing notion is responsible for adding unbounded reals in this sense, that MA(ℚ⊚) implies that every small forcing notion adding a new real adds an unbounded real (see Theorem 1.13).

In the second section we are interested in Anti-Martin Axioms for simple forcing notions. Here we interpret simple as nicely definable. Our aim is to show the consistency of AMA for as large as possible class of ccc forcing notions with large continuum. It has been known that AMA(ccc) implies CH, but it has been (rightly) expected that restrictions to regular (simple) forcing notions might help.

We give a short proof of the fundamental theorem of central element theory (see: Sanchez Terraf and Vaggione, Varieties with definable factor congruences, T.A.M.S. 361). The original proof is constructive and very involved and relies strongly on the fact that the class be a variety. Here we give a more direct nonconstructive proof which applies for the more general case of a first-order class which is both closed under the formation of direct products and direct factors.

In [3] Myhill has constructed a complete system K which allows in it the development of a large and important section of classical mathematics. Completeness is achieved essentially by sacrificing universal quantification and introducing instead the proper ancestral as a primitive idea.

In the following we are presenting a system K0 which will be shown to be equivalent to K (i.e. the primitive operators of both systems are mutually definable in terms of one another). K0 is also complete and covers the same ground as K. K0, however, differs from K by the introduction of the limited universal quantifier instead of the proper ancestral and of concatenation instead of the ordered-pair function as primitive operators. By a further reduction K0 will be shown to be equivalent to the system K1 not containing the abstraction-operator and the class-membership relation.

We construct a non-discrete Polish group none of whose non-discrete subgroups admits a complete left-invariant metric.