Cookies disclaimer

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.

One class less

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

theory Defs
imports Main

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 }"


Template File

theory Submission
  imports Defs

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)"


Check File

theory Check
imports Submission

  "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)


Terms and Conditions