section ‹Robbins Conjecture› theory Robbins_Conjecture imports Main begin text ‹The document gives a formalization of the proof of the Robbins conjecture, following A. Mann, \emph{A Complete Proof of the Robbins Conjecture}, 2003, DOI 10.1.1.6.7838› section ‹Axiom Systems› text ‹The following presents several axiom systems that shall be under study. The first axiom sets common systems that underly all of the systems we shall be looking at. The second system is a reformulation of Boolean algebra. We shall follow pages 7--8 in S. Koppelberg. \emph{General Theory of Boolean Algebras}, Volume 1 of \emph{Handbook of Boolean Algebras}. North Holland, 1989. Note that our formulation deviates slightly from this, as we only provide one distribution axiom, as the dual is redundant. The third system is Huntington's algebra and the fourth system is Robbins' algebra. Apart from the common system, all of these systems are demonstrated to be equivalent to the library formulation of Boolean algebra, under appropriate interpretation.› subsection ‹Common Algebras› class common_algebra = uminus + fixes inf :: "'a ⇒ 'a ⇒ 'a" (infixl "⊓" 70) fixes sup :: "'a ⇒ 'a ⇒ 'a" (infixl "⊔" 65) fixes bot :: "'a" ("⊥") fixes top :: "'a" ("⊤") assumes sup_assoc: "x ⊔ (y ⊔ z) = (x ⊔ y) ⊔ z" assumes sup_comm: "x ⊔ y = y ⊔ x" context common_algebra begin definition less_eq :: "'a ⇒ 'a ⇒ bool" (infix "⊑" 50) where "x ⊑ y = (x ⊔ y = y)" definition less :: "'a ⇒ 'a ⇒ bool" (infix "⊏" 50) where "x ⊏ y = (x ⊑ y ∧ ¬ y ⊑ x)" definition minus :: "'a ⇒ 'a ⇒ 'a" (infixl "-" 65) where "minus x y = (x ⊓ - y)" (* We shall need some object in order to define falsum and verum *) definition secret_object1 :: "'a" ("ι") where "ι = (SOME x. True)" end class ext_common_algebra = common_algebra + assumes inf_eq: "x ⊓ y = -(- x ⊔ - y)" assumes top_eq: "⊤ = ι ⊔ - ι" assumes bot_eq: "⊥ = -(ι ⊔ - ι)" subsection ‹Boolean Algebra› class boolean_algebra_II = common_algebra + assumes inf_comm: "x ⊓ y = y ⊓ x" assumes inf_assoc: "x ⊓ (y ⊓ z) = (x ⊓ y) ⊓ z" assumes sup_absorb: "x ⊔ (x ⊓ y) = x" assumes inf_absorb: "x ⊓ (x ⊔ y) = x" assumes sup_inf_distrib1: "x ⊔ y ⊓ z = (x ⊔ y) ⊓ (x ⊔ z)" assumes sup_compl: "x ⊔ - x = ⊤" assumes inf_compl: "x ⊓ - x = ⊥" subsection ‹Huntington's Algebra› class huntington_algebra = ext_common_algebra + assumes huntington: "- (-x ⊔ -y) ⊔ - (-x ⊔ y) = x" subsection ‹Robbins' Algebra› class robbins_algebra = ext_common_algebra + assumes robbins: "- (- (x ⊔ y) ⊔ - (x ⊔ -y)) = x" section ‹Equivalence› text ‹With our axiom systems defined, we turn to providing equivalence results between them. We shall begin by illustrating equivalence for our formulation and the library formulation of Boolean algebra.› subsection ‹Boolean Algebra› text ‹The following provides the canonical definitions for order and relative complementation for Boolean algebras. These are necessary since the Boolean algebras presented in the Isabelle/HOL library have a lot of structure, while our formulation is considerably simpler. Since our formulation of Boolean algebras is considerably simple, it is easy to show that the library instantiates our axioms.› context boolean_algebra_II begin lemma boolean_II_is_boolean: "class.boolean_algebra minus uminus (⊓) (⊑) (⊏) (⊔) ⊥ ⊤" apply unfold_locales apply (metis inf_absorb inf_assoc inf_comm inf_compl less_def less_eq_def minus_def sup_absorb sup_assoc sup_comm sup_compl sup_inf_distrib1 sup_absorb inf_comm)+ done end context boolean_algebra begin lemma boolean_is_boolean_II: "class.boolean_algebra_II uminus inf sup bot top" apply unfold_locales apply (metis sup_assoc sup_commute sup_inf_absorb sup_compl_top inf_assoc inf_commute inf_sup_absorb inf_compl_bot sup_inf_distrib1)+ done end subsection ‹Huntington Algebra› text ‹We shall illustrate here that all Boolean algebra using our formulation are Huntington algebras, and illustrate that every Huntington algebra may be interpreted as a Boolean algebra. Since the Isabelle/HOL library has good automation, it is convenient to first show that the library instances Huntington algebras to exploit previous results, and then use our previously derived correspondence.› context boolean_algebra begin lemma boolean_is_huntington: "class.huntington_algebra uminus inf sup bot top" apply unfold_locales apply (metis double_compl inf_sup_distrib1 inf_top_right compl_inf inf_commute inf_compl_bot compl_sup sup_commute sup_compl_top sup_compl_top sup_assoc)+ done end context boolean_algebra_II begin lemma boolean_II_is_huntington: "class.huntington_algebra uminus (⊓) (⊔) ⊥ ⊤" proof - interpret boolean: boolean_algebra minus uminus "(⊓)" "(⊑)" "(⊏)" "(⊔)" ⊥ ⊤ by (fact boolean_II_is_boolean) show ?thesis by (simp add: boolean.boolean_is_huntington) qed end context huntington_algebra begin lemma huntington_id: "x ⊔ -x = -x ⊔ -(-x)" proof - from huntington have "x ⊔ -x = -(-x ⊔ -(-(-x))) ⊔ -(-x ⊔ -(-x)) ⊔ (-(-(-x) ⊔ -(-(-x))) ⊔ -(-(-x) ⊔ -(-x)))" by simp also from sup_comm have "… = -(-(-x) ⊔ -(-x)) ⊔ -(-(-x) ⊔ -(-(-x))) ⊔ (-(-(-x) ⊔ -x) ⊔ -(-(-(-x)) ⊔ -x))" by simp also from sup_assoc have "… = -(-(-x) ⊔ -(-x)) ⊔ (-(-(-x) ⊔ -(-(-x))) ⊔ -(-(-x) ⊔ -x)) ⊔ -(-(-(-x)) ⊔ -x)" by simp also from sup_comm have "… = -(-(-x) ⊔ -(-x)) ⊔ (-(-(-x) ⊔ -x) ⊔ -(-(-x) ⊔ -(-(-x)))) ⊔ -(-(-(-x)) ⊔ -x)" by simp also from sup_assoc have "… = -(-(-x) ⊔ -(-x)) ⊔ -(-(-x) ⊔ -x) ⊔ (-(-(-x) ⊔ -(-(-x))) ⊔ -(-(-(-x)) ⊔ -x))" by simp also from sup_comm have "… = -(-(-x) ⊔ -(-x)) ⊔ -(-(-x) ⊔ -x) ⊔ (-(-(-(-x)) ⊔ -(-x)) ⊔ -(-(-(-x)) ⊔ -x))" by simp also from huntington have "… = -x ⊔ -(-x)" by simp finally show ?thesis by simp qed lemma dbl_neg: "- (-x) = x" apply (metis huntington huntington_id sup_comm) done lemma towards_sup_compl: "x ⊔ -x = y ⊔ -y" proof - from huntington have "x ⊔ -x = -(-x ⊔ -(-y)) ⊔ -(-x ⊔ -y) ⊔ (-(-(-x) ⊔ -(-y)) ⊔ -(-(-x) ⊔ -y))" by simp also from sup_comm have "… = -(-(-y) ⊔ -x) ⊔ -(-y ⊔ -x) ⊔ (-(-y ⊔ -(-x)) ⊔ -(-(-y) ⊔ -(-x)))" by simp also from sup_assoc have "… = -(-(-y) ⊔ -x) ⊔ (-(-y ⊔ -x) ⊔ -(-y ⊔ -(-x))) ⊔ -(-(-y) ⊔ -(-x))" by simp also from sup_comm have "… = -(-y ⊔ -(-x)) ⊔ -(-y ⊔ -x) ⊔ -(-(-y) ⊔ -x) ⊔ -(-(-y) ⊔ -(-x))" by simp also from sup_assoc have "… = -(-y ⊔ -(-x)) ⊔ -(-y ⊔ -x) ⊔ (-(-(-y) ⊔ -x) ⊔ -(-(-y) ⊔ -(-x)))" by simp also from sup_comm have "… = -(-y ⊔ -(-x)) ⊔ -(-y ⊔ -x) ⊔ (-(-(-y) ⊔ -(-x)) ⊔ -(-(-y) ⊔ -x))" by simp also from huntington have "y ⊔ -y = …" by simp finally show ?thesis by simp qed lemma sup_compl: "x ⊔ -x = ⊤" by (simp add: top_eq towards_sup_compl) lemma towards_inf_compl: "x ⊓ -x = y ⊓ -y" by (metis dbl_neg inf_eq sup_comm sup_compl) lemma inf_compl: "x ⊓ -x = ⊥" by (metis dbl_neg sup_comm bot_eq towards_inf_compl inf_eq) lemma towards_idem: "⊥ = ⊥ ⊔ ⊥" by (metis dbl_neg huntington inf_compl inf_eq sup_assoc sup_comm sup_compl) lemma sup_ident: "x ⊔ ⊥ = x" by (metis dbl_neg huntington inf_compl inf_eq sup_assoc sup_comm sup_compl towards_idem) lemma inf_ident: "x ⊓ ⊤ = x" by (metis dbl_neg inf_compl inf_eq sup_ident sup_comm sup_compl) lemma sup_idem: "x ⊔ x = x" by (metis dbl_neg huntington inf_compl inf_eq sup_ident sup_comm sup_compl) lemma inf_idem: "x ⊓ x = x" by (metis dbl_neg inf_eq sup_idem) lemma sup_nil: "x ⊔ ⊤ = ⊤" by (metis sup_idem sup_assoc sup_comm sup_compl) lemma inf_nil: "x ⊓ ⊥ = ⊥" by (metis dbl_neg inf_compl inf_eq sup_nil sup_comm sup_compl) lemma sup_absorb: "x ⊔ x ⊓ y = x" by (metis huntington inf_eq sup_idem sup_assoc sup_comm) lemma inf_absorb: "x ⊓ (x ⊔ y) = x" by (metis dbl_neg inf_eq sup_absorb) lemma partition: "x ⊓ y ⊔ x ⊓ -y = x" by (metis dbl_neg huntington inf_eq sup_comm) lemma demorgans1: "-(x ⊓ y) = -x ⊔ -y" by (metis dbl_neg inf_eq) lemma demorgans2: "-(x ⊔ y) = -x ⊓ -y" by (metis dbl_neg inf_eq) lemma inf_comm: "x ⊓ y = y ⊓ x" by (metis inf_eq sup_comm) lemma inf_assoc: "x ⊓ (y ⊓ z) = x ⊓ y ⊓ z" by (metis dbl_neg inf_eq sup_assoc) lemma inf_sup_distrib1: "x ⊓ (y ⊔ z) = (x ⊓ y) ⊔ (x ⊓ z)" proof - from partition have "x ⊓ (y ⊔ z) = x ⊓ (y ⊔ z) ⊓ y ⊔ x ⊓ (y ⊔ z) ⊓ -y" .. also from inf_assoc have "… = x ⊓ ((y ⊔ z) ⊓ y) ⊔ x ⊓ (y ⊔ z) ⊓ -y" by simp also from inf_comm have "… = x ⊓ (y ⊓ (y ⊔ z)) ⊔ x ⊓ (y ⊔ z) ⊓ -y" by simp also from inf_absorb have "… = (x ⊓ y) ⊔ (x ⊓ (y ⊔ z) ⊓ -y)" by simp also from partition have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ ((x ⊓ (y ⊔ z) ⊓ -y ⊓ z) ⊔ (x ⊓ (y ⊔ z) ⊓ -y ⊓ -z))" by simp also from inf_assoc have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ ((x ⊓ ((y ⊔ z) ⊓ (-y ⊓ z))) ⊔ (x ⊓ ((y ⊔ z) ⊓ (-y ⊓ -z))))" by simp also from demorgans2 have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ ((x ⊓ ((y ⊔ z) ⊓ (-y ⊓ z))) ⊔ (x ⊓ ((y ⊔ z) ⊓ -(y ⊔ z))))" by simp also from inf_compl have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ ((x ⊓ ((y ⊔ z) ⊓ (-y ⊓ z))) ⊔ (x ⊓ ⊥))" by simp also from inf_nil have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ ((x ⊓ ((y ⊔ z) ⊓ (-y ⊓ z))) ⊔ ⊥)" by simp also from sup_idem have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ ((x ⊓ ((y ⊔ z) ⊓ (-y ⊓ z))) ⊔ ⊥)" by simp also from sup_ident have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ (x ⊓ ((y ⊔ z) ⊓ (-y ⊓ z)))" by simp also from inf_comm have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ (x ⊓ ((-y ⊓ z) ⊓ (y ⊔ z)))" by simp also from sup_comm have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ (x ⊓ ((-y ⊓ z) ⊓ (z ⊔ y)))" by simp also from inf_assoc have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ (y ⊓ z)) ⊔ (x ⊓ y ⊓ -z)) ⊔ (x ⊓ (-y ⊓ (z ⊓ (z ⊔ y))))" by simp also from inf_absorb have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ (y ⊓ z)) ⊔ (x ⊓ y ⊓ -z)) ⊔ (x ⊓ (-y ⊓ z))" by simp also from inf_comm have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ (z ⊓ y)) ⊔ (x ⊓ y ⊓ -z)) ⊔ (x ⊓ (z ⊓ -y))" by simp also from sup_assoc have "… = ((x ⊓ y ⊓ z) ⊔ ((x ⊓ (z ⊓ y)) ⊔ (x ⊓ y ⊓ -z))) ⊔ (x ⊓ (z ⊓ -y))" by simp also from sup_comm have "… = ((x ⊓ y ⊓ z) ⊔ ((x ⊓ y ⊓ -z) ⊔ (x ⊓ (z ⊓ y)))) ⊔ (x ⊓ (z ⊓ -y))" by simp also from sup_assoc have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ ((x ⊓ (z ⊓ y)) ⊔ (x ⊓ (z ⊓ -y)))" by simp also from inf_assoc have "… = ((x ⊓ y ⊓ z) ⊔ (x ⊓ y ⊓ -z)) ⊔ ((x ⊓ z ⊓ y) ⊔ (x ⊓ z ⊓ -y))" by simp also from partition have "… = (x ⊓ y) ⊔ (x ⊓ z)" by simp finally show ?thesis by simp qed lemma sup_inf_distrib1: "x ⊔ (y ⊓ z) = (x ⊔ y) ⊓ (x ⊔ z)" proof - from dbl_neg have "x ⊔ (y ⊓ z) = -(-(-(-x) ⊔ (y ⊓ z)))" by simp also from inf_eq have "… = -(-x ⊓ (-y ⊔ -z))" by simp also from inf_sup_distrib1 have "… = -((-x ⊓ -y) ⊔ (-x ⊓ -z))" by simp also from demorgans2 have "… = -(-x ⊓ -y) ⊓ -(-x ⊓ -z)" by simp also from demorgans1 have "… = (-(-x) ⊔ -(-y)) ⊓ (-(-x) ⊔ -(-z))" by simp also from dbl_neg have "… = (x ⊔ y) ⊓ (x ⊔ z)" by simp finally show ?thesis by simp qed lemma huntington_is_boolean_II: "class.boolean_algebra_II uminus (⊓) (⊔) ⊥ ⊤" apply unfold_locales apply (metis inf_comm inf_assoc sup_absorb inf_absorb sup_inf_distrib1 sup_compl inf_compl)+ done lemma huntington_is_boolean: "class.boolean_algebra minus uminus (⊓) (⊑) (⊏) (⊔) ⊥ ⊤" proof - interpret boolean_II: boolean_algebra_II uminus "(⊓)" "(⊔)" ⊥ ⊤ by (fact huntington_is_boolean_II) show ?thesis by (simp add: boolean_II.boolean_II_is_boolean) qed end subsection ‹Robbins' Algebra› context boolean_algebra begin lemma boolean_is_robbins: "class.robbins_algebra uminus inf sup bot top" apply unfold_locales apply (metis sup_assoc sup_commute compl_inf double_compl sup_compl_top inf_compl_bot diff_eq sup_bot_right sup_inf_distrib1)+ done end context boolean_algebra_II begin lemma boolean_II_is_robbins: "class.robbins_algebra uminus inf sup bot top" proof - interpret boolean: boolean_algebra minus uminus "(⊓)" "(⊑)" "(⊏)" "(⊔)" ⊥ ⊤ by (fact boolean_II_is_boolean) show ?thesis by (simp add: boolean.boolean_is_robbins) qed end context huntington_algebra begin lemma huntington_is_robbins: "class.robbins_algebra uminus inf sup bot top" proof - interpret boolean: boolean_algebra minus uminus "(⊓)" "(⊑)" "(⊏)" "(⊔)" ⊥ ⊤ by (fact huntington_is_boolean) show ?thesis by (simp add: boolean.boolean_is_robbins) qed end text ‹Before diving into the proof that the Robbins algebra is Boolean, we shall present some shorthand machinery› context common_algebra begin (* Iteration Machinery/Shorthand *) primrec copyp :: "nat ⇒ 'a ⇒ 'a" (infix "⊗" 80) where copyp_0: "0 ⊗ x = x" | copyp_Suc: "(Suc k) ⊗ x = (k ⊗ x) ⊔ x" no_notation Product_Type.Times (infixr "×" 80) primrec copy :: "nat ⇒ 'a ⇒ 'a" (infix "×" 85) where "0 × x = x" | "(Suc k) × x = k ⊗ x" (* Theorems for translating shorthand into syntax *) lemma one: "1 × x = x" proof - have "1 = Suc(0)" by arith hence "1 × x = Suc(0) × x" by metis also have "… = x" by simp finally show ?thesis by simp qed lemma two: "2 × x = x ⊔ x" proof - have "2 = Suc(Suc(0))" by arith hence "2 × x = Suc(Suc(0)) × x" by metis also have "… = x ⊔ x" by simp finally show ?thesis by simp qed lemma three: "3 × x = x ⊔ x ⊔ x" proof - have "3 = Suc(Suc(Suc(0)))" by arith hence "3 × x = Suc(Suc(Suc(0))) × x" by metis also have "… = x ⊔ x ⊔ x" by simp finally show ?thesis by simp qed lemma four: "4 × x = x ⊔ x ⊔ x ⊔ x" proof - have "4 = Suc(Suc(Suc(Suc(0))))" by arith hence "4 × x = Suc(Suc(Suc(Suc(0)))) × x" by metis also have "… = x ⊔ x ⊔ x ⊔ x" by simp finally show ?thesis by simp qed lemma five: "5 × x = x ⊔ x ⊔ x ⊔ x ⊔ x" proof - have "5 = Suc(Suc(Suc(Suc(Suc(0)))))" by arith hence "5 × x = Suc(Suc(Suc(Suc(Suc(0))))) × x" by metis also have "… = x ⊔ x ⊔ x ⊔ x ⊔ x" by simp finally show ?thesis by simp qed lemma six: "6 × x = x ⊔ x ⊔ x ⊔ x ⊔ x ⊔ x" proof - have "6 = Suc(Suc(Suc(Suc(Suc(Suc(0))))))" by arith hence "6 × x = Suc(Suc(Suc(Suc(Suc(Suc(0)))))) × x" by metis also have "… = x ⊔ x ⊔ x ⊔ x ⊔ x ⊔ x" by simp finally show ?thesis by simp qed (* Distribution Laws *) lemma copyp_distrib: "k ⊗ (x ⊔ y) = (k ⊗ x) ⊔ (k ⊗ y)" proof (induct k) case 0 show ?case by simp case Suc thus ?case by (simp, metis sup_assoc sup_comm) qed corollary copy_distrib: "k × (x ⊔ y) = (k × x) ⊔ (k × y)" by (induct k, (simp add: sup_assoc sup_comm copyp_distrib)+) lemma copyp_arith: "(k + l + 1) ⊗ x = (k ⊗ x) ⊔ (l ⊗ x)" proof (induct l) case 0 have "k + 0 + 1 = Suc(k)" by arith thus ?case by simp case (Suc l) note ind_hyp = this have "k + Suc(l) + 1 = Suc(k + l + 1)" by arith+ hence "(k + Suc(l) + 1) ⊗ x = (k + l + 1) ⊗ x ⊔ x" by (simp add: ind_hyp) also from ind_hyp have "… = (k ⊗ x) ⊔ (l ⊗ x) ⊔ x" by simp also note sup_assoc finally show ?case by simp qed lemma copy_arith: assumes "k ≠ 0" and "l ≠ 0" shows "(k + l) × x = (k × x) ⊔ (l × x)" using assms proof - from assms have "∃ k'. Suc(k') = k" and "∃ l'. Suc(l') = l" by arith+ from this obtain k' l' where A: "Suc(k') = k" and B: "Suc(l') = l" by fast+ from this have A1: "k × x = k' ⊗ x" and B1: "l × x = l' ⊗ x" by fastforce+ from A B have "k + l = Suc(k' + l' + 1)" by arith hence "(k + l) × x = (k' + l' + 1) ⊗ x" by simp also from copyp_arith have "… = k' ⊗ x ⊔ l' ⊗ x" by fast also from A1 B1 have "… = k × x ⊔ l × x" by fastforce finally show ?thesis by simp qed end text ‹The theorem asserting all Robbins algebras are Boolean comes in 6 movements. First: The Winker identity is proved. Second: Idempotence for a particular object is proved. Note that falsum is defined in terms of this object. Third: An identity law for falsum is derived. Fourth: Idempotence for supremum is derived. Fifth: The double negation law is proven Sixth: Robbin's algebras are proven to be Huntington Algebras.› context robbins_algebra begin definition secret_object2 :: "'a" ("α") where "α = -(-(ι ⊔ ι ⊔ ι) ⊔ ι)" definition secret_object3 :: "'a" ("β") where "β = ι ⊔ ι" definition secret_object4 :: "'a" ("δ") where "δ = β ⊔ (-(α ⊔ -β) ⊔ -(α ⊔ -β))" definition secret_object5 :: "'a" ("γ") where "γ = δ ⊔ -(δ ⊔ -δ)" definition winker_object :: "'a" ("ρ") where "ρ = γ ⊔ γ ⊔ γ" definition fake_bot :: "'a" ("⊥⊥") where "⊥⊥ = -(ρ ⊔ -ρ)" (* Towards Winker's Identity *) (* These lemmas are due to Alan Mann *) lemma robbins2: "y = -(-(-x ⊔ y) ⊔ -(x ⊔ y))" by (metis robbins sup_comm) lemma mann0: "-(x ⊔ y) = -(-(-(x ⊔ y) ⊔ -x ⊔ y) ⊔ y)" by (metis robbins sup_comm sup_assoc) lemma mann1: "-(-x ⊔ y) = -(-(-(-x ⊔ y) ⊔ x ⊔ y) ⊔ y)" by (metis robbins sup_comm sup_assoc) lemma mann2: "y = -(-(-(-x ⊔ y) ⊔ x ⊔ y ⊔ y) ⊔ -(-x ⊔ y))" by (metis mann1 robbins sup_comm sup_assoc) lemma mann3: "z = -(-(-(-(-x ⊔ y) ⊔ x ⊔ y ⊔ y) ⊔ -(-x ⊔ y) ⊔ z) ⊔ -(y ⊔ z))" proof - let ?w = "-(-(-x ⊔ y) ⊔ x ⊔ y ⊔ y) ⊔ -(-x ⊔ y)" from robbins[where x="z" and y="?w"] sup_comm mann2 have "z = -(-(y ⊔ z) ⊔ -(?w ⊔ z))" by metis thus ?thesis by (metis sup_comm) qed lemma mann4: "-(y ⊔ z) = -(-(-(-(-x ⊔ y) ⊔ x ⊔ y ⊔ y) ⊔ -(-x ⊔ y) ⊔ -(y ⊔ z) ⊔ z) ⊔ z)" proof - from robbins2[where x="-(-(-x ⊔ y) ⊔ x ⊔ y ⊔ y) ⊔ -(-x ⊔ y) ⊔ z" and y="-(y ⊔ z)"] mann3[where x="x" and y="y" and z="z"] have "-(y ⊔ z) = -(z ⊔ -(-(-(-x ⊔ y) ⊔ x ⊔ y ⊔ y) ⊔ -(-x ⊔ y) ⊔ z ⊔ -(y ⊔ z)))" by metis with sup_comm sup_assoc show ?thesis by metis qed lemma mann5: "u = -(-(-(-(-(-x ⊔ y) ⊔ x ⊔ y ⊔ y) ⊔ -(-x ⊔ y) ⊔ - (y ⊔ z) ⊔ z) ⊔ z ⊔ u) ⊔ -(-(y ⊔ z) ⊔ u))" using robbins2[where x="-(-(-(-x ⊔ y) ⊔ x ⊔ y ⊔ y) ⊔ -(-x ⊔ y) ⊔ -(y ⊔ z) ⊔ z) ⊔ z" and y="u"] mann4[where x=x and y=y and z=z] sup_comm by metis lemma mann6: "-(- 3×x ⊔ x) = -(-(-(- 3×x ⊔ x) ⊔ - 3×x) ⊔ -(-(- 3×x ⊔ x) ⊔ 5×x))" proof - have "3+2=(5::nat)" and "3≠(0::nat)" and "2≠(0::nat)" by arith+ with copy_arith have ♡: "3×x ⊔ 2×x = 5×x" by metis let ?p = "-(- 3×x ⊔ x)" { fix q from sup_comm have "-(q ⊔ 5×x) = -(5×x ⊔ q)" by metis also from ♡ mann0[where x="3×x" and y="q ⊔ 2×x"] sup_assoc sup_comm have "… = -(-(-(3×x ⊔ (q ⊔ 2×x)) ⊔ - 3×x ⊔ (q ⊔ 2×x)) ⊔ (q ⊔ 2×x))" by metis also from sup_assoc have "… = -(-(-((3×x ⊔ q) ⊔ 2×x) ⊔ - 3×x ⊔ (q ⊔ 2×x)) ⊔ (q ⊔ 2×x))" by metis also from sup_comm have "… = -(-(-((q ⊔ 3×x) ⊔ 2×x) ⊔ - 3×x ⊔ (q ⊔ 2×x)) ⊔ (q ⊔ 2×x))" by metis also from sup_assoc have "… = -(-(-(q ⊔ (3×x ⊔ 2×x)) ⊔ - 3×x ⊔ (q ⊔ 2×x)) ⊔ (q ⊔ 2×x))" by metis also from ♡ have "… = -(-(-(q ⊔ 5×x) ⊔ - 3×x ⊔ (q ⊔ 2×x)) ⊔ (q ⊔ 2×x))" by metis also from sup_assoc have "… = -(-(-(q ⊔ 5×x) ⊔ (- 3×x ⊔ q) ⊔ 2×x) ⊔ (q ⊔ 2×x))" by metis also from sup_comm have "… = -(-(-(q ⊔ 5×x) ⊔ (q ⊔ - 3×x) ⊔ 2×x) ⊔ (2×x ⊔ q))" by metis also from sup_assoc have "… = -(-(-(q ⊔ 5×x) ⊔ q ⊔ - 3×x ⊔ 2×x) ⊔ 2×x ⊔ q)" by metis finally have "-(q ⊔ 5×x) = -(-(-(q ⊔ 5×x) ⊔ q ⊔ - 3×x ⊔ 2×x) ⊔ 2×x ⊔ q)" by simp } hence ♠: "-(?p ⊔ 5×x) = -(-(-(?p ⊔ 5×x) ⊔ ?p ⊔ - 3×x ⊔ 2×x) ⊔ 2×x ⊔ ?p)" by simp from mann5[where x="3×x" and y="x" and z="2×x" and u="?p"] sup_assoc three[where x=x] five[where x=x] have "?p = -(-(-(-(?p ⊔ 5×x) ⊔ ?p ⊔ -(x ⊔ 2×x) ⊔ 2×x) ⊔ 2×x ⊔ ?p) ⊔ -(-(x ⊔ 2×x) ⊔ ?p))" by metis also from sup_comm have "… = -(-(-(-(?p ⊔ 5×x) ⊔ ?p ⊔ -(2×x ⊔ x) ⊔ 2×x) ⊔ 2×x ⊔ ?p) ⊔ -(-(2×x ⊔ x) ⊔ ?p))" by metis also from two[where x=x] three[where x=x] have "… = -(-(-(-(?p ⊔ 5×x) ⊔ ?p ⊔ - 3×x ⊔ 2×x) ⊔ 2×x ⊔ ?p) ⊔ -(- 3×x ⊔ ?p))" by metis also from ♠ have "… = -(-(?p ⊔ 5×x) ⊔ -(- 3×x ⊔ ?p))" by simp also from sup_comm have "… = -(-(?p ⊔ 5×x) ⊔ -(?p ⊔ - 3×x))" by simp also from sup_comm have "… = -(-(?p ⊔ - 3×x) ⊔ -(?p ⊔ 5×x))" by simp finally show ?thesis . qed lemma mann7: "- 3×x = -(-(- 3×x ⊔ x) ⊔ 5×x)" proof - let ?p = "-(- 3×x ⊔ x)" let ?q = "?p ⊔ - 3×x" let ?r = "-(?p ⊔ 5×x)" from robbins2[where x="?q" and y="?r"] mann6[where x=x] have "?r = - (?p ⊔ - (?q ⊔ ?r))" by simp also from sup_comm have "… = - (- (?q ⊔ ?r) ⊔ ?p)" by simp also from sup_comm have "… = - (- (?r ⊔ ?q) ⊔ ?p)" by simp finally have ♠: "?r = - (- (?r ⊔ ?q) ⊔ ?p)" . from mann3[where x="3×x" and y="x" and z="- 3×x"] sup_comm have "- 3×x = -(-(-(?p ⊔ 3×x ⊔ x ⊔ x) ⊔ ?p ⊔ - 3×x) ⊔ ?p)" by metis also from sup_assoc have "… = -(-(-(?p ⊔ (3×x ⊔ x ⊔ x)) ⊔ ?q) ⊔ ?p)" by metis also from three[where x=x] five[where x=x] have "… = -(-(?r ⊔ ?q) ⊔ ?p)" by metis finally have "- 3×x = -(-(?r ⊔ ?q) ⊔ ?p)" by metis with ♠ show ?thesis by simp qed lemma mann8: "-(- 3×x ⊔ x) ⊔ 2×x = -(-(-(- 3×x ⊔ x) ⊔ - 3×x ⊔ 2×x) ⊔ - 3×x)" (is "?lhs = ?rhs") proof - let ?p = "-(- 3×x ⊔ x)" let ?q = "?p ⊔ 2×x" let ?r = "3×x" have "3+2=(5::nat)" and "3≠(0::nat)" and "2≠(0::nat)" by arith+ with copy_arith have ♡: "3×x ⊔ 2×x = 5×x" by metis from robbins2[where x="?r" and y="?q"] and sup_assoc have "?q = -(-(- 3×x ⊔ ?q) ⊔ -(3×x ⊔ ?p ⊔ 2×x))" by metis also from sup_comm have "… = -(-(?q ⊔ - 3×x) ⊔ -(?p ⊔ 3×x ⊔ 2×x))" by metis also from ♡ sup_assoc have "… = -(-(?q ⊔ - 3×x) ⊔ -(?p ⊔ 5×x))" by metis also from mann7[where x=x] have "… = -(-(?q ⊔ - 3×x) ⊔ - 3×x)" by metis also from sup_assoc have "… = -(-(?p ⊔ (2×x ⊔ - 3×x)) ⊔ - 3×x)" by metis also from sup_comm have "… = -(-(?p ⊔ (- 3×x ⊔ 2×x)) ⊔ - 3×x)" by metis also from sup_assoc have "… = ?rhs" by metis finally show ?thesis by simp qed lemma mann9: "x = -(-(- 3×x ⊔ x) ⊔ - 3×x )" proof - let ?p = "-(- 3×x ⊔ x)" let ?q = "?p ⊔ 4×x" have "4+1=(5::nat)" and "1≠(0::nat)" and "4≠(0::nat)" by arith+ with copy_arith one have ♡: "4×x ⊔ x = 5×x" by metis with sup_assoc robbins2[where y=x and x="?q"] have "x = -(-(-?q ⊔ x) ⊔ -(?p ⊔ 5×x))" by metis with mann7 have "x = -(-(-?q ⊔ x) ⊔ - 3×x)" by metis moreover have "3+1=(4::nat)" and "1≠(0::nat)" and "3≠(0::nat)" by arith+ with copy_arith one have ♠: "3×x ⊔ x = 4×x" by metis with mann1[where x="3×x" and y="x"] sup_assoc have "-(-?q ⊔ x) = ?p" by metis ultimately show ?thesis by simp qed lemma mann10: "y = -(-(-(- 3×x ⊔ x) ⊔ - 3×x ⊔ y) ⊔ -(x ⊔ y))" using robbins2[where x="-(- 3×x ⊔ x) ⊔ - 3×x" and y=y] mann9[where x=x] sup_comm by metis theorem mann: "2×x = -(- 3×x ⊔ x) ⊔ 2×x" using mann10[where x=x and y="2×x"] mann8[where x=x] two[where x=x] three[where x=x] sup_comm by metis corollary winkerr: "α ⊔ β = β" using mann secret_object2_def secret_object3_def two three by metis corollary winker: "β ⊔ α = β" by (metis winkerr sup_comm) corollary multi_winkerp: "β ⊔ k ⊗ α = β" by (induct k, (simp add: winker sup_comm sup_assoc)+) corollary multi_winker: "β ⊔ k × α = β" by (induct k, (simp add: multi_winkerp winker sup_comm sup_assoc)+) (* Towards Idempotence *) lemma less_eq_introp: "-(x ⊔ -(y ⊔ z)) = -(x ⊔ y ⊔ -z) ⟹ y ⊑ x" by (metis robbins sup_assoc less_eq_def sup_comm[where x=x and y=y]) corollary less_eq_intro: "-(x ⊔ -(y ⊔ z)) = -(x ⊔ y ⊔ -z) ⟹ x ⊔ y = x" by (metis less_eq_introp less_eq_def sup_comm) lemma eq_intro: "-(x ⊔ -(y ⊔ z)) = -(y ⊔ -(x ⊔ z)) ⟹ x = y" by (metis robbins sup_assoc sup_comm) lemma copyp0: assumes "-(x ⊔ -y) = z" shows "-(x ⊔ -(y ⊔ k ⊗ (x ⊔ z))) = z" using assms proof (induct k) case 0 show ?case by (simp, metis assms robbins sup_assoc sup_comm) case Suc note ind_hyp = this show ?case by (simp, metis ind_hyp robbins sup_assoc sup_comm) qed lemma copyp1: assumes "-(-(x ⊔ -y) ⊔ -y) = x" shows "-(y ⊔ k ⊗ (x ⊔ -(x ⊔ -y))) = -y" using assms proof - let ?z = "-(x ⊔ - y)" let ?ky = "y ⊔ k ⊗ (x ⊔ ?z)" have "-(x ⊔ -?ky) = ?z" by (simp add: copyp0) hence "-(-?ky ⊔ -(-y ⊔ ?z)) = ?z" by (metis assms sup_comm) also have "-(?z ⊔ -?ky) = x" by (metis assms copyp0 sup_comm) hence "?z = -(-y ⊔ -(-?ky ⊔ ?z))" by (metis sup_comm) finally show ?thesis by (metis eq_intro) qed corollary copyp2: assumes "-(x ⊔ y) = -y" shows "-(y ⊔ k ⊗ (x ⊔ -(x ⊔ -y))) = -y" by (metis assms robbins sup_comm copyp1) lemma two_threep: assumes "-(2 × x ⊔ y) = -y" and "-(3 × x ⊔ y) = -y" shows "2 × x ⊔ y = 3 × x ⊔ y" using assms proof - from assms two three have A: "-(x ⊔ x ⊔ y) = -y" and B: "-(x ⊔ x ⊔ x ⊔ y) = -y" by simp+ with sup_assoc copyp2[where x="x" and y="x ⊔ x ⊔ y" and k="0"] have "-(x ⊔ x ⊔ y ⊔ x ⊔ -(x ⊔ -y)) = -y" by simp moreover from sup_comm sup_assoc A B copyp2[where x="x ⊔ x" and y="y" and k="0"] have "-(y ⊔ x ⊔ x ⊔ -(x ⊔ x ⊔ -y)) = -y" by fastforce with sup_comm sup_assoc have "-(x ⊔ x ⊔ y ⊔ -(x ⊔ (x ⊔ -y))) = -y" by metis ultimately have "-(x ⊔ x ⊔ y ⊔ -(x ⊔ (x ⊔ -y))) = -(x ⊔ x ⊔ y ⊔ x ⊔ -(x ⊔ -y))" by simp with less_eq_intro have "x ⊔ x ⊔ y = x ⊔ x ⊔ y ⊔ x" by metis with sup_comm sup_assoc two three show ?thesis by metis qed lemma two_three: assumes "-(x ⊔ y) = -y ∨ -(-(x ⊔ -y) ⊔ -y) = x" shows "y ⊔ 2 × (x ⊔ -(x ⊔ -y)) = y ⊔ 3 × (x ⊔ -(x ⊔ -y))" (is "y ⊔ ?z2 = y ⊔ ?z3") using assms proof assume "-(x ⊔ y) = -y" with copyp2[where k="Suc(0)"] copyp2[where k="Suc(Suc(0))"] two three have "-(y ⊔ ?z2) = -y" and "-(y ⊔ ?z3) = -y" by simp+ with two_threep sup_comm show ?thesis by metis next assume "-(-(x ⊔ -y) ⊔ -y) = x" with copyp1[where k="Suc(0)"] copyp1[where k="Suc(Suc(0))"] two three have "-(y ⊔ ?z2) = -y" and "-(y ⊔ ?z3) = -y" by simp+ with two_threep sup_comm show ?thesis by metis qed lemma sup_idem: "ρ ⊔ ρ = ρ" proof - from winkerr two copyp2[where x="α" and y="β" and k="Suc(0)"] have "-β = -(β ⊔ 2 × (α ⊔ -(α ⊔ -β)))" by simp also from copy_distrib sup_assoc have "… = -(β ⊔ 2 × α ⊔ 2 × (-(α ⊔ -β)))" by simp also from sup_assoc secret_object4_def two multi_winker[where k="2"] have "… = -δ" by metis finally have "-β = -δ" by simp with secret_object4_def sup_assoc three have "δ ⊔ -(α ⊔ -δ) = β ⊔ 3 × (-(α ⊔ -β))" by simp also from copy_distrib[where k="3"] multi_winker[where k="3"] sup_assoc have "… = β ⊔ 3 × (α ⊔ -(α ⊔ -β))" by metis also from winker sup_comm two_three[where x="α" and y="β"] have "… = β ⊔ 2 × (α ⊔ -(α ⊔ -β))" by fastforce also from copy_distrib[where k="2"] multi_winker[where k="2"] sup_assoc two secret_object4_def have "… = δ" by metis finally have ♡: "δ ⊔ -(α ⊔ -δ) = δ" by simp from secret_object4_def winkerr sup_assoc have "α ⊔ δ = δ" by metis hence "δ ⊔ α = δ" by (metis sup_comm) hence "-(-(δ ⊔ -δ) ⊔ -δ) = -(-(δ ⊔ (α ⊔ -δ)) ⊔ -δ)" by (metis sup_assoc) also from ♡ have "… = -(-(δ ⊔ (α ⊔ -δ)) ⊔ -(δ ⊔ -(α ⊔ -δ)))" by metis also from robbins have "… = δ" by metis finally have "-(-(δ ⊔ -δ) ⊔ -δ) = δ" by simp with two_three[where x="δ" and y="δ"] secret_object5_def sup_comm have "3 × γ ⊔ δ = 2 × γ ⊔ δ" by fastforce with secret_object5_def sup_assoc sup_comm have "3 × γ ⊔ γ = 2 × γ ⊔ γ" by fastforce with two three four five six have "6 × γ = 3 × γ" by simp moreover have "3 + 3 = (6::nat)" and "3 ≠ (0::nat)" by arith+ moreover note copy_arith[where k="3" and l="3" and x="γ"] winker_object_def three ultimately show ?thesis by simp qed (* Idempotence implies the identity law *) lemma sup_ident: "x ⊔ ⊥⊥ = x" proof - have I: "ρ = -(-ρ ⊔ ⊥⊥)" by (metis fake_bot_def inf_eq robbins sup_comm sup_idem) { fix x have "x = -(-(x ⊔ -ρ ⊔ ⊥⊥) ⊔ -(x ⊔ ρ))" by (metis I robbins sup_assoc) } note II = this have III: "-ρ = -(-(ρ ⊔ -ρ ⊔ -ρ) ⊔ ρ)" by (metis robbins[where x="-ρ" and y="ρ ⊔ -ρ"] I sup_comm fake_bot_def) hence "ρ = -(-(ρ ⊔ -ρ ⊔ -ρ) ⊔ -ρ)" by (metis robbins[where x="ρ" and y="ρ ⊔ -ρ ⊔ -ρ"] sup_comm[where x="ρ" and y="-(ρ ⊔ -ρ ⊔ -ρ)"] sup_assoc sup_idem) hence "-(ρ ⊔ -ρ ⊔ -ρ) = ⊥⊥" by (metis robbins[where x="-(ρ ⊔ -ρ ⊔ -ρ)" and y="ρ"] III sup_comm fake_bot_def) hence "-ρ = -(ρ ⊔ ⊥⊥)" by (metis III sup_comm) hence "ρ = -(-(ρ ⊔ ⊥⊥) ⊔ -(ρ ⊔ ⊥⊥ ⊔ -ρ))" by (metis II sup_idem sup_comm sup_assoc) moreover have "ρ ⊔ ⊥⊥ = -(-(ρ ⊔ ⊥⊥) ⊔ -(ρ ⊔ ⊥⊥ ⊔ -ρ))" by (metis robbins[where x="ρ ⊔ ⊥⊥" and y="ρ"] sup_comm[where y="ρ"] sup_assoc sup_idem) ultimately have "ρ = ρ ⊔ ⊥⊥" by auto hence "x ⊔ ⊥⊥ = -(-(x ⊔ ρ) ⊔ -(x ⊔ ⊥⊥ ⊔ -ρ))" by (metis robbins[where x="x ⊔ ⊥⊥" and y=ρ] sup_comm[where x="⊥⊥" and y=ρ] sup_assoc) thus ?thesis by (metis sup_assoc sup_comm II) qed (* The identity law implies double negation *) lemma dbl_neg: "- (-x) = x" proof - { fix x have "⊥⊥ = -(-x ⊔ -(-x))" by (metis robbins sup_comm sup_ident) } note I = this { fix x have "-x = -(-(-x ⊔ -(-(-x))))" by (metis I robbins sup_comm sup_ident) } note II = this { fix x have "-(-(-x)) = -(-(-x ⊔ -(-(-x))))" by (metis I II robbins sup_assoc sup_comm sup_ident) } note III = this show ?thesis by (metis II III robbins) qed (* Double negation implies Huntington's axiom, hence Boolean*) theorem robbins_is_huntington: "class.huntington_algebra uminus (⊓) (⊔) ⊥ ⊤" apply unfold_locales apply (metis dbl_neg robbins sup_comm) done theorem robbins_is_boolean_II: "class.boolean_algebra_II uminus (⊓) (⊔) ⊥ ⊤" proof - interpret huntington: huntington_algebra uminus "(⊓)" "(⊔)" ⊥ ⊤ by (fact robbins_is_huntington) show ?thesis by (simp add: huntington.huntington_is_boolean_II) qed theorem robbins_is_boolean: "class.boolean_algebra minus uminus (⊓) (⊑) (⊏) (⊔) ⊥ ⊤" proof - interpret huntington: huntington_algebra uminus "(⊓)" "(⊔)" ⊥ ⊤ by (fact robbins_is_huntington) show ?thesis by (simp add: huntington.huntington_is_boolean) qed end no_notation secret_object1 ("ι") and secret_object2 ("α") and secret_object3 ("β") and secret_object4 ("δ") and secret_object5 ("γ") and winker_object ("ρ") and less_eq (infix "⊑" 50) and less (infix "⊏" 50) and inf (infixl "⊓" 70) and sup (infixl "⊔" 65) and top ("⊤") and bot ("⊥") and copyp (infix "⊗" 80) and copy (infix "×" 85) notation Product_Type.Times (infixr "×" 80) end