We prove the undecidability of a very large class of restricted and unrestricted wreath products (Theorem 1.2), and of some skew fields of power series (Section2). Both undecidabilities are obtained by interpreting some enrichments of twisted wreath products, which are themselves proved to be undecidable (Proposition 1.1).

We consider division rings of power series in various languages:

We show (Theorem 2.8) that every power series division ring k((B)), whose field of constants k is commutative and whose ordered group of exponents is noncommutative with a convex center, is undecidable in every extension of the language of rings where the valuation and the ordered group B are definable.

For certain k and B we prove here the undecidability of the structure

where X↾k((B))xB is the restriction of the multiplication to k((B)) Χ B,and γ is a given conjugation of k((B)). This shows that we cannot hope to improve our previous result, a sort of Ax-Kochen-Ershov principle for power series division rings, which ensures that

is decidable for every decidable solvable B.

We define a generalized version of CM-triviality, and show that in the presence of enough regular types, or solubility, a stable CM-trivial group is nilpotent-by-finite. A torsion-free small CM-trivial stable group is abelian and connected. The first result makes use of a generalized version of the analysis of bad groups.

(Xα: α < ω2) ⊂ ℘(ω1) is a strong chain in ℘(ω1)/Fin if and only if Xβ – Xα is finite and Xα – Xβ is uncountable for each β < α < ω1. We show that it is consistent that a strong chain in ℘(ω1) exists. On the other hand we show that it is consistent that there is a strongly almost-disjoint family in ℘(ω1) but no strong chain exists: is used to construct a c.c.c forcing that adds a strong chain and Chang's Conjecture to prove that there is no strong chain.

Quine's “New Foundations” (NF) was first presented in Quine [10] and later on in Quine [11]. Ernst Specker [15, 13], building upon a previous result of Ehrenfeucht and Mostowski [5], showed that NF is consistent if and only if there is a model of the Theory of Negative (and positive) Types (TNT) with full extensionality that admits of a “shifting automorphism,” but the existence of such a model remains an open problem.

In his [8], Ronald Jensen gave a partial solution to the problem of the consistency of Quine's NF. Jensen considered a version of NF—referred to as NFU—in which the axiom of extensionality is weakened to allow for Urelemente or “atoms.” He showed, modifying Specker's theorem, that the existence of a model of TNT with atoms admitting of a “shifting automorphism” implies the consistency of NFU, proceeding then to exhibit such a model.

This paper presents a reduction of the consistency problem for NF to the existence of a model of TNT with atoms containing certain “large” (unstratified) sets and admitting a shifting automorphism. In particular we show that such a model can be “collapsed” to a model of pure TNT in such a way as to preserve the shifting automorphism. By the above-mentioned result of Specker's, this implies the consistency of NF.

Let us take the time to explain the main ideas behind the construction. Suppose we have a certain universe U of sets, built up from certain individuals or “atoms.” In such a universe we have only a weak version of the axiom of extensionality: two objects are the same if and only if they are both sets having the same members. We would like to obtain a universe U′ that is as close to U as possible, but in which there are no atoms (i.e., the only memberless object is the empty set). One way of doing this is to assign to each atom ξ, a set a (perhaps the empty set), inductively identifying sets that have members that we are already committed to considering “the same.” In doing this we obtain an equivalence relation ≃ over U that interacts nicely with the membership relation (provided we have accounted for multiplicity of members, i.e., we have allowed sets to contain “multiple copies” of the same object). Then we can take U′ = U/≃, the quotient of U with respect to ≃. It is then possible to define a “membership” relation over U′ in such a way as to have full extensionality. Relations such as ≃ are referred to as “contractions” by Hinnion and “bisimulations” by Aczel.

We generalize a result on True Arithmetic (ℐA) by Lachlan and Soare to certain other completions of Peano Arithmetic (PA). If ℐ is a completion of PA, then Rep(ℐ) denotes the family of sets X ⊆ ω for which there exists a formula φ(x) such that for all n ∈ ω, if n ∈ X, then ℐ ⊢ φ(S(n) (0)) and if n ∉ X, then ℐ ⊢ ┐φ(S(n)(O)). We show that if S, J ⊆ P(ω) such that S is a Scott set, J is a jump ideal, S ⊂ J and for all X ∈ J, there exists C ∈ S such that C is a “coding” set for the family of subtrees of 2<ω computable in X, and if ℐ is a completion of PA Such that Rep(ℐ) = S, then there exists a model A of ℐ such that J is the Scott set of A and no enumeration of Rep(ℐ) is computable in A. The model A of ℐ is obtained via a new notion of forcing.

Before proving our main result, we demonstrate the existence of uncountably many different pairs (S, J) satisfying the conditions of our theorem. This involves a new characterization of 1-generic sets as coding sets for the computable subtrees of 2<ω. In particular, C C ⊆ ω is a coding set for the family of subtrees of 2<ω computable in X if and only if for all trees T ⊆ 2<ω computable in X, if χc is a path through T, then there exists σ ∈ T such that σ ⊂ χc and every extension of σ is in T. Jockusch noted a connection between 1-generic sets and coding sets for computable subtrees of 2<ω. We show they are identical.

A mapping u: X → Y between metric spaces is sequentially continuous if for each sequence (xn) converging to x ∈ X, (u(xn)) converges to u(x). It is well known in classical mathematics that a sequentially continuous mapping between metric spaces is continuous; but, as all proofs of this result involve the law of excluded middle, there appears to be a constructive distinction between sequential continuity and continuity. Although this distinction is worth exploring in its own right, there is another reason why sequential continuity is interesting to the constructive mathematician: Ishihara [8] has a version of Banach's inverse mapping theorem in functional analysis that involves the sequential continuity, rather than continuity, of the linear mappings; if this result could be upgraded by deleting the word “sequential”, then we could prove constructively the standard versions of the inverse mapping theorem and the closed graph theorem.

Troelstra [9] showed that in Brouwer's intuitionistic mathematics (INT) a sequentially continuous mapping on a separable metric space is continuous. On the other hand, Ishihara [6, 7] proved constructively that the continuity of sequentially continuous mappings on a separable metric space is equivalent to a certain boundedness principle for subsets of ℕ; in the same paper, he showed that the latter principle holds within the recursive constructive mathematics (RUSS) of the Markov School. Since it is not known whether that principle holds within Bishop's constructive mathematics (BISH), of which INT and RUSS are models and which can be regarded as the constructive core of mathematics, the exploration of sequential continuity within BISH holds some interest.

Applying Woodin's non-stationary tower notion of forcing, I prove that the existence of a supercompact cardinal κ in V and a Ramsey dilator in some small forcing extension V[G] implies the existence in V of a measurable dilator of size κ, measurable by κ-complete measures.

We study partitions of Fraïssé limits of classes of finite relational structures where the partitions are encoded by infinite binary strings which are random in the sense of Kolmogorov-Chaitin.

The main result of this paper is Theorem 3.1 which is a criterion for weak o-minimality of a linearly ordered structure in terms of realizations of 1-types. Here we also prove some other properties of weakly o-minimal structures. In particular, we characterize all weakly o-minimal linear orderings in the signature {<, =} . Moreover, we present a criterion for density of isolated types of a weakly o-minimal theory. Lastly, at the end of the paper we present some remarks on the Exchange Principle for algebraic closure in a weakly o-minimal structure.

We discuss the finite-to-one Rudin-Keisler ordering of ultrafilters on the natural numbers, which we baptize the Rudin-Blass ordering in honour of Professor Andreas Blass who worked extensively in the area.

We develop and summarize many of its properties in relation to its bounding and dominating numbers, directedness, and provide applications to continuum theory. In particular, we prove in ZFC alone that there exists an ultrafilter with no Q-point below in the Rudin-Blass ordering.

Henson and Ross [1] answered the question of when two hyperfinite sets A, B in an ℵ1-saturated nonstandard universe are bijective by a Borel function: precisely when ∣A∣/∣B∣ ≈ 1. Živaljević [5] generalized this result to nonvanishing Borel sets. He defined a set to be nonvanishing if it is Loeb-measurable and has finite, non-zero measure with respect to some Loeb counting measure. He then showed that two nonvanishing Borel sets are Borel bijective just in case they have the same finite, non-zero measure with respect to some Loeb counting measure.

Here we shall complete the cycle, for Borel sets at least. For N ∈ *N, let λN be the internal counting measure given by λN(A) = ∣A∣/N for A internal. Then for vanishing Loeb-measurable sets B, it is natural to consider the Dedekind cut (BL, BR) on *N consisting of those N for which B has 0λN-measure infinity and zero, respectively. We show that, for all vanishing Borel sets B, B and BL are Borel bijective. It follows that vanishing Borel sets B and C are Borel bijective if, and only if, BL = CL. Combined with Živaljević's result, we can characterize when arbitrary Borel sets are Borel bijective: precisely when they have the same measure with respect to all Loeb counting measures.

In the final section, we generalize in a similar way results of [2] and [5] to characterize when two Borel sets are bijective by a countably determined function: precisely when, for all N, one has 0λN-measure 0 if and only if the other also has 0λN-measure 0.

We study the monadic fragment of second order intuitionistic propositional logic in the language containing the standard propositional connectives and propositional quantifiers. It is proved that under the topological interpretation over any dense-in-itself metric space, the considered fragment collapses to Heyting calculus. Moreover, we prove that the topological interpretation over any dense-in-itself metric space of fragment in question coincides with the so-called Pitts' interpretation. We also prove that all the nonstandard propositional operators of the form q ↦ ∃p (q ↔ F(p)), where F is an arbitrary monadic formula of the variable p, are definable in the language of Heyting calculus under the topological interpretation of intuitionistic logic over sufficiently regular spaces.

We investigate the possibility to characterize (multi)functions that are -definable with small i (i = 1, 2, 3) in fragments of bounded arithmetic T2 in terms of natural search problems defined over polynomial-time structures. We obtain the following results:

(1) A reformulation of known characterizations of (multi)functions that are and -definable in the theories and .

(2) New characterizations of (multi)functions that are and -definable in the theory .

(3) A new non-conservation result: the theory is not -conservative over the theory .

To prove that the theory is not -conservative over the theory , we present two examples of a -principle separating the two theories:

(a) the weak pigeonhole principle WPHP(a2, f, g) formalizing that no function f is a bijection between a2 and a with the inverse g,

(b) the iteration principle Iter(a, R, f) formalizing that no function f defined on a strict partial order ({0,…, a}, R) can have increasing iterates.

Our goal in this paper is to analyze the interpretation of arbitrary unsolvable λ-terms in a given model of λ-calculus. We focus on graph models and (a special type of) stable models. We introduce the syntactical notion of a decoration and the semantical notion of a critical sequence. We conjecture that any unsolvable term β-reduces to a term admitting a decoration. The main result of this paper concerns the interconnection between those two notions: given a graph model or stable model , we show that any unsolvable term admitting a decoration and having a non-empty interpretation in generates a critical sequence in the model.

In the last section, we examine three classical graph models, namely the model of Plotkin and Scott, Engeler's model and Park's model . We show that and do not contain critical sequences whereas does.

We show: The procedure mentioned in the title is often impossible. It requires at least an inner model with a measurable cardinal. The consistency strength of changing and from a regular κ to some regular δ < κ is a measurable of Mitchell order δ. There is an application to Cichoń's diagram.

We prove that every rectangularly dense diagonal-free cylindric algebra is representable. As a corollary, we give finite, sound and complete axiomatizations for the finite-variable fragments of first order logic without equality and for multi-dimensional modal S5-logic.

We present a possible computational content of the negative translation of classical analysis with the Axiom of (countable) Choice. Interestingly, this interpretation uses a refinement of the realizability semantics of the absurdity proposition, which is not interpreted as the empty type here. We also show how to compute witnesses from proofs in classical analysis of ∃-statements and how to extract algorithms from proofs of ∀∃-statements. Our interpretation seems computationally more direct than the one based on Gödel's Dialectica interpretation.

We prove the following theorems:

(1) If X has strong measure zero and if Y has strong first category, then their algebraic sum has property S0.

(2) If X has Hurewicz's covering property, then it has strong measure zero if, and only if, its algebraic sum with any first category set is a first category set.

(3) If X has strong measure zero and Hurewicz's covering property then its algebraic sum with any set in is a set in . ( is included in the class of sets always of first category, and includes the class of strong first category sets.)

These results extend: Fremlin and Miller's theorem that strong measure zero sets having Hurewicz's property have Rothberger's property, Galvin and Miller's theorem that the algebraic sum of a set with the γ-property and of a first category set is a first category set, and Bartoszyfński and Judah's characterization of -sets. They also characterize the property (*) introduced by Gerlits and Nagy in terms of older concepts.

Large cardinals arising from the existence of arbitrarily long end elementary extension chains over models of set theory are studied here. In particular, we show that the large cardinals obtained in this fashion (‘unfoldable cardinals’) lie in the boundary of the propositions consistent with ‘V = L’ and the existence of 0#. We also provide an ‘embedding characterisation’ of the unfoldable cardinals and study their preservation and destruction by various forcing constructions.