Countably infinite groups such that every element has order 2 are isomorphic
I once saw the following puzzle:
Given a list of 2n-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, [ \bigoplus_{i=1}^{2n-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 (\mathbb{N}, \oplus) is a abelian group.
Is this the unique function to solve this problem?
In some way, yes. Here is a theorem.
The countably infinite group G such that g^2 = 1 for all g\in G is (\mathbb{N}, \oplus) up to isomorphism.
See the answer by Pete Clark for the proof.