Abstract We study the possible structures which can be carried by sets which have no countable subset, but which fail to be ‘surjectively Dedekind finite’, in two possible senses, that there is surjection to $\omega $ , or alternatively, that there is a surjection to a proper superset.

Abstract Two structures A and B are n-equivalent if Player II has a winning strategy in the n-move Ehrenfeucht-Fraïssé game on A and B. In earlier articles we studied n-equivalence classes of ordinals and coloured ordinals. In this article we similarly treat a class of scattered order-types, focussing on monomials and sums of monomials in ω and its reverse ω*.

Abstract In this paper we describe the well-founded initial segment of the free Heyting algebra α on finitely many, α, generators. We give a complete classification of initial sublattices of 2 isomorphic to 1 (called ‘low ladders’), and prove that for 2 ≤ α < ω, the height of the well-founded initial segment of α is ω2.

Abstract Generic automorphisms of certain homogeneous structures are considered, for instance, the rationals as an ordered set, the countable universal homogeneous partial order, and the random graph. Two of these cases were discussed in [7], where it was shown that there is a generic automorphism of the second in the sense introduced in [10], In this paper, I study various possible definitions of ‘generic’ and ‘mutually generic’, and discuss the existence of mutually generic automorphisms in some cases. In addition, generics in the automorphism group of the rational circular order are considered.

Abstract Tarski [5] showed that for any setX, its setω(X) of well-orderable subsets has cardinality strictly greater than that ofX, even in the absence of the axiom of choice. We construct a Fraenkel-Mostowski model in which there is an infinite strictly descending sequence under the relation ∣ω(X)∣ = ∣Y∣. This contrasts with the corresponding situation for power sets, where use of Hartogs' ℵ-function easily establishes that there can be no infinite descending sequence under the relation .

Abstract We show that the ‘tail’ of a doubly homogeneous chain of countable cofinality can be recognized in the quotient of its automorphism group by the subgroup consisting of those elements whose support is bounded above. This extends the authors' earlier result establishing this for the rationals and reals. We deduce that any group is isomorphic to the outer automorphism group of some simple lattice-ordered group.

Abstract The relationship between ideals I of Turing degrees and groups of I-recursive automorphisms of the ordering on rationals is studied. We discuss the differences between such groups and the group of all automorphisms, prove that the isomorphism type of such a group completely defines the ideal I, and outline a general correspondence between principal ideals of Turing degrees and the first-order properties of such groups.

Abstract It is shown that the boolean prime ideal theorem BPIT: every boolean algebra has a prime ideal, does not follow from the order-extension principle OE: every partial ordering can be extended to a linear ordering. The proof uses a Fraenkel–Mostowski model, where the family of atoms is indexed by a countable universal-homogeneous boolean algebra whose boolean partial ordering has a ‘generic’ extension to a linear ordering. To illustrate the technique for proving that the order-extension principle holds in the model we also study Mostowski's ordered model, and give a direct verification of OE there. The key technical point needed to verify OE in each case is the existence of a support structure.

Throughout, M will denote a transitive model of ZFC. Using the terms “random” and “generic” in the sense of [1], one may ask whether there can exist real numbers x and y such that x is generic over M[y] and y is random over M[x]. We shall see below by an elementary argument that this is not possible, and so, in a crude sense at least, random and generic extensions do not commute. This does not however rule out the possibility of a weaker commutativity. Let B be the complete Boolean algebra (in M) for adjoining a random real followed by a generic real and C be the complete Boolean algebra for adjoining a generic real followed by a random real. Then it still might be the case that B and C are isomorphic. This also fails, though, and we shall prove this by establishing the following combinatorial properties of MB and MC: but In addition this will show that C cannot be embedded as a complete subalgebra of B. The property satisfied by B is reminiscent of calibre ℵ1 [2]. B would have calibre if we could replace “infinite” by “uncountable”, and this occurs if Martin's Axiom holds in M. To obtain the nonisomorphism of B and C in general necessitated looking at the weaker property.