For any n, m given ##I_n \thicksim I_m##, prove that ## n=m##

  • Thread starter Thread starter issacnewton
  • Start date Start date
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
2 replies · 1K views
issacnewton
Messages
1,035
Reaction score
37
Homework Statement
Prove that for all natural numbers n and m, if ##I_n \thicksim I_m##, then ## n=m##.
Relevant Equations
Definition of equinumerous sets and definition of bijection
Let ##n, m## be arbitrary in ##\mathbb{N}##. Assume that ##I_n \thicksim I_m##. We are given that

$$ I_n = \big\{ i \in \mathbb{Z}^+ | i \leq n \big\} $$
$$ I_m = \big\{ i \in \mathbb{Z}^+ | i \leq m \big\} $$

These are following sets

$$ I_n = \bigg \{ 1,2,3,\ldots, n \bigg \} $$
$$ I_m = \bigg \{ 1,2,3,\ldots, m \bigg \} $$

Now, assume that ##n < m##. Since ##I_n \thicksim I_m##, there is a bijection from ##I_n## to ##I_m##. Since there are less members in ##I_n## than in ##I_m##, we can map these ##n## members to first ##n## members in ##I_m##. Then we are left with ##m-n## members in ##I_m## which do not have any pre image in ##I_n##. But since the function is onto, this is a contradiction and hence ## n \nless m ##. Similar argument can be given when ##n > m##. So we also prove that ## n \ngtr m##. So, we must have ##n = m##. Is this a valid proof ?
 
Physics news on Phys.org

Discussion

IssacNewton said:
Homework Statement:: Prove that for all natural numbers n and m, if ##I_n \thicksim I_m##, then ## n=m##.
Relevant Equations:: Definition of equinumerous sets and definition of bijection

Let ##n, m## be arbitrary in ##\mathbb{N}##. Assume that ##I_n \thicksim I_m##. We are given that

$$ I_n = \big\{ i \in \mathbb{Z}^+ | i \leq n \big\} $$
$$ I_m = \big\{ i \in \mathbb{Z}^+ | i \leq m \big\} $$

These are following sets

$$ I_n = \bigg \{ 1,2,3,\ldots, n \bigg \} $$
$$ I_m = \bigg \{ 1,2,3,\ldots, m \bigg \} $$

Now, assume that ##n < m##. Since ##I_n \thicksim I_m##, there is a bijection from ##I_n## to ##I_m##. Since there are less members in ##I_n## than in ##I_m##, we can map these ##n## members to first ##n## members in ##I_m##. Then we are left with ##m-n## members in ##I_m## which do not have any pre image in ##I_n##. But since the function is onto, this is a contradiction and hence ## n \nless m ##. Similar argument can be given when ##n > m##. So we also prove that ## n \ngtr m##. So, we must have ##n = m##. Is this a valid proof ?
Looks fine to me.