2018-05-15 問題論理整数ならば述語

任意の非負整数$m$について……

問題

$P$は非負整数に関する述語とします。

任意の非負整数$m$について、

「$n < m$を満たすすべての非負整数$n$について$P(n)$が成り立つならば、$P(m)$が成り立つ」

と仮定します。

このとき「任意の非負整数$n$について$P(n)$が成り立つ」といえますか。

解答表示

いえます。

この問題のポイントは$P(0)$が成り立つかどうかです。結論から言えば$P(0)$は成り立ちます。

$P(0)$が成り立つといえるのはなぜか、順序立てて解説します。

読みやすくするため、

「$n < m$を満たすすべての非負整数$n$について$P(n)$が成り立つ」

を$Q(m)$とおきます。

この問題では、任意の非負整数$m$について「$Q(m)$ならば、$P(m)$が成り立つ」を仮定しています。この仮定から、$Q(0)$が成り立つならば、$P(0)$も成り立つといえますね。

では、$Q(0)$を調べましょう。

$Q(0)$は、

「$n < 0$を満たすすべての非負整数$n$について$P(n)$が成り立つ」

です。ですから、$Q(0)$は次のように言い換えられます。

「どんな非負整数$n$についても『$n < 0$ならば$P(n)$』である」

どんな非負整数$n$についても$n < 0$は偽なので『$n < 0$ならば$P(n)$』は真です。

よって、$Q(0)$は成り立ちます。

以上により、$P(0)$は成り立つことがわかりました。