We show that under Martin's Axiom, the cofinality cf(Aut(Γ)) of the automorphism group of the random graph Γ is 2ω.

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.

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 κ<κ = κ.

With all seven of ‘∼’, ‘⊃’, ‘&’, ‘ν’, ‘≡’, ‘∀’, and ‘∃’ understood to serve as primitive signs, let an expression of the sort

A1, A2, … , An → B1, B2, … , Bm,

where A1, A2, …, Aη (η≥ 0), B1, B2, …, and Bm (m > 0 if n = 0, otherwise m ≥ 0) are wffs of the first-order quantificational calculus (QC), count as an L-sequent of QC; let an L-sequent of QC of the sort

A1, A2, … , An → B

count as an N-sequent of QC;2 and let an L-sequent S of QC count as a Gentzen L-sequent of QC if no individual variable of QC occurs both bound and free in S.

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 introduce the notions of copyable and diagonalizable classes of structures. We then show how these notions are connected to two other notions that had already been studied for some particular classes of structures, namely the listability property and the low property.

The main result of this paper is the characterizations of the classes of structures with the low property, that is, the classes whose low members all have computable copies. We characterize these classes as the ones whose structural jumps are listable.