4
$\begingroup$

Prove the following implication by induction on $m$:

If there exists an injection $N_m \rightarrow N_n$, then $m \le n$.

$N_n$ and $N_m$ are sets with $n$ and $m$ elements, respectively.

I know how to do proofs by induction, I'm just struggling with the inductive step. So far I have the predicate P(n) = If there exists an injection $N_m \rightarrow N_n$, then $m \le n$.

I proved the base case "P(1) = If there exists an injection $N_1 \rightarrow N_n$, then $1 \le n$" sloppily by saying no element in $N_n$ could be assigned to more than one element of $N_1$ because there is only a single element in $N_1$. There must at least one element in $N_n$ in order for it to be a function, so $1 \le n$.

So I know the inductive hypothesis is P(k) = If there exists an injection $N_k \rightarrow N_n$, then $k \le n$. Now I need to prove P(k+1) = If there exists an injection $N_{k+1} \rightarrow N_n$, then $k+1 \le n$, but I'm clueless about how to do this step.

  • 1
    I'm curious as to what you've tried. Perhaps start with providing definitions for what being an injection means, and what "base case" you can use. Also, please clarify whether you are struggling with the notion of an injective function, or how to proceed with a proof by induction on $m$, or both...2012-11-04
  • 0
    Sorry amWhy, I edited the post with what I've tried.2012-11-04
  • 1
    Great! That helps us help you! Thanks for being responsive to suggestions!2012-11-04
  • 0
    Yes, you're correct. You need to establish that, assuming P(k) is true, then P(k+1) is true. Just a typo perhaps, but you need to show that if there exists an injection $N_{k+1} \to N_n$ then $k+1 \leq n$. (I say that because what you've got in your edit is $N_k + 1 \to N_n$. For subscripting more than one character, you need to include, all characters in { }, like this `$N_{k+1} \to N_n$`.) Note that you can use take as given that P(k) is true. You need only rely on the definition of an injection...2012-11-04

2 Answers 2