述語論理

命題の内部構造と、量化子を扱える論理体系。一階述語論理。

$$\forall x(\mathrm{Human}(x)\to \mathrm{Mortal}(x))$$

量化子#

記号	読み	意味
$\forall$	すべての	全称量化
$\exists$	ある	存在量化

順序が意味を変える#

$$\forall x\exists yP(x,y)\ne \exists y\forall xP(x,y)$$

• 前者「どの $x$ にも、それに応じた $y$ がある」
• 後者「すべての $x$ に共通する $y$ がある」

後者の方が強い主張。 極限の $\epsilon$-$\delta$ 定義で 順序が本質的なのはこのため （$\delta$ は $\epsilon$ に依存してよい）。 一様連続との違いもこの順序の違い。

完全性と決定不能性#

• 完全性定理（Gödel, 1929）— 真な論理式はすべて証明できる
• 決定不能性（Church, Turing, 1936）— 与えられた式が真かを判定する アルゴリズムは存在しない

証明が存在することと、それを機械的に見つけられることは別、という関係。

参考文献#

• Herbert B. Enderton. A Mathematical Introduction to Logic, 2nd ed. Academic Press, 2001. https://doi.org/10.1016/b978-0-08-049646-7.50005-9
• Elliott Mendelson. Introduction to Mathematical Logic, 6th ed. CRC Press, 2015. https://doi.org/10.1201/b18519
• Stanford Encyclopedia of Philosophy. Classical Logic. https://plato.stanford.edu/entries/logic-classical/