111
$\begingroup$

It is easy to see that in ZFC, any non-empty set $S$ admits a group structure: for finite $S$ identify $S$ with a cyclic group, and for infinite $S$, the set of finite subsets of $S$ with the binary operation of symmetric difference forms a group, and in ZFC there is a bijection between $S$ and the set of finite subsets of $S$, so the group structure can be taken to $S$. However, the existence of this bijection needs the axiom of choice.

So my question is

Can it be shown in ZF that for any non-empty set $S$ there exists a binary operation $\ast$ on $S$ making $(S,\ast)$ into a group?

$\endgroup$
9
  • $\begingroup$ You should edit your LaTeX a bit. Also, I don't understand what you mean by a bijection between $S$ and its finite subsets - when $S$ is finite, doesn't Cantor's theorem that $|S|<|P(S)|$ mean this isn't the case? $\endgroup$ Jan 25, 2010 at 21:58
  • $\begingroup$ @Zev: you're right, I've edited the question. $\endgroup$ Jan 25, 2010 at 22:03
  • 6
    $\begingroup$ If it could be so shown, wouldn't the group identity give you a choice function? $\endgroup$ Jan 25, 2010 at 22:16
  • 1
    $\begingroup$ Zev, turning Konrad's semigroup into a monoid gives you the trivial monoid, since x*1 = x = s_0 for all x. $\endgroup$ Jan 25, 2010 at 22:46
  • 12
    $\begingroup$ @David: You don't get a choice function so easily, because of course there will generally be many group structures on the set, and you'd have to choose the group structure, before using your idea to "choose" the identity. $\endgroup$ Jan 26, 2010 at 13:24

2 Answers 2

174
$\begingroup$

In ZF, the following are equivalent:

(a) For every nonempty set there is a binary operation making it a group

(b) Axiom of choice

Non trivial direction [(a) $\to$ (b)]:

The trick is Hartogs' construction which gives for every set $X$ an ordinal $\aleph(X)$ such that there is no injection from $\aleph(X)$ into $X$. Assume for simplicity that $X$ has no ordinals. Let $\circ$ be a group operation on $X \cup \aleph(X)$. Now for any $x \in X$ there must be an $\alpha \in \aleph(X)$ such that $x \circ \alpha \in \aleph(X)$ since otherwise we get an injection of $\aleph(X)$ into $X$. Using $\circ$, therefore, one may inject $X$ into $(\aleph(X))^{2}$ by sending $x \in X$ to the $<$-least pair $(\alpha, \beta)$ in $(\aleph(X))^{2}$ such that $x \circ \alpha = \beta$. Here, $<$ is the lexicographic well-ordering on the product $(\aleph(X))^{2}$. This induces a well-ordering on $X$.

$\endgroup$
10
  • 8
    $\begingroup$ Fantastic! This is a great argument! It is just equivalent to AC. $\endgroup$ Jan 26, 2010 at 0:13
  • 2
    $\begingroup$ Aha, very neat! $\endgroup$ Jan 26, 2010 at 8:20
  • 8
    $\begingroup$ I did some googling and found this: Hajnal, A., Kertész, A. - Some new algebraic equivalents of the axiom of choice, Publ. Math. Debrecen 19 (1972), 339--340 (1973). Review on MathSciNet: The authors show that in ZF, the axiom of choice is equivalent to the statement: on every nonempty set there exists a cancellative groupoid. $\endgroup$
    – Ashutosh
    Jan 26, 2010 at 15:08
  • 7
    $\begingroup$ I have it. Same proof. $\endgroup$ Jun 13, 2010 at 17:29
  • 8
    $\begingroup$ Hajnal now loaded his paper with Kertesz to Reseacrhgate, so it's available: researchgate.net/publication/… $\endgroup$ Oct 10, 2015 at 7:03
29
$\begingroup$

You cannot in general put a group structure on a set. There is a model of ZF with a set A that has no infinite countable subset and cannot be partitioned into finite sets; such a set has no group structure.

See e.g at http://groups.google.com/group/sci.math/msg/06eba700dfacb6ed


Sketch of proof that in standard Cohen model the set $A=\{a_n:n\in\omega\}$ of adjoined Cohen reals cannot be partitioned into finite sets:

Let $\mathbb{P}=Fn(\omega\times\omega,2)$ which is the poset we force with. The model is the symmetric submodel whose permutation group on $\mathbb{P}$ is all permutations of the form $\pi(p)(\pi(m),n)=p(m,n)$ where $\pi$ varies over all permutations of $\omega$, (that is we are extending each $\pi$ to a permutation of $\mathbb{P}$ which I also refer to as $\pi$) and the relevant filter is generated by all the finite support subgroups.

Suppose for contradiction that $p\Vdash " \bigcup_{i\in I}\dot{A_i}=A$ is a partition into finite pieces"; let $E$ (a finite set) be the support of this partition. Take some $a_{i_0}\not\in E$ and extend $p$ to a $q$ such that $q\Vdash ``\{a_{i_0},\ldots a_{i_n}\}$ is the piece of the partition containing $a_{i_0}$". Then pick some $j$ which is not in $E$ nor the domain of $q$ nor equal to any of the $a_{i_0},\ldots a_{i_l}$. If $\pi$ is a permutation fixing $E$ and each of $a_{i_1},\ldots a_{i_n}$ and sending $a_{i_0}$ to $a_j$, it follows that $\pi(q) \Vdash " \{a_j,a_{i_1},\ldots a_{i_n}\}$ is the piece of the partition containing a_j". But also $q$ and $\pi(q)$ are compatible and here we run into trouble, because $q$ forces that $a_{i_0}$ and $a_{i_1}$ are in the same piece of the partition, and $\pi(q)$ forces that this is not the case (and they are talking about the same partition we started with because $\pi$ fixes $E$). Contradiction.

$\endgroup$
11
  • 1
    $\begingroup$ Justin, it would be kind of you to sketch the proof of Randall's point (3) in the link. $\endgroup$ Jan 25, 2010 at 23:17
  • $\begingroup$ do you mean how to get a model with an A satisfying (3)? $\endgroup$ Jan 25, 2010 at 23:26
  • $\begingroup$ Yes. I am clear on the usual symmetric name forcing argument for getting (1) and (2). And Dougherty suggests it is the same for (3), so I was wondering if you could give a quick sketch for the set theorists. (Otherwise, I'll just think it through myself.) $\endgroup$ Jan 25, 2010 at 23:36
  • $\begingroup$ Ok, I added a sketch (which initially was incorrect but I have edited it appropriately) $\endgroup$ Jan 26, 2010 at 1:43
  • $\begingroup$ This gives a good intuition of what is possible in ZF. And the link shows that my question came up in a discussion on sci.math in 2003.... $\endgroup$ Jan 26, 2010 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.