Question arising from Voevodsky's talk on inconsistency - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T13:51:10Z http://mathoverflow.net/feeds/question/41217 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41217/question-arising-from-voevodskys-talk-on-inconsistency Question arising from Voevodsky's talk on inconsistency John Stillwell 2010-10-05T22:43:53Z 2010-11-06T00:39:41Z <p>This question arises from the talk by Voevodsky mentioned in <a href="http://mathoverflow.net/questions/40920/what-if-current-foundations-of-mathematics-are-inconsistent" rel="nofollow">this recent MO question</a>. On one of his slides, Voevodsky says that</p> <blockquote> <p>a general formula even with one free variable describes a subset of natural numbers for which one can prove, using an argument similar to the one which is used in Goedel's proof, that there is not a single number n which can be shown to belong to this subset or not to belong to it.</p> </blockquote> <p>And in his spoken commentary he adds that there is a formula defining</p> <blockquote> <p>a subset about which you can prove that it is impossible to say anything about this subset, whatsoever.</p> </blockquote> <p>I interpret this as the claim that there is an arithmetically definable set $S$ for which there is no theorem of Peano arithmetic of the form $n\in S$ or $n\not\in S$. Perhaps I am misinterpreting, but can anyone supply (informally) the definition of such a set? </p> http://mathoverflow.net/questions/41217/question-arising-from-voevodskys-talk-on-inconsistency/41218#41218 Answer by Rodrigo Freire for Question arising from Voevodsky's talk on inconsistency Rodrigo Freire 2010-10-05T22:50:20Z 2010-10-05T22:50:20Z <p>(n=n)&amp;(con(ZF))</p> http://mathoverflow.net/questions/41217/question-arising-from-voevodskys-talk-on-inconsistency/41220#41220 Answer by Bjørn Kjos-Hanssen for Question arising from Voevodsky's talk on inconsistency Bjørn Kjos-Hanssen 2010-10-05T22:51:36Z 2010-10-05T23:01:16Z <p>Let $S$ be a first order definable Martin-Löf random set such as Chaitin's $\Omega$. If Peano Arithmetic, or ZFC, or any other theory with a computable set of axioms, proves infinitely many facts of the form $n\in S$ or $n\not\in S$ then it follows that $S$ is not immune or not co-immune and hence not ML-random after all. </p> <p>(The set of theorems of our theory of the form $n\in S$ (or $n\not\in S$) is computably enumerable and infinite, hence has an infinite computable subset. Being immune means having no infinite computable subset.)</p> <p>So only finitely many such facts can be proved. Now using an effective bijection between $\mathbb N$ and $\mathbb N\times \mathbb N$, decompose $S$ into infinitely many "columns", $S=S_0\oplus S_1\oplus\cdots$. Then one of these columns has the required property.</p> <p>The theory should be strong enough to deal effectively with breaking a definable set up into columns and associating values in a column with values in the original set, but this is certainly doable in PA or ZFC.</p>