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?

## Resources

### 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