5
$\begingroup$

Can anybody please give me an example of a binary operation under which N forms a group? More generally, how to find some operations to make possibly any set a group?

$\endgroup$
1
  • 12
    $\begingroup$ Take your favorite bijection of N with Z (integers under addition) and transfer the group structure via this bijection. $\endgroup$ May 23, 2010 at 10:59

5 Answers 5

18
$\begingroup$

As explained by Arturo, a simple example of a group structure on N is the operation a ⊕ b = f-1(f(a) + f(b)) where f:NZ is defined by f(2n) = n and f(2n+1) = -n.

The statement that any nonempty set admits a group structure is equivalent to the Axiom of Choice! This is explained in this answer.

$\endgroup$
4
  • $\begingroup$ Right: when I assume the given set has a cardinality and that we can find a bijection from $S$ to $\mathbb{Z}^{(|S|)}$, I am invoking choice a few times. $\endgroup$ May 23, 2010 at 1:36
  • $\begingroup$ (If you prefer N to include 0, define f(2n-1) = -n instead.) $\endgroup$ May 23, 2010 at 1:36
  • $\begingroup$ @Arturo: More precisely, you're invoking the fact that every infinite S has the same size as the family of all its finite subsets. $\endgroup$ May 23, 2010 at 1:39
  • $\begingroup$ @François G. Dorais, nice to learn it. Thanks. $\endgroup$
    – dexter
    May 23, 2010 at 2:21
23
$\begingroup$

Perform the usual addition of natural numbers in decimal representation, but let's forget about carrying the extra digit in the next column. So e.g. 356+75=321 and 123+987=0 . Note: This is very particular, as it is linked to base 10; but makes the example very concrete and quick. The poster asked for an example, and in my view, for an example, simplicity is prior to generality.

$\endgroup$
9
  • 1
    $\begingroup$ I didn't vote you down, but I think your answer would be improved if you replaced the entire last sentence with a description of the resulting group structure (i.e., an infinite sum of order $m$ cyclic groups). $\endgroup$
    – S. Carnahan
    May 24, 2010 at 1:47
  • $\begingroup$ You are certainly right, but I assumed that that point must be clear for everybody here. But say that asking for a + deserves a - , even if it was a joke. So now I am doubtful about changing the last sentence, as it is somehow instructive as it is :) / :( $\endgroup$ May 24, 2010 at 3:38
  • 1
    $\begingroup$ Actually my last sentence didn't express well what I meant, so I rewrite it (and incidentally dropped the request of +1). $\endgroup$ May 24, 2010 at 6:34
  • 1
    $\begingroup$ @Zsbán: It is associative: 16+6=12 $\endgroup$ May 24, 2010 at 11:10
  • 3
    $\begingroup$ Well for me 0 is a natural numer so I'd keep it in there if you don't mind ;) $\endgroup$ May 25, 2010 at 20:49
18
$\begingroup$

A useful one is the "nim sum".

$\endgroup$
2
11
$\begingroup$

There are groups of any size (except $0$): for finite ones, you can always take the cyclic groups. For infinite ones, to get a group of cardinality $\kappa\geq\aleph_0$, just take the direct sum of $\kappa$ copies of $\mathbb{Z}$. Given a set $S$ of cardinality $\lambda$ (finite or infinite), pick a bijection $f$ from $S$ to a group $G$ of cardinality $\lambda$, and define the operation on $S$ by $a*b = f^{-1}(f(a)f(b))$.

$\endgroup$
7
  • 3
    $\begingroup$ Well, except there are no groups of cardinality $0$, of course. $\endgroup$ May 23, 2010 at 1:21
  • $\begingroup$ But we still need to exhibit a group $G$ for each infinite cardinality $\lambda$. I don't know anything about set theory (as will become clear, I don't even know what the word "cardinality" means), but here's something: For the countably infinite cardinality, take $\mathbb{Z}$ with addition; for uncountably infinite cardinalities $\lambda$, assuming that $\lambda$ is the cardinality of the power set of some other smaller cardinality, then the group of automorphisms of a set of that smaller cardinality should have cardinality $\lambda$. But I don't know if my assumption is justified. $\endgroup$ May 23, 2010 at 1:24
  • 1
    $\begingroup$ First: I did exhibit a group $G$ for each infinite cardinal $\lambda$: the direct sum of $\lambda$ copies of $\mathbb{Z}$, endowed with the usual structure, has cardinality $\lambda$ (the direct sum is the set of all $\lambda$-tuples, all but finitely many equal to $0$. Second: in ZFC you cannot prove that every infinite cardinal is the cardinal of a power set. If the Continuum Hypothesis is false, for example, then there would be no set $S$ such that $P(S)$ has cardinality $\aleph_1$. And if you assume the Generalized Continuum Hypothesis, then no set would have cardinality $\aleph_{\omega}$. $\endgroup$ May 23, 2010 at 1:30
  • $\begingroup$ @Kevin: I assume, by the way, that by "automorphisms of a set" you mean all bijections from the set to itself. $\endgroup$ May 23, 2010 at 1:31
  • $\begingroup$ @Pete: quite right; I edited the answer to reflect the exception. $\endgroup$ May 23, 2010 at 1:33
4
$\begingroup$

So far, all the answers have taken the following form: you just biject N with some countably infinite group. But what if one regarded that as "cheating" and asked for a truly "natural" group operation on N? So far, I think Pietro Majer's answer comes closest, since his bijection with an infinite product of cyclic groups of order 10 is fairly natural (at least in the sense of "familiar"). But can one do any better than this?

Here is an attempt to argue that there is no 100% natural group structure on N. (I don't claim that this is surprising.)

First, we need to choose an identity element. The identity element is a privileged element of the group, so for the choice to be natural it should be a privileged element of N. The only privileged element of N is 1 (for me the natural numbers start at 1) so we are forced to choose that. Now let's consider the following question: what is the inverse of 2? I think there are two possible natural answers, namely 2 itself and 3. (One is the smallest element you can choose, and the other is the smallest element that is not equal to 2.) If we choose 2 and continue, then perhaps we'll end up with the binary version of PM's answer (except that everything would be shifted by 1 because of my insistence on making 1 the smallest natural number -- perhaps that was silly). So perhaps, contrary to my original intention, that is an argument that PM's answer is (apart from taking base 10) the most natural thing one can do, and not too unnatural.

If we go for 3, then there doesn't seem to be any natural choice for the order of 2 other than infinity. So then we need to keep powers of 2 away from powers of 3. The natural way of doing that looks like actually using the multiplicative structure of N. But then we get into trouble later, since 2*3 will be 1, so our treatment of 6 becomes a bit arbitrary. Or at least, I think it does. An implicit question here: is there some optimally natural way of putting a group structure on N in such a way that every element has infinite order? Perhaps the bijection-with-Z answer is the best one can do.

$\endgroup$
2
  • 8
    $\begingroup$ One can argue that the nim sum (strictly speaking on $\lbrace 0 \rbrace \cup \mathbb{N}$) gives a natural group structure since the nim sum of two numbers is recursively defined to be the smallest number that it could possibly be. $\endgroup$ May 24, 2010 at 9:04
  • $\begingroup$ Ah -- I had a look at the Wikipedia article on those but should have looked more carefully. $\endgroup$
    – gowers
    May 24, 2010 at 10:27

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