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.

We establish a coloring theorem for successors of singular cardinals, and use it prove that for any such cardinal μ, we have if and only if for arbitrarily large θ < μ.

Using square sequences, a stationary subset ST of אω1+1 is constructed from a tree T of height ω1, uniformly in T. Under suitable hypotheses, adding a closed unbounded subset to ST requires adding a cofinal branch to T or collapsing at least one of ω1, אω1, and אω1+1. An application is that in ZFC there is no parameter free definition of the family of subsets of אω1+1 that have a closed unbounded subset in some ω1, אω1, and אω1+1 preserving outer model.

Let T be a recursively enumerable theory extending Elementary Arithmetic EA. L. D. Beklemishev proved that the Σ2 local reflection principle for T, (T), is conservative over the Σ1 local reflection principle, (T), with respect to boolean combinations of Σ1-sentences; and asked whether this result is best possible. In this work we answer Beklemishev's question by showing that Π2-sentences are not conserved for T = EA + “f is total,” where f is any nondecreasing computable function with elementary graph. We also discuss how this result generalizes to n > 0 and obtain as an application that for n > 0, is conservative over IΣn with respect to Πn+2-sentences.

We formulate and prove (in ZFC) a strong coloring theorem which holds at successors of singular cardinals, and use it to answer several questions concerning Shelah's principle Pr1 (μ+, μ+, μ+, cf (μ)) for singular μ.

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.

For a fixed countably infinite structure Γ with finite relational signature τ, we study the following computational problem: input are quantifier-free τ-formulas ϕ0, ϕ1, …, ϕn that define relations R0, R1, …, Rn over Γ. The question is whether the relation R0 is primitive positive definable from R1, …, Rn, i.e., definable by a first-order formula that uses only relation symbols for R1, …, Rn, equality, conjunctions, and existential quantification (disjunction, negation, and universal quantification are forbidden).

We show decidability of this problem for all structures Γ that have a first-order definition in an ordered homogeneous structure Δ with a finite relational signature whose age is a Ramsey class and determined by finitely many forbidden substructures. Examples of structures Γ with this property are the order of the rationals, the random graph, the homogeneous universal poset, the random tournament, all homogeneous universal C-relations, and many more. We also obtain decidability of the problem when we replace primitive positive definability by existential positive, or existential definability. Our proof makes use of universal algebraic and model theoretic concepts, Ramsey theory, and a recent characterization of Ramsey classes in topological dynamics.

We show in ZFC that if there is no proper class inner model with a Woodin cardinal, then there is an absolutely definable core model that is close to V in various ways.

We give the natural topological model for ¬BD-ℕ, and use it to show that the closure of spaces with the anti-Specker property under product does not imply BD-ℕ. Also, the natural topological model for ¬BD is presented. Finally, for some of the realizability models known indirectly to falsify BD-ℕ, it is brought out in detail how BD-ℕ fails.

Working under AD, we investigate the length of prewellorderings given by the iterates of ℳ2k+1, which is the minimal proper class mouse with 2k + 1 many Woodin cardinals. In particular, we answer some questions from [4] (the discussion of the questions appears in the last section of [2]).

We say that an uncountable metric space is computably categorical if every two computable structures on this space are equivalent up to a computable isometry. We show that Cantor space, the Urysohn space, and every separable Hilbert space are computably categorical, but the space [0, 1] of continuous functions on the unit interval with the supremum metric is not. We also characterize computably categorical subspaces of ℝn, and give a sufficient condition for a space to be computably categorical. Our interest is motivated by classical and recent results in computable (countable) model theory and computable analysis.

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).

We present definitions of homology groups Hn (p), n ≥ 0, associated to a complete type p. We show that if the generalized amalgamation properties hold, then the homology groups are trivial. We compute the group H2(p) for strong types in stable theories and show that any profinite abelian group can occur as the group H2 (p).

We show that there are plenty of infinite sets that satisfy the omniscience principle, in a minimalistic setting for constructive mathematics that is compatible with classical mathematics. A first example of an omniscient set is the one-point compactification of the natural numbers, also known as the generic convergent sequence. We relate this to Grilliot's and Ishihara's Tricks. We generalize this example to many infinite subsets of the Cantor space. These subsets turn out to be ordinals in a constructive sense, with respect to the lexicographic order, satisfying both a well-foundedness condition with respect to decidable subsets, and transfinite induction restricted to decidable predicates. The use of simple types allows us to reach any ordinal below εQ, and richer type systems allow us to get higher.

In this paper we show that there are various pseudo-jump operators definable over inadmissible Jβ that relate to the failure of admissiblity and to non-regularity. We will use these ideas to construct some intermediate degrees.

We develop a version of Namba forcing which is useful for constructing models with no good scale on ℵω. A model is produced in which holds for all finite n ≥ 1, but there is no good scale on ℵω; this strengthens a theorem of Cummings, Foreman, and Magidor [3] on the non-compactness of square.

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by realtime 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of ω-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton and a Büchi automaton such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(), L()); (2) There exists a model of ZFC in which the Wadge game W(L(), L()) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(), L()).

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.

According to Belegradek, a first order structure is weakly small if there are countably many 1-types over any of its finite subset. We show the following results. A field extension of finite degree of an infinite weakly small field has no Artin-Schreier extension. A weakly small field of characteristic 2 is finite or algebraically closed. A weakly small division ring of positive characteristic is locally finite dimensional over its centre. A weakly small division ring of characteristic 2 is a field.