Countably infinite groups such that every element has order 2 are isomorphic

I once saw the following puzzle:

Problem1

Given a list of $2 n - 1$ non-negative integers. Every number except one appeared twice. The memory that contain the integers are read only. Can you use $O (1)$ additional space to find the integer that only appeared once?

The solution was the xor function.

If $a_{j}$ is the number that didn’t appear twice, $i = 1 ⨁ 2 n - 1 a_{i} = a_{j}$

The reason was because xor have the following property. $a \oplus b = b \oplus a$ , $a \oplus a = 0$ and $0 \oplus a = a$ for all $a, b \geq 0$ . One can see $(N, \oplus)$ is a abelian group.

Is this the unique function to solve this problem?

In some way, yes. Here is a theorem.

Theorem2

The countably infinite group $G$ such that $g^{2} = 1$ for all $g \in G$ is $(N, \oplus)$ up to isomorphism.

See the answer by Pete Clark for the proof.

Posted by Chao Xu on 2011-06-11.

Tags: group theory, puzzle.