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.

[2018-Dec] 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?

Resources

Download Files

Definitions 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

Template File

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

Check File

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