Suppose that G is a group that is not finitely generated. Then the cofinality of G, written c(G), is denned to be the least cardinal λ such that G can be expressed as the union of a chain of λ proper subgroups. If κ is an infinite cardinal, then Sym(κ) denotes the group of all permutations of the set κ = {α∣α < κ}. In [1], Macpherson and Neumann proved that c(Sym(κ)) > κ for all infinite cardinals κ. In [4], we proved that it is consistent that c(Sym(ω)) and 2ω can be any two prescribed regular cardinals, subject only to the obvious requirement that c(Sym(ω)) ≤ 2ω. Our first result in this paper is the analogous result for regular uncountable cardinals κ.

Theorem 1.1. Let V ⊨ GCH. Let κ, θ, λ ∈ V be cardinals such that

(i) κ and θ are regular uncountable, and

(ii) κ < θ ≤ cf(λ).

Then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that if G is ℙ-generic then V[G] ⊨ c(Sym(κ)) = θ ≤ λ = 2κ.

Theorem 1.1 will be proved in §2. Our proof is based on a very powerful uniformization principle, which was shown to be consistent for regular uncountable cardinals in [2].

We set up a general context in which one can prove Sauer–Shelah type lemmas. We apply our general results to answer a question of Bhaskar [1] and give a slight improvement to a result of Malliaris and Terry [7]. We also prove a new Sauer–Shelah type lemma in the context of $ \operatorname {\textrm{op}}$-rank, a notion of Guingona and Hill [4].

We study the following open question in computable model theory: does there exist a structure of computable dimension two which is the prime model of its first-order theory? We construct an example of such a structure by coding a certain family of c.e. sets with exactly two one-to-one computable enumerations into a directed graph. We also show that there are examples of such structures in the classes of undirected graphs, partial orders, lattices, and integral domains.

ℵ0-stable ℵ0-categorical linked quaternionic mappings are studied and are shown to correspond (in some sense) to special groups which are ℵ0-stable, ℵ0-categorical, satisfy AP(3) and have finite 2-symbol length. They are also related to special groups whose isometry relation is a finite union of cosets, which are then considered on their own, as well as their links with pseudofinite, profinite and weakly normal special groups.

Throughout the paper A will be a transitive set closed under finite subsets and the formulas in various classes mentioned are allowed to contain parameters from A (or from B in §2).

By use of a refinement of Moschovakis' notion of the game-quantifier [13], [14], [15] we are able to obtain a game-theoretic description of s-Π11 predicates over countable sets which then leads to a classification of positive Σ1 inductive sets.

Similar results are then proved for certain sets of cofinality ω. As a consequence we obtain the compactness results of Green [8], [11], Nyberg [16] and Makkai [12].

The use of games to classify inductive sets was initiated by Moschovakis [13], [14], [15] and has been extended to Q-inductive sets by Aczel [2]. Games were also used in a slightly different setting by Vaught [18] and Makkai [12]. In fact, Vaught's proof of the compactness theorem is very close to our proof in §1 and Makkai's extension to cofinality ω sets uses a result similar to Theorem 3 in §2.

We are indebted to the referee for many helpful suggestions, in particular, for bringing to our attention the related works of Vaught and Makkai cited above.

Our framework is ZFC, and we view cardinals as initial ordinals. Baumgartner ([Bal] and [Ba2]) studied properties of large cardinals by considering these properties as properties of normal ideals and not as properties of cardinals alone. In this paper we study these combinatorial properties by defining operations which take as input one or more ideals and give as output an ideal associated with a large cardinal property. We consider four operations T, P, S and C on ideals of a regular cardinal κ, and study the structure of the collection of subsets they give, and the relationships between them.

The operation T is defined using combinatorial properties based on trees 〈X, <T〉 on subsets X ⊆ κ (where α <T β → α < β). Given an ideal I, consider the property *: “every tree on κ with every branching set in I has a branch of size κ” (where a branching set is a maximal set with the same set of <T-predecessors, and a chain is a maximal <T-linearly ordered set; for definitions see §2). Now consider the collection T(I) of all subsets of κ that do not satisfy * (see Definition 2.2 and the introduction to §5). The operation T provides us with the large cardinal property (whether κ ∈ T(I) or not) and it also provides us with the ideal associated with this large cardinal property (namely T(I)); in general, we obtain different notions depending on the ideal I.

Woodin and Vopěnka cardinals are established notions in the large cardinal hierarchy and it is known that Vopěnka cardinals are the Woodin analogue for supercompactness. Here we give the definition of Woodin for strong compactness cardinals, the Woodinised version of strong compactness, and we prove an analogue of Magidor’s identity crisis theorem for the first strongly compact cardinal.

We study a partial order on countably complete ultrafilters introduced by Ketonen [2] as a generalization of the Mitchell order. The following are our main results: the order is wellfounded; its linearity is equivalent to the Ultrapower Axiom, a principle introduced in the author’s dissertation [1]; finally, assuming the Ultrapower Axiom, the Ketonen order coincides with Lipschitz reducibility in the sense of generalized descriptive set theory.

In this note we give a simplified ordinal analysis of first-order reflection. An ordinal notation system $OT$ is introduced based on $\psi $-functions. Provable $\Sigma _{1}$-sentences on $L_{\omega _{1}^{CK}}$ are bounded through cut-elimination on operator controlled derivations.