I agree Our site saves small pieces of text information (cookies) on your device in order to deliver better content and for statistical purposes. You can disable the usage of cookies by changing the settings of your browser. By browsing our website without changing the browser settings you grant us permission to store that information on your device.

Santa is playing around with presents and classes of presents. He realizes that he has two presents that he classifies differently but are actually quite equivalent presents. He wants to merge these classes, and is sure that after that there is one such class less.

Can you help him prove that?

Download Files
### Definitions File

### Template File

### Check File

theory Defs imports Main begin definition per_union where "per_union R a b \<equiv> R \<union> { (x,y). (x,a)\<in>R \<and> (y,b)\<in>R } \<union> { (y,x). (x,a)\<in>R \<and> (y,b)\<in>R }" end

theory Submission imports Defs begin lemma one_less_class: assumes "R``{x} \<noteq> R``{y}" and inV: "y\<in>V" "x\<in>V" and "R\<subseteq>V\<times>V" and eq: "equiv V R" and [simp]: "finite V" shows "Suc (card (quotient V (per_union R x y))) = card (quotient V R)" sorry end

theory Check imports Submission begin lemma "R``{x} \<noteq> R``{y} \<Longrightarrow> y\<in>V \<Longrightarrow> x\<in>V \<Longrightarrow> R\<subseteq>V\<times>V \<Longrightarrow> equiv V R \<Longrightarrow> finite V \<Longrightarrow> Suc (card (quotient V (per_union R x y))) = card (quotient V R)" by (rule Submission.one_less_class) end

Terms and Conditions