Prove that the set of natural numbers (in base 10) with exactly one of the digits equal to 7 is countably infinite.

"In base 10" means that it's the natural numbers between 0 and 9, correct? What might the first step be in starting a formal proof?

I know that in order to prove cardinality, there must be a bijection, and that a set S is countably infinite if |S|=|$\mathbb{N}$|, but I'm not sure where those definitions would come into play in this instance.

  • $\begingroup$ "I know that in order to prove cardinality, there must be a bijection" - true, but when all you need to show is 'countably infinite', it suffices to show 'not finite, and no bigger than $\mathbb N$' $\endgroup$ – AakashM Nov 16 '17 at 13:02

If $S$ is a subset of $T$, then $|S| \leq |T|$. The set in your question is a subset of the natural numbers, so it is either finite or countably infinite (and it's easy to see that it isn't finite).

  • $\begingroup$ It's hard for me to visualize the problem. Is it asking to show that some set, like (0, 7), or (7, 9) -- since one of the digits is 7 -- is countably infinite? The wording is slightly confusing to me. $\endgroup$ – wannabemathmajor Nov 16 '17 at 22:41
  • $\begingroup$ The elements of the set are natural numbers with exactly one digit equal to 7, such as 7, 27 74, 375, etc. "Base 10" is the way we usually write numbers. $\endgroup$ – manthanomen Nov 17 '17 at 3:51
  • $\begingroup$ Ok! So, one way to prove this would be to construct a simple table of values, or arrange a non-repeating list, showing a bijection. $\endgroup$ – wannabemathmajor Nov 17 '17 at 4:33

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.