User david diamondstone - MathOverflow

Are there examples of nonconstructive metaproofs?

2011-06-08T15:30:43Z

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?

Conversely, is it possible to prove a meta-metatheorem saying that any metaproof can be used to find a proof?

Given n k-element subsets of n, is there a small subset A of n which intersects them all?

2010-05-17T22:29:24Z

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

Given a set C consisting of n subsets of {1, 2, ..., n}, each of size k, does there exist some small A $\subset$ {1, 2, ..., n} such that A intersects all (or all except a small number) of the sets in C?

Preferably, "small" will be $\epsilon$n where $\epsilon$ can be made arbitrarily small, as long as n and k are sufficiently large.

I'm hoping the answer is yes. Here is why some such A might exist: on average, each element of {1, 2, ..., n} intersects k sets in C, so one might hope to make do with A of size on the order of n/k.

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.

Is there a computable model of ZFC?

2010-01-20T16:38:48Z

Background

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.

Can such a relation ever be computable?

Partial results

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

Comment by David Diamondstone

2011-06-08T19:19:09Z

Great answer. But I would still be interested in more examples, if anyone has some more.

Comment by David Diamondstone

2011-06-08T16:05:04Z

This can hardly be seen as a constructive proof, as the "constructive" part is entirely divorced from the "proof" part.

Comment by David Diamondstone

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?

Comment by David Diamondstone

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>0, h(n) is eventually less than a^n. So yes, 2^{-2^n} will work.

Comment by David Diamondstone

2010-05-18T07:34:11Z

Thank you very much.

Comment by David Diamondstone

2010-01-20T19:06:24Z

The difficulty is that we don't have a set of "all w for which w E s", 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.

Comment by David Diamondstone

2010-01-20T18:57:38Z

Gregory Igusa points out why the ordered pairing function is computable (actually, "computable enough"): 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.

Comment by David Diamondstone

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.

Comment by David Diamondstone

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.