集合論の公理系(その 3) - Red cat の数学よもやま話

何事も練習ですので、ここで述語論理の公理系を用いる練習を二つほどやっておきましょう。

練習 1. $\varphi\wedge\psi\to\psi\wedge\varphi$

公理 2 を以下の形に書き換えます。
$(\varphi\wedge\psi\to\varphi)\to[(\varphi\wedge\psi\to(\varphi\to\psi\wedge\varphi))\to(\varphi\wedge\psi\to\psi\wedge\varphi)]$
公理 3 とモーダス・ポーネンスから
$(\varphi\wedge\psi\to(\varphi\to\psi\wedge\varphi))\to(\varphi\wedge\psi\to\psi\wedge\varphi)$ … (1)
です。また、再び公理 2 を書き換えて
$(\varphi\wedge\psi\to\psi)\to\\\quad[(\varphi\wedge\psi\to(\psi\to(\varphi\to\psi\wedge\varphi)))\to(\varphi\wedge\psi\to(\varphi\to\psi\wedge\varphi))]$ … (2)
です。公理 4 を書き換えて
$\psi\to(\varphi\to\psi\wedge\varphi)$
また公理 1 を書き換えて
$(\psi\to(\varphi\to\psi\wedge\varphi))\to[\varphi\wedge\psi\to(\psi\to(\varphi\to\psi\wedge\varphi))]$
なので、この二つにモーダス・ポーネンスを使って
$\varphi\wedge\psi\to(\psi\to(\varphi\to\psi\wedge\varphi))$ … (3)
です。公理 3 と (2) にモーダス・ポーネンスを使って
$(\varphi\wedge\psi\to(\psi\to(\varphi\to\psi\wedge\varphi)))\to(\varphi\wedge\psi\to(\varphi\to\psi\wedge\varphi))$
これと (3) にモーダス・ポーネンスを使って
$\varphi\wedge\psi\to(\varphi\to\psi\wedge\varphi)$
となるので、これと (1) にモーダス・ポーネンスを使うと結論を得ます。

練習 2. $\varphi\vee\psi\to\psi\vee\varphi$

公理 5 を以下の形に書き換えます。
$\psi\to\psi\vee\varphi,\varphi\to\psi\vee\varphi$
また公理 6 を以下の形に書き換えます。
$(\varphi\to\psi\vee\varphi)\to[(\psi\to\psi\vee\varphi)\to(\varphi\vee\psi\to\psi\vee\varphi)]$
これと(書き換えた)公理 5 の後半の方とにモーダス・ポーネンスを使って
$(\psi\to\psi\vee\varphi)\to(\varphi\vee\psi\to\psi\vee\varphi)$
これと(書き換えた)公理 5 の前半とにモーダス・ポーネンスを使って結論を得ます。
皆さんも、良く知られた論理学の公式などを、公理系から上手く導く練習をしてみてください。次回から、いよいよ集合論の公理系の紹介に入ります。次回予定は 11/23 です。