10
$\begingroup$

Here is the idea for the set. Let $\alpha$ be a real number. Then $x_\alpha$ be a set of digits with the property that a digit is in the set if it appears infinitely many times in $\alpha$.

For many numbers $\alpha$ it is easy to determine $x_\alpha$. For some it is challenging like $\alpha = \pi$. However, what if $\alpha$ was a non-computable number? Then it would be impossible to list the elements of $x_\alpha$, right?

$\endgroup$
3
  • 1
    $\begingroup$ I would say that a (countable) set is listable iff we can determine for every element whether it is in the set. So, I would disagree with the given upvoted and accepted answer. For $\pi$ , none of the the digits is known to appear infinite many times , so we only know that the list $x_{\pi}$ contains at leat two digits. $\endgroup$
    – Peter
    Mar 2 at 13:37
  • 10
    $\begingroup$ There are $2^{10}$ such sets, and we can list all of them. The set can be listed, we just can't determine which set it is. $\endgroup$ Mar 2 at 13:50
  • $\begingroup$ How is it possible to list anything that appears 'infinitely many times'? $\endgroup$ Mar 3 at 22:03

2 Answers 2

21
$\begingroup$

There is a difference between the mathematical definition of being able to list all elements of a set and to actually and practically being able to list them.

Your set is mathematically well defined, and it has to be of finite size, so it is listable. Us potentially not being able to figure out what that set exactly looks like does not take away from that.

$\endgroup$
2
  • $\begingroup$ To add to this: it's not too hard for me to list the elements of $x_{\alpha}$. I'll write down [], and then [0], and then [1], and then [0,1], and then [2], and then [0,2], and ... until I've written down [0,1,2,3,4,5,6,7,8,9]. At some point in there I must have written down $x_{\alpha}$! Just don't ask me which one... $\endgroup$ Mar 5 at 21:00
  • $\begingroup$ Analogously, it's very hard for me to answer the Riemann hypothesis and know that I'm correct, but it's not hard to give the answer: one of "yes" or "no" will do just fine. $\endgroup$ Mar 5 at 21:02
5
$\begingroup$

In constructive mathematics, we often distinguish finite and subfinite. For a finite set, we know a bijection to some $\{0,1,\ldots,n\}$. A subfinite set is a set we know to be a subset of a finite set, but we do not necessarily know who is in and who is not.

With this terminology settled, we do indeed find that the set of digits occurring infinitiely often in the decimal expansion of a real number is definitely subfinite, but not necessarily finite. However, this is not closely tied to computability of the real.

For example, random real numbers are non-computable and normal, so all digits appear infinitely often in their expansions. On the other hand, consider the real $x_G$ defined by making its $n$-th digit $0$ if all even numbers $> 2$ below $n$ are the sum of two primes, and making it $1$ otherwise. This yields an algorithm to compute $x_G$, but knowing which digits appear infinitely often in $x_G$ would require solving Goldbach's conjecture.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .