# Thread: Which of the following sets is uncountable?

1. ## Which of the following sets is uncountable?

P(N) (N is the natural number set.)
Q
Z
[0, 1] n Q

2. Originally Posted by treetheta
P(N) (N is the natural number set.)
Q
Z
[0, 1] n Q
Its P(N) but it's important you understand why the others are countable. (I take it P means power set).

First of. If a set is countable then a subset of it is also countable.

So... Is $\displaystyle \mathbb{Q}$ countable?

If it is then $\displaystyle [0, 1] \cap \mathbb{Q}$ will be countable.

Surely you can tell that $\displaystyle \mathbb{Z}$ is countable?

Do you know anything about cardinality yet?

Its P(N) but it's important you understand why the others are countable. (I take it P means power set).

First of. If a set is countable then a subset of it is also countable.

So... Is $\displaystyle \mathbb{Q}$ countable?

If it is then $\displaystyle [0, 1] \cap \mathbb{Q}$ will be countable.

Surely you can tell that $\displaystyle \mathbb{Z}$ is countable?

Do you know anything about cardinality yet?
Well I think the justification of why $\displaystyle \mathcal{P}(\mathbb{N})$ isn't countable is non-trivial.

4. Originally Posted by Drexel28
Well I think the justification of why $\displaystyle \mathcal{P}(\mathbb{N})$ isn't countable is non-trivial.
Ya no way could I be fully proving that of the top of my head. Could prove the rest are countable though...

To be honest I kinda misinterpreted the question as 'which one is uncountable' so I figured try to show OP how to eliminate the countable ones. Never the less... If OP is learning about cardinality that could be used via Cantors card(x) < card(P(x)) theorem.

Ya no way could I be fully proving that of the top of my head. Could prove the rest are countable though...

To be honest I kinda misinterpreted the question as 'which one is uncountable' so I figured try to show OP how to eliminate the countable ones. Never the less... If OP is learning about cardinality that could be used via Cantors card(x) < card(P(x)) theorem.
It's easier to prove that $\displaystyle \mathbb{R}\simeq(0,1)\simeq\mathcal{P}(\mathbb{N})$ from where the conclusion follows immediately, but yes I was thinking of Cantor's theorem too.

6. I think i can see why P(N) is countable cus usually when you take all the subsets of N right? and thats not countable cus there's alot of sets i really suck at proving stuff I looked at cantors therom

Proof: It suffices to show that [0, 1] is uncountable (see Exercise 7). If
not, then we have a bijection from N to [0, 1]. This is a sequence (x) that
lists all numbers in [0, 1], in some order. By considering the canonical
decimal expansions, we will construct a number not on the list.
Xl = CI,I CI,2 C I.3
X2 = C2, I C2,2 C 2.3
X3 = C3,IC3,2C3.3
Suppose that the expansions appear in order as indicated above. We
build a canonical decimal expansion that disagrees with every expansion
in our list. Let an = 1 if Cn,n = 0, and an = 0 if Cn,n > o. Now (a) disagrees
in position n with the expansion of Xn. Furthermore, since (a) has no 9, (a)
cannot be the alternative expansion of any number in our list. Therefore,
the expansion (a) does not represent a number in our list. By Theorem
13.25, (a) is the canonical expansion of some real number. Thus our list
does not contain expansions for all real numbers in [0, 1]. .

but i dont really get how to use it