Skip to Content.
Sympa Menu

coq-club - Re: [Coq-Club] Proving the pairing axiom

coq-club AT inria.fr

Subject: The Coq mailing list

List archive

Re: [Coq-Club] Proving the pairing axiom


Chronological Thread 
  • From: mukesh tiwari <mukeshtiwari.iiitm AT gmail.com>
  • To: coq-club AT inria.fr
  • Subject: Re: [Coq-Club] Proving the pairing axiom
  • Date: Sat, 28 Dec 2024 19:17:57 +0000
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=mukeshtiwari.iiitm AT gmail.com; spf=Pass smtp.mailfrom=mukeshtiwari.iiitm AT gmail.com; spf=None smtp.helo=postmaster AT mail-wr1-f45.google.com
  • Ironport-data: A9a23:tHFwMa7AJJ7mOci3JDyK5QxRtJPDchMFZxGqfqrLsTDasY5as4F+v jEaWjrVM/aLZDGhfosnaIq3oUwP7ZODx4JlTwE6ry42Zn8b8sCt6faxfh6hZXvKRiHgZBs6t JtGMoGowOQcFCK0SsKFa+C5xZVE/fjUAOC6UoYoAwgpLSd8UiAtlBl/rOAwh49skLCRDhiE0 T/Ii5S31GSNhXgtaAr414rZ8Ekz5a6o6GtC1rADTakjUGH2xyF94K03fvnZw0vQGuF8AuO8T uDf+7C1lkuxE8AFV7tJOp6iGqE7aua60Tqm0hK6aID+6vR2nRHe545gXBYqhei7vB3S9zx54 I0lWZVd0m7FNIWU8AgWe0Ew/y2TocSqUVIISJSymZX78qHIT5fj69xgSx4nBJRBwd9uX2BMp aYKAhUPSA/W0opawJrjIgVtrsEqLc2uI5lG/388kHfWCvEpRZ2FSKLPjTNa9G1o14YeQLCEP ZNfNWcHgBfoO3WjPn8SFZEzh+e0h2b2aTweqVOUua8f7G3azQg327/oWDbQUoXSGJ8PwxnG9 woq+UzbOlYzEPOwxwaP2SmypL6enhLCVb8dQejQGvlC2wDKnjNCVnX6T2CTqv6gz0W6Rth3M F0R4iNorK4o9UXtQMOVYvGjiHuNvxpZRMAJVuNmtUeCza3b5wvfDW8BJtJcVDA4nOY4AmM77 0bQpOrwWz1t4OeHY1ef0KjB+FteJhMpBWMFYCYFSy4M7N/ivJw/g3rzojBLQP7dYjrdSWGY/ tyakBXSkYn/miLi6klW1VXOgjbpuYKQCwBpu0PYWWWq6g4/b4mgD2BJ1bQ5xacbRGp6ZgDe1 JThpyR4xL5WZX1qvHLUKNjh5Jnzu5643MT02DaD5aUJ+TW34GKEdotN+jx4L0oBGp9bImKyO hOI5FoOvcA70J6WgUlfM9LZ5yMCnfiIKDgZfqqMBjazSsEuJF/Zo3s2DaJu9zu8wBZyzMnTx qt3ge73UC9CVvU5pNZHb+ga1rAvy2g/w2iVLa0XPDz2uYdykEW9EO9fWHPXNrBRxPrd/G39r YwDX+PUkE43eLOlPUHqHXs7dwliwY4TX8qu85Q/my/qClYOJVzN/NeImu98IdU/wPgK/goKl 1nkMnJlJJPErSWvAW23hrpLMdsDhL4m9Slnbx8/d02lwWYiaouJ5aISPcl/N7o++eApibY+Q /AZco/SSr5CWxbWyQQ7NJPdlY1FcAj0pASsOyH+XiMzUaQ9TCP0+/jlXDDVyg8wMgSNu/ATn ZicxyLAYJ9aRw1dHMfcM/2u6FWqvEkiouF5XmqWA9wKeEzT75RmcA3hqsAGe+c3dBPJnGqc3 SmrHCZC9PXsopA0wvbNl6urv4ekKMogP0t4Tk3wz6e6CjnexUWnmbR/aeeveSvPcU/F44Ogb vVx49ClF9Nfh3dMkY53M4gz/JIE/9G1+oNrlFV1LkvEf3GAK+1GIEDf+eJtq6cU5LtSmTXua 3K14tMAZIm4YpL0ImUwejggQP+Ij8wPuz/o6v8wHkX2yQl38JeDUmRQJxO8szNcHpQkLLIax fodh+BO5zydkhYKNvO0vhJQ/UmILV0CVPwDnbMeC4nJlAEq6w9jZbrxNyzI26yMOu58ahQSH jyphaT5l+t9wGjGeCENDnTj57dWqqkPnxFo92U8AWq1tODLvdIN5y0Jww8LFlxU6j5lz9NMP nNaMhwpBKeWoBZtqstxf0GtPABjAhem1FT74AYLnjeBTm2DdG/EHEsiM8mjoWEb9GN9eGBA3 be6kWzKbxfjTPvT7AATB3F3iqXEZsNj0yH/g+abJtShM7hmRCv6k4msSHEtqRC6MfguhUbCm /ZmzNxwZYL/KyQUha8xUKue6pg9VzGGI35kU9h63aZUA1zZRi6+6QKOJ2+1ZMlJAf7Aqm28K s52I/NwRwaM7zmPoh8bFJwzDedNxtBx3+U7e5TvOWIimJmcpGAwsJvvqw7PtFVySNBqycsAO ofdcgyZKVOphFxWpnTsqfdVMW/pcPgGYwzBhNqOytsrLK5aku9QchAV6ICW7lG1Kwps+iyGs DzTP5H2y/NQ8qUyvo/OPJgaOSCKB4LdaOC6/jq3kexyVvLUEMKXtwoquljtZAtXGr0KWuVIr 7eGsf+p/UbJoIcJV3v9nr+fHZJo/uS3ZvJcaejsHUlZnAyDec7i2AQC8GaGMq50kMtRy82kZ gmgYu6ySIIxd/JC4kZKMg5yPg04CavlSovB/waGsOWqGBwR9SflPeGX3yblQk8DfxBZJqCkL BH/vsifw+xxraNOIUQhLO5nCZopG23Tc/IqWPOpvAbJE1TypE2Jv4bjsh8S6TvrLH2gO+Si6 LLnQinOTjiDiJvq/vp47bMr5gY2CUxji9YeZkgeot56qw6rBV48cNgyD880NYF2oAfTirfDe zD/XEkzA37cXBNFUynGzvbNYwO9PtEKa/DFfmEH3kXNZymPUdbKRPMr8yp7+H55dwfy1Ozte 5lU5nT0OQP32Z1zA/oa4vugm+p82/fG3TQy9Fvgl9DpSQMraVnQOKeNwCIWPcAGLy3MqKkPD W08RGQBX1viDECtTIBvfHlaHBxftzTqp9ntgeFj3/6H07h3DsUZoBE8Bw03+rIGZcUOYrUJQ BsbgkOTtnuO1CV7VbQB4roUbGwdNR5PNse/Ja7nAwYVmslcL4jh09wqxUIycS3pxOKT/54xW NVhD7jSyXlp8Hxs5YA=
  • Ironport-hdrordr: A9a23:lD8M36jG5lQKN667AvrTJ3OednBQXv4ji2hC6mlwRA09TyX4rb HKoB1/73XJYVkqKRcdcLy7Scu9qDbnhOVICPcqTM2ftXjdyQ+VxehZhOOIsl7d8m/Fh5dgPM 9bE5SWY+eAamSS4/yKmDWQIpIPxJ2o/smT6ts2DE0AceipUcxdBstCZDpzancGOTWuzKBZKK ah
  • Ironport-phdr: A9a23:zyh2TRytbt7Z/3TXCzKUw1BlVkEcU1XcAAcZ59Idhq5Udez7ptK+Z xWZvK83xwaTAc3y0LFttan/i+PaZSQ4+5GPsXQPItRndiQuroEopTEmG9OPEkbhLfTnPGQQF cVGU0J5rTngaRAGUMnxaEfPrXKs8DUcBgvwNRZvJuTyB4Xek9m72/q99pDdfglEniexba1sI Bm5sAndqMYbipZ+J6gszRfEvnRHd+NKyG1yIl6dgwjy7dqq8p559CRQtfMh98peXqj/Yq81U 79WAik4Pm4s/MHkugXNQgWJ5nsHT2UZiQFIDBTf7BH7RZj+rC33vfdg1SaAPM32Sbc0WSm+7 6puVRTlhjsLOyI//WrKjMF7kaBVrw+7pxFnw4DbfI6aOudwcKPTY90VR2lPUMFKWiNbHo+8a pECD+odMetaqYT2ulsArQG5BQmpHO7vzyJIhnzo0q0h0+QqDB3G3A0uHt0UqnTUrcj+OaAXU eCoz6nH0y7Db/NK2Tf85onHaAohofCWUbJxcMrRyFUvFwbeg1WfrIzqJTKV1uAXv2eH6OpgU Puihmg6oA5+vjah3N0jipXVho0L0FDE8z10zYYoKNC2R0N2Y9qpHpVQuSyZM4Z7QM0sT3xst Ss717ELtp62cSYWxJg62hLSd/yJfoqG7x79SOqcJSt1iX1ndb+5mh288lCgx/XiWsWo1FtGt ClIn9nWunwTyRDf99KLR/R980u5xzqAzRzf5ftBLE8qm6rWJIItz7stmpYNsUnMBSr7lUryg aOKa0kp/+ql5/j7brr7o5KTLJN7hwX+P6krmsGzHeo1PwcLUmSG++mzyL/u8EvkS7hUiv02j 7LZsIzEKsQBu6C5Ag5U3Zg75hqjCTqtzc4WkmMdLF1ffRKKl4jpNE/KIPD/Ffq/hk6jkDZvx /zfMLzhGIjBImHNkLrufbtx8UFcyA00zdBQ45JbFKsNL+70Wk/0rNDYDxk5PBKow+v/Ftlxy ocTVXiMD6KZKq/er0GE6v81L+SDZIIZoDP9JOIk5/7qg385g1gdfayx0JsSdXC4HeppI16ZY Xrwg9cAH30FvhA/TODwiV2CUD9TZ2q3X68n6TE7DZipDYbHRoy3nLOB2yK7EoVQZm9dEl+MC 2vnd52YW/cQbyKfOtJtniQeVbe9U48hyQ2utAjixrV7KerU4zQUuo7n1Nho/OLejgoy9DxxD 8SFyW6BVWB0nmUSRz83xq9zu0J9yk3QmZR/1vdfDJlY4+5DegY8L5/VieJgWP7oXQeUe8qKR U2mCsmnHjgrT5plxsINbl19B9S9hwrCmSurAqMQv7OODZ0wtKnb2i6idI5G13/a2fx53BEdS cxVODj+7kYe3w3aBoqS1l6ci77vbqMEmijE6GaEy2OK+kBeSg95F6vfDjgEfkWDi9P/6wvZS qO2T6w9O15E1M2PMatWa8Lgl1QARfbiJNH2bGe4mmP2DhGNlfuXdIS/Q2wGx23GDVQc1QUa/ HKILw87UyK8oG/FDCBvClv1YgXt8OhirVu0S0Y1y0eBaEgyn6Gt9EszgvqRA+gWwqpCuColr GBsG02h2tvNF9eajw9ofaEZfslkpVkbiCTWsAtyOpHmJKdn7rIHWyJwuU6mlxB+C4Eb1NMvs Gtv1w1qb6SRzFJGcTqcm5H2ILzebGforlipbObN11fS3czzmO9H4ekkq1jloACiF1Yzu3Rh3 d5P1nKA55LMRAMMWJP1W0wz+lB0vbbfKiU64orV0zVrP8zW+nfHxtEkH+s5ywmpZdYZMaKFC AraHMgTBszoI+sv2hCoYh8CIOFO5fssJcr1EpnOkKWvPetmgHenlTEduNE7gh/KrXAlDLKVj PNni7mC0wCKVinxlgKku8HzwsVfYC0KW3G40W7iDZJQYat7ecAKD32vKou53IYb5dalVnhG+ VqkH15D1tWufE/YakH+0BZQyUUIqGam3yq5ziBxuz4sp6ubmifJxq6xEXhPcn4OX2RkgVr2d MKxktMXR0i0bhcgjhrj5Ef7261zq6F2Lm2VSkBNNXuTTSkqQu67sbyMZNRK4ZUjvHBMUeiyV ludT6b0vxoQ1y6L83J2/DkgbHnqv5z4m0c/k2eBNDNoq2Kff8hsxBDZ7diaRPhL3zNASjMqw TXQA1G9OZGu87D239/Gr+OzTGK9V4JaayitzIKBqC6T6mhjABn5lPe20tHqCgk11ybn2sIiD 32Z6kahJNOxjuLmbKpuZSwKTBfk5tB/G51in4d4n5wW1XUAx92U8XcBjWbvIIBe0KP6YmAKQ G1DyNrU7Q75nUx7eyjRlsSpCzPHmJInO4TpBwFekjgw5M1LFqqOublNnC8u50G9sRqUev9l2 DEU1fop7ncexeAPogskiCuHUdVwVQFVOzLhkxOQ4pWwtqJSMSyqbLu9z0pinM+oFrDEowBdR HPRdZIrHCs25cJ6egGpsjW7+sT/dd/cYMhG/BiJkBrbj/RUN5srl7wLhCt7PEryuHQkz6gwi hkkjvTY9MCXbm5q+qy+GBtRMDb4MtgS9j/ahqFbhs+K3oqrE8YpCnARUZDvV/7tDCMKuKGtK VOVCDNl4CT+e/KXDUqF5UxhtX6KD527KyTdOiwC1ds7DBiFeB4E3UZNDW18xMJmUFjtnpCpc V8ltG5NoASj8V0VlLoub16mAwK97E+pcmtmFsbZdUIMqFkEvwCPaYSf9r4hQX8epMHw6lzVb DTcPVwADHlVCBPeQQm/eOD/v5+YtLHIY4j2Z/rWPefR9aoHDarOndT3ldI4tzeUapfWZikkV qJknBoFBTcjQozYg2ldEnNM0XucM4jD4k/7o3MSzIj38ey3Cli3tM3fVv0La4Upo1fv3u+CL 7LC3n8nb2sIkMpdnzmQj+FOlF8K13M0LmfrS+9R83WXCvqXw/4ybVZTfSp3MIEgA7sU+A5LN Iabj9r00uU9lfspExJeUkSnnMi1ZMsMKmX7NVXdBU/NOq7UbTvMi9r6Z6+xU9gyxK1dqgGwt DCHEkTiIiXLlj/nUAqqOP1NiyfTNQJXuYW0eBJgQWb5S9euZhq+Od5xxTo4pN98zmvNLnIZO CNgflllq7SR6WZHmKw6FTAcqHViKuaAlmCS6OyZYpcavP13AzhlwuJX5HNprtkdpCpARfFzh G7Ttos0+wDgwrTJkGA+FkYT+VMpzMqRsE5vOLvU7MxFUHfAp1cW6HmITg8Nv51jA8HuvKZZz p7OkrjyIXFM6YGxn4NUCs7KJcaAKHdkPwDuHWueCRYGQCWrKWDAjlZc1vCT92GQhpc/o5no3 pEJT/UIMT59XuNfEUljENEYdd1vWSg4lLeAkMMSzX+3rR2UW98D+56bC7SdBvLgLDvfhr5BL Uhto/uwPcEYMYv13FZnY19xkdHRGkbeattKpzVocg4+pEglGJ1WQWg62kajYQSosid7/RGck Rs/iw84auMopm6EC7YfI1PLoG4vihB0l4m4xz+WdzH1IeG7WoQEU0LJ
  • Ironport-sdr: 67704ef2_759mYPasIIc9eN1DHKS7r4zJg11t6YLMIF4Czug52idZDk3 K6rVVoxoZbXfZpLXVXLIGkze/bElKVrrPj8nYdQ==

Hi Richard,

Below is the code. I have slightly modified your code because I was not able to run it locally. To prove pairN, I have used two axioms *prop_degeneracy* (classical logic) and *functional_extentionality*. My intuition is that it cannot be proven in Coq because of this goal (but I am not a type theorist so I could be wrong).  

 object : Type
 eq_dec : ∀ x y : object, {x = y} + {x ≠ y}
 x : object
 f : object → Prop
 y : object
 Hb : x ≠ y
 Ha : (False = True) = (f y = True)
 ============================
  False = f y


From Coq Require Import Utf8.
Require Import Coq.Logic.FunctionalExtensionality.

Section Richard.
  Variable (object : Type).
  Variable (eq_dec : forall (x y : object), {x = y} + {x <> y}).

  Inductive N : Type :=
  | Caract : (object -> Prop) -> N.

  Definition caract (s : N) (a : object) : Prop :=
    let (f) := s in f a.

  Definition In (s : N) (a : object) : Prop :=
    caract s a = True.

  Definition incl (s1 s2 : N) :=
    forall a : object, In s1 a -> In s2 a.

  Definition set_eq (s1 s2 : N) :=
    forall a : object, In s1 a = In s2 a.

  Definition L (a : object) : N :=
    Caract
      (fun a' : object =>
         match eq_dec a a' with
         | left _ => True
         | right _ => False
         end).

  Axiom prop_degeneracy : forall (P : Prop),
      P = True \/ P = False.


  Lemma false_true_equality : (False = True) = (True = True) -> False.
  Proof.
    intros Ha.
    assert (Hb : True = True) by reflexivity.
    rewrite <- Ha in Hb.
    rewrite Hb.
    exact I.
  Qed.
  

  Lemma pairN : forall (x : object) (A : N),  L x = A <-> set_eq (L x) A.
  Proof.
    intros x A.
    split.
    -
      intro Ha; subst.
      unfold set_eq; intro a.
      apply eq_refl.
    -
      intro Ha.
      unfold set_eq, In in Ha.
      destruct A as [f]. cbn in Ha.
      unfold L.
      f_equal.
      eapply functional_extensionality; intro y.
      specialize (Ha y).
      destruct (eq_dec x y) as [Hb | Hb].
      +
        eapply eq_sym.
        rewrite <-Ha.
        exact eq_refl.
      +
        (* I am committing a sin :-) *)
        destruct (prop_degeneracy (f y)) as [Hc | Hc].
        ++
          rewrite Hc in Ha.
          eapply false_true_equality in Ha.
          inversion Ha.
        ++
          rewrite Hc.
          exact eq_refl.
  Qed.

End Richard.



Best, 
Mukesh 

On 28 Dec 2024, at 14:41, richard <richard.dapoigny AT univ-smb.fr> wrote:

Dear Coq user,

I am working on sets with characteristic functions and a datatype called object for wich equality is decidable.

Singletons called ι are also defined in this context. An excerpt of the code is given below.

Definition object: Type := t.

Definition eqobject_dec := eq_dec.

Inductive N : Type :=
    | Caract  : (object -> Prop) -> N.

Definition caract (s :N)(a:object) : Prop := let (f) := s in f a.
Definition In (s :N)(a:object) : Prop := caract s a = True.
Definition incl (s1 s2 :N) := forall a:object, In s1 a -> In s2 a.
Definition set_eq (s1 s2 :N) := forall a:object, In s1 a = In s2 a.

Definition ι (a:object) :=
  Caract
    (fun a':object =>
       match eqobject_dec a a' with
       | left h => True
       | right h => False
       end).

My question is the following : is there a possibility to prove the pairing axiom with these assumptions, i.e.  to prove that 

Lemma pairN : forall (x:object)(A:N), set_eq (ι x) A <-> ι x = A.

In addition we assume classical logic.

Thanks in advance,

Richard





Archive powered by MHonArc 2.6.19+.

Top of Page