What portion of mathematical statements are ZFC undecidable?

We can define a Chaitin's constant for the theory, representing a provability probability rather than a halting probability.

The setup is we first give it a prefix-free, binary encoding. Binary means there is a string of bits representing each symbol, for example $\emptyset \rightarrow 0000, \in \rightarrow 0001, \forall \rightarrow 0010, \dots$ and prefix-free means no prefix of a formula is itself a formula, one way of achieving this is to write all formulas in prefix order, that is $\neg \exists x \text{:} \in x \emptyset$ instead of $\neg \exists x \text{:} x \in \emptyset$. With some care this can be coded so that the binary representation of almost every real in $[0,1)$ has exactly one prefix encoding a valid formula. Then define:

$\Omega_{ZFC} = \sum_f{2^{-\vert f \vert}}$

where the sum is over all provable formulas $f$. This corresponds to the probability that, if we read a formula from a random bit string, it will be a provable one. We can define a variant of $\Omega$ for decidable formulas by summing over the formulas $f$ for which either $f$ or $\neg f$ is provable.

$\Omega_{ZFC} \lt 1$ is equivalent to $\text{Con}(ZFC)$, so in ZFC we won't be able to prove any better upper bound on its value (although every lower bound is provable). But it is possible to find upper bounds on the $\Omega$ of theories that ZFC can prove consistent such as Peano Arithmetic, defined similarly. Like Chaitin's constant, $\Omega_{PA}$ is algorithmically random (although PA cannot prove this) and so is $\Omega_{ZFC}$ if ZFC is consistent.

If you take any sort of straightforward approach to defining an encoding as I outlined above, the probability that a random formula is decidable is going to be very close to $1$. That's because the shortest formulas that have a chance of being undecidable are somewhat longer than the shortest formulas that can be expressed, and the weight of each formula is exponential in its length. Very short formulas are the most likely and these will all be decidable. That can be changed by extending the theory to have undecidable formulas with short codes (for example if we gave it a new relation symbol and axiomatized it as a provability predicate).

Tags:

Meta Math

Incompleteness

Provability

Related

Averaged dot product Riemann Integrable implies Lebesgue Integrable Explain phrase "For each pair of distinct elements" in reference to a graph. Maximum value of a complex polynomial on the unit disk Prove that $\forall a\in \mathbb{R\smallsetminus Q}$, there exist infinitely many $n\in \mathbb N$ such that $\lfloor{an^2}\rfloor$ is even. Why is the denominator $N-p-1$ in estimation of variance? How to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$ What is the least value of $k$ for which $B^k = I$? If $a_n$ is sequence of positive numbers such that $\sum a_n$ converges, then does $\sum \frac {{(a_n)}^{\frac 14}}{n^{\frac 45}}$ converge? How do we evaluate the closed form for $\int_{-\infty}^{+\infty}{(-1)^{n+1}x^{2n}+2n+1\over (1+x^2)^2}\cdot e^{-x^2}\mathrm dx?$ Regular Tetrahedron rotation problem Proof that degree of map is sum of its local degrees (prop 2.30 Hatcher)

Recent Posts