User david diamondstone - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T22:11:11Z http://mathoverflow.net/feeds/user/3410 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67271/are-there-examples-of-nonconstructive-metaproofs Are there examples of nonconstructive metaproofs? David Diamondstone 2011-06-08T15:30:43Z 2011-06-08T16:37:24Z <p>This came up in a question on the xkcd forums. Is it possible to have a nonconstructive metaproof, i.e. a proof that there exists a proof in some formal system which does not construct said proof? Are there any known examples, preferably with some well-known formal system like PA?</p> <p>Conversely, is it possible to prove a meta-metatheorem saying that any metaproof can be used to find a proof?</p> http://mathoverflow.net/questions/25067/given-n-k-element-subsets-of-n-is-there-a-small-subset-a-of-n-which-intersects-t Given n k-element subsets of n, is there a small subset A of n which intersects them all? David Diamondstone 2010-05-17T22:29:24Z 2010-05-19T16:20:42Z <p>I'm looking for an answer to the following question. (An answer to a slightly different question would be good as well, since it could be useful for the same purpose.)</p> <blockquote> <p>Given a set <em>C</em> consisting of <em>n</em> subsets of {1, 2, ..., <em>n</em>}, each of size <em>k</em>, does there exist some small A $\subset$ {1, 2, ..., <em>n</em>} such that <em>A</em> intersects all (or all except a small number) of the sets in <em>C</em>?</p> </blockquote> <p>Preferably, "small" will be $\epsilon$<i>n</i> where $\epsilon$ can be made arbitrarily small, as long as <em>n</em> and <em>k</em> are sufficiently large.</p> <p>I'm hoping the answer is yes. Here is why some such <em>A</em> might exist: on average, each element of {1, 2, ..., <em>n</em>} intersects <em>k</em> sets in <em>C</em>, so one might hope to make do with <em>A</em> of size on the order of <em>n</em>/<i>k</i>.</p> <p>This smells a bit like some version of Ramsey's theorem to me, or like the Erdős–Ko–Rado theorem, but it doesn't (as far as I can tell) follow directly from either.</p> http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc Is there a computable model of ZFC? David Diamondstone 2010-01-20T16:38:48Z 2010-05-05T14:16:37Z <p><strong>Background</strong></p> <p>Assuming ZFC is consistent, then by downward Löwenheim–Skolem, there is a countable model (M,$\in$) of ZFC. Since the universe M is countable, we may as well think of it as actually being the set of natural numbers, so $\in$ will be some binary relation on the natural numbers.</p> <blockquote> <p>Can such a relation ever be computable?</p> </blockquote> <p><strong>Partial results</strong></p> <p>One can show that the class of binary relations $R$ on the natural numbers such that $(\mathbb{N},R) \models ZFC$ forms a $\Pi_0^1$ class, and will be nonempty so long as ZFC is consistent. This already gives us some interesting results. For example, by the low basis theorem, there is a low $R$ such that $(\mathbb{N},R) \models ZFC$. But I have been unable to determine whether such a function can be made computable; the best I can do is show that if such a function is computable, then there is no effective way of finding, given a finite set D of natural numbers, the element n such that D={m : mRn}.</p> http://mathoverflow.net/questions/67271/are-there-examples-of-nonconstructive-metaproofs/67273#67273 Comment by David Diamondstone David Diamondstone 2011-06-08T19:19:09Z 2011-06-08T19:19:09Z Great answer. But I would still be interested in more examples, if anyone has some more. http://mathoverflow.net/questions/67271/are-there-examples-of-nonconstructive-metaproofs/67272#67272 Comment by David Diamondstone David Diamondstone 2011-06-08T16:05:04Z 2011-06-08T16:05:04Z This can hardly be seen as a constructive proof, as the &quot;constructive&quot; part is entirely divorced from the &quot;proof&quot; part. http://mathoverflow.net/questions/67271/are-there-examples-of-nonconstructive-metaproofs Comment by David Diamondstone David Diamondstone 2011-06-08T16:03:16Z 2011-06-08T16:03:16Z Isn't there a story where a famous mathematician was assigned an open problem as homework by a devious professor, and ended up solving it? http://mathoverflow.net/questions/24034/can-cantor-set-be-the-zero-set-of-a-continuous-function/24037#24037 Comment by David Diamondstone David Diamondstone 2011-05-16T18:24:28Z 2011-05-16T18:24:28Z Each bump in the bump function has width 1/3^n. If the height is h(n), then the largest value of the kth derivative of of the stage n bumps will be 3^{kn}h(n) times the largest value of the kth derivative of the original bump function. If you want these to converge uniformly, the exact condition you need is that 3^{kn}h(n) converges to 0. So the necessary and sufficient condition on h to make the construction work is that for all a&gt;0, h(n) is eventually less than a^n. So yes, 2^{-2^n} will work. http://mathoverflow.net/questions/25067/given-n-k-element-subsets-of-n-is-there-a-small-subset-a-of-n-which-intersects-t/25070#25070 Comment by David Diamondstone David Diamondstone 2010-05-18T07:34:11Z 2010-05-18T07:34:11Z Thank you very much. http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc/12434#12434 Comment by David Diamondstone David Diamondstone 2010-01-20T19:06:24Z 2010-01-20T19:06:24Z The difficulty is that we don't have a set of &quot;all w for which w E s&quot;, since we can see when something is in s, and not in s, but there's no general way of knowing that nothing else is in s. However, the solution to this is to look at a set* of all two-element sets. If s is in this set, then you know to stop looking for more elements once you have found two. *This doesn't, of course, exist, since it is a class rather than a set, but if you intersect it with a large enough set you are fine. http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc/12434#12434 Comment by David Diamondstone David Diamondstone 2010-01-20T18:57:38Z 2010-01-20T18:57:38Z Gregory Igusa points out why the ordered pairing function is computable (actually, &quot;computable enough&quot;): pretend we have a set A of all two element sets. Then, given n and m, we can compute the ordered pair (n,m) by first finding a set y in A containing both n and m, and then finding a set x in A containing both n and y. Then x is the ordered pair (n,m). Of course, A is not actually a set, so this function isn't quite computable, but given any set X, there is a set of all two-element subsets of X, which lets you compute the ordered pair of any two elements of X, which is good enough. http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc/12434#12434 Comment by David Diamondstone David Diamondstone 2010-01-20T18:29:42Z 2010-01-20T18:29:42Z I agree that if we could compute the function i, that would be enough to prove that there is no computable model of ZFC. However, I still don't buy the argument that i is computable. I have the same problem as I did with the previous answer. In order to compute i(n+1) from i(n), we must find the unique number m such that (the number corresponding to) the set {i(n),{i(n),m}} is in s. If the function that, given input i(n),m, returned the number corresponding to the ordered pair (i(n),m) then we would be in great shape, but I don't see any reason why this function should be computable. http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc/12431#12431 Comment by David Diamondstone David Diamondstone 2010-01-20T17:56:59Z 2010-01-20T17:56:59Z Doesn't that require that, given a, b, and c, you have a way of finding the triple (a,b,c) in order to determine whether it is in the sum relation? If the function that takes you from a, b, c to the ordered triple (a,b,c) is not computable, I don't see how this gives a contradiction. In other words, I don't see how you can conclude from the mere fact that you have a computable model of ZFC that you have a computable nonstandard model of PA.