We examine several conditions, either the existence of a rank or a particular property of þ-forking that suggest the existence of a well-behaved independence relation, and determine the consequences of each of these conditions towards the rosiness of the theory. In particular we show that the existence of an ordinal valued equivalence relation rank is a (necessary and) sufficient condition for rosiness.

We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is wellknown that Ramsey's Theorem for pairs () splits into a stable version () and a cohesive principle (COH). We show that the same is true of ADS and CAC, and that in their cases the stable versions are strictly weaker than the full ones (which is not known to be the case for and ). We also analyze the relationships between these principles and other systems and principles previously studied by reverse mathematics, such as WKL0, DNR, and BΣ2. We show, for instance, that WKL0 is incomparable with all of the systems we study. We also prove computability-theoretic and conservation results for them. Among these results are a strengthening of the fact, proved by Cholak, Jockusch, and Slaman, that COH is -conservative over the base system RCA0. We also prove that CAC does not imply DNR which, combined with a recent result of Hirschfeldt, Jockusch. Kjos-Hanssen, Lempp, and Slaman, shows that CAC does not imply (and so does not imply ). This answers a question of Cholak, Jockusch, and Slaman.

Our proofs suggest that the essential distinction between ADS and CAC on the one hand and on the other is that the colorings needed for our analysis are in some way transitive. We formalize this intuition as the notions of transitive and semitransitive colorings and show that the existence of homogeneous sets for such colorings is equivalent to ADS and CAC, respectively. We finish with several open questions.

We consider successor-invariant first-order logic (FO + succ)inv, consisting of sentences Φ involving an “auxiliary” binary relation S such that (, S1) ⊨ Φ ⇔ (, S2) ⊨ Φ for all finite structures and successor relations S1, S2 on . A successor-invariant sentence Φ has a well-defined semantics on finite structures with no given successor relation: one simply evaluates Φ on (, S) for an arbitrary choice of successor relation S. In this article, we prove that (FO + succ)inv is more expressive on finite structures than first-order logic without a successor relation. This extends similar results for order-invariant logic [8] and epsilon-invariant logic [10].

We show that in the models of u < ∂ from [14] there are infinitely many near-coherence classes of ultrafilters, thus answering Banakh's and Blass' Question 30 of [3] negatively. By an unpublished result of Canjar, there are at least two classes in these models.

In [2] John Burgess describes predicative versions of Frege's logic and poses the problem of finding their exact arithmetical strength. I prove here that PV, the simplest such theory, is equivalent to Robinson's arithmetical theory Q.

We apply Hrushovski-Fraïsseé's amalgamation procedure to obtain a theory of fields of prime characteristic of Morley rank 2 equipped with a definable additive subgroup of rank 1.

We give an exponential lower bound on number of proof-lines in the proof system K of modal logic, i.e., we give an example of K-tautologies ψ1, ψ2, … s.t. every K-proof of ψi must have a number of proof-lines exponential in terms of the size of ψi. The result extends, for the same sequence of K-tautologies, to the systems K4, Gödel–Löb's logic, S andS4. We also determine some speed-up relations between different systems of modal logic on formulas of modal-depth one.

Asymptotic extremal combinatorics deals with questions that in the language of model theory can be re-stated as follows. For finite models M, N of an universal theory without constants and function symbols (like graphs, digraphs or hypergraphs), let p(M, N) be the probability that a randomly chosen sub-model of N with ∣M∣ elements is isomorphic to M. Which asymptotic relations exist between the quantities p(M1,N),…, p(Mh,N), where M1,…, M1, are fixed “template” models and ∣N∣ grows to infinity?

In this paper we develop a formal calculus that captures many standard arguments in the area, both previously known and apparently new. We give the first application of this formalism by presenting a new simple proof of a result by Fisher about the minimal possible density of triangles in a graph with given edge density.

In 1981, Takeuti introduced quantum set theory as the quantum counterpart of Boolean valued models of set theory by constructing a model of set theory based on quantum logic represented by the lattice of closed subspaces in a Hilbert space and showed that appropriate quantum counterparts of ZFC axioms hold in the model. Here, Takeuti's formulation is extended to construct a model of set theory based on the logic represented by the lattice of projections in an arbitrary von Neumann algebra. A transfer principle is established that enables us to transfer theorems of ZFC to their quantum counterparts holding in the model. The set of real numbers in the model is shown to be in one-to-one correspondence with the set of self-adjoint operators affiliated with the von Neumann algebra generated by the logic. Despite the difficulty pointed out by Takeuti that equality axioms do not generally hold in quantum set theory, it is shown that equality axioms hold for any real numbers in the model. It is also shown that any observational proposition in quantum mechanics can be represented by a corresponding statement for real numbers in the model with the truth value consistent with the standard formulation of quantum mechanics, and that the equality relation between two real numbers in the model is equivalent with the notion of perfect correlation between corresponding observables (self-adjoint operators) in quantum mechanics. The paper is concluded with some remarks on the relevance to quantum set theory of the choice of the implication connective in quantum logic.

We consider the notion of bounded m-ary patch-width defined in [9], and its very close relative m-constructibility defined below. We show that the notions of m-constructibility all coincide for m ≥ 3, while 1-constructibility is a weaker notion. The same holds for bounded m-ary patch-width. The case m = 2 is left open.

Let μ be singular of uncountable cofinality. If μ > 2cf(μ), we prove that in ℙ = ([μ]μ, ⊇) as a forcing notion we have a natural complete embedding of Levy(ℵ0, μ+) (so ℙ collapses μ+ to ℵ0) and even Levy (). The “natural” means that the forcing ({p ∈ [μ] : p closed}, ⊇) is naturally embedded and is equivalent to the Levy algebra. Also if ℙ fails the χ-c.c. then it collapses χ to ℵ0 (and the parallel results for the case μ > ℵ0 is regular or of countable cofinality). Moreover we prove: for regular uncountable κ, there is a family P of κ partitions Ā = ⟨Aα : α < κ⟩ of κ such that for any A ∈ [κ]κ for some ⟨Aα : α < κ⟩ ∈ P we have α < κ ⇒ ∣Aα ∩ A∣ = κ.

We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV1 + dWPHP(PV).

We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories and .

The paper gives a soundness and completeness proof for the implicative fragment of intuitionistic calculus with respect to the semantics of computability logic, which understands intuitionistic implication as interactive algorithmic reduction. This concept — more precisely, the associated concept of reducibility — is a generalization of Turing reducibility from the traditional, input/output sorts of problems to computational tasks of arbitrary degrees of interactivity.

The splitting theorem says that any set of formulae has a finest representation as a family of letter-disjoint sets. Parikh formulated this for classical propositional logic, proved it in the finite case, used it to formulate a criterion for relevance in belief change, and showed that AGM partial meet revision can fail the criterion. In this paper we make three further contributions. We begin by establishing a new version of the well-known interpolation theorem, which we call parallel interpolation, use it to prove the splitting theorem in the infinite case, and show how AGM belief change operations may be modified, if desired, so as to ensure satisfaction of Parikh's relevance criterion.

A new axiom is proposed, the Ground Axiom, asserting that the universe is not a nontrivial set forcing extension of any inner model. The Ground Axiom is first-order expressible, and any model of ZFC has a class forcing extension which satisfies it. The Ground Axiom is independent of many well-known set-theoretic assertions including the Generalized Continuum Hypothesis, the assertion V=HOD that every set is ordinal definable, and the existence of measurable and supercompact cardinals. The related Bedrock Axiom, asserting that the universe is a set forcing extension of a model satisfying the Ground Axiom, is also first-order expressible, and its negation is consistent.

We completely characterize the logical hierarchy of subsystems of open induction introduced by Boughattas [1].

We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable subsets of 2ω and Kolmogorov complexity play a major role in the proof.

It is proved that the (2p)-c. e. e-degrees are not elementarily equivalent to the (2p + 1)-c. e. e-degrees for each nonzero p ∈ ω. It follows that m-c. e. e-degrees are not elementarily equivalent to the n-c e. e-degrees if 1 <m < n.

We show, for any ordinal γ ≥ 3, that the class ℜaCAγ is pseudo-elementary and has a recursively enumerable elementary theory. ScK denotes the class of strong subalgebras of members of the class K. We devise games, Fn (3 ≤ n ≤ ω), G, H, and show, for an atomic relation algebra with countably many atoms, that

for 3 ≤ n < ω. We use these games to show, for γ > 5 and any class K of relation algebras satisfying

that K is not closed under subalgebras and is not elementary. For infinite γ, the inclusion ℜaCAγ ⊂ ScℜaCAγ is strict.

For infinite γ and for a countable relation algebra we show that has a complete representation if and only if is atomic and ∃ has a winning strategy in F (At()) if and only if is atomic and ∈ ScℜaCAγ.