Let ℒ be a first-order language of cardinality κ++ with a distinguished unary predicate symbol U. In this paper we prove, working on L, the two cardinal transfer theorem (κ+,κ) ⇒ (κ++, κ+) for this language. This problem was posed by Chang and Keisler more than twenty years ago.

We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degrees f > e > d > 0 such that any degree u ≤ f is either comparable with both e and d, or incomparable with both.

Introduction. In 1937 E. Čech and M.H. Stone, independently, introduced the maximal compactification of a completely regular topological space, thereafter called Stone-Čech compactification [8, 23]. In the introduction of [8] the non-constructive character of this result is so described: “It must be emphasized that β(S) [the Stone-Čech compactification of S] may be defined only formally (not constructively) since it exists only in virtue of Zermelo's theorem”.

By replacing topological spaces with locales, Banaschewski and Mulvey [4, 5, 6], and Johnstone [14] obtained choice-free intuitionistic proofs of Stone-Čech compactification. Although valid in any topos, these localic constructions rely—essentially, as is to be demonstrated—on highly impredicative principles, and thus cannot be considered as constructive in the sense of the main systems for constructive mathematics, such as Martin-Löf's constructive type theory and Aczel's constructive set theory.

In [10] I characterized the locales of which the Stone-Čech compactification can be defined in constructive type theory CTT, and in the formal system CZF+uREA+DC, a natural extension of Aczel's system for constructive set theory CZF by a strengthening of the Regular Extension Axiom REA and the principle of Dependent Choice.

Shepherdson [14] showed that for a discrete ordered ring I, I is a model of I Open iff I is an integer part of a real closed ordered field. In this paper, we consider integer parts satisfyingPA. We show that if a real closed ordered fieldR has an integer part I that is a nonstandard model of PA (or even IΣ4), thenR must be recursively saturated. In particular, the real closure of I, RC (I), is recursively saturated. We also show that ifR is a countable recursively saturated real closed ordered field, then there is an integer part I such that R = RC(I) and I is a nonstandard model of PA.

In this paper, we continue the construction done in [3], so that under model-4-CA or 4-CA, given a bounded quadrangle C induced from a group configuration, we build a canonical hyperdefinable homogeneous space equivalent toC. When C is principal, we can choose the homogeneous space principal as well.

We generalize the model theory of small profinite structures developed by Newelski to the case of compact metric spaces considered together with compact groups of homeomorphisms and satisfying the existence of m-independent extensions (we call them compact e-structures). We analyze the relationships between smallness and different versions of the assumption of the existence of m-independent extensions and we obtain some topological consequences of these assumptions. Using them, we adopt Newelski's proofs of various results about small profinite structures to compact e-structures. In particular, we notice that a variant of the group configuration theorem holds in this context.

A general construction of compact structures is described. Using it, a class of examples of compact e-structures which are not small is constructed.

It is also noticed that in an m-stable compact e-structure every orbit is equidominant with a product of m-regular orbits.

We give several characterizations of weakly minimal abelian structures. In two special cases, dual in a sense to be made explicit below, we give precise structure theorems:

1. when the only finite 0-definable subgroup is {0}, or equivalently 0 is the only algebraic element (the co-strongly minimal case);

2. when the theory of the structure is strongly minimal.

In the first case, we identify the abelian structure as a “near-subspace” A of a vector space V over a division ring D with its induced structure, with possibly some collection of distinguished subgroups of A of finite index in A and (up to acl(∅)) no further structure. In the second, the structure is that of V/A for a vector space and near-subspace as above, with the only further possible structure some collection of distinguished points. Here a near-subspace of V is a subgroup A such that for any nonzero d ∈ D. the index of A ∩ dA, in A is finite. We also show that any weakly minimal abelian structure is a reduct of a weakly minimal module.

We prove quantifier elimination for the field ℚp((tℚ)) (the completion of the field of Puiseux series over ℚp) in Macintyre's language together with symbols for functions in a class containing both t-adically and p-adically overconvergent functions. We also show that the theory of ℚp((tℚ)) is b-minimal in this language.

As is well-known, the Bernays-Schönfinkel-Ramsey class of all prenex ∃*∀*-sentences which are valid in classical first-order logic is decidable. This paper paves the way to an analogous result which the authors deem to hold when the only available predicate symbols are ∈ and =, no constants or function symbols are present, and one moves inside a (rather generic) Set Theory whose axioms yield the well-foundedness of membership and the existence of infinite sets. Here semi-decidability of the satisfiability problem for the BSR class is proved by following a purely semantic approach, the remaining part of the decidability result being postponed to a forthcoming paper.

We show that if G is a strongly minimal finitely axiomatizable group, the division ring of quasi-endomorphisms of G must be an infinite finitely presented ring.

We prove that in a continuous ℵ0-stable theory every type-definable group is definable. The two main ingredients in the proof are:

(i) Results concerning Morley ranks (i.e., Cantor-Bendixson ranks) from [Ben08], allowing us to prove the theorem in case the metric is invariant under the group action; and

(ii) Results concerning the existence of translation-invariant definable metrics on type-definable groups and the extension of partial definable metrics to total ones.

We show that the free pseudospace is a reduct of a 1-based theory. This answers a question of David M. Evans. The theory is superstable, but not ω-stable.

The paper is aimed at studying the topological dimension for sets definable in weakly o-minimal structures in order to prepare background for further investigation of groups, group actions and fields definable in the weakly o-minimal context. We prove that the topological dimension of a set definable in a weakly o-minimal structure is invariant under definable injective maps, strengthening an analogous result from [2] for sets and functions definable in models of weakly o-minimal theories. We pay special attention to large subsets of Cartesian products of definable sets, showing that if X, Y and S are non-empty definable sets and S is a large subset of X × Y. then for a large set of tuples , where k = dim(Y), the union of fibers is large in Y. Finally, given a weakly o-minimal structure , we find various conditions equivalent to the fact that the topological dimension in enjoys the addition property.

There is a proper countable support iteration of length ω adding no new reals at finite stages and adding a Sacks real in the limit.

We examine fields in which model theoretic algebraic closure coincides with relative field theoretic algebraic closure. These are perfect fields with nice model theoretic behaviour. For example they are exactly the fields in which algebraic independence is an abstract independence relation in the sense of Kim and Pillay. Classes of examples are perfect PAC fields, model complete large fields and henselian valued fields of characteristic 0.

In this paper, we introduce the systems ns-ACA0 and ns-WKL0 of non-standard second-order arithmetic in which we can formalize non-standard arguments in ACA0 and WKL0, respectively. Then, we give direct transformations from non-standard proofs in ns-ACA0 or ns-WKL0 into proofs in ACA0 or WKL0.

A set A of vertices of a graph G is called d-scattered in G if no two d-neighborhoods of (distinct) vertices of A intersect. In other words, A is d-scattered if no two distinct vertices of A have distance at most 2d. This notion was isolated in the context of finite model theory by Ajtai and Gurevich and recently it played a prominent role in the study of homomorphism preservation theorems for special classes of structures (such as minor closed classes). This in turn led to the notions of wide, almost wide and quasi-wide classes of graphs. It has been proved previously that minor closed classes and classes of graphs with locally forbidden minors are examples of such classes and thus (relativized) homomorphism preservation theorem holds for them. In this paper we show that (more general) classes with bounded expansion and (newly defined) classes with bounded local expansion and even (very general) nowhere dense classes are quasi wide. This not only strictly generalizes the previous results but it also provides new proofs and algorithms for some of the old results. It appears that bounded expansion and nowhere dense classes are perhaps a proper setting for investigation of wide-type classes as in several instances we obtain a structural characterization. This also puts classes of bounded expansion in the new context. Our motivation stems from finite dualities. As a corollary we obtain that any homomorphism closed first order definable property restricted to a bounded expansion class is a restricted duality.

We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey. Griffiths and LaForte.

This paper presents a polarized phase semantics, with respect to which the linear fragment of second order polarized linear logic of Laurent [15] is complete. This is done by adding a topological structure to Girard's phase semantics [9], The topological structure results naturally from the categorical construction developed by Hamano–Scott [12]. The polarity shifting operator ↓ (resp. ↑) is interpreted as an interior (resp. closure) operator in such a manner that positive (resp. negative) formulas correspond to open (resp. closed) facts. By accommodating the exponentials of linear logic, our model is extended to the polarized fragment of the second order linear logic. Strong forms of completeness theorems are given to yield cut-eliminations for the both second order systems. As an application of our semantics, the first order conservativity of linear logic is studied over its polarized fragment of Laurent [16]. Using a counter model construction, the extension of this conservativity is shown to fail into the second order, whose solution is posed as an open problem in [16]. After this negative result, a second order conservativity theorem is proved for an eta expanded fragment of the second order linear logic, which fragment retains a focalized sequent property of [3].

We study the behaviour of stable types in rosy theories. The main technical result is that a non-þ-forking extension of an unstable type is unstable. We apply this to show that a rosy group with a þ-generic stable type is stable. In the context of super-rosy theories of finite rank we conclude that non-trivial stable types of Uþ-rank 1 must arise from definable stable sets.