0
$\begingroup$

If a set is an infinite set, is it the case that we can always find a 1-to-1 fxn from the said infinite set to the set of natural numbers N = {1,2,3}?

I know that if the infinite set is such that set N is a proper subset of it (such as set Z of integers), then there must be a 1-to-1 correspondence. But what if otherwise?

$\endgroup$
2
$\begingroup$

No, such a function does not necessarily exist.

The set of natural numbers $\mathbb N$ is a proper subset of the real numbers $\mathbb R$, but there is no one-to-one function $\mathbb R \to \mathbb N$. The proof is quite famous and is known as "Cantor's diagonal argument."

This examples also shows that your assumption in the second paragraph is incorrect.

$\endgroup$

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.