Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-flash· GoogleHugging Face LMArena Human Preference 140K

Coqで自分で集合と空集合を定義し、Theorem notinempty T a : ~ In (EmptySet T) a.を証明してください。

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Geminigemini-2.5-flash-preview-04-17’s answer.
  1. User

    Coqで自分で集合と空集合を定義し、Theorem not_in_empty T a : ~ In (EmptySet T) a.を証明してください。

  2. Gemini Assistant

    Coqで集合を定義し、空集合と、その性質である「空集合には要素が含まれない」ことを証明します。

    Coqでは、数学的な「集合」を様々な方法で表現できます。最も一般的で柔軟な方法は、ある型Tの要素がその集合に属するかどうかを判定する**述語(predicate)**として定義することです。つまり、集合SはT -> Propという関数型になります。S xがProp(命題)として真ならばxはSに属し、偽ならば属しません。

    Coqコード

    (* ----------------------------------------------------------- *)
    (* 1. 集合の定義 (Definition of a Set)                         *)
    (* ----------------------------------------------------------- *)
    
    (* 'Set T'は、型Tの要素に対する述語(T -> Prop)として定義されます。
       つまり、Set T型の値sは、s xが真ならばxが集合sに属することを示します。 *)
    Definition Set (T : Type) : Type := T -> Prop.
    
    (* 集合sに要素aが属すること('a In s')を定義します。
       これは単に、集合を表現する述語sにaを適用した結果が真である、とします。 *)
    Definition In {T : Type} (s : Set T) (a : T) : Prop := s a.
    
    (* ----------------------------------------------------------- *)
    (* 2. 空集合の定義 (Definition of EmptySet)                    *)
    (* ----------------------------------------------------------- *)
    
    (* 空集合は、いかなる要素も含まない集合です。
       したがって、型Tのいかなる要素xに対しても、
       EmptySet T xが常に偽(False)となるように定義します。 *)
    Definition EmptySet (T : Type) : Set T := fun (_ : T) => False.
    
    (* ----------------------------------------------------------- *)
    (* 3. 定理の証明 (Proof of Theorem)                            *)
    (* ----------------------------------------------------------- *)
    
    (* 定理: 任意の型Tと、その型の任意の要素aに対して、
       aはTの空集合に属さない。(aが空集合に属することは偽である) *)
    Theorem not_in_empty (T : Type) (a : T) : ~ In (EmptySet T) a.
    Proof.
      (* Goal: ~ In (EmptySet T) a
         これは ~ (In (EmptySet T) a) と同じです。
         つまり、In (EmptySet T) a が真であると仮定すると矛盾が導かれる、という形です。 *)
    
      (* InとEmptySetの定義を展開して、目標を簡略化します。 *)
      simpl.
      (* Goal: ~ False
         simpl (または unfold In, EmptySet.) を適用すると、
         In (EmptySet T) a が (fun (_ : T) => False) a に展開され、
         さらに False に簡約されます。
         したがって、目標は「Falseではない」、つまり「FalseであることからFalseを導く」となります。 *)
    
      (* 否定の定義 (~P は P -> False) に基づき、
         目標の False を仮定 H として導入します。 *)
      intro H.
      (* Context: H : False
         Goal: False
         HがすでにFalseなので、Hをそのまま提示すれば目標が達成されます。 *)
    
      (* Hをそのまま証拠として使用します。 *)
      exact H.
    Qed.
    
    (* ----------------------------------------------------------- *)
    (* 検証 (Verification)                                        *)
    (* ----------------------------------------------------------- *)
    (* CoqIDEでこのコードを実行すると、各定義と定理が正常にロードされ、
       not_in_emptyの証明が完了したことが確認できます。 *)
    

    解説

    1. Definition Set (T : Type) : Type := T -> Prop.

      • Setという型コンストラクタを定義します。これは型Tを受け取り、T -> Propという型を返します。
      • T -> Propは、「T型の値を受け取り、命題(真偽)を返す関数」を意味します。これがCoqにおける最も基本的な集合の表現方法です。
    2. Definition In {T : Type} (s : Set T) (a : T) : Prop := s a.

      • 要素aが集合sに「属する(In)」ことを定義します。
      • 集合sはT -> Prop型の関数なので、s aと書くと、aがsに属するかどうかを評価する命題が生成されます。
    3. Definition EmptySet (T : Type) : Set T := fun (_ : T) => False.

      • EmptySetは型Tを受け取り、その型の空集合を返します。
      • fun (_ : T) => Falseは、T型のどんな要素が入力されても常にFalse(偽)を返す関数です。これは「いかなる要素も含まない」という空集合の定義にぴったり合致します。
    4. Theorem not_in_empty (T : Type) (a : T) : ~ In (EmptySet T) a.

      • 証明すべき定理です。
      • ~ PはCoqではP -> Falseの糖衣構文(syntactic sugar)です。つまり、「Pが真であると仮定すると矛盾(False)が生じる」ことを意味します。
      • したがって、この定理は「aがEmptySet Tに属すると仮定すると、矛盾が生じる」ことを証明するものです。
    5. Proof.

      • simpl.: これは、InとEmptySetの定義を展開し、式を簡約するタクティックです。
        • In (EmptySet T) a は (EmptySet T) a に展開されます。
        • (EmptySet T) a は (fun (_ : T) => False) a に展開されます。
        • ((fun (_ : T) => False) a) はCoqの計算規則(ベータ簡約)によってFalseに簡約されます。
        • したがって、目標は ~ False となります。
      • intro H.: ~ False は False -> False なので、FalseをHという仮定としてコンテキストに導入します。
      • exact H.: HがすでにFalseであるため、目標のFalseをHそのもので証明します。

    この方法で、Coqの論理システム上で集合と空集合の基本的な性質を厳密に定義し、証明することができます。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.