I know that there is no vector space having precisely $6$ elements. Does every set have a group structure?
Does every set have a group structure?
-
0@Thomas. Of course, silly error! – 2012-02-04
4 Answers
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.
-
0@WernerGermánBusch: Because what you describe is not a group; in a group, for any two elements $x$ and $y$, there exists **a unique** element $z$ such that $xz=y$. What you describe does not satisfy that condition for any set with more than one element. – 2017-05-20
As I learned on MathOverflow, this is equivalent to the axiom of choice.
-
0@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. – 2012-02-04
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!)
-
0@Asaf: d'oh. I'm still a bit rusty with all these cardinality versus ordinals business. Thanks. – 2012-02-10
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.)
-
0@ArturoMagidin : It's just that I haven't completely read all of the other answers. – 2012-02-04