$ \newcommand{\calN}{{\cal N}} \newcommand{\bfn}{{\mathbf n}} $

数理論理学特論 2011年度前期 --- レポート

2011年度前期の数理論理学特論の講義で成績を出してほしい人は, 次のレポート課題を解いて 8月5日までに, 渕野グループのグラスドアを入ってすぐの場所に置いてある (予定の)提出ボックス (あるいは封筒)に出してください.なおレポートは返却しませんので, 必要ならコピーをとっておいてください. ただし,正規の受講者以外の受講者,かつ/あるいは,成績とは独立にレポートを提出したい人の場合には, 朱を入れて返却してあげることも可能です.そのような場合には私に直接相談してください.
1. 講義での Theorem 33C, Theorem 33D と Theorem 33I をまとめた,次の定理の証明を書きだしてください:

すべての bounded formula $\tau=\tau(x_0,\ldots, x_{m-1},y_0,\ldots,y_{n-1})$ と numerals $\bfn_0,\ldots,\bfn_{n-1}$ に対し, $\calN\models\exists x_0\cdots\exists x_{m-1} \tau(x_0,\ldots, x_{m-1},\bfn_0^\calN,\ldots,\bfn_{n-1}^\calN)$ $\Leftrightarrow$ $A_E\vdash\exists x_0\cdots\exists x_{m-1} \tau(x_0,\ldots, x_{m-1},\bfn_0,\ldots,\bfn_{n-1})$ が成り立つ.

ただし,論理式 $\tau$ が bounded formula であるとは,$\tau$ が quantifier free な論理式を bounded quantifiers で縛ることで得られるものになっていることである.

2. 最後の講義で証明した Tarski の真理の定義不可能性定理とゲーデルの不完全性定理を自分の言葉で整理しなおしてできるだけ詳しく説明 (証明も含む)してください.

注意. 上の課題は,2つとも, 「講義のノートの該当する箇所を(内容を吟味しながら)整理しなおしてください」という意味の問題です.


Last modified: Mon Jul 25 03:23:35 +0900 2011