数理論理学（数学基礎論）　その14

1 ：１３２人目の素数さん：2019/03/22(金) 11:55:47.59 ID:oVa5RLRo.net

数学基礎論は、数学の基礎づけを目的として誕生したが
現在では、数理論理学として、証明論、再帰的関数論、
構成的数学、モデル理論、公理的集合論など、 多くの分野
に分かれ、極めて高度な純粋数学として発展を続けています。
（「数学基礎論」という言葉の使い方には、専門家でも
若干の個人差があるようです。）
応用、ないし交流のある分野は、計算機科学の諸分野や、
代数幾何学、英米系哲学の一部などを含み、多岐にわたります。
（数学セミナー98年6月号、「数学基礎論の学び方」
ttp://www.math.tohoku.ac.jp/~tanaka/intro.html
或いは 岩波文庫「不完全性定理」 6.4 数学基礎論の数学化などを参照）

前スレ
数学基礎論・数理論理学　その13
https://rio2016.5ch.net/test/read.cgi/math/1532721493/

2 ：１３２人目の素数さん：2019/03/22(金) 13:13:35.41 ID:64YyWaX6.net

数学基礎論は数学の基礎論ではない。まったく数学には関係ない論理のお遊び

3 ：１３２人目の素数さん：2019/03/22(金) 21:35:59.55 ID:EWzYRJ4u.net

Vの中で操作してる以上は数学だぞ

4 ：１３２人目の素数さん：2019/03/22(金) 21:40:24.58 ID:EWzYRJ4u.net

計算機科学はチューリングマシンをイデア的に捉える
論理学は一階述語論理を人の論理の形式化とする
数学はチューリングマシンも一階述語論理も集合とする

5 ：１３２人目の素数さん：2019/03/24(日) 07:17:00.84 ID:N4FNRVCO.net

Yコンビネータ

型無しラムダ計算においてよく知られた（そしておそらく最もシンプルな）
不動点コンビネータはYコンビネータと呼ばれる。これはハスケル・カリーによって
発見されたもので、次のように定義される。

Y = (λf . (λx . f (x x)) (λx . f (x x)))

実際に関数gを適用することによって、この関数が不動点コンビネータとして動作する
のが分かる。

Y g = (λf . (λx . f (x x)) (λx . f (x x))) g (Yの定義より)
= (λx . g (x x)) (λx . g (x x)) (λfのβ簡約、主関数をgに適用)
= (λy . g (y y)) (λx . g (x x)) (α変換、束縛変数の名前を変える)
= g ((λx . g (x x)) (λx . g (x x))) (λyのβ簡約、左の関数を右の関数に適用)
= g (Y g) (第2式より)

これをそのままラムダ計算で使うと、評価戦略が値渡しだった場合には (Y g) が
(g (Y g)) と展開された後も、引数の値を先に求めようとして
(g (g (Y g))) →...→ (g ... (g (Y g))...) のように無限に展開され続けて
止まらなくなってしまうので、次節で示すZコンビネータのように修正する。

評価戦略が名前渡しの場合はこのまま使える。 このカリーによるコンビネータのみを
Yコンビネータとすることもあるが、実装などでは不動点コンビネータを指す名前として
他の形であってもYという名前を使っていることもある。

SKIコンビネータ計算では次のようになる。
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))

6 ：１３２人目の素数さん：2019/03/24(日) 07:19:23.05 ID:N4FNRVCO.net

>>4
計算機科学はチューリングマシンをハードウェア、機械として捉える、が正解

7 ：１３２人目の素数さん：2019/03/24(日) 21:34:57.51 ID:FOTRZJL+.net

>>5
> Yコンビネータ
・・・
> Y = (λf . (λx . f (x x)) (λx . f (x x)))
> 評価戦略が名前渡しの場合はこのまま使える。 ・・・

これは間違い。評価戦略が名前渡しであっても Y は使えない。それを示すために
君が書き下してくれたY gの式変形をどちら向きにも進める変換 “＝” による等式でなく
簡約 “→” による評価として→で向き付けられた形に書き直してみよう。

（“≡” は構文的に同一の項であることを示す。なお、「α変換」は
束縛変数に対する名前の付け替えというメタ言語的な操作なので
ここではα変換の前後は構文的に同一の項として扱い“≡”で示した）

　 Y g
≡ (λf . (λx . f (x x)) (λx . f (x x))) g (Yの定義より)
→ (λx . g (x x)) (λx . g (x x)) (λfのβ簡約、主関数をgに適用)
≡ (λy . g (y y)) (λx . g (x x)) (α変換、束縛変数の名前を変える)
→ g ((λx . g (x x)) (λx . g (x x))) (λyのβ簡約、左の関数を右の関数に適用)
← g (Y g) (第2式より)

最後のステップが逆向きの簡約 “←” であることに注意。
このステップは絶対に本来の簡約 “→” の向きには書き直せないので
Y コンビネータは名前呼びでも使えないことが分かる。

名前呼びの簡約戦略の場合に正しく動く不動点コンビネータで最も有名な例は
Turing のΘコンビネータで、λ項として書き下すと以下のようになる：

Θ ≡ (λx y, y(x x y))(λx y, y(x x y))

最後に、これを用いた Θg という項が簡約によって確かに g(Θg) になることを確かめておく：

　 Θ g
≡ ((λx y, y(x x y))(λx y, y(x x y))) g
≡ ((λz w, w(z z w))(λx y, y(x x y))) g　・・・・・・・・・・・・　α変換
→ (λw. w((λx y, y(x x y))(λx y, y(x x y)) w)) g　・・・　 β簡約
≡ (λw. w(Θ w)) g　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・　Θの定義で置き換え
→ g(Θ g)

なお、値呼びの簡約戦略で正しく動く不動点コンビネータも勿論ある。
具体的な定義は、例えば次にある：
Daniel P. Friedman & Matthias Felleisen “The Little Schemer” 4th ed., p. 172 (The MIT Press, 1996).

8 ：１３２人目の素数さん：2019/03/25(月) 18:38:51.28 ID:ZEwsypVC.net

>>7訂正

失礼、チューリングのΘコンビネータのλ項で、束縛変数とλ項本体とを区切るピリオド “.” が間違ってコンマ “,” になってました

9 ：１３２人目の素数さん：2019/03/25(月) 22:13:02.02 ID:MhMPsIFV.net

Bertrand Russellはその著書「Principia Mathematica」の序で次のように述べている。
「……数学の原理に関するいかなる理論も、それを支持する主たる論拠は、
常に帰納的なものでなければならない。換言すれば、それはその問題の理論によって、
我々が通常の数学を演繹できるという事実の中に存在するものでなければならない。
数学においては、最高度の自明性は、演繹のはじめの段階で得られることはめずらしく、
解いていくにつれてある段階で得られるというのが普通である。

したがって、その段階に到達するまでの初期の演繹においては、前提から真の結論が
引き出されるという理由でその前提が信じられるのであり、前提からその結論が
引き出されるという理由でその結論が信じられるのではない」

10 ：１３２人目の素数さん：2019/03/28(木) 11:25:18.38 ID:h+H0YW40.net

つまりコーエン最強と

11 ：１３２人目の素数さん：2019/03/31(日) 10:07:14.17 ID:pd4YzCEG.net

age

12 ：１３２人目の素数さん：2019/04/11(木) 21:03:28.51 ID:ZT7Ri93V.net

まだまだ死に絶えてはいません

13 ：１３２人目の素数さん：2019/05/06(月) 10:11:07.83 ID:X59eIqI1.net

∪Aに関する疑問を突き詰めてみると
P(x)≡∃y∈A(x∈y)
の真偽って確定するとしていいのかな？
与えられたｘについてyを選ばなくて良いって言うのはなんだか胡散臭いし
選び出すことができるってなんだか選択公理っぽい
公理にしてる根拠が薄くないかな

14 ：１３２人目の素数さん：2019/05/06(月) 15:38:16.17 ID:ffT6Gv3d.net

選び出すって何おかしなこと言うてんねん
存在するかどうかを問題にしてるだけや

15 ：１３２人目の素数さん：2019/05/06(月) 19:27:43.69 ID:FaiecvaY.net

何が存在してるか言えなくて
何か存在してるだけではやだなぁ

16 ：１３２人目の素数さん：2019/05/06(月) 19:38:32.02 ID:X9tK7TPF.net

xに対して
∃y∈A(x∈y)
が成り立っているとき、そのyをブルバキ流に書けば
τy(y∈A∧x∈y)
だ
これは∃の意味をどう決めるかによる

17 ：１３２人目の素数さん：2019/05/07(火) 18:27:34.24 ID:yJ06pJHo.net

ブルバキだと
｛(x,τy(y∈A∧x∈y))}
は集合なの？
これが集合なら
F=｛(x,τy(y∈Bx))｝
も集合？Fって選択関数のことだけど

18 ：１３２人目の素数さん：2019/05/07(火) 19:17:25.36 ID:+08/LJkT.net

xが集合で、
∃y(y∈A∧x∈y)
が成り立ってるなら
τy(y∈A∧x∈y)
も集合。だから
(x,τy(y∈A∧x∈y))
は集合。よって
｛(x,τy(y∈A∧x∈y))}
は集合。

Bxが何のことかわからないけど、
何か集合aがあって、Bをa上の写像と見做すことにする。
∀x∊a(Bx≠φ)
が成り立ってるなら、
F={(x,τy(y∈Bx))| x∊a}
はブルバキでは選択関数となる。
でもそれはτに強い規則を課していて
s=t⇒τy(y∈Bs)=τy(y∈Bt)
が満たされるから。
ブルバキでは選択公理は定理となる。
でもブルバキ読んでないしあまり詳しいことはよく知らない。

19 ：１３２人目の素数さん：2019/05/07(火) 23:24:21.19 ID:yJ06pJHo.net

>>18
>ブルバキでは選択公理は定理となる
ありがとう
やはりブルバキだとそうなるのね
ちょっと強すぎな感じ

20 ：１３２人目の素数さん：2019/05/16(木) 14:40:02.69 ID:+P5Ylnkx.net

数学基礎論=ZFC教

21 ：１３２人目の素数さん：2019/05/16(木) 22:16:22.92 ID:mLYM7DuU.net

>>20
そんなことはない

22 ：１３２人目の素数さん：2019/05/16(木) 22:56:30.67 ID:1KZufyIl.net

>>20
> 数学基礎論=ZFC教

全くの間違い
数学基礎論は本来は今の数理論理学全般を指すのではなく数学の基礎付け＝ヒルベルトのプログラムの精神を引き継いだ学問分野を表していた
そういう意味では数学基礎論の最もコアな部分は証明論それもGentzen流の純粋に構文的な手段のみに限定して還元主義的な証明論だが
このGentzen流証明論は構文的であるが故にZFCのような集合論とは全く無縁と言って良い

現在の日本のように「数学基礎論」という学問名を「数理論理学」つまり論理を数学的な手段で分析する学問一般を表すものとして使うのは
数学基礎論本来の意味からは邪道極まりない使い方

竹内先生や八杉さんらが共立現代数学講座から出した『数学基礎論』は実に正しい使い方だ、何しろあの本には証明論しか書いてないのだから
その点、新井さんの岩波からの『数学基礎論』は邪道なタイトルだなｗ

でも、竹内先生らの本が同講座の巻が軒並み品切れとなって久しいころに復刊された時には『証明論入門』というタイトルに変えられてしまった
その頃には「数学基礎論」という言葉が本来の意味でなく数理論理学一般を指す邪道な使われ方がメジャーになってしまっていたから
数理論理学の教科書としては証明論しか書いてないので羊頭狗肉だと（数学基礎論の本来の意味を知らない）無知な読者たちから
批判を浴びるのを出版社が恐れたからかも知れないね

23 ：１３２人目の素数さん：2019/05/16(木) 23:19:21.42 ID:mLYM7DuU.net

>>22は頭の堅い人の偏見だから割り引いて読むように

24 ：１３２人目の素数さん：2019/05/16(木) 23:23:56.09 ID:tdYDXMPB.net

計算機科学でも数学でもない一群

25 ：１３２人目の素数さん：2019/05/16(木) 23:33:46.85 ID:gL9bCd2q.net

「本来は」とか言い出したら現代数学のほぼ全てが邪道になってしまうよ
数学に限らず物理もそうかな

26 ：１３２人目の素数さん：2019/05/17(金) 07:36:28.10 ID:xqLphdBG.net

>>24
wikipediaでもmathoverflowでもmathematical logicを数学の分野として扱ってるが

27 ：１３２人目の素数さん：2019/05/17(金) 16:46:16.68 ID:xABauc9m.net

逆にマスマティクスじゃないロジックってなんなの？

28 ：１３２人目の素数さん：2019/05/17(金) 17:03:15.63 ID:H7rBRDln.net

ヘーゲルみたいなやつ

29 ：１３２人目の素数さん：2019/05/17(金) 17:16:59.61 ID:/cNjbkPD.net

論理哲学みたいな奴？

30 ：１３２人目の素数さん：2019/05/18(土) 00:28:38.47 ID:SjRfDMFu.net

>>23
“mathematical logic”という分野の意味で「数理論理学」でなく「数学基礎論」の語を使う日本だけが異常なんだよ
海外では“foundations of mathematics”と“mathematical logic”は適切に使い分けられているよ
学問分野の名称（前者FMは後者MLの一部分というか“philosophy of mathematics”とも共通部分を持つような学問領域を指す）でも
書籍のタイトルでもね

31 ：１３２人目の素数さん：2019/05/18(土) 00:40:09.67 ID:psenGI9v.net

数学に威張り散らすより実学工学な計算機科学と密接に連携しろよ。

まあ文学部卒のバカだと実学な時点で臍が曲がるんだろうけど。

32 ：１３２人目の素数さん：2019/05/18(土) 06:15:18.02 ID:HKFcHFTe.net

超巨大基数ってクラスぐらいに大きい集合があるってことにしたいことかな？
ZFに付け加えても矛盾起こらないんだろうけれども

33 ：１３２人目の素数さん：2019/05/18(土) 08:51:38.68 ID:nop0lv60.net

文学部が計算機科学と連携とか面白そうだな
俺は数学科卒だけど

34 ：１３２人目の素数さん：2019/05/18(土) 23:23:35.48 ID:nCdi+f/4.net

今日本の数理論理学、数学基礎論の日本を代表する研究者って誰？

35 ：１３２人目の素数さん：2019/05/18(土) 23:37:50.35 ID:HKFcHFTe.net

>>34
新井先生

36 ：１３２人目の素数さん：2019/05/19(日) 01:14:30.60 ID:9b1buNeX.net

誤解する人はいないとは思うが旦那の方だな

37 ：１３２人目の素数さん：2019/05/19(日) 11:14:04.85 ID:Kf1QbH9H.net

test

38 ：１３２人目の素数さん：2019/05/31(金) 00:36:22.13 ID:XkkEuHyI.net

test

39 ：１３２人目の素数さん：2019/06/05(水) 11:44:34.47 ID:bMrghUP7.net

ｎ変数部分帰納的関数ｆ、ｇについて質問ですが、
f \simeq g の定義って、｢ｆ、ｇの定義域が一致して、その定義域における値も一致している｣
つまり｢ｆ、ｇを(n+1)項関係関係と見たとき、集合としてｆ=ｇ｣という理解でいいですか？

40 ：１３２人目の素数さん：2019/06/05(水) 11:50:24.27 ID:bMrghUP7.net

それとも、｢ｆ、ｇの定義域は異なっていても良いが、ｆ、ｇ両方の定義域に属する元に対しては値が一致する｣ということですか？

41 ：１３２人目の素数さん：2019/06/05(水) 23:36:31.75 ID:MBnOpo4E.net

さあ？

42 ：１３２人目の素数さん：2019/06/29(土) 16:55:30.89 ID:DHiuKlHq.net

数理論理学（数学基礎論）　その14
ふうL@Fu_L12345654321
学コン1傑いただきました！
とても嬉しいです！

https://pbs.twimg.com/media/D-IuUuqVUAALnAB.jpg

https://twitter.com/Fu_L12345654321/status/1144528199654633477
(deleted an unsolicited ad)

43 ：１３２人目の素数さん：2019/07/03(水) 19:35:57.22 ID:dqLWAG/2.net

3600
ふうL@Fu_L12345654321
学コン1傑いただきました！
とても嬉しいです！

https://pbs.twimg.com/media/D-IuUuqVUAALnAB.jpg

https://twitter.com/Fu_L12345654321/status/1144528199654633477
(deleted an unsolicited ad)

44 ：１３２人目の素数さん：2019/08/24(土) 19:02:54.25 ID:F/68y/86.net

新井敏康『数学基礎論』の集合論の章で、
Godel operationとして書いてある
F4(x,y):={u∪{v}:u∈x, v∈y}から
直積が構成できると書いてあるけど、
具体的にはどうやれば良いですかね？

冪集合の公理も置換公理もないから
どうやれば良いのかちょっとよく分からないのですが。

45 ：１３２人目の素数さん：2019/09/05(木) 19:18:25.75 ID:l3HLNP+x.net

このスレ死んだな
たまにチラホラ更新されるから見てたんだけど

46 ：１３２人目の素数さん：2019/09/05(木) 23:14:43.33 ID:K6NA6nMr.net

新井さんの本のタイトルが『数学基礎論』ってなんか大袈裟というか羊頭狗肉というか

数学の基礎付けに関して特記すべきような内容は何も書いてなくて
数理論理学の教科書として標準的な話題を扱ってるだけなんだから
素直に『数理論理学』ってタイトルにしとけばよかったのに