Re: What are Simple Types (Was: Proofs as programs)

Liste des GroupesRevenir à s logic 
Sujet : Re: What are Simple Types (Was: Proofs as programs)
De : janburse (at) *nospam* fastmail.fm (Mild Shock)
Groupes : sci.logic
Date : 19. Dec 2024, 03:04:54
Autres entêtes
Message-ID : <vjvv05$124g0$3@solani.org>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
User-Agent : Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Firefox/91.0 SeaMonkey/2.53.19
Interestingly although this proof (Curry Howard
term) does not exist in Affine Logic:
λx:A->A.λy:A.(x (x y))   :  ((A -> A) -> (A -> A))
There is an alternative proof (Curry Howard
term) which does exist:
λx:A->A.x   :  ((A -> A) -> (A -> A))
This is just the I combinator of Affine Logic.
Mild Shock schrieb:
This is also not in the scope of advent of logic:
 From: Mild Shock <janburse@fastmail.fm>
Date: Mon, 18 Nov 2024 23:22:11 +0100
Subject: Re: How to prove this theorem with intuitionistic natural deduction?
 > 0: P -> (Q -> R) (Premisse)
 > 1: P /\ Q        (Assumption)
 > 2: P             (/\E,1)
 > 3: Q -> R        (->E,0,2)
 > 4: Q             (/\E,1)
 > 5: R             (->E,3,4)
 > 6: P /\ Q -> R   (Discharge,1)
 The advent of logic has only implication (->)/2
and no conjunction (/\)/2:
  > Advent of Logic 2024: Weekend 2
 > [...]
 > The propositional logic can do with
 > *implication only*, and it should be Linear Logic.
 > French logician Jean-Yves Girard is credited
 > [...]
 It says implication only. Just like here, implication
only is sometimes called positive logic:
 Meredith, D. (1978). Positive logic and λ-constants.
Studia Logica, 37(3), 269–285. doi:10.1007/bf02124728
 I think the example I gave is on page 288. The
lambda expression would need an additional combinator
W, it cannot be modelled with BCI alone:
 λx:A->A.λy:A.(x (x y))   :  ((A -> A) -> (A -> A))
 Meredith, D. gives the combinator expression BCWI.
Didn't verify. The combinator W is left contraction,
and since affine logic has no contraction, the
 combinator W is not part of affine logic:
 W: ((A -> (A ->B)) -> (A -> B))
 Mild Shock schrieb:
Julio Di Egidio schrieb:
On 19/12/2024 00:30, Mild Shock wrote:
It cannot be a proof term of Affine Logic, since x occurs twice.
That is not what affine logic means.
>
Well it does. It is based on the combinators B and C.
You cannot translate a lambda expression where x occurs twice
with B and C. You would need S.
>
Rule 7 and 8
https://en.wikipedia.org/wiki/Combinatory_logic#Combinators_B,_C
>
With B and C, you can only translate λx.(E1 E2) if x
occurs in E1 or E2 or none, but not in both E1 and E2.
>
Basically the implied requirement to have an equivalence
between the natural deduction and the hilbert style proofs,
that every lambda express can be translated to BCI.
>
Bye
 

Date Sujet#  Auteur
14 Dec 24 * Advent of Logic 2024: Weekend 158Mild Shock
14 Dec 24 +* Advent of Logic 2024: Weekend 2 (Was: Advent of Logic 2024: Weekend 1)36Mild Shock
14 Dec 24 i`* Re: Advent of Logic 2024: Weekend 3 (Was: Advent of Logic 2024: Weekend 2)35Mild Shock
17 Dec 24 i +* Proofs as programs (Was: Advent of Logic 2024: Weekend 3)33Julio Di Egidio
17 Dec 24 i i+- Re: Proofs as programs (Was: Advent of Logic 2024: Weekend 3)1Julio Di Egidio
17 Dec 24 i i+* Re: Proofs as programs (Was: Advent of Logic 2024: Weekend 3)21Mild Shock
17 Dec 24 i ii+* Re: Proofs as programs (Was: Advent of Logic 2024: Weekend 3)3Mild Shock
17 Dec 24 i iii+- Re: Proofs as programs (Was: Advent of Logic 2024: Weekend 3)1Mild Shock
17 Dec 24 i iii`- Re: Proofs as programs (Was: Advent of Logic 2024: Weekend 3)1Mild Shock
18 Dec 24 i ii`* Re: Proofs as programs17Julio Di Egidio
18 Dec 24 i ii `* Re: Proofs as programs16Mild Shock
18 Dec 24 i ii  `* Re: Proofs as programs15Mild Shock
18 Dec 24 i ii   `* Re: Proofs as programs14Julio Di Egidio
18 Dec 24 i ii    `* Re: Proofs as programs13Mild Shock
18 Dec 24 i ii     `* Hilbert Style proof system (Was: Proofs as programs)12Mild Shock
18 Dec 24 i ii      `* Re: Proofs as programs11Julio Di Egidio
19 Dec 24 i ii       `* What are Simple Types (Was: Proofs as programs)10Mild Shock
19 Dec 24 i ii        +* Re: What are Simple Types (Was: Proofs as programs)2Mild Shock
19 Dec 24 i ii        i`- Re: What are Simple Types (Was: Proofs as programs)1Mild Shock
19 Dec 24 i ii        `* Re: What are Simple Types (Was: Proofs as programs)7Julio Di Egidio
19 Dec 24 i ii         `* Re: What are Simple Types (Was: Proofs as programs)6Mild Shock
19 Dec 24 i ii          +* Re: What are Simple Types (Was: Proofs as programs)2Julio Di Egidio
19 Dec 24 i ii          i`- Re: What are Simple Types (Was: Proofs as programs)1Mild Shock
19 Dec 24 i ii          `* Re: What are Simple Types (Was: Proofs as programs)3Mild Shock
19 Dec 24 i ii           +- Re: What are Simple Types (Was: Proofs as programs)1Mild Shock
19 Dec 24 i ii           `- Re: What are Simple Types (Was: Proofs as programs)1Julio Di Egidio
19 Dec 24 i i+* Re: Proofs as programs (Was: Advent of Logic 2024: Weekend 3)5Julio Di Egidio
22 Dec 24 i ii`* Re: Proofs as programs4Julio Di Egidio
23 Dec 24 i ii `* /* A */ and /* B */ are different (Was: Proofs as programs)3Mild Shock
23 Dec 24 i ii  +- The Task is called the Inhabitation Problem (Was: /* A */ and /* B */ are different)1Mild Shock
23 Dec 24 i ii  `- Re: /* A */ and /* B */ are different (Was: Proofs as programs)1Julio Di Egidio
21 Dec 24 i i`* Curry-Howard Correspondence where? (Was: Proofs as programs (Was: Advent of Logic 2024: Weekend 3))5Mild Shock
21 Dec 24 i i `* A Christmas Miracle (Was: Curry-Howard Correspondence where?)4Mild Shock
21 Dec 24 i i  `* Re: A Christmas Miracle (Was: Curry-Howard Correspondence where?)3Mild Shock
21 Dec 24 i i   `* Re: A Christmas Miracle (Was: Curry-Howard Correspondence where?)2Mild Shock
21 Dec 24 i i    `- Re: A Christmas Miracle (Was: Curry-Howard Correspondence where?)1Mild Shock
27 Dec 24 i `- 4th Family Member: Relevant Logic (Re: Advent of Logic 2024: Weekend 3)1Mild Shock
20 Dec 24 +* Advent of Logic 2024: Specification and Deadline (Was: Advent of Logic 2024: Weekend 1)20Mild Shock
20 Dec 24 i+* Re: Advent of Logic 2024: Specification and Deadline (Was: Advent of Logic 2024: Weekend 1)15Mild Shock
20 Dec 24 ii+- Advent of Logic 2024: Solution Weekend 2 (Was: Advent of Logic 2024: Specification and Deadline)1Mild Shock
20 Dec 24 ii`* Repetition vs Use (Was: Advent of Logic 2024: Specification and Deadline)13Julio Di Egidio
20 Dec 24 ii `* Re: Repetition vs Use (Was: Advent of Logic 2024: Specification and Deadline)12Mild Shock
20 Dec 24 ii  `* Re: Repetition vs Use (Was: Advent of Logic 2024: Specification and Deadline)11Julio Di Egidio
20 Dec 24 ii   `* Please be patient (Was: Repetition vs Use)10Mild Shock
20 Dec 24 ii    `* Happy Now? (Was: Please be patient)9Mild Shock
20 Dec 24 ii     `* Re: Happy Now? (Was: Please be patient)8Julio Di Egidio
21 Dec 24 ii      `* What is it, a Bird or an Airplane? (Was: Happy Now? (Was: Please be patient))7Mild Shock
21 Dec 24 ii       `* Re: What is it, a Bird or an Airplane? (Was: Happy Now? (Was: Please be patient))6Julio Di Egidio
21 Dec 24 ii        `* Re: What is it, a Bird or an Airplane? (Was: Happy Now? (Was: Please be patient))5Mild Shock
21 Dec 24 ii         +- Re: What is it, a Bird or an Airplane? (Was: Happy Now? (Was: Please be patient))1Mild Shock
21 Dec 24 ii         `* Re: What is it, a Bird or an Airplane? (Was: Happy Now? (Was: Please be patient))3Julio Di Egidio
21 Dec 24 ii          `* Re: What is it, a Bird or an Airplane? (Was: Happy Now? (Was: Please be patient))2Mild Shock
21 Dec 24 ii           `- Re: What is it, a Bird or an Airplane? (Was: Happy Now? (Was: Please be patient))1Julio Di Egidio
21 Dec 24 i`* Advent of Logic 2024: Friendly Reminder (Re: Advent of Logic 2024: Specification and Deadline)4Mild Shock
24 Dec 24 i `* Re: Advent of Logic 2024: Friendly Reminder (Re: Advent of Logic 2024: Specification and Deadline)3Mild Shock
24 Dec 24 i  `* Linear Logic as Natural Deduction (Was: Advent of Logic 2024: Friendly Reminder)2Mild Shock
24 Dec 24 i   `- Re: Linear Logic as Natural Deduction (Was: Advent of Logic 2024: Friendly Reminder)1Mild Shock
17 Jan 25 `- Combinatorial Simple Typed Solution (Re: Advent of Logic 2024: Weekend 1)1Mild Shock

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal