$ \newcommand{\LEQ}{\leqq} $

 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)$は成り立つことがわかりました。

関連ツイート

この問題は想像以上に正答率が低かった問題です。結城がTwitterで出題したところ、回答者が1131人で、正答率は30%に留まりました。


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