P(N) (N is the natural number set.)

Q

Z

[0, 1] n Q

Printable View

- Apr 17th 2010, 03:33 PMtreethetaWhich of the following sets is uncountable?
P(N) (N is the natural number set.)

Q

Z

[0, 1] n Q - Apr 17th 2010, 04:15 PMDeadstar
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? - Apr 17th 2010, 04:53 PMDrexel28
- Apr 17th 2010, 05:03 PMDeadstar
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. - Apr 17th 2010, 05:15 PMDrexel28
- Apr 17th 2010, 07:15 PMtreetheta
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