Skip to content
The Chat Archive
gemini-2.5-pro· Google LMArena Human Preference 140K

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

  1. User

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

  2. Assistant

    はい、承知いたしました。 Coqで集合と空集合を(特性関数を用いて)定義し、ご指定の定理 not_in_empty を証明します。

    コードと証明

    (* 1. 集合の型の定義 *)
    (* 型 T の要素の集合は、T の各要素に対してそれが集合に含まれるか否かという命題を返す関数(述語)として定義します。*)
    Definition Set (T : Type) := T -> Prop.
    
    (* 2. 要素が集合に属すること (In) の定義 *)
    (* 要素 a が集合 S に属するとは、関数 S に a を適用した結果の命題が真であることを意味します。*)
    Definition In {T : Type} (a : T) (S : Set T) : Prop := S a.
    
    (* 補足:In の引数の順序を (S a) と逆にすることもよくあります。 *)
    (* Definition In {T : Type} (S : Set T) (a : T) : Prop := S a. *)
    (* このドキュメントでは (a S) の順序で進めますが、どちらでも本質は同じです。*)
    
    (* 3. 空集合 (EmptySet) の定義 *)
    (* 空集合とは、どの要素を渡されても「その要素は集合に含まれない」という命題、つまり常に偽 (False) を返す関数のことです。*)
    Definition EmptySet (T : Type) : Set T := fun (_ : T) => False.
    
    (* 4. 定理の証明 *)
    (* 定理:任意の型 T とその要素 a について、a は空集合の要素ではない。 *)
    Theorem not_in_empty : forall (T : Type) (a : T), ~ In a (EmptySet T).
    Proof.
      (* 証明したい変数を導入します。*)
      intros T a.
      
      (* ゴールは ~ In a (EmptySet T) です。*)
      (* Coqにおいて ~ P は P -> False の糖衣構文なので、それを展開します。*)
      unfold not.
      (* ゴールは In a (EmptySet T) -> False となります。*)
    
      (* In と EmptySet の定義を展開します。*)
      unfold In.
      unfold EmptySet.
      (* ゴールは ((fun _ => False) a) -> False となります。*)
      (* (fun _ => False) a は False に簡約されるので、ゴールは実質的に False -> False です。*)
    
      (* In a (EmptySet T) が成り立つという仮定 H を導入します。*)
      intro H.
      
      (* この時点で、仮定 H は In a (EmptySet T) であり、*)
      (* これは展開すると (fun _ => False) a となり、さらに False となります。*)
      (* つまり、我々の仮定は H : False です。*)
      
      (* 仮定 H (False) からゴールである False を証明するのは自明です。*)
      exact H.
    Qed.
    
    (* 証明の別解(より短く)*)
    Theorem not_in_empty_short : forall (T : Type) (a : T), ~ In a (EmptySet T).
    Proof.
      intros T a.
      unfold not, In, EmptySet.
      (* この時点でゴールは ((fun _ : T) => False) a -> False となる。*)
      (* この命題は自明に真なので、Coq は自動で証明できます。*)
      tauto.
    Qed.
    

    解説

    1. 集合の定義 (Set): Coqで集合を表現する最も一般的な方法は、特性関数(または述語)を用いることです。Set T を T -> Prop と定義しました。これは、「型 T の値を受け取り、その値が集合の要素であるかどうかを判定する命題 (Prop) を返す関数」が集合である、と定めています。

    2. 所属関係の定義 (In): In a S は、要素 a が集合 S に属していることを表します。私たちの Set の定義に基づけば、これは単に S という関数に a を適用することと同じです。S a が真の命題であれば、a は S に属します。

    3. 空集合の定義 (EmptySet): 空集合は、いかなる要素も含まない集合です。これを特性関数で表現すると、「どんな要素 x を与えられても、常に偽 (False) を返す関数」となります。fun (_ : T) => False がまさにその定義です。(_ は引数を使う必要がないことを示します)。

    4. 定理の証明 (not_in_empty):

      • Theorem not_in_empty : forall (T : Type) (a : T), ~ In a (EmptySet T).
        • この定理は「任意の型 T と、その型の任意の要素 a について、a は EmptySet T には属さない(~ In)」と主張しています。
      • intros T a.
        • 任意だと言われている T と a を固定して、議論を進めます。
      • unfold not.
        • Coqでは ~ P は P -> False の略記法です。証明を分かりやすくするため、この定義を展開します。ゴールは In a (EmptySet T) -> False に変わります。
      • unfold In, EmptySet.
        • 次に、In と EmptySet の定義を展開します。
        • In a (EmptySet T) は (EmptySet T) a になります。
        • (EmptySet T) a は (fun (_ : T) => False) a になります。
        • この関数適用 (fun (_ : T) => False) a を計算(β簡約)すると、結果は False そのものになります。
      • intro H.
        • P -> Q を証明するには、P を仮定して Q を導きます。ここでは In a (EmptySet T) を H という名前で仮定します。
      • しかし、上記で見たように In a (EmptySet T) の正体は False です。したがって、intro H を実行した時点で、我々の仮定 H の型は False となります。
      • exact H.
        • 証明のゴールは False であり、仮定として H : False を持っています。したがって、仮定 H を使えばゴールを直接満たすことができます。exact タクティックは、ゴールと完全に一致する仮定がある場合に証明を完了させます。

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