I am given the following problem:
Let $f$ be a function from $[0, 1]$ to $\mathbb{N}$. Prove there exists $x, y\in [0, 1]$ such that $x\neq y$ and $f(x) = f(y)$.
Clearly, this is true because $|[0, 1]| = |\mathbb{R}| > |\mathbb{N}|$, and there cannot be an injective function from an uncountable set to a countable set. But... how should I write my solution? They are asking for a proof and I do not know how to formally prove the statement above.
Thank you!
Consider $2^\omega$, the set of all binary sequences, one can inject $2^{\omega}\to [0,1]$, by mapping each binary sequence $x_{n}$, to $\sum_{n=0}^{\infty} \dfrac{x_{n}}{10^{n+1}}$ which belongs to $[0,1]$, it’s easy to check that this mapping is an injection.
So if there was an injection from $[0,1]$ into $\mathbb{N}$, there would be a surjection from $\mathbb{N}$ onto $2^\omega$, a simple diagonalization argument shows that is impossible for there to be such a surjection, therefore we have a contradiction. $\square$