Simple Question on 1 - 1, Increasing integer features

So my mind is tired which is possibly why this feels like a large bargain to me now, yet I simply can not overcome this thinking:

Suppose you have $$F = \{\text{all } 1\text{-}1, \text{increasing functions } \Bbb N \to \Bbb N\}$$

$1$ - $1$: suggests that every value of the domain name maps to some one-of-a-kind value of the array and also every value of the array amounts to $f(n)$ for some $n$. Therefore, given that $f$ is $1$ - $1$ and also raising, the only function that exists is the unimportant function, $f(n) = n$.

Please inform me why that is incorrect.

(ftr, this isn't the research inquiry. I am confirming uncountability of $F$, which is why my mind - fart is troubling me extra)

Answer: @Prometheus left this as a comment and afterwards removed it, possibly due to the fact that he really did not desire to be related to stupidness as wonderful as mine. The mistake is that I'm thinking one - to - one = > onto, which it plainly does not. gathers in a round and also sobs

2019-05-18 21:37:17
Source Share
Answers: 2

First, a theory: $|P(\mathbb{N})| > \aleph_0$ (this is Cantor is theorem related to the all-natural numbers. I will certainly not experience the evidence below.)

Currently a 2nd theory: Let $A$ be the set of all limited or carbon monoxide - limited (that is - the enhance is limited) parts of the all-natural numbers, after that $A$ is countable.

Evidence: The set of all parts of dimension $n$ can be mapped to a part of $\mathbb{N}^n$ (as photos of features from $n \to \mathbb{N}$), given that this is a countable set itself, and also we have countably several $n$ after that we have countably several limited parts of the all-natural numbers, and also given that each of those can be mapped to its enhance - we have actually the required evidence.

Effect: There are uncountably several parts of $\mathbb{N}$ which are boundless and also their enhance is additionally boundless.

For each and every of these parts we understand that we can get it, and also hence have a 1 - 1 function from $\mathbb{N}$ onto it, which is additionally raising.

Consequently, the set of all features 1 - 1 and also raising from $\mathbb{N}$ to itself is vast.

(I wish this is clear, otherwise - allow me recognize which aims requires more development.)

2019-05-21 06:56:39

The inquiry has actually been addressed in the remarks. The features are not thought to be onto.

Below is a tip for a strategy that is various from Asaf's: You can take into consideration the series of distinctions $f(n+1)-f(n)$. It suffices to limit to features that just increase by 1 or 2 at each integer.

2019-05-21 06:54:29