A set is said to be amorphous if it is infinite, but is not the disjoint union of two infinite subsets. Thus amorphous sets can exist only if the axiom of choice is false. We give a general study of the structure which an amorphous set can carry, with the object of eventually obtaining a complete classification. The principal types of amorphous set we distinguish are the following: amorphous sets not of projective type, either bounded or unbounded size of members (...) of partitions of the set into finite pieces), and amorphous sets of projective type, meaning that the set admits a non-degenerate pregeometry, over finite fields either of bounded cardinality or of unbounded cardinality. The hope is that all amorphous sets will be of one of these types. Examples of each sort are constructed, and a reconstruction result for bounded amorphous sets is presented, indicating that the amorphous sets of this kind constructed in the paper are the only possible ones. The final section examines some questions concerned with the resulting cardinal arithmetic. (shrink)

0-categorical o-minimal structures were completely described by Pillay and Steinhorn 565–592), and are essentially built up from copies of the rationals as an ordered set by ‘cutting and copying’. Here we investigate the possible structures which an 0-categorical weakly o-minimal set may carry, and find that there are some rather more interesting examples. We show that even here the possibilities are limited. We subdivide our study into the following principal cases: the structure is 1-indiscernible, in which case all possibilities are (...) classified up to binary structure; the structure is 2-indiscernible, classified up to ternary structure; the structure is 3-indiscernible, in which case we show that it is k-indiscernible for every finite k. We also make some remarks about the possible structures of higher arities which an 0-categorical weakly o-minimal structure may carry. (shrink)

We consider the relation between versions of Ramsey’s Theorem and König’s Infinity Lemma, in the absence of the axiom of choice.

We study a notion of ‘o-amorphous’ which bears the same relationship to ‘o-minimal’ as ‘amorphous’ 191–233) does to ‘strongly minimal’. A linearly ordered set is said to be o-amorphous if its only subsets are finite unions of intervals. This turns out to be a relatively straightforward case, and we can provide a complete ‘classification’, subject to the same provisos as in Truss . The reason is that since o-amorphous is an essentially second-order notion, it corresponds more accurately to 0-categorical o-minimal, (...) and our classification is thus very similar to the one given in 565–592) for that case. More interesting structures arise if we replace ‘interval’ in the definition by ‘convex set’, giving us the class of weakly o-amorphous sets. Here, in fact, there are so many examples that a complete classification seems out of the question. We illustrate some of the structures which these may exhibit, and classify them in certain instances not too far removed from the o-amorphous case. (shrink)

We study rigidity properties of linearly ordered sets (chains) under automorphisms, embeddings, epimorphisms, and endomorphisms. We focus on two main cases: dense subchains of the real numbers, and uncountable dense chains of higher regular cardinalities. We also give a Fraenkel‐Mostowski model which illustrates the role of the axiom of choice in one of the key proofs.

A set is said to be amorphous if it is infinite, but cannot be written as the disjoint union of two infinite sets. The possible structures which an amorphous set can carry were discussed in [5]. Here we study an analogous notion at the next level up, that is to say replacing finite/infinite by countable/uncountable, saying that a set is quasi-amorphous if it is uncountable, but is not the disjoint union of two uncountable sets, and every infinite subset has a (...) countably infinite subset. We use the Fraenkel–Mostowski method to give many examples showing the diverse structures which can arise as quasi-amorphous sets, for instance carrying a projective geometry, or a linear ordering, or both; reconstruction results in the style of [1] are harder to come by in this case. (shrink)

We consider the relation between versions of Ramsey’s Theorem and König’s Infinity Lemma, in the absence of the axiom of choice.

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 ������₂ isomorphic to ������₁ (called 'low ladders'), and prove that for 2 < α < ω, the height of the well-founded initial segment of ������α.

Starting from the definition of `amorphous set' in set theory without the axiom of choice, we propose a notion of rank (which will only make sense for, at most, the class of Dedekind finite sets), which is intended to be an analogue in this situation of Morley rank in model theory.

We show how to reconstruct the topology on the monoid of endomorphisms of the rational numbers under the strict or reflexive order relation, and the polymorphism clone of the rational numbers under the reflexive relation. In addition we show how automatic homeomorphicity results can be lifted to polymorphism clones generated by monoids.

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

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

Together, Models and Computability and its sister volume Sets and Proofs will provide readers with a comprehensive guide to the current state of mathematical logic. All the authors are leaders in their fields and are drawn from the invited speakers at 'Logic Colloquium '97' (the major international meeting of the Association of Symbolic Logic). It is expected that the breadth and timeliness of these two volumes will prove an invaluable and unique resource for specialists, post-graduate researchers, and the informed and (...) interested nonspecialist. (shrink)

Tarski [5] showed that for any set X, its set w(X) of well-orderable subsets has cardinality strictly greater than that of X, 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 |w (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 |P(X)| = (...) |Y|. (shrink)

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.

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.

In this paper, we give a classification of ℵ0-categorical coloured linear orders, generalizing Rosenstein's characterization of ℵ0-categorical linear orderings. We show that they can all be built from coloured singletons by concatenation and ℚn-combinations . We give a method using coding trees to describe all structures in our list.

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 ω*.

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.

A study of the elementary theory of quotients of symmetric groups is carried out in a similar spirit to Shelah . Apart from the trivial and alternating subgroups, the normal subgroups of the full symmetric group S on an infinite cardinal μ are all of the form Sκ = the subgroup consisting of elements whose support has cardinality 20, cƒ 20 < κ, 0 < κ < 20, and κ = 0, we make a further analysis of the first order (...) theory of Sλ/Sκ. introducing many-sorted second order structures , all of whose sorts have cardinality at most 20, and in terms of which we can completely characterize the elementary theory of the groups Sλ/Sκ. (shrink)

We show that the weak monadic second order theory of the structure is first order interpretable in its automorphism group.

It is shown that all the countable superatomic boolean algebras of finite rank have the small index property.