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.

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?

share|improve this question
    
What precisely counts as "closed form"? –  Hurkyl Jan 6 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 at 18:43

2 Answers 2

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

share|improve this answer
    
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 at 18:31
    
it is strictly increasing, so it is injective. –  themaker Jan 6 at 18:38
    
Sorry, I found that I used "injective" instead of bijective –  Vor Jan 6 at 18:39
    
Ok, then I understand your remark to my post. –  Jeremy Daniel Jan 6 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 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.

share|improve this answer
    
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 at 18:37

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.