Prove/disprove: $\forall f\ \in \mathbb N ^{\mathbb R}. \forall x\in \mathbb R. \exists y\in \mathbb R ((f(x)=f(y))\wedge (x\neq y))$

Question

Prove/disprove: $\forall f\ \in \mathbb N ^{\mathbb R}. \forall x\in \mathbb R. \exists y\in \mathbb R ((f(x)=f(y))\wedge (x\neq y))$

This statement looks very similar to the definition of injective function but it has $\exists y$ instead for all, so I think it's false, take $f(x)=\lfloor x\rfloor$ then the statement is false $\forall x\ge 1$.

I also tried to make it harder and prove:

$\forall f\ \in \mathbb N ^{\mathbb R}. \forall x,y \in \mathbb R ((f(x)=f(y))\wedge (x\neq y))$

Which I think is true, since the reals are compact and the cardinalities are different, is the way to do this is to suppose there exists a function such that $f(x)=f(y)\to x=y$? but I don't see how to reach the contradiction..

Answer 1

Hint: What happens if you map all real numbers to a given integer, except for one real number that you map to a different integer?

Answer 2

Suppose the statement isn't true. Then, as you noted, there exists a function $\;f:\Bbb R\to\Bbb N\;$ which is injective.

But then this carries that $\;2^{\aleph_0}=|\Bbb R|\le|\Bbb N|=\aleph_0\;$ , and this is very not true.

Answer 3

Look at the negation of the proposition. $$ \exists f\ \in \mathbb N ^{\mathbb R}. \exists x\in \mathbb R. \forall y\in \mathbb R ((f(x)\neq f(y))\vee (x= y)) $$ It is true. Just build a function with such property. For exemple, $$ f(x)= \left\{ \begin{array}{cc} 0 & \mbox{ if } x=0,\\ \left\lfloor x \right\rfloor^2+1 & \mbox{ if } x\neq 0 \end{array} \right. $$ So if the negation is true the statement is false.