1
$\begingroup$

I would like to know if the my proof to the below problem is correct.

Prove that a non-empty set $T_{1}$ is finite if and only there is a bijection from $T_{1}$ onto a finite set $T_{2}$.

Proof.

(1) Suppose that $T_{2}$ is a finite set with $m$ elements. Then there exists a bijection $f:\mathbb{N}_{m}\rightarrow{T_{2}}$.

$f$ is injective from $\mathbb{N}_{m}$ into $T_{2}$. If $i\ne{j}$ then $f(i)\ne{f(j)}$.

$f$ is surjective from $T_{2}$ onto $\mathbb{N}_{m}$. For all elements $y\in{T_{2}}$, there exists $i\in{\mathbb{N}_{m}}$, where $f(i)=y$.

(2) Assume, there exists a bijection $g:T_{1}\rightarrow{T_{2}}$.

(3) If (1) and (2) hold, the composition $g(f(i))$ is also a bijection from $\mathbb{N}_{m}$ to $T_{1}$.

Hence, $T_{1}$ is a finite set.

$\endgroup$
  • 1
    $\begingroup$ Yep. That's basically it. You don't need to define injectivity and surjectivity in the first part. Depending on your text you may or may not be expected to verify that the composition of bijections is a bijective (which is pretty basic and easy if you understand the definition of bijection). $\endgroup$ – fleablood Sep 17 '16 at 3:50

Your Answer

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

Browse other questions tagged or ask your own question.