We develop the theory of partial satisfaction relations for structures that may be proper classes and define a satisfaction predicate (⊨*) appropriate to such structures. We indicate the utility of this theory as a framework for the development of the metatheory of first-order predicate logic and set theory, and we use it to prove that for any recursively enumerable extension Θ of ZF there is a finitely axiomatizable extension *Θ′ of GB that is a conservative extension of Θ. We also prove a conservative extension result that justifies the use of ⊨* to characterize ground models for forcing constructions.

Given a theory T extending that of dense linear orders without endpoints (DLO), in a language ℒ ⊇ {<}, we are interested in extensions T′ of T in languages extending ℒ by unary relation symbols that are each interpreted in models of T′ as sets that are both dense and codense in the underlying sets of the models.

There is a canonically “wild” example, namely T = Th(〈ℝ, <, +, ·〉) and T′ = Th(〈ℝ, <, +, · ℚ 〉). Recall that T is o-minimal, and so every open set definable in any model of T has only finitely many definably connected components. But it is well known that 〈ℝ, <, +, · ℚ 〉 defines every real Borel set, in particular, every open subset of any finite cartesian power of ℝ and every subset of any finite cartesian power of ℚ. To put this another way, the definable open sets in models of T are essentially as simple as possible, while T′ has a model where the definable open sets are as complicated as possible, as is the structure induced on the new predicate.

In contrast to the preceding example, if ℝalg is the set of real algebraic numbers and T′ Th(〈ℝ, <, +, ·, 〈alg〉), then no model of T′ defines any open set (of any arity) that is not definable in the underlying model of T.

Justification logics are modal logics that include justifications for the agent's knowledge. So far, there are no decidability results available for justification logics with negative introspection. In this paper, we develop a novel model construction for such logics and show that justification logics with negative introspection are decidable for finite constant specifications.

We work under the assumption of the Axiom of Determinacy and associate a measure to each cardinal κ < ℵ ε0 in a recursive definition of a canonical measure assignment. We give algorithmic applications of the existence of such a canonical measure assignment (computation of cofinalities, computation of the Kleinberg sequences associated to the normal ultrafilters on all projective ordinals).

Assuming that 0# exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure such that

where is the set of Turing degrees which compute a copy of

More interesting than the result itself is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full “nth-order arithmetic for all n, cannot prove the existence of such a structure.

It is shown that the power set of κ ordered by the subset relation modulo various versions of the non-stationary ideal can be embedded into the partial order of Borel equivalence relations on 2κ under Borel reducibility. Here κ is an uncountable regular cardinal with κ<κ = κ.

In reverse mathematics, it is possible to have a curious situation where we know that an implication does not reverse, but appear to have no information on how to weaken the assumption while preserving the conclusion (other than reducing all the way to the tautology of assuming the conclusion). A main cause of this phenomenon is the proof of a sentence from the theory . Using methods based on the functional interpretation, we introduce a family of weakenings of and use them to give new upper bounds for the Nash-Williams Theorem of wqo theory and Menger's Theorem for countable graphs.

Non-n-ampleness as denned by Pillay [20] and Evans [5] is preserved under analysability. Generalizing this to a more general notion of Σ-ampleness, this gives an immediate proof for all simple theories of a weakened version of the Canonical Base Property (CBP) proven by Chatzidakis [4] for types of finite SU-rank. This is then applied to the special case of groups.

A generic computation of a subset A of ℕ consists of a computation that correctly computes most of the bits of A, and never incorrectly computes any bits of A, but which does not necessarily give an answer for every input. The motivation for this concept comes from group theory and complexity theory, but the purely recursion theoretic analysis proves to be interesting, and often counterintuitive. The primary result of this paper is that there are no minimal pairs for generic computability, answering a question of Jockusch and Schupp.

We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the ‘geometric’ sorts which suffice to code all imaginaries in the corresponding algebraic setting.

For any ordinal Λ, we can define a polymodal logic GLPΛ, with a modality [ξ] for each ξ < Λ. These represent provability predicates of increasing strength. Although GLPΛ has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities, denoted . Later, Icard defined a topological model for which is very closely related to Ignatiev's.

In this paper we show how to extend these constructions for arbitrary Λ. More generally, for each Θ, Λ we build a Kripke model and a topological model , and show that is sound for both of these structures, as well as complete, provided Θ is large enough.

We give a sharper version of a theorem of Rosický, Trnková and Adámek [13], and a new proof of a theorem of Rosický [12], both about colimits in categories of structures. Unlike the original proofs, which use category-theoretic methods, we use set-theoretic arguments involving elementary embeddings given by large cardinals such as α-strongly compact and C(n)-extendible cardinals.

We introduce martingales defined by probabilistic strategies, in which randomness is used to decide whether to bet. We show that different criteria for the success of computable probabilistic strategies can be used to characterize ML-randomness, computable randomness, and partial computable randomness. Our characterization of ML-randomness partially addresses a critique of Schnorr by formulating ML randomness in terms of a computable process rather than a computably enumerable function.

The notion J is independent in (M, M0, N) was established by Shelah, for an AEC (abstract elementary class) which is stable in some cardinal λ and has a non-forking relation, satisfying the good λ-frame axioms and some additional hypotheses. Shelah uses independence to define dimension.

Here, we show the connection between the continuity property and dimension: if a non-forking satisfies natural conditions and the continuity property, then the dimension is well-behaved.

As a corollary, we weaken the stability hypothesis and two additional hypotheses, that appear in Shelah's theorem.

We define a quasi-order on Borel functions from a zero-dimensional Polish space into another that both refines the order induced by the Baire hierarchy of functions and generalises the embeddability order on Borel sets. We study the properties of this quasi-order on continuous functions, and we prove that the closed subsets of a zero-dimensional Polish space are well-quasi-ordered by bi-continuous embeddability.

If G is a group with a supersimple theory having a finite SU-rank, then the subgroup of G generated by all of its normal nilpotent subgroups is definable and nilpotent. This answers a question asked by Elwes, Jaligot, Macpherson and Ryten. If H is any group with a supersimple theory, then the subgroup of H generated by all of its normal soluble subgroups is definable and soluble.

We give a commentary on Newelski's suggestion or conjecture [8] that topological dynamics, in the sense of Ellis [3], applied to the action of a definable group G(M) on its “external type space” SG.ext(M), can explain, account for, or give rise to, the quotient G/G00, at least for suitable groups in NIP theories. We give a positive answer for measure-stable (or f sg) groups in NIP theories. As part of our analysis we show the existence of “externally definable” generics of G(M) for measure-stable groups. We also point out that for G definably amenable (in a NIP theory) G/G00 can be recovered, via the Ellis theory, from a natural Ellis semigroup structure on the space of global f-generic types.

We introduce the notion of skinniness for subsets of and its variants, namely skinnier and skinniest. We show that under some cardinal arithmetical assumptions, precipitousness or 2λ-saturation of NSκλ ∣ X, where NSκλ denotes the non-stationary ideal over , implies the existence of a skinny stationary subset of X. We also show that if λ is a singular cardinal, then there is no skinnier stationary subset of . Furthermore, if λ is a strong limit singular cardinal, there is no skinny stationary subset of . Combining these results, we show that if λ is a strong limit singular cardinal, then NSκλ ∣ X can satisfy neither precipitousness nor 2λ-saturation for every stationary X ⊆ . We also indicate that , where , is equivalent to the existence of a skinnier (or skinniest) stationary subset of under some cardinal arithmetical hypotheses.