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

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.

• "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$' – AakashM Nov 16 '17 at 13:02

1 Answer

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).

• 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. – wannabemathmajor Nov 16 '17 at 22:41
• 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. – manthanomen Nov 17 '17 at 3:51
• 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. – wannabemathmajor Nov 17 '17 at 4:33