Are there any uncountable sets that are computable?

394 Views Asked by At

A set $Y\subseteq X$ is computable iff its characteristic function $f_Y:X\rightarrow\{0,1\}$ defined as $$f_Y(x)=\begin{cases} 1, & x\in Y \\ 0, & x\notin Y \end{cases}$$ is computable. In principle $Y$ need not be a subset of $\mathbb N$, it may be e.g. a subset of the Baire space $\mathbb N^{\omega}$ (i.e., infinite sequences of natural numbers).

I certainly cannot visualize any uncountable but computable set. Does this have anything to do with "computably uncountable" sets?