La mémoire de mathématiques

数学めも by Müde

述語論理入門3

二階述語論理の例として、数学的帰納法があるみたいです。

http://bukubukubun.blog90.fc2.com/blog-entry-290.html

数学的帰納法は、述語Pがあったとき、 P(1)が成り立ち、P(n) ならば P(n+1) が成り立つとき、すべての n について P(n) が成り立つ、というものです。

数学的帰納法を使おうとするとき、述語 P はどんなものを持ってきてもいいのです。

これを踏まえて式で示すと、

\forall P(P(1) \land \forall x(P(x) \to P(x+1)) \to \forall x(P(x)))

確かに「すべての述語P」ということで、述語に対して量を表す記号がついてますね…。これが二階述語論理。