命題論理に入門したい！

集合$X$に対して、$X$の要素を並べた有限列全体の集合を$X^{<\omega }={\displaystyle \bigcup _{n=1}^{\mathrm{\infty }}{X}^n}$で定める。
$X$の有限列$x\in X^{<\omega }$に対して、$x\in X^n$なる$n$が一意に存在する。この$n$を有限列$x$の長さ(length)という。

${\mathrm{\Omega }}_0$を可算集合とする。
また、$\mathbb{N}$から${\mathrm{\Omega }}_0$への全単射でもって、${\mathrm{\Omega }}_0$の元を$0$番目から順に一列に並べておく。
すなわち、${\mathrm{\Omega }}_0=\{p_0,p_1,p_2,\dots \}$とする。
これらの$p_n\in {\mathrm{\Omega }}_0$ $(n=0,1,2,\dots )$を命題変項(propositional variable)といい、これらは原子命題を表す非論理記号 (nonlogical symbol)である。

記号$\mathrm{\neg },\wedge ,\vee ,\to ,(,)$を論理記号(logical symbol)という。これら6つのうち丸括弧以外は論理演算子を表す記号である。

${\mathrm{\Omega }}_{lng}=\{\mathrm{\neg },\wedge ,\vee ,\to ,(,)\}\cup {\mathrm{\Omega }}_0$を、命題論理の言語(language)という。
また、${\mathrm{\Omega }}_{seq}$を${\mathrm{\Omega }}_{lng}$の有限列全体、つまり、${\mathrm{\Omega }}_{seq}＝{\mathrm{\Omega }}_{lng}^{<\omega }$と定め、
${\mathrm{\Omega }}_{seq}$の元を記号列(symbolic sequence)と呼ぶ。

記号列のうち、論理式(formula)であるものを、以下のように帰納的に定める。

1. 命題変項$p_n\in {\mathrm{\Omega }}_0(n=0,1,2,\dots )$は論理式である。
2. $A,B$が論理式ならば、$(\mathrm{\neg }A),(A\wedge B),(A\vee B),(A\to B)$という記号列は全て論理式である。
3. 以上により論理式であると定まる記号列以外は論理式ではない。

以上により定まる${\mathrm{\Omega }}_{seq}$に含まれる論理式全体の集合を$\mathrm{\Omega }$とする。

記号列全体の集合${\mathrm{\Omega }}_{seq}$の部分集合${\mathrm{\Omega }}^{\prime }\subset {\mathrm{\Omega }}_{seq}$が論理的であるとは、${\mathrm{\Omega }}^{\prime }$が以下を満たすことである。

1. ${\mathrm{\Omega }}^{\prime }$は全ての命題変項$p_n\in {\mathrm{\Omega }}_0(n=0,1,2,\dots )$を含む。つまり、${\mathrm{\Omega }}_0\subset {\mathrm{\Omega }}^{\prime }\subset {\mathrm{\Omega }}_{seq}$を満たす。
2. 記号列$A,B$が、もし${\mathrm{\Omega }}^{\prime }$の元ならば、$(\mathrm{\neg }A),(A\wedge B),(A\vee B),(A\to B)$という記号列は全て${\mathrm{\Omega }}^{\prime }$の元である。

${\mathrm{\Omega }}_{seq}$はそれ自身、${\mathrm{\Omega }}_{seq}$の論理的な部分集合である。よって論理的な部分集合は少なくとも1つ存在する。${\mathrm{\Omega }}_{seq}$の論理的な部分集合のうち、(包含関係で)最小のものを$\mathrm{\Omega }\subset {\mathrm{\Omega }}_{seq}$と定める。$\mathrm{\Omega }$は${\mathrm{\Omega }}_{seq}$の全ての論理的な部分集合の共通部分と一致するので存在することがわかる。
このとき、$\mathrm{\Omega }$に含まれる記号列を論理式(formula)という。

${\mathrm{\Omega }}_0=\{p_0,p_1,p_2,...\}$(再掲)
${\mathrm{\Omega }}_1=\{A,(\mathrm{\neg }A),(A\wedge B),(A\vee B),(A\to B)\mid A,B\in {\mathrm{\Omega }}_0\}$
$...$
${\mathrm{\Omega }}_{n+1}=\{A,(\mathrm{\neg }A),(A\wedge B),(A\vee B),(A\to B)\mid A,B\in {\mathrm{\Omega }}_n\}$
$...$
として、帰納的に${\mathrm{\Omega }}_n(n=0,1,2,\dots )$を定義する。また、
${\mathrm{\Omega }}_{\mathrm{\infty }}={\displaystyle \bigcup _{n\in \mathbb{N}}{\mathrm{\Omega }}_n={\mathrm{\Omega }}_0\cup {\mathrm{\Omega }}_1\cup \cdots \cup {\mathrm{\Omega }}_n\cup \dots }$
また定義から、これらは上昇列
${\mathrm{\Omega }}_0\subset {\mathrm{\Omega }}_1\subset \cdots \subset {\mathrm{\Omega }}_n\subset \cdots \subset {\mathrm{\Omega }}_{\mathrm{\infty }}$
をなす。また、${\mathrm{\Omega }}_{\mathrm{\infty }}$の元$x$に対して$x\in {\mathrm{\Omega }}_n$となる最小の$n$を$x$の深さといい、$n=d(x)$で表す。

順序数$\alpha$に対して、${\mathrm{\Omega }}_{\alpha }$を以下で定義する。

1. $\alpha =0$のとき、${\mathrm{\Omega }}_0=\{p_0,p_1,p_2,...\}$(再掲)
2. $\alpha$が後続順序数で$\alpha =\beta +1$のとき、
   ${\mathrm{\Omega }}_{\alpha }=\{A,(\mathrm{\neg }A),(A\wedge B),(A\vee B),(A\to B)\mid A,B\in {\mathrm{\Omega }}_{\beta }\}$
3. $\alpha$が極限順序数のとき、
   ${\mathrm{\Omega }}_{\alpha }={\displaystyle \bigcup _{\beta <\alpha }{\mathrm{\Omega }}_{\beta }}$

${\mathrm{\Omega }}_0=\{p_0,p_1,p_2,\dots \}$
${\mathrm{\Omega }}_{lng}=\{\mathrm{\neg },\wedge ,\vee ,\to ,(,)\}\cup {\mathrm{\Omega }}_0$
${\mathrm{\Omega }}_{seq}＝{\mathrm{\Omega }}_{lng}^{<\omega }$
$\mathrm{\Omega }=\bigcap \{{\mathrm{\Omega }}^{\prime }\mid {\mathrm{\Omega }}^{\prime }\subset {\mathrm{\Omega }}_{seq}$は論理的$\}$

写像$v:\mathrm{\Omega }\to \{0,1\}$が真理値関数あるいはモデル,解釈,意味であるとは、写像$v$が以下を満たすことである。

1. $v((\mathrm{\neg }A))=1⟺v(A)=0$
2. $v((A\wedge B))=1⟺v(A)=1$かつ$v(B)=1$
3. $v((A\vee B))=1⟺v(A)=1$または$v(B)=1$
4. $v((A\to B))=1⟺v(A)=0$または$v(B)=1$

論理式$A\in \mathrm{\Omega }$と真理値関数$v$に対して、
$v(A)=1$となるとき、$A$は$v$において真である(充足する,妥当である)といい、
$v(A)=0$となるとき、$A$は$v$において偽である(充足しない,非妥当である)という。
また、
$A$は$v$において真であるとき、$v\models A$
$A$は$v$において偽であるとき、$v⊭A$
と書く。

$T\subset \mathrm{\Omega }$に対して、$T$上で常に値が$1$のみを取る真理値関数を、$T$を充足する真理値関数あるいは$T$のモデルという。真理値関数$v$が$T$を充足するとき、$v\models T$と書く。

$T\subset \mathrm{\Omega }$に対して、$T$を充足する真理値関数が存在するとき、
$T$は充足可能であるという。

$T\subset \mathrm{\Omega }$と$A\in \mathrm{\Omega }$に対して、$T$を充足する任意の真理値関数$v$に対して、$v$が$A$を充足するとき、つまり、任意の真理値関数$v$に対して、
$v\models T⟹v\models A$
が成り立つとき、$A$を$T$上妥当であるといい、$T\models A$と書く。