# Question about countable and uncountable sets

1. Consider the following sets:
i. $Y_1 = ∅$
ii. $Y_2 = P(Y_1)$
iii. $Y = \{Y_1, Y_2\}$
iv. $Z × Z ∪ Q$
v. $N.$
vi. R
vii. ${f : \{0, 1\} → R}$
viii. Set of relations on $N$.
ix. $R × R$
x. $R × Q$.
xi. $\{0, 1\}^N$
xii. $N^{\{0,1\}}$

a) Which sets above are finite?
b) For the sets which are finite, order then by ascending cardinality.
c) Which sets above are countable?
d) Which sets above are countably infinite?
e) Which sets above are uncountable?
f) Which sets have cardinality greater than c = |R|?

a) i,ii,iii are finite and they are arranged in ascending order
c)if they are finite then they are countable, so i,ii,iii are countable.
d)iv is countable infinite because the union of two infinite countable sets is infinite countable. v is C.I. viii is countable because it will be set of all ordered pairs of the cartesian product of natural numbers. I have no idea how XI and XII work.

e) VI is uncountable by cantor's diagonalization. VIII, VIV,X ARE U.C (by intuition).

f) I don't know how to do this one and I need help with XI and XII

An explanation for the ones I am doing by intuition would be helpful. Cite a source if it's necessary. I am just making use of the fact the union of countable is countable, the union of uncountable is uncountable and the union of countable and uncountable is uncountable

• hint for xi: binary representation of reals – Max Jun 5 '16 at 9:08
• and that's for? – TheMathNoob Jun 5 '16 at 9:09
• you know the size of reals. so you know something about the minimal size of the representation (sequence of digits) of the reals in any number system (decimal, binary,...) – Max Jun 5 '16 at 9:11
• viii is not the set of all ordered pairs; it is the set of all subsets of the set of ordered pairs (because a relation is a set of ordered pars, i.e. a subset of the set of ordered pairs). – TonyK Jun 5 '16 at 9:12
• Right tony. xi and xii are countable infinite right?. – TheMathNoob Jun 5 '16 at 9:14