集合范畴内函子的性质及最终余代数

理论计算机科学电子笔记104（2004）61-80www.elsevier.com/locate/entcs集合函子的性质*Daniela Cancila1 Furio Honsell2 Marina Lenisa3，4DipartimentodiMatematiceInformatica，Universit`adiUdine， Viadelle Scienze 206，33100 Udine，ITALY.电话+39 0432 558417，传真：+39 0432 558499摘要我们证明了类论范畴上的任何内函子都有最终余代数。此外，我们刻画了函子的集合论范畴是相同的对象，和函子的对象是常数。关键词：集合范畴，部分定义的内函子，单位函子，常数函子，最终余代数。介绍近年来，集合论范畴，即对象是可能的非良基论域的集合（类），态射是集合（类）论函数的范畴，已被用作研究共归纳的共代数方法的基础的方便设置，见[1，2，6][7，8，10，18，19，17]。然而，在范畴理论家和集合理论家中，集合论范畴由于对立的意识形态动机而没有得到太多的关注。*研究部分得到MIUR项目COFIN 2001013518COMETA的支持。这项工作已在2003年4月30日至5月4日在都灵举行的类型会议上提出1电子邮件：sales@dimi.com 联合国。I T。2电子邮件：honsell@dimi。联合国。I T。3电子邮件：lenisa@dimi. uni ud. IT。4通讯作者。1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2004.08.01962D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-80在本文中，我们解决三个问题的结构结束函子在集理论范畴。第一个问题涉及具有最终余代数的集合论函子类。我们表明，所有类理论的endofunctors，即。一个范畴的内函子，其对象是类，其态射是函数类，有最终余代数。这加强了Aczel，Adamek等人[1，3，4]在非良基集合论中的早期结果，见[11]。后两个问题是基本的和关注的约束可能会出现从对象部分的函子到态射部分，因为特殊性质的集合。特别是(i) 函子对对象不变对态射不变吗？(ii) 函子在对象上全同在态射上全同吗？我们彻底地解决了这些问题，这些问题起源于麦克莱恩的基本书，[15]。特别是，我们表明：• 集合论范畴C上具有常基数<对象上的超级卡C自然同构于常数函子，其中超级卡C是C• 上面的结果不能推广到函子，函子在对象上与基数最大卡C的对象恒定相等;• 在一个范畴上的函子F是关于对象的单位，它自然同构于单位函子;• 然而，上述结果在集合论范畴对无限对象的限制上失败了。本文的初步版本见[9]的第3章。总结在第一节中，我们回顾了有关集合论和集合论范畴的一些定义和基本事实。特别地，我们回顾了基于集合的函子和包含保持函子的定义，以及Aczel-Mendler最终余代数定理。在第二节中，我们研究了包含保持函子的一些性质，这将有助于证明本文的主要结果。在第三节中，我们通过证明所有的类论函子都允许最终余代数来加强Aczel-Mendler定理。在第4节中，我们研究了集合论范畴上的两类部分特定的内函子：在对象上为常数的函子和在对象上为恒等的函子。未来工作的方向见第5节。D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-8063→记法。在本文中，只要不可能产生误解，我们就省略括号。此外，我们使用以下符号。设f：A→B是集合（或类）上的任意函数，且设AJ<$A，则：• gr（f）表示f的图;• imgf表示f的图像;• fAJ：AJB表示通过将f的域限制到AJ而从f1预赛1.1集合论在本文中，我们将经常提到大对象，例如真类，甚至非常大的对象，例如对象是类的范畴上的函子。一个基本的形式理论，可以容纳自然我们所有的论点是不容易获得的。 需要一个实质性的形式主义的解释来正确地“跨越我们所有的t”。因此，我们将采取务实的态度，并自由地假设我们手头有类和类上的函子。关于一致性的担忧可以通过假设我们的环境理论是一个具有不可达基数κ的集合理论来消除，并且我们的对象理论的模型由那些遗传基数小于κ的集合组成，比如说，我们的模型的类是Vκ的子集，并且函子生活在环境宇宙的适当行列1.2分类目录我们定义一个集合论范畴如下：定义1.1集合论范畴是一个自然同构于卡的初始段（CARD）的范畴。集合论范畴的典型例子如下，其中U是 一个集合的Urelementen：• 设置（U）（设置（U））：对象：属于（非良基）宇宙的集合，态射：集合论全函数。• F插入（U）（F插入（U））：[001 pdf1st-31 files]有限集合的集合（U）（集合）的子范畴。• C级（U）（C级（U））：64D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-80HCHCC对象：（非良基）集合类，态射：函数类。•（1）A（κ（U））：物件： （非良基）集，其遗传基数为<κ，κinac-可分割的，态射：集合论函数。• 卡（CARD）：对象：基数（包括Ord），态射：集合论函数。在本文中，我们将始终假设集合论函子F：C →C，其中C是一般集合论范畴，满足性质F（f） =，并且对于所有f：→A，F（f） =。这个假设并不特别重要，因为我们有以下内容：命题1.2对每一个集合论函子F：C → C，存在一个函子G：C → C使得对A/=A，F（A）= G（A），对所有的f：A → B，F（f）=G（f），且当G（A）=A时，dG（f）=A.证据我们可以很容易地检验出，如果F是一个函子，那么G也是一个函子，因为不存在函数f：A→ A，除非A是空的，并且只有函数f：A →A是空的。Q以下是一个众所周知的事实，这将在下文中有所帮助引理1.3设F：C → C。然后i) 若f：A→B是内射，则F（f）：F（A）→F（B）是内射;ii) 若f：A → B是满射，则F（f）：F（A）→ F（B）是满射。现在我们回想一下集合论函子的一些定义。在文献中，后者最初只针对定义在C类或C类X上的函子给出。然而，它们可以为任何集合范畴进行适当的修改。定义1.4（[1，2]）设F：C类→ C类是函子。• F是包含保持的，如果A，B. A <$B =<$（F（A）<$F（B）<$F（i A，B）= i F（A），F（B）），其中ιA，B：A→B是从A到B的包含映射。• F是基于集合的，如果对于每个类A和每个x∈F（A），存在一个集合a0<$A和x0∈F（a0）使得x=F（ia0，A）（x0）.在1989年，Aczel和Mendler证明了任何基于集合的函子都有最终余代数。D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-8065C →C|imgf定理1.5（最终余代数定理，[2]）C类代数上的每一个基于集合的函子都有最终余代数。上述定理对任何类论函子都成立。在第三节中，我们将证明Aczel-Mendler2包含保持函子在本节中，我们研究包含保持函子的性质。特别是，我们表明，• 函子是包含保持的当且仅当它关于态射的值仅依赖于态射的图;• 集合论范畴上的任何函子自然同构于包含保持函子。在这一节中，让C在一个一般的集合论范畴上变化。我们从一个简单的引理开始，它说包含保持函子保持函数的图像：引理2.1设F：C → C是包含保持函子。然后，F（img f）= img F（f）。证据 设f：A → B。则F（f）：F（A）→F（B）。 但F（f）= F（ιimgf，B<$f|imgf）= I F（imgf），FB<$F（f|imgf），因为F是包含保持的。因 此 ，img F（f）=img F（f|imgf）=F（imgf），因为f|imgf是满射的，根据引理1.3，F保持满射函数。Q提议2.2令F： 则F是包含保持的当且仅当它在任何态射上的值仅取决于态射的图而不取决于目标，即对于所有A，B和对于所有f：A →B，FJ：A →BJ，gr（f）= gr（fJ）<$gr（F（f））= gr（F（fJ））.证据设f：A→B，FJ：A→BJ使得gr（f）=gr（FJ）.则img（f）=img（fJ），因此f =fJ|imgf J，f=Iimg f，Bf|imgf，且fJ=|img f，BJ|F|imgf. 因此，由于F是包含保持的，因此F（f）= I F（imgf），FB<$F（f|imgf）和F（fJ）= iF（img f），F BJ<$F（f|imgf），即gr（F（f））=gr（F（fJ））。设A=B。然后gr（iA，B）=gr（idA），因此gr（F（iA，B））=gr（F（idA））=gr（idFA）。因此，F（A）<$F（B）和gr（F（iA，B））=gr（iFA，FB），因此F（iA，B）=iFA，FB。Q66D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-80C → C C → C一一一简单地说，不是每个函子都是包含保持的。只要考虑通过将给定类上的值同构映射到与子类上的函子的值不相交的类中而获得的任何函子。然而，在下一个命题中，我们证明了任何函子都自然同构于包含保持函子。提议2.3令F： 则存在G：包含保持使得G自然同构于F.证据 设G：C→C为函子，定义为：对于所有A，G（A）=F^（iA，V）（FA），和f或所有f：A→B，G（f）=G（A）→G（B），G（f）：F（μB，V）|imgF（iB、V）<$F（f）<$（F（ιA，V）|imgF（iA、V））−1.• 我们证明G是有定义的。根据定义，G保持恒等式。现在我们证明G保持合成。设f：A→B和g：B→C，G（g f）= F（i C，V）|imgF（iC、V）<$F（g <$f）<$（F（ι A，V）|imgF（iA、V））−1=F（μC，V）|imgF（iC、V）<$F（g）<$F（f）<$（F（ι A，V）|imgF（iA、V））−1=F（μC，V）|imgF（iC、V）<$F（g）<$（F（iB，V）|imgF（iB、V））−1◦F（μB，V）|imgF（i=G（g）<$G（f）B、V）<$F（f）<$（F（ιA，V）|imgF（iA、V））−1• 证明了函子G与F自然同构。 设τ={τA：GA→F A}A是双射函数族，定义为：（F（ιA，V）|imgF（iA、V））−1. 我们证明了τ是一个自然同构。令f：A→B. 我们证明了τB<$G（f）<$τ−1=F（f）。通过在Gf上替换，τ B<$G（f）<$τ −1= τ B<$F（ι B，V）|imgF（iB、V）<$F（f）<$（F（ιA，V）|imgF（iA、V））−1<$τ−1=F（f）通过定义τA，τB• 这需要证明G是包含保持的，即G（ιA，B）=ιGA，GB。设A<$B且设ιA，B：A→B。然后，G（i A，B）=（F（i B，V）<$F（i A，B）<$（F（i A，V）|imgF（iA、V））−1）|imgF（iB、V）D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-8067=（F（IB，V）IA，B）I（F（IA，V）|imgF（iA、V））−1）|imgF（iB、V）=（F（iA，V））（F（iA，V））|imgF（i=IGA，GBA、V））−1）|imgF（iB、V）Q推论2.4每个基于集合的函子F自然同构于标准函子.68D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-80C5→ ∈∈3加强最终余代数定理为了简单起见，在本节中，我们在满足公理N的宇宙中工作，也就是说，所有真类都与Ord一一对应。在下文中，我们将这一假设称为在此假设下，我们证明了每个包含保持函子都是基于集合的强结果。因此，利用文[2]的最终余代数定理，我们可以导出每个包含保持函子都有最终余代数。 通过第2节的命题2.3，利用具有最终余代数的性质是如果在同构下不成立，我们可以证明一个非常强的最终余代数定理，确保C上的所有函子都允许最终余代数。在这一节中，我们让范围覆盖一个类论范畴，除非有不同的说明。我们首先证明一些有用的结果。Lemma 3.1设F：C → C是包含保持的.如果存在这样的的{F（a）|a∈ A<$a set}<$F（A），则对于所有B，我们有{F（b）|b∈ B<$b集}<$F（B）.证据我们从矛盾出发。我们假设A是一个类，使得{F（a）|a∈A <$aset}<$F（A）而B是一个类，使得{F（b）| b ∈ B ∧ b set} = F (B). 根据笼统的假设，双射函数σ：B→A。则对所有x∈F（A），由于F保持同构，存在y ∈F（B）使得x = F（σ）（y）. 而且由于{F（b）|b∈B<$bset} =F（B），存在一个集合b<$B，使得y∈F（b）.但则x∈imgF（σ）|FB.现在，我们可以很容易地检查，因为F是包含保持的，所以F（σ|b）= F（σ）|FB.因此x∈imgF（σ|b），即，由引理2.1，x∈F（imgσ|b），和imgσ|b是A的子集。矛盾 Q定义3.2设F：C → C是函子，A是真类。然后x∈F（A）不可达，如果x/∈{F（a）|a∈ A<$aset}.引理3.3设F是包含保持的。如果x ∈ F（A）是不可达的，则不存在f：a →A，对于一个集合a，使得x ∈ img F（f）.证据我们从矛盾出发。 设对集合a，存在函数f：a→A使得x∈img F（f），设a0=img（f），则由引理2.2，F（f）|imgF （f）：F（a）F（a0）但如果x F（f），则x F（a0），这与x不可达的假设相矛盾。 Q在下面的引理3.4中，我们利用V同构于订单 如果我们考虑二叉树的分支的高度为Ord，那么我们得到5这个符号表示严格包含。D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-8069联系我们∩∩⎨α◦◦2Ord内射函数，其定义域为Ord且在非空集上两两重合因此，我们有：引理3.4i）存在2阶内射函数f α：V→V使得img（f α）是真类，且对所有α=β，img（f α）img（f β）是非空集.ii）存在2个Ord真类{A}α使得α ≤ 2 Ord且A α<$A β是非空集，对所有α/= β.命题3.5设F：C → C是一个包含保持函子，使得如果A B是一个集合，则F（A）F（B）包含在一个集合的象中。然后，F被设置为基于。证据 我们从矛盾出发。 我们假设F不是基于集合的。根据引理3.4。ii.存在2个Ord真类Aα使得Aα<$Aβ是一个集合，对所有α/=β。根据引理3.1，对于每个类Aα，存在一个不可达的元素xα∈Aα。但由于对所有α，β，Aα<$Aβ是一个集合，则xα/∈Aα<$Aβ，对所有α β，否则，xα将不是不可达的，通过使用F（Aα）<$F（Aβ）的事实，是一套假设。因此，存在2个Ord不同的不可达元素。这与以下事实相矛盾：|V|=订单。Q现在我们可以证明下面的关键结果。命题3.6设F：C → C是包含保持函子，因此是基于集合的。证据我们从矛盾出发。 我们假设F包含保持，F不是基于。根据引理3.4。i，存在2个阶内射函数fα：V→V，使得imgfα是一个真类，img（fα）∈img（fβ）是一个集合，对所有α定义2阶函数gα：V→V，使得(a) img（gα<$fα）是一个真类，(b) img（g α<$f β）是一个集合，对所有α/= β。设gα：V→V定义为：β。 现在我们g（x）=nx， 如果x∈imgfα很抱歉，否则。由（b）和引理2.1，我们得到F（img（gα fβ））=imgF（gα fβ）doesn’t contain any70D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-80◦νGνGνG... ..，τνGνGνGνG利 用 （ a ） 和 引 理 2.1 ， 我 们 得 到 F （ img （ gα<$fα ） ） =imgF（gα<$fα）.此外，根据引理3.1，imgF（gα<$fα）包含不可达的。因此，对于所有α，存在x α∈imgF（f α），其由F（g α）的像，在后继注dbyx<$α中，是一个不确定性。 M或eover，xα/∈imgF（fβ）f或所有β/=α，因为x α应该在集合img（g αf β）的像中。因此，我们认为，存在2个Ord不同的不可达元素。 这与以下事实相矛盾：|=订单。|= Ord.Q利用命题3.6，我们得到了如下结果，它推广了最终余代数定理[2]。推论3.7任何保包含函子都有最终余代数。下面是一个简单但有用的命题，它允许我们反映函子对之间的最终余代数的性质，并导出本节的主要结果。命题3.8设C是一个集合论范畴，设F，G：C −→ C，令τ：F−→·G是一种全变换。If（νG，ανG）是最终的G-co代数a，且τ νG是一个双射，则（νG，τ −1<$α νG）是一个最终F-余代数.证据 为了简洁起见，我们用αJ由τ−1<$ανG给出的函数，如下图所示。FXνGβX。.. .αJ。. . .. . ..，c（一）vG. .，c.F（X）、F（f）、、F（νG）、、、，νGανGτX，（二）、、、z，zctG（X）G（νG）G（f）设（X，βX）是F-余代数. 我们首先证明了存在一个F-余代数从（X，βX）到（νG，αJ）的态射）的。由于（X，τX<$βX）是G-余代数νG和（νG，ανG：νG→G（νG））是最终余代数，则唯一函数f：X→（νG）存在使得ανG<$f=G（f）<$τX<$βX（f）.由于τX是一个自然变换，G（f）<$τX=τν（G）<$F（f）。通过代入，方程（*）变为：α νG<$f = τ ν（G）<$F（f）<$β X。因为τ νG是双射的，所以函数τ −1存在。 因此，τ −1<$α νG<$f =τ−1 <$τ νG<$F（f）<$β X，即 τ −1<$α νG<$f = F（f）<$β X，因此f是F-余代数从（X，βX）到（νG，αJ）的态射），即存在（νG，τ −1 <$α νG）νG νG余代数、D. Cancila等/ Electronic Notes in Theoretical Computer Science 104（2004）61-8071νGCνG¯¯νGνGνGνGνG现在我们通过矛盾假设存在另一个F-余代数态射fJ：（X，βX）→（νG，αJ）的。那 么 ，F（f J））由于τ是自然变换，G（fJ）<$τX=τνG<$F（fJ）。通过τ的双射性，我们有（τ−1<$G（fJ））<$τX=（τ−1<$τνG）<$F（fJ），即（τ−1<$G（fJ））<$τX=F（fJ）. 通过在（*）中代入F（fJ），（τ −1<$G（f J））<$τ X<$β X=（τ −1<$α νG）<$f J，即 G（f J）<$τ X<$β X= α νG<$fJ，它与最终G-余代数（νG，α νG）相矛盾.Q最后，通过命题3.8和3.6，我们得到了以下强结果。定理3.9设F是类论范畴上的闭函子。然后F有最终余代数。显然，上述定理在一般的集合论范畴中不成立例如，它不适用于Set中的幂集函子。4函子部分由它们在对象上的值在这一节中，我们研究了集合论范畴中的两种特殊函子：作为对象上的常数的函子和作为对象上的恒等式的函子。首先证明了如果F是一个在对象上具有常数基数

下载后可阅读完整内容，剩余1页未读，立即下载