Coqで自分で集合と空集合を定義し、Theorem notinempty T a : ~ In (EmptySet T) a.を証明してください。
- User
Coqで自分で集合と空集合を定義し、Theorem not_in_empty T a : ~ In (EmptySet T) a.を証明してください。
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.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.
Identical first prompt
claude-sonnet-4-20250514Compare side by side →
- o3-2025-04-16Compare side by side →
deepseek-v3-0324Compare side by side →
gemini-2.5-flashCompare side by side →
gemini-2.5-flash-preview-04-17Compare side by side →
claude-opus-4-20250514Compare side by side →
- grok-3-preview-02-24Compare side by side →
claude-opus-4-20250514Compare side by side →
gemini-2.5-flashCompare side by side →
claude-opus-4-20250514Compare side by side →
- gpt-4.1-mini-2025-04-14Compare side by side →