In this article we provide wellordering proofs for metapredicative systems of explicit mathematics and admissible set theory featuring suitable axioms about the Mahloness of the underlying universe of discourse. In particular, it is shown that in the corresponding theories EMA of explicit mathematics and KPm0 of admissible set theory, transfinite induction along initial segments of the ordinal φω00, for φ being a ternary Veblen function, is derivable. This reveals that the upper bounds given for these two systems in the paper Jäger and Strahm [11] are indeed sharp.

An infinite binary sequence A is absolutely undecidable if it is impossible to compute A on a set of positions of positive upper density. Absolute undecidability is a weakening of bi-immunity. Downey, Jockusch and Schupp [2] asked whether, unlike the case for bi-immunity, there is an absolutely undecidable set in every non-zero Turing degree. We provide a positive answer to this question by applying techniques from coding theory. We show how to use Walsh–Hadamard codes to build a truth-table functional which maps any sequence A to a sequence B, such that given any restriction of B to a set of positive upper density, one can recover A. This implies that if A is non-computable, then B is absolutely undecidable. Using a forcing construction, we show that this result cannot be strengthened in any significant fashion.

We show that there are plenty of infinite sets that satisfy the omniscience principle, in a minimalistic setting for constructive mathematics that is compatible with classical mathematics. A first example of an omniscient set is the one-point compactification of the natural numbers, also known as the generic convergent sequence. We relate this to Grilliot's and Ishihara's Tricks. We generalize this example to many infinite subsets of the Cantor space. These subsets turn out to be ordinals in a constructive sense, with respect to the lexicographic order, satisfying both a well-foundedness condition with respect to decidable subsets, and transfinite induction restricted to decidable predicates. The use of simple types allows us to reach any ordinal below εQ, and richer type systems allow us to get higher.

By using some classical reasoning we show that any countably presented formal topology, namely, a formal topology with a countable axiom set, is spatial.

Although this problem is still open, there are a few related results concerning (i) theories equiconsistent with NF and (ii) consistent fragments of NF. Concerning (i) we will discuss the following results

(1) Specker's result about the equiconsistency of NF with an extension of the theory of types [16],

(2) the equiconsistency of NF with fragments of NF containing NFU [2], [10],

and a new one about

(3) the equiconsistency of NF with an extension of Zermelo's set theory with the axiom of comprehension restricted to bounded formulas.

Concerning (ii) we will give a simplified proof and a generalization of (4) Jensen's result about the consistency of NFU [13].

Only a few words will be devoted to

(5) Grishin's results and refinements [4], [5], [8], [9], treated with more details in [4].

The reader who is unfamiliar with NF or who has a natural repulsion for this system is first invited to read the excellent account contained in [7, Chapter III, §3].

Recent attempts to analyse or explicate assertion-statements and other kinds of indirect discourse in formal terms seem to have overlooked an even greater difficulty than the familiar problems arising about equivalence, synonymy, translatability, etc. This difficulty is created by the fact that in judicial, journalistic, or historical fact-finding, as well as in everyday conversation, we frequently cite statements about a witness's truthfulness alongside the report of his testimony as the premisses from which we argue about the facts. It is then an essential part of our argument that it should appear to jump from one level of statement to another, and perhaps back again. So that the difficulty emerges: how can the formalisation of such an argument adopt any of the usual hierarchy-principles as a guarantee against semantical antinomies?

Consider, for example,

We use a reverse Easton forcing iteration to obtain a universe with a definable well-order, while preserving the GCH and proper classes of a variety of very large cardinals. This is achieved by coding using the principle , at a proper class of cardinals κ. By choosing the cardinals at which coding occurs sufficiently sparsely, we are able to lift the embeddings witnessing the large cardinal properties without having to meet any non-trivial master conditions.

We characterize the bimodal provability logics for certain natural (classes of) pairs of recursively enumerable theories, mostly related to fragments of arithmetic. For example, we shall give axiomatizations, decision procedures, and introduce natural Kripke semantics for the provability logics of (IΔ0 + EXP, PRA); (PRA, IΣn); (IΣm, IΣn) for 1 ≤ m < n; (PA, ACA0); (ZFC, ZFC + CH); (ZFC, ZFC + ¬CH) etc. For the case of finitely axiomatized extensions of theories these results are extended to modal logics with propositional constants.

We show, relative to the base theory RCA0: A nontrivial tree satisfies Ramsey's Theorem only if it is biembeddable with the complete binary tree. There is a class of partial orderings for which Ramsey's Theorem for pairs is equivalent to ACA0. Ramsey's Theorem for singletons for the complete binary tree is stronger than . hence stronger than Ramsey's Theorem for singletons for ω. These results lead to extensions of results, or answers to questions, of Chubb, Hirst, and McNicholl [3].

The motivation for this paper is the following: In [4] I showed that it is inconsistent with ZFC that the Maximality Principle for directed closed forcings holds at unboundedly many regular cardinals κ (even only allowing κ itself as a parameter in the Maximality Principle for <κ-closed forcings each time). So the question is whether it is consistent to have this principle at unboundedly many regular cardinals or at every regular cardinal below some large cardinal κ (instead of ∞), and if so, how strong it is. It turns out that it is consistent in many cases, but the consistency strength is quite high.

If is a countable recursively saturated structure and T is a recursively axiomatizable theory that is consistent with Th(), then it is well known that can be expanded to a recursively saturated model of T [7, p. 186]. This is what has made recursively saturated models useful in model theory. Recursive saturation is the weakest notion of saturation for which this expandability result holds. In fact, if is a countable model of Pr = Th(ω, +), then can be expanded to a model of first order Peano arithmetic P just in case is recursively saturated (see [3]).

In this paper we investigate two natural sets of Turing degrees that tell a good deal about the expandability of a given structure. If is a recursively saturated structure, I() consists of the degrees of sets that are recursive in complete types realized in . The second set of degrees, D(), consists of the degrees of sets S such that is recursive in S-saturated. In general, I() ⊆ D(). Moreover, I() is obviously an “ideal” of degrees. For countable structures , D() is “closed” in the following sense: For any class C ⊆ 2ω, if C is co-r.e. in S for some set S such that , then there is some σ ∈ C such that . For uncountable structures , we do not know whether D() must be closed.

In this note we point out that two concepts which have been introduced separately into the theory of models are extensionally equivalent. The basic ideas can be expressed conveniently in the terminology of Tarski's theory of arithmetical classes. It will be recalled that an arithmetical class is a class consisting of all algebraic structures which satisfy some fixed sentence of the first-order functional calculus. A more general concept is that of a quasi-arithmetical class, whose elements are all algebraic structures which satisfy some fixed set of first-order sentences.

Now where H and K are any two classes of algebraic structures, Abraham Robinson has defined the relation H is persistent with respect to K to mean that (i) H∩K is non-empty, and (ii) whenever M ϵ H∩K, M′ is an extension of M, and M′ ϵ K, then M′ ϵ H. Concerning this notion Robinson has established the following theorem: If K is the class of abelian groups (or of commutative fields) and H is an arithmetical class which is persistent with respect to K, then H∩K contains a group (or field) which is finite. This leads us to the following definition.

In an earlier paper we proved that a universal Horn class generated by finitely many finite structures has a model companion. If the language has only finitely many fundamental operations then the theory of the model companion admits a primitive recursive elimination of quantifiers and is primitive recursive. The theory of the model companion is ℵ0-categorical iff it is complete iff the universal Horn class has the joint embedding property iff the universal Horn class is generated by a single finite structure. In the last section we look at structure theorems for the model companions of universal Horn classes generated by functionally complete algebras, in particular for the cases of rings and groups.

There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.

Let M be an o-minimal expansion of an ordered field. Let φ be a formula in the language of ordered domains. In this note we establish some topological properties which are transferred from φM to φR and vice versa. Then, we apply these transfer results to give a new proof of a result of M. Edmundo—based on the work of A. Strzebonski—showing the existence of torsion points in any definably compact group defined in an o-minimal expansion of an ordered field.

Bachmann, in [2] shows how certain ordinals <Ω(Ω = Ω1 where Ωξ is the (1 + ξ)th infinite initial ordinal) may be described from below using suitable descriptions of ordinals <Ω2. The aim of this paper is to consider another approach to describing ordinal <Ω and compare it with the Bachmann method. Our approach will use functionals of transfinite type based on Ω.

The Bachmann method consists in denning a hierarchy of normal functions ϕδ: Ω → Ω (i.e. continuous and strictly increasing) for δ ≤ η0 < Ω2, starting with ϕ0(λ) = ω1 + λ. The definition of depends on a suitable description of the ordinals ≤ η0. This is obtained by defining a hierarchy 〈Fδ ∣ δ ≤ Ω2〉 of normal functions Fδ: Ω2 → Ω2 analogously to the definition of the initial segment 〈ϕδ ∣ δ ≤ Ω〉 of . The ordinal η0 is .

Note. Our description of Bachmann's hierarchies will differ slightly from those in Bachmann's paper. Let and denote the hierarchies in [2]. Then as Bachmann's normal functions are not defined at 0 we let for λ, δ < Ω2. Bachmann defines for 0 < λ < Ω2 but it seems more natural to omit this so that we let . The situation is analogous for and leads to the following definitions:

where n < ω and ξ is a limit number of cofinality Ω, and

We extend the classical Feferman–Vaught theorem to logic for metric structures. This implies that the reduced powers of elementarily equivalent structures are elementarily equivalent, and therefore they are isomorphic under the Continuum Hypothesis. We also prove the existence of two separable C*-algebras of the form ⊕iMk(i) (ℂ) such that the assertion that their coronas are isomorphic is independent from ZFC, which gives the first example of genuinely noncommutative coronas of separable C*-algebras with this property.

The aim of this note is to determine whether certain non-o-minimal expansions of o-minimal theories which are known to be NIP, are also distal. We observe that while tame pairs of o-minimal structures and the real field with a discrete multiplicative subgroup have distal theories, dense pairs of o-minimal structures and related examples do not.

Much recent work in the theory of computational complexity ([Me], [FR]. [SI]) is concerned with establishing “the complexity” of various recursive functions, as measured by the time or space requirements of Turing machines which compute them. In the above work, we also observe another phenomenon: knowing the values of certain functions makes certain other functions easier to compute than they would be without this knowledge. We could say that the auxiliary functions “help” the computation of the other functions.

For example, we may conjecture that the “polynomial-complete” problems of Cook [C] and Karp [K] and Stockmeyer [S2], such as satisfiability of propositional formulas or 3-colorability of planar graphs, in fact require time proportional to nlog2n to be computed on a deterministic Turing machine. Then since the time required to decide if a planar graph with n nodes is 3-colorable can be lowered to a polynomial in n if we have a precomputed table of the satisfiable formulas in the propositional calculus, it is natural to say that the satisfiability problem “helps” the computation of the answers to the 3-coloring problem. Similar remarks may be made for any pair of polynomial-complete problems.

As a further illustration, Meyer and Stockmeyer [MS] have shown that, for a certain alphabet Σ, recognition of the set of regular expressions with squaring which are equivalent to Σ* requires Turing machine space cn for some constant c, on an infinite set of arguments. We also know that this set of regular expressions, which we call RSQ, may actually be recognized in space dn for some other constant d. Theorem 6.2 in [LMF] implies that there is some problem (not necessarily an interesting one) of complexity approximately equal to that of RSQ, which does not reduce the complexity of RSQ below cn . It does not “help” the computation of RSQ.

In [1] (p. 131 et seq) Professor A. N. Prior suggests a calculus of functions of propositions in which the range of the function variables is not restricted to truth functions.1 If f, g, … etc. represent such variables and we have quantification over all variables we can introduce propositional identity by definition as (ƒ)(ƒp ⊃ ƒq) Alternatively identity may be primitive with the usual axioms and schemata (v.e.g. [4] p. 190 et seq). We shall refer to such systems as ‘functorial calculi’2 (abbreviated as FC).