没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记91(2004)212-228www.elsevier.com/locate/entcs范畴理论的可读格雷格·澳大利亚国立大学自动推理组,澳大利亚摘要我们正式开发类理论米田的引理,使用伊莎贝尔/HOL/Isar,并调查以前的形式化。通过使用最近添加的伊莎贝尔功能,我们已经产生了一个正式的文本,更接近非正式的数学。保留字: 形式化数学,定理证明,范畴论1介绍形式化数学是一门计算机科学学科,在很大程度上被数学家所忽视。这是有充分理由的。它需要几个月才能成为一个合格的用户的任何证明助理。一旦掌握了这个工具,即使是最基本的结果也需要几天的乏味劳动才能重现。也许最糟糕的是,最终的正式文本对于任何不熟悉所讨论的工具的如果有可能在没有过多的误差的情况下产生形式化,那么数学家们可能会这样做以增加信心。如果证明中有错误,在试图将其形式化时,几乎肯定会被发现为了最大限度地减少所需的时间,并最大限度地提高结果的价值,形式化应该尽可能接近其非正式的起源。1电子邮件:greg. anu.edu.au1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2003.12.014G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-213在Isabelle [21]实施的证明辅助技术的最新进展使得减少正式和非正式工作之间的差距成为可能。我们的目标之一就是证明这一点。范畴论是一个合适的测试,因为范畴论我们首先对范畴论的现有形式化进行了一个调查。大部分的文件是我们自己的形式化使用的是- abelle/HOL/Isar的概述。我们的结束语包括一些进一步工作的计划。2调查范畴理论形式化的关键特征是:语言、类型系统、表示、自动化、覆盖和项目状态。证明助手提供了一种定义概念、陈述定理和给出证明的语言证明语言有两种风格:过程式和声明式。大多数的证明助理使用程序风格。一个过程性的证明包括一些指令,称为策略,展示了如何通过应用逻辑规则来达到目标定理请注意,这些只是广义上的“证明”,因为它们缺少两个重要的性质。首先,通常没有我们可以进行元理论推理的证明对象。其次,普通读者不会被说服接受这样一个证明的结论:相反,人们必须首先相信证明检查器的可靠性,然后执行它。声明式证明语言[19][5][33][32][12][36][28]试图克服第二个缺陷。它们模仿证明助理也配备了一个类型系统。根据我们的目的,主要的种是单型、简单型和依赖型。“Mono-typed”指的是像一阶逻辑这样的系统,在这种系统中没有真正有趣的类型系统。简单类型系统有原子类型和类型构造函数,它们组合类型以产生新类型。HOL证明器[30]的高阶逻辑是简单类型化的。依赖类型系统具有类型也接受条件的构造函数。例如,对于每对自然数(m,n),我们有一类m×n矩阵。Coq [14]和NuPrl [1]有依赖类型系统。一个有用的调查和比较定理证明助手可以在[35]中找到。在将前形式化概念编码到形式化概念中时,214G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-系统这些选择取决于开发过程的容易程度以及解释它需要多少时间。举个简单的例子,我们可以将函子表示为函数对,或者我们可以隐式地保留对对象的操作我们研究的一些发展自动化的证明作为一个主要目标,而其他人给出明确的详细证明。当然,自动化本身就是一个有价值的目标,但它对可读的形式化也很重要。因为冗长的证据会分散注意力。涵盖更多理论的发展值得更大的关注,因为这表明他们正在做正确的事情。然而,这个判断必须谨慎:好的想法可能因为实际原因而没有结果,或者坏的想法已经被纯粹的努力克服了为了比较所涵盖的理论数量,我们将使用标准文本的目录[16]。我称之为“麦克莱恩度量”。最后,我们感兴趣的是,形式化是否处于主动部署之下,是否在其证明助手的当前版本上运行,或者仅仅是历史兴趣。我们现在依次审查每一项发展。它们根据所使用的校对助手进行分组。我们给了更好的形式化更大的空间。2.1Coq和LegoPeter Aczel领导了一个项目Galois [3],其目标是“以谓词风格形式化一些ab-代数”。 这项工作的一部分是使用乐高的范畴理论的形式化[2]。这种形式化的理论覆盖面很小,而且没有得到积极的发展。然而,它在依赖类型理论中对范畴的新颖表示已经被最成功的形式化所采用:Saıbi和Huet [26][25]的Coq [14setoid是一个三元组,由类型、类型上的关系和关系是等价的证明组成。类型的论域,通过等价性分解,看起来很像一个集合。在Aczel和Sa bi的形式化中,母集材料从[16,I,II,III]覆盖,包括米田的引理。此外,还证明了Freyd当前版本[27]包含105个.v文件,与Coq的当前(7.4)版本兼容这是一项很难理解的工作,除非你熟悉构造依赖类型理论。它与数学教科书中通常呈现的范畴论的关系充其量是间接的。然而,它确实比其他现有的形式化发展了更多的范畴理论。G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-215该学位论文[8]扩展了萨伊比发展的旧版本2.2MizarMizar [5]由大约30个“文章”组成,有两个不同的范畴理论发展[16,I,II,III]的大部分内容都被涵盖了,但除此之外很少。没有任何限制或一般限制。这些发展是一个大型的形式化数学综合图书馆因此,有更多的例子比其他发展,包括类别的群体,环,和模块,和偏序集被视为类别。两个开阳井开发项目之间的主要区别是对箭头的处理。人们使用通常的定义,其中一个类别有一个箭头集合,并且有从箭头到对象的源函数和目标函数。于是,人类就根据这些来定义另一个发展是改变-本机定义在[16,§1.8],其中函数从对象对到箭头组是类别定义的一部分。Mizar图书馆正在积极开发中。Mizar最近关于范畴理论的文章来自2001年。维护Mizar库是为了使其与当前版本的证明检查器兼容大多数用于形式化数学的计算机系统使用类型λ-演算作为其基础。开阳是个例外。它的逻辑是经典的和一阶的。它的公理是塔斯基-格罗滕迪克集合论的公理,它“基本上是[23].另一个区别是证明的风格Mizar与Automath[19]起源于最近流行的“声明性”证明的概念这是可能遵循的推理在一个开阳证明。Mizar几乎没有自动化:必须详细地证明它。因此,Mizar的形式化非常长。证明米田引理的文章长达1730行,并且依赖于至少8篇类似大小的范畴论相关文章,以及更基本的文章。我们自己的formalisation下面由1208行,在我们看来,太长的内容。对显而易见的事实作冗长的证明并不能帮助读者理解其中的道理。Mizar的另一个缺点是缺乏介绍性文档。此外,该系统的源代码也不是公开的。这似乎216G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-不适合这样的基础工作,在那里一切都必须怀疑和检查,没有什么是信任的。2.3NuPrl在1990年,Altucher和Panangelo出版我似乎没有进一步的工作已经做了这个NuPrl [1]的发展。重点是证明的自动化,以及从这些证明中提取程序。这种能力是NuPrl的一个关键特性。范畴论被认为是一个很有前途的主题,因为它与类型论和函数式编程的联系,并且因为例行的这一发展的源文件似乎不可用。 无论如何,它不太可能与当前版本的系统一起工作。[4]中的解释是非常有限的。 有人声称, 子范畴,极限,双解,笛卡尔闭范畴和三元组。发展的重点是证明伴随函子定理[16,V.6,定理2]。NuPrl最近的一个发展是Tjark Weber在[31]中提出的。这篇硕士论文关注的是程序转换“变形”和“变形”,它们是根据范畴理论定义的在定义了范畴和函子之后,引入了代数、余代数和同态。这些概念然后被用来定义程序转换概念。2.4伊莎贝尔和霍尔Lockwood Morris使用HOL [30]形式化了[16,I,II,III]中的大部分,包括Yoneda目前还没有出版物,也没有公开分发HOL代码。我的资料来源是一份未发表的手稿[18]和与第一作者的电子邮件通信。像旧的NuPrl e Quiort [4]一样,这里的重点是自动化。已经编写了一些策略来自动化最常见的证明任务,例如显示给定的术语表示所考虑类别的箭头或对象,并将复杂的谓词分解为简单的子目标。虽然Coq和NuPrl有依赖类型,但HOL和Isabelle只有简单类型。这使得范畴论受制于令人讨厌的公案,比如以及这些在依赖类型系统中不会出现,因为相关的项和公式是病态类型的。Johan GlimmingG. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-217[ 10 ]包含了第一章的大部分内容和[16]第二章的部分内容均证明是在程序风格,使用伊萨尔的“战术仿真”。2.5别人在“计算范畴论”中描述的工作它由ML结构和功能组成,代表了分类理论的主要思想。例如,像许多形式化一样,一对类型上的类别是四个函数的元组:源目标标识和组合。不同之处在于没有公理。ML结构Cat的设计canhaveDom(1A)/=Aforex a mple e.即便如此,所定义的结构也可以用于正式的开发。此外,代码可能会形成一个分类的“逻辑框架”的基础[16,I,II,III]中的大多数概念的定义都已给出,再加上toposes。[ 24 ]的最后一章首先,由于Joseph Goguen使用了他开创性的代数规范语言OBJ [11]。只有最基本的概念被定义。 由于OBJ是“代数”的,唯一的公式是方程,唯一的推理规则是方程重写。没有明确的证明,只有自动重写。这肯定会限制该理论的发展。本章还总结了Roy Dyckho [ 9 ]利用Güot e borg T y p e TeC++理论直接表示为类型系统,具有原子类型(如Cat和Func)和规则(如ffi:CatB:CatFunc(ffi,B):type这是一个新颖的和有吸引力的方法,范畴理论和基础,值得进一步研究。我们还注意到Takahisi Mohri对形式化范畴理论的调查[17]。218G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-3发展正式发展的全文由Isabelle自动制作,长达27页。它可以在互联网上找到[20],以及Isabelle/HOL源文件。下面我们给出大部分定义、一些结果和几个证明。我们试图使范畴在这种形式背景下的表示尽可能接近数学文本中的通常描述一个类别被定义为一个六元组。类别记录类型有两个类型参数,箭头和对象类型各有一个。Isabelle的记录功能允许我们命名组件,并将这些名称用作投影。我们还定义了缩写形式(以大写字母开头)用于区域设置,其中类别可以省略或由数字下标指定record(Jo,Ja)类别=ob::Jo set(ob70)ar::Ja set(Ar70)dom::JaJo(Dom-[81]70)cod::JaJo(Cod-[81]70)[81]第80话:我是你的朋友comp::JaJaJa(infixl·60)每行末尾的括号之间是语法注释。例如,第一个(Ob170)就像是说:如果能单独给出这种语法可能会更好以明显的方式定义了人类常量定义hom::[(Jo,Ja,Jm)category-scheme,Jo,Jo] nJa set(Hom n- -)homCA Bn {f. f∈arC&domCf = A&codCf = B}MacLane [16,第27页]中的相应定义是hom C(a,b)={|f是一个箭头f:ab in C}locale[15]是一个固定的任意对象、假设和定义的命名集合。它节省了大量的重复,并模仿非正式的实践。这里,假设一个固定的对象C满足给定的规则。我们将假设写成规则(使用元连接词=),than公理(使用对象连接词)的。locale也会产生一个谓词,这样我们就可以写类别X来断言X满足locale中的假设G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-219comp-types假设中的箭头表示函数集。当应用于HomB C的成员时,复合操作返回一个函数,当应用于HomA B的成员时,该函数产生HomA C的成员。localecategory=structC+假设dom-object[intro]:f∈Ar=Dom f∈Obcod-object[intro]:f∈Ar=Cod f∈Ob左(左):f∈Ar=λId(Cod f)·f=f和id-right[simp]:F ∈Ar = πf ·Id(Dom f)=f和id-hom[介绍]:A∈Ob=A∈Hom A Aandcomp-types[intro]:AB C。 (化合物C):(HomB C)-(HomA B)-(HomA C)和comp-associative[simp]:f∈Ar=g∈Ar=h∈Ar=Cod h=Dom g=Cod g=Dom f=f·(g·h)=(f·g)·h虽然这个结合性规则相当清楚,但我们希望在未来的工作中更接近MacLane的陈述结合性。 对于配置中的给定对象和箭头,aFBGCK D一个人总是平等k(gf)=(kg)f甚至可以把任意的图表当作公式。那么上面的图可以是一个条件公式的前件,方程可以是条件公式的后件。我们跳过关于范畴的几个琐碎引理,继续讨论集合范畴的定义。我们不是假设存在一个包含所有集合的论域,而是定义一个给定论域集合U的子集的范畴。MacLane [16,page 11]称这些范畴为EnsU或Ens。该集合的类型是确定类别类型的参数。我们将集合范畴的箭头定义为三元组,以使定义域和上定义域明确。记录Jcset-arrow=set-dom::Jc setset-func::JcJcset-cod::Jc set不是记录类型set-arrow的每个实例都是合法的箭头。我们定义了一个谓词,它声明域和余域都在宇宙中,函数将域带入余域,220G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-该函数在域上是“外延的”。这意味着在该域之外,该函数采用“任意”值如果没有这个,N−i→dN和N−a→bsN是不同的,这不是我们想要的的具有限制域的函数理论是在Isabelle/HOL theorysrc/HOL/Library/FuncSet.thy中开发的,Isabelle2003发行版[21]。请注意,我们为集合箭头合成引入了一个新的符号一旦我们已经确定了我们的集合类别确实是类别,我们将能够在类别区域设置中使用·进行箭头组合。常量定义set-arrow::[Jc set,Jc set-arrow]设置boolset-arrow U fset-domfUset-codfU&(set-func f):(set-dom f)→(set-cod f)set-func f∈extensional(set-domf)set-id::[Jc set,Jc set]Jc set-arrowset-id U<$λs∈Pow U. (|set-dom = s,set-func = λx∈s. x,set-cod = s|)set-comp::[Jc set-arrow,Jc set-arrow]Jc set-arrow(中缀70)集合补偿(|set-dom=set-dom f,set-func=compose(set-dom f)(set-func g)(set-func f),设置代码=设置代码g|)set-cat::Jc set(Jc set,Jc set-arrow)category set-cat U(|ob=Pow U,ar ={f. 设置箭头U f},dom=set-dom,cod=set-cod,id=set-id U,comp=set-comp|)现在我们必须证明这个结构满足范畴公理。为举例说明:引理set-id-left:假设f ∈ar(set-cat U)显示set-id U(set-cod f)f=f和引理set-id-hom:假设A∈ob(集合U)显示id(set-cat U)A∈hom(set-cat U)A A并最终theoremset-cat-cat:category(set-cat U)函子是函数对目前的发展并不包括函子范畴,但要做到这一点,有必要将这些对与它们的域和上域范畴结合起来。record(Jo1,Ja1,Jo2,Ja2)functor=G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-221om::Jo1Jo2am::Ja1Ja2我们想写FA和Ff,这是通常的非正式符号。虽然我们可以用这种方式定义一个特定的F是重载的,但我们不能将函子定义为将对象带到对象、将箭头带到箭头的函数。尝试这样做会从类型推理模块产生一条愤怒的消息。相反,我们定义了一个替代的显式符号。还要注意,对于任何记录类型,都有一个名为whatever- scheme的类型用于该记录类型的扩展。语法-om::(Jo1,Ja1,Jo2,Ja2,Jm)函子-scheme-am::(Jo 1,Ja1,Jo2,Ja2,Jm)函子-方案Jo1Jo2(-a[81])翻译Foom F F a上午F我们用函子做的事情有点不同。函子的属性被定义为包含两个类别的区域设置中的谓词。locale为每个谓词节省了两个参数定义和命名谓词允许我们在推理中使用它们注意,我们断言类别与它们自己相等。这是一个将类型与谓词的类型对齐的localetwo-cats=categoryffi+categoryB+assumesffi=(ffi::(Jo1,Ja1,Jm1)category-scheme)assumesB=(B::(Jo2,Ja2,Jm2)category-scheme)修正了仿函数Bubool和仿函数cod::(Jo1,Ja1,Jo2,Ja2)仿函数Bubool和仿函数id::(Jo1,Ja1,Jo2,Ja2)仿函数Bubool和仿函数comp::(Jo1,Ja1,Jo2,Ja2)仿函数Bubool定义了仿函数Bubool和仿函数comp::(Jo1,Ja1,Jo2,Jf ∈Ar 1。 G o(Dom 1 f)= Dom 2(G a f)和鳕Gf ∈Ar 1。 G o(Cod 1 f)= Cod 2(G a f)和baves-idGA∈Ob 1. Ga(Id 1A)=Id 2(G oA)和无菌-compGf ∈Ar 1。 n ∈Ar 1。 Cod 1 f = Dom 1 g −→ G a(g·1 f)=(G a g)·2(G a f)在下一个引理中使用的locale函子添加了一个结构F,并断言了它的这些属性。下面是一个简单结果的例子及其证明。一些断言被赋予数字作为名称,以便稍后可以引用它们。为了证明我们有一个homset元素,我们必须证明它是一个箭头,并且有正确的域和上域。lemma(infunctor)functors-preserve-homsets:假设1:A∈Ob1和2:B∈Ob1和3:f∈Hom1AB表示Faf∈Hom 2(F oA)(F oB)222G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-证明-从3有4:f∈Arby(simp add:hom-def)withF-preserves-arrowshave5:Faf∈Ar2by(rule funcset-functions)从4和F-保留-dom有Dom2(F af)=F o(Dom 1f)通过(simp add:sample-dom-def)也从3有…=FoA通过(simp add:hom-def)最后有6:Dom2(Faf)= FoA。从4和F-保留-代码有Cod2(F af)=F o(Cod 1f)通过(simp add:sample-cod-def)也从3有…=FoB通过(simp add:hom-def)最后有7:代码2(F a f)= F o B。从5到6再到7表演?论文通过(simp add:hom-def)QED为了检查我们是否定义了我们认为我们已经定义的东西,谨慎的做法是为每个概念构造一个明显的实例,并证明它是一个实例。我们表明,对包含对象和箭头单位函数是一个函子。我们定义一个函数,它为我们提供了一个给定类别的这个对,以及一个用来证明我们的结果的区域。常量定义10. C++()++())+(|om =(λA∈obC. A),am =(λf∈arC. f)的|)localeone-cat=two-cats+假设endo:B=ffi经过几个引理,我们能够表明,theorem(inone-cat)id-func-functor:函子(id-funcffi):ffi −→ffi同样,我们回收了two-cats locale,将第二个类别设置为集合的类别,其类型是第一个类别的箭头。定义了Homfunctors,我们使用通常的符号Hom(A,-)。请注意,括号是这种表示法的重要组成部分。Homsets是写的没有括号,因为它们是应用于curry函数的。localeinto-set=两个猫+假设ffi=(ffi::(Jo,Ja,Jm)category-scheme)修复U和SetdefinesU定义(UNIV::Jaset)定义Set定义set-cat U假设B-Set:B=Setfixeshomf::Jo(|om::Jo(Ja set),am::Ja(Ja set-arrow)|)(Hom J(-,j-j))2、A、B、C、D、E、F(|om =(λB∈Ob. Hom A B),am=(λf∈Ar. (一)|set-dom = HomA(Dom f),set-func =(λg∈Hom A(Dom f). f·g),G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-223OBset-cod= Hom A(Cod f)|))|)目的是证明homfunctors是函子。以下是所需的引理。引理(在into-set中)homf-preserves-dom:假设f ∈Ar显示Hom(A,-)o(Dom f)=dom Set(Hom(A,-)af)证明-有Dom f ∈ Ob..因此1:Hom(A,-)o(Dom f)=Hom A(Dom f)(Simp!添加:homf-def)有2:dom Set(Hom(A,-)af)=Hom A(Dom f)(Simp!添加:homf-def)从1和2显示?Simp的文章QED最终,我们可以证明theorem(ininto-set)homf-into-set:函子Hom(A,-):ffi −→Set我们定义了自然变换,给出了它们的一个合理的符号,并证明了一个范畴的单位矢函数,当限制到该范畴的对象时,是从单位函子到它自身的一个自然变换。NatTrans=函数:localenatural-transformation=two-cats+var F+var G+var u+假设函子F:ffi−→B和函子G:ffi−→B和u:obffi→arB且u∈extensional(obffi)且n ∈A∈Ob。u A∈Hom 2(F o A)(G o A)且n ∈A∈Ob。B∈Ob。f∈Hom A B. (Gaf)·2(u A)=(u B)·2(Faf)最后一行断言下图中的F AuA G Ao oFafJGAFJFo BuGB自然变换区域给了我们一个谓词,它的论元是两个范畴,它们之间的两个平行函子和自然变换。而不是使用默认语法自然变换ffi BF G u224G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-())())我们已经定义了更熟悉的形式u:FGinFunc(ffi,B)请注意,表达式的Func(ffi,B)部分并不真正表示函子范畴。此表示法用于声明定理(在endoNT中)id-restrict-natural:(λA∈Ob. Id A):(id-func ffi)在Func(ffi,ffi)中调用(id-func ffi)我们将locale组合起来,得到一个具有任意类别的环境,对应的集合类别,以及它们之间的函子。在这里,我们定义了再次,我们帮助自己的符号糖。localeYoneda=functor+into-set+假设ffi=(ffi::(Jo,Ja,Jm)category-scheme)固定三明治::[Jo,Ja,Jo]Ja集合箭头(σ J-,-J定义三明治Aa(λB∈Ob. (一)|set-dom=HomA B,set-func =(λf∈Hom A B. set-func(Faf)a),set-cod = Fo B|))修复unsandwich::[Jo,JoJa set-arrow]Ja(σ←J-, -J定义了unsandwich A u函数set-func(u A)(Id A)有必要证明三明治产生自然变换,因此需要以下几个结果。lemma(inYoneda)假设A∈Oba∈FoA显示σ(A, a):Ob→ar集合然后我们得到引理(米田)natural:假设A∈Oba∈FoA显示函数(ffi,Set)中的σ(A, a):Hom(A,-)<$F我们证明了这两个函数是逆函数引理(米田)uncall-left-inverse:假设1:A∈Ob和2:a∈FoA显示σ←(A,σ(A, a))=a引理(米田)uncall-right-inverse:假设1:A∈Ob和2:u:Hom(A,-)F在Func(ffi,Set)中显示σ(A,σ←(A, u))=u现在我们有了证明我们目标所需的结果,但陈述它需要G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-225一些小的定义。为了陈述这个引理,我们必须纠正Isabelle/HOL库中一个奇怪的遗漏。它定义了给定集合上的内射性,但满射性只是相对于目标类型的整个宇宙常量定义surj-on::[Ja<$Jb,Ja set,Jb set]在f A B上的布尔surj-on <$bool y ∈B。 x ∈A。 f(x)= y bij-on::[JaJb,Ja set,Jbset]boolbij-on f AB inj-onf A&surj-on f A Bequinumerous::[Jaset,Jbset]bool(infix=40)equinumerous ABf.bij-on f A BMacLane [16,第61页]将引理陈述如下引理3.1(Yoneda)如果K:DSet是D的函子,r是 D中的对象(对于 D是具有小hom-sets的范畴),则存在双射y:Nat(D(r,),K)n=Kr米田可能称他的结果为引理,但在这么多不合理的命题之后,似乎有必要进行升级定理(米田)米田:假设1:A∈ObshowsFoA={u. u:Hom(A,-)nFinFunc(ffi,Set)}apply(unfold equinumerous-def bij-on-def surj-on-def inj-on-def)apply(intro exI conjI bexI ballI impl)证明-- 三明治是内射的固定x和y假设2:x∈FoA和3:y∈FoA和4:σ(A, x)=σ(A, y)因此σ←(A,σ(A, x))=σ←(A,σ(A, y))通过simp具有非左逆显示x=y通过(simp add:1 2 3)下- 夹层盖F A修复使用假设u∈ {y. y:Hom(A,-){F in Func(ffi,Set)}因此2:u:Hom(A,-)F在Func(ffi,Set)中通过simp其中1表示σ(A,σ←(A, u))=uby(rule untransmitted-right-inverse)- 三明治变成了F A选自1和2haveu A∈hom Set(Hom A A)(FoA)by(simp add:natural-transformation-def natural-transformation-axioms-def homf-def)因此u A∈ar集,dom集(uA)=HomA A,cod集(uA)=FoA通过(simp-all add:hom-def)因此,uAfuncset:set-func(u A):(Hom A A)→(FoA)通过(简单添加:Set-def set-cat-def set-arrow-def)有Id A ∈ Hom A A ..关于uAfuncsetshowσ←(A, u)∈FoA226G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-by(simp add:unauthor-def, rule funcset-def)QED端4结论与非正式的教科书证明相比,我们所展示的Isar证明是繁琐的。大部分推理都是为了证明者的利益,而不是读者。通过更熟练地应用现有的自动化,可能会获得更好的结果。仔细研究其他形式化,或许可以吸取一些教训。不过,我们的目标不是让所有事情都自动化,只是我们希望人类读者自己完成的步骤。形式语言仍然是一个负担,尽管ISAR,语言环境和语法扩展的改进。特别是,我们希望重复使用或“超载”词汇不同但类似的概念。例如,在这里没有介绍的形式化部分中,定义了子类别的明显的符号是ffiB,但这导致语句被误解。同样,我们使用·符号,而不是通常的箭头复合,因为后者被定义为函数复合。我们计划研究实现所需重载的方法,因为它对通常的数学表示似乎是必不可少的通过改进的自动化实现更高密度的打样最后,为了解决低生产率的问题,我们计划建立一个纪律严明的过程,生产形式化,并系统地改善它。尽管存在我们已经注意到的缺点,Isar的证明语言,场所和Isabelle的灵活语法已经使形式化的数学更接近于非专业人士。感 谢 MichaelNorrish 、 RajGor're 、 JeremyDawson 、 AmnonNeeman 、Marieke Huisman、Tjark Weber、Lockwood Morris和Roy Dyckho提供线索和有用的电子邮件。也感谢裁判的深刻见解。引用[1] Cornell Prl自动推理项目。http://www.cs.cornell.edu/Info/Projects/NuPrl的网站。[2] 乐高主页,1999年。http://www.dcs.ed.ac.uk/home/lego网站。[3] 彼得·阿采尔。伽罗瓦:一个理论发展项目。技术报告,曼彻斯特大学,1993年http://www.cs.man.ac.uk/Applpetera/papers.html。G. O'Keefe / Electronic Notes in Theoretical Computer Science 91(2004)212-227[4] Altucher,J. A. P. Panangeli,范畴论中的一个机械辅助构造性证明。在CADE-10中,人工智能讲义中的第449Springer,1990年。[5] Mizar用户协会。 Mizar主页。http://www.mizar.org网站。[6] Barr,Michael & Charles Wells,Category Theory for Computing Science. Prentice-Hall,1990年。[7] Bertot,Y. 、白藓G. Dowek,A.Hirschowitz,C. 帕林和L。他们,编辑们,《高阶逻辑的证明》,计算机科学讲义第1690卷,http://link.springer.de/link/service/series/0558/tocs/t1690.htm,1999年9月。斯普林格。[8] Carval h o,A. ,CategorytheheoryinCoq. Techn icalreport,Instit u toS u periorT′ecn ico,1049-001Lisboa,Portugal,1998.http://www.cs.math.ist.utl.pt/ftp/pub/CarvalhoA/+README.html网站。[9] Dyckh o no n o f Martin L?o f t y p e h oRy,Categorytheoryanexten o nofMartinL?oftypeh o ry. 美国圣路易斯大学计算机科学系教授。安德鲁斯1985年[10] 闪闪发光, 约翰,逻辑和自动化 for algebra代数of programming编程.牛津大学硕士论文,2001年。http://www.nada.kth.se/taggliming/publications.shtml。[11] 戈根,约瑟夫, OBJ家族http://www.cs.ucsd.edu/users/goguen/sys/obj.html网站。[12] 哈里森,约翰,形式化数学。技术报告36,图尔库输入科学中心(TUCS),L emm inkéaisenkatu14A,FIN-20520Turku,Finland,1996年。http://www.cl.cam.ac.uk/users/jrh/papers/form-math3.html的网站。[13] Harrison,John,A mizar mode for HOL.在Theorem Proving in Higher Order Logics中,计算机科学讲义第1125卷。Springer,1996年。[14] INRIA。Coq证明助手http://coq.inria.fr网站。[15] Kammüller,Florrien,MarkusWenz eland d Lawr en ceC. PAULSON,LOCALS:ASECTIONINGCONCPT for Isabelle.《高阶逻辑中的定理证明》,1999年。[7]的文件。[16] MacLane,Saunders,Categories for the Working Mathematician. 数学研究生教材第五名。Springer,第2版,1971年,1998年。[17] Mohri,Takahisa,论范畴理论的形式化。东京大学硕士http://www-unix.mcs.anl.gov/qed/mail-archive/volume-3/0134.html网站。[18] Morris,Lockwood等人,HOL中类别表示的临时部分描述lockwood@top.cis.cyr.edu,1998年6月[19] 内德佩尔特河P.,J. H. Geuvers和R. C. de Vrijer,editors,Select
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)