Coqで自分で集合と空集合を定義し、Theorem notinempty T a : ~ In (EmptySet T) a.を証明してください。
- User
Coqで自分で集合と空集合を定義し、Theorem not_in_empty T a : ~ In (EmptySet T) a.を証明してください。
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の証明が完了したことが確認できます。 *)解説
-
Definition Set (T : Type) : Type := T -> Prop.Setという型コンストラクタを定義します。これは型Tを受け取り、T -> Propという型を返します。T -> Propは、「T型の値を受け取り、命題(真偽)を返す関数」を意味します。これがCoqにおける最も基本的な集合の表現方法です。
-
Definition In {T : Type} (s : Set T) (a : T) : Prop := s a.- 要素
aが集合sに「属する(In)」ことを定義します。 - 集合
sはT -> Prop型の関数なので、s aと書くと、aがsに属するかどうかを評価する命題が生成されます。
- 要素
-
Definition EmptySet (T : Type) : Set T := fun (_ : T) => False.EmptySetは型Tを受け取り、その型の空集合を返します。fun (_ : T) => Falseは、T型のどんな要素が入力されても常にFalse(偽)を返す関数です。これは「いかなる要素も含まない」という空集合の定義にぴったり合致します。
-
Theorem not_in_empty (T : Type) (a : T) : ~ In (EmptySet T) a.- 証明すべき定理です。
~ PはCoqではP -> Falseの糖衣構文(syntactic sugar)です。つまり、「Pが真であると仮定すると矛盾(False)が生じる」ことを意味します。- したがって、この定理は「
aがEmptySet Tに属すると仮定すると、矛盾が生じる」ことを証明するものです。
-
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の論理システム上で集合と空集合の基本的な性質を厳密に定義し、証明することができます。
-
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-proCompare 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 →