[Math] Countable sets: Show there exists a bijection

elementary-set-theory

Prove that a nonempty set $T_1$ is finite if and only if there exists a bijection from $T_1$ onto a finite set $T_2$.

Edit of the foward direction
Proof: ($\rightarrow$)- Assume that $T_1$ is a nonempty finite set where $T_1=\{a_1,…,a_n| n\in\mathbb{N}\}$. By definition there exists a bijection from the set of natural numbers to $T_1$. Let $f:T_1\rightarrow\mathbb{N}_m$ where $f(a_m)=m$ where $1\leq m \leq n$. If we let $\mathbb{N_m}=T_2$, we see that $T_2$ is clearly finite since there is one to one correspondence. Thus existence is proven

Edit of the foward direction
$(\leftarrow)$ Assume there exists a bijection from $T_1\rightarrow T_2$ where $T_2$ is a finite set and since $T_2$ is finite there exists a bijective function $g:T_2\rightarrow \mathbb{N}_m$ where $\mathbb{N_m}=\{1,…,m| m\in\mathbb{N}\}$ Since $f$ and $g$ are bijective functions then $f o g$ exists and it is bijective function from $T_1\rightarrow \mathbb{N}_m$. Thus $T_1$ is finite since $\mathbb{N}_m$ is finite..

Would this be right?

Best Answer

EDIT: I noticed that your book is not using the usual set-theoretic definition of natural numbers, where $n = \{0,1,2,\ldots, n-1\}$. Namely, $0$ is not considered to be a natural number, so the prototypical $n$-element set is the set $\{1,\ldots,n\}$ rather than $n$ itself. I will update my answer to reflect this.

I think you are making this more complicated that it needs to be. The notion of countability does not seem to be relevant. As you said, we define a set $x$ to be finite if there is a bijection between $x$ and some natural number $n \in \mathbb{N}$ (or it is empty.) Let $x$ be a nonempty set.

If $x$ is finite, then there is a bijection from $x$ onto a finite set $y$: namely, let $y=x$ and consider the identity function.

Conversely, assume there is a bijection $f$ from $x$ onto a finite set $y$. By definition of "finite" there is a bijection $g$ from $y$ onto the set $\{1,\ldots,n\}$ for some natural number $n$. You can then show that the composition $g \circ f$ is a bijection from $x$ onto the set $\{1,\ldots,n\}$, so $x$ is finite as well.


One problem with your argument for the forward direction is that the theorem you are applying deals with countable sets rather than finite sets, so you cannot use it to conclude that there is a bijection from anything to a finite set. In fact, the theorem is irrelevant. I didn't finish reading the rest of this direction.

Your argument for the reverse direction is vague. You are proving that something is finite, so you should mention some natural number $n$, some set of the form $\{1,\ldots,n\}$, and some bijection between this set and some other set.

Related Question