A structure is an n-grid if each Ei, is an equivalence relation on A and whenever X and Y are equivalence classes of, respectively, distinct Ei, and Ej, then X ∩ Y is finite. A coloring χ: A → n is acceptable if whenever X is an equivalence class of Ei, then {x ∈ X: χ(x) = i} is finite. If B is any set, then the n-cube Bn = (Bn; E0, …, En−1) is considered as an n-grid, where the equivalence classes of Ei are the lines parallel to the i-th coordinate axis. Kuratowski [9], generalizing the n = 3 case proved by Sierpihski [17], proved that ℝn has an acceptable coloring iff 2ℵ0 ≤ ℵn−2. The main result is: if is a semialgebraic (i.e., first-order definable in the field of reals) n-grid, then the following are equivalent: (1) if embeds all finite n-cubes, then 2ℵ0 ≤ ℵn−2: (2) if embeds ℝn, then 2ℵ0 ≤ ℵn−2; (3) has an acceptable coloring.

A group is small if it has only countably many complete n-types over the empty set for each natural number n. More generally, a group G is weakly small if it has only countably many complete 1-types over every finite subset of G. We show here that in a weakly small group, subgroups which are definable with parameters lying in a finitely generated algebraic closure satisfy the descending chain conditions for their traces in any finitely generated algebraic closure. An infinite weakly small group has an infinite abelian subgroup, which may not be definable. A small nilpotent group is the central product of a definable divisible group with a definable one of bounded exponent. In a group with simple theory, any set of pairwise commuting elements is contained in a definable finite-by-abelian subgroup. First corollary: a weakly small group with simple theory has an infinite definable finite-by-abelian subgroup. Secondly, in a group with simple theory, a solvable group A of derived length n is contained in an A-definable almost solvable group of class at most 2n – 1.

In this paper we study with proof-theoretic methods the function(al)s provably recursive relative to Ramsey's theorem for pairs and the cohesive principle (COH).

Our main result on COH is that the type 2 functional provably recursive from are primitive recursive. This also provides a uniform method to extract bounds from proofs that use these principles. As a consequence we obtain a new proof of the fact that is -conservative over PRA.

Recent work of the first author showed that is equivalent to a weak variant of the Bolzano-Weierstraß principle. This makes it possible to use our results to analyze not only combinatorial but also analytical proofs.

For Ramsey's theorem for pairs and two colors we obtain the upper bounded that the type 2 functional provable recursive relative to are in T1. This is the fragment of Gödel's system T containing only type 1 recursion—roughly speaking it consists of functions of Ackermann type. With this we also obtain a uniform method for the extraction of T1-bounds from proofs that use . Moreover, this yields a new proof of the fact that is -conservative over .

The results are obtained in two steps: in the first step a term including Skolem functions for the above principles is extracted from a given proof. This is done using Gödel's functional interpretation. After this the term is normalized, such that only specific instances of the Skolem functions are used. In the second step this term is interpreted using -comprehension. The comprehension is then eliminated in favor of induction using either elimination of monotone Skolem functions (for COH) or Howard's ordinal analysis of bar recursion (for ).

If the Bounded Proper Forcing Axiom BPFA holds, then Mouse Reflection holds at ℵ2 with respect to all mouse operators up to the level of Woodin cardinals in the next ZFC-model. This yields that if Woodin's ℙmax axiom (*) holds, then BPFA implies that V is closed under the “Woodin-in-the-next-ZFC-model” operator. We also discuss stronger Mouse Reflection principles which we show to follow from strengthenings of BPFA, and we discuss the theory BPFA plus “NSω1 is precipitous” and strengthenings thereof. Along the way, we answer a question of Baumgartner and Taylor, [2, Question 6.11].

We show that the theory of the local structure of the enumeration degrees is computably isomorphic to the theory of first order arithmetic. We introduce a novel coding method, using the notion of a -pair, to code a large class of countable relations.

We consider the question of when an expansion of a first-order topological structure has the property that every open set definable in the expansion is definable in the original structure. This question has been investigated by Dolich, Miller and Steinhorn in the setting of ordered structures as part of their work on the property of having o-minimal open core. We answer the question in a fairly general setting and provide conditions which in practice are often easy to check. We give a further characterisation in the special case of an expansion by a generic predicate.

As proved recently, the satisfaction problem for all prenex formulae in the set-theoretic Bernays-Shönfinkel-Ramsey class is semi-decidable over von Neumann's cumulative hierarchy. Here that semi-decidability result is strengthened into a decidability result for the same collection of formulae.

In this paper, using definability of types over indiscernible sequences as a template, we study a property of formulas and theories called “uniform definability of types over finite sets” (UDTFS). We explore UDTFS and show how it relates to well-known properties in model theory. We recall that stable theories and weakly o-minimal theories have UDTFS and UDTFS implies dependence. We then show that all dp-minimal theories have UDTFS.

We shall show the consistency of CH+⌝(+) and CH+(+)+there are no club guessing sequences on ω1. We shall also prove that ◊+ does not imply the existence of a strong club guessing sequence on ω1.

We study definable irreducible actions of SL2 on an abelian group of Morley rank ≤ 3rk and prove they are rational representations of the group.

We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all equivalence relations on hyperarithmetical subsets of ω.

We work in , the untyped λ-calculus in which all unsolvables are identified. We resolve a conjecture of Barendregt asserting that the range of a definable map is either infinite or a singleton. This is refuted by constructing a λ-term Ξ such that ΞM = ΞI ⇔ ΞM ≠ ΞΩ. The construction generalizes to ranges of any finite size, and to some other sensible lambda theories.

In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.

In his book on ℙmax [7], Woodin presents a collection of partial orders whose extensions satisfy strong club guessing principles on ω1. In this paper we employ one of the techniques from this book to produce ℙmax variations which separate various club guessing principles. The principle (+) and its variants are weak guessing principles which were first considered by the second author [4] while studying games of length ω1. It was shown in [1] that the Continuum Hypothesis does not imply (+) and that (+) does not imply the existence of a club guessing sequence ω1. In this paper we give an alternate proof of the second of these results, using Woodin's ℙmax technology, showing that a strengthening of (+) does not imply a weakening of club guessing known as the Interval Hitting Principle. The main technique in this paper, in addition to the standard ℙmax machinery, is the use of condensation principles to build suitable iterations.

We show that given ω many supercompact cardinals, there is a generic extension in which the tree property holds at ℵω2+ 1 and the SCH fails at ℵω2.

We show that every splitting of in the local structure of the enumeration degrees, , contains at least one low-cuppable member. We apply this new structural property to show that the classes of all -pairs in , all downwards properly enumeration degrees and all upwards properly enumeration degrees are first order definable in .

We prove that a Kueker theory with infinite dcl(∅) does not have the strict order property and that strongly minimal types are dense: any non-algebraic formula is contained in a strongly minimal type.

The theory of valued difference fields (K, σ, υ,) depends on how the valuation υ interacts with the automorphism σ. Two special cases have already been worked out - the isometric case, where υ(σ(x)) = υ(x) for all x Є K, has been worked out by Luc Belair, Angus Macintyre and Thomas Scanlon; and the contractive case, where υ(σ(x)) > nυ(x) for all x Є K× with υ(x) > 0 and n Є ℕ, has been worked out by Salih Azgin. In this paper we deal with a more general version, the multiplicative case, where υ(σ(x)) = ρ · υ(x), where ρ (> 0) is interpreted as an element of a real-closed field. We give an axiomatization and prove a relative quantifier elimination theorem for this theory.

Dynamic Topological Logic () is a multimodal system for reasoning about dynamical systems. It is defined semantically and, as such, most of the work done in the field has been model-theoretic. In particular, the problem of finding a complete axiomatization for the full language of over the class of all dynamical systems has proven to be quite elusive.

Here we propose to enrich the language to include a polyadic topological modality, originally introduced by Dawar and Otto in a different context. We then provide a sound axiomatization for over this extended language, and prove that it is complete. The polyadic modality is used in an essential way in our proof.

A metric space (X, d) is monotone if there is a linear order < on X and a constant c such that d(x, y) ≤ c d(x, z) for all x < y < z in X. We investigate cardinal invariants of the σ-ideal Mon generated by monotone subsets of the plane. Since there is a strong connection between monotone sets in the plane and porous subsets of the line, plane and the Cantor set, cardinal invariants of these ideals are also investigated. In particular, we show that non(Mon) ≥ mσ-linked, but non(Mon) < mσ-centered is consistent. Also cov(Mon) < c and cof (N) < cov(Mon) are consistent.