0

Let $f : ℕ → P(ℕ)$ be given by $f(n) = {k*n | k ∈ ℕ}$. (P(ℕ) is the power set of the set A.)

Is f injective?

The answer to this question goes like this:

$f(n) = (n,2n,3n,4n,5n...)$

$min({ n,2n,3n,...})$ is $n$, as $n<2n<3n<....$

Suppose $f(m)=f(n)$. Then

${ (m,2m,3m,...)}={ (n,2n,3n,...)}$

smallest element of $( m,2m,3m,...)$ = smallest element of $(n,2n,3n,...)$, $m=n$.

My question is why do we focus on the smallest element of the set?

mathstudent288
  • 303
  • 2
  • 12

1 Answers1

1

We focus on it because it produces the contradiction we need. If you claim two sets are equal and I can show the smallest elements are different, it shows you are wrong, because I have identified and element that is in one set and not in the other. There may be other ways of showing the two sets are different, but this one works.

Ross Millikan
  • 374,822
  • So I could take, say, the 4th element in the set ($4n$) and show that that is equal to the 4th element of the other set ($4m$)? Would that accomplish the same thing? Once I divide by $4$ I find that $n=m$. Does choosing the smallest element in each set just skip the division by 4 step? – mathstudent288 Nov 17 '20 at 04:10
  • Sets do not have order. You could have $n=2m$, then $4n=8m$ and this element is in both sets. Yes, you can sort the sets and compare the fourth smallest of each to show they are different, but that is an added complication. – Ross Millikan Nov 17 '20 at 04:13