Let n ≥ 3 be an integer. We show that it is consistent (relative to the consistency of n − 2 strong cardinals) that every Σ1n-set of reals is universally Baire yet there is a (lightface) projective well-ordering of the reals. The proof uses “David's trick” in the presence of inner models with strong cardinals.

The use of Nepomnjaščiǐ's Theorem in the proofs of independence results for bounded arithmetic theories is investigated. Using this result and similar ideas, it is shown that at least one of S1 or TLS does not prove the Matiyasevich-Robinson-Davis-Putnam Theorem. It is also established that TLS does not prove a statement that roughly means nondeterministic linear time is equal to co-nondeterministic linear time. Here S1 is a conservative extension of the well-studied theory IΔ0 and TLS is a theory for LOGSPACE reasoning.

We combine a variety of constructive methods (including forcing, realizability, asymmetric interpretation), to obtain consistency results concerning combinatory logic with extensionality and (forms of) the axiom of choice.

The theory of ranked partial structures allows a reinterpretation of several of the standard results of model theory and first-order logic and is intended to provide a proof-theoretic method which allows for the intuitions of model theory. A version of the downward Löwenheim-Skolem theorem is central to our development. In this paper we will present the basic theory of ranked partial structures and their logic including an appropriate version of the completeness theorem.

We generalize tools and results from first order stable theories to groups inside a simple stable strongly homogeneous model.

A classic result of Baumgartner-Harrington-Kleinberg [1] implies that assuming CH a stationary subset of ω1 has a CUB subset in a cardinal-perserving generic extension of V, via a forcing of cardinality ω1. Therefore, assuming that ω2L is countable: {X ∈ L ∣ X ⊆ ω1L and X has a CUB subset in a cardinal-preserving extension of L} is constructive, as it equals the set of constructible subsets of ω1L which in L are stationary. Is there a similar such result for subsets of ω2L? Building on work of M. Stanley [9], we show that there is not. We shall also consider a number of related problems, examining the extent to which they are “solvable” in the above sense, as well as denning a notion of reduction between them.

The theme of this paper is the generalization of theorems about partitions of the sets of points and lines of finite-dimensional Euclidean spaces ℝd to vector spaces over ℝ of arbitrary dimension and, more generally still, to arbitrary vector spaces over other fields so long as these fields are not too big. These theorems have their origins in the following striking theorem of Sierpiński [12] which appeared a half century ago.

Sierpiński's Theorem. The Continuum Hypothesis is equivalent to: There is a partition {X, Y, Z} of ℝ3such that if ℓ is a line parallel to the x-axis [respectively: y-axis, z-axis] then X ∩ ℓ [respectively: Y ∩ ℓ, Z ∩ ℓ] is finite.

The history of this theorem and some of its subsequent developments are discussed in the very interesting article by Simms [13]. Sierpiński's Theorem was generalized by Kuratowski [9] to partitions of ℝn+2 into n + 2 sets obtaining an equivalence with . The geometric character that Sierpiński's Theorem and its generalization by Kuratowski appear to have is bogus, since the lines parallel to coordinate axes are essentially combinatorial, rather than geometric, objects. The following version of Kuratowski's theorem emphasizes its combinatorial character.

Kuratowski's Theorem. Let n < ω and A be any set. Then ∣A∣ ≤ ℵnif and only if there is a partition P: An+2 → n + 2 such that if i ≤ n + 1 and ℓ is a line parallel to the i-th coordinate axis, then {x ∈ ℓ: P(x) = i} is finite.

We describe the Ax-Kochen definable subsets of the value group of a Hensel field and apply our results to a problem on identifying invariant factors in Hecke algebras.

We show that the ‘tail’ of a doubly homogeneous chain of countable cofinality can be recognized in the quotient of its automorphism group by the subgroup consisting of those elements whose support is bounded above. This extends the authors' earlier result establishing this for the rationals and reals. We deduce that any group is isomorphic to the outer automorphism group of some simple lattice-ordered group.

Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.

We consider combinatorial principles based on playing several two person games simultaneously. We call strategies for playing two or more games simultaneously parallel. The principles are easy consequences of the determinacy of games, in particular they are true for all finite games. We shall show that the principles fail for infinite games. The statements of these principles are of lower logical complexity than the sentence expressing the determinacy of games, therefore, they can be studied in weak axiomatic systems for arithmetic (Bounded Arithmetic). We pose several open problems about the provability of these statements in Bounded Arithmetic and related computational problems.

It is shown in ZF (without choice) that if there is a finite-to-one map (X) → X, then X is finite.

We answer a question of Just, Miller, Scheepers and Szeptycki whether certain diagonalization properties for sequences of open covers are provably closed under taking finite or countable unions.

Supplementing the well known results of Kunen we show that Martin's Axiom is not sufficient to decide the existence of (ω1, ϲ)-gaps when (ϲ, ϲ)-gaps exist, that is, it is consistent with ZFC that Martin's Axiom holds and there are (ϲ, ϲ)-gaps but no (ω1, ϲ)-gaps.

We give a direct, purely arithmetical and elementary proof of the strong normalization of the cut-elimination procedure for full (i.e., in presence of all the usual connectives) classical natural deduction.

We define a generic notion of cut that applies to many first-order theories. We prove a generic cut elimination theorem showing that the cut elimination property holds for all theories having a so-called pre-model. As a corollary, we retrieve cut elimination for several axiomatic theories, including Church's simple type theory.

Let be the class of atomic models of a countable first order theory. We prove that if is excellent and categorical in some uncountable cardinal, then each model is prime and minimal over the basis of a definable pregeometry given by a quasiminimal set. This implies that is categorical in all uncountable cardinals. We also introduce a U-rank to measure the complexity of complete types over models. We prove that the U-rank has the usual additivity properties, that quasiminimal types have U-rank 1, and that the U-rank of any type is finite in the uncountably categorical, excellent case. However, in contrast to the first order case, the supremum of the U-rank over all types may be ω (and is not achieved). We illustrate the theory with the example of free groups, and Zilber's pseudo analytic structures.

An ordering (≤K) on maximal almost disjoint (MAD) families closely related to destructibility of MAD families by forcing is introduced and studied. It is shown that the order has antichains of size c and decreasing chains of length c+ bellow every element. Assuming t = c a MAD family equivalent to all of its restrictions is constructed. It is also shown here that the Continuum Hypothesis implies that for every ωω-bounding forcing ℙ of size c there is a Cohen-destructible, ℙ-indestructible MAD family. Finally, two other orderings on MAD families are suggested and an old construction of Mrówka is revisited.

We show that g ≤ c(Sym(ω)) where g is the groupwise density number and c(Sym(ω)) is the cofinality of the infinite symmetric group. This solves (the second half of) a problem addressed by Thomas.

It is shown that the class of Kolmogorov-Loveland stochastic sequences is not closed under selecting subsequences by monotonic computable selection rules. This result gives a strong negative answer to the question whether the Kolmogorov-Loveland stochastic sequences are closed under selecting sequences by Kolmogorov-Loveland selection rules, i.e., by not necessarily monotonic, partial computable selection rules. The following previously known results are obtained as corollaries. The Mises-Wald-Church stochastic sequences are not closed under computable permutations, hence in particular they form a strict superclass of the class of Kolmogorov-Loveland stochastic sequences. The Kolmogorov-Loveland selection rules are not closed under composition.