Incomparable consistency strengths

Wed May 5 08:48:39 EDT 2021

Hello,

Theorem 3 of this paper: 
http://jdh.hamkins.org/wp-content/uploads/linearity-2.pdf gives 
sentences incomparable in consistency strength that may be easily 
explicitable enough for J. Shipman.

Best regards,
-- 
Vincent R.B. Blazy
Doctorant en Logique Mathématique à l'Université de Paris

Le 03/05/2021 06:59, fom-request at cs.nyu.edu a écrit :
> Send FOM mailing list submissions to
> 	fom at cs.nyu.edu
> 
> To subscribe or unsubscribe via the World Wide Web, visit
> 	https://cs.nyu.edu/mailman/listinfo/fom
> or, via email, send a message with subject or body 'help' to
> 	fom-request at cs.nyu.edu
> 
> You can reach the person managing the list at
> 	fom-owner at cs.nyu.edu
> 
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of FOM digest..."
> 
> 
> Today's Topics:
> 
>    1. Re: Incomparable consistency strengths (Anton Freund)
>    2. Re: Incomparable consistency strengths (Mirko Engler)
>    3. Re: Incomparable consistency strengths  (JOSEPH SHIPMAN)
>    4. Re: 881: Some Logical Thresholds (Harvey Friedman)
>       (Juan P. Aguilera)
> 
> 
> ----------------------------------------------------------------------
> 
> Message: 1
> Date: Fri, 30 Apr 2021 09:13:18 +0200
> From: "Anton Freund" <freund at mathematik.tu-darmstadt.de>
> To: fom at cs.nyu.edu
> Subject: Re: Incomparable consistency strengths
> Message-ID:
> 	<a1aee15ee9cee6ae4434532e3cfbc354.squirrel at webmail.mathematik.tu-darmstadt.de>
> 
> Content-Type: text/plain;charset=iso-8859-1
> 
>> Can anyone give explicitly (not merely prove they exist, but actually 
>> give
>> the axioms or schemes in a level of specificity and detail typical of
>> published math papers) two axiomatized theories A and B such that
>> 1) ZF proves Con(A)
>> 2) ZF proves Con(B)
>> 3) PA does not prove Con(A)->Con(B)
>> 4) PA does not prove Con(B)->Con(A)
> 
> In Section II of the following paper there is an example of A and B 
> that
> satisfy 3) and 4) (but not 1) and 2), because the theories involve 
> large
> cardinals):
> 
> Kai Hauser & W. Hugh Woodin, Strong Axioms of Infinity and the Debate
> About Realism, Journal of Philosophy 111 (8):397-419 (2014),
> https://doi.org/10.5840/jphil2014111828.
> 
> Specifically, let MC and MC2 be the assertions that there are at least 
> one
> resp. two measurable cardinals. In the cited paper, A is the extension 
> of
> ZFC by MC; and B is the extension by the statement "if ZFC+MC2 proves 
> no
> contradiction in k steps, then A=ZFC+MC proves no contradiction in
> 2^(2^(2^k)) steps".
> 
> Best,
> Anton
> 
> 
> 
> 
> ------------------------------
> 
> Message: 2
> Date: Fri, 30 Apr 2021 14:19:03 +0200
> From: Mirko Engler <mir.engler at gmail.com>
> To: JOSEPH SHIPMAN <joeshipman at aol.com>
> Cc: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: Re: Incomparable consistency strengths
> Message-ID:
> 	<CA+vYAKdpDfD9oPhPSp44RxmT_UxZT=fqo2OYXYPeRqknFxK8yw at mail.gmail.com>
> Content-Type: text/plain; charset="utf-8"
> 
> Dear Joseph Shipman,
> 
> I guess a standard way of constructing those theories A and B is the
> following:
> 
> First you take something like two incomparable Rosser-sentences phi and
> psi, s.t. PA does not prove phi -> psi and PA does not prove psi -> 
> phi.
> These sentences will be Pi1 and hold in the standard model. For any
> consistent r.e. extension T of PRA,  every Pi1-sentence is modulo 
> Con(T)
> provably equivalent to a consistency-statement, i.e. there are
> Pi1-sentences a and b s.t.:
> PRA+Con(PRA) |- phi <-> Con(PRA+a)
> PRA+Con(PRA) |- psi <-> Con(PRA+b)
> As Con(PRA+a) and Con(PRA+b) hold in the standard model, a and b hold 
> in
> standard model themselves (for being Pi1).
> Now take A:= PRA+a and B:=PRA+b, so A and B also hold in the standard
> model. As PA |- Con(PRA), both the assumption that
> PA|-Con(A) -> Con(B) and PA|-Con(B) -> Con(A) lead to the contradiction
> that PA|- phi -> psi and PA|- psi -> phi.
> Of course, ZF|-Con(A) and ZF|-Con(B).
> 
> All of the details can be found in Smorynski: Self-Reference and Modal
> Logic. Ch 6, Corollary 3.3. and Ch 7, Corollary 2.6.
> 
> Best regards,
> 
> Mirko Engler
> 
> Am Fr., 30. Apr. 2021 um 07:26 Uhr schrieb JOSEPH SHIPMAN <
> joeshipman at aol.com>:
> 
>> Can anyone give explicitly (not merely prove they exist, but actually 
>> give
>> the axioms or schemes in a level of specificity and detail typical of
>> published math papers) two axiomatized theories A and B such that
>> 1) ZF proves Con(A)
>> 2) ZF proves Con(B)
>> 3) PA does not prove Con(A)->Con(B)
>> 4) PA does not prove Con(B)->Con(A)
>> ?
>> 
>> ? JS
>> 
>> Sent from my iPhone
>> 
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: </pipermail/fom/attachments/20210430/99fd9b80/attachment.html>
> 
> ------------------------------
> 
> Message: 3
> Date: Fri, 30 Apr 2021 08:33:55 -0400
> From: JOSEPH SHIPMAN <joeshipman at aol.com>
> To: Mirko Engler <mir.engler at gmail.com>
> Cc: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: Re: Incomparable consistency strengths
> Message-ID: <D588B1D9-560D-447A-A510-ECD6CFFFB2C0 at aol.com>
> Content-Type: text/plain; charset="utf-8"
> 
> This works but it involves finding ?two incomparable Rosser
> sentences?. That?s an existence proof, I asked if they could be given
> explicitly. Rosser sentences are even worse for that than Godel
> sentences.
> 
> ? JS
> 
> Sent from my iPhone
> 
>> On Apr 30, 2021, at 8:19 AM, Mirko Engler <mir.engler at gmail.com> 
>> wrote:
>> 
>> ?
>> Dear Joseph Shipman,
>> 
>> I guess a standard way of constructing those theories A and B is the 
>> following:
>> 
>> First you take something like two incomparable Rosser-sentences phi 
>> and psi, s.t. PA does not prove phi -> psi and PA does not prove psi 
>> -> phi.
>> These sentences will be Pi1 and hold in the standard model. For any 
>> consistent r.e. extension T of PRA,  every Pi1-sentence is modulo 
>> Con(T)
>> provably equivalent to a consistency-statement, i.e. there are 
>> Pi1-sentences a and b s.t.:
>> PRA+Con(PRA) |- phi <-> Con(PRA+a)
>> PRA+Con(PRA) |- psi <-> Con(PRA+b)
>> As Con(PRA+a) and Con(PRA+b) hold in the standard model, a and b hold 
>> in standard model themselves (for being Pi1).
>> Now take A:= PRA+a and B:=PRA+b, so A and B also hold in the standard 
>> model. As PA |- Con(PRA), both the assumption that
>> PA|-Con(A) -> Con(B) and PA|-Con(B) -> Con(A) lead to the 
>> contradiction that PA|- phi -> psi and PA|- psi -> phi.
>> Of course, ZF|-Con(A) and ZF|-Con(B).
>> 
>> All of the details can be found in Smorynski: Self-Reference and Modal 
>> Logic. Ch 6, Corollary 3.3. and Ch 7, Corollary 2.6.
>> 
>> Best regards,
>> 
>> Mirko Engler
>> 
>>> Am Fr., 30. Apr. 2021 um 07:26 Uhr schrieb JOSEPH SHIPMAN 
>>> <joeshipman at aol.com>:
>>> Can anyone give explicitly (not merely prove they exist, but actually 
>>> give the axioms or schemes in a level of specificity and detail 
>>> typical of published math papers) two axiomatized theories A and B 
>>> such that
>>> 1) ZF proves Con(A)
>>> 2) ZF proves Con(B)
>>> 3) PA does not prove Con(A)->Con(B)
>>> 4) PA does not prove Con(B)->Con(A)
>>> ?
>>> 
>>> ? JS
>>> 
>>> Sent from my iPhone
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: </pipermail/fom/attachments/20210430/a1af8983/attachment.html>
> 
> ------------------------------
> 
> Message: 4
> Date: Fri, 30 Apr 2021 16:13:38 +0200
> From: "Juan P. Aguilera" <aguilera at logic.at>
> To: fom at cs.nyu.edu
> Subject: Re: 881: Some Logical Thresholds (Harvey Friedman)
> Message-ID: <DFF1ED47-8B52-4D63-9815-CDC74110592E at logic.at>
> Content-Type: text/plain;	charset=utf-8
> 
> Concerning the question:
> 
>> On a vaguely related note, there used to be an open problem of whether
>> any two Rosser sentences for PA (and other systems) are provably
>> equivalent over PA, or even over EFA. Is still problem still open?
> 
> There is a theorem of Guaspari and Solovay (AML 1979) by which the
> answer depends on how one formalizes ?provability in PA.? More
> precisely, there are extensionally correct Sigma_1 provability
> predicates P, Q (which can be assumed to satisfy Modus Ponens and
> provable Sigma_1 completeness) such that
> i) all Rosser sentences for P are provably equivalent.
> ii) not all Rosser sentences for Q are provably equivalent.
> 
> As far as I know, the problem for the ?usual? proof predicate (i.e.,
> the one used by G?del) is still open.
> 
> Regards,
> Juan
> 
> ------------------------------
> 
> Subject: Digest Footer
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom
> 
> 
> ------------------------------
> 
> End of FOM Digest, Vol 221, Issue 1
> ***********************************