It has been shown by Quine that an interpreted theory Θ, formulated in the notation of quantification theory, is translatable into a theory Θ′ in which the only primitive predicate is a dyadic F. In establishing this result Quine takes for the universe of Θ′ a set which comprehends the universe of Θ and has the property that if x and y are members then so is {x, y}. For this fragmentary set theory the distinctness of x from {x, y} and {{x}} is assumed. It will be shown here that, if a pair of somewhat more stringent restrictions are assumed for the set theory, then there is a symmetric dyadic predicate G definable within Θ′, i.e., in terms of F alone, in terms of which F is in turn definable. It follows from this extended result that the theory Θ is translatable into a theory in which the only primitive predicate is symmetric and dyadic.

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

The main result of this paper will be that various notions of majorizability and compactness coincide in the full typestructure over the natural numbers. Moreover we shall show that the extensional typestructure of strongly majorizable functionals can be obtained by applying Zucker's construction ( )E to any of these coinciding intensional typestructures. A different result is proved in the typestructure of effective operations, where not every majorizable functional is compact. Finally we shall introduce the concept of relative compactness in the full typestructure and prove that there are just two degrees of compactness.

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

We consider a weak version of Schindler’s remarkable cardinals that may fail to be ${{\rm{\Sigma }}_2}$-reflecting. We show that the ${{\rm{\Sigma }}_2}$-reflecting weakly remarkable cardinals are exactly the remarkable cardinals, and that the existence of a non-${{\rm{\Sigma }}_2}$-reflecting weakly remarkable cardinal has higher consistency strength: it is equiconsistent with the existence of an ω-Erdős cardinal. We give an application involving gVP, the generic Vopěnka principle defined by Bagaria, Gitman, and Schindler. Namely, we show that gVP + “Ord is not ${{\rm{\Delta }}_2}$-Mahlo” and ${\text{gVP}}(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{\Pi } _1 )$ + “there is no proper class of remarkable cardinals” are both equiconsistent with the existence of a proper class of ω-Erdős cardinals, extending results of Bagaria, Gitman, Hamkins, and Schindler.

The language of linear temporal logic can be interpreted on the class of dynamic topological systems, giving rise to the intuitionistic temporal logic ${\sf ITL}^{\sf c}_{\Diamond \forall }$ , recently shown to be decidable by Fernández-Duque. In this article we axiomatize this logic, some fragments, and prove completeness for several familiar spaces.

We introduce and study the framework of compact metric structures and their associated notions of isomorphisms such as homeomorphic and bi-Lipschitz isomorphism. This is subsequently applied to model various classification problems in analysis such as isomorphism of C*-algebras and affine homeomorphism of Choquet simplices, where among other things we provide a simple proof of the completeness of the isomorphism relation of separable, simple, nuclear C*-algebras recently established by M. Sabok.

We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π1(ℕ) + ¬Ω1 has a proper end-extension to a model of Π1(ℕ), and so Π1(ℕ) + ¬Ω ⊢ BΣ1. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π1(ℕ) + ¬Exp ⊢ BΣ1. Both assumptions can be modified to versions which make it possible to replace Π1(ℕ) by IΔ0 as the base theory.

We also show that any proof that IΔ0 + ¬Exp does not prove a given finite fragment of BΣ1 has to be “nonrelativizing”, in the sense that it will not work in the presence of an arbitrary oracle.

Chang, in [1], proves an interpolation theorem (Theorem I, remark b)) for a first-order language. The proof of Chang's theorem uses essentially nonsimple devices, like special and ω1-saturated models.

In remark e) in [1], Chang asks if there is a simpler proof of his Theorem I.

In [1], Chang proves also another interpolation theorem (Theorem II), which is not an extension of his Theorem I, but extends Craig's interpolation theorem to Lα+,ω languages with interpolant in Lα+,α where α is a strong limit cardinal of cofinality ω.

In remark k) in [1], Chang asks if there is a generalization of both Theorems I and II in [1], or at least a generalization of both Theorem I in [1] and Lopez-Escobar's interpolation theorem in [7].

Maehara and Takeuti, in [8], show that there is a completely different proof of Chang's interpolation Theorem I as a consequence of their interpolation theorems. The proofs of these theorems of Maehara and Takeuti are proof theoretical in character, involving the notion of cut-free natural deduction, and it uses devices as simple as those needed for the usual Craig's interpolation theorem. Hence this can be considered as a positive answer to Chang's question in remark e) in [1].

In his paper [1] Chang provides among other things answers to questions of the following type: Given two models and of powers α and β, respectively, what is the least λ such that implies His proofs are by induction on the quantifier rank of formulas and they use an idea which in the case of ordinary first-order language goes back to Ehrenfeucht and Fraïssé. But, as we show, one can easily prove that if λ is big compared with κ and with the cardinality of the universe of the structure , then every L∞κ-formula is equivalent modulo the set of all Lλκ-sentences which hold in to a Lλκ-formula. From this, Chang's results follow immediately. The same method can be applied to similar problems concerning generalized languages.

We extend the usual language of second order arithmetic to one in which we can discuss an ultrafilter over of the sets of a given model. The semantics are based on fixing a subclass of the sets in a structure for the basic language that corresponds to the intended ultrafilter. In this language we state axioms that express the notion that the subclass is an ultrafilter and additional ones that say it is idempotent or Ramsey. The axioms for idempotent ultrafilters prove, for example, Hindman’s theorem and its generalizations such as the Galvin--Glazer theorem and iterated versions of these theorems (IHT and IGG). We prove that adding these axioms to IHT produce conservative extensions of ACA0 +IHT, ${\rm{ACA}}_{\rm{0}}^ +$, ATR0, ${\rm{\Pi }}_2^1$-CA0, and ${\rm{\Pi }}_2^1$-CA0 for all sentences of second order arithmetic and for full Z2 for the class of ${\rm{\Pi }}_4^1$ sentences. We also generalize and strengthen a metamathematical result of Wang (1984) to show, for example, that any ${\rm{\Pi }}_2^1$ theorem ∀X∃YΘ(X,Y) provable in ACA0 or ${\rm{ACA}}_{\rm{0}}^ +$ there are e,k ∈ ℕ such that ACA0 or ${\rm{ACA}}_{\rm{0}}^ +$ proves that ∀X(Θ(X, Φe(J(k)(X))) where Φe is the eth Turing reduction and J(k) is the kth iterate of the Turing or Arithmetic jump, respectively. (A similar result is derived for ${\rm{\Pi }}_3^1$ theorems of ${\rm{\Pi }}_1^1$-CA0 and the hyperjump.)