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?

  • 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? – Zev Chonoles Jan 25 '10 at 21:58
  • @Zev: you're right, I've edited the question. – Konrad Swanepoel Jan 25 '10 at 22:03
  • 6
    If it could be so shown, wouldn't the group identity give you a choice function? – David Eppstein Jan 25 '10 at 22:16
  • 1
    Zev, turning Konrad's semigroup into a monoid gives you the trivial monoid, since x*1 = x = s_0 for all x. – Qiaochu Yuan Jan 25 '10 at 22:46
  • 7
    @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. – Joel David Hamkins Jan 26 '10 at 13:24
up vote 146 down vote accepted

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$.

  • 6
    Fantastic! This is a great argument! It is just equivalent to AC. – Joel David Hamkins Jan 26 '10 at 0:13
  • 1
    Aha, very neat! – Konrad Swanepoel Jan 26 '10 at 8:20
  • 4
    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. – Ashutosh Jan 26 '10 at 15:08
  • 5
    I have it. Same proof. – Péter Komjáth Jun 13 '10 at 17:29
  • 3
    Hajnal now loaded his paper with Kertesz to Reseacrhgate, so it's available: researchgate.net/publication/… – Péter Komjáth Oct 10 '15 at 7:03

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.

  • 1
    Justin, it would be kind of you to sketch the proof of Randall's point (3) in the link. – Joel David Hamkins Jan 25 '10 at 23:17
  • do you mean how to get a model with an A satisfying (3)? – Justin Palumbo Jan 25 '10 at 23:26
  • 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.) – Joel David Hamkins Jan 25 '10 at 23:36
  • Ok, I added a sketch (which initially was incorrect but I have edited it appropriately) – Justin Palumbo Jan 26 '10 at 1:43
  • 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.... – Konrad Swanepoel Jan 26 '10 at 9:28

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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