We investigate diagonal actions of Polish groups and the related intersection operator on closed subgroups of the acting group. The Borelness of the diagonal orbit equivalence relation is characterized and is shown to be connected with the Borelness of the intersection operator. We also consider relatively tame Polish groups and give a characterization of them in the class of countable products of countable abelian groups. Finally an example of a logic action is considered and its complexity in the Borel reducbility hierarchy determined.

Strengthening a theorem of Hjorth this paper gives a new characterization of which Polish groups admit compatible complete left invariant metrics. As a corollary it is proved that any Polish group without a complete left invariant metric has a continuous action on a Polish space whose associated orbit equivalence relation is not essentially countable.

We show that there exist downwards properly (in fact noncuppable) e-degrees that are not high. We also show that every high e-degree bounds a noncuppable e-degree.

Let 0 < n < ω. If there are n Woodin cardinals and a measurable cardinal above, but doesn't exist, then the core model K exists in a sense made precise. An Iterability Inheritance Hypothesis is isolated which is shown to imply an optimal correctness result for K.

In this paper we formulate epsilon substitution method for a theory -FIX for nonmonotonic inductive definitions. Then we give a termination proof of the H-processes based on Ackermann [1].

Gödel's Second Incompleteness Theorem states axiom systems of sufficient strength are unable to verify their own consistency. We will show that axiomatizations for a computer's floating point arithmetic can recognize their cut-free consistency in a stronger respect than is feasible under integer arithmetics. This paper will include both new generalizations of the Second Incompleteness Theorem and techniques for evading it.

Let V be the cumulative set theoretic hierarchy, generated from the empty set by taking powers at successor stages and unions at limit stages and. following [2], let the primitive language of set theory be the first order language which contains binary symbols for equality and membership only. Despite the existence of ∀∀-formulae in the primitive language, with two free variables, which are satisfiable in ∀ but not by finite sets ([5]). and therefore of ∃∃∀∀ sentences of the same language, which are undecidable in ZFC without the Axiom of Infinity, truth in V for ∃*∀∀-sentences of the primitive language, is decidable ([1]). Completeness of ZF with respect to such sentences follows.

We show that the structure of recursively enumerable degrees is not a Σ1-elementary substructure of , where (n > 1) is the structure of n-r.e. degrees in the Ershov hierarchy.

In this paper we introduce a notation system for the infinitary derivations occurring in the ordinal analysis of KP + Π3-Reflection due to Michael Rathjen. This allows a finitary ordinal analysis of KP + Π3-Reflection. The method used is an extension of techniques developed by Wilfried Buchholz, namely operator controlled notation systems for RS∞-derivations. Similarly to Buchholz we obtain a characterisation of the provably recursive functions of KP + Π3-Reflection as <-recursive functions where < is the ordering on Rathjen's ordinal notation system . Further we show a conservation result for -sentences.

We show that in the language of { ≤ }. the Π3-fragment of the first order theory of the -enumeration degrees is undecidable. We then extend this result to show that the Π3-theory of any substructure of the enumeration degrees which contains the -degrees is undecidable.

Let λ be a singular cardinal of uncountable cofinality ν. Under various assumptions about the sizes of covering families for cardinals below λ, we prove upper bounds for the covering number COV(λ. λ. ν+. 2). This covering number is closely related to the cofinality of the partial order ([λ]ν. ⊆).

In this paper, we show that the predicate logics of consistent extensions of Heyting's Arithmetic plus Church's Thesis with uniqueness condition are complete . Similarly, we show that the predicate logic of HA*. i.e. Heyting's Arithmetic plus the Completeness Principle (for HA*) is complete . These results extend the known results due to Valery Plisko. To prove the results we adapt Plisko's method to use Tennenbaum's Theorem to prove ‘categoricity of interpretations’ under certain assumptions.

Levin and Schnorr (independently) introduced the monotone complexity, Km (α), of a binary string α. We use monotone complexity to define the relative complexity (or relative randomness) of reals. We define a partial ordering ≤Km on 2ω by α ≤Km β iff there is a constant c such that Km(α | n) ≤ Km(β | n)+ c for all n. The monotone degree of α is the set of all β such that α Km β and β Km α. We show the monotone degrees contain an antichain of size , a countable dense linear ordering (of degrees of cardinality ), and a minimal pair.

Downey, Hirschfeldt, LaForte, Nies and others have studied a similar structure, the K-degrees, where K is the prefix-free Kolmogorov complexity. A minimal pair of K-degrees was constructed by Csima and Montalban. Of particular interest are the noncomputable trivial reals, first constructed by Solovay. We defineareal to be (Km,K)-trivial if for some constant c, Km(α | n) ≤ K(n) + c for all n. It is not known whether there is a Km-minimal real, but we show that any such real must be (Km,K)-trivial.

Finally, we consider the monotone degrees of the computably enumerable (c.e.) and strongly computably enumerable (s.c.e.) reals. We show there is no minimal c.e. monotone degree and that Solovay reducibility does not imply monotone reducibility on the c.e. reals. We also show the s.c.e. monotone degrees contain an infinite antichain and a countable dense linear ordering.

We show that if κ is a weakly compact cardinal, then

for any ordinals α < κ+ and μ < κ, and any finite ordinals m and n. This polarized partition relation represents the statement that for any partition

of κ × κ+ into m + μ pieces either there are A ∈ [κ]κ, B ∈ [κ]+]α and i < m with A × B ⊆ Ki or there are C ∈ [κ]κ, , and j < μ with C × D ⊆ Lj. Related results for measurable and almost measurable κ are also investigated. Our proofs of these relations involve the use of elementary substructures of set models of large fragments of ZFC.

It is well known that classical propositional logic can be interpreted in intuitionistic prepositional logic. In particular Glivenko's theorem states that a formula is provable in the former iff its double negation is provable in the latter. We extend Glivenko's theorem and show that for every involutive substructural logic there exists a minimum substructural logic that contains the first via a double negation interpretation. Our presentation is algebraic and is formulated in the context of residuated lattices. In the last part of the paper, we also discuss some extended forms of the Koltnogorov translation and we compare it to the Glivenko translation.

A real is called properly n-generic if it is n-generic but not n + 1-generic. We show that every 1-generic real computes a properly 1-generic real. On the other hand, if m > n ≥ 2 then an m-generic real cannot compute a properly n-generic real.

Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating properties. Although these computability results had been announced earlier, their proofs have been deferred until this paper.

Computably enumerable sets have long been used to prove undecidability of mathematical problems such as the word problem for groups and Hilbert's Tenth Problem. However, this example by Nabutovsky and Weinberger is perhaps the first example of the use of c.e. sets to demonstrate specific mathematical or geometric complexity of a mathematical structure such as the depth and distribution of local minima.

We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows:

• ΩU[X] is random whenever X is Σn0-complete or Πn0-complete for some n ≥ 2.

• However, for n ≥ 2, ΩU[X] is not n-random when X is Σn0 or Πn0. Nevertheless, there exists Δn+10 sets such that ΩU[X] is n-random.

• There are Δ20 sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is Δn+10 and Σn0-hard such that ΩU[X] is not random.

We also look at the range of ΩU as an operator. We prove that the set {ΩU[X]: X ⊆ 2≤ω} is a finite union of closed intervals. It follows that for any optimal machine U and any sufficiently small real r, there is a set X ⊆ 2≤ω recursive in ∅′ ⊕ r, such that ΩU[X] = r.

The same questions are also considered in the context of infinite computations, and lead to similar results.

Jeremy Avigad kindly pointed out to me that the proof of Theorem 2 in [3] is incomplete. At the very end it assumes that when is located, so is . This is not correct. In fact, Avigad explained that the construction in the proof of Theorem 15.3 in [1] can be read as a recursive counterexample to the statement: ‘If , then Anx converges for every x’. As a result the conclusion of Theorem 2 should be that An converges if and only if is located. Similar changes have to be made in the abstract, Lemma 4, and Theorem 16. Finally, the paragraph on ergodic measure preserving transformations should be removed.

As an unrelated point we would like to mention that in the last two displayed equations of the proof of theorem 1 the term should be replaced by .