Family of subset of N is countable?

  • Thread starter Thread starter Unassuming
  • Start date Start date
Click For Summary

Homework Help Overview

The discussion revolves around the problem of demonstrating that the family of all finite subsets of the natural numbers (denoted as F) is countable. Participants are exploring the implications of the definitions and properties of finite and infinite sets within this context.

Discussion Character

  • Conceptual clarification, Assumption checking, Problem interpretation

Approaches and Questions Raised

  • Participants are examining the reasoning behind the assertion that if a subset A is finite, then the family F is also finite. There is also a discussion about the necessity of considering the case where A is countably infinite, despite the problem focusing on finite subsets. Additionally, questions arise regarding the notation used in the proof, specifically the transition from F to M.

Discussion Status

The discussion is active, with participants seeking clarification on the definitions and logical steps involved in the proof. Some guidance has been offered regarding the nature of finite subsets and the implications of the proof structure, but there is no explicit consensus on the reasoning behind certain aspects of the proof.

Contextual Notes

Participants note that the original problem does not explicitly state that A is finite, leading to some confusion about the assumptions being made in the proof. The use of different notations (F and M) in the proof is also a point of contention, as it raises questions about consistency and clarity in the argument.

Unassuming
Messages
165
Reaction score
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
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.
 
Thanks Dick,

but why, if the problem states that A is finite, must they prove the case in which A is countable infinite?
 
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.
 
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?
 
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.
 

Similar threads

Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Proof that algebraic numbers are countable
  • · Replies 6 ·
Replies
6
Views
3K
Proving that the natural numbers are countable, stuck.
  • · Replies 8 ·
Replies
8
Views
3K
Countably Compact: Necessity & Sufficiency
  • · Replies 1 ·
Replies
1
Views
2K
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
  • · Replies 4 ·
Replies
4
Views
1K
Every subset of a finite set is finite
  • · Replies 1 ·
Replies
1
Views
2K
Union of countable sets is countable
  • · Replies 2 ·
Replies
2
Views
3K
Topology: Understanding open sets
  • · Replies 8 ·
Replies
8
Views
2K
Image of a f with a local minima at all points is countable.
  • · Replies 16 ·
Replies
16
Views
2K
Set of all finite subsets of N (real analysis)
  • · Replies 4 ·
Replies
4
Views
7K