Let $X=\{x\in \mathbb{R}\ | \ \hbox{the decimal representation of $x$ contains only 4s and 7s}\}$. Is $X$ countable or uncountable? Prove that your answer is correct.

Should an argument like Cantor's diagonalization be used? Or an argument based on the fact that sequences of 0s and 1s are uncountable? I don't know how to really prove that either.

  • 1
    $\begingroup$ Cantor's diagonal argument should be any easy adaptation (if the nth place in the nth number is 4, change it to 7; if it is 7 change it to 4). Your other idea seems good too (each real number should have a binary representation and there is a one-to-one correspondence to reals with 4's and 7's as digits). $\endgroup$ – Leonard Blackburn Apr 8 at 23:45

If the set is countable, then there must be a way to put all elements of it in a sequence - e.g. 0.444..., 0.7444..., 0.47444..., 0.77444... etc.

If the set is uncountable, then you may be able to prove it using a diagonalisation proof, which typically starts with "assume that the set is countable, and that the set can be put in sequence $a$", then you show that the sequence can't possibly hold all elements of the set by producing an element that doesn't belong in it.

Either way, you're going to want to try putting the elements in sequence. Try to find a sequence that looks like it will work, then see if you can either (a) prove that it does contain the whole set (or can be easily modified to do so), or (b) demonstrate a way of constructing an element of the set that doesn't belong in the sequence such that there's no easy way to fix it.

You might want to see if something resembling the original diagonalisation proof makes sense - given a sequence $a_n$ of elements of $X$, let $b_n$ be the $n$-th decimal value of $a_n$ and see whether smooshing them together and swapping the 4s and 7s does anything.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.