Finite Subsets of N: Proving Countability

  • Context: Graduate 
  • Thread starter Thread starter kingtaf
  • Start date Start date
  • Tags Tags
    Finite Subsets
Click For Summary

Discussion Overview

The discussion revolves around proving that the collection F(N) of all finite subsets of natural numbers N is countable. Participants explore various approaches and reasoning related to this concept, including mathematical arguments and constructions.

Discussion Character

  • Exploratory, Technical explanation, Mathematical reasoning

Main Points Raised

  • One participant asserts that the countable union of countable sets is countable and notes that for each n > 0, the number of subsets of cardinality n is countable, including the empty set for n = 0.
  • Another participant suggests considering the maximal element in a finite subset S of F(N) and proposes that there are 2max(S) - 1 sets in F(N) that have max(S) as a maximum.
  • A different participant claims it is straightforward to construct a bijection from the set of finite subsets to N by mapping each subset to a binary number represented as a string of 1's and 0's.

Areas of Agreement / Disagreement

Participants present multiple approaches and reasoning, indicating that there is no consensus on a single method for proving countability. The discussion remains unresolved with various perspectives offered.

Contextual Notes

Some arguments depend on the definitions of countability and subsets, and there may be missing assumptions regarding the properties of finite sets and their cardinalities.

kingtaf
Messages
8
Reaction score
0
Prove that the collection F(N) of all fi nite subsets of N (natural numbers) is countable.
 
Physics news on Phys.org
Countable union of countable sets is countable.
For each n > 0, the number of subsets having cardinality n is countable. There's the empty set for n = 0 also.
 
Last edited:
you have to look at the maximal element in an S in F(N). After that consider there are 2max(S) - 1 sets in F(N) which have max(S) as a maximum. Hope this helps.
 
It's easy to construct a bijection from this set to N, by mapping the set to a string of 1's and 0's and so construct a binary number.
 

Similar threads

Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Vector subspace and basis vectors in the context of data science
  • · Replies 6 ·
Replies
6
Views
4K
Undergrad The set of nonzero values of pmf is at most countable
  • · Replies 3 ·
Replies
3
Views
4K
Undergrad Dyadic cubes generate Borel sigma algebra of subset
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Equivalent definitons for primitive polynomials
  • · Replies 24 ·
Replies
24
Views
2K
MHB Proving that a subset of a countable set is countable
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Trouble with a passage in Zariski & Samuel's Commutative algebra text
  • · Replies 5 ·
Replies
5
Views
2K
MHB Finitely Generated Modules - Bland Problem 1(a), Problem Set 2.2
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Proof of a fact about real numbers - transcendental and algebraic
  • · Replies 7 ·
Replies
7
Views
3K
MHB Proving a Subset of a Group is a Group
  • · Replies 2 ·
Replies
2
Views
3K