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?
[Thanks to the problem author Max Haslbeck, and the translators Sebastian Joosten (ACL2), and Kevin Kappelmann (Lean).]
theory Defs
imports Main
begin
definition per_union where "per_union R a b ≡ R ∪
{ (x,y). (x,a)∈R ∧ (y,b)∈R } ∪ { (y,x). (x,a)∈R ∧ (y,b)∈R }"
end
theory Submission
imports Defs
begin
lemma one_less_class:
assumes "R``{x} ≠ R``{y}" and inV: "y∈V" "x∈V" and "R⊆V×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} ≠ R``{y} ⟹ y∈V ⟹ x∈V ⟹ R⊆V×V ⟹ equiv V R ⟹ finite V
⟹ Suc (card (quotient V (per_union R x y))) = card (quotient V R)"
by (rule Submission.one_less_class)
end
(in-package "ACL2")
(defun symmetric-acc (orig lst)
(if (endp lst) (alistp orig)
(and (member-equal (cons (cdar lst) (caar lst)) orig)
(symmetric-acc orig (cdr lst))))
)
(defun trans-acc-acc (orig lst pair)
(if (endp lst) t
(and (implies (equal (caar lst) (cdr pair)) (member-equal (cons (car pair) (cdar lst)) orig))
(trans-acc-acc orig (cdr lst) pair)))
)
(defun trans-acc (orig lst)
(if (endp lst) (alistp orig)
(and (trans-acc-acc orig orig (car lst))
(trans-acc orig (cdr lst))))
)
(defun transitive (lst) (trans-acc lst lst))
(defun symmetric (lst) (symmetric-acc lst lst))
(defun reflexive-acc (orig lst)
(if (endp lst) (alistp orig)
(and (member-equal (cons (caar lst) (caar lst)) orig)
(reflexive-acc orig (cdr lst))))
)
(defun reflexive (lst) (reflexive-acc lst lst))
(defthm trans-acc-alist
(implies (trans-acc lst x)
(alistp lst)))
(defthm transitive-alist
(implies (transitive lst)
(alistp lst))
)
(defthm symmetric-acc-alist
(implies (symmetric-acc lst x)
(alistp lst)))
(defthm symmetric-alist
(implies (symmetric lst)
(alistp lst))
)
(defthm reflexive-acc-alist
(implies (reflexive-acc lst x)
(alistp lst)))
(defthm reflexive-alist
(implies (reflexive lst)
(alistp lst)))
(defthm trans-acc-acc-dest
(implies (and (trans-acc-acc orig lst (cons a b))
(member-equal (cons b c) lst))
(member-equal (cons a c) orig))
)
(defthm trans-acc-dest
(implies (and (trans-acc orig lst)
(member-equal (cons a b) lst)
(member-equal (cons b c) orig))
(member-equal (cons a c) orig))
)
(defthm transitive-dest
(implies (and (transitive lst)
(member-equal (cons a b) lst)
(member-equal (cons b c) lst))
(member-equal (cons a c) lst))
)
(defthm sym-acc-dest
(implies (and (symmetric-acc orig lst)
(member-equal (cons a b) lst))
(member-equal (cons b a) orig))
)
(defthm symmetric-dest
(implies (and (symmetric lst)
(member-equal (cons a b) lst))
(member-equal (cons b a) lst))
)
(defthm reflexive-1
(implies
(and (transitive lst)
(member-equal (cons a b) lst)
(member-equal (cons b a) lst))
(member-equal (cons a a) lst))
)
(defthm reflexive-2
(implies
(and (transitive lst)
(symmetric lst)
(member-equal (cons a b) lst))
(member-equal (cons a a) lst))
)
(defthm trans-sym-then-reflexive-acc
(implies (and (transitive orig) (symmetric orig)
(case-split (subsetp lst orig)) (case-split (alistp lst)))
(reflexive-acc orig lst)
)
:rule-classes (:rewrite :generalize)
)
(defthm subsetp-cons
(implies
(subsetp x y)
(subsetp x (cons z y)))
)
(defthm subsetp-refl
(subsetp x x)
)
(defthm trans-sym-then-reflexive
(implies (and (transitive lst) (symmetric lst))
(reflexive lst)
)
)
(defun equivalence (lst)
(and (transitive lst) (symmetric lst) (reflexive lst))
)
(defun get-class (a lst)
(if (endp lst) nil
(if (equal (caar lst) a)
(cons (cdar lst) (get-class a (cdr lst)))
(get-class a (cdr lst))))
)
(include-book "std/alists/top" :dir :system)
(defthm remove-assocs-length
(< (len (REMOVE-ASSOCS-EQUAL X Y)) (+ 1 (len Y)))
:hints (("Goal" :in-theory (enable REMOVE-ASSOCS-EQUAL)))
)
(defun get-classes (lst)
(declare (xargs :measure (len lst)))
(if (endp lst) nil
(let ((cl (get-class (caar lst) lst)))
(cons cl (get-classes (remove-assocs cl (cdr lst))))
))
)
(defun connect-all (a lst)
(if (endp lst) nil
(cons (cons a (car lst))
(cons (cons (car lst) a)
(connect-all a (cdr lst))))
)
)
(defun per-union (lst a b)
(append lst (connect-all b (get-class a lst)) (connect-all a (get-class b lst)))
)
(in-package "ACL2")
(include-book "Defs")
(skip-proofs
(defthm goal
(implies (and (assoc a lst)
(assoc b lst)
(equivalence lst)
(not (member-equal (cons a b) lst))
)
(equal (+ 1 length (get-classes (per-union lst a b)))
(length (get-classes lst))))
)
)
; The four lines just below are boilerplate, that is, the same for every
; problem.
(in-package "ACL2")
(include-book "Submission")
(set-enforce-redundancy t)
(include-book "Defs")
; The events below represent the theorem to be proved, and are copied from
; template.lisp.
(defthm goal
(implies (and (assoc a lst)
(assoc b lst)
(equivalence lst)
(not (member-equal (cons a b) lst))
)
(equal (+ 1 length (get-classes (per-union lst a b)))
(length (get-classes lst))))
)
-- Lean version: 3.4.2
-- Mathlib version: 2019-07-31
-- we want to have decidable relations
open classical
attribute [instance] prop_decidable
variable {α : Type*}
/--
Given a relation r (on christmas presents), `merge_presents r x y` returns
`r ∪ {(a, b) | r(a, x) ∧ r(b, y)} ∪ {(a, b) | r(b, x) ∧ r(a, y)}`
-/
def merge_presents (r : α → α → Prop) (x y : α) : α → α → Prop
| a b := r a b ∨ (r a x ∧ r b y) ∨ (r b x ∧ r a y)
/--
Given a proof that `merge_presents s.r x y` is an equivalence for a setoid `s`,
`merge_presents_setoid` returns a new setoid of merged present classes.
-/
def merge_presents_setoid {s : setoid α} {x y} (is_equiv : equivalence (merge_presents s.r x y)) :
setoid α :=
⟨merge_presents s.r x y, is_equiv⟩
import .defs
import data.fintype
variables {α : Type*} [fintype α]
local notation `|` t `|` := fintype.card t
-- show that merging two presents of a setoid return an equivalence on presents again.
lemma merge_presents_equiv (s : setoid α) (x y : α) :
equivalence (merge_presents s.r x y) :=
sorry
-- show that santa actually removes a present class by merging the two presents
lemma one_less_present_class {s : setoid α} {x y : α} (not_x_equiv_y : ¬x ≈ y) :
|quotient (merge_presents_setoid $ merge_presents_equiv s x y)| + 1 = |quotient s| :=
sorry
import data.fintype
import .defs
import .submission
variables {α : Type*} [fintype α]
local notation `|` t `|` := fintype.card t
lemma santa_is_real {s : setoid α} {x y : α} (not_x_equiv_y : ¬x ≈ y) :
|quotient (merge_presents_setoid $ merge_presents_equiv s x y)| + 1 = |quotient s| :=
one_less_present_class not_x_equiv_y
theory Defs
imports Main
begin
definition per_union where "per_union R a b ≡ R ∪
{ (x,y). (x,a)∈R ∧ (y,b)∈R } ∪ { (y,x). (x,a)∈R ∧ (y,b)∈R }"
end
theory Submission
imports Defs
begin
lemma one_less_class:
assumes "R``{x} ≠ R``{y}" and inV: "y∈V" "x∈V" and "R⊆V×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} ≠ R``{y} ⟹ y∈V ⟹ x∈V ⟹ R⊆V×V ⟹ equiv V R ⟹ finite V
⟹ Suc (card (quotient V (per_union R x y))) = card (quotient V R)"
by (rule Submission.one_less_class)
end
theory Defs
imports Main
begin
definition per_union where "per_union R a b ≡ R ∪
{ (x,y). (x,a)∈R ∧ (y,b)∈R } ∪ { (y,x). (x,a)∈R ∧ (y,b)∈R }"
end
theory Submission
imports Defs
begin
lemma one_less_class:
assumes "R``{x} ≠ R``{y}" and inV: "y∈V" "x∈V" and "R⊆V×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} ≠ R``{y} ⟹ y∈V ⟹ x∈V ⟹ R⊆V×V ⟹ equiv V R ⟹ finite V
⟹ Suc (card (quotient V (per_union R x y))) = card (quotient V R)"
by (rule Submission.one_less_class)
end