In Royden's book Real Analysis, page 13, he writes that "We call two sets A and b equipotent provided there is a one-to-one mapping $f$ from A onto B Equipotence defines a equivalence relation among sets, that is, it is reflexive, symmetric, and transitive." He then uses equipotence to $\mathbb{N}$ define countably infinite.
I find out another definition of countably infinite using injection which is a one-to-one and left-total relation, not necessarily onto. But if it's not onto, how can the equipotence be symmetric?
When proving that the Cartesian product $\mathbb{N}\times\mathbb{N}$ is countably infinite, he defines a mapping $g$ by $g(m,n)=(m+n)^2+n$. This mapping from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$ is one-to-one but not onto.
$\endgroup$ 52 Answers
$\begingroup$The function isn't onto since there is no $a$, $b$ such that $g(a,b)=3$. You can see this by considering a few cases: $g(0,1)=2$, $g(1,0)=1$, $g(0,0)=0$, and $g(1,1)=5$.
However, if $g(a,b)$ is unique in $\Bbb N$ then it's possible to define a bijective mapping $f$ from the range of $g$ to $\Bbb N$ such that $f \circ g$ is onto. (I don't know whether $g(a,b)$ actually is unique in $\Bbb N$.)
Regardless of whether this function $g$ "works" or not, we can make a bijective map from $\Bbb N\times\Bbb N$ to $\Bbb N$ using the same trick as the one for proving that the rational numbers are countable. The general result is that the cross-product of two countable sets is countable.
$\endgroup$ 2 $\begingroup$I'm not sure where Royden gives the definition of countably infinite using injection. If this is in reference to Theorem 3 on page 13, I think it only says "A subset of a countable set is countable."
Consider $A \subseteq B$, with B a countable set.
In the proof he discusses two cases, one where B is finite, and the other when B is countably infinite.
In the countably infinite case, he gives a selection process that forms a one-to-one correspondence between ℕ and A. If A is not finite, we can show that not only is A countable (finite or countably infinite), it is countably infinite.
Thus, as long as B is countably infinite, A a subset of B and A not finite, we can use the selection process he mentions to create a bijection between ℕ and A.
When proving that the Cartesian product ℕ×ℕ is countably infinite, he creates an injection from ℕ×ℕ to ℕ. Thus there is a bijection from ℕ×ℕ to a subset of ℕ. Since ℕ is countably infinite, we can use the selection process mentioned above to create a bijection from this subset of ℕ to ℕ.
$\endgroup$
