没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记106(2004)279-295www.elsevier.com/locate/entcs由满足理论构造的Harsanyi型空间和最终余代数Lawrence S.Moss1马西莫D. 维利佐2印第安纳大学数学系Bloomington,IN47405USA摘要本文将余代数与博弈论基础中关于型空间建模的长期讨论联系起来。我们认为类型空间是余代数,泛类型空间是最终余代数,并且在经济理论文献中已经提出的模态逻辑与最近在余代数模态逻辑中的工作密切相关。在另一个方向上,这项工作中感兴趣的范畴通常是可测空间或紧(Hausdor)拓扑空间。Heifetz和Samet [5]的泛型空间的构造的一个余代数版本被推广到这些范畴中的一些函子。由于在余代数文献中对兴趣的具体范畴还没有进行过深入的研究,我们得到了一些新的结果。我们证明了由常数函子、积、余积和概率测度空间函子构成的可测空间范畴上的每个函子都有一个最终余代数。 此外,委员会认为, 我们从相关版本的余代数模态逻辑构造这个最终余代数。 具体地说,我们考虑了所有余代数中的点的理论集合,并赋予这个集合一个可测的余代数结构。关键词:余代数,最终余代数,哈桑尼型空间,可测空间,概率,信念。1简介:类型空间本文是第一次探索应用的想法和结果从余代数的基本领域的博弈论有关的类型空间。类型空间是在建模设置中使用的数学结构,其中代理由其类型描述,并且这些类型给我们1电子邮件地址:lsm@cs.indiana.edu2电子邮件地址:igvigliz@indiana.edu1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2004.02.036280L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279∈×世界1994年诺贝尔经济学奖授予了约翰·C.约翰?海萨尼小纳什,和莱因哈德·塞尔滕“对非合作博弈理论中的均衡进行了开创性的分析”。除了他的工作平衡,海萨尼也将记住他介绍的类型空间在一个三部分的文件发表于1967年和1968年[4]。他展示了如何将一个信息不完全的博弈转化为一个信息完全但不完美的博弈。这一问题与我们的文件无关,但有三点值得注意。首先,海萨尼第二,尽管有这种循环,类型的非正式概念(作为一个最后,类型空间的形式化过去是,在某种程度上现在仍然是一个开放的领域。也就是说,海萨尼在他的原始论文中并没有真正形式化类型空间;这是留给后来的研究者的。回到我们上面非常粗略的非正式描述,到底什么是“信念”?一个结构如何能包含引起对其他类型的信念的类型呢? 这与关于世界的信念的无限等级的信念有什么关系?我们能刻画所有可能类型的空间吗?因此,有一个收集的文件对他的材料,开始与博格和埃塞勒的文件[ 2 ]从1979年同样,我们在本文中不太关心这些概念问题。我们研究的大多数重要论文都是关于泛型空间的技术贡献。通用类型空间旨在捕获所有可能的类型,因此它是对上面第三个问题的回答。有一些明确的概念线索表明余代数可以与类型空间相联系。首先,博弈论文献中的“信念”概念通常是概率性的。如果我们把上面的“信念”替换可能世界语义的数学结构是具有两个函数的世界的集合W,每个函数给出世界W一些“原子命题”在w处为真,而另一个对于每个w给出一组所谓“从w可能“的世界这些结构本质上是函子F(W)=AP(W)的集合的集合范畴中的余代数,其中A是原子命题集合的幂集,P是集合上的幂集函子。 也许主要的L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279281到目前为止,余代数对这一领域的贡献是表明模态逻辑,结构的自然逻辑语言,推广到模态逻辑的余代数。我们第二条线索与泛类型空间在这个领域中的作用有关。类型被认为是通用类型空间的元素。在泛类型空间中,所有可能的类型都被唯一地表示,其思想是,两种类型对“自然”的底层世界以及其他参与者的类型具有完全相同的信念,这两种类型被认为是不可区分的。这与我们发现的关于最终余代数的思想相同,在最终余代数中(众所周知)具有相同行为的点被识别。回到类型空间,我们记得在博弈论中信念的通常建模是通过概率。所以我们可以预期类型空间应该是Kripke模型的概率版本。我们应该用类似于的东西来代替函子P,其中(W)={µ|是W上的概率测度}。(一个)事实上,情况确实如此:文献中的大多数建议最终都研究了从空间X到应用于X的函子的某种变体的某些映射。这是第三条线索 但请注意,(1)留下了一个如果W只是一个集合,我们怎么知道它有任何概率测度?我们用哪种σ-代数有关系吗?如果W是另一个范畴中的对象,比如可测空间或紧度量空间,那么我们给(W)加上什么结构呢?我们打算这篇论文是一个贡献,这一领域的连接它与余代数。以下是该论文的主要概念主张以及主要结果:*哈桑尼型空间的原始概念可以被认为是函子F在MeasI上的一个coal- gebra,其中Meas是可测空间和可测映射的范畴,而I是一个离散的(主体的)范畴。但这种重新表述并不明显,因为最初的概念有一个额外的条件,即行动者“知道他们自己的类型”。我们将在第2节讨论这一点。* 泛型空间是最终余代数。*文献中泛型空间的构造与余代数中的构造有关。然而,有分歧,主要是由于这样一个事实,即工作正在进行的类别,如Meas,而不是集。通过不同的方法,可以推广泛型空间的构造,这是余代数中的一个有趣的问题。* 对于相关的函子,有不同版本的共代数模态逻辑,282L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279××B→ ∈∈→{∈ ∈}→人们可以通过考虑这些逻辑中的满意理论来证明最终余代数的存在性。这种构造类似于利用所有可能世界的所有模态理论的描述集构造集合上的最终余代数,其中F(W)=AP(W)(或者更确切地说,APfin(W在Kurz [9]和R?oßig er[11,12,13]的工作基础上,我们在Jacobs [ 7 ]的基础上建立了一个余代数模态逻辑公式. 但是,从这些经验中得出的两个结论是,我们的最终余代数与逻辑理论无关,而是与在余代数中实现的理论有关。在经济学文献中,这种结构是由于海菲兹和萨米特[5]。*我们制定了一个概念的我们在第3节中证明了一个新的结果:每个这样的多项式都有一个最终余代数,其载体由特定语言的句子集组成。该方法也适用于集合上的多项式函子,如我们在5.2节中所示。1.1背景概念一个可测空间是一个对M=(M,n),其中M是一个集合,n是M的子集的σ-代数。这些集合被称为可测集合或事件。通常,M包含所有单元素{x};我们几乎总是假设一个较弱的条件,即对于每个x∈M,{x}是M中包含x的可测子集的交集。M的子集的集合生成一个σ-代数<$如果<$是包含B的最小σ-代数。M上的测度是σ-可加函数µ:μ→ [0,∞]。如果µ(M)= 1,则测度µ是概率测度可测空间f:(M,n)的一个态射 (N,<$J)是一个函数f:M N使得对于每个A <$J,f−1(A) - 是的 这给出了一个类别Meas。Meas有乘积和副乘积;实际上它有更多的结构。有一个内函子:Meas Meas定义为:(M)是M上的概率测度集,σ-代数由βp(E)生成:p[0, 1], E,哪里βp(E)={µ ∈ φ(M)|µ(E)≥ p}。下面是正则表达式如何作用于态射。如果f:M→N是可测的,则对于µ∈N(M)和A∈NJ,(N)(µ)(A)=µ(f−1(A))。也就是说,(f)(µ)=μf−1。我们还注意到一些额外的结构。首先,有一个自然的转换-式δ:Id→d_e_f由δM(m)(E) = 1ifm∈E和0如果m∈/E.我们也用δm代替δM(m);这是在m处支持的狄拉克测度。其次,存在由下式给出的自然变换γ:γ→ γ引理1.1(Giry [3])(θ,δ,γ)是单子。γM(µ)(E)=ν∈π(M)ν(E)dµ.L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279283∈−∫∫×一B一引理1.2对于每个p [0,1],βp可以被认为是“谓词提升”。也就是说,βp将每个空间M的可测子集取为f(M)的可测子集,这在以下意义上是自然的:如果f:M→N,则对所有可测E<$Y,βp(f−1(E))=(f <$f)−1(βp(E))。引理1.3假设集合B生成n。则M上的σ-代数是由形式{βp(E)|E∈B且p∈ [0,1]}。我们还需要从测度论中得到一个关于概率测度从集合到它们所生成的σ-代数的推广的结果。下面的引理1.4 更多详情,参见例如Billingsley [1],第36页。引理1.4设µ1和µ2是σ(ffi)上的概率测度,其中ffi是交闭集族,σ(ffi)是由ffi生成的σ-代数。 如果µ1和µ2在ffi上一致,那么它们在σ(ffi)上一致。我们还需要在某个时候更仔细地研究Meas中的产品。给定两个可测空间A和B,它们的乘积是集合A和B的卡丁车乘积,赋予由作为A的可测子集乘以B的可测子集的卡丁车乘积获得的“矩形”生成的σ-代数有了这个σ-代数,两个投影都是可测的。对于一个子集E<$A×B,E的截面是集合:Ea={b:<$a,b<$∈E},Eb={a:a,b<$∈E}.产品的可测量子集的每个部分都是可测量的。如果µ是A上的概率测度,ν是B上的概率测度,我们可以通过(µ×ν)(E)=µ(Eb)dν=ν(Ea)dµ.在另一个方向上,A B上的概率测度µ通过投影导出每个因子空间上的测度。这些测度称为边际,记为marAµ=(πA)µ=µπ−1;marBµ=(ππB)µ=µππ−1。引理1.5设µ是乘积可测空间上的概率测度A× B。如果对某个b 0 ∈ B,marBµ = δb0,则µ = marAµ × δb0。证据 我们只需要对矩形G×F证明它,其中G是A的可测子集,F是B的可测子集。我们要证明µ(G × F)=(marAµ)(G)× δb0(F)。 我们有两种情况:ifb0∈/F,由此导出s在g中的存在性为µ(G×F)=0,且ifb0∈F,则我们要证明µ(G × F)= marAµ(G)= µ(π−1(G))= µ(G × B)。284L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279一→首先注意,对于µ(G×B)=µ(π−1(G))=marAµ(G)=marAµ(G)×δb0(B).同样,µ(A×F)=marBµ(F)=δb0(F)=(marAµ)(A)×δb0(F)。本文给出了如果b0∈/F,则µ(G×F)≤µ(A×F)=0,如果b0∈F,则µ(G×F)= µ(G×{b0})+ µ(G×(F\ {b0})≤µ(G×{b0})+ µ(A ×(F\{b0}))= µ(G × {b0}). 另一方面,µ(G × B)也等于µ(G×{b0})+0。Q2型空间作为余代数哈桑尼型空间的第一个构造是基于信念的层次结构。在这种分层方法中,例如在[10]中看到的,类型是通过详细描述参与者对自然的信念,其他参与者对自然的信念等来构建的。由于每个类型都给出了所有类型集合上的概率测度,因此存在从类型到自然状态和类型的概率测度的函数。正如我们前面提到的,这几乎是一个余代数,除了对这些函数施加了一些额外的条件在这一点上,我们需要公式化MeasI范畴。确定一个有限的参与人集合I。我们假设0∈/I,并定义I0=I∈{0}。 his“0”代表“自然”,因此I 0将自然作为参与者之一(但不会对其他参与者有任何信念)。 我们认为I和I0是离散的范畴。MeasI的对象是可测空间族X=(Xi)i∈I确定一个可测量的空间M来表示每个参与者都应该对自然和其他参与者的信仰有信念。这导致了以下定义。设C:MeasI→Meas是由下式给出的函子:CX=Xii∈I0乍看之下,我们想要考虑的是对每个xi∈Xi,都是CX上的概率测度。 然而,这不是我们想要的,因为它忽略了关于类型空间的一个重要直觉。这就是说,玩家应该知道自己的类型。换句话说,每个参与人i只应该对其他参与人的信念(联合分布)有信念 因此,我们定义函子Ui:MeasIMeas,Ui(X)=<${Xj|j∈I0,j = i}.Ui对态射的作用显而易见注意,Ui依赖于空间自然状态的X0,尽管我们的符号没有提到这一点。L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279285×现在CX=UiX Xi直到同构。我们上面提到的关于参与人i知道自己的类型的事实在[5]中通过添加条件CX上的相应测度在Xi上具有边际δxi来建模。引理1.5在这里起了一个作用,它允许我们将型空间重新定义为余代数:考虑UiX上的测度和CX上的测度本质上是相同的,其中Xi上的边际是一个已知点上的狄拉克测度。最后,我们的主要创新之一,让我们模型的类型空间作为余代数是工作在Meas我,而不是与产品的不同空间考虑。设F:MeasI→MeasI定义为:F(X)=(<$Ui(X))i∈I和前面一样,X是概率测度空间函子,我们的符号再一次省略了自然状态的基础空间X0这样,MeasI中的任何态射都可以作为一个余代数结构,而不是Meas中的一个函数族,每个函数我们使用的特殊函子自动地处理了边缘的条件。定义2.1(M上的)哈桑尼型空间是范畴MeasI中函子F的余代数。一个泛型空间是F在MeasI中的最终余代数。CX的点称为世界的状态。 Xi的一个点称为i型。我们的主要结果是存在一个泛海萨尼型空间。我们的证明遵循Heifetz和Samet的证明[5]。(然而,他们没有将类型空间公式化为余代数。为了使想法更加透明,也因为方法更加通用,我们将暂时忘记多玩家设置中涉及的所有机械。相反,我们考虑Meas上的函子是使用functional构建的。我们在下面的第3节中证明,每个这样的函子都有一个最终余代数。3可测空间上函子的余代数模态逻辑3.1语法和语义定义3.1测度多项式函子类是Meas上最小的函子类,它包含单位元,每个可测空间M的常数函子,并且在乘积,余积和乘积下闭286L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279∈∈SMSU×VSU对于测度多项式函子T,我们定义Ing(T),T的成分,通过以下递归:对于“每个T只有有限的成分。语法我们在下面定义一个语言L(T)。语言是排序的,排序是T的成分。我们写S表示S是一个S类公式;当我们需要它时,我们让FormS表示这样的公式的集合(i) 若M∈Ing(T)且A是M的可测子集,则A:M.(ii) 真S:S。(iii) 若S∈Ing(T)且,:S,则也:S。(iv) 若U×V∈Ing(T),则U:U,且U:V,则U×V:U×V。(v) 如果U+VIng(T)(V+UIng(T))且U=U,则inlU+V=U+V(inrV+U:V+U)。(vi) 若φS∈Ing(T)且φ:S且p∈[0,1],则βpφ:φS.(vii) 如果:T,那么[下一个]:ID。语义设c :X→TX是T的余代数。 语义分配给每个[1][2][3][4][5][6][7][8][9][10][11][12][12][13][14][15][16][17][18][19][19[[A]]c[[trueS]]c[[]]c=A=S(X)=[]]c[[]]cS[[,U×V]]cS S=[]]c×[[]]U+VU+V公司简介ID符号Pf(A)在整个论文中表示f下的图像,设置A。我们可以很容易地检查到[c]。总是SX的可测子集。 在接下来,我们将省略对、inl和inr运算符上的上标,因为它们在上下文中大多是清楚的我们偶尔也会忽略CV[[inlU+V]]c=PinlUX+VX([[]]c)U[[inrU+V]]c[[βpα]]c[[[下一页]===PinrUX+VX([[]]c)Vβp([[]]c)Sc−1([[]]c)不L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279287→ →→SSSSSS在处理的语义时,X:S在一个特殊的余代数c:X→TX上。注3.2如前所述,若M是可测空间,则M的可测子集取为公式.这与大多数在共代数模态逻辑中的处理方法不同,在那里人们将M的元素作为公式;然后这些公式由单例解释。我们在这里的处理方法使语言更有表现力。我们认为,当处理像[0, 1]这样的空间时,人们可能希望有一个表示子区间或其可测子集的集合,而且,这有一个技术上的优势:在不同的点上,知道各种公式的解释集合与可测子集一致是很好的。为了得到这个结果,显然必须从常数的可测子集开始。我们为此付出的唯一代价是,我们要求所有空间都是分离的:也就是说,对于每个x∈M,{x}是所有包含x的可测A的交集。(但是,该要求可以取消:见第5.1节。)引理3.3余代数态射保持语义。 也就是说,如果f:Bc是余代数b:X的态射TX和c:Y如果,如果:S,则(Sf)−1([[S S3.2描述运算与典范空间对于每个余代数c:X→TX和每个x∈SX,我们定义dc(x) ={x:S |x ∈ [[n]] c}.在本文标题的术语作为定义和引理3.3的一个简单推论,余代数同态存在一个映射,即:在引理的条件s中,dc=德湾对于每一个S∈Ing(T),我们定义S的正则域S∈,S是以下是可测量的空间。 在每种情况下,底层集合都是S={dc(x)| 对于某个c:X→TX,x∈ SX}.注意,每个S是一个集合;实际上它的基数至多为2cλ,其中c= 2λ0是连续统的基数,λ是 中的常数函子的可测子集的集合的基数Ing(T).通常我们会用像s这样的字母来表示S的元素。对于σ-代数,我们首先取S的以下形式的子集:|S = { s ∈ S <$|∈s }。|ϕ ∈ s}.(二)288L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279SSSϕ∗^所有S,t^rue=S(Id)和d^=^。S→^^,cJ,,SSS、^则每个S上的σ-代数是由这一族子集生成的。(顺便说一句,每个S都是分离的:s ={|ϕ|S|s∈ |ϕ|)。引理3.4对于所有c:X→TX,所有S∈Ing(T):(1)对于每一个S,S = 1,S= 2(|ϕ|)的。(ii)dc:SX→Sε是可测的。证据x∈[[]] ci <$$>∈dc(x)i <$dc(x)∈ |ϕ|S.Q在这一点上,我们需要对空间上的σ-代数有一个处理S(Id)。我们首先为每个n:S定义一个子集,定义是在Ing(T)上递归(而不是在n上):(Id). 的对于Id:Id,Id = |ϕ|ID. 对于A:M,A=A。 对于U×V,U× V,U × V,U×V,U× V=U×V。F:U,inl=inl(^);且inr=inr(^)。 F:S,βp=βp^。和引理3.5对于S::S的集合族是S(Id)上的σ-代数,并且这个族在有限交下是闭的。3.3映射rS:S→S(Id)引理3.6存在一族由T的成分索引的可测映射rS(i) 对于所有的余代数c:X→TX,下图交换:SX, ,Sd(三)c、IdS, 中文(简体)SrS(ii) 对于所有的ε:S,r−1(ε)= |ϕ|.S^3.4L(T)的正则模型在这一点上,我们几乎准备好定义规范模型。我们首先需要一个初步的概念。对于每个s∈Id,令[next] −1(s)={:T|[next] ∈ s}。(四)引理3.7对于每个s∈Id<$,[next] −1(s)∈T<$。此外,这定义了一个可测的内射函数[next] −1:Id→T。DL.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279289ID→ ∈∈∗IDD不不ID不ID^证据 设c:XTX和xX使得s = dc(x)。那么c(x)TX。我们主张[next]−1(dc(x))=dc(c(x))。对于所有的T:T,名Tc(x)∈ [[]] c i <$x ∈ c−1([[]] c)=[[next]] c.这证实了我们的说法。 我看,这是一个“一”字,一个“一”字。T.对于可测性断言,请注意,对于T:T,|下一个-1是|[下一页]|.|. (For由于符号的原因,我们不喜欢将逆图像写成([next]-1)-1(|ϕ|).)通过定义Id上的σ-代数,这个集合是可测的。我们的结论是,[next]-1是单射的。假设[next]−1(s)=[next]−1(t)。则s和t在形式[next]的所有公式上一致。所以他们同意所有的公式排序Id。 因此s=t。Q我们定义c:Id→T(Id)为rT[next]−1:Id→T→T(Id)(5)注意c是单射的。我们将证明c是一个最终的T-余代数。正如我们的标题所示,我们从满足的理论中构建最终余代数。引理3.8(真值引理)对于所有的S:S,[[]] c=。S3.5最终余代数定理引理3.9dc= Id Id。证据 如果:Id,则根据真理引理,[]] c== |ϕ|. 所以对于s∈Id,ID^dc(s) ={:Id|s∈ [[]] c}={:Id|s ∈ |ϕ|}=s.ID IdQ引理3.10对于每个余代数c:X→TX,下面的图可交换:XcT X,TdcC c名T,Id、、、JJzId[next]−1RTT(Id)所以是dc是余代数的态射证据正方形的验证很容易,三角形来自引理3.6。QD、290L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279IDS我SU1M公关2中pr3U3T3U3IDIDIDIDIDIDIDS定理3.11 c:Id → T(Id)是T的最终余代数。证据设c:X→TX是T-余代数.根据引理3.10,dc是余代数态射 对于唯一性,假设f是任意态射。 由于f保留描述,dcf= dc。 但根据引理3.9,dc = Id Id 所以f= dc,如所愿。Q最后,我们提出我国发展的一个重要必然结果。我们不知道下面推论3.12的直接证明。推论3.12对每个S∈Ing(T),映射rS:S→S(Id)是满射的。证据 考虑余代数c:Id→T(Id)。 根据引理3.6,rSdc=Sdc. 根据引理3.9,dc= Id Id。 因此rSdc= SId Id = Id S(Id)。和这意味着rS是满射的。Q4泛Harsanyi型空间在这一节中,我们将展示如何将我们的工作应用于被认为是MeasI上的余代数的Harsanyi型空间的情况。 为了使符号更易于管理,我们假设I={1,2,3}。设M是一个固定的分离可测空间。设Pr1、Pr2和Pr3为明显的投影Pri:MeasI→Meas。设 U1, U2, U3为函子Ui:MeasI→Meas, U1( X1, X2, X3)=M×Pr2×Pr3,U2(X1,X2,X3)= M×Pr1×Pr3,U3(X1,X2,X3)=M×Pr1×Pr2.设Ti=Ui。所以我们对函子F:MeasI→MeasI由(T1,T2,T3)给出感兴趣对于{M,Ui,Ti,Pr i},我们记为Ing(F)|i = 1,2,3}。注意,如这里所定义的,F的所有成分都是从Meas到Meas的函子。我们用公式表示我们的语言L,使其具有S类公式,其中S∈Ing(F)。L的定义如下:truePri:Pri。如果A是M的可测子集,则A:M。如果0:M,2:Pr2,3:Pr3,则0,2,3:U1。我们对U2和U3也有类似的条款.我们也有关于βp函子的子句:如果β p:Ui,则βp:Ti。若:Ti,则[nexti]:Pri。(This对于M类并不真正需要。)设X=(X1,X2,X3),c:X→FX是F的余代数.的语义赋予每个S∈Ing(F)和每个S:S一个子集[]]cSX。以下是一些有代表性的案例。 [true Pr]]= Xi. [nexti] c= c−1([[]]c),iPrii Ti其中c=(c1,c2,c3),或者换句话说,ci=Pri(c)。假设:M,n2:Pr2和n3:Pr3,然后n0,n2,n3n:U1。 我们设置[0,2,3]]c=[[0]] c×[[2]] c×[[3]] c. 最后,假设βp=U3,使得βp=T3。给定[[p]]c<$U3(X),设[βp<$]]c=βp([[p]]c)<$T3(X).L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279291SSSS(Pr,Pr,Pr)PR1→SC→C对于一个F-余代数X,且S∈Ing(F),我们定义dc使得dc(x)={f:S|x∈ [[n]] c}.我们也定义|ϕ|和之前一样,使用集合|ϕ|S作为S上σ-代数的生成元。 每个dc都是可测量的。剩下的大部分结构与我们已经看到的相似。 Id的作用由(Pr_n1,Pr_n2,Pr_n3)表示。它变成了汽车-F的最终余代数的函数。 我们定义dc1 2 3 :X→(Pr1,Pr2,Pr3)作为(dcC公关2Pr3)。Lemma4. 1.re是可满足的映射S 族:SS(Pr1,Pr2,Pr3)由Ing(F)索引,使得以下成立:a. 对所有的余代数c:X→FX,rS<$dc(Pr 1,Pr 2,Pr 3)。b. r S是单射的。c. S上的σ-代数a(Pr1,Pr2,Pr3)是由S上的σ-代数a的集合R:这个证明紧密地遵循引理3.6中概述的工作。对于eachi∈I,我们有一个函数[nexti]−1:Pri→Tii且ci=rTi ◦ [nexti]-1。对应于引理3.9的陈述是,dc=IdPr,所以dc= Id(Pr,Pr,Pr)。Prii(Pr1,Pr2,Pr3)1 2 3TheoreM4. 2c:(Pr1, P r2,Pr3)F(Pr1, Pr2,Pr3)是F.证据都是一样的,只是作了必要的修改。正如读者可能已经猜到的那样,这里的工作可以推广到MeasI上的多项式。这些是I-索引的函子族Ti:MeasI→Meas,由投影、分离空间的常数、乘积和和,以及π建立。本节中的工作推广到证明MeasI上的每个多项式都有最终余代数。细节并不比我们看到的多。5基本结构的进一步变化和扩展我们已经看到了Meas上由分离空间构成的多项式的最终余代数的主要构造。我们还看到(通过例子)如何将其推广到系统,从而构建泛海萨尼型空间。本文的其余部分介绍了基本技术的变化和扩展。,d,d=SD292L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)2795.1扩展:非分离空间研究分离空间的要点是,这样一个空间的点可以从σ-代数(作为所有单点交的集合)和我们语言中的满意理论中恢复这使我们有了一种语言来描述各种空间的可测子集在缺乏分离性的情况 我们需要添加单例集{m}到排序M的公式。有些句子的语义不可测量。所以为了补偿,我们坚持认为在形式为βp的公式中,所有常数排序的子项都是可测的。这个副条件使得语义定义良好。其余的论证基本上与我们所看到的5.2集上的Kripke多项式函子在这一节中,我们检查相同的方法给出了由单位函子、有限幂集函子、积和余积、固定(有限或无限)集以及来自固定集的函数构成的集上函子的最终余代数的表示。在Roßiger和Jacobs的基础上,我们把这两 类函子称为集合上的Kripke多项式函子(KPF函数空间构造意味着如果S是KPF,E是一个集合,那么SE是KPF。作为一个函子,它由SE(a)=(S(a))E给出;这是函数α:E→Sa的集合。若f:a→b使得Sf:Sa→Sb,则SEf由SEf(α)=(Sf)<$α给出.我们也取Ing(SE)={SE}Ing(S)。为了避免双下标或与我们表示幂集函子的符号P混淆,我们将使用Q表示Set上的有限幂集函子。作为一个函子,我们将Q应用于函数以及集合,写作,例如,Qr(X)对于有限集合X在r下的像r[X]。在余代数文献中众所周知,有限Kripke多项式函子都有最终余代数。人们可以通过检查所有这样的函子都是有界的,然后使用更一般的事实来证明这一点,即Set上的有界函子具有最终余代数。或者,可以使用逻辑方法,如[7,9,11,13]等论文中所做的那样。这是我们采取的方法。然而,我们的工作与引用的工作有点不同,因为我们的最终余代数是基于满足理论而不是某些逻辑系统中的最大相容理论。这意味着我们的结果实际上更弱,因为我们没有得到一个完备性结果。另一方面,我们相信这样更容易得到最终余代数。一般方法甚至在没有逻辑的情况下也能起作用,正如我们在可测空间的工作中所看到的那样。L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279293一QSSQSSΣSID我们的语法被构造成:如果对于某个集合A,其相关联的常数函子A∈Ing(T),则每个元素a∈A都是A的一个公式。此外,如果QS∈Ing(T)且S:S,则QS:QS,且如果对于某个集合E,SE∈Ing(T),:S且e∈E,则(e)最后,我们丰富了我们的语法,以允许在所有种类的布尔否定和合取在我们的语义中,我们定义[a]c[[Q]]c={a},并且=Q([[]] c).(六)像往常一样,我们也使用符号Q表示Q的对偶。所以[[Q]]c={w ∈ QSX |w [[]] c/= 0}。(e)结构的语义是[[(e)]] cE={f ∈ S(X)E|f(e)∈ [[n]] c}.(七)SS布尔连接词的语义是经典的。本文前面的大多数结果都只做了很小的修改,去掉了“可测量”这个词唯一不同的是引理3.6和真值引理3.8。在我们讨论这些结果的类似物之前,我们需要一个一般性的结果。引理5.1设C是任意范畴,设(Xi)i∈I是C-对象族,其中X= Xi是它们的余积,其中i:Xi→X是余积映射. 设T:C → C是函子,(ci)i∈I是T-余代数映射族,则ci:Xi→TXi. 则存在一个映射c:X→TX使得对所有i,ini是一个T-余代数态射ini:ci→ c。证据对于每个i∈I,T在i∈ci中:Xi→TX。根据余积的万有性质,存在某个c:X→TX,使得对所有i,Tini<$ci=c<$ini。所以c是一个余代数结构映射。如所期望的,在i中是一个T-余代数态射.Q我们在本节中的工作与第3节中的早期工作之间的主要区别是,这次我们在证明真值引理之前证明了函数rS(回想一下,在可测空间中,我们在推论3.12中导出了rS的满射性。)引理5.2存在一族双射映射rS:S→S(Id),T的成分使得对所有余代数c:X→TX,rSdc= Sdc.引理5.2的论证与我们在模态逻辑的经典工作中发现的相当接近。294L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279→∗与3.5节相同的工作给出了所需的最终余代数定理。定理5.3对于每个Kripke多项式函子T,c∈:Id∈T(Id∈)是最终余代数。5.3其他空间我们确信,这里的技巧可以推广到其他种类的具体范畴,例如紧Hausdor空间和具有弱拓扑的Borel概率测度。这种情况已经在[2]开始的类型空间中进行了研究。事实上,我们希望在未来几个月内尽可能5.4结论和今后的方向本文件有两个总的要点。首先,我们将经济学/博弈论领域的工作与余代数联系起来。我们认为,大多数(如果不是全部的话)泛类型空间和相关对象的构造可以通过我们的方法获得。我们打算在我们的论文的最后版本中说明这一点。该领域中更常见的方法是构造ωop-极限,然后通过子空间构造来遵循它。虽然我们在这里没有讨论这个问题,但我们觉得我们的方法更简单一些。正如我们已经指出的,它很容易推广到其他环境。我们也已经将已知结果从特定函子推广到多项式。由于这里的理论与逻辑有关,因此应该可以为所有涉及的函子制定逻辑系统并证明完备性定理。 但这一点我们留给未来的工作。利用满意理论来构造最终余代数在余代数及其前身领域中是相当古老的。对于余代数per 在《易经》中,可以找到它。该技术可能隐含在Kurz,Kupke和Venema [8]中;本文还包含一个注释,即Jacobs我们的结果不使用逻辑系统中的极大相容集,而是使用满足理论。这是更简单的,虽然当然必须做更多的工作才能获得完整性结果。从余代数的角度来看,也许这里最原始的是采用一种集的语言,而不是(或者除了)一种点的语言。 这两种语言的相互作用很值得研究。引用[1] Patrick Billingsley,Probability and Measure,Second Edition. Wiley Series inProbability and Mathematical Statistics,New York,1986.L.S. 莫斯身份证Viglizzo/理论计算机科学电子笔记106(2004)279295[2] W. BüogeandT. 1979年,第8期,第193-215页[3] Mich`eleGiry,“A cate e gorica l a p roa c h to p ro b a b ili t y the e or y,“in C a t e goric a lA p e ct s of Topology and Analysis , Springer Lecture Notes in Mathematics 915 ,Berlin-New York,1982,68-85.[4] John C. Harsanyi,出版社:中国出版社.[5] Aviad Heifetz和Dov Samet,“Topology-free typology of beliefs”。Journal of Economic Theory 82(1998),no.2,324[6] Aviad Heifetz和Dov Samet,Journal of Mathematical Economics 32(1999),475[7] 巴特雅各布斯“多分类共代数模态逻辑:一模型论语学习。”Theor.告知。Appl.35(2001),no. 1,31[8] Clemens Kupke,Alexander Kurz,and Yde Venema,“Stone coalgebras”,in H. P. Gumm(ed.),2002年《CMCS》[9] Alexander Kurz,“带模态逻辑的代数”,H。P. Gumm(ed.),1998年《中国共产党章程》[10]Jean-Francco isMert ens和Shmu elZamir,“对于不完全信息的Bayes i an n aly y y m o n t i on”。International Journal of Game Theory 14(1985),no.1,1[11] MartinRüoßiger,“L a n g u age s for or coalge bra s o n d a f un c t ors. “CMC S '99(阿姆斯特丹,1999年),ENTCS 19,Elsevier,阿姆斯特丹,1999年。[12]MartinRüoßiger,“Coalge bra s and d mo d a l logic. ”[13]MartinRoßiger,“从现代逻辑到最终的融合。“The heore tica l C om pu t e r S c i n c e 260(2001),no. 1-2,209-228.[14]Jan Rutten, 以. Ponse等人(编辑),模态逻辑和过程代数,互模拟观点,CSLI讲义53,1995。
下载后可阅读完整内容,剩余1页未读,立即下载
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.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)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)