Jumps of computably enumerable equivalence relations

We study computably enumerable equivalence relations (or, ceers), under computable reducibility ≤, and the halting jump operation on ceers. We show that every jump is uniform join-irreducible, and thus join-irreducible. Therefore, the uniform join of two incomparable ceers is not equivalent to any jump. On the other hand there exist ceers that are not equivalent to jumps, but are uniform join-irreducible: in fact above any non-universal ceer there is a ceer which is not equivalent to a jump, and is uniform join-irreducible. We also study transfinite iterations of the jump operation. If a is an ordinal notation, and E is a ceer, then let $E^{(a)}$ denote the ceer obtained by transfinitely iterating the jump on E along the path of ordinal notations up to a. In contrast with what happens for the Turing jump and Turing reducibility, where if a set X is an upper bound for the A-arithmetical sets then $X^{(2)}$ computes $A^{(\omega )}$, we show that there is a ceer R such that $R\ge {\mathrm{Id}}^{(n)}$, for every finite ordinal n, but, for all k, $R^{(k)}?{\mathrm{Id}}^{(\omega )}$ (here Id is the identity equivalence relation). We show that if $a,b$ are notations of the same ordinal less than ${\omega }^2$, then $E^{(a)}\equiv E^{(b)}$, but there are notations $a,b$ of ${\omega }^2$ such that ${\mathrm{Id}}^{(a)}$ and ${\mathrm{Id}}^{(b)}$ are incomparable. Moreover, there is no non-universal ceer which is an upper bound for all the ceers of the form ${\mathrm{Id}}^{(a)}$ where a is a notation for ${\omega }^2$.     

Essential countability of treeable equivalence relations

We establish a dichotomy theorem characterizing the circumstances under which a treeable Borel equivalence relation E is essentially countable. Under additional topological assumptions on the treeing, we in fact show that E   is essentially countable if and only if there is no continuous embedding of _E1${\mathbb{E}}_1$ into E. Our techniques also yield the first classical proof of the analogous result for hypersmooth equivalence relations, and allow us to show that up to continuous Kakutani embeddability, there is a minimum Borel function which is not essentially countable-to-one.     

Coding into HOD via normal measures with some applications

We develop a new method for coding sets while preserving GCH in the presence of large cardinals, particularly supercompact cardinals. We will use the number of normal measures carried by a measurable cardinal as an oracle, and therefore, in order to code a subset A of κ, we require that our model contain κ many measurable cardinals above κ. Additionally we will describe some of the applications of this result. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Definable nilpotent and soluble envelopes in groups without the independence property

We prove that in a group without the independence property a nilpotent subgroup is always contained in a definable nilpotent subgroup of the same nilpotency class. The analogue for the soluble case is also shown when the subgroup is normal in the ambient group.     

On the rank of certain matrices

This note is an appendix to the paper “Osculating spaces and diophantine equations (with an Appendix by Pietro Corvaja and Umberto Zannier)” by M. Bolognesi and G. Pirola.     

On definability of types of finite Cantor‐Bendixson rank

We prove that every type of finite Cantor‐Bendixson rank over a model of a first‐order theory without the strict order property is definable and has a unique nonforking extension to a global type. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

The rigid relation principle,a new weak choice principle

The rigid relation principle, introduced in this article, asserts that every set admits a rigid binary relation. This follows from the axiom of choice, because well‐orders are rigid, but we prove that it is neither equivalent to the axiom of choice nor provable in Zermelo‐Fraenkel set theory without the axiom of choice. Thus, it is a new weak choice principle. Nevertheless, the restriction of the principle to sets of reals (among other general instances) is provable without the axiom of choice.     

A note on parameter free Π1‐induction and restricted exponentiation

We characterize the sets of all Π₂ and all $\mathcal {B}(\Sigma _{1})We characterize the sets of all Π₂ and all $\mathcal {B}(\Sigma _{1})$ (= Boolean combinations of Σ₁) theorems of IΠ^?₁ in terms of restricted exponentiation, and use these characterizations to prove that both sets are not deductively equivalent. We also discuss how these results generalize to n > 0. As an application, we prove that a conservation theorem of Beklemishev stating that IΠ^?_{n + 1} is conservative over IΣ^?_n with respect to $\mathcal {B}(\Sigma _{n+1})$ sentences cannot be extended to Π_{n + 2} sentences. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

On a positive set theory with inequality

We introduce a quite natural Frege‐style set theory, which we call Strong‐Frege‐2 $(\mathsf {SF}_2)$, a sort of simplification of the theory considered in 13 (under the name Strong‐Frege‐3) and 1 (under the name F2). We give a model of a weaker variant of $\mathsf {SF}_2$, called $\mathsf {SF}_2\mathsf {AC}$, where atoms and coatoms are allowed. To construct the model we use an enumeration “almost without repetitions” of the Π¹₁ sets of natural numbers; such an enumeration can be obtained via a classical priority argument much in the style of 5 and 15 . © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Models of expansions of \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}${\mathbb N}$\end{document} with no end extensions

We deal with models of Peano arithmetic (specifically with a question of Ali Enayat). The methods are from creature forcing. We find an expansion of ${\mathbb N}$ such that its theory has models with no (elementary) end extensions. In fact there is a Borel uncountable set of subsets of ${\mathbb N}$ such that expanding ${\mathbb N}$ by any uncountably many of them suffice. Also we find arithmetically closed ${\mathcal A}$ with no ultrafilter on it with suitable definability demand (related to being Ramsey). © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

On monotone hull operations

We extend results of Elekes and Máthé on monotone Borel hulls to an abstract setting of measurable space with negligibles. This scheme yields the respective theorems in the case of category and in the cases associated with the Mendez σ‐ideals on the plane. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

On the mutually non isomorphic ℓp(ℓq) spaces

We extend a result of Pe?czyński showing that {?_p(?_q): 1 ≤ p, q ≤ ∞} is a family of mutually non isomorphic Banach spaces. Some results on complemented subspaces of ?_p(?_q) are also given.     

Weak saturation of ideals on Pκ(λ)

We show that if κ is an infinite successor cardinal, and λ > κ a cardinal of cofinality less than κ satisfying certain conditions, then no (proper, fine, κ‐complete) ideal on P_κ(λ) is weakly λ⁺‐saturated. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Simple monadic theories and partition width

We study tree‐like decompositions of models of a theory and a related complexity measure called partition width. We prove a dichotomy concerning partition width and definable pairing functions: either the partition width of models is bounded, or the theory admits definable pairing functions. Our proof rests on structure results concerning indiscernible sequences and finitely satisfiable types for theories without definable pairing functions. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Indestructibility,HOD, and the Ground Axiom

Let φ₁ stand for the statement V = HOD and φ₂ stand for the Ground Axiom. Suppose T_i for i = 1, …, 4 are the theories “ZFC + φ₁ + φ₂,” “ZFC + ¬φ₁ + φ₂,” “ZFC + φ₁ + ¬φ₂,” and “ZFC + ¬φ₁ + ¬φ₂” respectively. We show that if κ is indestructibly supercompact and λ > κ is inaccessible, then for i = 1, …, 4, A_i = _df{δ < κ∣δ is an inaccessible cardinal which is not a limit of inaccessible cardinals and V_δ?T_i} must be unbounded in κ. The large cardinal hypothesis on λ is necessary, as we further demonstrate by constructing via forcing four models in which A_i = ?? for i = 1, …, 4. In each of these models, there is an indestructibly supercompact cardinal κ, and no cardinal δ > κ is inaccessible. We show it is also the case that if κ is indestructibly supercompact, then V_κ?T₁, so by reflection, B₁ = _df{δ < κ∣δ is an inaccessible limit of inaccessible cardinals and V_δ?T₁} is unbounded in κ. Consequently, it is not possible to construct a model in which κ is indestructibly supercompact and B₁ = ??. On the other hand, assuming κ is supercompact and no cardinal δ > κ is inaccessible, we demonstrate that it is possible to construct a model in which κ is indestructibly supercompact and for every inaccessible cardinal δ < κ, V_δ?T₁. It is thus not possible to prove in ZFC that B_i = _df{δ < κ∣δ is an inaccessible limit of inaccessible cardinals and V_δ?T_i} for i = 2, …, 4 is unbounded in κ if κ is indestructibly supercompact. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Weakly measurable cardinals

In this article, we introduce the notion of weakly measurable cardinal, a new large cardinal concept obtained by weakening the familiar concept of a measurable cardinal. Specifically, a cardinal κ is weakly measurable if for any collection $\mathcal {A}$ containing at most κ⁺ many subsets of κ, there exists a nonprincipal κ‐complete filter on κ measuring all sets in $\mathcal {A}$. Every measurable cardinal is weakly measurable, but a weakly measurable cardinal need not be measurable. Moreover, while the GCH cannot fail first at a measurable cardinal, I will show that it can fail first at a weakly measurable cardinal. More generally, if κ is measurable, then we can make its weak measurability indestructible by the forcing Add(κ, η) for any η while forcing the GCH to hold below κ. Nevertheless, I shall prove that weakly measurable cardinals and measurable cardinals are equiconsistent. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Kolmogorov complexity and characteristic constants of formal theories of arithmetic

We investigate two constants c _T and r _T , introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that c _T does not represent the complexity of T and found that for two theories S and T , one can always find a universal Turing machine such that $c_\mathbf {S}= c_\mathbf {T}$. We prove the following are equivalent: $c_\mathbf {S}\ne c_\mathbf {T}$ for some universal Turing machine, $r_\mathbf {S}\ne r_\mathbf {T}$ for some universal Turing machine, and T proves some Π₁‐sentence which S cannnot prove. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Stability of representations of effective partial algebras

An algebra is effective if its operations are computable under some numbering. When are two numberings of an effective partial algebra equivalent? For example, the computable real numbers form an effective field and two effective numberings of the field of computable reals are equivalent if the limit operator is assumed to be computable in the numberings (theorems of Moschovakis and Hertling). To answer the question for effective algebras in general, we give a general method based on an algebraic analysis of approximations by elements of a finitely generated subalgebra. Commonly, the computable elements of a topological partial algebra are derived from such a finitely generated algebra and form a countable effective partial algebra. We apply the general results about partial algebras to the recursive reals, ultrametric algebras constructed by inverse limits, and to metric algebras in general. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim