Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is my first question and I hope this question is not too brief to be acceptable:

There are well-known bijections $\mathbb{N \times N \to N}$ and well-known associative compositions on countably infinite sets. What if we combine the two properties?

Is there a bijective function $f\colon \mathbb{N \times N \to N}$ which is also associative: $$f(x,f(y,z)) = f(f(x,y),z)\quad\text{ for all } \quad x,y,z \in \mathbb{N}\:?$$

Thanks in advance!

share|cite|improve this question
up vote 7 down vote accepted

Suppose $f$ is associative and bijective. For any $x,y, z \in \mathbb{N}$, we have $f(x,f(y,z))=f(f(x,y),z)$ by associativity. Thus by injectivity we have $x=f(x,y), f(y,z)=z$ for all $x, y, z$. But this is impossible, since it implies for example that $f(1,2)=1$ and $f(1,2)=2$.

share|cite|improve this answer
Neat! Thank you. Now I feel a bit silly... – Heinrich Nov 9 '12 at 1:12
This works for every set with $\geq 2$ elements. – Martin Brandenburg Jun 13 '13 at 23:31

Your Answer


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.