# Bijective functions over naturals

It is easy to prove that one-to-one (bijective) functions $f : \mathbb{N} \to \mathbb{N}$ are uncountable using a diagonalization argument like this:

Suppose that an enumeration $f_1,f_2,f_3,...$ exists; start with $A_1 = \mathbb{N} = \{1,2,3,...\}$ and iteratively define the one-to-one function $g(n)$ in this way:

• $g(2n-1) = \min \{ y \in A_n \mid f_n(2n-1) \neq y \}$;
• $g(2n) = \min \{ y \in A_n \setminus \{g(2n-1)\} \mid f_n(2n) \neq y \}$ and set
• $A_{n+1} = A_n \setminus \{ g(2n-1),g(2n)\}$

I didn't think of it too much, but:

Question 1: Is there a closed form to define a one-to-one "diagonal" function $g$ that differs from every $f_i$ in at least one point? (something like the standard diagonal function that can be use to prove that generic functions $\mathbb{N} \to \mathbb{N}$ are not countable: $g(i) = f_i(i)+1$)

Question 2: If such a closed form doesn't exist, is there a way to formally prove it?

-
What precisely counts as "closed form"? – Hurkyl Jan 6 '14 at 17:40
@Hurkyl: see the two answers below, they are "closed" (non-iterative) definitions of $g$ (but they are wrong because I wrongly used "injective" instead of "bijective" in the title of the question) – Vor Jan 6 '14 at 18:43

Consider the function $$g(n)= \sum_{k\leq n} f_k(k)+1$$

-
Are you sure that your $g(n)$ is injective? Suppose that $f_1 = \{1,2,3,4...\}, f_2 = \{2,1,3,4,....\}$ then it seems that for all n $g(n) \neq 1$ – Vor Jan 6 '14 at 18:31
it is strictly increasing, so it is injective. – themaker Jan 6 '14 at 18:38
Sorry, I found that I used "injective" instead of bijective – Vor Jan 6 '14 at 18:39
Ok, then I understand your remark to my post. – Jeremy Daniel Jan 6 '14 at 18:39
@Vor in that case, your construction doesnt work either. For example, if $f_n(n)=1 \forall n\in \mathbb N$, then $g(n)\neq 1\forall n\in \mathbb N$ – themaker Jan 6 '14 at 18:46

You can consider the function $g(n)$ which is $2n$ if $f_n(n) \neq 2n$ and $2n+1$ if $f_n(n)$ is $2n$. This $g$ is clearly injective and by construction is different from $f_n$ at $n$. However, this $g$ is not the $g$ you define but it has the same properties.

-
Sorry, I found that I used "injective" instead of bijective; your answer doesn't work (for all n $g(n) \neq 1$) – Vor Jan 6 '14 at 18:37