# Proving a set is Uncountable or Countable Using Cantor's Diagonalization Proof Method

I understand the idea that some infinities are "bigger" than other infinities. The example I understand is that all real numbers between 0 and 1 would not be able to "fit" on an infinite list.

I have to show whether these sets are countable or uncountable. If countable, how would you enumerate the set? If uncountable, how would you prove using diagonalization?

Set 1. All real numbers represented only by 1's. EX) 1, .11, 111.11, 1.111...

Set 2. All real numbers represented only by 2's and 3's. EX) .2, 23.2, 22.2232...

• I think you have to be a little more precise in your wording. When you say "represented only by 2's and 3's", do you allow infinitely many of them? (I imagine you do, because otherwise it would be countable.) Note that Set 1 is not much affected by this. Only countably many elements get excluded by adding the condition that your representation has to be finite. In other words, there are only countably many infinite representations consisting of 1's only, but there are uncountably many infinite representations consisting of 2's and 3's. – Tunococ Nov 6 '15 at 2:34
• I believe your assumption is correct. I see how set 1 would be countable and set 2 would be uncountable. I understand why set two is uncountable but I don't know how to use the diagonalization method to prove such. – Hani Al-shafei Nov 6 '15 at 2:37
• Well, I guess you should read how diagonalization is done. It should not be hard to adapt the original argument to this setting. – Tunococ Nov 6 '15 at 2:46

Set $2$ can be put into one-to-one correspondence with the binary representation of the reals by the map that takes $2$ to $0$ and $3$ to $1$. Thus, this set has the same cardinality as $\mathbb R$ which is uncountable.

Hints: 1) You just listed these numbers, so.... 2) Use the exact same technique of diagnolization you say you understand.

• I see that set 1 is countable and set 2 is uncountable. I know why in my head, I just don't understand what to put on paper. Is it sufficient to simply say that there are infinite combinations of 2s and 3s and that if any infinite amount of these numbers were listed, it is possible to generate a completely new combination of 2s and 3s by going down the infinite list's digits diagonally and choosing 2s for 3s and 3s for 2s? – Hani Al-shafei Nov 6 '15 at 2:31

Set 1 is very countable; it can be placed into 1-1 correspondence with the integers. Set 2 is not countable. It is extremally disconnected and its intersection with $[0,1]$ is homeomorphic to a Cantor set.

• So when asked to enumerate the countable set, what does that even mean? Also, how do I show a set is uncountable using diagonalization? – Hani Al-shafei Nov 6 '15 at 2:40
• A set is $S$ countable iff there is a surjection $f:\mathbb{N}\rightarrow S$. – ncmathsadist Nov 6 '15 at 15:35

For Set $2$: Just consider the subset of this set consisting of numbers in the interval $(0, 1)$. Assume you have a complete listing of such numbers, and write them out, padding them with trailing zeros as needed. (Remember that the defining characteristic of Set $2$ is that the numbers can be represented only with $2$s and $3$s—not that they cannot be represented otherwise.) Now each position in each number in the list is either a $0$, a $2$, or a $3$. If you can generate a number whose value in Set $2$ that nevertheless differs from the $n$th item in the list in the $n$th place value, then you have properly executed the diagonalization argument.

Since Set $2$ is a superset of its restriction to $(0, 1)$, if that restriction is uncountable, then Set $2$ itself must also be uncountable.