Surjections from $ \mathbb N $ to itself where each image has an infinity of antecedents in $ \mathbb N $

Question

I am interested in learning about more various examples of such functions, for example:

Let's take an enumeration of $ \mathbb N ^ 2 $ and use a projection. Then we get a surjection from $ \mathbb N $ to itself, where each image has an infinity of antecedents in $ \mathbb N $.

I am curious if there is another type of such functions which is not using explicitly a mechanism of projection ($ \mathbb Q $ projected over $ \mathbb N $ for instance).

Answer 1

While one can provide examples that don't explicitly address an enumeration of $ \mathbb N ^ 2 $ (as has been demonstrated in several comments above), nevertheless the following holds:

For a function $ f : \mathbb N \to \mathbb N $, the following are equivalent:

• for any $ m \in \mathbb N $, the preimage of $ \{ m \} $ under $ f $ is infinite;
• there exists a bijective function $ e : \mathbb N \to \mathbb N ^ 2 $ such that $ f ( n ) = p \big( e ( n ) \big) $ for all $ n \in \mathbb N $, where $ p : \mathbb N ^ 2 \to \mathbb N $ is projection on the left coordinate.

So you're asking for nothing more than various examples of enumerations of $ \mathbb N ^ 2 $. One direction of the above equivalence is already noted by yourself. For the other direction, first define the function $ g : \mathbb N \to \mathbb N $ with $$ g ( n ) = \# \{ k < n | f ( k ) = f ( n ) \} $$ for all $ n \in \mathbb N $. Then define $ e : \mathbb N \to \mathbb N ^ 2 $ with $$ e ( n ) = \big( f ( n ) , g ( n ) \big) $$ for all $ n \in \mathbb N $. The equation $ f ( n ) = p \big( e ( n ) \big) $ is an immediate consequence of the definition. If $ e ( n ) = e ( m ) $ for some $ n , m \in \mathbb N $, then by equality of left coordinates we get $ f ( n ) = f ( m ) $. Thus, if $ n < m $, we have $ \{ k < n | f ( k ) = f ( n ) \} \subset \{ k < m | f ( k ) = f ( m ) \} $ and $ g ( n ) < g ( m ) $. Similarly, if $ n > m $ we get $ g ( n ) > g ( m ) $. But by equality of the right coordinates, non of those cases can happen, and we must have $ n = m $. Therefore $ e $ is an injective function. To show that $ e $ is surjective, consider any $ m \in \mathbb N $. Since $ f ^ { - 1 } [ \{ m \} ] $ is infinite, we can define $ s : \mathbb N \to f ^ { - 1 } [ \{ m \} ] $ recursively with $$ s ( i ) = \min \left( f ^ { - 1 } [ \{ m \} ] \setminus \{ s ( k ) | k < i \} \right) $$ for all $ i \in \mathbb N $. This way, $ s $ will be a bijection, and for any $ i \in \mathbb N $ we will have $ f \big( s ( i ) \big) = m $ and $ g \big( s ( i ) \big) = i $. Therefore, any pair $ ( m , i ) \in \mathbb N ^ 2 $ will be in the range of $ e $, and thus $ g $ is surjective, which completes the proof.