Results in recursion-theoretic inductive inference have been criticized as depending on unrealistic self-referential examples. J. M. Bārzdiņš proposed a way of ruling out such examples, and conjectured that one of the earliest results of inductive inference theory would fall if his method were used. In this paper we refute Bārzdiņš' conjecture.

We propose a new line of research examining robust separations; these are defined using a strengthening of Bārzdiņš' original idea. The preliminary results of the new line of research are presented, and the most important open problem is stated as a conjecture. Finally, we discuss the extension of this work from function learning to formal language learning.

With all seven of ‘∼’, ‘⊃’, ‘&’, ‘ν’, ‘≡’, ‘∀’, and ‘∃’ understood to serve as primitive signs, let an expression of the sort

A1, A2, … , An → B1, B2, … , Bm,

where A1, A2, …, Aη (η≥ 0), B1, B2, …, and Bm (m > 0 if n = 0, otherwise m ≥ 0) are wffs of the first-order quantificational calculus (QC), count as an L-sequent of QC; let an L-sequent of QC of the sort

A1, A2, … , An → B

count as an N-sequent of QC;2 and let an L-sequent S of QC count as a Gentzen L-sequent of QC if no individual variable of QC occurs both bound and free in S.

We extend the usual language of second order arithmetic to one in which we can discuss an ultrafilter over of the sets of a given model. The semantics are based on fixing a subclass of the sets in a structure for the basic language that corresponds to the intended ultrafilter. In this language we state axioms that express the notion that the subclass is an ultrafilter and additional ones that say it is idempotent or Ramsey. The axioms for idempotent ultrafilters prove, for example, Hindman’s theorem and its generalizations such as the Galvin--Glazer theorem and iterated versions of these theorems (IHT and IGG). We prove that adding these axioms to IHT produce conservative extensions of ACA0 +IHT, ${\rm{ACA}}_{\rm{0}}^ +$, ATR0, ${\rm{\Pi }}_2^1$-CA0, and ${\rm{\Pi }}_2^1$-CA0 for all sentences of second order arithmetic and for full Z2 for the class of ${\rm{\Pi }}_4^1$ sentences. We also generalize and strengthen a metamathematical result of Wang (1984) to show, for example, that any ${\rm{\Pi }}_2^1$ theorem ∀X∃YΘ(X,Y) provable in ACA0 or ${\rm{ACA}}_{\rm{0}}^ +$ there are e,k ∈ ℕ such that ACA0 or ${\rm{ACA}}_{\rm{0}}^ +$ proves that ∀X(Θ(X, Φe(J(k)(X))) where Φe is the eth Turing reduction and J(k) is the kth iterate of the Turing or Arithmetic jump, respectively. (A similar result is derived for ${\rm{\Pi }}_3^1$ theorems of ${\rm{\Pi }}_1^1$-CA0 and the hyperjump.)

Meet semidistributive varieties are in a sense the last of the most important classes in universal algebra for which it is unknown whether it can be characterized by a strong Maltsev condition. We present a new, relatively simple Maltsev condition characterizing the meet-semidistributive varieties, and provide a candidate for a strong Maltsev condition.

A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$ , to find a solution relative to which A is still noncomputable.

In this article, we compare relativized versions of computability-theoretic notions of preservation which have been studied in reverse mathematics, and prove that the ones which were not already separated by natural statements in the literature actually coincide. In particular, we prove that it is equivalent to admit avoidance of one cone, of $\omega $ cones, of one hyperimmunity or of one non- $\Sigma ^{0}_1$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non- $\Sigma ^{0}_1$ definitions coincide. On the other hand, none of these notions coincide in a nonrelativized setting.

We introduce and study the framework of compact metric structures and their associated notions of isomorphisms such as homeomorphic and bi-Lipschitz isomorphism. This is subsequently applied to model various classification problems in analysis such as isomorphism of C*-algebras and affine homeomorphism of Choquet simplices, where among other things we provide a simple proof of the completeness of the isomorphism relation of separable, simple, nuclear C*-algebras recently established by M. Sabok.

We consider a weak version of Schindler’s remarkable cardinals that may fail to be ${{\rm{\Sigma }}_2}$-reflecting. We show that the ${{\rm{\Sigma }}_2}$-reflecting weakly remarkable cardinals are exactly the remarkable cardinals, and that the existence of a non-${{\rm{\Sigma }}_2}$-reflecting weakly remarkable cardinal has higher consistency strength: it is equiconsistent with the existence of an ω-Erdős cardinal. We give an application involving gVP, the generic Vopěnka principle defined by Bagaria, Gitman, and Schindler. Namely, we show that gVP + “Ord is not ${{\rm{\Delta }}_2}$-Mahlo” and ${\text{gVP}}(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{\Pi } _1 )$ + “there is no proper class of remarkable cardinals” are both equiconsistent with the existence of a proper class of ω-Erdős cardinals, extending results of Bagaria, Gitman, Hamkins, and Schindler.

We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π1(ℕ) + ¬Ω1 has a proper end-extension to a model of Π1(ℕ), and so Π1(ℕ) + ¬Ω ⊢ BΣ1. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π1(ℕ) + ¬Exp ⊢ BΣ1. Both assumptions can be modified to versions which make it possible to replace Π1(ℕ) by IΔ0 as the base theory.

We also show that any proof that IΔ0 + ¬Exp does not prove a given finite fragment of BΣ1 has to be “nonrelativizing”, in the sense that it will not work in the presence of an arbitrary oracle.

We consider the modality “ $\varphi $ is true in every $\sigma $ -centered forcing extension,” denoted $\square \varphi $ , and its dual “ $\varphi $ is true in some $\sigma $ -centered forcing extension,” denoted $\lozenge \varphi $ (where $\varphi $ is a statement in set theory), which give rise to the notion of a principle of $\sigma $ -centered forcing. We prove that if ZFC is consistent, then the modal logic of $\sigma $ -centered forcing, i.e., the ZFC-provable principles of $\sigma $ -centered forcing, is exactly $\mathsf {S4.2}$ . We also generalize this result to other related classes of forcing.

We establish a surprising connection between Menger's classical covering property and Blass-Laflamme's modern combinatorial notion of groupwise density. This connection implies a short proof of the groupwise density bound on the additivity number for Menger's property.

An r.e. degree a ≠ 0, 0′ is called strongly noncappable if it has no inf with any incomparable r.e. degree. We show the existence of a high strongly noncappable degree.

This paper continues the project initiated in [5]: a model-theoretic study of the concept of cardinality within certain higher-order logics. As recommended by an editor of this Journal, I will digress to say something about the project's motivation. Then I will review some of the basic definitions from [5]; for unexplained notation the reader should consult [5].

The syntax of ordinary usage (with respect to the construction of arguments as well as the construction of individual sentences) makes it natural to classify numerals and expressions of the form ‘the number of F's’ as singular terms, expressions like ‘is prime’ or ‘is divisible by’ as predicates of what Frege called “level one”, and expressions like ‘for some natural number’ as first-order quantifier-phrases. From this syntatic classification, it is a short step—so short as to be frequently unnoticed—to a semantic thesis: that such expressions play the same sort of semantic role as is played by the paradigmatic (and nonmathematical) members of these lexical classes. Thus expressions of the first sort are supposed to designate objects (in post-Fregean terms, entities of type 0), those of the second sort to be true or false of tuples of objects, and those of the third sort to quantify over objects. All this may be summed up in Frege's dictum: “Numbers are objects.”

An important program in the study of the structure the lattice of r.e. sets modulo finite sets, is the classification of the orbits under Aut(), the automorphism group of , If Φ ∈ Aut() and Φ(We) =* Wh(e) for all e ∈ ω, then h is called a presentation of Φ. Define Autχ() to be the class of those elements of Aut() that have a presentation in the class of functions X, where for instance X might be the class of Δn functions for n ∈ ω. If Φ ∈ Autx() then we will say that Φ is an X-automorphism. Note that we only need to consider Δn- and Πn-orbits and automorphisms since if f is a Σn-presentation, then f is a total function and therefore Δn.

Definition. If X is a class of functions and ⊆ {Wi: i < ω}, then is an X-orbit iff is an orbit under Aut() and for all A, B ∈ there is a Φ ∈ Autx() satisfying Φ(A) =* B. (Here Φ: → .)

Harrington proved that the creative sets form a Δ0-orbit and Soare proved that the maximal sets form Δ3-orbit. We will show that there is no Boolean algebra such that {A: A is r.e. and ℒ*(A) ≈ ] forms a Δ2-orbit, where ℒ*(A) is the principal filter of A in ; ℒ*(A) = {B: B ⊆* A & B ∈ }. The idea behind the proof of this theorem is very similar to the proof by Soare that maximal sets do not form a Δ2-orbit (see Soare [1974] or Soare [1987]).