Skip to Content.
Sympa Menu

coq-club - Re: [Coq-Club] Proving a multi-part theorem where later parts are a consequence of others

coq-club AT inria.fr

Subject: The Coq mailing list

List archive

Re: [Coq-Club] Proving a multi-part theorem where later parts are a consequence of others


Chronological Thread 
  • From: Jason -Zhong Sheng- Hu <fdhzs2010 AT hotmail.com>
  • To: "coq-club AT inria.fr" <coq-club AT inria.fr>
  • Subject: Re: [Coq-Club] Proving a multi-part theorem where later parts are a consequence of others
  • Date: Tue, 24 Mar 2020 16:50:24 +0000
  • Accept-language: en-CA, en-US
  • Arc-authentication-results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none
  • Arc-message-signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Zp/LRQgN08IUnFR2pppPsK2zH9kSsFF5pXtuvIAdaNY=; b=MkyryUjFqT4GDanKIN+UYN6y1nA8P8+0pq/esxmGDjJDpSyeOnV6srm5+UQ++zssBHW0BuR+dlyHhOaKml0KxLeUhZWXNv7mG0T4/AJkjjBE6UJv7c3idHDv6oxvWx9AjvpaetoV5UwhqXMhsld5s8sGYblIBqkJRTWKGRyRYbE5uyBmTm+mB2yqiGeG6wVOA53tNZImHKbmgmF0vzoNbuDYv9YHqaCkkznMngWaKZITxbfjRTdP2vRwf48+1mwyY/O83jYk7/Hao1SyYcjJH4jKHdeXhdlzx72KhM6SjjXKhfoa0TXj4Sj8dMY/qCZ7lcR9eSCPVv+yPvvZzSrG+A==
  • Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=am8Yd2SMPbDfjayuEPUXxRlX/Lwcdz1hhJ7apy6NlsESXF5ifS7oZCSfAKN2GAnWtkAT2TPA82WbTSYHlbQTfbLpYVa5UpR3CY2WwulU3mYLsWn+mMJgFGWPvsGxRxzGINYEJBR2rFQF9/IRuS2X5aSf18zi6+8RUS6OijGqQkbeeg9EGWHFnjftCjDFVGDJ/faDdxQVfD7C4juee83Uc7+r1+S1fYaVaYVX34iFP6UG+h8PbxqSsYXHmPjaTTuxLsk4mOzDfCZ7cbHL96l/WNWN7pN+EHpNojPtrQfPg19EdjbWYyXStUKfBXzInBUlzGoX4zXjbu5n/JSSFALu8A==
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=fdhzs2010 AT hotmail.com; spf=Pass smtp.mailfrom=fdhzs2010 AT hotmail.com; spf=Pass smtp.helo=postmaster AT NAM11-DM6-obe.outbound.protection.outlook.com
  • Ironport-phdr: 9a23:0aGUlhIoe5qPQwqFk9mcpTZWNBhigK39O0sv0rFitYgfL/TxwZ3uMQTl6Ol3ixeRBMOHsq4C0reP+P65EUU7or+/81k6OKRWUBEEjchE1ycBO+WiTXPBEfjxciYhF95DXlI2t1uyMExSBdqsLwaK+i764jEdAAjwOhRoLerpBIHSk9631+ev8JHPfglEnjWwba59IRmssAncttQajYRjJ6os1xDEvmZGd+NKyGxnIl6egwzy7dqq8p559CRQtfMh98peXqj/Yq81U79WAik4Pm4s/MHkugXNQgWJ5nsHT2UZiQFIDBTf7BH7RZj+rC33vfdg1SaAPM32Sbc0WSm+76puVRTlhjsLOyI//WrKjcN+kb9boAm5pxNh34HUfI+bNP17fqzHfNMaQ3dKUsJeWiFFB4+xaZYEAegcMuZCt4Tzp0UAowaiBQeiB+3vxD1HiWP50qAhyestDR3K0RY8E94SsnnZqsj+OqcIUeCyyanF1THNYOlN2Tf67ojDbwktrvKMXbJ3d8rRxlQkGR7FjlqOr4zlMCqZ3fkPvWiG8uFtUuyvhHMnqwBwuTij2NsghpTVio8OylDE8jl5wIMvKt25TE53e8KrEJxVtyyDMYZ9X80sQ2ZtuCkgy70Gv4a2fCcLyJQ7xx7fdueIf5KJ4hLkTOqRJjF4i2xheLK+gRay8lKsyujiWcSyzV1ErTJFn8HDu3wRzRDe7taLRuFg8kqlwzqC2Rzf5vlKIU8qlqfXN5ssz7stmZccv0TDECr7lFvrgKOKaEop//Wk5Prlb7Xoo5KTKZV7hRv+P6koh8exG/43MhIUUGie4em81KPs/Un+QLhSlvM7jq7XvI3HKcgCqKC3BA5Y3p8k6xmkETiqytMYnWQbLF1efxKHko7pNEzULPDgF/e/hEisnyl3yPDaP73hBZPNImLEkLf8YbZ970lcyA0wzdxF+51UDbQBLOryWk/3qtPYEgc0PgOoz+r9DNhxyJkSVX+LD6ODPq7erUeE5uc1LOmNYI8Vtiz9K/8g5/P2g382hF8dfKiy3ZcJdHy0A+hqLl6ZYXrrntcBFH0Fvgs6TODwlFKCVjtTa26oX60g/jE7FJ6mDYDbS4+xh7yBxT63EYFSZmBbEV+BCmzodoWBW/cUci2eOM5hkjoeVbigUYAtzx+utBWpg4Zge6Df/TRdvpb+3vB04ffSnFc873Y8W8+ayiSGS3x+tmIOXT4/mq5l9x9T0FCGhIpxmPteXZlh5/RPXU8BNZPawKkyK826DgzNfsWSEg7/Gv2mBi00R9M1hdQJZhAuSJ2Zkhnf0n/yUPcunLuRCcloo/uNjUi0HN50zjP97IdkilAnRsVVMmj/3fx/8BTWDo/N1U6ekvTzLPhO7Gv27G6GiFG2kgRASgcpCvfFWmwab0rS69/+4xGaFuL8OfEcKgJEjPW6BO5KZ9nu0QoUYt7GYY2bT0fv3mC6CFCP26+Ga5fsdyMFxiLBBUMYkgcVu3GbKQw5ASTnqGXbXmVj

I think you can prove something like

exists x, P(x) /\ (P(x) -> Q(x))

then it is tedious to show

exists x, P(x) /\ Q(x)

in particular, the latter does not require inspection of P(x)

in this particular example:

Lemma monSlider_state {A : Type} : forall mon buf sc l,
    length l > 0 ->
    length buf > 0 ->
    forall bs mon', (eval4 mon l) = (bs, mon') ->
    forall slb' slmon', (eval2 (monSlider mon buf sc) l) = (slb', slmon') ->
    exists buf', buf' = firstn (length buf) (bs ++ buf)
        /\ slmon' = @monSlider A mon' buf' sc
        /\ length buf' = length buf
        /\ (slmon' = @monSlider A mon' buf' sc -> slb' = sc buf').

Thanks,
Jason Hu

From: coq-club-request AT inria.fr <coq-club-request AT inria.fr> on behalf of Roger Witte <rogerwite AT yahoo.co.uk>
Sent: March 24, 2020 12:24 PM
To: coq-club AT inria.fr <coq-club AT inria.fr>
Subject: Re: [Coq-Club] Proving a multi-part theorem where later parts are a consequence of others
 
You can use the Section Mechanism to make assumptions and proofs sequentially (using Let instead of Lemma) and then have your Lemma statement before the end of section containing the local symbols

Sent from Yahoo Mail on Android

On Tue, 24 Mar 2020 at 16:19, Théo Winterhalter
<theo.winterhalter AT ens-cachan.fr> wrote:
One way is to define a tactic that does it for you:

Ltac split_rem_left h :=
match goal with
| |- ?A /\ ?B =>
assert A as h ; [
| split ; [
exact h
|]
]
end.

Goal forall A B C, A /\ B /\ C.
Proof.
intros A B C.
split_rem_left hA.
- admit.
- split_rem_left hB.
+ admit.
+ admit. (* hA : A, hB : B ⊢ C *)
Abort.

Le 24 mars 2020 à 17:09, Agnishom Chattopadhyay <agnishom AT cmi.ac.in> a écrit :

Often it is customary to phrase a theorem in a way that has multiple parts and each of the parts depend on the others and they may additionally introduce new variables.

For example,

For all sequences s of real numbers,
 s is increasing ->
 for all real number b, s is bounded above by b ->
    exists real number l,
       l = sup(s)
       /\ s converges to l
       /\ s is a cauchy sequence.

One might prove "s is a cauchy sequence" by appealing to some "s converges to l" (and some other theorem which says convergent sequences are Cauchy) but when they switch to the last conjunct, the previous conjuncts are not directly accessible.

How does one get around this issue?

One way might be to write two different lemmas: One talking about the first two conjuncts, and the second talking about just the third. However, this is ugly because in the second lemma one has to repeat a lot of boilerplate in order to even define what l is.

Is there a cleaner way to do this? Any tactics or patterns to make coq remember older conjuncts?

For reference, my actual theorem looks like this:

Lemma monSlider_state {A : Type} : forall mon buf sc l,
    length l > 0 ->
    length buf > 0 ->
    forall bs mon', (eval4 mon l) = (bs, mon') ->
    forall slb' slmon', (eval2 (monSlider mon buf sc) l) = (slb', slmon') ->
    exists buf', buf' = firstn (length buf) (bs ++ buf)
        /\ slmon' = @monSlider A mon' buf' sc
        /\ length buf' = length buf
        /\ slb' = sc buf'.

The proof of `slb' = sc buf'` depends on the fact that `slmon' = @monSlider A mon' buf' sc` but this fact is not accessible when I am proving the last conjunct.

--Agnishom




Archive powered by MHonArc 2.6.18.

Top of Page