Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
There are several statements known to be undecidable in ZFC, with the continuum hypothesis probably being the most "popular" one.
Is it known how many undecidable statements are there in ZFC? I.e. is it known if there are finitely many of them (maybe even some specific number or a bound), infinitely many of them, etc.?
As indicated in the other answer, there are countably many undecidable statements (the largest possible number), and this is an immediate consequence of the incompleteness theorem. The version of incompleteness that Andrews is using is that if $T$ is a consistent, recursive set of axioms that interprets a modicum of arithmetic, then the set of $T$-decidable statements is r.e. but not recursive. Actually, Andrews is only using the case of this result where $T=\mathsf{ZFC}$. But consider the version I just stated. It allows us to prove that there are in fact continuum many (that is, $2^{\aleph_0}=|\mathbb R|$) complete theories that extend $\mathsf{ZFC}$.
To prove this, consider a construction that assigns recursive, consistent theories extending $\mathsf{ZFC}$ to the nodes of the complete binary tree, as follows: Let $T_\emptyset=\mathsf{ZFC}$. Fix an enumeration $\phi_0,\phi_1,\dots$ of all sentences in the language of set theory. Given a finite sequence $s$ of zeros and ones, suppose we have defined the theory $T_s$ and, as indicated, it is a consistent, recursive extension of $\mathsf{ZFC}$. Let $n=n_s$ be least such that $\phi_n$ and $\lnot\phi_n$ are not provable in $T_s$. This number exists by the remark in the previous paragraph. Now let $T_{s{}^\frown\langle 0\rangle}=T_s\cup\{\phi_n\}$ and $T_{s{}^\frown\langle 1\rangle}=T_s\cup\{\lnot \phi_n\}$. Note that these are consistent theories, and both are recursive, since they are obtained from a recursive theory by adding a single additional axiom.
Finally, to each infinite sequence $x$ of zeros and ones assign the theory $T_x=\bigcup_n T_{x\upharpoonright n}$, where $x\upharpoonright n$ is the finite sequence of the first $n$ bits of $x$. Note that by construction all these theories are consistent and complete (they are no longer recursive, of course, again by appealing at the remark in the first paragraph). Also, if $x\ne y$ and $m$ is least such that the $m$-th bits $x_m$ and $y_m$ of $x$ and $y$ are different, say $x_m=0$ and $y_m=1$ (but $x\upharpoonright m =y\upharpoonright m=s$, say), then $T_x$ and $T_y$ are incompatible theories, since $\phi_{n_s}\in T_x$ and $\lnot \phi_{n_s}\in T_y$. This shows that the number of completions of $\mathsf{ZFC}$ generated by this construction is precisely $2^{\aleph_0}=|\mathcal P(\mathbb N)|$, that is, the largest possible number.
This large variety is not the end of the story, since one can prove that each complete extension of $\mathsf{ZFC}$ admits continuum many non-isomorphic countable models, again the largest possible number (and, in fact, it admits $2^\kappa$ non-isomorphic models of size $\kappa$ for each infinite cardinal $\kappa$). For a proof of this, see for example here.
Assuming consistency, there are infinitely many undecidable statements.
The set of decidable statements is recursively enumerable, but not recursive. Which means the set of undecidable statements is not recursively enumerable - that is, any computer program which enumerates only undecidable statements will fail to enumerate all undecidable statements.
So there are necessarily infinitely many.
Since there are only countably many statements, there must be countably many undecidable statements.
