Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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

 
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.