Posted by Jason Polak on 15. October 2011 · 1 comment · Categories: model-theory, set-theory · Tags: , ,

Here I explain the proof that in ZF, the axiom of choice (AC) is equivalent to every nonempty set having group structure (GS). I first learned of the nontrivial direction of this argument in this MathOverflow post and as far as I know first appeared in “Some new algebraic equivalents of the axiom of choice” by A. Hajnal and A. Kertész in Publ. Math. Debrecen 19 (1972), pp. 339-340.

AC Implies GS

This direction is the “easier” direction because once we invoke the axiom of choice, we can just use some basic model theory. But first, let us look at a slightly different proof that only uses set theory.

First Proof. If $ S$ is finite and nonempty, then the bijection $ S\to \mathbb{Z}/|S|$ gives a group structure on $ S$. If $ S$ is infinite, the by (AC) there is a set bijection $ S\xrightarrow{\sim} FS$ where $ FS$ denotes the set of finite subsets of $ S$. For $ U,V\in FS$, let

$ \displaystyle U\Delta V = (U – V)\cup (V – U)$

be the operation of symmetric difference. It is not too difficult to verify that this operation makes $ FS$ into a group whose identity element is the empty set. $ \blacksquare$

Second Proof. For finite nonempty sets, the statement was already proved in the first proof. Now, the axiom of choice implies the Lowenheim-Skolem theorem in model theory. Since $ \mathbb{Z}$ is an infinite model for the axioms of a group (these axioms being stated in first-order logic), by Lowenheim-Skolem there is a model for the axioms of a group of every infinite cardinality. $ \blacksquare$

Modifying this proof we see that every set can be giving a monoid structure, a ring structure, a field structure, etc.

GS Implies AC: Preliminaries

We first need to review Hartogs’ construction. Hartogs proved in 1915 that in ZF, given any set $ S$, the set $ h(S)$ of all the ordinals $ \alpha$ such that there is an injection $ \alpha\hookrightarrow S$ is also an ordinal. Further, Hartogs showed that there is no injection $ h(S)\hookrightarrow S$; both of these statements are not difficult to prove and are good exercises. See the nLab page on Hartogs number for more details.

This statement is interesting in itself, because it shows that in ZF, although not every set is well-orderable, for each set $ S$, we can still find a larger set $ h(S)$ that is well-ordered. In honour of Hartogs, $ h(S)$ is called the Hartogs number of $ S$.

GS Implies AC: The Proof

We shall now slay the dragon. We claim that GS implies AC. Indeed:

Proof. Let $ S$ be a set and let $ h(S)$ be the Hartogs number of $ S$. Let $ *:S\sqcup h(S)\to S\sqcup h(S)$ be a group operation on the disjoint union $ S\sqcup h(S)$. We first claim that for each $ x\in S$, there is an $ \alpha\in h(S)$ such that $ x*\alpha\in h(S)$. Indeed, if not, then choose some counterexample $ x\in S$; multiplication by $ x$ gives an injection $ h(S)\to S$, which contradictions the properties of the Hartogs number.

Now, given the dictionary order, $ h(S)\times h(S)$ is a well-ordered set. Thus, for each $ x\in S$, define $ \varphi: S\to h(S)\times h(S)$ by $ \varphi(x)$ being the least element $ (\alpha,\beta)\in h(S)\times h(s)$ such that $ x*\alpha = \beta$. Because multiplication by a fixed element of a group is injective, this gives an injection $ S\hookrightarrow h(S)\times h(S)$, inducing a well-ordering on $ S$. $ \blacksquare$

1 Comment

  1. Hi!

    I have recently (a couple of days ago) written an article for Wikipedia covering some of this at
    I found your blog while Googling for related stuff. I like the second version of AC implies GS, and I’m thinking about “borrowing” it for my article.

    Best regards, YohanN7

Leave a Reply to Johan Nystrom Cancel reply

Your email address will not be published. Required fields are marked *