diff --git a/thys/AxiomaticCategoryTheory/AxiomaticCategoryTheory.thy b/thys/AxiomaticCategoryTheory/AxiomaticCategoryTheory.thy --- a/thys/AxiomaticCategoryTheory/AxiomaticCategoryTheory.thy +++ b/thys/AxiomaticCategoryTheory/AxiomaticCategoryTheory.thy @@ -1,679 +1,679 @@ (*<*) theory AxiomaticCategoryTheory imports Main abbrevs f_neg="\<^bold>\" and f_or="\<^bold>\" and f_and="\<^bold>\" and f_impl="\<^bold>\" and f_imp="\<^bold>\" and mequ="\<^bold>\" and f_all="\<^bold>\" and f_exi="\<^bold>\" and f_all2="(\<^bold>\x.)" and f_exi2="(\<^bold>\x.)" and f_kleeneeq="\" and f_primeq="\" and f_comp2="(\)" and f_comp="\" begin (*Begin: some useful parameter settings*) nitpick_params[user_axioms, show_all, format = 2, expect = genuine] (*End: some useful parameter settings*) (*>*) section\Introduction\ text\This document provides a concise overview on the core results of our previous - work @{cite "C67" and "R58" and "C57"} on the exploration of axiom systems for category theory. + work \<^cite>\"C67" and "R58" and "C57"\ on the exploration of axiom systems for category theory. Extending the previous studies we include one further axiomatic theory in our experiments. This additional - theory has been suggested by Mac Lane~@{cite "MacLane48"} in + theory has been suggested by Mac Lane~\<^cite>\"MacLane48"\ in 1948. We show that the axioms proposed by Mac Lane are equivalent to the ones studied - in~@{cite "R58"}, which includes an axioms set suggested by Scott~@{cite "Scott79"} - in the 1970s and another axioms set proposed by Freyd and Scedrov~@{cite "FreydScedrov90"} in 1990, - which we slightly modified in~@{cite "R58"} to remedy a minor technical issue. + in~\<^cite>\"R58"\, which includes an axioms set suggested by Scott~\<^cite>\"Scott79"\ + in the 1970s and another axioms set proposed by Freyd and Scedrov~\<^cite>\"FreydScedrov90"\ in 1990, + which we slightly modified in~\<^cite>\"R58"\ to remedy a minor technical issue. The explanations given below are minimal, for more details we refer to the referenced - papers, in particular, to~@{cite "R58"}.\ + papers, in particular, to~\<^cite>\"R58"\.\ section\Embedding of Free Logic in HOL\ -text\We introduce a shallow semantical embedding of free logic @{cite "R58"} in Isabelle/HOL. +text\We introduce a shallow semantical embedding of free logic \<^cite>\"R58"\ in Isabelle/HOL. Definite description is omitted, since it is not needed in the studies below and also - since the definition provided in @{cite "C57"} introduces the here undesired commitment + since the definition provided in \<^cite>\"C57"\ introduces the here undesired commitment that at least one non-existing element of type $i$ is a priori given. We here want to consider this an optional condition.\ typedecl i \ \Type for individuals\ consts fExistence:: "i\bool" ("E") \ \Existence/definedness predicate in free logic\ abbreviation fNot ("\<^bold>\") where "\<^bold>\\ \ \\" abbreviation fImpl (infixr "\<^bold>\" 13) where "\ \<^bold>\ \ \ \ \ \" abbreviation fId (infixr "\<^bold>=" 25) where "l \<^bold>= r \ l = r" abbreviation fAll ("\<^bold>\") where "\<^bold>\\ \ \x. E x \ \ x" abbreviation fAllBi (binder "\<^bold>\" [8]9) where "\<^bold>\x. \ x \ \<^bold>\\" abbreviation fOr (infixr "\<^bold>\" 21) where "\ \<^bold>\ \ \ (\<^bold>\\) \<^bold>\ \" abbreviation fAnd (infixr "\<^bold>\" 22) where "\ \<^bold>\ \ \ \<^bold>\(\<^bold>\\ \<^bold>\ \<^bold>\\)" abbreviation fImpli (infixr "\<^bold>\" 13) where "\ \<^bold>\ \ \ \ \<^bold>\ \" abbreviation fEquiv (infixr "\<^bold>\" 15) where "\ \<^bold>\ \ \ (\ \<^bold>\ \) \<^bold>\ (\ \<^bold>\ \)" abbreviation fEx ("\<^bold>\") where "\<^bold>\\ \ \<^bold>\(\<^bold>\(\y. \<^bold>\(\ y)))" abbreviation fExiBi (binder "\<^bold>\" [8]9) where "\<^bold>\x. \ x \ \<^bold>\\" section\Some Basic Notions in Category Theory\ text \Morphisms in the category are modeled as objects of type $i$. We introduce three partial functions, $dom$ (domain), $cod$ (codomain), and morphism composition ($\cdot$). For composition we assume set-theoretical composition here (i.e., functional composition from right to left). \label{IDMcL}\ consts domain:: "i\i" ("dom _" [108] 109) codomain:: "i\i" ("cod _" [110] 111) composition:: "i\i\i" (infix "\" 110) \ \Kleene Equality\ abbreviation KlEq (infixr "\" 56) where "x \ y \ (E x \<^bold>\ E y) \<^bold>\ x \<^bold>= y" \ \Existing Identity\ abbreviation ExId (infixr "\" 56) where "x \ y \ (E x \<^bold>\ E y \<^bold>\ x \<^bold>= y)" \ \Identity-morphism: see also p.~4. of \cite{FreydScedrov90}.\ abbreviation "ID i \ (\<^bold>\x. E(i\x) \<^bold>\ i\x \ x) \<^bold>\ (\<^bold>\x. E(x\i) \<^bold>\ x\i \ x)" \ \Identity-morphism: Mac Lane's definition, the same as ID except for notion of equality.\ abbreviation "IDMcL \ \ (\<^bold>\\. E(\\\) \<^bold>\ \\\ = \) \<^bold>\ (\<^bold>\\. E(\\\) \<^bold>\ \\\ = \)" \ \The two notions of identity-morphisms are obviously equivalent.\ lemma IDPredicates: "ID \ IDMcL" by auto -section\The Axioms Sets studied by Benzm\"uller and Scott @{cite "R58"}\ +section\The Axioms Sets studied by Benzm\"uller and Scott \<^cite>\"R58"\\ subsection\AxiomsSet1\ text\AxiomsSet1 generalizes the notion of a monoid by introducing a partial, strict binary composition operation ``$\cdot$''. The existence of left and right identity elements is addressed in axioms @{term "C\<^sub>i"} and @{term "D\<^sub>i"}. The notions of $dom$ (domain) and $cod$ (codomain) abstract from their common meaning in the context of sets. In category theory we work with just a single type of objects (the type $i$ in our setting) and therefore identity morphisms are employed to suitably characterize their meanings.\ locale AxiomsSet1 = assumes S\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" and E\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" and A\<^sub>i: "x\(y\z) \ (x\y)\z" and C\<^sub>i: "\<^bold>\y.\<^bold>\i. ID i \<^bold>\ i\y \ y" and D\<^sub>i: "\<^bold>\x.\<^bold>\j. ID j \<^bold>\ x\j \ x" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ lemma E\<^sub>iImpl: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" by (metis A\<^sub>i C\<^sub>i S\<^sub>i) \ \Uniqueness of i and j in the latter two axioms.\ lemma UC\<^sub>i: "\<^bold>\y.\<^bold>\i. ID i \<^bold>\ i\y \ y \<^bold>\ (\<^bold>\j.(ID j \<^bold>\ j\y \ y) \<^bold>\ i \ j)" by (smt (verit) A\<^sub>i C\<^sub>i S\<^sub>i) lemma UD\<^sub>i: "\<^bold>\x.\<^bold>\j. ID j \<^bold>\ x\j \ x \<^bold>\ (\<^bold>\i.(ID i \<^bold>\ x\i \ x) \<^bold>\ j \ i)" by (smt (verit) A\<^sub>i D\<^sub>i S\<^sub>i) \ \But i and j need not to equal.\ lemma "(\C D. (\<^bold>\y. ID (C y) \<^bold>\ (C y)\y \ y) \<^bold>\ (\<^bold>\x. ID (D x) \<^bold>\ x\(D x) \ x) \<^bold>\ \<^bold>\(D \<^bold>= C))" nitpick [satisfy] oops \ \Model found\ lemma "(\x. E x) \<^bold>\ (\C D. (\<^bold>\y. ID(C y) \<^bold>\ (C y)\y \ y) \<^bold>\ (\<^bold>\x. ID(D x) \<^bold>\ x\(D x) \ x) \<^bold>\ \<^bold>\(D \<^bold>= C))" nitpick [satisfy] oops \ \Model found\ end subsection\AxiomsSet2\ text\AxiomsSet2 is developed from AxiomsSet1 by Skolemization of the existentially quantified variables $i$ and $j$ in axioms $C_i$ and $D_i$. We can argue semantically that every model of AxiomsSet1 has such functions. Hence, we get a conservative extension of AxiomsSet1. The strictness axiom $S$ is extended, so that strictness is now also postulated for the new Skolem functions $dom$ and $cod$.\ locale AxiomsSet2 = assumes S\<^sub>i\<^sub>i: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" and E\<^sub>i\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" and A\<^sub>i\<^sub>i: "x\(y\z) \ (x\y)\z" and C\<^sub>i\<^sub>i: "E y \<^bold>\ (ID(cod y) \<^bold>\ (cod y)\y \ y)" and D\<^sub>i\<^sub>i: "E x \<^bold>\ (ID(dom x) \<^bold>\ x\(dom x) \ x)" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ lemma E\<^sub>i\<^sub>iImpl: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" by (metis A\<^sub>i\<^sub>i C\<^sub>i\<^sub>i S\<^sub>i\<^sub>i) lemma domTotal: "E x \<^bold>\ E(dom x)" by (metis D\<^sub>i\<^sub>i S\<^sub>i\<^sub>i) lemma codTotal: "E x \<^bold>\ E(cod x)" by (metis C\<^sub>i\<^sub>i S\<^sub>i\<^sub>i) end subsubsection\AxiomsSet2 entails AxiomsSet1\ context AxiomsSet2 begin lemma S\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" using S\<^sub>i\<^sub>i by blast lemma E\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" using E\<^sub>i\<^sub>i by blast lemma A\<^sub>i: "x\(y\z) \ (x\y)\z" using A\<^sub>i\<^sub>i by blast lemma C\<^sub>i: "\<^bold>\y.\<^bold>\i. ID i \<^bold>\ i\y \ y" by (metis C\<^sub>i\<^sub>i S\<^sub>i\<^sub>i) lemma D\<^sub>i: "\<^bold>\x.\<^bold>\j. ID j \<^bold>\ x\j \ x" by (metis D\<^sub>i\<^sub>i S\<^sub>i\<^sub>i) end subsubsection\AxiomsSet1 entails AxiomsSet2 (by semantic means)\ text\By semantic means (Skolemization).\ subsection\AxiomsSet3\ text\In AxiomsSet3 the existence axiom $E_{ii}$ from AxiomsSet2 is simplified by taking advantage of the two new Skolem functions $dom$ and $cod$. The left-to-right direction of existence axiom $E_{iii}$ is implied.\ locale AxiomsSet3 = assumes S\<^sub>i\<^sub>i\<^sub>i: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x ) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" and E\<^sub>i\<^sub>i\<^sub>i: "E(x\y) \<^bold>\ (dom x \ cod y \<^bold>\ E(cod y))" and A\<^sub>i\<^sub>i\<^sub>i: "x\(y\z) \ (x\y)\z" and C\<^sub>i\<^sub>i\<^sub>i: "E y \<^bold>\ (ID(cod y) \<^bold>\ (cod y)\y \ y)" and D\<^sub>i\<^sub>i\<^sub>i: "E x \<^bold>\ (ID(dom x) \<^bold>\ x\(dom x) \ x)" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ lemma E\<^sub>i\<^sub>i\<^sub>iImpl: "E(x\y) \<^bold>\ (dom x \ cod y \<^bold>\ E(cod y))" by (metis (full_types) A\<^sub>i\<^sub>i\<^sub>i C\<^sub>i\<^sub>i\<^sub>i D\<^sub>i\<^sub>i\<^sub>i S\<^sub>i\<^sub>i\<^sub>i) end subsubsection\AxiomsSet3 entails AxiomsSet2\ context AxiomsSet3 begin lemma S\<^sub>i\<^sub>i: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x ) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" using S\<^sub>i\<^sub>i\<^sub>i by blast lemma E\<^sub>i\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" by (metis A\<^sub>i\<^sub>i\<^sub>i C\<^sub>i\<^sub>i\<^sub>i D\<^sub>i\<^sub>i\<^sub>i E\<^sub>i\<^sub>i\<^sub>i S\<^sub>i\<^sub>i\<^sub>i) lemma A\<^sub>i\<^sub>i: "x\(y\z) \ (x\y)\z" using A\<^sub>i\<^sub>i\<^sub>i by blast lemma C\<^sub>i\<^sub>i: "E y \<^bold>\ (ID(cod y) \<^bold>\ (cod y)\y \ y)" using C\<^sub>i\<^sub>i\<^sub>i by auto lemma D\<^sub>i\<^sub>i: "E x \<^bold>\ (ID(dom x) \<^bold>\ x\(dom x) \ x)" using D\<^sub>i\<^sub>i\<^sub>i by auto end subsubsection\AxiomsSet2 entails AxiomsSet3\ context AxiomsSet2 begin lemma S\<^sub>i\<^sub>i\<^sub>i: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" using S\<^sub>i\<^sub>i by blast lemma E\<^sub>i\<^sub>i\<^sub>i: "E(x\y) \<^bold>\ (dom x \ cod y \<^bold>\ E(cod y))" by (metis C\<^sub>i\<^sub>i D\<^sub>i\<^sub>i E\<^sub>i\<^sub>i S\<^sub>i\<^sub>i) lemma A\<^sub>i\<^sub>i\<^sub>i: "x\(y\z) \ (x\y)\z" using A\<^sub>i\<^sub>i by blast lemma C\<^sub>i\<^sub>i\<^sub>i: "E y \<^bold>\ (ID(cod y) \<^bold>\ (cod y)\y \ y)" using C\<^sub>i\<^sub>i by auto lemma D\<^sub>i\<^sub>i\<^sub>i: "E x \<^bold>\ (ID(dom x) \<^bold>\ x\(dom x) \ x)" using D\<^sub>i\<^sub>i by auto end subsection\The Axioms Set AxiomsSet4\ text\AxiomsSet4 simplifies the axioms $C_{iii}$ and $D_{iii}$. However, as it turned out, these simplifications also require the existence axiom $E_{iii}$ to be strengthened into an equivalence.\ locale AxiomsSet4 = assumes S\<^sub>i\<^sub>v: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" and E\<^sub>i\<^sub>v: "E(x\y) \<^bold>\ (dom x \ cod y \<^bold>\ E(cod y))" and A\<^sub>i\<^sub>v: "x\(y\z) \ (x\y)\z" and C\<^sub>i\<^sub>v: "(cod y)\y \ y" and D\<^sub>i\<^sub>v: "x\(dom x) \ x" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ end subsubsection\AxiomsSet4 entails AxiomsSet3\ context AxiomsSet4 begin lemma S\<^sub>i\<^sub>i\<^sub>i: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" using S\<^sub>i\<^sub>v by blast lemma E\<^sub>i\<^sub>i\<^sub>i: "E(x\y) \<^bold>\ (dom x \ cod y \<^bold>\ (E(cod y)))" using E\<^sub>i\<^sub>v by blast lemma A\<^sub>i\<^sub>i\<^sub>i: "x\(y\z) \ (x\y)\z" using A\<^sub>i\<^sub>v by blast lemma C\<^sub>i\<^sub>i\<^sub>i: "E y \<^bold>\ (ID(cod y) \<^bold>\ (cod y)\y \ y)" by (metis C\<^sub>i\<^sub>v D\<^sub>i\<^sub>v E\<^sub>i\<^sub>v) lemma D\<^sub>i\<^sub>i\<^sub>i: "E x \<^bold>\ (ID(dom x) \<^bold>\ x\(dom x) \ x)" by (metis C\<^sub>i\<^sub>v D\<^sub>i\<^sub>v E\<^sub>i\<^sub>v) end subsubsection\AxiomsSet3 entails AxiomsSet4\ context AxiomsSet3 begin lemma S\<^sub>i\<^sub>v: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x ) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" using S\<^sub>i\<^sub>i\<^sub>i by blast lemma E\<^sub>i\<^sub>v: "E(x\y) \<^bold>\ (dom x \ cod y \<^bold>\ E(cod y))" by (metis (full_types) A\<^sub>i\<^sub>i\<^sub>i C\<^sub>i\<^sub>i\<^sub>i D\<^sub>i\<^sub>i\<^sub>i E\<^sub>i\<^sub>i\<^sub>i S\<^sub>i\<^sub>i\<^sub>i) lemma A\<^sub>i\<^sub>v: "x\(y\z) \ (x\y)\z" using A\<^sub>i\<^sub>i\<^sub>i by blast lemma C\<^sub>i\<^sub>v: "(cod y)\y \ y" using C\<^sub>i\<^sub>i\<^sub>i S\<^sub>i\<^sub>i\<^sub>i by blast lemma D\<^sub>i\<^sub>v: "x\(dom x) \ x" using D\<^sub>i\<^sub>i\<^sub>i S\<^sub>i\<^sub>i\<^sub>i by blast end subsection\AxiomsSet5\ - text\AxiomsSet5 has been proposed by Scott @{cite "Scott79"} in the 1970s. This set of + text\AxiomsSet5 has been proposed by Scott \<^cite>\"Scott79"\ in the 1970s. This set of axioms is equivalent to the axioms set presented by Freyd and Scedrov in their textbook - ``Categories, Allegories'' @{cite "FreydScedrov90"} when encoded in free logic, corrected/adapted + ``Categories, Allegories'' \<^cite>\"FreydScedrov90"\ when encoded in free logic, corrected/adapted and further simplified, see Section 5.\ locale AxiomsSet5 = assumes S1: "E(dom x) \<^bold>\ E x" and S2: "E(cod y) \<^bold>\ E y" and S3: "E(x\y) \<^bold>\ dom x \ cod y" and S4: "x\(y\z) \ (x\y)\z" and S5: "(cod y)\y \ y" and S6: "x\(dom x) \ x" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ end subsubsection\AxiomsSet5 entails AxiomsSet4\ context AxiomsSet5 begin lemma S\<^sub>i\<^sub>v: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x ) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" using S1 S2 S3 by blast lemma E\<^sub>i\<^sub>v: "E(x\y) \<^bold>\ (dom x \ cod y \<^bold>\ E(cod y))" using S3 by metis lemma A\<^sub>i\<^sub>v: "x\(y\z) \ (x\y)\z" using S4 by blast lemma C\<^sub>i\<^sub>v: "(cod y)\y \ y" using S5 by blast lemma D\<^sub>i\<^sub>v: "x\(dom x) \ x" using S6 by blast end subsubsection\AxiomsSet4 entails AxiomsSet5\ context AxiomsSet4 begin lemma S1: "E(dom x) \<^bold>\ E x" using S\<^sub>i\<^sub>v by blast lemma S2: "E(cod y) \<^bold>\ E y" using S\<^sub>i\<^sub>v by blast lemma S3: "E(x\y) \<^bold>\ dom x \ cod y" using E\<^sub>i\<^sub>v by metis lemma S4: "x\(y\z) \ (x\y)\z" using A\<^sub>i\<^sub>v by blast lemma S5: "(cod y)\y \ y" using C\<^sub>i\<^sub>v by blast lemma S6: "x\(dom x) \ x" using D\<^sub>i\<^sub>v by blast end -section\The Axioms Sets by Freyd and Scedrov @{cite "FreydScedrov90"}\ +section\The Axioms Sets by Freyd and Scedrov \<^cite>\"FreydScedrov90"\\ subsection\AxiomsSet6\ -text\The axioms by Freyd and Scedrov @{cite "FreydScedrov90"} in our notation, when being +text\The axioms by Freyd and Scedrov \<^cite>\"FreydScedrov90"\ in our notation, when being corrected (cf. the modification in axiom A1). Freyd and Scedrov employ a different notation for $dom\ x$ and $cod\ x$. They denote these operations by $\Box x$ and $x\Box$. Moreover, they employ diagrammatic composition instead of the set-theoretic definition (functional composition from right to left) used so far. We leave it to the reader to verify that their axioms corresponds to the axioms presented here modulo an appropriate conversion of notation.\ locale AxiomsSet6 = assumes A1: "E(x\y) \<^bold>\ dom x \ cod y" and A2a: "cod(dom x) \ dom x" and A2b: "dom(cod y) \ cod y" and A3a: "x\(dom x) \ x" and A3b: "(cod y)\y \ y" and A4a: "dom(x\y) \ dom((dom x)\y)" and A4b: "cod(x\y) \ cod(x\(cod y))" and A5: "x\(y\z) \ (x\y)\z" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ end subsubsection\AxiomsSet6 entails AxiomsSet5\ context AxiomsSet6 begin lemma S1: "E(dom x) \<^bold>\ E x" by (metis A1 A2a A3a) lemma S2: "E(cod y) \<^bold>\ E y" using A1 A2b A3b by metis lemma S3: "E(x\y) \<^bold>\ dom x \ cod y" by (metis A1) lemma S4: "x\(y\z) \ (x\y)\z" using A5 by blast lemma S5: "(cod y)\y \ y" using A3b by blast lemma S6: "x\(dom x) \ x" using A3a by blast lemma A4aRedundant: "dom(x\y) \ dom((dom x)\y)" using A1 A2a A3a A5 by metis lemma A4bRedundant: "cod(x\y) \ cod(x\(cod y))" using A1 A2b A3b A5 by (smt (verit)) lemma A2aRedundant: "cod(dom x) \ dom x" using A1 A3a A3b A4a A4b by smt lemma A2bRedundant: "dom(cod y) \ cod y" using A1 A3a A3b A4a A4b by smt end subsubsection\AxiomsSet5 entails AxiomsSet6\ context AxiomsSet5 begin lemma A1: "E(x\y) \<^bold>\ dom x \ cod y" using S3 by blast lemma A2: "cod(dom x) \ dom x" by (metis S1 S2 S3 S6) lemma A2b: "dom(cod y) \ cod y" using S1 S2 S3 S5 by metis lemma A3a: "x\(dom x) \ x" using S6 by auto lemma A3b: "(cod y)\y \ y" using S5 by blast lemma A4a: "dom(x\y) \ dom((dom x)\y)" by (metis S1 S3 S4 S5 S6) lemma A4b: "cod(x\y) \ cod(x\(cod y))" by (metis (full_types) S2 S3 S4 S5 S6) lemma A5: "x\(y\z) \ (x\y)\z" using S4 by blast end subsection\AxiomsSet7 (technically flawed)\ text\The axioms by Freyd and Scedrov in our notation, without the suggested correction of axiom A1. This axioms set is technically flawed when encoded in our given context. It leads to a constricted inconsistency.\ locale AxiomsSet7 = assumes A1: "E(x\y) \<^bold>\ dom x \ cod y" and A2a: "cod(dom x) \ dom x " and A2b: "dom(cod y) \ cod y" and A3a: "x\(dom x) \ x" and A3b: "(cod y)\y \ y" and A4a: "dom(x\y) \ dom((dom x)\y)" and A4b: "cod(x\y) \ cod(x\(cod y))" and A5: "x\(y\z) \ (x\y)\z" begin lemma True nitpick [satisfy] oops \ \Consistency\ (* lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops --{*No model found*} lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops --{*No model found*} *) lemma InconsistencyAutomatic: "(\x. \<^bold>\(E x)) \<^bold>\ False" by (metis A1 A2a A3a) \ \Inconsistency\ lemma "\x. E x" using InconsistencyAutomatic by auto lemma InconsistencyInteractive: assumes NEx: "\x. \<^bold>\(E x)" shows False proof - obtain a where 1: "\<^bold>\(E a)" using NEx by auto have 2: "a\(dom a) \ a" using A3a by blast have 3: "\<^bold>\(E(a\(dom a)))" using 1 2 by metis have 4: "E(a\(dom a)) \<^bold>\ dom a \ cod(dom a)" using A1 by blast have 5: "cod(dom a) \ dom a" using A2a by blast have 6: "E(a\(dom a)) \<^bold>\ dom a \ dom a" using 4 5 by auto have 7: "E(a\(dom a))" using 6 by blast then show ?thesis using 7 3 by blast qed end subsection\AxiomsSet7orig (technically flawed)\ text\The axioms by Freyd and Scedrov in their original notation, without the suggested correction of axiom A1. We present the constricted inconsistency argument from above once again, but this time in the original notation of Freyd and Scedrov.\ locale AxiomsSet7orig = fixes source:: "i\i" ("\_" [108] 109) and target:: "i\i" ("_\" [110] 111) and compositionF:: "i\i\i" (infix "\<^bold>\" 110) assumes A1: "E(x\<^bold>\y) \<^bold>\ (x\ \ \y)" and A2a: "((\x)\) \ \x" and A2b: "\(x\) \ \x" and A3a: "(\x)\<^bold>\x \ x" and A3b: "x\<^bold>\(x\) \ x" and A4a: "\(x\<^bold>\y) \ \(x\<^bold>\(\y))" and A4b: "(x\<^bold>\y)\ \ ((x\)\<^bold>\y)\" and A5: "x\<^bold>\(y\<^bold>\z) \ (x\<^bold>\y)\<^bold>\z" begin lemma True nitpick [satisfy] oops \ \Consistency\ (* lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops --{*No model found*} lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops --{*No model found*} *) lemma InconsistencyAutomatic: "(\x. \<^bold>\(E x)) \<^bold>\ False" by (metis A1 A2a A3a) \ \Inconsistency\ lemma "\x. E x" using InconsistencyAutomatic by auto lemma InconsistencyInteractive: assumes NEx: "\x. \<^bold>\(E x)" shows False proof - obtain a where 1: "\<^bold>\(E a)" using assms by auto have 2: "(\a)\<^bold>\a \ a" using A3a by blast have 3: "\<^bold>\(E((\a)\<^bold>\a))" using 1 2 by metis have 4: "E((\a)\<^bold>\a) \<^bold>\ (\a)\ \ \a" using A1 by blast have 5: "(\a)\ \ \a" using A2a by blast have 6: "E((\a)\<^bold>\a)" using 4 5 by blast then show ?thesis using 6 3 by blast qed end subsection\AxiomsSet8 (algebraic reading, still technically flawed)\ text\The axioms by Freyd and Scedrov in our notation again, but this time we adopt an algebraic reading of the free variables, meaning that they range over existing morphisms only.\ locale AxiomsSet8 = assumes B1: "\<^bold>\x.\<^bold>\y. E(x\y) \<^bold>\ dom x \ cod y" and B2a: "\<^bold>\x. cod(dom x) \ dom x " and B2b: "\<^bold>\y. dom(cod y) \ cod y" and B3a: "\<^bold>\x. x\(dom x) \ x" and B3b: "\<^bold>\y. (cod y)\y \ y" and B4a: "\<^bold>\x.\<^bold>\y. dom(x\y) \ dom((dom x)\y)" and B4b: "\<^bold>\x.\<^bold>\y. cod(x\y) \ cod(x\(cod y))" and B5: "\<^bold>\x.\<^bold>\y.\<^bold>\z. x\(y\z) \ (x\y)\z" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ end text\None of the axioms in AxiomsSet5 are implied.\ context AxiomsSet8 begin lemma S1: "E(dom x) \<^bold>\ E x" nitpick oops \ \Nitpick finds a countermodel\ lemma S2: "E(cod y) \<^bold>\ E y" nitpick oops \ \Nitpick finds a countermodel\ lemma S3: "E(x\y) \<^bold>\ dom x \ cod y" nitpick oops \ \Nitpick finds a countermodel\ lemma S4: "x\(y\z) \ (x\y)\z" nitpick oops \ \Nitpick finds a countermodel\ lemma S5: "(cod y)\y \ y" nitpick oops \ \Nitpick finds a countermodel\ lemma S6: "x\(dom x) \ x" nitpick oops \ \Nitpick finds a countermodel\ end subsection\AxiomsSet8Strict (algebraic reading)\ text\The situation changes when strictness conditions are postulated. Note that in the algebraic framework of Freyd and Scedrov such conditions have to be assumed as given in the logic, while here we can explicitly encode them as axioms.\ locale AxiomsSet8Strict = AxiomsSet8 + assumes B0a: "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" and B0b: "E(dom x) \<^bold>\ E x" and B0c: "E(cod x) \<^bold>\ E x" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ end subsubsection\AxiomsSet8Strict entails AxiomsSet5\ context AxiomsSet8Strict begin lemma S1: "E(dom x) \<^bold>\ E x" using B0b by blast lemma S2: "E(cod y) \<^bold>\ E y" using B0c by blast lemma S3: "E(x\y) \<^bold>\ dom x \ cod y" by (metis B0a B0b B0c B1 B3a) lemma S4: "x\(y\z) \ (x\y)\z" by (meson B0a B5) lemma S5: "(cod y)\y \ y" using B0a B3b by blast lemma S6: "x\(dom x) \ x" using B0a B3a by blast end subsubsection\AxiomsSet5 entails AxiomsSet8Strict\ context AxiomsSet5 begin lemma B0a: "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" using S1 S2 S3 by blast lemma B0b: "E(dom x) \<^bold>\ E x" using S1 by blast lemma B0c: "E(cod x) \<^bold>\ E x" using S2 by blast lemma B1: "\<^bold>\x.\<^bold>\y. E(x\y) \<^bold>\ dom x \ cod y" by (metis S3 S5) lemma B2a: "\<^bold>\x. cod(dom x) \ dom x" using A2 by blast lemma B2b: "\<^bold>\y. dom(cod y) \ cod y" using A2b by blast lemma B3a: "\<^bold>\x. x\(dom x) \ x" using S6 by blast lemma B3b: "\<^bold>\y. (cod y)\y \ y" using S5 by blast lemma B4a: "\<^bold>\x.\<^bold>\y. dom(x\y) \ dom((dom x)\y)" by (metis S1 S3 S4 S6) lemma B4b: "\<^bold>\x.\<^bold>\y. cod(x\y) \ cod(x\(cod y))" by (metis S1 S2 S3 S4 S5) lemma B5: "\<^bold>\x.\<^bold>\y.\<^bold>\z. x\(y\z) \ (x\y)\z" using S4 by blast end subsubsection\AxiomsSet8Strict is Redundant\ text\AxiomsSet8Strict is redundant: either the B2-axioms can be omitted or the B4-axioms.\ context AxiomsSet8Strict begin lemma B2aRedundant: "\<^bold>\x. cod(dom x) \ dom x " by (metis B0a B1 B3a) lemma B2bRedundant: "\<^bold>\y. dom(cod y) \ cod y" by (metis B0a B1 B3b) lemma B4aRedundant: "\<^bold>\x.\<^bold>\y. dom(x\y) \ dom((dom x)\y)" by (metis B0a B0b B1 B3a B5) lemma B4bRedundant: "\<^bold>\x.\<^bold>\y. cod(x\y) \ cod(x\(cod y))" by (metis B0a B0c B1 B3b B5) end - section\The Axioms Sets of Mac Lane @{cite "MacLane48"}\ + section\The Axioms Sets of Mac Lane \<^cite>\"MacLane48"\\ - text\We analyse the axioms set suggested by Mac Lane~@{cite "MacLane48"} already in 1948. + text\We analyse the axioms set suggested by Mac Lane~\<^cite>\"MacLane48"\ already in 1948. As for the theory by Freyd and Scedrov above, which was developed much later, we need to assume strictness of composition to show equivalence to our previous axiom sets. Note that his complicated conditions on existence of compositions proved to be unnecessary, as we show. It shows it is hard to think about partial operations.\ locale AxiomsSetMcL = assumes C\<^sub>0 : "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" and C\<^sub>1 : "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E((\\\)\\)) \<^bold>\ E(\\\)" and C\<^sub>1': "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E(\\(\\\))) \<^bold>\ E(\\\)" and C\<^sub>2 : "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E(\\\)) \<^bold>\ (E((\\\)\\) \<^bold>\ E(\\(\\\)) \<^bold>\ ((\\\)\\) = (\\(\\\)))" and C\<^sub>3 : "\<^bold>\\. \<^bold>\eD. IDMcL(eD) \<^bold>\ E(\\eD)" and C\<^sub>4 : "\<^bold>\\. \<^bold>\eR. IDMcL(eR) \<^bold>\ E(eR\\)" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ end text\Remember that IDMcL was defined on p.~\pageref{IDMcL} and proved equivalent to ID.\ subsection\AxiomsSetMcL entails AxiomsSet1\ context AxiomsSetMcL begin lemma S\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" using C\<^sub>0 by blast lemma E\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" by (metis C\<^sub>2) lemma A\<^sub>i: "x\(y\z) \ (x\y)\z" by (metis C\<^sub>1 C\<^sub>1' C\<^sub>2 C\<^sub>0) lemma C\<^sub>i: "\<^bold>\y.\<^bold>\i. ID i \<^bold>\ i\y \ y" using C\<^sub>4 by fastforce lemma D\<^sub>i: "\<^bold>\x.\<^bold>\j. ID j \<^bold>\ x\j \ x" using C\<^sub>3 by fastforce end subsection\AxiomsSet1 entails AxiomsSetMcL\ context AxiomsSet1 begin lemma C\<^sub>0 : "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" using S\<^sub>i by blast lemma C\<^sub>1 : "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E((\\\)\\)) \<^bold>\ E(\\\)" by (metis A\<^sub>i S\<^sub>i) lemma C\<^sub>1': "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E(\\(\\\))) \<^bold>\ E(\\\)" by (metis A\<^sub>i S\<^sub>i) lemma C\<^sub>2 : "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E(\\\)) \<^bold>\ (E((\\\)\\) \<^bold>\ E(\\(\\\)) \<^bold>\ ((\\\)\\) = (\\(\\\)))" by (smt A\<^sub>i C\<^sub>i E\<^sub>i S\<^sub>i) lemma C\<^sub>3 : "\<^bold>\\. \<^bold>\eD. IDMcL(eD) \<^bold>\ E(\\eD)" using D\<^sub>i by force lemma C\<^sub>4 : "\<^bold>\\. \<^bold>\eR. IDMcL(eR) \<^bold>\ E(eR\\)" using C\<^sub>i by force end subsection\Skolemization of the Axioms of Mac Lane\ text\Mac Lane employs diagrammatic composition instead of the set-theoretic definition as used in our axiom sets. As we have seen above, this is not a problem as long as composition is the only primitive. But when adding the Skolem terms $dom$ and $cod$ care must be taken and we should actually transform all axioms into a common form. Below we address this (in a minimal way) by using $dom$ in axiom @{term "C\<^sub>3s"} and $cod$ in axiom @{term "C\<^sub>4s"}, which is opposite of what Mac Lane proposed. For this axioms set we then show equivalence to AxiomsSet1/2/5.\ locale SkolemizedAxiomsSetMcL = assumes C\<^sub>0s : "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \ (E(dom x) \<^bold>\ E x) \ (E(cod y) \<^bold>\ E y)" and C\<^sub>1s : "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E((\\\)\\)) \<^bold>\ E(\\\)" and C\<^sub>1's: "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E(\\(\\\))) \<^bold>\ E(\\\)" and C\<^sub>2s : "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E(\\\)) \<^bold>\ (E((\\\)\\) \<^bold>\ E(\\(\\\)) \<^bold>\ ((\\\)\\) = (\\(\\\)))" and C\<^sub>3s : "\<^bold>\\. IDMcL(dom \) \<^bold>\ E(\\(dom \))" and C\<^sub>4s : "\<^bold>\\. IDMcL(cod \) \<^bold>\ E((cod \)\\)" begin lemma True nitpick [satisfy] oops \ \Consistency\ lemma assumes "\x. \<^bold>\(E x)" shows True nitpick [satisfy] oops \ \Consistency\ lemma assumes "(\x. \<^bold>\(E x)) \ (\x. (E x))" shows True nitpick [satisfy] oops \ \Consistency\ end subsection\SkolemizedAxiomsSetMcL entails AxiomsSetMcL and AxiomsSet1-5\ context SkolemizedAxiomsSetMcL begin lemma C\<^sub>0 : "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" using C\<^sub>0s by blast lemma C\<^sub>1 : "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E((\\\)\\)) \<^bold>\ E(\\\)" using C\<^sub>1s by blast lemma C\<^sub>1': "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E(\\(\\\))) \<^bold>\ E(\\\)" using C\<^sub>1's by blast lemma C\<^sub>2 : "\<^bold>\\ \ \. (E(\\\) \<^bold>\ E(\\\)) \<^bold>\ (E((\\\)\\) \<^bold>\ E(\\(\\\)) \<^bold>\ ((\\\)\\) = (\\(\\\)))" using C\<^sub>2s by blast lemma C\<^sub>3 : "\<^bold>\\. \<^bold>\eD. IDMcL(eD) \<^bold>\ E(\\eD)" by (metis C\<^sub>0s C\<^sub>3s) lemma C\<^sub>4 : "\<^bold>\\. \<^bold>\eR. IDMcL(eR) \<^bold>\ E(eR\\)" by (metis C\<^sub>0s C\<^sub>4s) lemma S\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y)" using C\<^sub>0s by blast lemma E\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" by (metis C\<^sub>2s) lemma A\<^sub>i: "x\(y\z) \ (x\y)\z" by (metis C\<^sub>1s C\<^sub>1's C\<^sub>2s C\<^sub>0s) lemma C\<^sub>i: "\<^bold>\y.\<^bold>\i. ID i \<^bold>\ i\y \ y" by (metis C\<^sub>0s C\<^sub>4s) lemma D\<^sub>i: "\<^bold>\x.\<^bold>\j. ID j \<^bold>\ x\j \ x" by (metis C\<^sub>0s C\<^sub>3s) lemma S\<^sub>i\<^sub>i: "(E(x\y) \<^bold>\ (E x \<^bold>\ E y)) \<^bold>\ (E(dom x ) \<^bold>\ E x) \<^bold>\ (E(cod y) \<^bold>\ E y)" using C\<^sub>0s by blast lemma E\<^sub>i\<^sub>i: "E(x\y) \<^bold>\ (E x \<^bold>\ E y \<^bold>\ (\<^bold>\z. z\z \ z \<^bold>\ x\z \ x \<^bold>\ z\y \ y))" by (metis C\<^sub>2s) lemma A\<^sub>i\<^sub>i: "x\(y\z) \ (x\y)\z" by (metis C\<^sub>1s C\<^sub>1's C\<^sub>2s C\<^sub>0s) lemma C\<^sub>i\<^sub>i: "E y \<^bold>\ (ID(cod y) \<^bold>\ (cod y)\y \ y)" using C\<^sub>4s by auto lemma D\<^sub>i\<^sub>i: "E x \<^bold>\ (ID(dom x) \<^bold>\ x\(dom x) \ x)" using C\<^sub>3s by auto \ \AxiomsSets3/4 are omitted here; we already know they are equivalent.\ lemma S1: "E(dom x) \<^bold>\ E x" using C\<^sub>0s by blast lemma S2: "E(cod y) \<^bold>\ E y" using C\<^sub>0s by blast lemma S3: "E(x\y) \<^bold>\ dom x \ cod y" by (metis (full_types) C\<^sub>0s C\<^sub>1s C\<^sub>1's C\<^sub>2s C\<^sub>3s C\<^sub>4s) lemma S4: "x\(y\z) \ (x\y)\z" by (metis C\<^sub>0s C\<^sub>1s C\<^sub>1's C\<^sub>2s) lemma S5: "(cod y)\y \ y" using C\<^sub>0s C\<^sub>4s by blast lemma S6: "x\(dom x) \ x" using C\<^sub>0s C\<^sub>3s by blast end (*<*) end (*>*)