We investigate the pair-splitting number which is a variation of splitting number, pair-reaping number which is a variation of reaping number and cardinal invariants of ideals on ω. We also study cardinal invariants of Fσ ideals and their upper bounds and lower bounds. As an application, we answer a question of S. Solecki by showing that the ideal of finitely chromatic graphs is not locally Katětov-minimal among ideals not satisfying Fatou's lemma.

Let = ⟨M, +, <, 0, S⟩ be a linear o-minimal expansion of an ordered group, and G = ⟨G, ⊕,eG ) an n-dimensional group definable in . We show that if G is definably connected with respect to the t-topology, then it is definably isomorphic to a definable quotient group U/L. for some convex ∨-definable subgroup U of ⟨Mn , +⟩ and a lattice L of rank equal to the dimension of the ‘compact part’ of G.

We construct a high c.e. degree which is not the join of two minimal degrees and so refute Posner's conjecture that every high c.e. degree is the join of two minimal degrees. Additionally, the proof shows that there is a high c.e. degree a such that for any splitting of a into degrees b and c one of these degrees bounds a 1-generic degree.

We provide a first order axiomatization of the expansion of the complex field by the exponential function restricted to the subring of integers modulo the first order theory of (Z, +, −).

We say a countable model has a 0-basis if the types realized in are uniformly computable. We say has a (d-)decidable copy if there exists a model ≅ such that the elementary diagram of is (d-)computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous model with a 0-basis but no decidable copy. We extend this result here. Let d ≤ 0′ be any low2 degree. We show that there exists a homogeneous model with a 0-basis but no d-decidable copy. A degree d is 0-basis homogeneous bounding if any homogenous with a 0-basis has a d-decidable copy. In previous work, we showed that the non low2 Δ20 degrees are 0-basis homogeneous bounding. The result of this paper shows that this is an exact characterization of the 0-basis homogeneous bounding Δ20 degrees.

Dp-minimality is a common generalization of weak minimality and weak o-minimality. If T is a weakly o-minimal theory then it is dp-minimal (Fact 2.2), but there are dp-minimal densely ordered groups that are not weakly o-minimal. We introduce the even more general notion of inp-minimality and prove that in an inp-minimal densely ordered group, every definable unary function is a union of finitely many continuous locally monotonic functions (Theorem 3.2).

For automatic and recursive graphs, we investigate the following problems:

(A) existence of a Hamiltonian path and existence of an infinite path in a tree

(B) existence of an Euler path, bounding the number of ends, and bounding the number of infinite branches in a tree

(C) existence of an infinite clique and an infinite version of set cover

The complexity of these problems is determined for automatic graphs and. supplementing results from the literature, for recursive graphs. Our results show that these problems

(A) are equally complex for automatic and for recursive graphs (-complete).

(B) are moderately less complex for automatic than for recursive graphs (complete for different levels of the arithmetic hierarchy),

(C) are much simpler for automatic than for recursive graphs (decidable and -complete, resp.).

We reformulate, in the context of continuous logic, an oscillation theorem proved by G. Hjorth and give a proof of the theorem in that setting which is similar to, but simpler than, Hjorth's original one. The point of view presented here clarifies the relation between Hjorth's theorem and first-order logic.

We establish the following results:

1. In ZF (i.e., Zermelo-Fraenkel set theory minus the Axiom of Choice AC), for every set I and for every ordinal number α ≥ ω, the following statements are equivalent:

(a) The Tychonoff product of ∣α∣ many non-empty finite discrete subsets of I is compact.

(b) The union of ∣α∣ many non-empty finite subsets of I is well orderable.

2. The statement: For every infinite set I, every closed subset of the Tychonoff product [0, 1]Iwhich consists offunctions with finite support is compact, is not provable in ZF set theory.

3. The statement: For every set I, the principle of dependent choices relativised to I implies the Tychonoff product of countably many non-empty finite discrete subsets of I is compact, is not provable in ZF0 (i.e., ZF minus the Axiom of Regularity).

4. The statement: For every set I, every ℵ0-sized family of non-empty finite subsets of I has a choice function implies the Tychonoff product of ℵ0many non-empty finite discrete subsets of I is compact, is not provable in ZF0.

Bounded lattices (that is lattices that are both lower bounded and upper bounded) form a large class of lattices that include all distributive lattices, many nondistributive finite lattices such as the pentagon lattice N5. and all lattices in any variety generated by a finite bounded lattice. Extending a theorem of Paris for distributive lattices, we prove that if L is an ℵ0-algebraic bounded lattice, then every countable nonstandard model of Peano Arithmetic has a cofinal elementary extension such that the interstructure lattice Lt(/) is isomorphic to L.

We present Woodin's proof that if there exists a measurable Woodin cardinal δ then there is a forcing extension satisfying all sentences ϕ such that CH + ϕ holds in a forcing extension of V by a partial order in Vδ. We also use some of the techniques from this proof to show that if there exists a stationary limit of stationary limits of Woodin cardinals, then in a homogeneous forcing extension there is an elementary embedding j: V → M with critical point such that M is countably closed in the forcing extension.

The undecidability of first-order logic implies that there is no computable bound on the length of shortest proofs of valid sentences of first-order logic. Some valid sentences can only have quite long proofs. How hard is it to prove such “hard” valid sentences? The polynomial time tractability of this problem would imply the fixed-parameter tractability of the parameterized problem that, given a natural number n in unary as input and a first-order sentence φ as parameter, asks whether φ has a proof of length ≤ n. As the underlying classical problem has been considered by Gödel we denote this problem by p-Gödel. We show that p-Gödel is not fixed-parameter tractable if DTIME(h O(1)) ≠ NTIME(h O(1)) for all time constructible and increasing functions h. Moreover we analyze the complexity of the construction problem associated with p-Gödel.

We construct a computable ℵ0-categorical structure whose first order theory is computably equivalent to the true first order theory of arithmetic.

We consider valued fields with a distinguished isometry or contractive derivation as valued modules over the Ore ring of difference operators. Under certain assumptions on the residue field, we prove quantifier elimination first in the pure module language, then in that language augmented with a chain of additive subgroups, and finally in a two-sorted language with a valuation map. We apply quantifier elimination to prove that these structures do not have the independence property.

We work in set-theory without choice ZF . A set is countable if it is finite or equipotent with ℕ. Given a closed subset F of [0, 1]I which is a bounded subset of ℓ 1(I) (resp. such that F ⊆ c 0(I)), we show that the countable axiom of choice for finite sets, (resp. the countable axiom of choice AC ℕ) implies that F is compact. This enhances previous results where AC ℕ (resp. the axiom of Dependent Choices) was required. If I is linearly orderable (for example I = ℝ), then, in ZF , the closed unit ball of the Hilbert space ℓ 2 (I) is (Loeb-)compact in the weak topology. However, the weak compactness of the closed unit ball of is not provable in ZF .

§1. Introduction. It is a well-known phenomenon in set theory that problems in infinite combinatorics involving singular cardinals and their successors tend to be harder than the parallel problems for regular cardinals. Examples include the behaviour of cardinal exponentiation, the extent of the tree property, the extent of stationary reflection, and the existence of non-free almost-free abelian groups. The explanation for this phenomenon lies in inner model theory, in particular core models and covering lemmas. If W is an inner model of V then

1. W strongly covers V if every uncountable set of ordinals is covered by a set of the same V -cardinality lying in W.

2. W weakly covers V if W computes the successor of every V-singular cardinal correctly.

Strong covering implies weak covering.

In inner model theory there are many theorems of the general form “if there is no inner model of large cardinal hypothesis X then there is an L-like inner model Kx which Y covers V”. Here the L-like properties of Kx always include GCH and Global Square. Examples include

1. X is “0# exists”, Kx is L, Y is “strongly”.

2. X is “there is a measurable cardinal”, Kx is the Dodd-Jensen core model, Y is “strongly”.

3. X is “there is a Woodin cardinal”, Kx is the core model for a Woodin cardinal, Y is “weakly”.

Let λ denote a singular cardinal. Zeman, improving a previous result of Shelah, proved that together with 2λ = λ+ implies ⋄S for every S ⊆ λ+ that reflects stationarily often.

In this paper, for a set S ⊆ λ+, a normal subideal of the weak approachability ideal is introduced, and denoted by I[S; λ]. We say that the ideal is fat if it contains a stationary set. It is proved:

1. if I[S; λ] is fat, then NSλ + ∣ S is non-saturated;

2. if I[S; λ] is fat and 2λ = λ+, then ⋄S holds;

3. implies that I[S; λ] is fat for every S ⊆ λ+ that reflects stationarily often;

4. it is relatively consistent with the existence of a supercompact cardinal that fails, while I[S; λ] is fat for every stationary S ⊆ λ+ that reflects stationarily often.

The stronger principle is studied as well.

We prove that if V = L then there is a maximal orthogonal (i.e., mutually singular) set of measures on Cantor space. This provides a natural counterpoint to the well-known theorem of Preiss and Rataj [16] that no analytic set of measures can be maximal orthogonal.

There exists a model in a countable language having a unique element which is not definable in .

Dans [2], Salma et Franz Viktor Kuhlmann définissent plu-sieurs notions d'espace vectoriel valué et démontrent un principe d'Ax-Kochen pour celles de ces structures dans lesquelles la multiplication par un scalaire du corps préserve la valuation. Nous travaillons ici avec des conditions plus faibles. On va définir en premier lieu la notion d'espace vectoriel valué sur un corps K, et associer canoniquement à un tel espace une valuation sur K, notée w, compatible en un sens à préciser avec celle de l'espace vectoriel. Ceci va nous permettre de parler de (K, w)-espaces vectoriels valués pour tout corps valué (K, w) (definition 24). Le cas où (K, w) est trivialement valué correspond exactement à la condition de [2] de préservation de la valuation par la multiplication par un scalaire. On fixe un corps K. Les espaces vectoriels valués sur le corps K vont être traités comme des structures à deux sortes: la sorte de l'espace vectoriel et celle de l'espace des valuations. Le langage LE de la sorte de l'espace vectoriel contient le symbole de la somme, celui de l'élément neutre, et un symbole de fonction unaire pour chaque scalaire de K. Le langage LV de l'espace des valuations contient une relation d'ordre total, un symbole de fonction unaire pour la multiplication par chaque scalaire de K, et pour tout n ∈ ℕ*, un symbole de prédicat Rn contrôlant la cardinalité résiduelle. LV contient aussi un symbole de fonction unaire s qui sera la fonction successeur quand elle est définie et l'identité sinon.