Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.?

share|improve this question
6  
Countably many. There are only countably many statements in ZFC, and if only finitely many were undecidable, we could violate the incompleteness theorem by adding a finite number of axioms. –  Thomas Andrews Aug 21 at 0:27
2  
More importantly, the set of undecidable theorems is not recursively enumerable. This means that we can't even write a computer algorithm that would theoretically output all undecidable theorems. –  Thomas Andrews Aug 21 at 0:29
    
It's fairly obvious that there are infinitely many, since, if $P$ is undecidable, then so is $(P\land\lnot P)\lor P$,$(P\land\lnot P)\lor(P\land\lnot P)\lor P$, etc. The lack of recursive enumerability says that the set of undecidable theorems is very complex. –  Thomas Andrews Aug 21 at 0:31
2  
@ThomasAndrews The proof in your first comment actually shows more, namely that there are infinitely many undecidable sentences no two of which are ZFC-provably equivalent. So the question retains the same answer even if one excludes examples like your third comment. –  Andreas Blass Aug 21 at 0:41
1  
Gödel's incompleteness theorem shows that unless ZFC is inconsistent, there must be infinitely many: it constructs one, say $G$, and then you can consider ZFC $\cup\{ G\} $ and apply the theorem again to construct another, and so on. –  MJD Aug 21 at 1:05

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks for an elaborate answer, I appreciate it a lot. –  user132181 Aug 21 at 13:02

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.