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

  • Thread starter issacnewton
  • Start date
  • Tags
    Finite Set
In summary: This is the main part of the proof. You're assuming that there is a function from A to In that goes from m elements in A to the first m elements in In. And then, because In is a subset of A, it follows that there are fewer elements in A than in In.
  • #1
issacnewton
1,000
29
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
 
Physics news on Phys.org
  • #2
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
WWGD, thanks, but is the proof presented here valid ?
 
  • #4
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

1. What is a subset of a finite set?

A subset of a finite set is a set that contains elements from the original set, but may not contain all of the elements. It is a smaller set that is contained within the larger set.

2. How do you determine if a set is a subset of a finite set?

To determine if a set is a subset of a finite set, you must check if all of the elements in the smaller set are also present in the larger set. If so, then the smaller set is a subset of the larger set.

3. Can a set be a subset of itself?

Yes, a set can be a subset of itself. This is because all of the elements in the original set are also present in the original set, making it a subset of itself.

4. What is the difference between a proper subset and an improper subset?

A proper subset is a subset that does not contain all of the elements of the original set, while an improper subset contains all of the elements of the original set. In other words, an improper subset is equal to the original set, while a proper subset is a smaller subset of the original set.

5. Can a set have more than one proper subset?

Yes, a set can have multiple proper subsets. This is because there can be multiple smaller sets that contain some, but not all, of the elements of the original set. Each of these smaller sets would be considered a proper subset of the original set.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
883
  • Calculus and Beyond Homework Help
Replies
1
Views
494
  • Calculus and Beyond Homework Help
Replies
4
Views
487
  • Precalculus Mathematics Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
919
  • Calculus and Beyond Homework Help
Replies
34
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
2K
Back
Top