1997
年度後期 数学概論B 自己参照の数理
資料シラバスより
種々の生命的・人間的状況の言明に頻出する自己参照性は、その本質を素朴に 理解 しようとするとき混乱を引き起こすことが多い。この講義では、いくつか の自己参 照性を現代数学の言葉により分析する。これを通して現代数学の重要 な役割の一つ、
すなわち日常的な言葉や考え方だけでは捕捉し難いことを明晰 に考察することを可 能にするという役割を、理解させることを目指す。
目次
1.
静的自己参照•
自己参照の図示（有向グラフ・サイクル）•
形の自己参照(
フラクタル) 2.
動的自己参照•
生成の自己参照（代謝系・閉包作用素・束）•
動作の自己参照（プロセス・再帰）•
作用の自己参照（チューリング機械・計算不能問題・Lawvere
の不動点 定理）3.
認知的自己参照•
主張の自己参照（ゲーデル数・不完全性定理）•
知識の自己参照（共通知識・非有基的集合）•
形式化できない自己参照（認知の自己参照）目 次
1 グラフ 2
1.1 グラフの基礎概念. . . . 2
1.1.1 定義 . . . . 2
1.1.2 図示 . . . . 2
1.1.3 道とサイクル. . . . 3
1.1.4 鎖とサーキット . . . . 3
1.1.5 強連結性と連結性 . . . . 4
1.2 言及としての辺. . . . 4
1.3 例 . . . . 4
1.4 グラフの用語 . . . . 5
2 木グラフ 6 2.1 定義. . . . 6
2.2 実世界に現れる木の例 . . . . 6
2.3 木の頂点の標準的ラベル付け. . . . 6
2.4 木構造の記号列による表示法. . . . 7
2.5 木の図示法 . . . . 7
2.5.1 木構造の入れ子箱による表示法 . . . . 7
3 印付きグラフの方程式 8 3.1 印付グラフ . . . . 8
3.2 印付きグラフの解きほぐし. . . . 8
3.3 印付グラフのunfoldingの相互関係 . . . . 8
3.4 グラフの接ぎ木，印付グラフ木の代入 . . . . 8
3.5 印付きグラフの方程式 . . . . 9
3.6 フラクタル図形の木構造 . . . . 9
4 グラフ方程式の例 10 4.1 変化の型 . . . . 10
4.2 分裂・合成の型. . . . 10
4.3 再帰的定義の型. . . . 10
4.4 連立方程式の例. . . . 10
5 素朴集合論 11 5.1 基本表現 . . . . 11
5.2 ブール演算 . . . . 11
5.3 ブール演算の代数的法則 . . . . 12
5.4 集合論の公理 . . . . 12
1 グラフ
1.1 グラフの基礎概念
1.1.1
定義一つのグラフは頂点と辺から成る．各辺には始点と終点と呼ばれる頂点が 対応している．始点と終点が同一である辺はループとよばれる．始点と終点 は，その辺の端点とも呼ばれる．
辺
e
の始点がa,
終点がb
であるとき，e
はa
からb
への辺であるとい いe : a → b
またはa → e b
と書く．一方から他方への辺が２つ以上ある２頂 点があるグラフは多重であるという．そうでないグラフは単純であるという．この講義ではとくにことわらない限りグラフは単純であるとする．単純グラ フでは，aから
b
への辺はa
とb
で決まるのでこれを(a, b)
と書き，さらに「(a, b)という辺がある」を
a → b
と略記することがある．1.1.2
図示頂点数の少ないグラフは，平面上に次のように図示することができる．各 頂点ごとに平面上の点をうつ．辺ごとに，その始点から終点へ矢印を描く．多 重なグラフについては，矢印に辺の名前を付けておく必要がある．そうでな い場合も辺に名前を付けておかないと不便なことが多い．また，同じグラフ
を図示する方法は無数にある．次の２図は同じグラフを表示している．右図 のようにグラフをなるべく簡単に見えるように図示することが好ましいが，
それは必ずしも容易にできるとは限らない．
a
b c
d
d e
f
3 2
1
4 4
5
6 7
a
b c
e f
3 2
1
5 6
8 7 8
9 9
図
1:
同一グラフの２つの図示の例：9
はループ, 174, 1564, 24, 24864
などはa
からe
への道, 1268
は道ではない鎖, 486
はサイクル, 127, 756
はサイクルではない サーキット.
このグラフは単純である．1.1.3
道とサイクル１個以上の辺の有限列があって、各辺の終点が次の辺の始点となっている とき，この列をグラフの道と呼ぶ．道の始点とは、最初の辺の始点のことを いい、終点とは、最後の辺の終点のことをいう。道
γ
の始点がa
，終点がb
であるときγ
はa
からb
への道であるという．aからb
への道があるときa → ∗ b
とかくことがある．図1
で，174, 1564, 24, 24864
などがa
からe
への 道の例となる．ある頂点からそれ自身への道のことをサイクルと呼ぶ．図
1
のグラフでは486
がサイクルとなっている．サイクルのないグラフを無循環グラフ(acyclic graph)
という．1.1.4
鎖とサーキット１個以上の相異なる辺の有限列があって、隣同士の辺は端点を１つだけ共 有するとき，この列をグラフの鎖
(chain)
と呼ぶ．鎖の端点とは、最初の辺の 端点で次の辺の端点でないもの，または最後の辺の端点で直前の辺の端点で はないものをいう．上のグラフで1268
はb, e
を端点とする鎖であるが，道 にはなっていない．端点が重複する鎖をサーキットという．上のグラフでは，124,
756
がサイ クルではないサーキットである．いうまでもなく，道は鎖であり，サイクル はサーキットである．サーキットがないグラフのことを非輪状(acircuit)であるという．グラフが 非輪状であるということは，２つの頂点の間の鎖は多くても一つしかない，
ということと同じことである．これは後に扱う木グラフと本質的には同じも のとなる．
1.1.5
強連結性と連結性どの２頂点
a, b
についても，aからb
への道が存在するとき，グラフは強 連結であるという．どの２頂点間にも，それらを端点とする鎖があるとき，グ ラフは連結であるという．強連結ならば連結であるが，逆は正しくない．実際，図１のグラフは連結 であるが強連結ではない．
1.2 言及としての辺
a → b
によりa
がb
に直接言及すると考える．このとき•
道は間接的な言及を与える言及列．•
ループは直接的な自己言及.•
サイクルは間接的な自己言及を意味する．強連結であることは，すべてがすべてを間接的に言及すること を意味する．非輪状なときは，間接的な言及は，ただ一つの言及列で実現さ れていることをしめす．
1.3 例
道路網 頂点は交差点，辺は道（一方通行でないときは方向が逆の２つの辺を 与える，図では矢印のない辺で表す．）これは強連結でないと困る．
ガス管 頂点はガス管の分岐，辺の向きは供給源から遠ざかる方向を与える．
こういう言い方で方向が決まるのは，acircuitで連結であるからである．
（ガス配管ではサーキットの存在は許されない．）どの頂点も入次数は１ である．別の言葉でいうと，これは木グラフである．
親子関係 頂点は人間，a
→ b
はa
がb
の親であることを表す． どの頂点も 入次数は２である．サイクルはありえないがサーキットはありえる．支配関係
a → b
「aがb
を支配する．」 伝達関係a → b
「aがb
に伝達する．」因果関係
e → e 0
「事件e
が事件e 0
を引き起こす．」論理関係
P → Q
：「命題P
を仮定して命題Q
が示せる．」このグラフは推移 的である．a→ b, b → c
ならばa → c
である．言及関係
a → b
：「a
がb
に言及する．」1.4 グラフの用語
頂点の入次数(indegree)というのは，その頂点に入ってくる辺の数のこと をいい，出次数
(outdegree)
というのは，その頂点から出ていく辺の数のこと をいう．出次数が0
の頂点は葉(leaf)あるいは終点と呼ばれる． 入次数が0
の頂点は湧点あるいは入点と呼ばれる．2 木グラフ
2.1 定義
グラフが木グラフ(tree)というのは，
•
根(root)と呼ばれる入点があり，•
他のどの頂点へも根からただ一つの道がある ということである．根以外のどの頂点もただ一つの辺の終点となるがその辺の始点を，親頂点 という．また，その頂点を始点とする辺の終点のことを子頂点という．子頂 点は必ずしも存在しない．
2.2 実世界に現れる木の例
1.
トーナメント（２分木(binary tree)）
2.
命令系統［軍隊組織、官僚組織］3.
分類システム（住所システム、ファイルシステム、図書分類）4.
構文木（生成文法）5.
代数式6.
集合2.3 木の頂点の標準的ラベル付け
各頂点の子の数は有限であるような木に対して、各頂点にラベルとして数 のリストを次のように対応つけることができる。
1.
各頂点の子に１から通し番号付ける2.
根には空リスト[]
を対応させる。3. [n 1 , · · · , n k ]
というラベルのついた頂点のm
番目の子には[n 1 , · · · , n k , m]
というラベルと付ける。
2.4 木構造の記号列による表示法
1.
葉には記号•
を対応させる。2.
頂点v
の子の各々に記号列s 1 , s 2 , · · · , s m
が対応しているとき、v
には(s 1 s 2 · · · s m )
を対応させる。この操作により、木のすべての頂点に唯一つの記号が付く。根に対応する記 号列を，この木の標準的記号表示という。記号表示から木が再構成できる。
この表示法は，木の合成法も記述している：
T 1 , · · · , T n
があるとき，それ ぞれをs 1 , · · · , s n
と表示したとき，表示(s 1 , · · · , s n )
を持つ木を(T 1 , · · · , T n )
と表す．これにより，任意個数の木の合成が定義される．この講義で扱う木 は主に，各頂点の子供の数は有限である．こういう木を有限分岐の木という．(前回資料の § 2.6
以降は，以下に差し替えてください．)練習問題 次の記号表示の木を描け。
1. (( • • ( • ))( •• )( • )) 2. ((((( •• ) • ) • ) • ) • )
2.5 木の図示法
樹状図
入れ子図
•
箱の平面配置 （図詳しくは後述）•
区間の直線配置 記号表示• Spencer-Brown
式•
括弧式（リスト）表示 （詳しくは後述）•
集合表示2.5.1
木構造の入れ子箱による表示法1.
葉には空箱を対応させる。2.
頂点v
の子の各々に箱s 1 , s 2 , · · · , s m
が対応しているとき、v
にはこれ らを入れた箱s 1 , s 2 , · · · , s m
を対応させる。この操作により、木のすべての頂点に入れ子の箱唯が対応する。根に対応す る箱を，この木の入れ子箱表示という。入れ子箱表示から木が再構成できる。
練習問題 次の入れ子箱に対応する木を求めよ。
3 印付きグラフの方程式
3.1 印付グラフ
木グラフは根という特別な頂点を持っている．グラフにはそういうものは 一般にないが，一頂点を選び印しを付けたものを印付グラフといい，その選 ばれた頂点をその印付グラフの始点と呼ぶ．当然のことであるが一つのグラ フに対して印の付け方は頂点の数だけある．
3.2 印付きグラフの解きほぐし
印付グラフ
(G, v)
には解きほぐし(unfolding)と呼ばれる木T (G, v)
が対 応する．この木の頂点は，始点から始まる道（空の道も含む）である．その 辺は，２つの道の組(γ 1 , γ 2 )
であってγ 2
はγ 1
の終点からさらに一つの辺を たどってできる道である．これが木となることは当たり前である．3.3 印付グラフの unfolding の相互関係
一つのグラフ
G
に対して，各頂点v
ごとに印付グラフ(G, v)
の解きほぐ しT v
がある．これらは，T v = (T w ) v →
Gw ∀ v
という関係式を満たす1
．3.4 グラフの接ぎ木，印付グラフ木の代入
一つのグラフの頂点に他のグラフのある頂点を「接ぎ木」して新しいグラ フを作ることができる．この操作で接がれる頂点を接点と呼ぼう．
一方の印付きグラフ
G
の接点x
が終点であり，他方の印付きグラフH
の 接点が始点a
であるとき，この操作をG
に印付グラフH
を「代入」したも のと考えることができる．印付き
G
の終点のいくつかにx
というラベル がついているとき，これをG(x)
と書きグラフ多項式という．このラベルのついた終点の各々にH
と同じ 印付グラフを接ぎ木したものをG(x = H)
とかく．一般に終点のいくつかに1グラフの等号はグラフ同型を意味する
{ x 1 , · · · , x n }
のいずれかのラベルがついているとき，G(x1 = H 1 , · · · , x n = H n )
により，代入を同時に行ったものを表す．3.5 印付きグラフの方程式
グラフ方程式は，グラフ多項式
G(x)
に対してx = G(x)
で与えられ，その解とは，印付きグラフH
で
H = G(x = H )
を満たすもののことをいう．両辺の頂点数を考えると，H は無限グラフでな ければ ならないことは明らかである．
連立グラフ方程式は，グラフ多項式の族
G i (x 1 , · · · , x n )(1 ≤ i ≤ n)
に よってx i = G i (x 1 , · · · , x n ) 1 ≤ i ≤ n
と表わされる．この解とは印付きグラフの族H 1 , · · · , H n
でH i = G i (x 1 = H 1 , · · · , x n = H n ) 1 ≤ i ≤ n
を満たすもののことである．定理 どのグラフ多項式
G(x)
についても，方程式x = G(x)
は少なくとも 一つの解を持つ．その解としては木によって与えられる．同様に連立グラフ方程式も解を少なくとも一つ持ち，その解は木によって 得られる．
略証 グラフ多項式
G(x)
に対して，xというラベルのついた終点を印と同 一視したグラフをG e
と書く．この印付グラフを解きほぐした木をT
とする と，これはT = G(x = T )
を満たす．3.6 フラクタル図形の木構造
フラクタル図形のあるものは木の骨組みを持っている．それらは
x = T (x)
という形で与えられる．ここで
T
は有限木である．4 グラフ方程式の例
4.1 変化の型
x = (x).
メタ定理
x = f (x)
の形式解はx = f ∞ (x 0 )
で与えられる.
縮小写像（この形式解の実現法の例）4.2 分裂・合成の型
x = (xx).
同じものを
x
を２つ合体すると，同じx
になる．xを２つに分解すると，同 じx
が２つになる．•
無限２分木•
２文字のなす語を頂点とする木．•
実数と無限２分木•
区間縮小法•
２つの変換による実現•
カントール集合4.3 再帰的定義の型
x = (ax).
4.4 連立方程式の例
x = (xy), y = (yxy).
5 素朴集合論
集合論の基本的な言い回しと，その略記法を復習する。
集合論の魔法は，どんな「こと」でもそれを「もの」として語ることを可 能にすることだ．これは内包性公理と呼ばれ，何々であることが，そうであ るものの集まりというモノで表現されることを主張する．しかし「ことをも のとすること」だけは「もの」にできないというのがラッセルの逆理である．
5.1 基本表現
• x
は集合A
の要素である．x
はA
に属する．このときx ∈ A
とかく．• B
はA
の部分集合である．B はA
に含まれる．これをB ⊆ A
とか く．Aの部分集合の全体をA
のべき集合といいpow (A)
と表す．•
要素がない集合というものも便宜上考えてそれを∅
と書き空集合と呼ぶ．•
要素がx
かy
のどちらかである集合をh x, y i
と書く．•
性質P
を持つものから成る集合を{ x P
}
と書く．これを性質P
の外延とよび，性質
P
をこの集合の内包と呼ぶ．{
x x / ∈ x
}
を集合 と考えると矛盾する(Russel
の逆理)．•
集合X, Y
各々の要素x, y
に対して，順序対h x, y i
と呼ばれるものが定 義される．h x, y i
とh x 0 , y 0 i
が同じであるとはx = x 0
とy = y 0
がなり たつことをいう．直積集合X× Y
は順序対の全体を表す．•
集合X
の各要素に対してY
の要素が一つ定まっているとき，その定 まり方を写像という．それについて議論するために普通それに名前を付 ける．f という記号を使うことが多いが何でもよい．f: X → Y
により，f
がX
からY
への写像の名前であることを表す．写像f
によりX
の 要素x
に対応するY
の要素をf (x)
と表す．5.2 ブール演算
A, B
をX
の部分集合であるとする．•
集合和:A∪ B.
少なくとも一方に属するものの集合．•
集合積:A∩ B.
双方に同時に属するものの集合．•
集合差:A\ B. A
に属してB
に属さないものの集合．•
補集合:A c := X \ A. A
には属さないX
の要素の集合．5.3 ブール演算の代数的法則
•
分配法則：A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
• De Morgan
の法則:(A∪ B) c := A c ∩ B c , (A ∩ B) c := A c ∪ B c ,
•
ベン図法について5.4 集合論の公理
ラッセルの逆理から集合論を「救う」ために多くの研究がなされた．その
中で
Zermelo-Fraenkel (ZF)
による公理的集合論が一応の解決とされている．しかし，集合論の「基礎付け」（無矛盾性）の証明はできていない（というよ りも，無矛盾性の証明は通常集合論を用いるので，集合論自身の無矛盾性は 証明のしようがない．）いかは
