Is almost every definable number uncomputable

cardinalscomputabilitymeasure-theoryorder-theoryreal numbers

We know that almost all real numbers are undefinable.

We also know that almost all real numbers are uncomputable.

We also know that there are numbers that can be defined but not computed.
However, every computable number is definable.

Intuitively, because computable numbers are a subset of definable numbers, there should be 'more' definable numbers than computable numbers.

I don't really know if I can say that though. Afterall, intuitively there are more rationals than whole numbers, even though that's not the case.

Does my question have anything to do with the possibility of a mapping of computable numbers to definable numbers?
Because if there were such a mapping, it would mean that they would be of equal 'size', or cardinality.

Is almost every definable number uncomputable?

Best Answer

First of all, there's a crucial vagueness here: what does "definable" mean? For example, in a precise sense it is consistent with $\mathsf{ZFC}$ that every real number is definable, the saving grace being that the relevant sense of "definable" is (per Tarski) too powerful to be subject to the obvious counting argument.

But as interesting as it is, this isn't really the core problem with your question. Let's fix some "reasonably rich" notion of definability; for example, the following will (I suspect) satisfy all the basic requirements one might have:

Say that a real number $r$ is definable iff it is first-order definable without parameters in the structure $\mathcal{A}:=(V_{\omega_{17}};\in)$.

I'm using $\omega_{17}$ here just as some "really big" ordinal. Feel free to go bigger or smaller as you prefer, and see this old post of mine if you're unfamiliar with the notion of definability in a structure. Note that all computable reals are indeed definable in this sense (this is basically just a tweak to Post's theorem).

Let $\mathcal{D}$ be the set of definable (in the above sense) reals and $\mathcal{C}$ be the set of computable reals. Now here's the truly serious problem:

Both $\mathcal{C}$ and $\mathcal{D}$ are countable, so the standard "coarse" tools of analysis (e.g. measure and category) are useless for measuring the size of $\mathcal{C}$ relative to $\mathcal{D}$.

To compare countable sets in a meaningful way, we usually need to turn to some kind of asymptotic analysis. For example, the following is an almost completely precise question:

Let $(\varphi_i)_{i\in\mathbb{N}}$ enumerate the formulas of set theory which define a single real number in $\mathcal{A}$. For each $n\in\mathbb{N}$, let $$p_n={\vert i: \varphi_i^\mathcal{A}\in\mathcal{C}\vert\over n}.$$ What is $\lambda:=\lim\sup_{n\rightarrow\infty}p_n$?

The "obvious" conjecture is that $\lambda=0$. But note that this is highly dependent on the way we choose to enumerate the formulas of set theory (and this explains the "almost" five sentences prior): we can in fact get any value we want for $\lambda$ by enumerating formulas in a perhaps pathological manner. So the question above only becomes precise once we fix an enumeration of formulas, and moreover it only becomes interesting once we justify a particular choice of enumeration (or a class of enumerations, and show that any enumeration from that class yields the same answer).

Admittedly, in terms of heuristics I find that it's almost always a good idea to assume that $\mathcal{C}$ is a negligible subset of $\mathcal{D}$. But this is very vague. So at present I will tentatively claim the following:

While very plausible, we currently have no good way to make precise the conjecture that "most definable numbers are not computable" (let alone prove such a precisiation).

Related Question