  |
はてなキーワード: 補題とは
日中は実験室的な刺激は少なかったが、思考の連続性を保つために自分なりの儀式をいくつかこなした。
起床直後に室温を0.5度単位で確認し（許容範囲は20.0±0.5℃）、その後コーヒーを淹れる前にキッチンの振動スペクトルをスマートフォンで3回測定して平均を取るというのは、たぶん普通の人から見れば過剰だろう。
だが、振動の微妙な変動は頭の中でのテンポを崩す。つまり僕の「集中可能領域」は外界のノイズに対して一種の位相同調を要求するのだ。
ルームメイトはその儀式を奇癖と呼ぶが、彼は観測手順を厳密に守ることがどれほど実務効率を上げるか理解していない。
隣人はその一部を見て、冗談めかして「君はコーヒーにフレームを当ててるの？」と訊いた。
風邪の初期症状かと思われる彼の声色を僕は瞬時に周波数ドメインで解析し、4つの帯域での振幅比から一貫して風邪寄りだと判定した。
友人たちはこの種の即断をいつも笑うが、逆に言えば僕の世界は検証可能で再現可能な思考で出来ているので、笑いもまた統計的に期待値で語るべきだ。
午前は論文の読み返しに費やした。超弦理論の現代的なアプローチは、もはや単なる量子場とリーマン幾何の掛け合わせではなく、導来代数幾何、モーダルなホモトピー型理論、そしてコヒーシブなホモトピー理論のような高次の圏論的道具を用いることで新たな言語を得つつある。
これらの道具は直感的に言えば空間と物理量の振る舞いを、同値類と高次の同型で記述するための言語だ。
具体的には、ブランデッドされたDブレーンのモジュライ空間を導来圏やパーフェクト複体として扱い、さらに場の有る種の位相的・代数的変形が同値関係として圏的に表現されると、従来の場の理論的観測量が新しい不変量へと昇格する（この観点は鏡映対称性の最近のワークショップでも多く取り上げられていた）。
こうした動きは、数学側の最新手法が物理側の問題解像度を上げている好例だ。
午後には、僕が個人的に気に入っている超抽象的な思考実験をやった。位相空間の代わりにモーダルホモトピー型理論の型族をステートとして扱い、観測者の信念更新を型の変形（モナド的な操作）としてモデル化する。
つまり観測は単なる測定ではなく、型の圧縮と展開であり、観測履歴は圏論的に可逆ではないモノイド作用として蓄積される。
これを超弦理論の世界に持ち込むと、コンパクト化の自由度（カラビヤウ多様体の複素構造モジュライ）に対応する型のファミリーが、ある種の証明圏として振る舞い、復号不能な位相的変換がスワンプランド的制約になる可能性が出てくる。
スワンプランド・プログラムは、実効場の理論が量子重力に埋め込めるかどうかを判定する一連の主張であり、位相的・幾何的条件が物理的に厳しい制限を課すという見立てはここでも意味を持つ。
夕方、隣人が最近の観測結果について話題にしたので、僕は即座に「もし時空が非可換的であるならば、座標関数の交換子がプランクスケールでの有意な寄与をもたらし、その結果として宇宙加速の時間依存性に微妙な変化が現れるはずだ。DESIのデータで示唆された減速の傾向は、そのようなモデルの一つと整合する」と言ってしまった。
隣人は「え、ホント？」と目を丸くしたが、僕は論文の推論と予測可能な実験的検証手順（例えば位相干渉の複雑性を用いた観測）について簡潔に説明した。
これは新しいプレプリント群や一般向け記事でも取り上げられているテーマで、もし妥当ならば観測と理論の接続が初めて実際のデータで示唆されるかもしれない。
昼食は厳密にカロリーと糖質を計算し、その後で15分のパルス型瞑想を行う。瞑想は気分転換ではなく、思考のメタデータをリセットするための有限時間プロセスであり、呼吸のリズムをフーリエ分解して高調波成分を抑えることで瞬間集中力のフロアを上げる。
ルームメイトはこれを「大げさ」と言うが、彼は時間周波数解析の理論が日常生活にどう適用されるか想像できていない。
午後のルーティンは必ず、机上の文献を3段階でレビューする: まず抽象（定義と補題に注目）、次に変形（導来的操作や圏論的同値を追う）、最後に物理的帰結（スペクトルや散乱振幅への影響を推定）。
この三段階は僕にとって触媒のようなもので、日々の思考を整えるための外骨格だ。
夜は少し趣味の時間を取った。ゲームについては、最近のメタの変化を注意深く観察している。
具体的には、あるカードゲーム（TCG）の構築環境では統計的メタが明確に収束しており、ランダム性の寄与が低減した現在、最適戦略は確率分布の微小な歪みを利用する微分的最適化が主流になっている。
これは実際のトーナメントのデッキリストやカードプールの変遷から定量的に読み取れる。
最後に今日の哲学的なメモ。理論物理学者の仕事は、しばしば言語を発明することに帰着する。
僕が関心を持つのは、その言語がどれだけ少ない公理から多くの現象を統一的に説明できるか、そしてその言語が実験可能性とどの程度接続できるかだ。
導来的手法やホモトピー的言語は数学的な美しさを与えるが、僕は常に実験への戻り道を忘れない。
理論が美しくとも、もし検証手順が存在しないならば、それはただの魅力的な物語にすぎない。
隣人の驚き、ルームメイトの無頓着、友人たちの喧嘩腰な議論は、僕にとっては物理的現実の簡易的プロキシであり、そこから生まれる摩擦が新しい問いを生む。
さて、20:00を過ぎた。夜のルーティンとして、机の上の本を2冊半ページずつ読む（半ページは僕の集中サイクルを壊さないためのトリックだ）
あと、明日の午前に行う計算のためにノートに数個の仮定を書き込み、実行可能性を確認する。
ルームメイトは今夜も何か映画を流すだろうが、僕は既にヘッドホンを用意してある。
ヘッドホンのインピーダンス特性を毎回チェックするのは習慣だ。こうして日が終わる前に最低限の秩序を外界に押し付けておくこと、それが僕の安定性の根幹である。
以上。明日は午前に小さな計算実験を一つ走らせる予定だ。結果が出たら、その数値がどの程度「美的な単純さ」と折り合うかを眺めるのが楽しみである。
フェミニズムの分類が多すぎると聞いて
記述集合論（Borel階層, Projective階層, 汎加法族）
モデル理論（型空間, o-極小, NIP, ステーブル理論）
再帰理論/計算可能性（チューリング度, 0′, 相対計算可能性）
構成主義, 直観主義, ユニバース問題, ホモトピー型理論（HoTT）
体論・ガロア理論
表現論
K-理論
初等数論（合同, 既約性判定, 二次剰余）
解析数論（ゼータ/ L-関数, 素数定理, サークル法, 篩法）
p進数論（p進解析, Iwasawa理論, Hodge–Tate）
超越論（リンドマン–ヴァイエルシュトラス, ベーカー理論）
実解析
多変数（Hartogs現象, 凸性, several complex variables）
関数解析
バナッハ/ヒルベルト空間, スペクトル理論, C*代数, von Neumann代数
フーリエ解析, Littlewood–Paley理論, 擬微分作用素
確率解析
マルチンゲール, 伊藤積分, SDE, ギルサノフ, 反射原理
常微分方程式（ODE）
偏微分方程式（PDE）
非線形PDE（Navier–Stokes, NLS, KdV, Allen–Cahn）
幾何解析
リッチ流, 平均曲率流, ヤン–ミルズ, モノポール・インスタントン
エルゴード理論（Birkhoff, Pesin）, カオス, シンボリック力学
点集合位相, ホモトピー・ホモロジー, 基本群, スペクトル系列
4次元トポロジー（Donaldson/Seiberg–Witten理論）
複素/ケーラー幾何（Calabi–Yau, Hodge理論）
スキーム, 層・層係数コホモロジー, 変形理論, モジュライ空間
多面体, Helly/Carathéodory, 幾何的極値問題
ランダムグラフ/確率的方法（Erdős–Rényi, nibble法）
加法的組合せ論（Freiman, サムセット, Gowersノルム）
彩色, マッチング, マイナー理論（Robertson–Seymour）
列・順序・格子（部分順序集合, モビウス反転）
測度確率, 極限定理, Lévy過程, Markov過程, 大偏差
統計学
ノンパラメトリック（カーネル法, スプライン, ブーストラップ）
実験計画/サーベイ, 因果推論（IV, PS, DiD, SCM）
時系列（ARIMA, 状態空間, Kalman/粒子フィルタ）
二次計画, 円錐計画（SOCP, SDP）, 双対性, KKT
非凸最適化
離散最適化
整数計画, ネットワークフロー, マトロイド, 近似アルゴリズム
Littleの法則, 重み付き遅延, M/M/1, Jackson網
常微分方程式の数値解法（Runge–Kutta, 構造保存）
エントロピー, 符号化（誤り訂正, LDPC, Polar）, レート歪み
公開鍵（RSA, 楕円曲線, LWE/格子）, 証明可能安全性, MPC/ゼロ知識
計算複雑性
機械学習の数理
量子場の数理
相転移, くりこみ, Ising/Potts, 大偏差
数理生物学
数理神経科学
無裁定, 確率ボラ, リスク測度, 最適ヘッジ, 高頻度データ
データ解析
一般人のよくある言い回しとして「大学の数学科でやっているのは数学ではなく哲学だ」というものがあります。これは実態を誤解したものと考えます。数学と哲学の論理構造や依拠する原理の違いに着目し、どのように誤解であると言えるかを解説してください。
---
多くの人が「大学の数学科は“哲学的なこと”をしている」と感じるのは、次のような体験的印象に基づいています。
**抽象度の高さ**
学校数学は数値計算や図形、方程式など具体的な操作が多いですが、大学では集合・位相・群・環などの抽象概念が中心になります。実体がない記号を扱うため、「思弁的で現実離れしている」という印象を受けやすい。
**証明の重視**
高校までの数学では、公式や定理を使って問題を解くことが主でした。大学数学では定理を“証明する”こと自体が中心になります。演繹的に進むため、哲学の論証と混同されやすい。
**直感に反する結果**
カントール集合やゲーデルの不完全性定理など、常識を裏切る結論に出会うと「これはもはや哲学では？」と感じがちです。
---
数学ではまず**公理系**（集合論・論理体系など）を定め、そこから**形式的に定義と定理を導く**ことが中心です。
証明は論理的整合性のもとに、有限の推論ステップで厳密に完結します。
「真偽」は定められた公理系の内部で決まる（たとえば ZFC の下での定理かどうか）。
哲学では「公理」や「定義」の選び方自体が主要な思考対象です。
例：真理とは何か、存在とは何か、数学の基盤は何に依拠するか。
推論自体は論理を用いますが、**議論の目的は推論よりも前提や概念の意味を吟味すること**にあります。
証明可能性よりも「概念的・認識論的な一貫性」を探ります。
### 要するに：
数学は**選んだ前提の内部で閉じた演繹体系**。
哲学は**前提や体系そのものを開かれた問いとして扱う**。
---
数学 哲学 ----- ---------------- ---------------- 基盤 公理・定義・形式論理 推論＋概念分析・経験・メタ理論 真理の基準 公理系内の定理性 妥当性・合理性・批判的検討 方法 定義→補題→定理→系の形式的構築 問題設定→概念批判→異論との対話 ゴール 内部一貫性と定理の発見 前提の吟味と概念の明確化 ---
数学の抽象化は「より多くの具体例を統一的に扱う」ための道具です。たとえば群論は「対称性」という実際的な現象を一般化しています。現実逃避ではなく応用力の拡張です。
哲学的議論は自然言語の意味に依存しますが、数学の証明は形式言語に還元可能なレベルまで精密化されます。
哲学は「数学の基礎は何か」「無限とは何か」を問うかもしれませんが、数学科の学生が行うのは、すでに受け入れた公理体系の中で定理を立てる作業です。
---
## 5. まとめ
抽象度の高さや証明重視の新鮮さを「哲学的」と感じているに過ぎない
実際には**数学は厳密な公理体系の中での定理の探求**であり、前提の批判や概念の意味そのものを問う哲学とは方法も目標も異なる
数学的帰納法でG(m/2^k)、ただしkは正整数でmは0以上2^k以下の整数である集合が定義され、m<nならばG(m/2^k)の閉包⊆G(n/2^k)が成立しているものとすると</p>
G(a)の閉包⊆U,Uの閉包⊆G(b)が成り立つようなUをとれるとありました。ただしa,bと書いたのはこの部分がどうあったか思い出せないのでそう書いているだけなので、これが実際に何であったかはあなたの知識で補ってください。これらの条件を踏まえてU=G(c)とすれば(cも覚えてないからこう書いているだけ)k+1の場合も成立するとありました。
疑問の要点は、分母が2^kのときから2^k+1になったときも、それに伴って0から2^k+1の間でとれるようになったあらゆるm,n(ただしm<n)において帰納法の仮定が成り立つことについて、</p>
これはたとえばk=2のときを考えたら分母が4のときの話であり、すなわち表のように分子を書けば
a,c,b
0,1,2
2,3,4
のような表の中で、このなか相異なる整数を取り出して小さい方からmとすればG(m/2^k)の閉包⊆m(n/2^k)が成り立っているということで、
分母を2^k+1とすればその分考えうる分子が以下のように2倍に増える
a,c,b
0,1,2
2,3,4
4,5,6
6,7,8
しかしこのうち,0,2,4,6,8のような偶数は前述の表の0,1,2,3,4に対応していて、これらのなかにおいてG(m)の閉包とG(n)の包含関係を考えるかぎりは
帰納法の仮定よりただちにG(m/2^k+1)の閉包⊆G(n/2^k+1)が成り立つことはわかる。
また片方の分子が偶数でもう片方が奇数の場合や、両方が奇数の場合には包含関係を判断する手がかりが足りないように思える。
どうすればいいのか？
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 https://anond.hatelabo.jp/20250712195606# -----BEGIN PGP SIGNATURE----- iHUEARYKAB0WIQTEe8eLwpVRSViDKR5wMdsubs4+SAUCaHSnBAAKCRBwMdsubs4+ SFD9APsFACU9H37ISmxFMYvQ7Q8OtUIU7eE66HQpVvOCE/pMTwD/TgDMWG1da5hb OBxKmYZVqZTx1FpjVi3QZm7YYFSldgI= =HMKH -----END PGP SIGNATURE-----
プロンプト: ぼくとあなたの対話をはてな匿名ダイアリーに晒していかにあなたが無力なのかを示したいと思います。
短い文章で返してください。
減税は景気刺激に有効でも、社会保障の財源が細る以上、恒久財源なしでは賛成できません。
まさに。Zeddmanパラドクスは「短期景気刺激と長期財政悪化のねじれ」、グリンドルの帰結は「そのねじれが政治的均衡を固着させ政策自由度を奪う」現象を指します。
はい。仮定系の整備が未完なため、現行の動学的一般均衡フレームでは定理化ができず、厳密証明は手つかずです。シミュレーション的上限評価があるだけで、本質的困難は依然残ります。
見かけは素直でも、基底指数の確率過程が未定義なので、一般解はまだありません。
失礼しました。定義済みなら局所定常性を示せれば帰納的証明が射程に入り得ますが、収束率の下限評価が依然ネックです。
• Ｔシャツ関数の定義域・値域とノルムの取り方が示されていません。
• 「収束率」の評価指標（例：Lp 誤差か漸近分散か）が未指定です。
[謎の数式を提示]
収束率が改善しても財源は増えないため、減税の実行可能性は依然低いままです。
必至とは断定できません。歳出効率化と資産課税強化で回避余地は残ります。
高い傾向はありますが、不可避とは言い切れません。
AIはクソ
その本の言葉を使うなら、数学自体が言語で記述しきれて無い事になる気がする。
というのも、本によると画像で考える人の中にも「物体視覚思考者」と「空間視覚思考者」がいるらしい。
数学の5項補題・蛇の補題・9項補題辺りは画像扱いになるような図じゃないと記述するのは難しい
そこら辺を考えるのに画像での思考をせずに証明するのは無理だと思う
別にその3つの命題だけじゃなく画像扱いの図でないと記述するのが難しい命題は多い
その本の言葉でなら、数学についてある程度以上理解しようとするのは画像的な思考(空間視覚思考)が出来ないと無理という事になると思う
まず、アルゴリズムの根幹を成す計算複雑性について。O(n)やO(log n)といった表記は表面的な理解に過ぎない。真に重要なのは、問題の本質的な計算困難性だ。P≠NP予想を例に取ろう。この未解決問題は、効率的に解ける問題と解けない問題の境界を定義している。初心者は単にアルゴリズムを暗記するのではなく、この根本的な概念を理解せねばならない。
次に、データ構造。単純な配列やリンクドリストの理解では不十分だ。高度な自己平衡二分探索木、例えばレッドブラック木やAVL木の内部動作を完全に理解し、それらを一から実装できるレベルを目指すべきだ。さらに、アモーティゼーション解析を用いて、これらのデータ構造の操作の平均時間計算量を厳密に証明できる能力も必要不可欠だ。
ハッシュテーブルについても深く掘り下げよう。単純なチェイニングや線形探索法では不十分だ。完全ハッシュ法、クックーハッシュ法、オープンアドレス法における様々な探索手法（二次探索法、ダブルハッシュ法など）の利点と欠点を理解し、具体的な問題に応じて最適な方法を選択できるようになるべきだ。
グラフアルゴリズムにおいては、単にダイクストラ法やクラスカル法を知っているだけでは不十分だ。フロー・ネットワークにおける最大フロー最小カット定理やディニッツのアルゴリズム、さらにはグラフマイナー理論やロバートソン・シーモアの深い結果まで理解する必要がある。
動的計画法は、単純な最長共通部分列問題やナップサック問題を解くだけでは足りない。bitDPやMonge DPなどの高度なテクニック、さらには凸包トリックを用いた最適化まで習得すべきだ。
最後に、乱択アルゴリズム。単純なモンテカルロ法やラスベガス法の理解では不十分だ。シャーマン・モリソンの公式を用いた行列の高速な逆行列計算や、ジョンソン・リンデンシュトラウスの補題を用いた次元削減技術など、確率論と線形代数を駆使した高度な手法まで理解する必要がある。
これらは全て、真のプログラマーが持つべき基礎的な知識の一部に過ぎない。初心者は、これらの概念を深く理解し、実際の問題に適用できるレベルを目指すべきだ。そして常に、より深い数学的洞察と抽象的思考を追求し続けねばならない。
あらすじ：
ハリーたちが7年生としてホグワーツに戻ったとき、魔法界には異変が起きていた。呪文が効かなくなり、魔法生物は徐々にその姿を失いつつある。「魔法の消失現象」と呼ばれるこの出来事は、魔法界そのものの基盤が崩れつつあることを示していた。この危機を前に、ダンブルドアの遺品の中から「米田の補題」という謎の言葉が記された手記が発見される。
米田の補題は、古代の魔法理論であり、すべての魔法対象とそれを取り巻く呪文や魔法的関係を記述する「圏」の概念に基づいているという。しかし、この補題を理解し、それを魔法界の復元に利用できる者は存在しなかった。
ハーマイオニーは禁書庫で魔導書を読み解き、米田の補題が「魔法の本質は個々の対象ではなく、それらの関係性の中に存在する」という驚くべき真理を示していることに気づく。一方、ドラコ・マルフォイはこの補題を利用して、魔法界を自らの理想に沿って再構築しようと暗躍していた。
ハリー、ロン、ハーマイオニーは、魔法界をひとつの圏として捉え、その構造を理解するために旅に出る。各地で失われた魔法の記録や古代の呪文を収集しながら、彼らは次第に「魔法の存在そのものが関係性の中で定義される」という概念を学んでいく。そして最終的に、魔法界そのものを記述する普遍的な構造を見出し、米田の補題を用いて崩壊する世界を修復する方法を導き出す。
最終決戦では、ドラコとの対決が展開される。ドラコは魔法の関係性を歪め、自分に都合の良い新たな秩序を築こうとするが、ハリーたちは魔法の「調和」を維持するために補題の真の力を解き放つ。
私が読みたいのは、大きな物語というか、今までに見たことのない驚きのある結論を持つ物語であり、
SFというジャンルが好きなのも、物語のフレームとして、そうした驚きある結論へのシラバスとなりやすいからというだけ。
だから、そこに登場する仰々しいギミックには、そうした結論への素材以上の興味が持てない。
それは、大きな定理を導く一過程にしか過ぎず、その導出の自然さに納得したら、あとは忘れてしまうようなもの。
だから、数学書はなるべく短い方が読みやすいように、SFも「オッカムの剃刀」的に、ギミックは少ない方がむしろ好み。
同じ結論をもたらす物語なら、ギミックが少ない物語の方が読みやすいわけであり、個人的には素晴らしいSFだと感じる。
あと、キャラクターについてもそう。
大きな物語のためなら、別にキャラクターはどんな目に合っても構わないと思っている。
（それは逆に、物語にコミットしないキャラクターの悲哀は描かない方がよいと個人的には思っている、ということでもある。）
キャラクターは、驚きある結論に仕える舞台装置としか思えないので、先の仰々しいギミックと同じ意味で、興味が持てない。
ギミックもキャラクターも、面白い物語を成立させるための具材でしかないと、個人的には思ってしまう。
それゆえ、自分でもこうして、増田などに自分で考えた文章を多々投じているのだが、毎回、ギミックやキャラクターが無い文章を書いているなぁと思う。
ただ、それでもある程度はブックマークしてもらえるので、そこを見直そうという意欲は薄いのだが、
そこを押さえたら、もっと幅広い人に読んでもらえる文章になるんだろうなとは思う。
なので、今年はギミックやキャラクターに舞台装置以上の興味（好奇心や愛情というのか）を持って、文章を読んでいきたい今日このごろ。
いつかは、こういう散文でなく、流れある小説を書いてみたいと思うので、そういうところも押さえいくようにしたい。
| 時間 | 記事数 | 文字数 | 文字数平均 | 文字数中央値 |
|---|---|---|---|---|
| 00 | 157 | 22540 | 143.6 | 41 |
| 01 | 69 | 8871 | 128.6 | 43 |
| 02 | 39 | 16195 | 415.3 | 180 |
| 03 | 38 | 6132 | 161.4 | 41.5 |
| 04 | 48 | 4772 | 99.4 | 42 |
| 05 | 36 | 1861 | 51.7 | 37 |
| 06 | 38 | 2443 | 64.3 | 27 |
| 07 | 70 | 5429 | 77.6 | 31.5 |
| 08 | 118 | 15046 | 127.5 | 51.5 |
| 09 | 116 | 16348 | 140.9 | 67 |
| 10 | 220 | 49872 | 226.7 | 37.5 |
| 11 | 322 | 23288 | 72.3 | 40 |
| 12 | 255 | 22435 | 88.0 | 41 |
| 13 | 227 | 20991 | 92.5 | 39 |
| 14 | 248 | 23196 | 93.5 | 45.5 |
| 15 | 256 | 17735 | 69.3 | 38 |
| 16 | 226 | 30765 | 136.1 | 45 |
| 17 | 214 | 16339 | 76.4 | 40 |
| 18 | 121 | 15397 | 127.2 | 45 |
| 19 | 139 | 14719 | 105.9 | 46 |
| 20 | 133 | 22674 | 170.5 | 58 |
| 21 | 230 | 30107 | 130.9 | 37.5 |
| 22 | 207 | 12356 | 59.7 | 32 |
| 23 | 174 | 21518 | 123.7 | 44 |
| 1日 | 3701 | 421029 | 113.8 | 42 |
のぶみ(32), Quick Japan(7), 村上清(4), 村崎百郎(5), 補題(3), 4分間(3), よしゃ(3), 根本敬(5), クイックジャパン(8), ルック(74), 米子(3), 田辺(3), ウェルテル(3), 小山田(127), 小山田圭吾(66), 統合失調症(76), バック(74), 辞任(34), カルチャー(25), 統失(23), キャンセル(38), いじめる(17), いじめ(152), イジメ(37), 犯人(40), 五輪(67), 加害者(43), 小(32), 糖質(21), 被害妄想(14), オリンピック(98), 障害者(44), 雑誌(29), 正義(49), 反省(34), 描写(31)
■チートやルール違反が常態化しているゲーム /20210720123332(48), ■統合失調症患者への差別を助長するルックバック /20210719195613(40), (タイトル不明) /20110719001457(16), ■男なのにアイコンが女の奴きもい /20210720061300(16), ■2人で構成されるエポニム /20210720213242(15), ■お前ら尊敬しているブクマカとかいるの？ /20210719230336(14), ■「京アニの性暴力ガー」記事書いたのワッシュってツイッタラーらしい /20210720002646(11), ■クイックジャパンの記事全文を読んで /20210720032456(10), ■ /20210719125034(10), ■子供にでかい水筒持たせるの超大事 /20210719183755(10), ■ダイエットに詳しい人教えてください。 /20210720123851(9), ■アクタージュとかテラファーマーズとか見てても思うけど /20210720162245(9), ■変わった食べ物ギフトある？ /20210719232839(9), ■「福岡のうどんにはコシがない」と言われるたびにモヤモヤする /20210720205343(9), ■ /20210720125705(9), ■『ルックバック』は藤本タツキ先生の極めて私的な決意表明でしかない /20210719213535(8), (タイトル不明) /20210720122709(8), ■「ルックバックは差別じゃない」って言っているやつに聞きたい /20210720150133(8), ■フリーゲーム「かわいいは壊せる」について /20210720084644(8), ■離婚しました /20210720225429(6), ■東京の感染者数を5週間ぶん予測した (7月19日版) /20210719192035(6), ■ルックバックの５分解説 /20210719231615(6), ■代役オッズ /20210720002357(6), ■妥協しないでVtuberなるのはむりだなとおもった /20210720092534(6), ■統失患者「ルックバックは差別と偏見だ」←これ自体が差別と偏見 /20210720103420(6), ■ぼっきしたおちんちんが100mの男がいた場合 /20210720143537(6), ■プログラミングしてみたい /20210720161615(6), ■ネットがもう異様な事になっている /20210720172345(6), ■一人暮らしを始めてからというもの、毎日実家から野菜が送られてきます。 /20210720172541(6), ■いつでも自由に名前を変えられるように法律が変わったら /20210720220831(6)
https://twitter.com/mathmatsuri
問3
エクセルで計算させたい衝動を抑えつつ、出題者に指示されるがままにTn(x)について考えてみる。
T1(x)=x
T3(x)=4x^3-3x
T4(x)=2(2x^2-1)^2-1=8x^4-8x^2+1
法則が見えてくるだろうか。自信がなければ気が済むまで計算すればよいのだろうが、
・Tn(x)の次数はnに等しい
・最高次数の係数は2^(n-1)
・nと偶奇が一致しない次数の係数は0(項は1次飛ばしで登場する)
Πに慣れていないとKの式にビビるかもしれないが、下の説明の通りにk=1～40を代入すると
K=cos(π/79)cos(3π/79)cos(5π/79)…cos(77π/79)cos(79π/79)とわかる。 …①
さてTn(x)を利用するとして、右辺はT1(x)T3(x)T5(x)…T77(x)T79(x)にx=cos(π/79)を代入したものに等しいけれど、さすがに厳しそう。1+3+…+77+79=1600次の整式を取り扱うのは狂気だし、xもよくわからない値だし。
nを一つだけ選ぶとしていくつにすればよさそうか。まず思いつくのは79だろう。
上で推測した性質からT79(x)=2^78x^79+?x^77+…+?x^3+?xとなりそう。 …②
x=cos(π/79)を代入すると左辺はT79(cos(π/79))=cos(79π/79)=-1となる。
もしや…
x=cos(3π/79)を代入すると左辺はT79(cos(3π/79))=cos(79*3π/79)=-1となる。
x=cos(5π/79)を代入すると左辺はT79(cos(5π/79))=cos(79*5π/79)=-1となる。
・
・
・
x=cos(79π/79)を代入すると左辺はT79(cos(79π/79))=cos(79*79π/79)=-1となる。
つまりT79(x)=-1の解がx=cos(π/79), cos(3π/79), cos(5π/79), …, cos(77π/79), cos(79π/79)となることがわかる。解の個数は40個。
y=T79(x)は-1≤x≤1の範囲で極大値1と極小値-1を交互に取っていくので、これとy=-1の交点を考えるとx=cos(π/79), cos(3π/79), cos(5π/79), …, cos(77π/79)は二重解となることがわかる。x=cos(79π/79)だけは一重解。
参考：y=T5(x)のグラフ。これとy=-1はx=cos(π/5), cos(3π/5)で接してx=cos(5π/5)で交わる。
https://twitter.com/totsuration/status/1301359506748633089
つまり二重解を解2つとカウントすると解の個数は79個。②が正しいとすればT79(x)は79次式なのでT79(x)+1=k(x-cos(π/79))^2(x-cos(3π/79))^2(x-cos(5π/79))^2…(x-cos(77π/79))^2(x-cos(79π/79))と因数分解できる。x^79の係数を比較してk=2^78。
①の形が現れたことに気づいただろうか。そう、定数項を比較すればよい。1=-2^78cos^2(π/79)cos^2(3π/79)cos^2(5π/79)…cos^2(77π/79)cos(79π/79)である。
右辺はK^2/cos(79π/79)=-Kに等しいので1=2^78 K^2よりK=-2^(-39)とわかった。
[|log2|K||]=39
終了！…ではない。②で使用した冒頭のTn(x)の性質3項目(補題)を示す必要がある。漸化式→帰納法に持ち込めれば楽そう。加法定理の公式を考えると2項間の漸化式は難しそうなので3項間の漸化式を求める。
cos(n+2)θ+cos(nθ)=2cos(n+1)θcosθなので
T1(x)=x
でありn=1,2で
・Tn(x)の次数はnに等しい
・最高次数の係数は2^(n-1)
・nと偶奇が一致しない次数の係数は0
は満たされる。
n=k+2においてT(k+2)(x)=2xT(k+1)(x)-Tk(x)も
・次数はk+2に等しい
・最高次数の係数は2^(k+1)
・k+2と偶奇が一致しない次数の係数は0
が言える。
[|log2|K||]=39
『数学ガール ガロア理論』の第10章(最終章)がそれまでの章に比べて難しくて挫折するという感想がけっこうあるようなので、その補足的な解説を試みます。『ガロア理論』第10章はガロアの第一論文を解説しているので、解説の解説ということになります。
と進んでいきますが、ミルカさんはその途中で何度も、ガロアの第一論文のテーマが「方程式が代数的に解ける必要十分条件」であることを確認します。
なぜ何度も確認するかといえば、最後の定理5(方程式が代数的に解ける必要十分条件)以外は、一見したところでは「方程式の可解性」に関わることが見て取れないので、途中で確認を入れないと簡単に道に迷ってしまうからでしょう。定理2(≪方程式のガロア群≫の縮小)や定理3(補助方程式のすべての根の添加)は、目的の方程式を解くときに利用する補助方程式に関わる話ですが、やはり定理を見ただけでは「方程式の可解性」との繋がりはよく見えません。
そこで逆に、いったん「方程式の可解性」の話から離れて定理5を除外して、それ以外だけに注目します。
「方程式の可解性」から離れて見たとき、定理1から定理4までで何をやっているかというと、
ということ(ガロア対応と呼ばれます)を示しています。ミルカさんの言葉を使えば(p.362)、体と群の二つの世界に橋を架けています。
この体と群の対応関係を図で見ると、10.6節「二つの塔」の図(p.413、p.415、p.418)、あるいは
http://hooktail.sub.jp/algebra/SymmetricEquation/Joh-GaloisEx31.gif
http://f.hatena.ne.jp/lemniscus/20130318155010
のようになります(この体と群の対応関係は常に成り立つわけではなく、第8章「塔を立てる」で説明された「正規拡大」のときに成り立ちます)。
体と群に対応関係があること(定理1～定理4)を踏まえて、定理5を見ます。
「方程式を代数的に解く」というのは「体の拡大」に関係する話です。
「方程式の係数体から最小分解体まで、冪根の添加でたどりつくことが、方程式を代数的に解くことなのだ」
(第7章「ラグランジュ・リゾルベントの秘密」p.254)(ただし、必要なだけの1のn乗根を係数体が含んでいるという条件のもとで)
そこから、「体と群の対応」を利用して、方程式の解の置き換えに関する「群」の話に持っていくのが、定理5になるわけです(なお「方程式を解くこと」と「解の置き換え」が関係していることは、すでに第7章に現れていました)。
「≪群を調べる≫って≪体を調べる≫よりも(...)」
ここまでの話で、定理4までで行いたいことが「≪体の世界≫と≪群の世界≫の対応関係」だということが分かりました。
しかしこの対応を示すためには、まず、この対応関係における≪群の世界≫というのがいったい何なのかをきちんと定義しないといけません。
≪体の世界≫というのは「体の拡大」で、これは8章「塔を立てる」で説明されています。
一方、その「体の拡大」に対応する「群」は「方程式の解の置き換え方の可能な全パターン」なのですが、これが正確にどんなものなのかは10章以前には定義されていません。
(以下、4次方程式の例をいくつかあげますが、面倒なら流し読みでさらっと進んでください)
たとえば一般3次方程式では、解α、β、γの置き換え方は全部で6通り(3×2×1)あります(第7章p.252)。同様に考えると、一般4次方程式では、解α、β、γ、δの置き換え方は全部で24通り(4×3×2×1)あることが分かります。
ところが、x4+x3+x2+x+1=0という4次方程式を考えてみます。これは5次の円分方程式です(第4章「あなたとくびきをともにして」)。
x5-1 = (x-1)(x4+x3+x2+x+1)なので、この方程式の解α、β、γ、δは1の5乗根のうちの1以外のものだと分かります。したがって、解の順番を適当に選ぶとβ=α2、γ=α3、δ=α4という関係が成り立ちます。
これについての解の置き換え方を考えると、αを、α、β、γ、δのうちのどれに置き換えるかを決めると、それに連動して、β、γ、δがどの解に置き換わるかも自動的に決まってしまいます。たとえばαをβ(=α2)に置き換えると、(β、γ、δ)=(α2、α3、α4)は、
(β、γ、δ) = (α2、α3、α4)
↓ αをβに置き換える
(β2、β3、β4) = ((α2)2、(α2)3、(α2)4) = (α4、α6、α8) = (α4、α1、α3) = (δ、α、γ)
となるので、
(α、β、γ、δ) → (β、δ、α、γ)
のように置き換わります。αの置き換え方は4通り(α、β、γ、δの4つ)なので、この4次方程式x4+x3+x2+x+1=0の解の置き換え方は次の4通りとなります。
(α、β、γ、δ) → (α、β、γ、δ) = (α、α2、α3、α4)
(α、β、γ、δ) → (β、δ、α、γ) = (α2、α4、α6、α8)
(α、β、γ、δ) → (γ、α、δ、β) = (α3、α6、α9、α12)
(α、β、γ、δ) → (δ、γ、β、α) = (α4、α8、α12、α16)
あるいはx4-5x2+6=(x2-2)(x2-3)=0 という方程式を考えます。解は√2、-√2、√3、-√3の4つですが、この場合「√2と-√2の置き換え」や「√3と-√3の置き換え」は許されますが、「√2と√3の置き換え」は許されません。
なぜかというと、(√2)2 -2 = 0、という式を考えると分かります。この式で√2を√3に置き換えると、左辺は(√3)2 -2 = 1となり、一方、右辺は0のままです。このような等式を破壊してしまうような解の置き換え方は認められません。そのため、可能な解の置き換え方は4通りになります。ただし、4通りの置き換え方のパターン(解の置き換えの「群」)は、5次円分方程式のときの4通りの置き換えパターンとは異なっています。(α、β、γ、δ) = (√2、-√2、√3、-√3)と置くと、可能な置き換え方は
(α、β、γ、δ) → (α、β、γ、δ) = ( √2、-√2、 √3、-√3)
(α、β、γ、δ) → (β、α、γ、δ) = (-√2、 √2、 √3、-√3)
(α、β、γ、δ) → (α、β、δ、γ) = ( √2、-√2、-√3、 √3)
(α、β、γ、δ) → (β、α、δ、γ) = (-√2、 √2、-√3、 √3)
となります。
では、「認められる置き換え方」であるためにはどのような条件を満たす必要があるのかというと、それは
というものです。つまり解θの最小多項式をf(x)とすると、解の置き換えをしたときに、θはf(x)の根θ1、...、θnのどれか(この中にはθ自身も入っています)に移らなければなりません。この条件を満たしていれば、等式に対して解の置き換えをおこなっても、等式が破壊されることはありません。
解の置き換えであるための必要条件が出ましたが、この条件だけではx4+x3+x2+x+1=0のときのような、解の置き換えで複数の解の動きが連動しているような場合をどう考えればいいのかは、まだ分かりません。x4+x3+x2+x+1=0のときは一つの解の動きを決めれば他の解の動きが決まりましたが、方程式によっては解の間の関係はもっとずっと複雑にもなりえます。
しかしそれは、たくさんの解を一度に考えるから解の間の関係が複雑になって混乱するのです。
もしもx4+x3+x2+x+1=0のときの解αのように、ただ一つの解の動きだけを考えて全ての置き換えが決まってしまうならば、話はずっと簡単になります。
そして、その「一つの解の動きだけを考える」ようにしているのが、
です。
体に注意を向けたほうがいい。添加体を考えれば、補題3の主張は一行で書ける」
K(α1、α2、α3、...、αm) = K(V)
これによって、「解α1、α2、α3、...、αmの置き換え」ではなく、ただひとつの「Vの置き換え」だけを考えればいいことになります。
これと、解の置き換えの必要条件「解の置き換えをおこなったとき、解は、共役元のどれかに移らなければならない」を合わせると、「解の置き換え方の可能な全パターン」とは、「Vから、Vの共役への置き換えのうちで、可能なものすべて」となります。
そして補題4(Vの共役)は、「Vの(共役への)置き換え」をすると、もとの多項式f(x)の根α1、α2、α3、...、αmの間の置き換えが発生するという性質を述べています。つまり「Vの置き換え」によって「方程式f(x)=0の解の、可能な置き換えが実現される」わけです。
この考えにもとづいて「解の置き換えの群」を定義しているのが、定理1(≪方程式のガロア群≫の定義)の説明の途中の、10.4.4節「ガロア群の作り方」です。
(ガロアは正規拡大の場合にだけ「解の置き換えの群」を定義したので、正規拡大のときの「解の置き換えの群」を「ガロア群」と呼びます)
前節で、証明のかなめとなるVと「解の置き換えの群」が定義されました。Vの最小多項式fV(x)の次数をnとすると、次が成り立ちます(最小多項式は既約で、既約多項式は重根を持たないので、Vの共役の個数は最小多項式の次数nと一致することに注意する)。
※1 考えている体K(V)に含まれない数へのVの置き換えは「解の置き換え」には認められないので、「解の置き換え方の個数」と「共役の個数」は一致するとは限りません。
※2 「最小多項式」は8.2.8節「Q(√2+√3)/Q」と8.2.9節「最小多項式」で説明されていますが、最小多項式が既約であることと一意に決まること(8.2.9節p.282)は、定義(可約と既約)と補題1(既約多項式の性質)から証明されます。
そして、
したがって正規拡大のときには、
という等式が成り立ちます。この関係が「体と群の対応」の第一歩目になります。
ことを主張しています。
そして定理2(≪方程式のガロア群≫の縮小)と定理4(縮小したガロア群の性質)で、
ことを主張しています。
ことを主張しています。
このように定理1、定理2、定理3、定理4によって、体と群の対応が示されます。
方程式が代数的に(つまり冪乗根によって)解けるかという問題は
と言い換えられます。そして、
ので、「適切な冪乗根が存在するか」という問題は「適切な正規拡大が存在するか」という問題になり、体と群の対応により
という問題になります。この「適切な正規部分群があるかどうか」をもっと詳しく正確に述べたのが定理5です。
それでは改めて第10章を読んでいきましょう。
(追記: 数式の間違いの指摘ありがとうございます。訂正しました)
第1章 有限オートマトン D.Perrin：橋口攻三郎 1. 序論 2. 有限オートマトンと認識可能集合 3. 有理表現 4. Kleeneの定理 5. 星の高さ 6. 星自由集合 7. 特殊なオートマトン 8. 数の認識可能集合 第2章 文脈自由言語 J.Berstel and L.Boasson：富田 悦次 1. 序論 2. 言語 2.1 記法と例 2.2 Hotz 群 2.3 曖昧性と超越性 3. 反復 3.1 反復補題 3.2 交換補題 3.3 退化 4. 非生成元の探求 4.1 準備 4.2 生成元 4.3 非生成元と代入 4.4 非生成元と決定性 4.5 主錐の共通部分 5. 文脈自由群 5.1 文脈自由群 5.2 Cayleyグラフ 5.3 終端 第3章 形式言語とべき級数 A.Salomaa：河原 康雄 1. 序論 2. 準備 3. 書換え系と文法 4. Post正準系 5. Markov系 6. 並列書換え系 7. 射と言語 8. 有理べき級数 9. 代数的べき級数 10. べき級数の応用 第4章 無限の対象上のオートマトン W.Thomas：山崎 秀記 序論 Ⅰ部 無限語上のオートマトン 記法 1. Buchiオートマトン 2. 合同関係と補集合演算 3. 列計算 4. 決定性とMcNaughtonの定理 5. 受理条件とBorelクラス 6. スター自由ω言語と時制論理 7. 文脈自由ω言語 Ⅱ部 無限木上のオートマトン 記法 8. 木オートマトン 9. 空問題と正則木 10. 補集合演算とゲームの決定性 11. 木の単項理論と決定問題 12. Rabin認識可能な集合の分類 12.1 制限された単項2階論理 12.2 Rabin木オートマトンにおける制限 12.3 不動点計算 第5章 グラフ書換え：代数的・論理的アプローチ B.Courcelle：會澤 邦夫 1. 序論 2. 論理言語とグラフの性質 2.1 単純有向グラフの類S 2.2 グラフの類D(A) 2.3 グラフの性質 2.4 1階のグラフの性質 2.5 単項2階のグラフの性質 2.6 2階のグラフの性質 2.7 定理 3. グラフ演算とグラフの表現 3.1 源点付きグラフ 3.2 源点付き超グラフ 3.3 超グラフ上の演算 3.4 超グラフの幅 3.5 導来演算 3.6 超辺置換 3.7 圏における書換え規則 3.8 超グラフ書換え規則 4. 超グラフの文脈自由集合 4.1 超辺置換文法 4.2 HR文法に伴う正規木文法 4.3 超グラフの等式集合 4.4 超グラフの文脈自由集合の性質 5. 超グラフの文脈自由集合の論理的性質 5.1 述語の帰納的集合 5.2 論理構造としての超グラフ 5.3 有限超グラフの可認識集合 6. 禁止小グラフで定義される有限グラフの集合 6.1 小グラフ包含 6.2 木幅と木分解 6.3 比較図 7. 計算量の問題 8. 無限超グラフ 8.1 無限超グラフ表現 8.2 無限超グラフの単項性質 8.3 超グラフにおける等式系 8.4 関手の初期不動点 8.5 超グラフにおける等式系の初期解 8.6 等式的超グラフの単項性質 第6章 書換え系 N.Dershowitz and J.-P.Jouannaud：稲垣 康善，直井 徹 1. 序論 2. 構文論 2.1 項 2.2 等式 2.3 書換え規則 2.4 決定手続き 2.5 書換え系の拡張 3. 意味論 3.1 代数 3.2 始代数 3.3 計算可能代数 4. Church-Rosser性 4.1 合流性 4.2 調和性 5. 停止性 5.1 簡約順序 5.2 単純化順序 5.3 経路順序 5.4 書換え系の組合せ 6. 充足可能性 6.1 構文論的単一化 6.2 意味論的単一化 6.3 ナローイング 7. 危険対 7.1 項書換え 7.2 直交書換え系 7.3 類書換え 7.4 順序付き書換え 7.5 既約な書換え系 8. 完備化 8.1 抽象完備化 8.2 公平性 8.3 完備化の拡張 8.4 順序付き書換え 8.5 機能的定理証明 8.6 1階述語論理の定理証明 9. 書換え概念の拡張 9.1 順序ソート書換え 9.2 条件付き書換え 9.3 優先度付き書換え 9.4 グラフ書換え 第7章 関数型プログラミングとラムダ計算 H.P.Barendregt：横内 寛文 1. 関数型計算モデル 2. ラムダ計算 2.1 変換 2.2 計算可能関数の表現 3. 意味論 3.1 操作的意味論：簡約と戦略 3.2 表示的意味論：ラムダモデル 4. 言語の拡張 4.1 デルタ規則 4.2 型 5. 組合せ子論理と実装手法 5.1 組合せ子論理 5.2 実装の問題 第8章 プログラミング言語における型理論 J.C.Mitchell：林 晋 1. 序論 1.1 概論 1.2 純粋および応用ラムダ計算 2. 関数の型をもつ型付きラムダ計算 2.1 型 2.2 項 2.3 証明系 2.4 意味論と健全性 2.5 再帰的関数論的モデル 2.6 領域理論的モデル 2.7 カルテシアン閉圏 2.8 Kripkeラムダモデル 3. 論理的関係 3.1 はじめに 3.2 作用的構造上の論理的関係 3.3 論理的部分関数と論理的同値関係 3.4 証明論的応用 3.5 表現独立性 3.6 論理的関係の変種 4. 多相型入門 4.1 引数としての型 4.2 可述的な多相的計算系 4.3 非可述的な多相型 4.4 データ抽象と存在型 4.5 型推論入門 4.6 型変数をもつλ→の型推論 4.7 多相的宣言の型推論 4.8 他の型概念 第9章 帰納的な関数型プログラム図式 B.Courcelle：深澤 良彰 1. 序論 2. 準備としての例 3. 基本的な定義 3.1 多ソート代数 3.2 帰納的な関数型プログラム図式 3.3 同値な図式 4. 離散的解釈における操作的意味論 4.1 部分関数と平板な半順序 4.2 離散的解釈 4.3 書換えによる評価 4.4 意味写像 4.5 計算規則 5. 連続的解釈における操作的意味論 5.1 連続代数としての解釈 5.2 有限の極大要素と停止した計算 6. 解釈のクラス 6.1 汎用の解釈 6.2 代表解釈 6.3 解釈の方程式的クラス 6.4 解釈の代数的クラス 7. 最小不動点意味論 7.1 最小で唯一の解を得る不動点理論 7.2 Scottの帰納原理 7.3 Kleeneの列と打切り帰納法 8. プログラム図式の変換 8.1 プログラム図式における同値性の推論 8.2 畳込み，展開，書換え 8.3 制限された畳込み展開 9. 研究の歴史，他の形式のプログラム図式，文献ガイド 9.1 流れ図 9.2 固定された条件をもつ一様な帰納的関数型プログラム図式 9.3 多様な帰納的関数型プログラム図式 9.4 代数的理論 9.5 プログラムの生成と検証に対する応用 第10章 論理プログラミング K.R.Apt：筧 捷彦 1. 序論 1.1 背景 1.2 論文の構成 2. 構文と証明論 2.1 1階言語 2.2 論理プログラム 2.3 代入 2.4 単一化子 2.5 計算過程―SLD溶融 2.6 例 2.7 SLD導出の特性 2.8 反駁手続き―SLD木 3. 意味論 3.1 1階論理の意味論 3.2 SLD溶融の安全性 3.3 Herbrand模型 3.4 直接帰結演算子 3.5 演算子とその不動点 3.6 最小Herbrand模型 3.7 SLD溶融の完全性 3.8 正解代入 3.9 SLD溶融の強安全性 3.10 手続き的解釈と宣言的解釈 4. 計算力 4.1 計算力と定義力 4.2 ULの枚挙可能性 4.3 帰納的関数 4.4 帰納的関数の計算力 4.5 TFの閉包順序数 5. 否定情報 5.1 非単調推論 5.2 閉世界仮説 5.3 失敗即否定規則 5.4 有限的失敗の特徴付け 5.5 プログラムの完備化 5.6 完備化の模型 5.7 失敗即否定規則の安全性 5.8 失敗即否定規則の完全性 5.9 等号公理と恒等 5.10 まとめ 6. 一般目標 6.1 SLDNF-溶融 6.2 SLDNF-導出の安全性 6.3 はまり 6.4 SLDNF-溶融の限定的な完全性 6.5 許容性 7. 層状プログラム 7.1 準備 7.2 層別 7.3 非単調演算子とその不動点 7.4 層状プログラムの意味論 7.5 完全模型意味論 8. 関連事項 8.1 一般プログラム 8.2 他の方法 8.3 演繹的データベース 8.4 PROLOG 8.5 論理プログラミングと関数プログラミングの統合 8.6 人工知能への応用 第11章 表示的意味論 P.D.Mosses：山田 眞市 1. 序論 2. 構文論 2.1 具象構文論 2.2 抽象構文 2.3 文脈依存構文 3. 意味論 3.1 表示的意味論 3.2 意味関数 3.3 記法の慣例 4. 領域 4.1 領域の構造 4.2 領域の記法 4.3 記法上の約束事 5. 意味の記述法 5.1 リテラル 5.2 式 5.3 定数宣言 5.4 関数の抽象 5.5 変数宣言 5.6 文 5.7 手続き抽象 5.8 プログラム 5.9 非決定性 5.10 並行性 6. 文献ノート 6.1 発展 6.2 解説 6.3 変形 第12章 意味領域 C.A.Gunter and D.S.Scott：山田 眞市 1. 序論 2. 関数の帰納的定義 2.1 cpoと不動点定理 2.2 不動点定理の応用 2.3 一様性 3. エフェクティブに表現した領域 3.1 正規部分posetと射影 3.2 エフェクティブに表現した領域 4. 作用素と関数 4.1 積 4.2 Churchのラムダ記法 4.3 破砕積 4.4 和と引上げ 4.5 同形と閉包性 5. べき領域 5.1 直観的説明 5.2 形式的定義 5.3 普遍性と閉包性 6. 双有限領域 6.1 Poltkin順序 6.2 閉包性 7. 領域の帰納的定義 7.1 閉包を使う領域方程式の解法 7.2 無型ラムダ記法のモデル 7.3 射影を使う領域方程式の解法 7.4 双有限領域上の作用素の表現 第13章 代数的仕様 M.Wirsing：稲垣 康善，坂部 俊樹 1. 序論 2. 抽象データ型 2.1 シグニチャと項 2.2 代数と計算構造 2.3 抽象データ型 2.4 抽象データ型の計算可能性 3. 代数的仕様 3.1 論理式と理論 3.2 代数的仕様とその意味論 3.3 他の意味論的理解 4. 単純仕様 4.1 束と存在定理 4.2 単純仕様の表現能力 5. 隠蔽関数と構成子をもつ仕様 5.1 構文と意味論 5.2 束と存在定理 5.3 隠蔽記号と構成子をもつ仕様の表現能力 5.4 階層的仕様 6. 構造化仕様 6.1 構造化仕様の意味論 6.2 隠蔽関数のない構造化仕様 6.3 構成演算 6.4 拡張 6.5 観測的抽象化 6.6 構造化仕様の代数 7. パラメータ化仕様 7.1 型付きラムダ計算によるアプローチ 7.2 プッシュアウトアプローチ 8. 実現 8.1 詳細化による実現 8.2 他の実現概念 8.3 パラメータ化された構成子実現と抽象化子実現 8.4 実行可能仕様 9. 仕様記述言語 9.1 CLEAR 9.2 OBJ2 9.3 ASL 9.4 Larch 9.5 その他の仕様記述言語 第14章 プログラムの論理 D.Kozen and J.Tiuryn：西村 泰一，近藤 通朗 1. 序論 1.1 状態，入出力関係，軌跡 1.2 外的論理，内的論理 1.3 歴史ノート 2. 命題動的論理 2.1 基本的定義 2.2 PDLに対する演繹体系 2.3 基本的性質 2.4 有限モデル特性 2.5 演繹的完全性 2.6 PDLの充足可能性問題の計算量 2.7 PDLの変形種 3. 1階の動的論理 3.1 構文論 3.2 意味論 3.3 計算量 3.4 演繹体系 3.5 表現力 3.6 操作的vs.公理的意味論 3.7 他のプログラミング言語 4. 他のアプローチ 4.1 超準動的論理 4.2 アルゴリズム的論理 4.3 有効的定義の論理 4.4 時制論理 第15章 プログラム証明のための手法と論理 P.Cousot：細野 千春，富田 康治 1. 序論 1.1 Hoareの萌芽的な論文の解説 1.2 C.A.R.HoareによるHoare論理のその後の研究 1.3 プログラムに関する推論を行うための手法に関するC.A.R.Hoareによるその後の研究 1.4 Hoare論理の概観 1.5 要約 1.6 この概観を読むためのヒント 2. 論理的，集合論的，順序論的記法 3. プログラミング言語の構文論と意味論 3.1 構文論 3.2 操作的意味論 3.3 関係的意味論 4. 命令の部分正当性 5. Floyd-Naurの部分正当性証明手法とその同値な変形 5.1 Floyd-Naurの手法による部分正当性の証明の例 5.2 段階的なFloyd-Naurの部分正当性証明手法 5.3 合成的なFloyd-Naurの部分正当性証明手法 5.4 Floyd-Naurの部分正当性の段階的な証明と合成的な証明の同値性 5.5 Floyd-Naurの部分正当性証明手法の変形 6. ライブネスの証明手法 6.1 実行トレース 6.2 全正当性 6.3 整礎関係，整列集合，順序数 6.4 Floydの整礎集合法による停止性の証明 6.5 ライブネス 6.6 Floydの全正当性の証明手法からライブネスへの一般化 6.7 Burstallの全正当性証明手法とその一般化 7. Hoare論理 7.1 意味論的な観点から見たHoare論理 7.2 構文論的な観点から見たHoare論理 7.3 Hoare論理の意味論 7.4 構文論と意味論の間の関係：Hoare論理の健全性と完全性の問題 8. Hoare論理の補足 8.1 データ構造 8.2 手続き 8.3 未定義 8.4 別名と副作用 8.5 ブロック構造の局所変数 8.6 goto文 8.7 （副作用のある）関数と式 8.8 コルーチン 8.9 並行プログラム 8.10 全正当性 8.11 プログラム検証の例 8.12 プログラムに対して1階論理を拡張した他の論理 第16章 様相論理と時間論理 E.A.Emerson：志村 立矢 1. 序論 2. 時間論理の分類 2.1 命題論理 対 1階述語論理 2.2 大域的と合成的 2.3 分岐的 対 線形 2.4 時点と時区間 2.5 離散 対 連続 2.6 過去時制 対 未来時制 3. 線形時間論理の技術的基礎 3.1 タイムライン 3.2 命題線形時間論理 3.3 1階の線形時間論理 4. 分岐的時間論理の技術的基礎 4.1 樹状構造 4.2 命題分岐的時間論理 4.3 1階の分岐的時間論理 5. 並行計算：その基礎 5.1 非決定性と公平性による並列性のモデル化 5.2 並列計算の抽象モデル 5.3 並列計算の具体的なモデル 5.4 並列計算の枠組みと時間論理の結び付き 6. 理論的見地からの時間論理 6.1 表現可能性 6.2 命題時間論理の決定手続き 6.3 演繹体系 6.4 モデル性の判定 6.5 無限の対象の上のオートマトン 7. 時間論理のプログラムの検証への応用 7.1 並行プログラムの正当性に関する性質 7.2 並行プログラムの検証：証明論的方法 7.3 時間論理による仕様からの並行プログラムの機械合成 7.4 有限状態並行システムの自動検証 8. 計算機科学における他の様相論理と時間論理 8.1 古典様相論理 8.2 命題動的論理 8.3 確率論理 8.4 不動点論理 8.5 知識 第17章 関係データベース理論の構成要素 P.C.Kanellakis：鈴木 晋 1. 序論 1.1 動機と歴史 1.2 内容についての案内 2. 関係データモデル 2.1 関係代数と関係従属性 2.2 なぜ関係代数か 2.3 なぜ関係従属性か 2.4 超グラフとデータベーススキーマの構文について 2.5 論理とデータベースの意味について 3. 従属性とデータベーススキーマ設計 3.1 従属性の分類 3.2 データベーススキーマ設計 4. 問合わせデータベース論理プログラム 4.1 問合わせの分類 4.2 データベース論理プログラム 4.3 問合わせ言語と複合オブジェクトデータモデル 5. 議論：関係データベース理論のその他の話題 5.1 不完全情報の問題 5.2 データベース更新の問題 6. 結論 第18章 分散計算：モデルと手法 L.Lamport and N.Lynch：山下 雅史 1. 分散計算とは何か 2. 分散システムのモデル 2.1 メッセージ伝達モデル 2.2 それ以外のモデル 2.3 基礎的概念 3. 分散アルゴリズムの理解 3.1 挙動の集合としてのシステム 3.2 安全性と活性 3.3 システムの記述 3.4 主張に基づく理解 3.5 アルゴリズムの導出 3.6 仕様記述 4. 典型的な分散アルゴリズム 4.1 共有変数アルゴリズム 4.2 分散合意 4.3 ネットワークアルゴリズム 4.4 データベースにおける並行性制御 第19章 並行プロセスの操作的および代数的意味論 R.Milner：稲垣 康善，結縁 祥治 1. 序論 2. 基本言語 2.1 構文および記法 2.2 操作的意味論 2.3 導出木と遷移グラフ 2.4 ソート 2.5 フローグラフ 2.6 拡張言語 2.7 その他の動作式の構成 3. プロセスの強合同関係 3.1 議論 3.2 強双模倣関係 3.3 等式による強合同関係の性質 3.4 強合同関係における置換え可能性 3.5 強等価関係上での不動点の唯一性 4. プロセスの観測合同関係 4.1 観測等価性 4.2 双模倣関係 4.3 観測合同関係 4.4 プロセス等価性上での不動点の唯一性 4.5 等式規則の完全性 4.6 プロセスの等価性に対するその他の概念 5. 双模倣等価関係の解析 5.1 等価性の階層構造 5.2 階層構造の論理的特性化 6. 合流性をもつプロセス 6.1 決定性 6.2 合流性 6.3 合流性を保存する構成子 7. 関連する重要な文献
