Family of subset of N is countable?

  • Thread starter Unassuming
  • Start date
In summary: Thanks,In summary, the problem asks for a proof that a family of all finite subsets of a natural number is countable. The proof used the family M of all finite subsets of a natural number and showed that it is countable.
  • #1
Unassuming
167
0

Homework Statement


I am trying to show that a family F {A[tex]\subseteq[/tex][tex]N[/tex]: A is finite} Show that F is countable.

I found a proof in a book but I don't understand it. Could you help me please?


Homework Equations





The Attempt at a Solution



If A is finite, then F is clearly also finite and the claim becomes trivially true. We therefore suppose that A is countable infinite.

To prove that F is countable it would be sufficient to show that the family of all finite subsets of "Naturals" is countable. For each n an element of "Naturals", let Mn denote the family of all subsets N of "Naturals" satisfying N[tex]\subseteq[/tex] {1,2,...,n}.
Mn is obviously finite.

If M is the family of all finite subsets of "Naturals", we see that it can be expressed as M= the union of all Mn from n=1 to infinity. From the theorem that "union of countable sets is countable" we see though that M is countable and hence see that the family F is also countable.

---
My first question is as follows. In the beginning, how do they know that if A is finite, then F is clearly also finite?
 
Physics news on Phys.org
  • #2
If A is finite and the number of elements in A is n. Then the number of subsets of A is 2^n. You can prove this be induction. But it's pretty obvious if you think about how to choose a subset. For each element a of A you can either have a in the subset or a not in the subset.
 
  • #3
Thanks Dick,

but why, if the problem states that A is finite, must they prove the case in which A is countable infinite?
 
  • #4
The problem doesn't state A is finite. It wants you to prove that the infinite set N has a countable number of finite subsets. 'A' is just a dummy variable in the set notation. In the proof M_n are the sets that are finite.
 
  • #5
Thanks again Dick,

Why is it that F is stated as the family of all subsets A, but the proof uses M? Could they have used F without loss?
 
  • #6
I don't know why they switched from F to M in the proof. They are both the set of all finite subsets of N.
 

What does it mean for a family of subsets of N to be countable?

A family of subsets of N is countable if there exists a one-to-one correspondence between the family and the set of natural numbers. This means that each subset in the family can be assigned a unique natural number, and every natural number corresponds to exactly one subset in the family.

How can you prove that a family of subsets of N is countable?

One way to prove that a family of subsets of N is countable is by constructing a bijection (a one-to-one and onto function) between the family and the set of natural numbers. This can be done by assigning a unique natural number to each subset in the family.

Is every family of subsets of N countable?

No, not every family of subsets of N is countable. There are infinite families of subsets of N that are uncountable, meaning they cannot be put into a one-to-one correspondence with the set of natural numbers. Examples of uncountable families include the power set of N and the set of all real numbers.

Why is it important to study countable families of subsets of N?

Studying countable families of subsets of N is important because they have many applications in mathematics, computer science, and other fields. For example, they are essential in understanding the concept of infinite sets and in proving important theorems such as Cantor's diagonal argument.

Can a family of subsets of N be both countable and uncountable?

No, a family of subsets of N cannot be both countable and uncountable at the same time. It is either one or the other. If a family is countable, then it cannot be uncountable, as this would contradict the definition of countability. Similarly, if a family is uncountable, then it cannot be countable.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
440
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
446
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
810
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
Back
Top