gemini-2.5-pro· Google LMArena Human Preference 140K
Coqで自分で集合と空集合を定義し、Theorem notinempty T a : ~ In (EmptySet T) a.を証明してください。
- User
Coqで自分で集合と空集合を定義し、Theorem not_in_empty T a : ~ In (EmptySet T) a.を証明してください。
- 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.解説
-
集合の定義 (
Set): Coqで集合を表現する最も一般的な方法は、特性関数(または述語)を用いることです。Set TをT -> Propと定義しました。これは、「型Tの値を受け取り、その値が集合の要素であるかどうかを判定する命題 (Prop) を返す関数」が集合である、と定めています。 -
所属関係の定義 (
In):In a Sは、要素aが集合Sに属していることを表します。私たちのSetの定義に基づけば、これは単にSという関数にaを適用することと同じです。S aが真の命題であれば、aはSに属します。 -
空集合の定義 (
EmptySet): 空集合は、いかなる要素も含まない集合です。これを特性関数で表現すると、「どんな要素xを与えられても、常に偽 (False) を返す関数」となります。fun (_ : T) => Falseがまさにその定義です。(_は引数を使う必要がないことを示します)。 -
定理の証明 (
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に変わります。
- Coqでは
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タクティックは、ゴールと完全に一致する仮定がある場合に証明を完了させます。
- 証明のゴールは
-
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-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 →