[FOM] AI-completeness (and settling CH)

James Hirschorn James.Hirschorn at univie.ac.at
Tue May 8 05:08:07 EDT 2007

On Friday 04 May 2007 16:50, Timothy Y. Chow wrote:
> What exactly is the problem here?  To determine the truth value of the
> continuum hypothesis?  Or what?

The intended problem was to settle the Continuum Hypothesis. Thanks for 
pointing this out, i.e. that my suggestion doesn't make sense as is. On the 
other hand, the fact that it is not even clear what it means to settle CH is 
one of the things that makes the continuum problem so interesting. I think if 
I instead wrote "P is AI-complete" where P is any open problem say from core 
mathematics, there would be no ambiguity (beyond the exact meaning of 
AI-completeness); well, I think that either determining the truth value of P 
or else showing that this cannot be done within ZFC (obviously assuming 
Con(ZFC)) would constitute a solution. 

This is probably getting off topic, but concerning settling CH, the criterion 
might be (roughly) that it has been settled once there is a unanimous 
consensus among the leading experts that no further mathematical progress is 
possible, regardless of how the truth value turns out, e.g. false, true, 1/3 
true and 2/3 false, 'completely' intractable, etc ... 

Such a scenario is hypothesized in some slides of John Steel (laguna.ps on his 
web site). A sequence of theories T_0, T_1, ... is postulated there which in 
the presence of large enough cardinals, assuming that they are not destroyed 
by small forcing notions, decides the theory of V_omega+2 or at least all the 
sentences whose truth value can be forced. If the existence of such a 
sequence of theories can be proved, and if it can be proved that any such 
sequence of theories agrees on CH, then (at least up to my understanding) the 
truth value of CH will have been decided, or at least reduced to the question 
of the consistency of the needed large cardinals. On the other hand so long 
as there exists one such sequence of theories, the theory of V_omega+2 will 
be for all intents and purposes completely determined, owing 
to "bi-interpretability" even if there is a second sequence yielding 
different truth values for various sentences over V_omega+2 (this is just my 
interpretation of what I read, and may be wrong). In the latter case, when two 
sequences interpret the truth of CH differently, it is suggested there (now 
paraphrasing) that we may have arrived at a point where no further 
mathematical progress on CH is possible, even though a definite truth value 
has not been determined. 

Aside: If anyone can suggest further reading on this material (preferably 
newer than Dehornoy's survey article) I would be much obliged. 

> > Bobby Fischer concluded a long time ago that chess had been "played out"
> > in a sense that would preclude this.
> It's not clear how much stock one should place in such pronouncements.
> Capablanca spoke of the "drawing death" of chess long before Fischer.
> They might be right, but just because they say so doesn't make it so.

Of course, but I would tend to give Fischer's opinion a lot of weight, in this 
particular matter.

James Hirschorn

More information about the FOM mailing list