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 Template:Math there exists a binary operation Template:Math such that Template:Math 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 Template:Math can be endowed with a group structure Template:Math.

Let Template:Math be a set. Let Template:Math be the Hartogs number of Template:Math. This is the least cardinal number such that there is no injection from Template:Math into Template:Math. It exists without the assumption of the axiom of choice. Assume here for technical simplicity of proof that Template:Math has no ordinal. Let Template:Math denote multiplication in the group Template:Math.

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

Now define a map Template:Math of Template:Math into Template:Math endowed with the lexicographical wellordering by sending Template:Math to the least Template:Math such that Template:Math. By the above reasoning the map Template:Math 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 Template:Math by Template:Math if Template:Math. It follows that every set Template:Math 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 Template:Math to be a cancellative magma, e.g. a quasigroup. The cancellation property is enough to ensure that the Template:Math 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 Template:Math is equipotent with a unique cardinal number Template:Abs which equals an aleph. Using the axiom of choice, one can show that for any family Template:Math of sets Template:Math (A). Moreover, by Tarski's theorem on choice, another equivalent of the axiom of choice, Template:Math for all finite Template:Math (B).

Let Template:Math be an infinite set and let Template:Math denote the set of all finite subsets of Template:Math. There is a natural multiplication Template:Math on Template:Math. For Template:Math, let Template:Math, where Template:Math denotes the symmetric difference. This turns Template:Math into a group with the empty set, Template:Math, being the identity and every element being its own inverse; Template:Math. The associative property, i.e. Template:Math is verified using basic properties of union and set difference. Thus Template:Math is a group with multiplication Template:Math.

Any set that can be put into bijection with a group becomes a group via the bijection. It will be shown that Template:Math, and hence a one-to-one correspondence between Template:Math and the group Template:Math exists. For Template:Math, let Template:Math be the subset of Template:Math consisting of all subsets of cardinality exactly Template:Math. Then Template:Math is the disjoint union of the Template:Math. The number of subsets of Template:Math of cardinality Template:Math is at most Template:Math because every subset with Template:Math elements is an element of the Template:Math-fold cartesian product Template:Math of Template:Math. So Template:Math for all Template:Math (C) by (B).

Putting these results together it is seen that Template:Math by (A) and (C). Also, Template:Math, since Template:Math contains all singletons. Thus, Template:Math and Template:Math, so, by the Schröder–Bernstein theorem, Template:Math. This means precisely that there is a bijection Template:Math between Template:Math and Template:Math. Finally, for Template:Math define Template:Math. This turns Template:Math 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 well-ordered (call these "non-wellorderable" sets). Let Template:Math be any such set. Now consider the set Template:Math. If Template:Math were to have a group structure, then, by the construction in first section, Template:Math can be well-ordered. This contradiction shows that there is no group structure on the set Template:Math.

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. However these properties are not equivalent. Namely, it is possible for sets which cannot be well-ordered to have a group structure.

For example, if $X$ is any set, then $𝒫(X)$ has a group structure, with symmetric difference as the group operation. Of course, if $X$ cannot be well-ordered, then neither can $𝒫(X)$. One interesting example of sets which cannot carry a group structure is from sets $X$ with the following two properties:

1. $X$ is an infinite Dedekind-finite set. In other words, $X$ has no countably infinite subset.
2. If $X$ is partitioned into finite sets, then all but finitely many of them are singletons.

To see that the combination of these two cannot admit a group structure, note that given any permutation of such set must have only finite orbits, and almost all of them are necessarily singletons which implies that most elements are not moved by the permutation. Now consider the permutations given by $x\mapsto a\cdot x$, for $a$ which is not the neutral element, there are infinitely many $x$ such that $a\cdot x=x$, so at least one of them is not the neutral element either. Multiplying by $x^{-1}$ gives that $a$ is in fact the identity element which is a contradiction.

The existence of such a set $X$ is consistent, for example given in Cohen's first model. Surprisingly, however, being an infinite Dedekind-finite set is not enough to rule out a group structure, as it is consistent that there are infinite Dedekind-finite sets with Dedekind-finite power sets.

References

• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book