Skinerrian's blog

論理学・哲学・科学史・社会学などに興味があるので、その方面のことを書きます。更新は不定期。

パラドクスの効用

ラッセルのパラドクスは、パラドクスというよりも「ラッセル集合なんて存在しない」という趣旨の定理だという風に言われることがある。これは単に言葉の問題だと思うのだが、どちらの見方にも意義があると思う。

数学の基礎に関心のある哲学者なら、素朴集合論から矛盾が出てきてしまうのでどうしようか、という問題がラッセルのパラドクスだと考えると思う。対処策は包括原理を弱めるとか非古典論理に進むとかタイプ理論とか色々ある。

他方で、そんな多様な選択肢など相手にせず、ZF集合論一択でよかろうと決めてかかるなら、ラッセルのパラドクスは {x |¬x∈x} なんて集合は存在しない、という論理学上の定理とみなせる。これは有用な定理でもある。例えば、普遍クラスV = {x | x=x} なんて存在しないことを示すにあたって、ラッセルのパラドクスを利用する。Vが集合だと仮定すると、分出公理によって {x |¬x∈x} も集合だが、それはありえないので、Vは集合じゃない(QED)。これは単純な例だが、いろいろな固有クラスの非存在をラッセル集合の非存在に帰着させることで示すことができると思われる。

ある意味これと似たようなことは、停止問題を解くプログラムは存在しないという定理についても言える。ある問題を実効的に解くプログラムが存在しないことを証明する一つの方法は、もしそれが解けると仮定すると停止問題も解けてしまうことを示す、というものになるから。

ネガティブな結果のなかにポジティブな側面を見るといえば、ゲーデルの定理にもそういう側面がある。第二不完全性定理は、算術の無矛盾性を自分では証明できない、といえば悲観的に聞こえるが、逆にいえば、ある理論の無矛盾性を別の理論で証明できるなら、その別の理論はよい強いことになる。第二不完全性定理は理論間の強弱を測る道具となる。

例えば、ZF集合論でペアノ算術PAの無矛盾性を証明できるから、ZFはPAより強い。クワインの新基礎集合論NFの変種でNFUというのがあるが、これの無矛盾性はPAで証明できるので、NFUはPAより弱い(なお、NFの無矛盾性は未解決問題)。