Group structure and the axiom of choice

Ernst Zermelo in 1904 proved the wellordering theorem using what was to become known as the axiom of choice.

In mathematics a group is a set together with a binary operation on the set called multiplication that obeys the group axioms. The axiom of choice is an axiom of ZFC set theory which in one form states that every set can be wellordered.

In ZF set theory, i.e. ZFC without the axiom of choice, the following statements are equivalent:

• For every nonempty set X there exists a binary operation • such that (X, •) is a group.
• The axiom of choice is true.

A group structure implies the axiom of choice

In this section it is assumed that every set X can be endowed with a group structure (X, •).

Let X be a set. Let ℵ(X) be the Hartogs number of X. This is the least cardinal number such that there is no injection from ℵ(X) into X. It exists without the assumption of the axiom of choice. Assume here for technical simplicity of proof that X has no ordinal. Let • denote multiplication in the group (X ∪ ℵ(X), •).

For any x ∈ X there is an α ∈ ℵ(X) such that x • α ∈ ℵ(X). Suppose not. Then there is an y ∈ X such that y • α ∈ X for all α ∈ ℵ(X). But by elementary group theory, the y • α are all different as α ranges over ℵ(X) (i). Thus such a y gives an injection from ℵ(X) into X. This is impossible since ℵ(X) is a cardinal such that no injection into X exists.

Now define a map j of X into ℵ(X) × ℵ(X) endowed with the lexicographical wellordering by sending x ∈ X to the least (α, β) ∈ ℵ(X) × ℵ(X) such that x • α = β. By the above reasoning the map j exists and is unique since least elements of subsets of wellordered sets are unique. It is, by elementary group theory, injective.

Finally, define a wellordering on X by x < y if j(x) < j(y). It follows that every set X can be wellordered and thus that the axiom of choice is true.

For the crucial property expressed in (i) above to hold, and hence the whole proof, it is sufficient for X to be a cancellative magma, e.g. a quasigroup. The cancellation property is enough to ensure that the y • α are all different.

The axiom of choice implies a group structure

Any nonempty finite set has a group structure as a cyclic group generated by any element. Under the assumption of the axiom of choice, every infinite set X is equipotent with a unique cardinal number | X | which equals an aleph. Using the axiom of choice, one can show that for any family S of sets | ⋃S | ≤ | S | × sup { |s| : s ∈ S} (A). Moreover, by Tarski's theorem on choice, another equivalent of the axiom of choice, | X |ⁿ = | X | for all finite n (B).

Let X be a nonempty set and let F denote the set of all finite subsets of X. There is a natural multiplication • on F. For f, g ∈ F, let f • g = f Δ g, where Δ denotes the symmetric difference. This turns (F, •) into a group with the empty set, Ø, being the identity and every element being its own inverse; f Δ f = Ø. The associative property, i.e. (f Δ g) Δ h = f Δ (g Δ h) is verified using basic properties of union and set difference. Thus F is a group with multiplication Δ.

Any set that can be put into bijection with a group becomes a group via the bijection. It will be shown that | X | = | F |, and hence a one-to-one correspondence between X and the group (F, •) exists. For n = 0,1,2, ..., let F_n be the subset of F consisting of all subsets of cardinality exactly n. Then F is the disjoint union of the F_n. The number of subsets of X of cardinality n is at most | X |ⁿ because every subset with n elements is an element of the n-fold cartesian product Xⁿ of X. So | F_n | ≤ | X |ⁿ = | X | for all n (C) by (B).

Putting these results together it is seen that | F | = | ⋃_{n ∈ ω}F_n | ≤ ℵ₀ · | X | = | X | by (A) and (C). Also, | F | ≥ | X |, since F contains all singletons. Thus, | X | ≤ | F | and | F | ≤ | X |, so, by the Schroeder–Bernstein theorem, | F | = | X |. This means precisely that there is a bijection j between X and F. Finally, for x, y ∈ X define x • y = j⁻¹(j(x) Δ j(y)). This turns (X, •) into a group. Hence every set admits a group structure.

A ZF set with no group structure

There are models of ZF in which the axiom of choice fails. In such a model, there are sets that cannot be wellordered (call these "non-wellorderable" sets). Let X be any such set. Now consider the set Y = X ∪ ℵ(X). If Y were to have a group structure, then, by the construction in first section, X is wellordered. This contradiction shows that there is no group structure on the set Y.

If a set is such that it cannot be endowed with a group structure, then it is necessarily non-wellorderable. Otherwise the construction in the second section does yield a group structure. Non-wellorderable sets have the properties of being infinite and Dedekind-finite. If X is a set without possible group structure, hence Dedekind-finite, then its power set ℙ(X) is Dedekind-finite as well, but ℙ(X) can be endowed with a group structure using the same method as in the second section. This shows that being non-wellorderable is not sufficient for a set to not have a group structure. By adding one more property one finds a list of three properties that together suffice:

• (1) X is infinite.
• (2) X is Dedekind-finite.
• (3) X cannot be partitioned into finite sets of size n for n > 1.

Property (2) implies that there is no sequence from ω to X with distinct elements. Assume that there is a group structure on X. Then by (1) there is an element x ∈ X that is not the identity of the group, hence its order is not 1. By (2) the order of x cannot be infinite. If the order of x is finite, then the set of all cosets of the cyclic subgroup generated by x partitions X, producing a contradiction with point (3). Since any element of any group has a definite (possible infinite) order, X cannot have a group structure.

There are models of ZF with sets having properties (1)–(3). One such is obtained from the standard Cohen model with countably many adjoined Cohen reals by passing to a certain symmetric submodel.