1
$\begingroup$

I am trying to prove this by contradiction. Can I somehow do it by restricting the domain and using a corollary that states if X and Y are non-empty finite sets and there exists an injection $f: X \rightarrow Y$ then $\lvert X\rvert \le \lvert Y\rvert$. I am just struggling because most of the theorems I know only apply to finite sets, and the set of integers is not finite.

$\endgroup$
2
$\begingroup$

Suppose that $|X|=n$ for some finite $n$. Then, $$ X\supset f(\mathbb{Z^+})\supset f(\{0,1,2,\ldots,n\})\implies |X|\geq|f(\{0,1,2,\ldots,n\})| $$ which is a contradiction because by injectivity $f(\{0,1,2,\ldots,n\})$ is a set of $n+1$ (distinct) elements.

$\endgroup$
  • $\begingroup$ G++d way to solve the case. :-) $\endgroup$ – mrs Nov 19 '16 at 9:04
2
$\begingroup$

If such that function is an injection so $$f:\mathbb{Z}^{+}\to\text{Im}(f)\subset X,~~~~|\mathbb{Z}^{+}|=\infty$$ is an isomorphism so $X$ cannot be a finite set.

$\endgroup$
  • $\begingroup$ Come by and ping me from the constructive feedback chatroom! $\endgroup$ – Namaste Nov 18 '16 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.