We study inversions of the jump operator on classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A further application is the complete solution of [24, Problem 3.6.9]: one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails.

Finally we discuss various techniques for coding information into incomplete randoms. Using these techniques we give a negative answer to [24, Problem 8.2.14]: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable.

An argument of A. Borel [Bor-61, Proposition 3.1] shows that every compact connected Lie group is homeomorphic to the Cartesian product of its derived subgroup and a torus. We prove a parallel result for definably compact definably connected groups definable in an o-minimal expansion of a real closed field. As opposed to the Lie case, however, we provide an example showing that the derived subgroup may not have a definable semidirect complement.

Given a finitely generated group Γ we study the space Isom(Γ, ) of all actions of Γ by isometries of the rational Urysohn metric space , where Isom (Γ, ) is equipped with the topology it inherits seen as a closed subset of Isom . When Γ is the free group on n generators this space is just Isom , but is in general significantly more complicated. We prove that when Γ is finitely generated Abelian there is a generic point in Isom(Γ, ), i.e., there is a comeagre set of mutually conjugate isometric actions of Γ on .

We answer a question raised in [9], that is whether the infinite weight of the generic type of the free group is witnessed in Fω. We also prove that the set of primitive elements in finite rank free groups is not uniformly definable. As a corollary, we observe that the generic type over the empty set is not isolated. Finally, we show that uncountable free groups are not ℵ1-homogeneous.

The results herein form part of a larger project to characterize the classification properties of the class of submodels of a homogeneous stable diagram in terms of the solvability (in the sense of [1]) of the potential isomorphism problem for this class of submodels.

We restrict ourselves to locally saturated submodels of the monster model , of some power π. We assume that in Gödel's constructive universe , π is a regular cardinal at least the successor of the first cardinal in which , is stable.

We show that the collection of pairs of submodels in as above which are potentially isomorphic with respect to certain cardinal-preserving extensions of is equiconstructible with 0#. As 0# is highly “transcendental” over , this provides a very strong statement to the effect that potential isomorphism for this class of models not only fails to be set-theoretically absolute, but is of high (indeed of the highest possible) complexity.

The proof uses a novel method that does away with the need for a linear order on the skeleton.

We find the complete Euler characteristics for the categories of definable sets and functions in strongly minimal groups. Their images, which represent the Grothendieck semirings of those categories, are all isomorphic to the semiring of polynomials over the integers with nonnegative leading coefficient. As a consequence, injective definable endofunctions in those groups are surjective. For infinite vector spaces over arbitrary division rings, the same results hold, and more: We also establish the Fubini property for all Euler characteristics, and extend the complete one to the eq-expansion of those spaces while preserving the Fubini property but not completeness. Then, surjective interpretable endofunctions in those spaces are injective, and conversely. Our presentation is made in the general setting of multi-sorted structures.

We prove the statement in the title.

One of the numerous characterizations of a Ramsey cardinal κ involves the existence of certain types of elementary embeddings for transitive sets of size κ satisfying a large fragment of ZFC. We introduce new large cardinal axioms generalizing the Ramsey elementary embeddings characterization and show that they form a natural hierarchy between weakly compact cardinals and measurable cardinals. These new axioms serve to further our knowledge about the elementary embedding properties of smaller large cardinals, in particular those still consistent with V = L.

We consider actions of completely metrisable groups on simplicial trees in the context of the Bass–Serre theory. Our main result characterises continuity of the amplitude function corresponding to a given action. Under fairly mild conditions on a completely metrisable group G, namely, that the set of elements generating a non-discrete or finite subgroup is somewhere dense, we show that in any decomposition as a free product with amalgamation, G = A *cB, the amalgamated groups A, B and C are open in G.

Louveau and Rosendal [5] have shown that the relation of bi-embeddability for countable graphs as well as for many other natural classes of countable structures is complete under Borel reducibility for analytic equivalence relations. This is in strong contrast to the case of the isomorphism relation, which as an equivalence relation on graphs (or on any class of countable structures consisting of the models of a sentence of ) is far from complete (see [5, 2]).

In this article we strengthen the results of [5] by showing that not only does bi-embeddability give rise to analytic equivalence relations which are complete under Borel reducibility, but in fact any analytic equivalence relation is Borel equivalent to such a relation. This result and the techniques introduced answer questions raised in [5] about the comparison between isomorphism and bi-embeddability. Finally, as in [5] our results apply not only to classes of countable structures defined by sentences of , but also to discrete metric or ultrametric Polish spaces, compact metrizable topological spaces and separable Banach spaces, with various notions of embeddability appropriate for these classes, as well as to actions of Polish monoids.

This paper continues the study of the Ramsey-like large cardinals introduced in [5] and [14]. Ramsey-like cardinals are defined by generalizing the characterization of Ramsey cardinals via the existence of elementary embeddings. Ultrafilters derived from such embeddings are fully iterable and so it is natural to ask about large cardinal notions asserting the existence of ultrafilters allowing only α-many iterations for some countable ordinal α. Here we study such α-iterable cardinals. We show that the α-iterable cardinals form a strict hierarchy for α ≤ ω1, that they are downward absolute to L for , and that the consistency strength of Schindler's remarkable cardinals is strictly between 1-iterable and 2-iterable cardinals.

We show that the strongly Ramsey and super Ramsey cardinals from [5] are downward absolute to the core model K. Finally, we use a forcing argument from a strongly Ramsey cardinal to separate the notions of Ramsey and virtually Ramsey cardinals. These were introduced in [14] as an upper bound on the consistency strength of the Intermediate Chang's Conjecture.

We prove that the additive group of the rationals does not have an automatic presentation. The proof also applies to certain other abelian groups, for example, torsion-free groups that are p-divisible for infinitely many primes p, or groups of the form ⊕pϵIZ(p∞), where I is an infinite set of primes.

Jullien's indecomposability theorem (INDEC) states that if a scattered countable linear order is indecomposable, then it is either indecomposable to the left, or indecomposable to the right. The theorem was shown by Montalbán to be a theorem of hyperarithmetic analysis, and then, in the base system RCA0 plus induction, it was shown by Neeman to have strength strictly between weak choice and comprehension. We prove in this paper that induction is needed for the reversal of INDEC. that is for the proof that INDEC implies weak choice. This is in contrast with the typical situation in reverse mathematics, where reversals can usually be refined to use only induction.

We observe simple links between equivalence relations, groups, fields and groupoids (and between preorders, semi-groups, rings and categories), which are type-definable in an arbitrary structure, and apply these observations to the particular context of small and simple structures. Recall that a structure is small if it has countably many n-types with no parameters for each natural number n. We show that a ∅-type-definable group in a small structure is the conjunction of definable groups, and extend the result to semi-groups, fields, rings, categories, groupoids and preorders which are ∅-type-definable in a small structure. For an A-type-definable group GA(where the set A may be infinite) in a small and simple structure, we deduce that

(1) if GA is included in some definable set X such that boundedly many translates of GA cover X, then GA is the conjunction of definable groups.

(2) for any finite tuple ḡ in GA, there is a definable group containing ḡ.

We prove that the first-order theory of the Medvedev degrees, the first-order theory of the Muchnik degrees, and the third-order theory of true arithmetic are pairwise recursively isomorphic (obtained independently by Lewis, Nies, and Sorbi [7]). We then restrict our attention to the degrees of closed sets and prove that the following theories are pairwise recursively isomorphic: the first-order theory of the closed Medvedev degrees, the first-order theory of the compact Medvedev degrees, the first-order theory of the closed Muchnik degrees, the first-order theory of the compact Muchnik degrees, and the second-order theory of true arithmetic. Our coding methods also prove that neither the closed Medvedev degrees nor the compact Medvedev degrees are elementarily equivalent to either the closed Muchnik degrees or the compact Muchnik degrees.

The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar results also for tree automatic structures. These findings close the gaps left open in [28] by improving both the lower and the upper bounds.

We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and all ω-c.e. random degrees. The last result implies recent results of Diamondstone's and Ng's regarding cupping with superlow c.e. degrees and thus gives a use of algorithmic randomness in the study of the c.e. Turing degrees.

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.

We present a characterization of weakly compact cardinals in terms of generalized stationarity. We apply this characterization to construct a model with no partial square sequences.

We study the computability-theoretic complexity and proof-theoretic strength of the following statements: (1) “If is a well-ordering, then so is ”, and (2) “If is a well-ordering, then so is φ(α, )”, where ∝ is a fixed computable ordinal and φ represents the two-placed Veblen function. For the former statement, we show that ω iterations of the Turing jump are necessary in the proof and that the statement is equivalent to over RCA0. To prove the latter statement we need to use ωα iterations of the Turing jump, and we show that the statement is equivalent to . Our proofs are purely computability-theoretic. We also give a new proof of a result of Friedman: the statement “if is a well-ordering, then so is φ(, 0)” is equivalent to ATR0 over RCA0.