現代数学の系譜工学物理雑談古典ガロア理論も読む62

[過去ﾛｸﾞ] 現代数学の系譜工学物理雑談古典ガロア理論も読む62 (1002ﾚｽ)
上下前次1-新
通常表示 512ﾊﾞｲﾄ分割ﾚｽ栞
抽出解除必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞あぼーん

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

176: 現代数学の系譜 雑談 古典ガロア理論も読む ◆e.a0E5TtKE  [sage] 2019/03/11(月) 07:59:44.48 ID:NUGiaq8/

>>175

つづき

Contents
1 Existence
1.1 From the compactness theorem
1.2 From the incompleteness theorems
1.2.1 Arithmetic unsoundness for models with ~G true
1.3 From an ultraproduct
2 Structure of countable non-standard models

References
・Boolos, G., and Jeffrey, R. 1974. Computability and Logic, Cambridge University Press. ISBN 0-521-38923-2
・Thoralf Skolem (1934). "Uber die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzahlbar unendlich vieler Aussagen mit ausschlieslich Zahlenvariablen" (PDF). Fundamenta Mathematicae (in German). 23 (1): 150?161.
http://matwbn.icm.edu.pl/ksiazki/fm/fm23/fm23115.pdf
Citations
1 Andrey Bovykin and Richard Kaye Order-types of models of Peano arithmetic: a short survey June 14, 2001
http://web.mat.bham.ac.uk/R.W.Kaye/papers/survey6.pdf
2 Andrey Bovykin On order-types of models of arithmetic thesis submitted to the University of Birmingham for the degree of Ph.D. in the Faculty of Science 13 April 2000
http://logic.pdmi.ras.ru/~andrey/phd.pdf
3 Fred Landman LINEAR ORDERS, DISCRETE, DENSE, AND CONTINUOUS ? includes proof that Q is the only countable dense linear order.
http://www.tau.ac.il/~landman/Online_Class_Notes_file/Boolean/1%20%20Linear%20orders,%20discrete,%20dense%20and%20continuous.pdf
(引用終り)
以上

http://rio2016.5ch.net/test/read.cgi/math/1551963737/176

177: 現代数学の系譜 雑談 古典ガロア理論も読む ◆e.a0E5TtKE  [sage] 2019/03/11(月) 09:01:00.23 ID:NUGiaq8/

>>172 補足追加

https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%9A%8E%E8%BF%B0%E8%AA%9E%E8%AB%96%E7%90%86
二階述語論理
(抜粋)
一階述語論理と同様に議論領域（ドメイン）の考え方を使う。
ドメインとは、量化可能な個々の元の集合である。一階述語論理では、そのドメインの個々の元が変項の値となり、量化される。
例えば、一階の論理式 ∀x (x ≠ x + 1) では、変項 x は任意の個体を表す。二階述語論理は個体の集合を変項の値とし、量化することができる。
例えば、二階の論理式 ∀S ∀x (x ∈ S ∨ x ? S) は、個体の全ての集合 S と全ての個体 x について、x が S に属するか、あるいは属さないかのどちらかであるということを主張している。

目次
1 二階論理の表現能力
2 文法
3 意味論
6 歴史と論争

二階論理の表現能力
二階述語論理は一階述語論理よりも表現能力が高い。例えば、ドメインが全ての実数の集合としたとき、一階述語論理を使ってそれぞれの実数には加法の逆元が存在するということを ∀x ∃y (x + y = 0) と表せる。
しかし、空でなく上に有界な実数の集合があるとき常にその集合には上限が存在するという命題を表すには、二階述語論理が必要となる。ドメインが全ての実数の集合としたとき、次の二階の論理式がこの命題を表している。

二階述語論理では、「ドメインは有限である」とか「ドメインは可算無限集合の濃度である」といった文も形式的に表現可能である。
ドメインが有限であるというには、そのドメインから同じドメインへの全ての単射関数が全射であることを論理式で表せばよい。
ドメインが可算無限集合の濃度であることをいうには、そのドメインの任意のふたつの無限部分集合間に全単射があることを論理式で表せばよい。
一階述語論理ではこれら（「有限集合であること」や、「可算集合であること」）を表現できないことが、レーヴェンハイム-スコーレムの定理から導かれる。

文法

意味論
二階述語論理の意味論は、個々の文の意味を確立するものである。
一階述語論理では単一の標準の意味論しかなかったが、二階述語論理では2種類の意味論 standard semantics と Henkin semantics がある。
(引用終り)

http://rio2016.5ch.net/test/read.cgi/math/1551963737/177

178: 現代数学の系譜 雑談 古典ガロア理論も読む ◆e.a0E5TtKE  [sage] 2019/03/11(月) 20:48:18.37 ID:NUGiaq8/

>>177 追加の追加
「ゲーデルやスコーレムが一階述語論理に固執したこともあって、二階や高階の述語論理はほとんど省みられなかった」
「近年、二階述語論理は一種の回復の途上にある」
か、なるほどねー（＾＾
https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%9A%8E%E8%BF%B0%E8%AA%9E%E8%AB%96%E7%90%86
二階述語論理
(抜粋)

推論体系
二階述語論理には、いくつかの推論体系があるが、standard semantics に対して完全と言えるものは存在しない。どの体系も健全であり、証明に使える全ての文は適当な意味論において論理的に妥当である。

Shapiro (1991) と ヘンキン(1950) が検討した推論体系は、内包公理と選択公理を追加したものである。これら公理は二階述語論理の standard semantics に対して健全である。

二階論理とメタ論理学の成果
ゲーデルの不完全性定理の系の1つとして、以下の3つの属性を同時に満足するような二階述語論理の推論体系は存在しないとされた[4]。

・（健全性）証明可能な二階述語論理の文は常に真である。すなわち standard semantics に従ったあらゆるドメインで真である。
・（完全性）standard semantics において常に妥当な二階述語論理の論理式は、全て証明可能である。
・（実効性）与えられた論理式の並びが妥当な証明かどうかを正しく決定できる証明検証アルゴリズムが存在する。
この系を言い換えると、二階述語論理は完全な証明理論に従わない、とも言える。この観点で、standard semantics を伴った二階述語論理は一階述語論理とは異なり、そのせいもあって論理学者は長年、二階述語論理に関わることを避けてきた。

上述のように Henkin は Henkin semantics を使えば二階述語論理に一階述語論理の標準的な健全で完全で実効的な推論体系を適用できることを証明した。

歴史と論争
一階述語論理を使うと、集合論を公理的体系として形式化できることがわかり（完全性の問題はあるが、ラッセルのパラドックスほど悪いことではない）、公理的集合論が生まれ、集合は数学の基盤となった。
算術、メレオロジー、その他の様々な論理的理論が一階述語論理の範囲内で公理的に定式化でき、ゲーデルやスコーレムが一階述語論理に固執したこともあって、二階や高階の述語論理はほとんど省みられなかった。

つづく

http://rio2016.5ch.net/test/read.cgi/math/1551963737/178

181: 現代数学の系譜 雑談 古典ガロア理論も読む ◆e.a0E5TtKE  [sage] 2019/03/11(月) 23:08:55.07 ID:NUGiaq8/

>>180
つづき

（圏論（トポス）と高階論理）
https://staff.fnwi.uva.nl/t.uemura/
PhD candidate at Institute for Logic, Language and Computation, University of Amsterdam.
トポスと高階論理 Taichi Uemura 2018年12月9日
この文書は Category Theory Advent Calendar 2018 (https://adventar.org/calendars/3168 *) の 9 日目の記事です。
*) Category Theory Advent Calendar 2018 作成者：piano2683
(抜粋)
0 はじめに
トポスとは、有限極限と部分対象分類子と羃対象を持つ圏である。

1 章では高階論理を導入する。
2 章でトポスを定義する。この段階ではトポスの圏論的性質には一切立ち入らない。
3 章で高階論理のトポスでの解釈を与える。
4 章でトポスの内部言語 (internal language) を高階理論として定義し、内部言語で導出できることとトポスの性質との関係をいくつか見る。
5 章でトポスの性質を内部言語を使っていくつか証明する。

基本的な圏論の知識 (極限、部分対象、随伴、デカルト閉圏など) は仮定するが、トポスについては前提知識は仮定しない。
トポスの知識がある人は圏論的な証明と高階論理を使った証明を比べてみると面白いと思います。
(引用終り)

https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E8%BF%B0%E8%AA%9E%E8%AB%96%E7%90%86
高階述語論理
(抜粋)
高階述語論理は表現能力が高いが、その特性、特にモデル理論に関わる部分では、多くの応用について性格が良いとは言えない。クルト・ゲーデルの業績により、古典的高階述語論理は（帰納的に公理化された）健全で完全な証明計算が認められないとされた。しかし、Henkin model によれば、健全で完全な証明計算は存在する。
高階述語論理の例として、アロンゾ・チャーチの Simple Theory of Types や Calculus of Constructions (CoC) がある。

https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AD%E3%83%B3%E3%82%BE%E3%83%BB%E3%83%81%E3%83%A3%E3%83%BC%E3%83%81
アロンゾ・チャーチ（Alonzo Church, 1903年6月14日 - 1995年8月11日）はアメリカの論理学者、数学者。ラムダ計算の創案者、「チャーチ＝チューリングのテーゼ」の提唱者として知られる。
(引用終り)
以上

http://rio2016.5ch.net/test/read.cgi/math/1551963737/181

182: 現代数学の系譜 雑談 古典ガロア理論も読む ◆e.a0E5TtKE  [sage] 2019/03/11(月) 23:15:40.94 ID:NUGiaq8/

>>181 追加
>（圏論（トポス）と高階論理）

こんなのもヒットしたね（＾＾
https://www.amazon.co.jp/dp/4130120573
圏論による論理学―高階論理とトポス 単行本 ? 2007/12/1 清水 義夫
出版社: 東京大学出版会
20世紀後半、数学、計算機科学、論理学などの分野で採用されてきている圏論。関数概念を基本として現象をとらえようというこの方法を、関数型高階論理とトポスを題材にして丁寧に解説する。論理学の観点を中心に、圏論の考え方を紹介するテキスト。

著者略歴 (「BOOK著者紹介情報」より)
清水/義夫
1939年東京に生まれる。1963年東京大学文学部哲学科卒業。1967年東京大学大学院人文科学研究科博士課程退学。現在、千葉工業大学情報科学部教授(本データはこの書籍が刊行された当時に掲載されていたものです)

レビュー
sw
5つ星のうち4.0
目的次第で、よい本です
2010年5月17日
形式: 単行本Amazonで購入
わかりやすく書かれていて読みやすいのですが、著者の目的や興味は、圏論では無く論理学にあることを念頭に読むべき本です。
高階論理と圏、高階論理とトポス・・・などのように、毎回論理学との対応が記述されており、高階論理を学びたい人にはよい一冊である一方、純粋に圏論を学びたい、あるいは別の目的で学びたい人には、もっとよい本があるかもしれません。

星の空
5つ星のうち5.0圏論およびトポスの良い入門書
2009年3月14日
形式: 単行本
圏論を独学で勉強して苦労している人は多いと思います。
マックレーンの「圏論の基礎」は良い本だと思いますが、
議論の半分くらいをはしょっているので、
正直これだけで圏論を理解するのは難しいと思います。
そんなときは本書を読むと良いと思います。
この本は、哲学科の学生に圏論を使った記号述語論理の
講義をすることを前提に書かれており、そのためか、
圏論の話をはしょることなく実に分かり易く解説しています。
使われている図も細部まで良く描かれています。
米田の補題こそ出てきませんが、圏、関手、極限、トポス、
などが実に丁寧に書かれています。
本書を読んでから「圏論の基礎」を読めば、より一層
理解が進むことでしょう。

http://rio2016.5ch.net/test/read.cgi/math/1551963737/182

183: 現代数学の系譜 雑談 古典ガロア理論も読む ◆e.a0E5TtKE  [sage] 2019/03/11(月) 23:36:52.07 ID:NUGiaq8/

>>174

正則性公理に、「もやもや感」がある人のご参考（＾＾
http://www.cs-study.com/koga/set/setRegularity.html
集合論：正則性 (Regularity) 24th Jan. 2018 (Updated) Akihiko Koga
(抜粋)
Axiom of Regularity
∀ A (A ≠ Φ => ∃ X ∈ A (X ∩ A = Φ))
(空でない集合は自分自身とまじわりの無い要素を１つは持つ)
http://www.cs-study.com/koga/set/pictures/SetRegularity00.jpg

本当は，
１．A ∈ A となるような集合 A (つまり，A = { ..., A, ...} ) は存在しない とか
２．A ∋ A1 ∋ A2 ∋ A3 ... という無限列は存在しない
などと言いたいのに，上のように持って回った言い方をする．

正則性公理についてはなんとなく 「もやもや感」が付きまとって嫌な気分になるので，ここでは，正則性公理と上で書いたような性質との間の含意関係などを図をつかって証明して，少しでも「もやもや感」 をなくすことにしたい．
http://www.cs-study.com/koga/set/pictures/RegularityAxiom01.png

[もやもや感」の解消
(このページの内容は 英語版の Wikipedia の Axiom of Regularity の項目 を参考にした．と言うか殆ど絵を入れただけのような気もする)

１．正則性 => A ∋ A1 ∋ A2 ∋ A3 ... という無限列は存在しない
http://www.cs-study.com/koga/set/pictures/RegularityProperty01.png

２．正則性 => A ∈ A となるような集合 A (つまり，A = { ..., A, ...})は存在しない
A を A ∈ A となる集合とする． 次の図（と言って良いかどうか）のように B := {A} とおけば，この B が正則性に反する．
http://www.cs-study.com/koga/set/pictures/RegularityProperty02.png

３．A1 ∋ A2 ∋ A3 ... という無限列は存在しない & 選択公理 => 正則性
対偶をとり，選択公理が成り立つとの仮定の下に，正則性を満たさない集合があったとき，正則性を満たさない集合があったとき，A1 ∋ A2 ∋ A3 ...という無限列が作れることを示します．
ここで無限回の要素の選択が必要ですから，選択公理を使う必要性があることに注意してください．
http://www.cs-study.com/koga/set/pictures/RegularityProperty03.png
(引用終り)
以上

http://rio2016.5ch.net/test/read.cgi/math/1551963737/183

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.053s