Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
4  
If it could be so shown, wouldn't the group identity give you a choice function? –  David Eppstein Jan 25 '10 at 22:16
    
@David: if $S$ is non-empty, I can take an element $s_0$ from $S$, and define an operation $x\ast y=s_0$ for all $x,y\in S$. This gives me a semigroup on $S$, and can be done without the axiom of choice. –  Konrad Swanepoel Jan 25 '10 at 22:23
5  
@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

3 Answers 3

up vote 98 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) -> (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 $o$ 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 o \alpha \in \aleph(X)$ since otherwise we get an injection of $\aleph(X)$ into $X$. Using $o$, 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 o \alpha = \beta$. Here, < is the lexic well ordering on the product $(\aleph(X))^{2}$. This induces a well ordering on $X$.

share|improve this answer
3  
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
3  
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
1  
I think this proof is Hajnal and Kertesz'. Some indirect evidence via Google: in these lecture notes on set theory on the web (in German) users.math.uni-potsdam.de/~raesch/logik/Seminarbericht.pdf on pages 36-37 the same proof occurs. The only reference there is to the paper of Hajnal and Kertesz. Somebody with access to this paper out there? –  Konrad Swanepoel Jan 26 '10 at 21:36
5  
I have it. Same proof. –  Péter Komjáth Jun 13 '10 at 17:29

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.

share|improve this answer
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

I'm not sure what to make of the part about the subsets of $S$ under symmetric difference - yes, they form a group, but I don't believe that imparts a group structure on $S$ itself - but the answer to your main question is yes. Simply declare one element to be the identity and make the rest equal to powers of some other element - in other words, the set $S$ can made into the cyclic group of order $|S|$.

share|improve this answer
2  
What if $S$ is uncountable? –  Konrad Swanepoel Jan 25 '10 at 22:05
    
Cyclic groups, by definition, are countable. –  HJRW Jan 25 '10 at 22:05
2  
In ZFC, any infinite set $S$ has the same cardinality as the set of finite subsets of $S$. In fact, I think it is equivalent in ZF to the axiom of choice. –  Konrad Swanepoel Jan 25 '10 at 22:06
    
Ach, ok - reading the edited question, I see the difficulty now. –  Zev Chonoles Jan 25 '10 at 22:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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