We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅(n − 1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ ∣x∣ − c. The ‘only if’ direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity.

Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those l-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω. sets coincide with the r.e. K-trivial ones.

Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees.

We study the sets of the infinite sentences constructible with a dictionary over a finite alphabet, from the viewpoint of descriptive set theory. Among others, this gives some true co-analytic sets. The case where the dictionary is finite is studied and gives a natural example of a set at level ω of the Wadge hierarchy.

The weak non-finite cover property (wnfcp) was introduced in [1] in connection with “axiomatizability” of lovely pairs of models of a simple theory. We find a combinatorial condition on a simple theory equivalent to the wnfcp, yielding a direct proof that the non-finite cover property implies the wnfcp, and that the wnfcp is preserved under reducts. We also study the question whether the wnfcp is preserved when passing from a simple theory T to the theory Tp of lovely pairs of models of T (true in the stable case). While the question remains open, we show, among other things, that if (for a T with the wnfcp) Tp is low, then TP has the wnfcp. To study this question, we describe “double lovely pairs”, and, along the way, we develop the notion of a “lovely n-tuple” of models of a simple theory, which is an analogue of the notion of a beautiful tuple of models of stable theories [2].

Using possibly infinite computations on universal monotone Turing machines, we prove Martin-Löf randomness in ∅′ of the probability that the output be in some set under complexity assumptions about .

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric λ-calculus) is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinatory has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes in both left and right associated terms. Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property.

This paper proves that the disjunction property, the numerical existence property. Church's rule, and several other metamathematical properties hold true for Constructive Zermelo-Fraenkel Set Theory, CZF, and also for the theory CZF augmented by the Regular Extension Axiom.

As regards the proof technique, it features a self-validating semantics for CZF that combines realizability for extensional set theory and truth.

We prove that the property “P doesn't make the old reals Lebesgue null” is preserved under countable support iterations of proper forcings, under the additional assumption that the forcings are nep (a generalization of Suslin proper) in an absolute way. We also give some results for general Suslin ccc ideals.

Let [NB]1 denote the ideal generated by nonbounding c.e. degrees and NCup the ideal of noncuppable c.e. degrees. We show that both [NB]1 ∩ NCup and the ideal generated by nonbounding and noncuppable degrees are new, in the sense that they are different from M, [NB]1 and NCup—the only three known definable ideals so far.

In 1924 Banach and Tarski demonstrated the existence of a paradoxical decomposition of the 3-ball B, i.e., a piecewise isometry from B onto two copies of B. This article answers a question of de Groot from 1958 by showing that there is a paradoxical decomposition of B in which the pieces move continuously while remaining disjoint to yield two copies of B. More generally, we show that if n > 2, any two bounded sets in Rn that are equidecomposable with proper isometries are continuously equidecomposable in this sense.

In the absence of Woodin cardinals, fine structural inner models for mild large cardinal hypotheses admit forcing extensions where bounded forcing axioms hold and yet the reals are projectively well-ordered.

In this note I construct a proper o-minimal expansion of the ordered additive group of rationals.

In this paper we shall prove

Theorem 0.1. Suppose there is a singular strong limit cardinal κ such that □κ fails; then AD holds in L(R).

See [10] for a discussion of the background to this problem. We suspect that more work will produce a proof of the theorem with its hypothesis that κ is a strong limit weakened to ∀α < κ (αω < κ), and significantly more work will enable one to drop the hypothesis that K is a strong limit entirely. At present, we do not see how to carry out even the less ambitious project.

Todorcevic [23] has shown that if the Proper Forcing Axiom (PFA) holds, then □κ fails for all uncountable cardinals κ. Thus we get immediately:

It has been known since the early 90's that PFA implies PD, that PFA plus the existence of a strongly inaccessible cardinal implies ADL(ℝ) and that PFA plus a measurable yields an inner model of ADℝ containing all reals and ordinals. As we do here, these arguments made use of Tororcevic's work, so that logical strength is ultimately coming from a failure of covering for some appropriate core models.

In late 2000, A. S. Zoble and the author showed that (certain consequences of) Todorcevic's Strong Reflection Principle (SRP) imply ADL(ℝ). (See [22].) Since Martin's Maximum implies SRP, this gave the first derivation of ADL(ℝ) from an “unaugmented” forcing axiom.

We consider the reduct to the module language of certain theories of fields with a non surjective endomorphism. We show in some cases the existence of a model companion. We apply our results for axiomatizing the reduct to the theory of modules of non principal ultraproducts of separably closed fields of fixed but non zero imperfection degree.

Being able to state the principles which lie deepest in the foundations of mathematics by sentences in three variables is crucially important for a satisfactory equational rendering of set theories along the lines proposed by Alfred Tarski and Steven Givant in their monograph of 1987.

The main achievement of this paper is the proof that the ‘kernel’ set theory whose postulates are extensionality. (E), and single-element adjunction and removal. (W) and (L), cannot be axiomatized by means of three-variable sentences. This highlights a sharp edge to be crossed in order to attain an ‘algebraization’ of Set Theory. Indeed, one easily shows that the theory which results from the said kernel by addition of the null set axiom, (N), is in its entirety expressible in three variables.

We consider a family of finite universes. The second order existential quantifier Qℜ means for each U Є quantifying over a set of n(ℜ)-place relations isomorphic to a given relation. We define a natural partial order on such quantifiers called interpretability. We show that for every Qℜ, either Qℜ is interpretable by quantifying over subsets of U and one to one functions on U both of bounded order, or the logic L(Qℜ) (first order logic plus the quantifier Qℜ) is undecidable.

The purpose of this paper is to present an algebraic generalization of the traditional two-valued logic. This involves introducing a theory of automorphism algebras, which is an algebraic theory of many-valued logic having a complete lattice as the set of truth values. Two generalizations of the two-valued case will be considered, viz., the finite chain and the Boolean lattice. In the case of the Boolean lattice, on choosing a designated lattice value, this algebra has binary retracts that have the usual axiomatic theory of the propositional calculus as suitable theory. This suitability applies to the Boolean algebra of formalized token models [2] where the truth values are, for example, vocabularies. Finally, as the actual motivation for this paper, we indicate how the theory of formalized token models [2] is an example of a many-valued predicate calculus.

Families of Borel equivalence relations and quasiorders that are cofinal with respect to the Borel reducibility ordering. ≤B, are constructed. There is an analytic ideal on ω generating a complete analytic equivalence relation and any Borel equivalence relation reduces to one generated by a Borel ideal. Several Borel equivalence relations, among them Lipschitz isomorphism of compact metric spaces, are shown to be Kσ complete.

We show that for any real number, the class of real numbers less random than it, in the sense of rK-reducibility, forms a countable real closed subfield of the real ordered field. This generalizes the well-known fact that the computable reals form a real closed field.

With the same technique we show that the class of differences of computably enumerable reals (d.c.e. reals) and the class of computably approximable reals (c.a. reals) form real closed fields. The d.c.e. result was also proved nearly simultaneously and independently by Ng (Keng Meng Ng, Master's Thesis, National University of Singapore, in preparation).

Lastly, we show that the class of d.c.e. reals is properly contained in the class or reals less random than Ω (the halting probability), which in turn is properly contained in the class of c.a. reals, and that neither the first nor last class is a randomness class (as captured by rK-reducibility).

The Dedekind cuts in an ordered set form a set in the sense of constructive Zermelo–Fraenkel set theory. We deduce this statement from the principle of refinement, which we distill before from the axiom of fullness. Together with exponentiation, refinement is equivalent to fullness. None of the defining properties of an ordering is needed, and only refinement for two–element coverings is used.

In particular, the Dedekind reals form a set: whence we have also refined an earlier result by Aczel and Rathjen, who invoked the full form of fullness. To further generalise this, we look at Richman's method to complete an arbitrary metric space without sequences, which he designed to avoid countable choice. The completion of a separable metric space turns out to be a set even if the original space is a proper class: in particular, every complete separable metric space automatically is a set.

We develop a dimension theory for D-semianalytic sets over an arbitrary non-Arehimedean eomplete field. Our main results are the equivalence of several notions of dimension and a theorem on additivity of dimensions of projections and fibers in characteristic 0. We also prove a parameterized version of normalization for D-semianalytic sets.