# Does every set have a group structure?

I know that there is no vector space having precisely $6$ elements. Does every set have a group structure?

-
Not related to your actual question, but just as a warning: there certainly are vector spaces with $6$ elements over finite fields. –  Santiago Canez Feb 3 '12 at 22:02
@SantiagoCanez No, there are not. The only finite fields are of order $q=p^n$, with $p$ prime, and the only finite sizes for vector spaces over a field are $q^m$ for some $m$. –  Thomas Andrews Feb 3 '12 at 22:29
You're both right - there are vector spaces with 6 elements, but there are no vector spaces with precisely 6 elements. –  Gerry Myerson Feb 3 '12 at 23:18
I've added [axiom-of-choice] "post-answering" since most of the questions mention and link, and mine somewhat explains, how this assertion is in fact equivalent to the axiom of choice in ZF. –  Asaf Karagila Feb 4 '12 at 0:32
@Thomas. Of course, silly error! –  Santiago Canez Feb 4 '12 at 0:47

The trivial answer is "no": the empty set does not admit a group structure.

The statement

If $X$ is a nonempty set, then there is a binary operation $\cdot$ such that $(X,\cdot)$ is a group.

is equivalent to the Axiom of Choice.

It is not needed for finite or countable sets: if $X$ is finite, with $n$ elements, then let $f\colon X\to\{0,1,\ldots,n-1\}$ be a bijection, and use transport of structure to give $X$ the structure of a cyclic group of order $n$. If $X$ is denumerably infinite, biject with $\mathbb{Z}$ and use transport of structure.

For uncountable sets, we can use the Axiom of Choice: let $|X|=\kappa$. Then the direct sum of $\kappa$ copies of $\mathbb{Z}$ has cardinality $\kappa$, so there is a bijection $$f\colon X\to \bigoplus_{i\in\kappa}\mathbb{Z}.$$ Use transport of structure again to make $X$ into a group.

That the converse holds (the statement implies the Axiom of Choice), is proven in this Math Overflow post.

-
And you won't get a better answer to this question then that. +1 and good job. –  Mathemagician1234 Feb 5 '12 at 23:30
Wow, finally I know the technical term "transport of structure" for what it means to "create new spaces from old spaces". I have wondered that for a long time but didn't want to ask such a trivial question. –  ItsNotObvious Feb 10 '12 at 15:12

As I learned on MathOverflow, this is equivalent to the axiom of choice.

-
Nice. It is obviously true if the set is countable, though. –  M.B. Feb 3 '12 at 21:27
@M.B. It is true if you can biject the set with an ordinal, countable being a special case of this. –  Arturo Magidin Feb 3 '12 at 21:48
That is an amazing result! –  Aryabhata Feb 3 '12 at 23:34
@Aryabhata: I agree. This is truly amazing, and I think that I've spent quite some time in the choiceless context; this proof still amazes me - time and time again. –  Asaf Karagila Feb 4 '12 at 0:41

Assuming the axiom of choice, then the universe is "well-behaved" and we are finding ourselves in two different situations given a non-empty set $X$:

• If $X$ is finite, then there is a bijection between $X$ and $\{0,\ldots,n-1\}$ which then implies there is a group structure similar to $X$ and $\mathbb Z/n\mathbb Z$ with $+^{\!\!\mod n}$.
• The set $X$ is infinite, then by we can take $G=\bigoplus_{i\in X}\mathbb Z$. We can consider $G$ as finite functions from $X\times\mathbb Z$. This means that: $$|G|\le|\{f\subseteq X\times\mathbb Z\mid f\text{ is a finite set}\}|=|X\times\mathbb Z|=|X|\cdot\aleph_0=|X|\le|G|$$ Where the first $=$ sign follows from the axiom of choice: every infinite set is equinumerous with the collection of all its finite subsets; and the last $\le$ follows from the injective map $x\mapsto\{\langle x,1\rangle\}$, thus by Cantor-Bernstein we have that $X$ and $G$ have the same cardinality therefore we can use a bijection between them to define the group structure on $X$.

On the other hand, it appears that if every set has a group structure then the axiom of choice holds. The proof appears in this MathOverflow thread, and requires a mild familiarity with constructs which relate to the axiom of choice.

The nutshell of the proof is this:

• Given an infinite set $X$ we define $H(X)$ to be the least ordinal $\alpha$ that there is no injection $g:\alpha\to X$ (this is known as the Hartog number of $X$)
• If $X$ can be injected into $H(X)$ then $X$ can be well ordered, since being injected into an ordinal means that $X$ inherits a well order.
• Using the assumption that every set can be given a group structure we give a group structure to $X\cup H(X)$, and from this we deduce that there exists an injection from $X$ into $H(X)$.
• Therefore if every set can be given a group structure, every set can be well ordered and therefore the axiom of choice holds.

Lastly, a somewhat natural example of a set which cannot be given a group structure in a model contradicting the axiom of choice:

We say that $A$ is Dedekind-finite if every proper subset $B$ of $A$ has cardinality strictly less than the cardinality of $A$. Every finite set, then, is a Dedekind-finite set. Equivalently $A$ is Dedekind-finite if and only if it does not have a countably infinite subset.

When not assuming the axiom of choice it is consistent that infinite Dedekind-finite sets exist (infinite means not in bijection with $\{0,\ldots,n\}$ for any $n\in\mathbb N$).

The first Cohen model which exhibited the independence of the axiom of choice from ZF was one in which he added a Dedekind-finite set of real numbers. This set cannot be given a group structure.

Why? If $X$ has a group structure if there is an element of infinite order we can define an injection from $\mathbb N$ into $X$ using $n\mapsto x^n$; if all the elements have finite order then we can partition the set into infinitely many parts of finite size defined by the order of each element.

The set $A$ in the first Cohen model is Dedekind finite, therefore every group structure would have that all elements have finite order; however its construction gives us that every partition into finite subsets is almost entirely singletons. This means that if a group structures was endowed almost every element would have to be of order $1$. This is of course impossible, therefore this set is an example of how a set might not have a group structure definable on without the axiom of choice.

(Interestingly enough, not all infinite Dedekind-finite sets are counterexamples. It is perfectly consistent to have a group structure on an infinite Dedekind finite set in some cases!)

-
Do we really need to invoke Lowenheim-Skolem? We can just construct them explicitly if we know AC, by taking a direct of $\kappa$ copies of any group of cardinality less than or equal to $\kappa$ (or just making the set $2^{(\kappa)}$ into a group by pointwise addition). –  Arturo Magidin Feb 5 '12 at 3:51
@Arturo: Indeed we could use $2^{(\kappa)}$ or even $\mathbb Z^{(\kappa)}$. –  Asaf Karagila Feb 5 '12 at 6:23
In the third step of the construction of (*) implies Well Ordering, I don't quite see how to get $X \to H(X)$ injection. The MO link shows how to get $\to H(X)^2$... –  Willie Wong Feb 10 '12 at 15:27
@WillieWong: You are correct, however even without the axiom of choice $H(X)^2$ has the same cardinality as $H(X)$; but even easier than that - it can be well ordered by a lexicographic ordering from the original well order. This suffices to have $X$ well ordered. –  Asaf Karagila Feb 10 '12 at 16:06
@Asaf: d'oh. I'm still a bit rusty with all these cardinality versus ordinals business. Thanks. –  Willie Wong Feb 10 '12 at 17:00
Every non-empty finite set of size $n$ in one-to-one correspondence with $\{0,1,2,\ldots,n-1\}$ (which is just $\{0\}$ if $n=1$), and so can be made into a cyclic group with the right group operation. Likewise every countably infinite set and $\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ (with addition). Every set with the same cardinality as $\mathbb{R}$ can be given a group structure that makes it isomorphic to $(\mathbb{R},+)$. Generally, of course, if the set has the same cardinality as the underlying set of any group, it can be done. The question can be read as "What is the set of cardinalities that are orders of groups?". A partial answer, then is that it includes all non-zero finite cardinalities, $\aleph_0$, and $2^{\aleph_0}$.
(If I can believe some other answers, it also includes $\aleph_1$ and lots of others.)
Is there some reason you find it hard to believe the other answers? I didn't prove that $\oplus_{i\in\kappa}\mathbb{Z}$ has cardinality $\kappa$ for all cardinals $\kappa$, but I can give a proof if necessary; I'm pretty sure it doesn't even need choice, since $\kappa$ is assumed to be an ordinal and $\mathbb{Z}$ has a natural well-ordering. –  Arturo Magidin Feb 4 '12 at 3:34