Problem on a set which is a subset of a finite set

  • #1
issacnewton
983
22
Homework Statement:
Prove that if ##n \in \mathbb{N}## and ##A \subseteq I_n##, then ##A## is finite and ##|A|\leq n ##. Furthermore, if ##A \ne I_n##, then ##|A| < n##. We are given that
$$ I_n = \big \{ i \in \mathbb{Z}^+ | i \leq n \big \} $$
Relevant Equations:
Definition of a finite set and definition of bijections
Here is my attempt. Since we have to prove that ##A## is finite, we need to prove that there exists some ##m \in \mathbb{N}##, such that there is a bijection from ##A## to ##I_m##. And hence we have ##A \thicksim I_m##. Now, since there are ##n## elements in ##I_n##, number of elements in ##A## are less than or equal to ##n##. So, we have ## |A|\leq n ##. Let, ##|A| = m##. Now, we can construct a function from ##A## to ##I_n##, such that ##m## elements in ##A## are paired with first ##m## members in ##I_n##. And, we see that the first ##m## members in ##I_n## is the set ##I_m##. So, the function would be one to one and onto and hence we have ##A \thicksim I_m##. Which proves that ##A## is a finite set. Furthermore, if ##A \ne I_n##, then ##A## is a strict subset of ##I_n## and ##A## would have less number of elements than ##I_n##. So, we have ##|A| < n##. Is the proof valid ?

Thanks
 

Answers and Replies

  • #2
WWGD
Science Advisor
Gold Member
6,291
8,135
I don't know if you're allowed to use this but I think inclusion/exclusion would do it since it applies to finite sets.
 
  • #3
issacnewton
983
22
WWGD, thanks, but is the proof presented here valid ?
 
  • #4
WWGD
Science Advisor
Gold Member
6,291
8,135
This is a tricky issue because it depends on all the definitions, results and theorems available to you. Still, from what I have read, it seems you're assuming what you want to prove: ( bold is mine).

"Here is my attempt. Since we have to prove that A is finite, we need to prove that there exists some m∈N, such that there is a bijection from A to Im. And hence we have A∼Im. Now, since there are n elements in In, number of elements in A are less than or equal to n"
 
  • Like
Likes FactChecker

Suggested for: Problem on a set which is a subset of a finite set

  • Last Post
Replies
18
Views
638
Replies
1
Views
775
Replies
3
Views
354
Replies
12
Views
573
  • Last Post
Replies
10
Views
427
Replies
17
Views
1K
Replies
12
Views
353
Top