0

The question: suppose $S$ is a set and $f(s): S \rightarrow \mathbb{N}_n$ is an injection. Then $|S|$ must be finite.

My proof: I will proceed by contradiction. Presume that $|S|$ is infinite. By the definition of an injection, every $s\in S$ must map to a unique $N\in \mathbb{N}_n$. By the pigeonhole principle, this is only possible if $|S|\le n$, which contradicts the presumption. Therefore $|S|$ must be finite.

Michael Stachowsky
  • 2,943
  • 1
    Can you rigorously prove the pigeonhole principle yourself? If not, then I strongly recommend figuring out a proof that doesn't rely on it. There are some basic concepts here you need to master, and using a tool you don't understand yourself will not allow you to master them. How you should prove this without it will depend on which definition of finite and infinite you are using. – Paul Sinclair Feb 08 '20 at 04:13
  • You are correct that I cannot rigorously prove it. I'm clearly missing some subtleties. What are some pitfalls of my proof? – Michael Stachowsky Feb 08 '20 at 05:27
  • Logically, it is okay. The only problem is that by pulling out a name-brand theorem you know but do not fully understand, you bypassed the real purpose the exercise, which is for you to develop an understanding of cardinality and the tools one uses to work with it. The main tool is the well-ordering of cardinal numbers, along with its sibling, induction (ordinary or transfinite). I could give you some hints as to what you could do, except as I said before, I don't know what definition of finite and infinite youa re using (are a couple that are common usage). – Paul Sinclair Feb 08 '20 at 14:16
  • Interesting. I know of multiple definitions of Infinity but not of finite. I'll look into it more. A proof I've seen had included creating a bijection using S. But to me it seemed irrelevant. Informally, of I have more elements in S than in N_n I can't have an injection and I'm done, but I recognize that is not rigorous. – Michael Stachowsky Feb 08 '20 at 19:00
  • "infinite" $\iff$ "not finite". To define infinite is to define finite, and vice versa. The problem with your informal argument is the question of what does it mean "to have more elements". What you dismissed as irrelevant was the answer to that question. – Paul Sinclair Feb 08 '20 at 19:07

0 Answers0