「スマリヤン数理論理学」P83練習問題への回答
ただし命題変数が可算個あるとする。
K={∨,∧,¬,⊃,≣,∀i i∈N ai}とする。
aiは実質的に正の整数と同じ位数を持つので、aiと5つの論理記号の和集合Kも正の整数と同じ位数を持つ。
論理式xの長さは有限なので、xはKの有限部分集合と言える。
すべての「可算無限集合の要素からなる有限部分集合」からなる集合の位数は可算無限である。
QED
*論理式は、x⊃yとy⊃xのように、おなじ要素であっても異なる論理式が存在するのでそれらを分類する必要はある。それは可能だ。