[FOM] AI-completeness (and settling CH)
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
More information about the FOM