In this paper we introduce a new property of families of functions on the Baire space, called pseudo-dominating, and apply the properties of these families to the study of cardinal characteristics of the continuum. We show that the minimum cardinality of a pseudo-dominating family is min {τ, ∂}. We derive two corollaries from the proof: τ ≥ min{∂, u} and min{∂, τ} = min{∂, τσ}. We show that if a dominating family is partitioned into fewer that s pieces, then one of the pieces is pseudo-dominating. We finally show that u < g implies that every unbounded family of functions is pseudo-dominating, and that the Filter Dichotomy principle is equivalent to every unbounded family of functions being finitely pseudo-dominating.

We explore some topics in the model theory of sheaves of modules. First we describe the formal language that we use. Then we present some examples of sheaves obtained from quivers. These, and other examples, will serve as illustrations and as counterexamples. Then we investigate the notion of strong minimality from model theory to see what it means in this context. We also look briefly at the relation between global, local and pointwise versions of properties related to acyclicity.

We examine the question of how many Boolean algebras, distinct up to isomorphism, that are quotients of the powerset of the naturals by Borel ideals, can be proved to exist in ZFC alone. The maximum possible value is easily seen to be the cardinality of the continuum ; earlier work by Ilijas Farah had shown that this was the value in models of Martin's Maximum or some similar forcing axiom, but it was open whether there could be fewer in models of the Continuum Hypothesis.

We develop and apply a new technique for constructing many ideals whose quotients must be nonisomorphic in any model of ZFC. The technique depends on isolating a kind of ideal, called shallow, that can be distinguished from the ideal of all finite sets even after any isomorphic embedding, and then piecing together various copies of the ideal of all finite sets using distinct shallow ideals. In this way we are able to demonstrate that there are continuum-many distinct quotients by Borel ideals, indeed by analytic P-ideals, and in fact that there is in an appropriate sense a Borel embedding of the Vitali equivalence relation into the equivalence relation of isomorphism of quotients by analytic P-ideals. We also show that there is an uncountable definable wellordered collection of Borel ideals with distinct quotients.

A family A ⊆ (ω) is called countably splitting if for every countable F ⊆ [ω]ω, some element of A splits every member of F. We define a notion of a splitting tree, by means of which we prove that every analytic countably splitting family contains a closed countably splitting family. An application of this notion solves a problem of Blass. On the other hand we show that there exists an Fσ splitting family that does not contain a closed splitting family.

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].

We introduce an operation existsn (S) on properties S that says “there are n components having S”. We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.

We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.

We introduce another operation alt(S) on properties which has the same relationship with the Circuit Value Problem as reach(S) (defined in [JM01]) has with the Directed Reachability Problem. We use alt(S) to show that Πn ⊈ FO(Σn), Σn ⊈ FO(∆n). and ∆n+1 ⊈ FOB(Σn), solving some open problems raised in [Mat98].

We interpret the algebra of finite rank operators as imaginaries inside a Hilbert space. We prove that the Hilbert space enlarged with these imaginaries has built-in canonical bases.

A relation on a linearly ordered structure is called semi-bounded if it is definable in an expansion of the structure by bounded relations. We study ultimate behavior of semi-bounded relations in an ordered module M over an ordered commutative ring R such that M/rM is finite for all nonzero r ϵ R. We consider M as a structure in the language of ordered R-modules augmented by relation symbols for the submodules rM, and prove several quantifier elimination results for semi-bounded relations and functions in M. We show that these quantifier elimination results essentially characterize the ordered modules M with finite indices of the submodules rM. It is proven that (1) any semi-bounded k-ary relation on M is equal, outside a finite union of k-strips, to a k-ary relation quantifier-free definable in M, (2) any semibounded function from Mk to M is equal, outside a finite union of k-strips, to a piecewise linear function, and (3) any semi-bounded in M endomorphism of the additive group of M is of the form x ↦ σx, for some σ from the field of fractions of R.

We show that if d ∈ GH1 then (≤ d) has the complementation property, i.e., for all a < d there is some b < d such that a ∧ b = 0 and a ∨ b = d.

The purpose of this paper is to establish some basic points in the model theory of comodules over a coalgebra. It is not even immediately apparent that there is a model theory of comodules since these are not structures in the usual sense of model theory. Let us give the definitions right away so that the reader can see what we mean.

Fix a field k. A k-coalgebra C is a k-vector space equipped with a k-linear map Δ: C → C ⊗ C, called the comultiplication (by ⊗ we always mean tensor product over k), and a k-linear map ε: C → k, called the counit, such that Δ⊗1C = 1C ⊗ Δ (coassociativity) and (1C ⊗ ε)Δ = 1C = (ε ⊗ 1C)Δ, where we identify C with both k ⊗ C and C ⊗ k. These definitions are literally the duals of those for a k-algebra: express the axioms for C′ to be a k-algebra in terms of the multiplication map μ: C′ ⊗ C′ → C′ and the “unit” (embedding of k into C′), δ: k → C′ in the form that certain diagrams commute and then just turn round all the arrows. See [5] or more recent references such as [7] for more.

For a stationary set S ⊆ ω1, and a ladder system C over S, a new type of gaps called C-Hausdorff is introduced and investigated. We describe a forcing model of ZFC in which, for some stationary set S, for every ladder C over S, every gap contains a subgap that is C-Hausdorff. But for every ladder E over ω1 ∖ S there exists a gap with no subgap that is E-Hausdorff.

A new type of chain condition, called polarized chain condition, is introduced. We prove that the iteration with finite support of polarized c.c.c. posets is again a polarized c.c.c. poset.

In a simple theory with elimination of finitary hyperimaginaries if tp(a) is real and analysable over a definable set Q, then there exists a finite sequence (ai \ i ≤ n*) ⊆ dcleq(a) with an* = a such that for every i ≤ n* if pi = tp(ai/{aj |j < i}) then Aut(pi / Q) is type-definable with its action on . A unidimensional simple theory eliminates the quantifier ∃∞ and either interprets (in Ceq) an infinite type-definable group or has the property that ACL(Q) = C for every infinite definable set Q.

In this paper, we prove the wellfoundedrtess of recursive notation systems for reflecting ordinals up to Π3-reflection by relevant inductive definitions.

Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-Löf random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of “Schnorr reducibility” which allows us to calibrate the Schnorr complexity of reals. We define the class of “Schnorr trivial” reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members.

We prove that a computably enumerable set A is effectively speedable (effectively levelable) if and only if there exists a splitting (A0, A1) of A such that both A0 and A1 are effectively speedable (effectively levelable). These results answer two questions raised by J. B. Remmel.

Let be an o-minimal expansion of the ordered field of real numbers , and let S be an -definable subset (parameters allowed unless otherwise stated) of ℝn. In this note I investigate questions concerning the distribution of points on S with integer coordinates. My main theorem gives an estimate which, though probably far from best possible, at least shows that the o-minimal assumption does have diophantine consequences. This is, perhaps, surprising in view of the flexibility that we now seem to have in constructing o-minimal expansions of (see, e. g. [7], [8], [9]).

We study the expansion of stable structures by adding predicates for arbitrary subsets. Generalizing work of Poizat-Bouscaren on the one hand and Baldwin-Benedikt-Casanovas-Ziegler on the other we provide a sufficient condition (Theorem 4.7) for such an expansion to be stable. This generalization weakens the original definitions in two ways: dealing with arbitrary subsets rather than just submodels and removing the ‘small’ or ‘belles paires’ hypothesis. We use this generalization to characterize in terms of pairs, the ‘triviality’ of the geometry on a strongly minimal set (Theorem 2.5). Call a set A benign if any type over A in the expanded language is determined by its restriction to the base language. We characterize the notion of benign as a kind of local homogenity (Theorem 1.7). Answering a question of [8] we characterize the property that M has the finite cover property over A (Theorem 3.9).

The authors show, by means of a finitary version of the combinatorial principle of [7]. the consistency of the failure, relative to the consistency of supercompact cardinals, of the following: for all regular filters D on a cardinal λ. if Mi and Ni are elementarily equivalent models of a language of size ≤ λ, then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ+ on ΠiMi/D and ΠiNi/D. If in addition 2λ = λ+ and i < λ implies |Mi| + |Ni| ≤ λ+ this means that the ultrapowers are isomorphic. This settles negatively conjecture 18 in [2].

We prove, in ZFC, the existence of a definable, countably saturated elementary extension of the reals.

We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard notion from computable analysis. However, no satisfactory theory of degrees of continuous functions exists. We introduce the continuous degrees and prove that they are a proper extension of the Turing degrees and a proper substructure of the enumeration degrees. Call continuous degrees which are not Turing degrees non-total. Several fundamental results are proved: a continuous function with non-total degree has no least degree representation, settling a question asked by Pour-El and Lempp; every non-computable f ∈ [0,1] computes a non-computable subset of ℕ there is a non-total degree between Turing degrees a <Tb iff b is a PA degree relative to a; ⊆ 2ℕ is a Scott set iff it is the collection of f-computable subsets of ℕ for some f ∈ [0,1] of non-total degree; and there are computably incomparable f, g ∈ [0,1] which compute exactly the same subsets of ℕ. Proofs draw from classical analysis and constructive analysis as well as from computability theory.

We present a comparatively simple way to construct Martin-Löf random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of Gács and Kučera, for any given set X we construct a Martin-Löf random set from which X can be decoded effectively.

By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-Löf random sets that are computably enumerable self-reducible. The two latter results complement the known facts that no rec-random set is truth-table autoreducible and that no Martin-Löf random set is Turing-autoreducible [8, 24].