$ \newcommand{\exi}{\exists\,} \newcommand{\all}{\forall} \newcommand{\equ}{\!=\!} \newcommand{\nequ}{\!\neq\!} \newcommand{\amp}{\;\&\;} \renewcommand{\Set}[2]{\left\{\;#1\mathrel{}\middle|\mathrel{}#2\;\right\}} \newcommand{\parenth}[1]{\left(\;#1\;\right)} \newcommand{\braces}[1]{\left\{\;#1\;\right\}} \newcommand{\bracket}[1]{\left[\;#1\;\right]} \newcommand{\godel}[1]{\left\ulcorner #1 \right\urcorner} $

数理論理学

帰納的関数論 3:自然数論の形式的体系${\cal P}$

自然数論の形式的体系${\cal P}$を定義する。 記号 対象記号:${\mathbf 0}$ 関数記号:$^\prime$ 論理記号:$\neg$、$\lor$、$\all$ 補助記号:$($、$)$ 変数記号:おのおのの型ごとに、それぞれ可算個無限個ずつの変数を用意する。 $1$階のタイプの変数記…

${\rm S}_n^m$-定理を自分なりに纏める。

$\newcommand{\godel}[1]{\left\ulcorner#1\right\urcorner}$ $S_n^m$-定理を自分なりに纏める。 $\lambda y_1 \cdots y_m x_1 \cdots x_n \; f(y_1,\cdots,y_m,x_1,\cdots,x_n)$を$(m+n)$-変数の帰納的な部分関数とする。 この関数$f$のゲーデル数を$e$とす…

形式的体系${\cal R}$を算術化する。

形式的体系${\cal R}$を算術化する。 $\newcommand{\godel}[1]{\left\ulcorner#1\right\urcorner}$ ${\cal R}$の基本記号のゲーデル数 定記号のゲーデル数: $\godel{{\mathbf 0}} \equ 3、\godel{^\prime} \equ 5、\godel{\equ} \equ 7$ 変数および関数記号…

形式的体系${\cal R}$を定義する

今週のお題「最近おいしかったもの」} 形式的体系${\cal R}$を定義する。 (参考文献:廣瀬健、「帰納的関数」、75ページ~81ページ) ${\cal R}$の基本記号 定記号: 対象記号として、${\mathbf 0}$ (特定の)関数記号として、$^\prime$ 述語記号として、$\equ$ …

安井邦夫、「現代論理学」、現代思想社 の分からない所メモ 第2弾

p188の$\fbox{15}$が分からない! $\fbox{15}$ S(x,t,u):「(x)$_0$は、表現(x)$_1$において、変項uの自由な表れすべてに項tを代入するとき、そこに得られる表現である。」 S(x,t,u)は次の関係で定義される。 \begin{array}{ll} {VE(u) \amp TM(t) \amp} \{ \\ …

数学的帰納法の定理、最小値の定理、累積帰納法の定理 の同値性

数学的帰納法の定理 A(n)を自然数nを変数とする論理式とする。この時次が成り立つ: \begin{array}{l} A(0) \Rightarrow \left[ \forall n \left( A(n) \Rightarrow A(n+1) \right) \Rightarrow \forall n A(n) \right] \end{array} これから直接次の定理が…

論理式の一意性記号について

論理式の一意性記号について以下のように定義する: \begin{align} \exists!xA(x) \equiv \exists x \left[ A(x) \land \forall y \left( A(y) \Rightarrow x = y \right) \right] \end{align} この時、$(x,y)$が組として一意に存在する意味で$\exists!x \ex…

安井邦夫、「現代論理学」、現代思想社 の分からない所メモなどなど

div.cite { border: solid white 1pt !important; border-radius: 5px !important; margin-bottom: 3pt !important; padding: 5px !important; --> 41ページ このBは無論、LPの公理にAを公理シェーマとして加えた公理系(これをTとする)において証明可能で…