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?

  • $\begingroup$ If there exists an injection $S \to \mathbb N$, $S$ is not necessarily countable. The empty set satisfies this property. You probably mean an injection $\mathbb N \to S$ ; that would make more sense. Similarly, if there exists a surjection $\mathbb N \to S$, $S$ is not necessarily countable ; $S = \{1\}$ satisfies this property. A surjection $S \to \mathbb N$ would give you the property that $S$ is infinite, although we don't know if it would be countable. $\endgroup$ – Patrick Da Silva Oct 1 '13 at 17:08
  • $\begingroup$ you mean the theorem? $\endgroup$ – user60887 Oct 1 '13 at 17:10
  • $\begingroup$ I mean the theorem you're trying to prove, as stated, is false. Just take $S = \{1\}$ ; there exists an injection from $\{1\}$ to $\mathbb N$ ; just map $1$ to $1$, the map is clearly injective, but $\{1\}$ is not countable. Similarly, you can map $\mathbb N \to \{1\}$ by sending everything to $1$ and the map will be surjective, but $\{1\}$ is again not countable. $\endgroup$ – Patrick Da Silva Oct 1 '13 at 17:11
  • 1
    $\begingroup$ Finite. My book states a set is countable if it is either finite or denumerable. $\endgroup$ – user60887 Oct 1 '13 at 17:14
  • 1
    $\begingroup$ A set that is finite if its either empty or has n elements where $n\in\mathbb{N}$ $\endgroup$ – user60887 Oct 1 '13 at 17:20

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.

  • $\begingroup$ So my proof works but I need to clean it up then? $\endgroup$ – user60887 Oct 1 '13 at 17:39
  • $\begingroup$ yeah in our book we don't consider 0 to be a natural number. $\endgroup$ – user60887 Oct 1 '13 at 17:41
  • $\begingroup$ @user60887 As far as I understand your proof, I don't think it is correct. I will edit my answer to explain why. $\endgroup$ – Trevor Wilson Oct 1 '13 at 17:43
  • 1
    $\begingroup$ @user60887 I think you need to worry about more than correctness. The statement is very easy, as Trevor's proof indicates. Your proof, even if correct, is a rather confusing way of going about it, and indicates you do not understand these concepts as well as it would be desirable. You can always go to the corner grocery by taking a plane to the Patagonia, and hitchhiking back; it does not mean it makes sense to proceed that way. $\endgroup$ – Andrés E. Caicedo Oct 1 '13 at 17:43
  • 1
    $\begingroup$ @user60887 The moral of the story is that you don't need to read any of that stuff after definition 1.3.1 in order to prove this proposition. $\endgroup$ – dfeuer Oct 1 '13 at 19:03

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.