Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-pro· 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 DeepSeekdeepseek-v3-0324’s answer.
  1. User

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

  2. Gemini Assistant

    はい、承知いたしました。Coqで独自の集合と空集合を定義し、Theorem not_in_empty T a : ~ In (EmptySet T) a. を証明する方法を、ステップバイステップで解説します。

    集合の表現方法

    Coqで集合を表現する最も一般的で強力な方法は、「述語(predicate)」として定義することです。つまり、型 T の要素の集合は、「型 T の値を受け取り、命題 Prop を返す関数」として表現できます。

    • s : T -> Prop という関数があったとします。
    • ある要素 a : T が集合 s に含まれるとは、s a という命題が真であることだと定義します。
    • s a が偽であれば、a は集合 s に含まれません。

    この考え方に基づいて、集合、所属関係、空集合を定義し、定理を証明します。


    1. 集合、所属関係、空集合の定義

    まず、必要な定義をCoqで記述します。

    (* --- 1. 集合の型の定義 --- *)
    (* 型Tの集合とは、Tから命題(Prop)への関数であると定義する *)
    Definition Set (T : Type) : Type := T -> Prop.
    
    (* --- 2. 所属関係 'In' の定義 --- *)
    (* sが集合で、aが要素のとき、'aがsに属する'とは、s aが真であること *)
    (* {T : Type} のように波括弧で囲むと、Coqが文脈から型を推論してくれる *)
    Definition In {T : Type} (s : Set T) (a : T) : Prop := s a.
    
    (* 数学の記法 '∈' を使えるようにする *)
    Notation "x ∈ s" := (In s x) (at level 70).
    
    (* --- 3. 空集合 'EmptySet' の定義 --- *)
    (* 空集合とは、どんな要素aに対しても偽(False)を返す集合である *)
    (* _ は、その引数を使わないことを明示する *)
    Definition EmptySet {T : Type} : Set T := fun (_ : T) => False.
    
    (* 空集合の記法 '∅' を使えるようにする *)
    Notation "∅" := EmptySet.
    

    2. 定理の証明

    上記の定義を使って、目的の定理 not_in_empty を証明します。この定理は「任意の要素 a は、空集合 ∅ には含まれない (~ (a ∈ ∅))」ということを主張しています。

    Coqでは、~ P (Pの否定) は P -> False (Pを仮定すると矛盾に至る) の糖衣構文(syntactic sugar)です。このことを念頭に置いて証明を進めます。

    以下に、証明のステップを詳しく解説したバージョンと、より簡潔なバージョンの2つを示します。

    証明 (詳細なステップ解説付き)

    この証明は、各タクティクが何をしているかを理解するのに役立ちます。

    (* 定理:任意の型Tと、その型の要素aについて、aは空集合には属さない *)
    Theorem not_in_empty_detailed : forall {T : Type} (a : T), ~ (a ∈ ∅).
    Proof.
      (* 1. ゴールを 'P -> False' の形にする *)
      (* notの定義を展開する *)
      unfold not.
      (*
        現在のゴール:
        forall (T : Type) (a : T), a ∈ ∅ -> False
      *)
    
      (* 2. 全称量化子と仮定を導入する *)
      (* 任意の T, a を導入し、'a ∈ ∅' を H という名前の仮定として導入する *)
      intros T a H.
      (*
        現在のコンテキスト:
        T: Type
        a: T
        H: a ∈ ∅
        --------------------
        現在のゴール:
        False
      *)
    
      (* 3. 仮定Hの定義を展開する *)
      (* まず、記法 '∈' を In に展開する *)
      unfold In in H.
      (*
        H: In ∅ a
        ...
      *)
    
      (* 次に、空集合 '∅' (EmptySet) の定義を展開する *)
      unfold EmptySet in H.
      (*
        H: (fun (_ : T) => False) a
        ...
        (fun (_ : T) => False) という関数に a を適用すると、結果は 'False' になる。
        Coqはこれを自動で計算(β簡約)してくれる。
        結果として、仮定Hは 'False' そのものになる。
      *)
      (*
        現在のコンテキスト:
        T: Type
        a: T
        H: False  <-- 仮定が矛盾そのものになった!
        --------------------
        現在のゴール:
        False
      *)
    
      (* 4. 仮定を使ってゴールを証明する *)
      (* ゴールは 'False' であり、仮定Hも 'False' である。
         したがって、仮定Hをそのまま使えばゴールを達成できる。 *)
      exact H.
    Qed.
    

    証明 (よりCoqらしい簡潔なバージョン)

    実際のCoqプログラミングでは、より自動化されたタクティクを使い、証明を短く書くことがよくあります。

    Theorem not_in_empty : forall {T : Type} (a : T), ~ (a ∈ ∅).
    Proof.
      (* intros で T, a と仮定 H: a ∈ ∅ を一気に導入する *)
      intros T a H.
      (*
        H: a ∈ ∅
        -----------
        False
      *)
    
      (* H の定義を展開すると、H が False と同義であることがわかる *)
      unfold In, EmptySet in H.
      (*
        H: False
        -----------
        False
      *)
    
      (* contradiction タクティクは、仮定の中に矛盾 (False) があることを見つけて
         証明を完了させてくれる。 'exact H.' と同じ働きをする。 *)
      contradiction.
    Qed.
    

    trivial というタクティクを使えば、さらに短く書くこともできます。trivialは定義を展開して自明なゴールを自動で証明しようと試みます。

    Theorem not_in_empty_trivial : forall {T : Type} (a : T), ~ (a ∈ ∅).
    Proof.
      trivial.
    Qed.
    

    全体のコードまとめ

    以下に、定義から証明までをまとめた完全なCoqコードを記載します。

    (* Coq 8.1x.x *)
    
    (* --- 1. 集合の型の定義 --- *)
    Definition Set (T : Type) : Type := T -> Prop.
    
    (* --- 2. 所属関係 'In' の定義 --- *)
    Definition In {T : Type} (s : Set T) (a : T) : Prop := s a.
    
    (* 数学の記法 '∈' を使えるようにする *)
    Notation "x ∈ s" := (In s x) (at level 70).
    
    (* --- 3. 空集合 'EmptySet' の定義 --- *)
    Definition EmptySet {T : Type} : Set T := fun (_ : T) => False.
    
    (* 空集合の記法 '∅' を使えるようにする *)
    Notation "∅" := EmptySet.
    
    (* --- 4. 定理と証明 --- *)
    (* 定理:任意の型Tと、その型の要素aについて、aは空集合には属さない *)
    Theorem not_in_empty : forall {T : Type} (a : T), ~ (a ∈ ∅).
    Proof.
      (*
        証明の意図:
        1. `~ P` は `P -> False` と定義されている。
        2. よって、`a ∈ ∅` を仮定する (これを H とする)。
        3. `a ∈ ∅` の定義を展開すると `In ∅ a` となり、
           さらに `EmptySet a` となり、最終的に `False` になる。
        4. つまり、仮定 H は `False` そのものである。
        5. `False` を仮定して `False` を導くのは自明なので、証明は完了する。
      *)
    
      (* T と a を導入する *)
      intros T a.
      (* `~ (a ∈ ∅)` は `(a ∈ ∅) -> False` なので、仮定 `a ∈ ∅` を導入する *)
      intro H.
      (* H の定義を展開すると、Hは `False` になる *)
      unfold In, EmptySet in H.
      (* 仮定H (`False`) からゴール (`False`) を証明する *)
      exact H.
    Qed.
    
    (* 証明が完了したことを確認 *)
    Print not_in_empty.
    

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