2

Definition of $\mathbb{N}_m$ is a set $\{x \in \mathbb{Z}^+ | 1 \leq x \leq m\}$.

The book "An introduction mathematical reasoning" by Eccles has this proof written out on 3 pages. They use induction on $n$ to prove it. But I fail to see why you need to go to such lengths to prove it.

In my head, without providing a rigorous proof, this is quite clear just from the definition of injection. Namely, given function $f: X \rightarrow Y$, it is injection if: $\forall x_1,x_2 \in X, (x_1 \neq x_2 \implies f(x_1) \neq f(x_2))$. Meaning each element in $\mathbb{N}_m$ will map to at most one element in $\mathbb{N}_n$. Therefore, $|N_m| \leq |N_n| \implies m \leq n$. Is this intuition valid? Because if not, then that would explain the lengthy proof in the book.

Naz
  • 3,289
  • These arguments tend to be a function of the axiom system involved. That is, the exact list of things you are meant to assume before starting the proof. – lulu Aug 29 '22 at 19:53
  • If you try to prove the contrapositive, you will see that the argument you use in your proof can be made quite rigorous. – MasB Aug 29 '22 at 20:52
  • You're proving the pigeonhole principle here, which is an important result. The longer proof may be to avoid using other axioms or counting arguments, or simply to give a larger example using induction. It's hard to say without more information. – CyclotomicField Aug 29 '22 at 22:23
  • I believe you are right @CyclotomicField. I also thought of the author giving the longer proof as an example of how it may go if we used a different proving technique / wanted to be super rigorous. But I avoided mentioning this in my question to avoid biasing anyone. – Naz Aug 29 '22 at 23:21
  • I think proving, via axioms, that $|f(A)| \le |A|$ and that if $B \subset C$ then $|B| \le |C|$ may take up a good part of three pages. Your intuition is spot on but it is assuming those two concepts, both of which are pretty danged obvious but.... none the less have to be formally proven... and that is why these basic proofs are so frequently so very long. – fleablood Aug 30 '22 at 00:05

0 Answers0