In the first part we show a counterexample to a conjecture by Shelah regarding the existence of indiscernible sequences in dependent theories (up to the first inaccessible cardinal). In the second part we discuss generic pairs, and give an example where the pair is not dependent. Then we define the notion of directionality which deals with counting the number of coheirs of a type and we give examples of the different possibilities. Then we discuss nonsplintering, an interesting notion that appears in the work of Rami Grossberg, Andrés Villaveces and Monica VanDieren, and we show that it is not trivial (in the sense that it can be different than splitting) whenever the directionality of the theory is not small. In the appendix we study dense types in RCF.

Inquisitive modal logic, InqML, is a generalisation of standard Kripke-style modal logic. In its epistemic incarnation, it extends standard epistemic logic to capture not just the information that agents have, but also the questions that they are interested in. Technically, InqML fits within the family of logics based on team semantics. From a model-theoretic perspective, it takes us a step in the direction of monadic second-order logic, as inquisitive modal operators involve quantification over sets of worlds. We introduce and investigate the natural notion of bisimulation equivalence in the setting of InqML. We compare the expressiveness of InqML and first-order logic in the context of relational structures with two sorts, one for worlds and one for information states, and characterise inquisitive modal logic as the bisimulation invariant fragment of first-order logic over various natural classes of two-sorted structures.

In the paper we introduce and study regular enumerations for arbitrary recursive ordinals. Several applications of the technique are presented.

Let S be the group of finitely supported permutations of a countably infinite set. Let $K[S]$ be the group algebra of S over a field K of characteristic 0. According to a theorem of Formanek and Lawrence, $K[S]$ satisfies the ascending chain condition for two-sided ideals. We study the reverse mathematics of this theorem, proving its equivalence over $RC{A_0}$ (or even over $RCA_0^{\rm{*}}$) to the statement that ${\omega ^\omega }$ is well ordered. Our equivalence proof proceeds via the statement that the Young diagrams form a well partial ordering.

We generalize a well-known theorem binding the elementary equivalence relation on the level of PAC fields and the isomorphism type of their absolute Galois groups. Our results concern two cases: saturated PAC structures and nonsaturated PAC structures.

We prove that for p-optimal fields (a very large subclass of p-minimal fields containing all the known examples) a cell decomposition theorem follows from methods going back to Denef’s paper [7]. We derive from it the existence of definable Skolem functions and strong p-minimality. Then we turn to strongly p-minimal fields satisfying the Extreme Value Property—a property which in particular holds in fields which are elementarily equivalent to a p-adic one. For such fields K, we prove that every definable subset of K × Kd whose fibers over K are inverse images by the valuation of subsets of the value group is semialgebraic. Combining the two we get a preparation theorem for definable functions on p-optimal fields satisfying the Extreme Value Property, from which it follows that infinite sets definable over such fields are in definable bijection iff they have the same dimension.

We modify the definable ultrapower construction of Kanovei and Shelah (2004) to develop a ZF-definable extension of the continuum with transfer provable using countable choice only, with an additional mild hypothesis on well-ordering implying properness. Under the same assumptions, we also prove the existence of a definable, proper elementary extension of the standard superstructure over the reals.

For any linear order type τ with first element let be the Boolean set algebra generated by the left-closed right-open (including [x, ∞)) intervals of some linear order of type τ. Let η and ω be the order types of the rationals and natural numbers respectively (when not used as an order type, ω will, as usual, be the set of nonnegative integers). We show that the Boolean algebra of the elementary theory of well-orders, i.e., the Boolean algebra of elementary classes of well-orders or, equivalently, the algebra of equivalence classes of sentences of the elementary theory of well-orders, is isomorphic to and that the Boolean algebra of the elementary theory of abelian groups is isomorphic to . Both results are obtained by applying Hanf's structure diagram technique to the work of Mostowski, Tarski, and Szmielew. One may formalize discussion of algebras of proper classes by assuming the classes are included in a universe which is a set in a larger universe.Given a Boolean algebra, let 0 be its zero and 1 its unit, let ≤ be its associated partial ordering, and, for any elements a, b, and c of the algebra, let “a + b = c ” be the assertion that c is the disjoint sum of a and b. A subset of the algebra disjointly generates the algebra iff each of the algebra's elements is a disjoint sum of a finite number of the subset's elements.

A coarse description of a set A ⊆ ω is a set D ⊆ ω such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1-genericity in place of weak 2-randomness. In the other direction, we show that if $A \le _{{\rm{T}}} \emptyset {\rm{'}}$ is a 1-random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set. We study both uniform and nonuniform notions of coarse reducibility. A set Y is uniformly coarsely reducible to X if there is a Turing functional Φ such that if D is a coarse description of X, then ΦD is a coarse description of Y. A set B is nonuniformly coarsely reducible to A if every coarse description of A computes a coarse description of B. We show that a certain natural embedding of the Turing degrees into the coarse degrees (both uniform and nonuniform) is not surjective. We also show that if two sets are mutually weakly 3-random, then their coarse degrees form a minimal pair, in both the uniform and nonuniform cases, but that the same is not true of every pair of relatively 2-random sets, at least in the nonuniform coarse degrees.

In this paper we study (self-)applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on = {0, 1}* are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory.

We consider separably closed fields of characteristic p > 0 and fixed imperfection degree as modules over a skew polynomial ring. We axiomatize the corresponding theory and we show that it is complete and that it admits quantifier elimination in the usual module language augmented with additive functions which are the analog of the p-component functions.

In this paper we investigate the structure of uncountable maximal antichains of Silver forcing and show that they have to be at least of size d, where d is the dominating number. Part of this work can be used to show that the additivity of the Silver forcing ideal has size at least the unbounding number b. It follows that every reasonable amoeba Silver forcing adds a dominating real.

For the terminology and motivation of this note, my earlier paper [3] should be consulted. Here I make a slight change by requiring the Intuitionist Propositional Logic H to be given in terms of axiom schemata rather than axioms.

Definition. An axiom schema F is essentially negative iff each schematic letter appearing in F is negated.

Thus the schemata (¬P ∨ ¬¬P), (¬¬(¬P ∨ ¬Q)→(¬P ∨ ¬Q)) are essentially negative, whereas (¬P ∨ P) and (¬¬P→P) are not.

Lemma. Let F be an essentially negative axiom schema. Then F yields at most finitely many intuitionistically nonequivalent axioms whose atoms are chosen from a fixed finite set.

Universal theories with model completions are characterized. A new omitting types theorem is proved. These two results are used to prove the existence of a universal ℵ0-categorical partial order with an interesting embedding property. Other aspects of these results also are considered.

We prove that cons(ZF) implies cons(ZF + Borel conjecture + there exists a Ramsey ultrafilter). We also prove some results on strong measure zero sets from the existence of generalized Luzin sets. We study the relationships between strong measure zero sets and rapid filters on ω.

In Gabbay [1] it is stated as an open problem whether or not Craig's Theorem holds for the logic of constant domains CD, i.e. for the extension of the intuitionistic predicate calculus, IPC, obtained by adding the schema; . Then in the later article, [2], Gabbay gives a proof of it. The proof given in [2] is via Robinson's (weak) consistency theorem and depends on relatively complicated (Kripke-) model-theoretical constructions developed in [1] (see p. 392 of [1] for a brief sketch of the method). The aim of this note is to show that the interpolation theorem for CD can also be obtained, by simple proof-theoretic methods, from §80 of Kleene's Introduction to Metamathematics [3].

GI is the classical formal system whose postulates are given on p. 442 of [3]. Let GD be the system obtained from GI by the following modifications: (1) the sequents of GD are to have at most two formulas in their succedents and (2) the intuitionistic restriction that Θ be empty is required for the succedent rules (→ ¬) and (→ ⊃). It is a simple matter to show that: , x not free in . It then follows that, using Theorem 46 of [3], if then .

The uniform halting problem (UH) can be stated as follows.

Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID).

An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky [3, p. 118]) we assume that in an ID the tape must be blank except for some finite numbers of squares. If we remove this restriction the UH becomes the immortality problem (IP). The UH should not be confused with the initialised uniform halting problem (whether or not a TM has an immortal ID when started in a specified state) which can easily be shown to be undecidable (see e.g. Minsky [3, p. 151]).

A seminal theorem due to Weyl [14] states that if (an) is any sequence of distinct integers, then, for almost every x ∈ ℝ, the sequence (anx) is uniformly distributed modulo one. In particular, for almost every x in the unit interval, the sequence (anx) is uniformly distributed modulo one for every computable sequence (an) of distinct integers. Call such an x UD random. Here it is shown that every Schnorr random real is UD random, but there are Kurtz random reals that are not UD random. On the other hand, Weyl's theorem still holds relative to a particular effectively closed null set, so there are UD random reals that are not Kurtz random.

A new method for blowing up the power of a singular cardinal is presented. It allows to blow up the power of a singular in the core model cardinal of uncountable cofinality. The method makes use of overlapping extenders.