# Set of all Subsets of Natural Numbers

• PingPong
In summary: In the diagonal argument, we can only guarantee that the resulting sequence is not in the set we started with, but it is possible to construct infinite sequences that are not in the set of finite subsets (for example, an infinite sequence of all 1's). Therefore, the diagonal argument cannot prove the uncountability of the set of finite subsets of the natural numbers. In summary, the proof that the set of all subsets of the natural numbers is uncountable involves defining a bijective function and utilizing Cantor's diagonal process. However, this method cannot be applied to prove the uncountability of the set of finite subsets of the natural numbers.
PingPong

## Homework Statement

Prove that the set of all subsets of the natural numbers is uncountable.

## Homework Equations

All of the countability stuff - including Cantor's diagonal argument

## The Attempt at a Solution

I think I have this one figured out, but I was wondering if somebody would be willing to check it for me.

Suppose we have a subset of the natural numbers, A. Then I've defined a bijective function $$f:A\rightarrow \{s_k\}$$, where $$s_k=1$$ if $$k\in A$$ and 0 if $$k\notin A$$ (that is, convert A to a sequence of 0's and 1's, based on whether or not the kth natural number is in the subset A). Using Cantor's diagonal process (Theorem 2.14 in baby Rudin if anybody's interested), we can say that since the set of all sequences whose elements are 0's and 1's are uncountable, A is also uncountable.

That works. You knew that didn't you? If you want to test your understanding a little further, tell me why if we take all finite subsets of the naturals, that the Cantor diagonal argument doesn't show that that set is uncountable?

The map f: [0,1) -> P(N) given by
f(0.a1 a2 a3 a4 ...) = {a1, 10+a2, 20+a3, 30+a4, ...}
is one-to-one, so P(N) cannot be countable since [0,1) isn't countable.

Hi Dick and mathboy,

To (maybe) answer Dick's question, is it that, while using the diagonal argument, you may get an infinite sequence of 0's and 1's that isn't in the set of finite subsets?

PingPong said:
Hi Dick and mathboy,

To (maybe) answer Dick's question, is it that, while using the diagonal argument, you may get an infinite sequence of 0's and 1's that isn't in the set of finite subsets?

Exactly.

## 1. What is the "Set of all Subsets of Natural Numbers"?

The "Set of all Subsets of Natural Numbers" is a mathematical concept that refers to the collection of all possible subsets that can be formed from a set of natural numbers. It includes all the individual elements of the set, as well as the empty set and the set itself.

## 2. How many subsets are there in the "Set of all Subsets of Natural Numbers"?

The number of subsets in the "Set of all Subsets of Natural Numbers" is infinite. This is because natural numbers are also infinite, and for every natural number, there is a corresponding subset that includes only that number.

## 3. What is the cardinality of the "Set of all Subsets of Natural Numbers"?

The cardinality, or size, of the "Set of all Subsets of Natural Numbers" is equal to 2 to the power of n, where n is the number of elements in the original set of natural numbers. For example, if the original set has 3 elements, the cardinality of the "Set of all Subsets of Natural Numbers" would be 2^3 = 8.

## 4. Is the "Set of all Subsets of Natural Numbers" countable or uncountable?

The "Set of all Subsets of Natural Numbers" is countable, as it can be put in a one-to-one correspondence with the set of natural numbers. This means that each subset can be assigned a unique natural number, making it countable.

## 5. What is the significance of the "Set of all Subsets of Natural Numbers" in mathematics?

The "Set of all Subsets of Natural Numbers" is significant in mathematics as it provides a foundation for understanding concepts such as power sets, combinatorics, and set theory. It also has applications in other areas of mathematics, such as in probability and graph theory.

Replies
1
Views
1K
Replies
4
Views
1K
Replies
1
Views
1K
Replies
2
Views
4K
Replies
3
Views
1K
Replies
6
Views
3K
Replies
11
Views
5K
Replies
2
Views
936
Replies
3
Views
2K
Replies
11
Views
4K