Share
Embed
Transcript
23 slides
-
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ࣗݾհ ݚڀ • ݴޠ (HydLa)
ͷҙຯ ʢݩʣझຯ • ֶ • ڝϓϩ 2 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ֓ཁ ͜ͷൃදͰ͢͜ͱ • ݍͷఆٛͱ؆୯ͳྫ •
ݍͷߟ͑ํ͕৽͍͠ࢹΛ༩͑ͯ͘ΕΔ͜ͱ • ݍ͕ CS ʹͲ͏Ԡ༻͞Ε͍ͯΔ͔ ҙ ͨͿΜ͔Βͳ͍ྫ͕ग़ͯ͘Δͱࢥ͍·͢ Βͳ͍ͷ۩ମྫదٓεϧʔ͍ͯͩ͘͠͞ ͨͩ͠ҎԼͷ͍ͬͯΔͷͱͯ͠ਐΊ·͢ • ू߹ɼࣸ૾ͷجૅࣝʢશࣹɼ୯ࣹɼੵɼʣ 3 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ݍͱ ݍͱԿͰ͋Δ͔ • 20 ੈلத൫ʹͰ͖ͨ৽ֶ͍͠
• நతͰ͓͠Ζ͍ • ֶʹݶΒͳ͍ཧͷڞ௨ݴޠ ݍͱԿͰͳ͍ͷ͔ • ϓϩάϥϜΛॻ্͘Ͱʹཱͭͷ 4 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ֶͷ෮श 1 ◦ ू߹ͱࣸ૾ ू߹ͱࣸ૾ʹରͯ͠ҎԼ͕Γཱͭ
• ҙͷू߹ X ʹରͯ͠߃ࣸ૾ idX ͕ଘࡏ • ҙͷࣸ૾ f : X → Y, g : Y → Z ʹରͯ͠ ߹ࣸ૾ g ◦ f : X → Z ͕ଘࡏ άϥϑͱ४ಉܕ άϥϑͱͦͷ४ಉܕʹରͯ͠ҎԼ͕Γཱͭ • ҙͷάϥϑ G ʹରͯ͠߃ࣸ૾ idG ४ಉܕ • ҙͷ४ಉܕ f : G1 → G2 , g : G2 → G3 ʹରͯ͠ ߹ࣸ૾ g ◦ f : G1 → G3 ४ಉܕ 5 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ֶͷ෮श 2 ◦ ܈ͱ४ಉܕ ܈ͱͦͷ४ಉܕʹରͯ͠ҎԼ͕Γཱͭ
• ҙͷ܈ G ʹରͯ͠߃ࣸ૾ idG ४ಉܕ • ҙͷ४ಉܕ f : G1 → G2 , g : G2 → G3 ʹରͯ͠ ߹ࣸ૾ g ◦ f : G1 → G3 ४ಉܕ ॱংू߹ͱ୯ௐࣸ૾ ॱংू߹ͱ୯ௐʢ૿Ճʣࣸ૾ʹରͯ͠ҎԼ͕Γཱͭ • ҙͷॱংू߹ X ʹରͯ͠߃ࣸ૾ idX ୯ௐ • ҙͷ୯ௐࣸ૾ f : X → Y, g : Y → Z ʹରͯ͠ ߹ࣸ૾ g ◦ f : X → Z ୯ௐ 6 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ݍͷؾ࣋ͪ Ҏ্ͷྫͰϞϊͱҹʹରͯ࣍͠ͷ 2 ͕ͭΓཱ͍ͬͯͨ •
ҙͷϞϊʹରͯ͠߃తͳҹ͕ଘࡏ • ߦ͖ઌͱग़ൃ͕ಉ͡ҹʹରͯ͠߹ͨ͠ҹ͕ଘࡏ ݍ͜ͷ͋Γ;ΕͨಛͰఆٛ͞ΕΔ 7 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ݍͷఆٛ ఆٛ [1] ݍ࣍ͷཁૉ͔ΒΓཱͭ •
ରɿA, B, C, ... • ࣹɿf, g, h, ... • ҙͷࣹ f ʹରͯ͠ର dom(f), cod(f) ͕͋Δ A = dom(f), B = cod(f) Ͱ͋Δ f Λ f : A → B ͱॻ͘ • ࣹ f : A → B, g : B → C s.t. cod(f) = dom(g) ʹରͯ͠ ࣹ g ◦ f : A → C ͕͋Γɼ ҙͷࣹ f : A → B, g : B → C, h : C → D ʹରͯ͠ h ◦ (g ◦ f) = (h ◦ g) ◦ f ͕Γཱͭ • ҙͷର A ʹରࣹ͠ idA : A → A ͕͋Γɼ ҙͷࣹ f : A → B ʹର͠ f ◦ idA = f = idB ◦ f ͕Γཱͭ 8 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ҙ ରͱͯ͠ू߹ɺࣹͱͯࣸ͠૾ΛऔͬͨݍΛ Sets ͱݺͿ ݍͷྫʢߏ͖ʣू߹ͱʢߏΛอͭʣࣸ૾͚ͩͰͳ͍
ॱংͦͷͷ ॱংू߹ P Λߟ͑Δ ରͱͯ͠ཁૉΛͱΓɼॱং͕ؔ͋Δͱ͖ʹࣹ͕͋Δͱ͢Δ • ҙͷཁૉ x ʹର͠ x ≤ x • x ≤ y, y ≤ z ͳΒ x ≤ z ݍͰͳ͍ྫ • ॱংू߹ͱ୯ௐݮগࣸ૾ ∵ ୯ௐݮগࣸ૾ͷ߹୯ௐ૿Ճࣸ૾ • ϚάϚ M ͷཁૉͱͦͷԋࢉ ∵ ϚάϚͷԋࢉ୯Ґݩ͕ͳ݁͘߹తͰͳ͍ 9 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ CS ͬΆ͍ྫ ໋ͱূ໌ • ҙͷ໋
φ ʹରͯ͠ φ ⊢ φ • φ ⊢ ψ, ψ ⊢ ρ ͳΒ φ ⊢ ρ ϓϩάϥϜʹ͓͚Δܕͱؔ ϓϩάϥϛϯάݴޠ L Λߟ͑Δ • L ͷҙͷܕ T ʹର͠ҾΛͦͷ··ฦ͕ؔ͢ॻ͚Δ • ؔ f : T1 → T2 , g : T2 → T3 ʹର͠ g(f(t)) Λฦؔ͢ 10 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ԋश ͜ΕΒ͕ݍʹͳ͍ͬͯΔ͜ͱΛ֬ೝͯ͠Έ͍ͯͩ͘͞ ର ࣹ ϕΫτϧۭؒ
ઢܗࣸ૾ ࣮ R ͷΈ ࿈ଓؔ ू߹ 2 ߲ؔ ϞϊΠυ ϞϊΠυ४ಉܕ ू߹ X ͷཁૉ = ܈ G ͷཁૉ ܈ԋࢉ 11 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ݍͷಛ ݍͰରࣹͷಛ͚ΛࣹͷΈΛ༻͍ͯߦ͏ ू߹ͱҟͳΓରͷதݟͳ͍ ʢཁૉΛݟͳͯ͘ಉͷදݱྗ͕͋Δʣ ཁૉΛݟͳ͍͜ͱʹΑͬͯ
• ఆ͕ٛ؆ܿʹͳΔ • ΑΓநతʹͳΔ • ࠓ·Ͱ͔Βͳ͔ͬͨ͜ͱ͕͔Δ 12 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ Ϟϊࣹ ࣹͷಛ͚ͷྫͱͯ͠୯ࣹੑͱશࣹੑΛऔΓ্͛Δ ఆٛ ࣹ f
: A → B ͕ϞϊࣹͰ͋Δͱ ҙͷࣹ g, h : C → A ʹରͯ͠ fg = fh ͳΒ g = h Ͱ͋Δ͜ͱ C g // h // A f // B Sets ʹ͓͍ͯϞϊࣹͰ͋Δ͜ͱ୯ࣹͰ͋Δ͜ͱͱಉʢԋशʣ g, h ͕ A ͷҙͷݩΛද͍ͯ͠Δͱࢥ͑ࣗવ Ͱશࣹʁ 13 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ Τϐࣹ ఆٛ ࣹ f :
A → B ͕ΤϐࣹͰ͋Δͱ ҙͷࣹ i, j : B → C ʹରͯ͠ if = jf ͳΒ i = j Ͱ͋Δ͜ͱ A f // B i // j // C Sets ʹ͓͍ͯΤϐࣹͰ͋Δ͜ͱશࣹͰ͋Δ͜ͱͱಉʢԋशʣ if = jf ͔Β i = j ͕ݴ͑ΔͨΊʹ f Λ߹ͨ͜͠ͱͰใ͕ࣦΘΕ͍͚ͯͳ͍ͱߟ͑Δͱࣗવ ͞ΒʹϞϊࣹͱΤϐࣹରʹͳ͍ͬͯΔ 14 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ର ݍʹ͓͍ͯ 2 ͭͷ֓೦͕ରͰ͋Δͱɺ ยํͷࣹͷ͖Λશͯٯ͖ʹ͢Δͱ͏ยํʹͳΔ͜ͱ
ࢼ͠ʹΤϐࣹͷਤΛͻͬ͘Γฦͯ͠ΈΔͱ Ϟϊࣹͷਤ C g // h // A f // B ͻͬ͘Γฦͨ͠Τϐࣹͷਤ C i // j // B f // A ͭ·Γ୯ࣹੑͱશࣹੑͪΐ͏Ͳରͷ֓೦Ͱ͋Δ͜ͱ͕͔ͬͨ 15 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ੵ ରͷಛ͚ͷྫͱͯ͠ੵͱ༨ੵΛऔΓ্͛Δ ෳͷࣹΛߟ͑Δ࣌ɼਤࣜͱ͍͏ɽ ੵ ਤࣜ
A p1 ←− P p2 −→ B ͕ A, B ͷੵͰ͋Δͱ ҙͷର Z ͱਤࣜ A z1 ←− Z z2 −→ B ʹରͯ͠ pi ◦ u = zi Λຬͨ͢Ұҙͳ u : Z → P ͕ଘࡏ͢Δ͜ͱ Z z1 u z2 A P p1 oo p2 // B Sets ʹ͓͍ͯ P ͕ੵͰ͋Δ͜ͱੵͰ͋Δ͜ͱͱಉʢԋशʣ (P = A × Bɼpi ͕ࣹӨɼu = ⟨z1 , z1 ⟩) 16 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ༨ੵ ݍʹ͓͍ͯରͷ֓೦ΛΑ͘༨ʙͱݺͿ ༨ੵ ਤࣜ A
q1 −→ Q q2 ←− B ͕ A, B ͷ༨ੵͰ͋Δͱ ҙͷର Z ͱਤࣜ A z1 −→ Z z2 ←− B ʹରͯ͠ u ◦ qi = zi Λຬͨ͢Ұҙͳ u : Q → Z ͕ଘࡏ͢Δ͜ͱ Z A z1 ?? q1 // Q u OO B z2 __ q2 oo Sets ʹ͓͍ͯ Q ͕༨ੵͰ͋Δ͜ͱͰ͋Δ͜ͱͱಉʢԋशʣ ੵͱͪΐ͏Ͳରͷ֓೦Ͱ͋Δ͜ͱ͕͔ͬͨ ͦΕͧΕΑ͘ ∏ ͱ ⨿ Ͱॻ͕͘ରͳͷͰࣗવ 17 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ܕແ͠ϥϜμܭࢉ ܕແ͠ϥϜμܭࢉͰ࣍ͷΑ͏ͳϥϜμࣜΛߟ͑Δ λx.xx ܕແ͠ϥϜμܭࢉͷϞσϧΛ୳ͯ͠ΈΔ 1
x ؔͷͣ 2 A → B ͱ͍͏ؔͩͱࢥͬͯΈΔ 3 x ͦͷҾͱͯ͠༩͑ΒΕΔͷͰू߹ A ͷཁૉͰ͋Δ 4 BA = A ໃ६͢ΔͷͰ BA ∼ = A ͱͯ͠ΈΔ 5 ͦΕͰೱΛߟ͑Δͱ |A| = |B| = 1 ͱ͍͏ࣗ໌ͳղͷΈ 6 ܕແ͠ϥϜμܭࢉͷϞσϧͳ͍ʁ ʢ༨༟͕͋ͬͨΒͲ͕͓͔͍͔͜͠ߟ͔͑ͯΒ࣍ʹߦ͍ͬͯͩ͘͞ʣ 18 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ී௨ |A| ͕େ͖͘ͳΕ |A| <
|BA| ͳͷͰղʹͳΒͳ͍ ∵ Sets Ͱߟ͍͑ͯΔ͔Βʂ ܕແ͠ϥϜμܭࢉͷඇࣗ໌ͳϞσϧͷߏ๏ 1 cpoʢඋॱংू߹ʣͷݍͰߟ͑Δ 2 উखͳ cpo D ʹରͯ͠ɺD0 = D, Dn+1 = DDn n ͱ͢Δ 3 Dn Dn+1 ʹຒΊࠐΊɺ·ͨ D∞ cpo Ͱ͋Δ͜ͱ͕ࣔͤΔ 4 ͦͯ͠ D∞ ∼ = DD∞ ∞ ࣔͤΔ 5 D D∞ ʹຒΊࠐΊͯ D Λେ͖͘औΕ D∞ ͖ͳ͚ͩେ͖͘Ͱ͖Δ ͜ͷߏ๏͋Δ݅Λຬͨ͢ݍʹҰൠԽͰ͖ΔͨΊ ܕແ͠ϥϜμܭࢉͷඇࣗ໌ͳϞσϧ͕ແʹ͋Δ͜ͱ͕͔Δ [2] 20 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ܕ͖ϥϜμܭࢉ ܕ͖ϥϜμܭࢉͷ΄͏ͦΕ΄Ͳ͘͠ͳ͍ Sets ͪΖΜϞσϧʹͳ͍ͬͯΔ Ұൠʹ͋Δݍ͕ϥϜμܭࢉͷϞσϧʹͳΔʹ
ݍతͳҙຯͰͷႈ͕͋ΕΑ͍ ·ͨੵܕ͕͋ΔͳΒશͯͷ༗ݶੵ͕͋Εྑ͍͠ ܕ͕͋ΔͳΒશͯͷ༗ݶ༨ੵ͕͋Εྑ͍ ܕ͖ϥϜμܭࢉʹ͓͍ͯϞσϧʹඞཁͳ͕͔݅ͬͨ 21 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ͦͷଞ ϥϜμܭࢉҎ֎ͷԠ༻ͱͯ͠ Ϟφυ Haskell, Scala
ͰΘΕͯΔ ݍؔܕϓϩάϥϛϯάͷʹཱ͔ͭ τϙε ߴ֊؍ओٛཧͷϞσϧʹͳ͍ͬͯΔΒ͍͠ [3] ༨ ঢ়ଶભҠܥແݶσʔλߏΛ؆୯ʹॻ͚Δ [4] ͳͲ͕͋Δ 22 / 23 -
֓ཁ ಋೖ ݍͷಛ CS ͷԠ༻ ࢀߟจݙ [1] Steve Awodey. ݍ
ݪஶୈ 2 ൛. ڞཱग़൛, 2015. [2] ԣจ. ϓϩάϥϜҙຯ. ڞཱग़൛, 1994. [3] ਗ਼ਫٛ. ݍʹΑΔཧֶ ߴ֊ཧͱτϙε. ౦ژେֶग़൛ձ, 2007. [4] J. Rutten. Universal coalgebra: a theory of systems. 1996. 23 / 23