<   2015年 11月 ( 7 )   > この月の画像一覧

OneNote

Microsoft surface pro 4 を衝動買いした。しかし、買ったものの何に使うのか正直困惑した。ベッドに横になってネットサーフィン(死語)しようと思っても少しでも画面に手が触れると他の機能が起動してブラウザが見えなくなってしまう。キーボードカバーはカバーなので膝の上に置いてタイプするのが難しい。


ところが、いろいろといじっているうちに、ペンののボタンを押すと、いきなり OneNoteというアプリケーションが起動した。説明書もないし何に使うのかもよく分からない。ところが、ネットの記事や設定メニューのヘルプをしらベていたらこれが優れものだった。


一言で言うと、ペイントソフトのシートを何枚も束ねたノートブックのようなものだ。画面のどの位置にも活字を入力できるし、その上からペンで図を描くこともできる。活字の入力はsurface pro の手書き入力の効率がいいので、キーボードを外してしまってペン1本で入力してもストレスは感じない。まるで紙と鉛筆でアイディアを整理しているような感覚だ。


アイディアをまとめるのにワープロの文字情報だけでは不便なので紙に書いていたが、散逸しやすいので、後でワープロに打ち直していた。しかし、これならパソコンの中でずっと保存しておくことができる。写真やネットの情報も取り込めるようなので、使い慣れたら手放なせなくなるかも知れない。贅沢だが、0neNote を使うためだけに surface pro 4 を買うという選択枝もあるかもしれないと思った。


OnNote で作った図


d0038298_13340110.gif

[PR]
by tnomura9 | 2015-11-26 13:35 | 考えるということ | Comments(0)

自然数とそのべき集合の全単射はできないのか?

今から書くことは私見なので間違っているかもしれない。しかし、対角線論法の本質に関連しているように思ったので書いてみる。

1から3までの自然数の集合 A = {1, 2, 3} について、それ自身との直積 A × A から集合 {0, 1} の間で、ψ(x,y) : A × A -> {0, 1} を考えることができる。ψ(x,y) は複数考えられるが次のような演算表で考えるのが便利である。たとえば、ひとつの ψ(x, y) の演算表は次のようになる。

_ 1 2 3
1 0 0 0
2 0 1 0
3 1 1 0

ここで、A のべき集合を [0 0 1] のように表すことにすると、この時演算表の各行の数列は A のべき集合の要素を表す。例えば2行目の [0 1 0] は {2} を表している。従って、a が A の要素のとき、g(x) = ψ(a,x) という関数は A = {1, 2, 3} の各要素が a に対応する A の部分集合の要素であるか否かを表すことができる。すなわち g(x) は a に対応する A の部分集合と同一視できる。

この表について、対角線論法では ψ(x,y) から対角関数を作る。すなわち、Δ(x) = ψ(x,x) である。このとき、g(x) = ¬ Δ(x) = ¬ ψ(x,x) で表される関数は、A の要素 x に対応する A の部分集合が x を含まないことを示している。そこで g(x) に対応する a0 があると仮定すると g(a0) = ¬ ψ(a0,a0) = ψ(a0,a0) となり矛盾が生じる。従って ψ(x, y) には g(x) に対応する A の要素 a0 は存在しない。これはどのような自然数 n についても成立するので、結局自然数の集合とそのべき集合との全単射は存在しないという結論が得られる。

実際、上の演算表から g(x) を作ると g(x) = [1 0 1] となりこの演算表には現れない。3ビットの配列は、次のような8個の可能性があるが、どの3つを選んで演算票を作っても、それから作られる g(x) に対応する A の要素はない。

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

これは、当然といえば当然で、8個ある A の部分集合のうち 3 個しか演算表には使えないのだから演算表に表すことができない A の部分集合は必ず存在する。しかし、次のような演算表を考えてみたらどうだろうか。

_ 1 2 3
1 0 0 0
2 0 0 1
3 0 1 0
4 0 1 1
5 1 0 0
6 1 0 1
7 1 1 0
8 1 1 1

この演算表から ψ(x,y) : {1,2,3,4,5,6,7,8} × {1,2,3} -> {0,1} を考えると任意の {1,2,3} の部分集合に対応する a ∈ {1,2,3,4,5,6,7,8} を見つけることができる。これは n がどのように大きくても {1,2, ... ,n} の部分集合に対応する自然数を {1,2, ... , 2^n} の自然数の中に見つけることができるから、結局のところ自然数の部分集合全てに対し、それに対応する自然数を見つけることができるという対角線論法とは真逆の結論が得られる。

なぜこのようなことができるかというと、上の演算表は正方形ではないため、行の全ての数に対する対角関数を作れないからだ。対角線論法では対角関数が存在することから結論を導くが、上の長方形の演算表では対角関数は存在しない。

カントールの対角線論法では 0.100101100 ... という無限小数の一点が存在するという実無限の立場を取っているが、小数点下の数が無限に続く小数の一点をどうしてとらえるのだろうか。対角線論法で次々と対角線上の ψ(x,x) の値を調べていっても調べることができるのは常に有限な確定した値で、無限大の桁の値を得ることはできないのである。対角線論法で得られる演算表に属さない自然数の部分集合は、対角線論法のどの時点でも有限集合でしかない。結局のところ自然数を使って実数を無限に切り取っていってもその操作をやり終えることはできない。実無限は便利な概念ではあるが、それを自然数の拡張である無限小数で完全にとらえることはできないのだ。

このように考えると長方形の演算表の議論では、自然数と対応するのは全て有限集合であるが、対角線論法の正方形の演算表を使った議論でも議論で作られる演算表に含まれない集合は全ての段階で有限集合であることがわかる。長方形の演算表を使って議論しても、正方形の演算表を使って議論しても扱われているのは常に有限集合であると考えてよい。また、どちらも集合の要素の個数をどこまでも増やしていくことができるので、実質上の無限集合を扱っていると考えることができる。

したがって、対角線論法では正方形の演算表を仮定したため、どのような自然数についても演算表に載らない部分集合があるし、長方形の演算表を仮定するとどのような自然数の集合についてもその部分集合に対応する自然数を見つけることができる。矛盾しているようだが、無限の性質をどれだけでも大きい自然数を見つけてくることができることと定義すると、演算表の作り方で全く異なった結論を許容することができるのだ。無限に広がる2次元の平面の中には無限に大きい正方形も、無限に大きい長方形も同じように収めることができるからだ。このあたりの様子はユークリッド幾何学と非ユークリッド幾何学の関係に似ている。実際、コーエンの定理では、一般連続体仮説はZFC集合論からは独立しているらしい。

実無限は非常に便利な考え方だが、実無限と可能無限の間の関係性があいまいな気がする。無限については、ゼノンの一連のパラドックスに答えることができるようにならなければ、その本質を理解したことにはならないのではないだろうか。

[PR]
by tnomura9 | 2015-11-19 01:53 | 考えるということ | Comments(0)

ラッセルのパラドックスと不動点定理

ラッセルの集合が集合として存在できない理由は、不動点定理で説明できる。

集合 A の直積から {0, 1} への写像 ψ(x, y) : A × A -> {0, 1} について任意の g(x) : A -> {0, 1} が g(x) = ψ(a0, x) で表せると仮定する。つまり g(x) を A 自身の要素 a0 に対応させることができるとする。この a0 をインデックスという。この仮定のもとでは、任意の f(x) : {0, 1} -> {0, 1} について g(x) = f (ψ(x,x)) に対応する a0 が存在するはずである。この時、g(a0) = f(ψ(a0, a0)) = ψ(a0, a0) である。すなわち、f(ψ(a0, a0)) = ψ(a0, a0) となるので、ψ(a0, a0) は f の不動点となる。

ここで、集合の集合について ψ(x,y) は集合間の所属関係を表すとする。すなわち、ψ(a, b) = 1 の時は a ∈ b である。この時 ψ(x,x) は自分自身を要素として含むという述語である。ψ(a, a) = 1 なら a は自分自身を要素として含み、0 なら自分自身を要素としては含まない。そこで、g(x) = ¬ ψ(x,x) : A -> {0, 1} という関数を考える。この関数は x が自分自身を要素として含まない時は 1 となり、そうでない時は 0 となる。従ってこの g(x) に対応するインデックスを a0 とすると g(a0) = ¬ ψ(a0, a0) = ψ(a0, a0) となり矛盾する。従って、任意の g(x) : A -> {0, 1} が g(x) = ψ(a0, x) で表せるという仮定は否定される。すなわち自分自身を要素として含まない集合の集合を表すインデックスは存在しない。

数学の証明としてはこれでいいのかもしれないが、天から降ってきたように対角関数 ψ(x,x) が出現するのが気に入らない。もっと全体的な見通しのできる見方はできないものだろうか。

そこで、自然数の集合 A = {1, 2, 3} について ψ(x,y) : A × A -> {0, 1} を考えてみた。ψ(x,y) の作り方は簡単だ。任意の (x,y) について 0 か 1 を割り振ってやればいいだけだ。この関数は次のように演算表の形式で表現するのが一番わかりやすい。

_ 1 2 3
1 0 0 0
2 0 1 0
3 1 1 0

そこで、この演算表を眺めてみると、行の数値が a の時、その行の数列は関数 ψ(a, x) と対応していることがわかる。例えば、行 2 の場合は、ψ(2,1) = 0, ψ(2,2) = 1, ψ(2,3) = 0 である。また、この行の数列の取り方は他の行とは独立なので、どのような ψ(x, y) も作ることができることがわかる。

ここで、この演算表を元に g(x) = ¬ ψ(x,y) を作ってみる。演算表から対角関数 Δ(x) = ψ(x,x) は演算表の対角部分の値をとることがわかる。わかりやすいように関数の出力をリスト表示すると Δ(x) = [ 0, 1, 0 ] である。従って g(x) = [1, 0, 1] となるがこのリストと一致する行は演算表にはない。すなわち、g(x) はインデックスを持たないことがわかる。

これは当たり前といえば当たり前で、3ビットの数列は次のように8種類あるので、演算表の3行はそのほんの一部を表現しているにすぎない。

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

ラッセルのパラドックスはそれらの 8 種類を全て ψ(x,y) で表現できると仮定したために発生したのだ。実際にはこれらの数列のわずか 3 種類しか ψ(x,y) で表現できない。自分自身を要素としない集合の集合は、演算表の外にしか取れないのだ。

しかし、それにもかかわらず演算表の内部には自分自身を要素とする集合と要素としない集合の集まりは存在する。つまり、対角線部分の値をみると {1, 3} は自分自身を要素として含まない集合の集まりであり、{2} は自分自身を要素として含む集合の集まりだ。しかし、その集合を表す関数 g(x) = [1, 0, 1] を表すインデックスがないのだ。クラスがものの集まりであるのに、集合と考えると矛盾するのはそのためだ。

そう考えると、上のψ(x,y) の演算表にない行の数列(関数)は全てインデックスを持っていないのでクラスになることがわかる。例えば、「2 を含まない集合」のリストは [ 1, 0, 1 ] だが、この数列は演算表にはないので「2を含まない集合」は集合ではなくクラスである。

このように演算表にインデックスを持つもののみが集合で、それ以外はクラスであると考えるとスッキリするが、それでは演算表の中で集合の積や和などの演算は閉じているのか。演算表にインデックスを持つもののみを集合と考えると素朴集合論から矛盾を取り除けるのかなどといろいろな疑問が湧いてくるし、また、何が集合であるかという疑問も再び湧いてくる。もう少し、集合関係では遊べそうだ。

[PR]
by tnomura9 | 2015-11-15 08:30 | 考えるということ | Comments(0)

実数と不動点定理

0以上1未満の実数を2進数表記にすると、0.1001011... のように小数点下に0と1が適当に並んでいるのがわかる。そこでこれを適当に並べて次のような表にしてみる。

1: 0.1001011...
2: 0.0101000...
3: 0.0001010...
...

そうすると上の表の行の数を x 小数点下の桁数を y とすると、この表は ψ(x,y) : N × N -> {0, 1} という関数で表すことができる。つまり自然数 n に対応する実数の小数点下 m 桁の数は ψ(n, m) で表せる。

ここで、gn(x) = ψ(n, x) という関数を考えてみる。これは n 行の実数について小数点下 x が 0 であるか 1 であるかを示す gn(x) : N -> {0, 1} 型の関数である。

ここで任意の h(x) : N -> {0, 1} 型の関数がこの表の n 行目の関数として表現出来ると仮定する。そこで、gf(x) = f (ψ(x,x)) という関数を考えてみる。これは f が f : {0, 1} -> {0, 1} 型の関数であるとき、gf(x) は gf(x) : N -> {0, 1} 型の関数である。従って、仮定から gf(x) に対応する行 n が存在し gf(x) = ψ(n, x) = f (ψ(x,x)) が存在する。このとき gf(n) = ψ(n, n) = f (ψ(n,n)) となるので、関数 f : {0, 1} -> {0,1} について f (ψ(n,n)) = ψ(n,n) であるので、ψ(n,n) は関数 f の不動点となる。

そこで、関数 f として否定演算子 ¬ : {0, 1} -> {0, 1} を考える。すなわち ¬ (0) = 1, ¬ (1) = 0 である。このとき d(x) = ¬ (ψ(x,x)) に対応する行の数を n とすると、不動点定理から ¬ (ψ(n,n)) = ψ(n, n) となり矛盾する。これは任意の h(x) : N -> {0,1} 型の関数が上の表で表現できるという仮定が誤っていたことを示している。すなわち、d(x) = ¬ (ψ(x,x)) で定義される関数を上の表で定義することはできない。つまり、自然数と0以上1未満の実数を全単射で対応づけることはできない。

上の表の行の 0 と1 の数列は、対応する列の数が 1 の時は自然数の集合の部分集合にその列の数が含まれ、0 の時は含まれないということを表していると考えると、これは自然数とそのべき集合の関係を表していると見ることもできる。従って上の自然数と実数についての証明はそのまま自然数と自然数のべき集合との関係の証明となっている。

また、すべての集合の集合については、その要素である集合はその外延としてすべての集合の集合の部分集合と対応づけられるはずだから、すべての集合の集合の要素についての上のような ψ(x, y) が定義できるはずである。従って上の証明と同じ証明でラッセルのパラドックス ¬ (ψ(n,n)) = ψ(n,n) が発生する。

この証明の中心となっているのが ψ(x,x) という対角関数である。なぜこの関数を導入すると矛盾が起きてしまうのかを考えてみる。gn(x) : N -> {0, 1} 型の関数を gn(x) = ψ(n, x) で定義すると、これは gn(x) を n と同一視すれば n(x) = ψ(n, x) と表現できる。すると n(x) = ψ(n(x), x) となるので、x = n の時 n(n) = ψ(n(n), n) という自己言及の命題が発生してしまう。つまり、すべての f(x) : N -> {0, 1} 型の関数を ψ(x, y) で表現できると仮定すると、対角関数 ψ(x,x) の導入によって不動点が発生してしまうことを示している。つまり、素朴集合論のように関数 n(x) を n と同一視するような高階関数を含む体系は、自己言及関数 ψ(x,x) によって不動点が発生し、不動点の扱い方次第で矛盾が発生してしまう。

ところで、有限集合では上のような表で 0, 1 による配列の可能性を網羅することは不可能であることはすぐに分かる。例えば {1, 2, 3} については

_ 1 2 3
1 0 1 0
2 1 0 0
3 0 1 1

という 3 × 3 の表で3ビットの配列をすべて尽くすことができないことはすぐに分かる。3ビットの2進数は次のように 2^3 = 8 個あるので 3 × 3 の表には収まらないのは当然だ。

000
001
010
011
100
101
110
111

n ビットの数を n × n 行の表に収めることはできないので、同じような外型が対称的な表を作成する限り n が無限に大きくなっても n ビットの変化の可能性を収めることはできない。カントールの定理の結論が導き出されたのは、このような表を作るやり方ですべての可能性を表現しようとしたためだ。ただし、有限の集合ではこれは明らかだが、無限集合についても証明するためには対角関数 ψ(x,x) が必要だった。この関数は ψ(x,y) が外型が対称的な表であることを示している。

ただし、対照表が n × n でなければ、すべての有限集合のべき集合は自然数と対応づけることができる。{1,2,3} のべき集合は {1, 2, ... , 8} の自然数と対応づけることができるからだ。実数の場合も小数点下 n 桁で打ち切ったものは自然数と対応づけることができる。n がどのようになってもそれは可能である。しかし n が無限大の時はできない。無限大は数ではないからだ。

自然数と偶数が全単射で対応づけることができると言っても、それはあくまでも有限の数と有限の数との対応であって、有限の数と無限の数との対応関係は現れない。 n と 2n との対応は n がどんなに大きくても有限の数と有限の数の対応だ。自然数と実数の対応関係はそうではなく、有限の数と無限との対応関係を問うために対応関係を作ることができないのだ。

自然数と実数との対応関係を作ることは不可能だが、それは無限を含む実数を一つの点で表すことができると考えるためだ。無限小数は一点で表すことはできず常に確率的な揺らぎを持っていると考えるべきなのだ。

従って、自然数の無限と実数の無限の間に濃度の差があると単純に喜んでいてよいものか納得できないものがある。

参考サイト

ラッセルのパラドックス傾向と対策(あいまいな本日の私)
A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points. Noson S. Yanofsky
Diagonal Arguments and Cartesian Closed Categories. F. William Lawvere

[PR]
by tnomura9 | 2015-11-12 06:17 | 考えるということ | Comments(0)

床屋のパラドックスと不動点

不動点定理の考え方は床屋のパラドックスについても適用できる。話を単純にするために村人が3人だけの村について考えてみよう。前回のテーブルを流用すると次のようになる。

_ 1 2 3
1 0 0 0
2 0 1 0
3 0 1 1

これは、横の行の村人が縦の列の村人の髭を剃ることを示している。また集合 X = {1, 2, 3} は村人の集まりを示し。ψ(x, y) : X × X -> {0, 1} は上の演算表で表される二項演算を表している。これはまたこの演算表で表される ψ(x,y) の値が、x が y の髭を剃れば 1, 剃らなければ 0 の値をとることを示す。この演算表の対角線の部分に注目すると、ψ(1,1) = 0, ψ(2,2) = 1, ψ(3,3) = 1 となるので、村人 1 は自分自身の髭を剃らず、村人 2 と村人 3 は自分自身の髭を剃ることを示している。

また、各行の村人を固定して得られる gn : X -> {1,2} 型の関数 gn(x) = ψ(n, x)を定義できる。この時、gn(x) に対する n をこの関数のインデックスという。例えば g1(x) = ψ(1, x) は村人 1 がどの村人の髭を剃るかを示している。例えば g1(1) = 0, g1(2) = 0, g1(3) = 0 なので村人 1 は誰の髭も剃らない。この表ではまだどの村人が「自分の髭を剃らない人の髭を剃る」という床屋であるかわからないが、仮にそのような床屋 a0 がいるとすると ga0(x) = ψ(a0,x) の振る舞いはどうなるだろうか。床屋 a0 は村人 1 の髭を剃るので ga0(1) = 1 である。同様に ga0(2) = 0, ga0(3) = 0 となるはずだ。しかし、このような ga0(x) は上の表の中にはない。

そこで村人 1 をそのような床屋にしようとやってみると。g1(2) = 0, g1(3) = 0 は問題ないが、g1(1) = 1 にしてしまうとψ(1,1) = 1 でないといけないしかし、その場合 g1(1) = 0 でないといけなくなるので、結局 g1(1) の値を決められなくなる。

これは ga0(x) = ψ(a0, x) のインデックス a0 が集合 X の要素でなくてはならないという条件があるからだ。a0 が村人でなければ ga0(1) = 1, ga0(2) = 0, ga0(3) = 0 となる関数を見つけることは簡単だ。a0 が村人でなければ何の問題もない。つまり対角線論法で矛盾が発生するのは、関数 ga0(x) = ψ(a0, x) のインデックス a0 を集合 X の中に限定するという条件があるからだ。

全く同じ状況がラッセルのパラドックスでも見られる。上の演算表を再掲してみる。

_ 1 2 3
1 0 0 0
2 0 1 0
3 0 1 1

この表は、集合 X = {1, 2, 3} について、ψ(x, y) : X × X -> {1, 0} という二項演算の演算表である。集合 X が集合 1, 2, 3 の集合の集合と考え、上の演算が集合間の所属関係 ∋ と考えると、ラッセルのパラドックスの状況を再現できる。例えば 1 の行を見ると集合 1 はどの集合も要素としては含んでいないので 1 = {} である。また、集合 3 は集合 2 と 3 を要素として含むので 3 = {2, 3} だ。そこでこの表で対角線部分に注目すると、これは、集合の自己言及について表している。ψ(1, 1) = 0 だから、集合 1 は自分自身を要素として含まない集合である。また、ψ(2,2) = 1 だから集合 2 は自分自身を要素として含む。同様に 3 も自分自身を要素として含む集合である。すなわち集合 X は自分自身を要素として含まない集合 1 と自分自身を要素として含まない集合 2, 3 で構成されていることがわかる。

そこで、自分自身を要素として含まない集合の集合 r を考えてみる。r が上の表に含まれていると考えるとその行は次のようになるはずだ。

r 1 0 0

しかしこのような行は上の演算表には現れない。r が 1 になるように調整しようとしても ψ(1,1) = 1 なら ψ(1,1) = 0 でなければならないので矛盾してしまう。結局 r は X = {1, 2, 3} は X の外に求めなくてはならなくなる。これは不動点定理を使えばきちんと表現できるが、おおよその意味はこの通りだ。つまり、「自分自身を要素として含まない集合の集合」を集合の集まりの中で求めようとしても不動点定理のために a0 ∈ a0 ⇔ a0 /∈ a0 となることがわかるため、すべての集合についての ψ(x,y) を作ることができないことがわかる。

このように対角線論法は ψ(x, y) : X × X -> {0, 1} についての不動点定理によって統一的に理解することができる。不動点の存在によって、すべてのインデックスが集合 X の要素であるという条件を、自己言及が満たさなくさせることがあるということだ。

床屋のパラドックスにしても、ラッセルのパラドックスにしても、「自分自身の髭を剃らない人の髭を剃る床屋」や「自分自身を要素としない集合の集合」は存在しそうに見えるのに集合 X の中に見つけようとすると矛盾がおきる。しかし、それを集合 X の外に求めると存在するように見える。だから、このような要素の存在しない理由がもう一つ納得できない気がするが、これは、ψ(x,y) が X × X の定義域では、その可能性の全てを表現することができないからだ。そのため集合 X の外にはいつでも求める理想郷が見つかるように思える。

このことは、X の二項演算では、全ての可能性を尽くすことができないことを示している。集合と集合のべき集合の全単射が作れないのはそのためだ。集合の二項演算で全てのべき集合を表現することはできない。それは集合が無限集合であっても事情が同じため、自然数と実数の全単射ができなくなるのだ。

また、ψ(x,x) のような自己言及が問題を起こす理由は、ψ(x, y) で x と y が異なる場合と違って、ψ(x,x) は第1引数と第2引数が独立にできないため、ga0(x) = ψ(a0, x) は変数 x が完全な独立変数とは言えないからだ。ga0(x) を一般的な1変数関数と考えることはできないのだ。その関数は必ず ga0(a0) という特別な点を含んでいる。

このように不動点定理の考え方で見ると、対角線論法で発生する矛盾全てに、ψ(x, y) : X × X -> {1,0} という関数の性質が関与していることがわかる。

[PR]
by tnomura9 | 2015-11-03 10:36 | 考えるということ | Comments(0)

不動点定理のおもちゃ

ψ: X × X -> {0, 1} について、g(x) = ψ(a0, x) と定義する。このとき g(x) = f(ψ(x,x)) であれば、すなわち、g(x) = ψ(a0, x) = f(ψ(x,x)) であれば、ψ(a0, a0) は f に対して不動点になる。なぜなら f(ψ(a0, a0)) = g(a0) = ψ(a0, a0) である。この不動点定理はわかりやすいが、いや、わかったと思いやすいがこのモデルになる ψ(x,y) を作ろうと思うと結構難しい。

そこで、おもちゃのような例を考えてみた。X = {1, 2, 3} という有限集合について ψ(x, y) を考えてみる。ψ(x, y) : X × X -> {0,1} は次のような表で表現できる。行と列の数字は引数の値を表し、行と列の交点の値が ψ(x,y) の値である。例えば次のような表ができる。

_ 1 2 3
1 0 0 0
2 0 1 0
3 0 1 1

すぐにわかるように3列に配置される0と1の組み合わせは上に採用した3つだけでなく 2^3 = 8 個ある。

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

したがって ψ(x, y) の値としてはこの8つのうちの3つだけしか使えないことになるが、ここでは冒頭に示した例に戻る。冒頭の計算表がここで定義した ψ(x,y) の振る舞いの全てを尽くしていることは明らかだ。このとき g1(x) = ψ(1, x) とおくと、

g1(1) = 0, g1(2) = 0, g1(3) = 0

になる。同様に、

g2(1) = 0, g2(2) = 1, g2(3) = 0
g3(1) = 0, g3(2) =1, g3(3) = 1

である。またψの対角線部分については ψ(1,1) = 0, ψ(2,2) = 1, ψ(3,3) = 1 である。

ここで引数が {0, 1} の要素であるブール代数 f を次のように定義する。

f(x) = ¬(1 ∨ x)
を考える。この関数は常に 0 を出力するつまり、f(0) = 0, f(1) = 1 である。この f を使って g(x) を定義する。

g(x) = f(ψ(x,x))

この関数の値は、

g(1) = f(ψ(1,1)) = f(0) = 0
g(2) = f(ψ(2,2)) = f(1) = 0
g(3) = f(ψ(3,3)) = f(1) = 0

明らかにこの g(x) は g1(x) と同じものだ。そこで f(ψ(1,1)) を計算すると、

f(ψ(1,1)) = f(0) = 0 = ψ(1,1)

となり、ψ(1,1) = 0 が f の不動点になっていることがわかる。ちなみに、ψ(2,2) は f の不動点ではない。

f(ψ(2,2)) = f(1) = 0 /= ψ(2,2)

しかしどのような f に対しても ψ(a0, a0) が不動点となるわけではない。上の例で g(x) = ¬ ψ(x,x) で定義すると、

g(1) = ¬ ψ(1,1) = ¬ 0 = 1
g(2) = ¬ ψ(2,2)) = ¬ 1 = 0
g(3) = f(ψ(3,3)) = ¬ 1 = 0

となり、このような関数 g(x) は ψ の計算表の中に見つけることはできない。

これは可能な8個の可能性のどの3つを採用しても同様である。したがって、g(x) = ¬ ψ(x,x) に対応する a0 を見つけることはできない。この関係は集合 X に採用する自然数の範囲をどんなに広げても同じである。

上の gn(x) という関数は値が 1 のところの自然数を拾っていくと自然数の集合を規定しているので、結局のところ自然数と自然数のべき集合の全単射ができないことの証明になる。この証明の利点は、どの自然数が議論に使われているかが明確なところだ。全ての自然数をシステム的に考慮しているのが明白だ。カントールの対角線論法では、全ての自然数について考慮されているかどうかが必ずしも明白でない。

ψ(x,y) は2項演算だが、これを集合の所属関係 ∈ と考えるとそのままラッセルのパラドックスになる。

自然数と偶数の全単射を考えるとき、要素が無限大になるのは一方向だけだ。どちらも再帰的に要素が1つずつ増加していく。しかし、自然数の直積の関数を考えるときは値の可能性が 2^n - 2^(n-1) ずつ増加する。このことが再帰的定義で全単射が作れない理由なのではないだろうか。要は再帰関数の性質の違いなのだろう。無限を数え尽くすことはできないのだから、問題はその過程に存在するはずだからだ。

[PR]
by tnomura9 | 2015-11-02 23:37 | Comments(0)

対角線論法の意味

対角線論法は結局皆同じことを論じているのではないだろうか。

0以上1未満の実数全体は小数点下を2進数表記をすると、一つの実数は自然数の部分集合と同一視できるし、自然数の直積から {0,1} への関数の全体はやはり自然数のべき集合と同一視できる。また、集合の所属関係 ∈ は対象の直積集合から {0, 1} への写像だ。さらには、命題の直積集合から {真, 偽} への写像も同じ構造をしている。つまり集合とそのべき集合との関係も、集合とその集合からそれ自身への写像との関係も、自然数と実数の関係も、ゲーデルの不完全性定理も結局同じことを論じているのではないかということだ。

直観的な印象なので、間違っているかもしれないが、結局のところ、集合とべき集合の関係がはっきり分かれば、その他の問題についてもその構造が分かるのではないかという気がする。つまり、自己言及の問題、あるいは不動点定理である。どちらも、しっかり数学なので説明を読んでもわからないが、これを平易に理解できる方法があれば、謎は氷解するのではないだろうか。

フェルマーの定理を証明しようとして人生を浪費した数学愛好家が無数にいるらしい。ラッセルのパラドックスもそうで、一見素人にも少し考えれば解決できそうに見えるのだが、結局きちんとした数学をマスターしないと理解できないのだろう。靴の上から足のかゆいところが掻けない感じで不満は残るが。

追記

上に書いたような考え方はどこかで読んだような気がしていたら、このブログでも何度か引用した『自己言及の論理と計算』長谷川真人著という文書にきちんと書いてあった。

簡単に言うと集合 X の直積集合 X × X から集合 {0,1} への関数 ψ(x, y) : X × X -> {1,0} について任意の a0 ∈ X について g(x) = ψ(a0, x) が定義できるとき任意の f について g(x) = f (ψ(x, x)) と定義すると、g(x) に対応する a0 について、g(a0) = ψ(a0, a0) なので、f(ψ(a0, a0)) = g(a0) = ψ(a0, a0) となり f について ψ(a0, a0) は不動点になってしまうような g(x) を作ることができる。不動点とはある関数の引数にしたときその値が引数と同じになってしまう点のことだ。たとえば f(x) = 2 * x とすると f(0) = 0 になってしまう。この場合 0 は f の不動点である。

ところが、f が否定演算ならψ(a0,a0) = ¬ψ(a0,a0) になってしまうので、上の条件のような ψ(x,y) が存在しないことがわかる。ψ(x,y) が存在するとき、g(x) は a0 に対応する X の部分集合を定めるので、集合 X の要素とそのべき集合を対応させるが、上の議論からそれは矛盾になってしまう。

また、実数は自然数の集合と全単射なので、上の結論から自然数と実数の全単射をつくるような ψ(x,y) はできないことがわかる。

ラッセルのパラドックスでも上の議論で ψ が ∈(x, y) で f が否定演算子であると考えるとよい。このとき g(x) = ¬ (∈(a0, x) は x が a0 を要素として含まない集合であることを示す。このような集合が定められると仮定すると、∈ (a0,a0) = ¬∈(a0, a0) となって矛盾する。

床屋のパラドックスでは ψ(x,y) が「x が y のひげを剃る」という2項演算子で、f が否定演算子になる。

ψ(x,y) は 一般に A × A -> B 型の関数についても考えることができるため、また、計算可能な関数のみを扱うラムダ演算では ψ が存在するのでこの不動点を利用して再帰関数を定義できる。

いろいろな形の対角線論法が不動点定理で統一して説明できるのが不思議な感じだ。

[PR]
by tnomura9 | 2015-11-01 08:01 | 考えるということ | Comments(0)