When is a function a permutation of the integers?
In his 2011 paper on the Collatz conjecture here Lagarias writes;
> Collatz’s original function, which is a permutation of the integers...
But when is a function over the integers a permutation of the integers? My understanding would be that a permutation must be a bijection from a domain onto itself because only this will reposition every domain element uniquely in the range.
But if we consider the Collatz function exactly a sixth of the integers are mapped to by two distinct elements; namely every even number equivalent to $1\mod 3$, which is is mapped to by both $3x+1$ and $x/2$ e.g.the number 16.
This doesn't seem to be a permutation because $16$ and other numbers will appear multiple times in the range.
Where am I (or Lagarias) going wrong? If it's his mistake, what do you suppose he meant by this?
Collatz original function was defined as follows: Consider the infinite permutation $$ P ={1 2 3 4 5 6 \cdots \choose 1 3 2 5 7 4 \cdots} $$ taking $n\to f(n)$ where $f : \mathbb{N}^+ \mapsto \mathbb{N}^+$ is given by $$f(3n) = 2n, f(3n−1) = 4n−1, f(3n−2) =4n − 3.$$ This is different from the Collatz function defined in the $3n+1$-problem!
Reference: Jeffrey C. Lagarias: The $3x + 1$ Problem: An Annotated Bibliography (1963–1999); page 37.
Edit: A permutation of a set $X$ is an element of the group ${\rm Sym}(X)$ consisting of all bijective maps from $X$ to $X$. If $|X|=n$, then ${\rm Sym}(X)\cong S_n$, the symmetric group.