[FOM] Finite functions and necessary use of large cardinals

[S. Gill Williamson]

Hi Tim,


Your concerns are certainly relevant.  Referring to the arXiv paper
reference I sent you:


I have had plenty of feedback on this paper (referees for the JOC version
[Wil17c], logician friends).  We think the proofs as stated are correct.   A
key paper not published is [Fri97].  I went over this paper with Jeff in
1999.  Recently, Victor Marek has gone over some of the key results, like
the Jump Free Theorem, with Harvey.


The remark on page 10 of my arXiv  paper  (“*Remark: Independence of the
families of Theorem 5.4*”)  is important relative to your comments.  This
refers to [Fri97].  Harvey seems to be going back to this area in his new
FOM program.  I hope so.


If Theorem 6.7 turns out to be provable in ZFC, it would be a nice addition
to combinatorics.   On the other hand if Theorem 6.7 is shown to be
unprovable in ZFC that would be interesting also.  It would support the
common belief that P=NP is false.


My hope for this paper is that turns out to be "fun and interesting to
think about" for people interested in logic, algorithms and complexity
theory.


-- Gill

On Tue, Nov 12, 2019 at 4:38 PM Timothy Y. Chow <tchow at math.princeton.edu>
wrote:

> Gill Williamson wrote:
>
> > Below is a link to my latest thoughts on connections between Harvey
> > Friedman's 1998 paper (Annals of Mathematics) and the P vs NP problem:
> >
> > https://arxiv.org/abs/1907.11707v2
>
> This is an intriguing suggestion, but I thought that one lesson from
> Friedman's Boolean relation theory was that a seemingly innocuous "tweak"
> of statement to a superficially similar statement can abruptly switch it
> from unprovable in ZFC to trivially provable in an extremely weak system.
> So it seems very bold to me to conjecture that a whole family of
> superficially similar statements are all unprovable in ZFC just because
> some, or even most, of them are.
>
> Tim
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20191113/efdc4387/attachment.html>