[FOM] Weak foundations for cohomological number theory

Tue Jan 4 20:54:50 EST 2011

> From: Harvey Friedman <friedman at math.ohio-state.edu>
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Date: Tue, 4 Jan 2011 07:40:10 -0500
> Subject: Re: [FOM] Weak foundations for cohomological number theory
> On Jan 3, 2011, at 11:04 AM, Colin McLarty wrote:

> I gather that "bounded Zermelo Fraenkel set theory with choice" is not what you meant to write, and you mean "bounded Zermelo set theory with choice" =  "bounded ZC".

Agh!  Yes, or course.  My fingers got carried away on the keyboard.

> A good next step would be to do this in full ZFC with Power Set weakened to
> 100 power sets of omega exists.
>
> Then reduce 100 considerably, maybe down to 0.
>
> It is well known that any arithmetic (and much more) sentence provable in this system - even with >100 replaced by any specific integer in base 10 notation - is provable in bounded ZC.

Very nice, and I did not know it.   Is there a good reference on this
so I can absorb more of  the approach?

I expect that 0 powersets is adequate for the theorems, but the
question is how far can you go by expressing the tools of cohomology
in weaker set theory (as I have done so far) before you have to start
detailed arithmetic analysis of individual proofs.

> It is also well known that any arithmetic (and much more) sentence provable in any of these
> systems, including ZC, is provable in the same system without use of the axiom of choice.

Yes, a good point for me to keep in mind, because cohomology does need
choice to get off the ground.   These tools need it though the results
do not.

> From: Robert Solovay <solovay at gmail.com>
writes
>
> Mathias used "MacLane set theory" to refer to the theory you consider
> (which he dubs ZBQC)  + "Every set is a member of a transitive set".
>
> MacLane set theory is strictly stronger (proves more theorems)  than
> ZBQC though they have the same proof-theoretic strength (are provably
> equiconsistent in the metatheory PA).

Are there known examples of a mathematical kind?  Or is it mostly
foundational theorems of set theory?  Is this in Mathias's long paper?
 I have looked through it a lot but hardly absorbed it all.

> By the way, I am not sure if you include foundation in your theory.
> Mathias definitely includes it in ZBQC.

That never even occurred to me.  I don't think I have any reason to
include it.  Am I right that foundation has no effect on arithmetic or
analysis since n-th order arithmetic is all in the well founded part
anyway?  Or have I put that too crudely?

thanks,  Colin

>
> --Bob Solovay
>
> On Mon, Jan 3, 2011 at 8:04 AM, Colin McLarty <colin.mclarty at case.edu> wrote:
>> Hello,
>>
>> I can now show that the Grothendieck-Deligne proof of the Weil
>> conjectures, and Wile's and Kisin's proofs of Fermat's Last Theorem,
>> can be formalized in Bounded Zermelo Fraenkel set theory with choice.
>> This is the finitely axiomatized fragment of ZC where the separation
>> axiom scheme is restricted to bounded (delta-nought) formulas, so ZC
>> proves it is consistent.  It has the proof-theoretic strength of
>> simple type theory.  Following Mathias I call it MacLane set theory.
>>
>> The whole apparatus of Grothendieck's SGA can be formalized in that
>> set theory extended by an axiom positing one suitable universe U.
>> That set theory proves the universe U is an omega-model of ZC, while
>> the theory itself is modeled by the ZFC set V-sub-omega-times-3.
>>
>> Both cases are shown by general considerations on the tools involved.
>> I'm sure both remain great overestimates of the proof-theoretic
>> strength of FLT and the Weil conjectures.  But sharp estimates will
>> presumably require a huge amount of new arithmetic specific to each
>> proof.
>>
>> I am finishing up a paper on this which I will post on my website as
>> soon as it is presentable.  Thanks to all who have answered my
>> questions about this.
>>
>> best, Colin
>> _______________________________________________
>> FOM mailing list
>> FOM at cs.nyu.edu
>> http://www.cs.nyu.edu/mailman/listinfo/fom
>>
>
>
>
>
> ---------- Message transféré ----------
> From: Ruy de Queiroz <ruy at cin.ufpe.br>(by way of Martin Davis <eipye at pacbell.net>)
> To: fom at cs.nyu.edu
> Date: Tue, 04 Jan 2011 16:20:10 -0800
> Subject: [FOM] WoLLIC 2011 - Submission Deadline Extended
> WoLLIC 2011
> 18th Workshop on Logic, Language, Information and Computation
> May 18th to 21st, 2011
>
> University of Pennsylvania
> Philadelphia, USA
>
> Scientific Sponsorship
> Interest Group in Pure and Applied Logics (<http://www.cin.ufpe.br/~igpl/>IGPL)
> The Association for Logic, Language and Information (<http://www.folli.org/>FoLLI)
> Association for Symbolic Logic (<http://www.aslonline.org/>ASL)
> European Association for Theoretical Computer Science (<http://www.eatcs.org/>EATCS)
> European Association for Computer Science Logic (<http://www.eacsl.org/>EACSL)
> Sociedade Brasileira de Computação (<http://www.sbc.org.br/>SBC)
> Sociedade Brasileira de Lógica (<http://www.cle.unicamp.br/sbl/>SBL)
>
> Organisation
> <http://www.math.upenn.edu/>Department of Mathematics, <http://www.upenn.edu/>University of Pennsylvania, USA
> <http://www.cin.ufpe.br/>Centro de Informática, <http://www.ufpe.br/>Universidade Federal de Pernambuco, Brazil
>
>
> ----------
>
>
> Submission Deadline Extended
>
>
>
>
> There will be a Special Session honoring Max Kanovich on the occasion of his 65-th birthday
> Speakers include John Mitchell, Mitsuhiro Okada, Paul Rowe, and others (tba)
>
>
>
>
> Call for Papers
>
> <http://wollic.org/>WoLLIC is an annual international forum on inter-disciplinary research involving formal logic, computing and programming theory, and natural language and reasoning. Each meeting includes invited talks and tutorials as well as contributed papers. The eighteenth WoLLIC will be held at the University of Pennsylvania, Philadelphia, USA, from May 18th to 21st, 2011. It is sponsored by the <http://www.aslonline.org/>Association for Symbolic Logic (ASL), the <http://www.cin.ufpe.br/~igpl>Interest Group in Pure and Applied Logics (IGPL), the <http://www.folli.org/>The Association for Logic, Language and Information(FoLLI), the <http://www.eatcs.org/>European Association for Theoretical Computer Science (EATCS), the <http://www.eacsl.org/>European Association for Computer Science Logic (EACSL), the <http://www.sbc.org.br/>Sociedade Brasileira de Computação (SBC), and the <http://www.cle.unicamp.br/sbl/>Sociedade Brasileira de Lógica (SBL).
>
> Paper submission
> Contributions are invited on all pertinent subjects, with particular interest in cross-disciplinary topics. Typical but not exclusive areas of interest are: foundations of computing and programming; novel computation models and paradigms; broad notions of proof and belief; formal methods in software and hardware development; logical approach to natural language and reasoning; logics of programs, actions and resources; foundational aspects of information organization, search, flow, sharing, and protection. Proposed contributions should be in English, and consist of a scholarly exposition accessible to the non-specialist, including motivation, background, and comparison with related works. They must not exceed 10 pages (in font 10 or higher), with up to 5 additional pages for references and technical appendices. The paper's main results must not be published or submitted for publication in refereed venues, including journals and other scientific meetings. It is expected that each accepted paper be presented at the meeting by one of its authors. Papers must be submitted electronically at the WoLLIC 2011 EasyChair website. (Please go to <http://wollic.org/wollic2011/instructions.html>http://wollic.org/wollic2011/instructions.html for instructions.) A title and single-paragraph abstract should be submitted by January 8 (NEW), and the full paper by January 15 (NEW, firm date). Notifications are expected by February 21, and final papers for the proceedings will be due by March 1 (firm date).
>
> Proceedings
> The proceedings of WoLLIC 2011, including both invited and contributed papers, will be published in advance of the meeting as a volume in Springer's <http://www.springer.com/lncs>LNCS series. In addition, abstracts will be published in the Conference Report section of the Logic Journal of the IGPL, and selected contributions will be published as a special post-conference WoLLIC 2011 issue of the <http://www.elsevier.com/locate/jcss>Journal of Computer and System Sciences (confirmed).
>
> Invited Speakers
> <http://www.cis.upenn.edu/~alur/>Rajeev Alur (Philadelphia) <http://www.phil.uu.nl/~iemhoff/eigen.html>Rosalie Iemhoff (Utrecht) <http://theory.stanford.edu/people/jcm/>John Mitchell (Stanford) <http://www.math.ias.edu/~vladimir/Site3/home.html>Vladimir Voevodsky (Princeton) <http://www.phil.uu.nl/~yoad/>Yoad Winter (Utrecht) <http://www.dcs.bbk.ac.uk/~michael/>Michael Zakharyaschev (London)
>
> Student Grants
> ASL sponsorship of WoLLIC 2011 will permit ASL student members to apply for a modest travel grant (deadline: February 18, 2011). See<http://www.aslonline.org/studenttravelawards.html>http<http://www.aslonline.org/studenttravelawards.html>://www.aslonline.org/studenttravelawards.html for details.
>
> Important Dates
> January 8, 2011 (NEW): Paper title and abstract deadline January 15, 2011 (NEW): Full paper deadline (firm) February 21, 2011: Author notification March 1, 2011: Final version deadline (firm)
>
> Programme Committee
> <http://web.cs.gc.cuny.edu/~sartemov/>Sergei Artemov (New York) <http://www.andrew.cmu.edu/user/avigad/>Jeremy Avigad (Pittsburgh) <http://www.cs.swan.ac.uk/~csarnold/>Arnold Beckman (Swansea) <http://www.mi.ras.ru/~bekl/>Lev Beklemishev (Moscow) (CHAIR) <http://www.dm.unipi.it/~berardu/>Alessandro Berarducci (Pisa) <http://www.math.lsa.umich.edu/~ablass/>Andreas Blass (Ann Arbor) (tbc) <http://www.math.ucsd.edu/~sbuss/>Sam Buss (San Diego) <http://www.cs.bham.ac.uk/~axj/>Achim Jung (Birmingham) <http://staff.science.uva.nl/~bloewe/>Benedikt Löwe (Amsterdam) <http://www.cs.technion.ac.il/~janos/>Janos Makowsky (Haifa) <http://www.let.uu.nl/~ctl/docenten/moortgat.html>Michael Moortgat (Utrecht) <http://www.phil.uu.nl/~oostrom/>Vincent van Oostrom (Utrecht) <http://www.cs.mcgill.ca/~prakash/>Prakash Panangaden (Montréal) <http://www.sci.brooklyn.cuny.edu/cis/parikh/>Rohit Parikh (New York) <http://www.cin.ufpe.br/~ruy>Ruy de Queiroz (Recife) <http://www.poncelet.ru/pers/shen.htm>Alexander Shen (Marseilles and Moscow) <http://www.cs.ru.nl/~spitters/>Bas Spitters (Nijmegen) <http://www7.in.tum.de/~veith/>Helmut Veith (Wien) <http://staff.science.uva.nl/~yde/>Yde Venema (Amsterdam) <http://www.cis.upenn.edu/~weinstei/>Scott Weinstein (Philadelphia) <http://www.csc.liv.ac.uk/~frank/>Frank Wolter (Liverpool)
>
> Steering Committee
> Samson Abramksy, Johan van Benthem, Anuj Dawar, Joe Halpern, Wilfrid Hodges, Daniel Leivant, Angus Macintyre, Grigori Mints, Hiroakira Ono, Ruy de Queiroz.
>
> Organising Committee
> <http://www.math.upenn.edu/~vnigam/>Vivek Nigam (U Penn) <http://www.cin.ufpe.br/~ago>Anjolina G. de Oliveira (U Fed Pernambuco) <http://www.cin.ufpe.br/~ruy>Ruy de Queiroz (U Fed Pernambuco) (co-chair) <http://www.cis.upenn.edu/~scedrov/>Andre Scedrov (U Penn) (co-chair)
>
> Further information
> Contact one of the Co-Chairs of the Organising Committee.
>
> Web page
> <http://wollic.org/wollic2011/>http://wollic.org/wollic2011/
>
>
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
>