<   2014年 07月 ( 12 )   > この月の画像一覧

中国の本気

仰天した。

日本はすでに中国の属国に!? 北京の教科書の仰天地図

これが中国の本音だったら大変な事だ。
[PR]
by tnomura9 | 2014-07-30 06:40 | 話のネタ | Comments(0)

ラッセルのパラドックスと排中律

命題 P は真であるか、偽であるかのどちらかであるというのが排中律だ。述語論理では述語 P 命題変数 x の組 P(x) を考え、x に要素や論理式を代入する事で、命題 P(x) の真偽が決定する。この P(x) が真となる x を集めて集合を構成しようとするのが、集合の内包的定義だ。記号で書くと次のようになる。

A = { x | P(x) }

この場合述語 P については、排中律から、考えられる全ての x について P(x) の真偽が決定されなければならない。これは当然述語 P の自己言及 P(A) についても真偽が決定される事が要求される。そうでないと命題は真であるか偽であるかのどちらかであるという排中律が成立しないからだ。幸いな事に大抵の普通の集合ではそれを定義する述語をその集合自身が充足することはないので問題は起きない。

しかし、ラッセルの集合、

R = { x | ¬ (x ∈ x) }

では R 自身が R の要素である、すなわち R の述語を充足するとも充足しないとも言えないパラドックスになってしまう。しかし、数学の理論のなかにパラドックスが入ってしまっては理論自体が成立しない。どう解決されているかというと、ラッセルの集合はクラスという集まりであって集合ではないとされている。

つまり、ラッセルの述語は排中律には違反しないが、すなわち、ある要素が「自分自身を含まない集合」という述語をみたすか満たさないかという判定を全ての要素についてできるが、ラッセルの集合は集合ではないため、¬ (x ∈ x) という述語を適用するのは意味がないと考えるのだ。∈という記号は集合についてのみ適用されるため、集合でない R について R ∈ R は意味をなさない。つまり R ∈ R という論理式の真偽を言う事はできないという立場だ。実際 ∈ をある集合の要素であるものだけに限定すると、ラッセルの集合は自然に排除される。

しかし、この議論も無限に大きい数は存在しないという議論に似てなんとなくうさんくさい感じがする。ラッセルの集合が集合でないとしても、ラッセルの述語にラッセルの集合を適用した論理式は排中律を破っているという事実は否定できないのではないかと思うのだ。そのため、排中律そのものを否定する直観主義論理学が作られている。これはプログラミングの理論とよく適合するらしいが、詳しい事は知らない。

なぜクラスという微妙な概念が導入されたのか不勉強で知らないが、たぶん、「自分自身を要素としない集合」というのは普通に存在しているからだろう。自然数の集合のような普通の集合はその集合自体が自分自身の要素となる事はない。「自分自身を要素としない集合」というものを集める事はできるように思えるからだ。それにも関わらず、「自分自身を要素としない集合」全ての集合を集めた集合を考えるとパラドックスになってしまう。だから、そういう「集合」はないが、そういう「集まり」はありそうなので「クラス」と呼ぶ事にしたのではないだろうか。

自分自身を要素としない集合を全て集めた集合を考える事ができないのはつぎのように考えるとわかる。当座考えられる「自分を要素としない集合」xi を集めた集合 R' を考える。すなわち、

R' = {x0, x1, ... }

である。このとき R' は自分自身の要素となることはない。つまり、

R' = {R', x0, x1, ... }

となることはない。その場合要素としての R' が「自分自身を要素として含む集合」になってしまい、R' の内包的定義に抵触してしまうからだ。したがって、R' の要素の中には R' は含まれないが、そのことが R' を自分自身を要素として含まない集合にしてしまう。したがって、 R' と R' の要素を含む新しい集合 R'' を考える、すなわち、

R'' = {R', x0, x1, ... }

であるが、上に述べた議論と同じで R'' もまた「自分自身を要素として含まない集合」になってしまう。このへんの事情が、「自然数の最大数は存在しない」という議論に似てなにか居心地がわるいものがある。「自然数の最大値を N とすると N + 1 は自然数であって N よりは大きい。これは自然数 N が最大値であるという仮定に反する。よって自然数には最大の数は存在しない。」とそっくりだからだ。

自然数に関する述語「x は偶数である」は x の値に応じて論理式が真となったり偽となったりする。しかし「無限大は偶数である」という命題は真偽を決める事ができない。無限大は自然数のひとつだから偶数であるか奇数であるかのどれかであるはずだが、無限大を奇数とも偶数とも確定する事はできない。無限大はどの自然数とも大小を比較できるから、自然数の仲間のはずだが、無限大を捕まえることはできないので、それが偶数とも奇数ともきめることはできない。

同様なことがラッセルの集合の場合も言える。「自分自身を要素としない集合の集合」は自分自身を要素としない集合「全て」を集めたものでなければ、いろいろな集合を作ることができる。そこで、それらのうち最大の集合 R が作れたと仮定すると、上に述べたような理由で R は R に含まれない「自分自身を要素としない集合」になってしまう。したがって、最大の集合 R を仮定したら、それに含まれない集合 R が存在することがわかったので R という最大の集合はつくることができない事がわかる。そうであれば、自然数の無限大とおなじように最大の集合 R というものは存在しないのだから、R にどのような述語も適用できないことになる。

したがって、トリックのようだが、R という集合を確定できないので、R に述語を適用できなくても、述語の排中律を侵害したことにはならない。確定した要素には述語は適用できるが、確定できない要素について述語を適用した時の真理値は確定できないからだ。

ラッセルの集合は集合における、自然数の無限大に相当するものとはかんがえられないだろうか。集合は自分自身を要素としない集合か、自分自身を要素とする集合かのいずれかだが、それらの集まりは集合ではなくクラスであるということだろう。自然数は、10未満の数と、10以上の数に分けることができるが、10以上の数の最大値は求めることができないというのに似ている。

数学をアナロジーで論じるべきではないのだろうが、両者の共通点をみると、どうも、演算規則の普遍性を基礎として、既存の要素から新しい要素を作り出すやりかたには、ラッセルのパラドックスを発生させる要因が潜んでいるような気がする。
[PR]
by tnomura9 | 2014-07-30 06:15 | 考えるということ | Comments(0)

自然変換の水平合成

これが最近の圏論関係の記事の当分最後の記事になる。というのは、うれしいことに、圏論の考え方が少し分かってきたのだ。今までこのブログにメモ書きのように書いてきたことで、マックレーンの『圏論の基礎』の第1章がなんとなく理解できるようになってきた。

圏論を理解するためのキーポイントは、対象と射の中が覗けないという external の立場に慣れる事と、射の「可換」についてのしっかりしたイメージを作ることだ。

しかし、わかりだしたがゆえに自分の理解が本当なのか不安になってきたのも事実だ。マックレーンの教科書には様々な合成の記号が登場するがそれには一つ一つ意味がある。キーボードで入力する都合から、これまでの記事では記号を恣意的に使いすぎてきた。

プログのメモ書きを作って理解を深めようとする段階からしっかりとノートをとる段階になってきた。プログの記事の内容も「私はこんなふうに考えています」というところから、「圏論ではこのようなことが述べられています」という内容の記事にならなくてはいけないのではないかと考えるようになった。ノイズを増やすだけの記事では迷惑になる段階になったのかもしれない。したがって、圏論についての記事はしばらくお休みにしたほうがいいようだ。

しかし、自然変換の水平合成の考え方は、モナドの理解に直結するので一連のチャレンジの最後として挑戦してみたい。

1. 自然変換の垂直合成

まず自然変換の垂直合成について復習してみる。圏 C から B への関手 R, S, T : C -> B があり、これらの自然変換を σ : R -.-> S, τ : S -.-> T とするとき、自然変換 σ と τ の垂直合成 τ ・ σ が次のように定義できる。

(τ ・ σ)c = τc o σc

これは τ と σ の垂直合成のコンポーネントが、τ のコンポーネントと σ のコンポーネントの射の合成になっていることを示している。合成記号の ・ は自然変換の垂直合成として定義されたものであり、合成記号 o は通常の射の合成をあらわしている。圏論ではいろいろな合成記号があってそれぞれ意味が異なっているので慣れておく必要がある。

上に述べたような垂直合成された自然変換 (τ ・ σ) は関手 R から T への自然変換となる。すなわち、

(τ ・ σ) : R -.-> T

である。すっきりとしているが、中にはいろいろな工夫がごちゃごちゃとつめ込まれている。

2. 自然変換の水平合成

3つの圏 C, B, A について次のような関手があるとする。

C --{S}--> B --{S'}--> A
C --{T}--> B --{T'}-->A

さらに、各関手の間に次のような自然変換があるとする。

τ : S -.-> T
τ' : S' -.-> T'

このとき τ と τ’ の水平合成 (τ’ o τ) は関手 S と S' の合成 S'S から、関手 T と T' の合成 T'T への自然変換である。すなわち、

τ' o τ : S'S -.-> T'T

このとき τ と τ' は垂直合成のときとはちがって、合成関手にそって水平方向に並んでいるので、水平合成だ。このとき、τ’ o τ のコンポーネント (τ' o τ)c は、圏 A の対象 S'Sc から T'Tc への射となる。

(τ o τ')c : S'Sc -> T'Tc

これを、どのような射で表現できるだろうか。まず圏 C の対象 c の関手 S による像である圏 B の対象を考えると、それは Sc である。この対象を関手 S' で圏 A に写像するとそれは S'Sc である。

つぎに、圏 A の対象 S'Sc から対象 T'Sc への自然変換 τ' のコンポーネント τ’Sc を考える。τ'Sc は τ’ の圏 B の対象 Sc についてのコンポーネントだ。τ' を Sc に関数適用しているわけではないので注意が必要だ。このとき、τ'Sc は次のような射である。

τ’Sc : S'Sc -> T'Sc

だ。これは τ’ の 圏 B の対象 Sc についてのコンポーネント τ'Sc は domain が 圏 A の対象 S'Sc で codomain が圏 A の対象 T'Scであることを示している。

今度は、圏 B の対象 Sc についての 自然変換 τ を考える。すなわち、τc だ。この場合も τc は、自然変換 τ の圏 C の対象 c についてのコンポーネントをあらわしているので、これを τ を c に関数適用したものと誤解すると意味がわからなくなる。ところで τ : S -.-> T であるので、結局、τc は domain が Sc で cocomain が Tc の射になる。

τc : Sc -> Tc

さらに、τc が圏 B の射であることに注目すると、τc の関手 S' による圏 A の射への像 S'τc を考えることができる。この場合は S' は τc に関数適用しており S' のコンポーネントが τc であるというわけではないので注意が必要だ。

ここで、この圏 A の射 S'τc の domain を考えると、それは圏 A の対象 S'Sc である。また、codomain は、S'Tc である。つまり、S'τc は次のような射となる。

S'τc : S'Sc -> S'Tc

ここで、これまで論じてきた自然変換のコンポーネントの射をならべてみるとおもしろことが分かる。

τ’Sc : S'Sc -> T'Sc
S'τc : S'Sc -> S'Tc

これは、自然変換のコンポーネントの τ をその domain の関手に作用させると、codomain の対象になるということを示している。偶然ではないと思うが、論証はできない。しかし、便利な簡略法だ。そこでこれを使って T'Sc -> T'Tc, S'Tc -> T'Tc の自然変換のコンポーネントを作ってみると次のようになる。

T'τc : T'Sc -> T'Tc
τ’Tc : S'Tc -> T'Tc

この4つの射からなる図式は、圏 B の射 τc についての τ’ の自然性から可換である。したがって水平合成 (τ' o τ) : S'S -.-> T'T を次の2つの合成射で定義できる。

(τ' o τ)c = T'τc o τ'Sc = τ'Tc o S'τc

これまでの圏論に関する記事は、集合に関する初歩的な知識しかない管理人が、Haskell 経由で圏論に取り組むとどうなるかというライブレポートだ。したがって、間違いが多分に含まれているだろう。将来的にはすっかり書き直したい気になるのかもしれない。しかし、圏論の議論を理解するのに、高等な数学的知識はいらないこと。圏のイメージ作りのためには集合の圏があれば十分なこと。圏論の議論が理解できるようになるためのポイントは「可換」のしっかりしたイメージを作ることなどが実証できたように思う。

Haskell などをはじめなければ、圏論の学習など思いもつかなかっただろうが、モナドに苦しめられたお陰で、圏論の面白さが予感できるようなくらいのところまではこれたように思う。地道に学習をつづけて、数学者でない素人が読んでも圏論を扱えるようになるような記事を書けるようになるとうれしい。

数学者は素人がどこに躓くかがわからないだろうが、障害を除けば案外圏論の考え方に馴染むかもしれない。案外、圏論は集合と同じような、考え方のプラットフォームになるような単純さと明快さを備えているかもしれないと思うようになった。
[PR]
by tnomura9 | 2014-07-26 04:59 | 圏論 | Comments(2)

自然変換の垂直合成と水平合成

圏 C と B が与えられたとき、関手 R, S, T : C -> B について、σ : R -.->S と τ : S -.-> T が二つの自然変換であれば、各 c ∈ C に対するそれらのコンポーネントから合成射 (τ * σ)c = τc . σc が定義される。これらのコンポーネントを集まりは自然変換

τ * σ : R -.-> T

になる。これは Rf : Rc -> Rc' と Tf : Tc -> Tc' について、次の可換式を成立させるので自然である。

Tf . (τ * σ)c = (τ * σ)c' . Rf

つまり、自然変換はつぎつぎに合成していくことができる。ここでは記述しないがその合成は結合的である。また、各関手 T について恒等変換があって、それはコンポーネントが 1Tc = 1Tc の自然変換 1T : T -> T がある。したがって、圏 C と B の全ての関手を対象とし、自然変換を射とする関手圏(functor category)

BC = Funct(C, B)

を構築することができる。

関手圏の例としては B と C が集合(つまり要素が対象で、要素から要素への恒等射だけからなる圏)の場合、B から C への関手は、B の要素から C の要素への写像になる。したがって、B と C の個数が有限の場合、B の任意の要素を C の要素に対応づける可能性は BCあることを考慮に入れて、BC 個の要素数を持つ集合 BC が関手圏になる。

自然変換 σ と τ の合成は、関手を縦方向に並べて変換していくので、垂直合成と呼ばれる。

自然変換にはもうひとつ水平合成がある。関手と自然変換がつぎのように与えられた時、

C --{ S }--> B --{ S' }--> A
C --{ T }--> B --{ T' }--> A

ただし、

τ : S -.-> T
τ' : S' -.-> T'

このとき、自然変換 τ と τ' は水平に並んでいる。詳細は省くが、c ∈ C を合成関手 S' . S で写像した S'Sc と T' . T で写像した T'Tc の間の射を (τ' * τ)c で定義すると、

(τ' * τ)c = T'τc * τ’Sc = τ’Tc * S'τc

のようになる。これを自然変換の水平合成という。

このように自然変換の合成には垂直合成と水平合成のふたとおりの合成方法がある。この2つの自然変換の合成法はモナドのときに活躍する。
[PR]
by tnomura9 | 2014-07-25 01:21 | 圏論 | Comments(0)

関手の圏

1.自然変換

圏 C から圏 B へ二つの関手 S, T : C -> B があるとする。この時、圏 C の対象 c, c' とその射 f : c - c' を関手 S, T によって圏 B に写像するとその像はそれぞれ、

Sf : Sc -> Sc' および Tf : Tc -> Tc' になる。

このとき、対象 Sc から対象 Tc への射 τc : Sc -> Tc と、対象 Sc' から対象 Tc' への射 τc' : Sc' -> Tc' があって次の可換関係があるとき、τc : Sc -> Tc は c において自然であるという。

Tf . τc = τc' . Sf

これは Sc --{ Sf }--> Sc' という関係を τc' と τc' によって、Tc --{Tf}--> Tc' という関係に写すことができるからだ。なぜなら Sc |--> Tc は Tc = τc Sc で簡単に求められるし、Sc' |--> Tc' も Tc' = τc' Sc' だ、さらに上の可換式から、Tf (τc Sc) = Tf (Tc) = τc' ( Sf Sc) = τc' (Sc') = Tc' のように Sf から Tf : Tc -> Tc' を導くことができるからだ。(ここで = を流用して可換であることを表すために使っているので = の普通の使い方ではない。Tf Tc のように射を対象に適用する場合をどのように表記したらよいのか管理人は知らない。紛らわしい書き方だが Tf Tc = Tc' で Tf : Tc -> Tc' をイメージした。)

したがって、τc のような射を圏 C の全ての対象 c について集めたものは、関手 S から関手 T への射(意味的には写像の一種)と考えて良い。この τ を関手 S から関手 T への自然変換といい、τc のような射を自然変換 τ のコンポーネントという。

2.関手の圏

ここで、S, T のような圏 C から圏 B への関手を全てを集めたものと、その自然変換 τ を考えると、関手を対象とし、自然変換を射とする「関手の圏」を考えることができる。

関手のような「機能」を対象と考え、「機能」を別の「機能」に変換する自然変換という射とあわせて新たな圏を作ることができるのがおもしろい。要素を集めた集合を1つの集合と考え、それらの集まりである集合の集合が考えられるという集合の自由さに似ている。

3.1個の関手とその恒等射のみからなる関手の圏

さて、圏 C にある自己関手 T があったとする。この場合、c --{ f }--> c' は、Tc --{ Tf }--> Tc' に写される。T は圏 C からそれ自身への関手だから、Tc, Tc' は圏 C の対象で、Tf は圏 C の射だ。このとき関手 T 1個だけが対象として存在する関手の圏を作れるだろうか。

圏に必ず存在する射は恒等射だ。これを作ってみよう。関手 T の恒等射は関手 T を関手 T それ自身に変換する自然変換だ。これを τ とするとタウの圏 C の対象 c についてのコンポーネント τc : Tc -> Tc は、Tc の恒等射 1Tc になる。したがって、このようなコンポーネントを全て集めたものが τであり、τT = T となる。対象1個と、その対象の恒等射のみからなる圏はトリビアルな圏だが、圏 C の自己関手から関手の圏を作るときの作り方がわかる。

これで、「単なる自己関手の圏のモノイド対象」にすこし近づけた気がする。
[PR]
by tnomura9 | 2014-07-24 08:08 | 圏論 | Comments(0)

可換 commutative

集合は、要素と集合と写像という3つの要素だけですべての数学的対象の構造を記述できる。それは公理的集合論から全数学の体系を組み立てるというような、数学基礎論のような意味ではなく、数学の対象について整理して記述するために集合の考え方が便利であるという意味合いだ。

集合と要素と写像の性質を理解するのにそう難しい数学的な背景知識はいらない。むしろ、最初に集合的な考え方を身につけていると、いろいろな数学を学ぶときに議論がわかりやすくなる。

圏論というのも、このような集合の特質と同じような特徴があるのではないかという気がしてきた。圏論の場合も集合のそれと同じように道具立てはシンプルだ。圏、対象、射、射の合成、可換、関手、自然変換くらいしかない。様々な数学的構造の複雑な議論は、圏の対象と射のなかに閉じ込められてしまう。圏論の議論では、そのような個別の議論は対象と射のなかに閉じ込められて考慮する必要がなくなるからだ。

圏論を理解するための最も重要な考え方は、external な立場ということだ。集合では集合と集合の写像を考える際にも、始域の集合の要素がとのように終域の集合の要素に関連付けられているかを考えたり、端的に集合の中の要素間の関係を考えたりする。圏論の external の立場ではこのような集合の要素を直接に扱うことは全くない。集合の要素や、単射、全射のようなものも、すべて射の関係性で表現される。

また、隠蔽されるのは対象の中身だけでなく、射の中身ものぞくことはできない。圏論の議論では、射 f と g の関係については考察されるが、射そのものの実体はなんであるのかについては触れられない。射がたんなる矢印なのか、写像なのか、凖同型写像なのか、連続写像なのかは、まったく圏論の議論に影響しない。

圏論の学習の敷居を高くしているのは、参考書にかかれている実例がとんでもなく高度な数学の知識ばかりだということだ。実例をまったく理解できないのに、どうしてそれを扱う抽象的な議論ができるだろうか。

しかし、上で述べた圏論の道具の本質を考えると、圏論を学習するのにそのような高度に数学的な実例はまったく必要がない。圏論の議論ではそのような高度な知識は対称と射のなかに隠蔽されてしまうからだ。むしろ、圏論を学習した後で、それぞれの高度な理論を勉強すると、それらの議論に随伴のような圏論の考え方を当てはめることで、数学的構造が把握しやすくなるのではないだろうか。

実際、圏論を理解するには、実例としては、集合の圏である Set だけで充分なのだ。圏論の議論のイメージを作る際には、対称を集合に、射を domain の要素すべてを定義域とする全域写像に置き換えると。ほとんどの議論のイメージをうまく作ることができる。

圏論の議論のすべては射と射の関係性について述べてあるのだ。

このように、圏論は射と射の関係性について述べてあるが、そのときに、最も重要なポイントは「可換」という概念だ。一口に言うと、「可換」とは射 f と g の動作がまったく一致するということだ。集合の圏についていえば、写像 f と g の定義域が一致し、定義域の要素の関数による値がまったく一致するということだ。つまり任意の x ∈ A について f (x) = g (x) ということだ。一部が等しいということではなく、すべての点で f と g は動作が一致していなければならない。

つまり、f : A -> B, g: B -> C, h : A -> C のとき h が g . f と可換である、すなわち、h = g . f であるためには、h と g . f は同じ domain A と同じ codomain C を持ち、x ∈ A であるすべての x について h (x) = (g . f) (x) でなければならないということだ。圏論で使用される様々な射と対象の関係を表した図式は「可換」であるということの意味を考えておかないと理解できない。

対象と射のモデルとしては集合と写像を使い、射の可換の意味に注意して読めば、高度な数学の知識がなくても圏論の議論を理解するのは不可能ではない。さらに、集合と同じように、圏論も数学を学ぶときに最初に習得しなくてはならない知識の一つになるのではないかとすら思える。
[PR]
by tnomura9 | 2014-07-21 13:31 | 圏論 | Comments(0)

単純な双対の例

圏 C の射 f : A -> B が mono である条件は、任意の対象 C, 射 g : C -> A, h : C -> A について

f . g = f . h ならば g = h

が成立する事だ。ところで圏 C の双対圏(逆圏) COP を考えると、COP の対象は C と同じで、射の向きが逆になるから、COP の f, g, h に相当する射はそれぞれ、f' : B -> A, g' : A -> C, h' : A -> C となる。また、合成射 f . g に対応する COP の合成射は合成の順序が入れ替わるから g' * f' になる。

そうすると上の mono の定義の圏 COP における表現は、

圏 COP の射 f' : B -> A が「 mono の双対」である条件は、任意の C, g' : A -> C, h' : A -> C について、

g' * f' = h' * f' ならば g' = h'

が成立する事だということになる。これは 圏 C の射 f が epi である条件と同じになる。つまり圏 C の射 f : A -> B が mono である場合、圏 C の双対圏 COP の f の双対となる射 f' は epi であることを示している。したがって、圏 C の射 f が mono である事を使って証明された定理は、その双対圏 COP では、f の双対である f' が epi である場合にその双対となる命題が成立する事が分かる。

話が抽象的で分かりにくいので、まず、圏 C の射 f : A -> B と射 g : B -> C について、次の簡単な定理を証明してみる。

定理
g . f が mono であるなら、f は mono である。

証明
いま、h, k : D -> A として、f . h = f . k と仮定する。すると g . f . h = g . f . k である。一方 g . f は mono であるから h = k である。ゆえに f . h = f . k のとき h = k であるから、f もまた mono である。

この定理の命題を圏 C の双対圏 COP の命題に翻訳してみる。すると、f |---> f', g |--> g', g . f |--> f' * g', mono -> epi だから、

f' * g' が epi であるなら、f' は epi である。

圏 C と圏 COP は射の向きを反対にしただけだし、上の証明の内容をすべて双対に翻訳すると、定理の双対は圏 COP で成立する事が分かる。

ところで、圏 C に epi の射が存在すれば、圏 COP にはその双対である mono 射が存在するので、上の 圏 C における mono の証明は、圏 COP でも可能であるから。つぎの定理が成立する。

f' * g' が mono であるなら、g' は mono である。

これの双対を作ると、

g . f が epi であるなら、g は epi である。

という命題になり、これは圏 C における定理として成立する。蛇足だが、上の命題を圏 C で証明してみよう。

f : A -> B, g : B ->C, h, k : B -> D について、h . g = k . g と仮定すると、h . g . f = k . g . f である。一方 g . f は epi であるから h = k となる。h . g = k . g を仮定すると h = k であるから、g は epi である。

ちなみに、この証明の双対は次のようになる。

g' * h' = g' * k' と仮定すると、f' * g' * h' = f' * g' * h' である。一方 f' * g' は mono であるから、h' = k' となる。g' * h' = g' * k' を仮定すると h' = k' であるから、g' は mono である。

このように圏に関する定理の双対は証明しなくても定理となる場合があることが分かる。つまり、

g . f が mono であるならば f は mono である。

が定理ならば、その双対命題である、

f . g が epi であるならば f は epi である。

も定理であるということだ。
[PR]
by tnomura9 | 2014-07-20 14:12 | 圏論 | Comments(0)

圏論では射の中身もみえない。

今日の記事は参考書を土台にしている訳ではないので誤解が含まれているかもしれないが、双対について考えているうちに思いついたので書いてみる。

圏論と集合を比較する上でポイントとなるのが、圏論の external な立場だ。集合では集合の要素の振る舞いが重要な関心事になるが、圏論では対象の内部の要素については一切触れない。mono や epi などのように対象の内部が問題になる場合でも、それについては全て射の関係性で表現する。

最初は戸惑うが、対象の内部に立ち入らないで済むというのはなかなか便利で、慣れてくると、対象をひとつの点や丸のようにイメージするようになる。すると、関手の対象関数といっても、対象の丸と丸を結ぶ単なる矢印でイメージできるのが快適に感じられるようになる。その矢印がどのような写像になるのかなどと余計なイメージをする必要がなく、イメージ的にはただ単に対象と対象を対応づけるだけだからだ。

そうしているうちに内部の隠蔽ができるのは対象だけでなく、射も同じように考える事ができるのに気づいた。整数の集合が、2乗の関数で平方数に写像されるなどの関数の性質は、集合すなわち対象の要素が記述できなければ意味がないからだ。圏論では対象の中を覗く事はできないので、対象と対象を結ぶ射についても、その性質は隠蔽されているという事になる。

これの何が便利かというと、前回述べた「双対」のようなものも、集合の圏 Set の射は何かという事を考えたので、その双対圏の SetOP の射のイメージ作りがたいへんだったのだ。どうせ、射の中身は見えないのだから、射そのものについて考えればもっと簡単に双対の性質を考える事ができた。

たとえば、圏 C の射 f : A -> B の双対である圏 COP の射 g : B -> A を考える。また、h : B -> C の双対が k : C -> B であるとする。この場合合成射 h . f : A -> C の双対はどのようにして作られるのだろうか。

h と f の双対はそれぞれ k : C -> B と g : B -> A だからこれを合成する方法は g . k : C -> A しかない。そうして、h . f : A -> C と g . k : C -> A を比べるとこれは確かに互いに双対になっていることがわかる。このとき圏 C から 圏 COP への射関数T は T : h . f |---> g . k のような射の合成の順序を入れ替える操作になる。

これは、SetOP の射の実体はどういうものかなどと苦労してイメージを作るよりもずっと簡潔に考える事ができる。どうせ射の中身は見えないのだから、射の向きを反対にした場合どういう事が起きるかという事だけを考えればいい。向きを換えた射の中身を詮索する事は不要なのだ。

集合になれた考え方だとつい向きが逆の射はどのような関数なのだろうかと射の中身を詮索してイメージを複雑にしやすいが、射の中身も見えないのだと割り切ると別の考え方ができるようになる。圏論が分かりにくいと考えるのは、こういった対象や射の中身を見ないやり方がなんとなく頼りなく思えるからなのではないだろうか。
[PR]
by tnomura9 | 2014-07-17 07:49 | 圏論 | Comments(0)

双対 dual

1. 双対 dual とは

圏論では双対が重要な役割を果たしているらしいが、双対とは一体何なのかは常識なのか参考書には詳しくはかかれていない。そこで、論理学の双対がわかりやすそうだったので調べてみた。論理学の双対についての Wikipedia の記述は次のようになる。
論理の双対

命題を論理式として表したとき、論理和 ∨ と論理積 ∧ とをすべて入れ替え、全称記号 ∀ と存在記号 ∃ とをすべて入れ替えたものをもとの論理式の双対といい、入れ替えて得られた命題をもとの命題の双対命題と呼ぶ。双対の双対はきっちり元に戻る。

元の論理式が証明可能ならばその双対の否定が証明可能であり、ある論理式の否定が証明可能ならば、その論理式の双対が証明可能になる。
要するに数学的構造の要素の何かを入れ替えても変わらない性質があるということだ。論理の双対のばあい元の命題が証明可能なら、細かい証明をやらなくても双対命題の否定の証明が保証される。手抜きができるというわけだ。

しかし数学的対象に限っても双対には多様なものがあって、入れ替えるという操作以外には共通点がなさそうに思われる。双対という名前が出てきたら、単に「いれかえちゃえ!」と考えるとよいのかもしれない。この漠然とした双対の高度な抽象性が双対をつかみ所のないものにしているのだろう。

2. 圏の双対 ---- 双対圏 dual category

それでは、圏の双対とはなんだろうか、それはある圏 C の矢印を全部反対にした双対圏 dual category をつくることだ。つまり、圏 C の対象を Ci、対象 Ci から Cj への射を fi j とすると、

fi j : Ci -> Cj

を、

j i : Ci <- Cj

に置き換えてしまう。このことを『圏論による論理学 高階論理とトポス』では次のように文章で定義している。
定義(双対)

S を圏についての何らかの命題とする。このとき、S 内における dom を cod に、cod を dom に変え、また g . f を f . g のように矢の合成順序を変えた命題は、命題 S の「双対」 (dual) と呼ばれ、記号 SOP で表される。

また命題 SOP によって記述されている概念は、対応する命題 S によって記述されている概念の「双対」 (dual) と呼ばれる。

定義(双対圏)

C を圏として、この C から得られる次の条件 (1) ~ (3) をみたす圏は、C の双対圏 (dual category) と呼ばれ、記号 COP で表される。

(1) COP の対象の全体は、C の対象の全体と同じである。
(2) COP の矢の全体は C の矢の全体と同じである。
(3) COP で f : A -> B であることは、C で f : B -> A であることと同等である。

なお上記した二つの定義から直ちに明らかなように、命題SがCで成立することと、SOP が COP で成立することとは同等である。たとえば、Cでの終対象は、COP では始対象である。

3. 集合の圏 Set の双対圏 SetOP

これから書くことは参考書にはなく、管理人の単なる意見なので聞き流してほしいが、こうすれば双対圏のイメージが作りやすいのではないかという提案だ。

集合と写像の集まりを圏にするには少々条件の整備が必要だった、圏 Set の射 f の domain を集合 A、codomain を集合 B とすると次のように表記できる。

f : A -> B

しかし、この場合写像 f が圏の射となるためには、射の合成可能という条件を満たす必要がある。射 f の codomain A と射 g の domain A が一致する場合、

g . f

という合成関数を作ることができるが、これは f とは別の h という関数の codomain が A であれば、やはり、

g . h

という合成関数が作られないといけない。f の像と h の像は一般に異なるから、g に接続されるどのような関数 k についても g . k が合成できないないといけない。したがって、当然 g の定義域は domain A と一致しなくてはならない。つまり、Set の射はどれも全域関数である必要がある。しかし、codomain の方にはそのような制約はなく、f の像は f の codomain の部分集合であれば、全射でなくても一向構わない。

したがって、

f : A -> B

の矢の向きをひっくり返せといわれても、全単射なら逆写像に置き換えられるかもしれないが、どのような射もひっくり返すわけにはいかない。f の domain は A と一致するが、f の像は B の部分集合であるだけなので、f の矢頭だけを付け替えるわけには行かない。

しかし、いい方法がある。

f : A -> B

の写像はそのままにして、SetOP の f に対応する射 g の定義を次のようにするのだ。

dom g = B
cod g = A
g = f

つまり、写像の f はそのままに、domain と codomain を逆転するのだ。そんなことをしたら g B のように g による B の射はどうするのだ、f は全射で B に写像しているわけではないという意見もあろう。しかし、圏論の世界では g は別に写像である必要はないのだ。集合 A から集合 B への写像 f を、domain B から codomain A への射とみなしても構わない。写像という傘を反対に置いたというイメージだ。

それは圏論の立場では、射 g の domain と codomain が定義できればいいだけだからだ。 dom g = B であって、cod g = A であって、さらに、g : B -> A と h : C -> B の合成射 g * h : C -> A が定義できれば g の実体が f であっても別に構わない。

ほんとうにこのような合成射が定義できるのかどうか見てみよう。まず g と h の元となる Set の射 f と k を考える。

f : A -> B
k : B -> C

このとき k . f : A -> C が定義できる。また、このとき圏 SetOP の射 g と h は次のようになる。

g : B -> A
h : C -> B

したがって、g と h の合成は g * h : C -> A となる。これは k . f : A -> C の domain と codomain を入れ替えたものだ。このとき、 g * h と k . f は同じ関数を表している。つまり、

g * h = k . f

だ。合成射 g * h : C -> A は実際は集合 A から集合 C への写像 k . f : A -> C であるが domain は C で、codomain が A である。つまり圏 COP の合成射 g * h は 写像 k . f を逆さにしたような形になっている。これは圏 COP の射の定義に添っていることになる。

このように圏 Set の双対圏 SetOP の射は写像ではなく、写像をひっくり返したものになる。このような定義でも上で述べたように、射は domain と codomain をもち、射の合成を射の定義と整合的に作ることができることがわかる。ただし Set の双対圏 SetOP の射は集合で言う写像にはならないことがわかる。

4. まとめ

双対の概念は分かりづらいが、これを利用すれば証明をしなくてはならない命題の数が半分になる。また、圏論の推論には双対を利用しているものが数多くあるので、双対についてのイメージを持っておくことが大切だ。また、圏論の双対は矢印を反対方向にするだけなので、証明に使われた図式の矢印を全て反対方向にした図式はすべて証明済みと考えることができる。便利なものだ。
[PR]
by tnomura9 | 2014-07-14 21:25 | 圏論 | Comments(0)

cone と limit

1. コーン cone

『圏論による論理学 高階論理とトポス』 清水義夫著 によると、コーン (cone) の定義は次のようになる。

Cを圏とし、DをCの部分集合とする。その上で、Cの対象 X と D の各対象 Di について、 fi : X -> Di が定まっており、かつ D の任意の射 dij : Di -> Dj について次の可換があるとき、対象 X と { fi | fi : X -> Di, i ∈ I } なる矢の集合は、D へのコーン (cone) と呼ばれる。

dij . fi = fj

ただし、
fi : X -> Di
fj : X -> Dj
dij : Di -> Dj

まず部分圏という用語について考えてみる。圏は対象と射から構成されており、射には結合則をみたす射の合成と、恒等射があるという制限がある。この場合、圏は射の合成に関して自己完結的であり、圏の射を合成した結果もやはりその圏の射である。部分圏とは、ある圏の一部の対象と射を取り出したとき、それが圏をなしており射の合成がその部分圏で自己完結しているようなものを言う。圏の中に、部分的な圏が含まれている状態だ。上の定義では C が元々の圏で、Dがその部分圏だ。

コーンとは、Cの対象 X をひとつ取り出して、圏Dの全ての対象への射 fi を考えたものだ。ただし、この射は Di の射 dij について次の可換式が成り立っている必要がある。

dij . fi = fj

これがどういう意味を持っているのか考えてみる。dij は単に Di -> Dj 型の射を表しているにすぎない。Di -> Dj 型の射は複数ある事が普通だから dij はその中の射のひとつを代表している。

fi は X -> Di 型の射だ。これは仮定からひとつの射に限定される。また、対象 X の fi による像は対象 Di の部分集合になる。そうして、fj についても同じことが言える。

fi と fj はドメインが同じなので、fij : Di -> Dj という射を定める事ができる。なぜなら、任意の X の要素 x について、

fi x |--> fj x

という対応関係が生じるからだ。この対応関係によって生じる射を fij とすると、

fij : Di -> Dj

である。

このとき次の可換式が成立する。

fij . fi = fj

ところで、射 fi による対象 X の像は対象 Di の部分集合であるから、fi と dij の合成は、dij の定義域に制限をかけるという意味合いもある。したがって、コーンを定義する可換式は、dij の定義域に fi による制限をかけると、 fij と同じ射になるということを示している。

また、この可換関係が全ての dij について成り立っているという事は、対象 Di から対象 Dj への全ての射について考えたとき、X からの射 fi と fj によって制限された Di と Dj については全ての射に共通する fij が含まれているということになる。

この事情は X と全ての圏 D の対象 Di について成立するから、対象 X と射の集合 { fi } で構成されるコーンは、圏 C と 圏 D のある構造を反映しているといえる。コーン (cone) という名称は頂点 X から圏 D へ射が張り巡らされている様子から命名されたのではないだろうか。

2. リミット limit

リミットの定義については次のように記載されている。

C を圏とし、D を C の部分圏とする。また X と { fi | fi : X -> D i, i ∈ I } を D へのコーンとする。その上で、Y と { gi | gi : Y -> Di, i ∈ I } なる D への任意のコーンについて、ある射 h : Y -> X が一意的に存在して、 下図(図を書くのが面倒なので可換式で代用する)が可換となるとき、X と { fi | fi : X -> Di なる D のコーンは、D の「リミット」(limit) と呼ばれ記号 <lim D (これもプログでは表記できなかった、原著を参照してほしい)で表される。

コーン Y とコーン X の可換式

fi . h = gi
fj . h = gj

Y と X はいずれも D のコーンである事の可換式、

dij . gi = gj
dij . fi = fj

要するに、圏 C と圏 D について、対象 Y によるコーンを 対象 X によるコーンに変換する射 h があるということ。コーン間の変換をおこなう射 h は複数個存在する事もあるが、そのうち他のコーンからのこのような変換を行う射 h が一意的に定まるコーンがリミットであるということだ。

一意的な射という考え方は対象の積の定義でも出てきた。圏論ではよく出くわす言い回しだ。対象 A から 対象 B へのある性質を保存するような射は複数あるのが普通だが、他の全ての対象からの射がそれぞれ一意的なものはその性質を最も普遍的にあるいは後半に保存する対象や射であるという意味だろうか。

個々のコーンは 圏 C と 圏 D のある構造を表しているが、その最も広範なものあるいは本質的なものがリミットであると考えてよいのだろうか。

3. リミットの例

リミットの意味が分かっているのか甚だ不安だが、参考書に対象の積の例がでていたので見てみる。対象の積は対象の積となる対象 A × B とそれの対象 A への射影 π1 と対象 B への射影 π2 から構成されている。これは対象 A と 対象 B からなる部分圏を考えると、ひとつの対象 A × B と射の集合 { π1, π 2 } で形成されているからこれはコーンである。A × B の要素 は A の x と B の y に写像され、このとき A から B への写像は x |--> y になる。

A <--{ π1 }-- A × B --{ π2 }--> B

この圏で、対象 C から対象 A への射 f と 対象 B への射 g があるとき次のような図式がかけるから、これもまた、対象 C と射の集合 { f, g } で構成されるコーンである。

A <--{ f }-- C --{ g }--> B

この場合 C の要素を c とすると、c |--> f c, c |--> g c で、A から B への射は fc |--> g c となる。

このとき定義から射 h : C -> A × B が一意的であるから、A × B と { π1, π2 } からなるコーンはリミットである。どんな対象 C と { f, g } のコーンも対象の積によるコーンに変換できるから、対象の積によるコーンは対象の積の振る舞いを示すパターンのうち最も広範で基本的なものであるという事ができる。

コーンやリミットの考え方は抽象的なので意味付けが難しいが、ここで書いたようなことを踏み台にしてさらに学習をすすめるしかない。
[PR]
by tnomura9 | 2014-07-13 08:54 | 圏論 | Comments(0)