数学 背理法

質問

3つの自然数a,b,cがa^2+b^2=c^2を満たしている。
このとき，a,bの少なくとも一方は偶数であること…(※)を証明せよ。

の問題について，背理法でa,bがどちらも奇数のとき矛盾することは，(※)が成立するための必要条件ではなくて，必要十分条件なのでしょうか。a,bのどちらかが偶数でも，a,bの両方が偶数でも成り立たない場合は(実際にはないが)考えなくてよいのでしょうか。

回答No.7

Caper · ベストアンサー

● ANo.6 のお礼欄を拝見しました。

　 お礼欄に提示なさいました ikzy さん からの再度のご質問に対して、私はまず忠実に回答を記述します。回答としてふさわしいと思われるものは 2つ あります。

　 < 1つ目 >

　「『 P かつ Q 』ならば R 」は
　「『 P かつ Q かつ ￢R 』ならば 偽 」の
　 必要十分条件である。

　 すなわち

　「『 [ a, b, c はいずれも自然数であり ] かつ [ a^2 + b^2 = c^2 である ] 』ならば『 a, b の少なくとも一方は偶数である 』」は
　「『 [ a, b, c はいずれも自然数であり ] かつ [ a^2 + b^2 = c^2 である ] かつ [a, b はいずれも奇数である] 』ならば 偽 」の
　 必要十分条件である。

　 < 2つ目 >

　 「 任意に選んだ a, b, c に対して (= どの a, b, c に対しても )
　 次の命題が真である。
　『 [ P かつ Q ] ならば R 』」

　 という命題は

　「『 次の命題を真とすることが可能な a, b, c が存在する。
　 [ P かつ Q かつ ￢R ] 』
　 ならば 偽 」

　 という命題の

　 必要十分条件である。

　 すなわち …

　 (※ これより後の記述は括弧だらけになり、正確に記述したとしても理解しづらいであろうと思われますので、省略します。お許しください。代わりに、論理記号を用いた表記のほうがもしかしたら理解しやすいかもしれませんので、それを付記します。∀ は「 任意に選んだ … に対して、右の ( )内 の命題が真である 」を、∃ は「 右の ( )内 の命題を真とするような … が存在する 」を、∧ は「 かつ 」を、→ は「 ならば 」をそれぞれ意味します )

　 ∀a ∀b ∀c((P∧Q)→R)

　 という命題は

　 (∃a ∃b ∃c(P∧Q∧￢R))→偽

　 という命題の

　 必要十分条件である。

　 (※ なお、P, Q, R はそれぞれ P(a, b, c), Q(a, b, c), R(a, b) と表記されるべきです。ここでは、わずらわしいので省略しています )

● 以下については、気が向いたらお読みになってください。

●「 U を証明せよ 」という問題が出された場合、その問題は「 U という命題が真であることを示せ 」を意味します

　 U という命題が真であることを示すためには、(￢U)→偽 という命題が真であることを示してもよいのです。これを示すという作業が、背理法による証明を行なうという作業なわけです。

　 ところで、ikzy さん が今回提示なさいました証明問題は、1つ の全称命題が真であることを示せというものであると、私は考えます。全称命題とは、例えば、「 任意に選んだ x に対して (= どの x に対しても )、次の 命題 V(x) が真である 」という表現がなされる命題です。∀x(V(x)) などと表記されます。

　 全称命題において、特に注意すべきは、∀x(V(x)→W(x)) という形の全称命題を取り扱う場合です。すなわち、どんな x を選んでも、V(x)→W(x) がはたして真となるかどうかを考察する場合です。
　 V(x) が偽であれば、W(x) の真偽にかかわらず、V(x)→W(x) は真です。ですから、通常の場合、考察の対象は、V(x) が真である場合に的をしぼればよいのです。
　 (※ ところが、どんな x を選んでも V(x) が偽である場合も考えられます。すなわち、∀x(￢V(x)) が真である場合です。∀x(￢V(x)) が真であることが判明した場合は、∀x(V(x)→W(x)) は真です。注意してください )　

　 全称命題のほかに、特称命題という命題もあります。この特称命題は、例えば、「 次の 命題 V(x) を真とするような x が存在する 」という表現がなされる命題です。∃x(V(x)) などと表記されます。

　 ￢(∀x(V(x))) と ∃x(￢V(x)) とは互いに必要十分条件です。
　 ￢(∃x(V(x))) と ∀x(￢V(x)) とは互いに必要十分条件です。

● ikzy さん が今回提示なさいました証明問題を、これまでの私の記述にあてはめてみましょう。その証明問題が 1つ の全称命題が真であることを示せというものであることについては、すでに触れました。その全称命題を論理記号で表記したものも、すでに紹介しました。

　 ∀a ∀b ∀c((P∧Q)→R)

　 いま、∀a ∀b ∀c を 1つ に束ねて、無理やり、∀x と表記することにします。そして、(P∧Q)→R を V(x) と表記することにします。

　 すると、提示なさいました証明問題は ∀x(V(x)) と表記されます。さらに、この ∀x(V(x)) を U と置くなどしてみてください。そして、ANo.7 における私のこれまでの記述を読み返してみください。なお、∃a ∃b ∃c を 1つ に無理やり束ねて ∃x と表記することもよしとしてください。

● ANo.2-7 における私の回答にまちがいがありましたら、重ねてごめんなさい。不明な点・あやしい点などが見受けられましたら、遠慮なくお知らせください。

お礼

諸事情によりお礼が大変遅れてしまいました。申し訳ありません。
回答ありがとうございました。

回答No.9

Caper

ANo.8 は、別のかたへの投稿です。ikzy さん へあてたものではありません。あやまって、こちらの Web ページ に投稿してしまいました。どうもすみません。

お礼

わかりました。

回答No.8

Caper

ごめんなさい。訂正です。つまらない訂正ですが、誤解を生むかもしれませんので … 。

　(1) の終わりのほうです。

(誤) 私は ∃x(P(x)) は偽であると、私は判断しました。
(正) 私は ∃xP(x) は偽であると、私は判断しました。

お礼

諸事情によりお礼が大変遅れてしまいました。申し訳ありません。
回答ありがとうございました。

回答No.6

Caper

ごめんなさい。ANo.5 の下から 2番目の ●項目 内に脱落がありました。

< 誤 >

　… すなわち ANo.4 が証明済みになっているということに変わりはないのです。

< 正 >

　… すなわち ANo.4 < 1 > が証明済みになっているということに変わりはないのです。

お礼

AnswerNo.5で御指摘をいただきましたので，表現を変えさせていただきます。
なお,P,Q,RはAnswerNo.4のP,Q,Rと同じものです。

【「PかつQならばR」が真であること】は【「PかつQかつ￢Rは偽」が真である】ことの必要十分条件

　　　　　　　　　　　　　　　　　　　　　　すなわち

【a, b, c は自然数でa^2+b^2=c^2であるならばa, b の少なくとも一方は偶数である　が真】
　　　　　　　　　　　　　　　　　　　　　であることは
【a, b, c はいずれも自然数でa^2+b^2=c^2でありa, b はいずれも奇数である　が偽】
　　　　　　　　　　　　　　　　　　　　　であることの
　　　　　　　　　　　　　　必要十分条件ということでよろしいでしょうか。

回答No.5

Caper

● ikzy さん のご質問に対して、的を射た回答を私はしていませんでしたね。反省しています。

● ikzy さん のご質問は、2つ に分かれていますよね。

　 ご質問の前半については、何をお尋ねになりたいのか、私はいまだにつかむことができないでいます。ですから、その前半について、私からいくつか質問させてください。

　 ご質問の後半については、お尋ねになりたいことをようやく私はつかむことができたような気がします。

● ご質問の後半について、先に回答させてください。

　 < ご質問の後半 >

　 a, b のどちらかが偶数でも，a, b の両方が偶数でも成り立たない場合は ( 実際にはないが ) 考えなくてよいのでしょうか。

　 < Caper からの回答 >

　 考えなくてよいと、私は思います。

　 ANo.4 における < 2 > の証明 ( 背理法 ) がなされたとします。それによって、ANo.4 における < 1 > も証明済みとなります。すなわち、ikzy さん のご質問にある問題は証明済みとなります。

　 その後、その問題について、再調査したとします。< 2 > と同様の手法を用いて、a, b の少なくとも一方が偶数である場合にについて調べたとします。すなわち、次の命題 < 5 > に取り組んだとします。

　 < 5 >
　「 次の命題を満たすことが可能な a, b, c が存在する。
　『 [【P】a, b, c はいずれも自然数であり ] かつ [【Q】a^2 + b^2 = c^2 であり ] かつ [【R】a, b の少なくとも一方は偶数である ] 』」ならば「 矛盾に至る 」。

　 [ 注意 ]
　 ANo.4 < 2 > において【￢R】となっていたところが、この < 5 > では【R】になっています。

　 その結果、仮にこの < 5 > も証明の道筋がしっかりついてしまったとします。すなわち、仮に矛盾に至ってしまったとします。

　 ところが、ANo.4 < 2 > が証明された後なら、仮に < 5 > が証明されようとも、ANo.4 < 1 > が証明済みであることに変わりはないのです。

　 ただし、ANo.4 < 2 > が証明された後に、仮に < 5 > が証明されてしまった場合は、「 P かつ Q 」という命題がいかなる a, b, c に対しても偽ということになります。そのことを念頭に置きながら、ANo.4 < 1 > をごらんください。

　「 偽 ならば R 」という命題は、いかなる a, b, c に対しても真です。ですから、ANo.4 < 1 > が真である、すなわち ANo.4 が証明済みになっているということに変わりはないのです。

● ご質問の前半について。

　 < ご質問の前半 >

　 … の問題について，背理法で a, b がどちらも奇数のとき矛盾することは，(※) が成立するための必要条件ではなくて，必要十分条件なのでしょうか。

　 < Caper からの質問・その他 >

　 (※) はどの範囲を指しているのでしょうか。
　 ANo.4 < 1 > 全体でしょうか。それとも、R だけでしょうか … 。
　 別の表現でご質問しなおしていただければ、助かります。

　 ANo.4 < 2 > は ANo.4 < 1 > が成立するための必要条件ではなくて、互いに必要十分条件なのでしょうかということをお尋ねになりたいのであれば、そのとおりであると私は思います。

お礼

何回もありがとうございます。
No.4-6についてNo.6にコメントさせていただきます。

回答No.4

Caper

● うっかりしていました。ごめんなさい。ANo.2 にまちがいがありました。訂正させてください。

● ikzy さん が提示なさいました証明問題の表現のしかたを少し変更させてください。

　 < 1 >
　 任意に選んだ a, b, c に対して (= どの a, b, c に対しても )、次の命題が満たされる。
　「『 [【P】a, b, c はいずれも自然数であり ] かつ [【Q】a^2 + b^2 = c^2 である ] 』ならば『【R】a, b の少なくとも一方は偶数である 』」。

　 そこで、この < 1 > という表現を、さらに変更させてください。こんどは背理法を用いた表現です。

　 < 2 >
　「 次の命題を満たすことが可能な a, b, c が存在する。
　『 [【P】a, b, c はいずれも自然数であり ] かつ [【Q】a^2 + b^2 = c^2 であり ] かつ [【￢R】a, b はいずれも奇数である ] 』」ならば「 矛盾に至る 」。

　 [ 注意 ]
　 ￢ という記号は、否定を意味します。
　 3種類 の括弧 「 」『 』 [ ] のくくりかたには、特に注意をはらってください。
　 ANo.2 における P, Q の割り当てと、ここでのそれらの割り当ては異なります。また、それにともない、R を新たに設けました。

● < 1 > という表現から、通常の証明を行なおうとするときは、次のとおりではないでしょうか。
　 a, b, c を任意に選んだものであることを念頭に置いた上で、「 P かつ Q 」から推論を開始させます。「 P かつ Q 」から始まって、R という結論を得るまでの過程を記述しようとします。

　 一方、< 2 > という表現から、背理法による証明を行なおうとするときは、次のとおりではないでしょうか。
　 a, b, c が特定の存在であることを念頭に置いた上で、「 P かつ Q かつ ￢R 」から推論を開始させます。それらの存在を肯定することから始まって、その存在自体が「 矛盾に至る 」という結論を得るまでの過程を記述しようとします。

● ところで、この証明問題が本当に証明されるのか否かに関係なく、この < 1 > と < 2 > は互いに必要十分条件になっているのです。すなわち、この証明問題に着手する前の時点において、< 1 > と < 2 > の真偽が一致することだけは確かなのです。( 「 偽 ならば 偽 」という命題が真であることに注意してください )

　 その理由は、次のとおりです。
　 まず、次の < 3 > < 4 > という ( "基本的な" とでも言えばよいのでしょうか ) 命題をごらんください。

　 < 3 >
　 任意に選んだ x に対して (= どの x に対しても )、次の命題が満たされる。
　「『 x は ○○○ である 』ならば『 x は △△△ である 』」

　 < 4 >
　「 次の命題を満たすことが可能な x が存在する。
　『 [ x は ○○○ であり ] かつ [ x は △△△ でない ] 』」ならば「 矛盾に至る 」。

　 上記の < 3 > という形の命題と < 4 > という形の命題は、互いに必要十分条件になっているのです。

　 おおざっぱに言えば、< 1 > は < 3 > という形の命題です。< 2 > は < 4 > という形の命題です。ですから、仮に < 2 > が証明された場合 (=「 矛盾に至る 」にたどりつくまでの記述が理にかなっている場合 )、自動的に < 1 > は証明済みとなります。もちろん、仮に < 1 > が証明された場合、自動的に < 2 > は証明済みとなります。

● ANo.1 において、indigobluet さん が次のとおりに記述をなさいました。

　「 命題自体を仮定的に否定してそれが矛盾することを示すのが背理法です 」

　 < 1 > の否定は、< 2 > における前半の「 」内の命題です。すなわち、次の命題です。

　「 次の命題を満たすことが可能な a, b, c が存在する。
　『 [【P】a, b, c はいずれも自然数であり ] かつ [【Q】a^2 + b^2 = c^2 であり ] かつ [【￢R】a, b はいずれも奇数である ] 』」

　 同様に、< 3 > の否定は、< 4 > における前半の「 」内の命題です。すなわち、次の命題です。

　「 次の命題を満たすことが可能な x が存在する。
　『 [ x は ○○○ であり ] かつ [ x は △△△ でない ] 』」

● この ANo.4 における私の記述にも、まちがいが含まれているかもしれません。その場合、私はひたすらあやまるのみです。

　 ikzy さん へ。
　 私のこれまでの記述に関して、わからない個所・まちがいではないかと思われる個所などがございましたら、補足欄において、遠慮なくご指摘ください。

　 閲覧者のみなさん へ。
　 私のこれまでの記述に含まれる誤記を、ご指摘いただければ幸いです。まことに恐れ入りますが、よろしくお願いいたします。

お礼

何度もありがとうございます。
No.6にコメントさせていただきます。

回答No.3

Caper

● ANo.2 の < 2 > にまちがいがあることを、まずお伝えいたします。うっかりしていました。どうもすみません。

　 ANo. 2 の < 2 > は全称命題として記述されていますが、これは 特称命題 (= 存在命題 )として記述されなければいけないものです。

　 それに連動して、他の記述も改める必要があると思われます。

● 後日、改めて投稿しなおすつもりで私はいます。恐れ入りますが、私に少し時間をください。まことに申しわけありません。取り急ぎ、ご連絡まで。

お礼

わざわざ時間を割いて，ご丁寧な解答をありがとうございます。

回答No.2

Caper

● ikzy さん が提示なさいました証明問題の表現のしかたを少し変更させてください。

　 < 1 >
　 a, b, c は任意に選んだ自然数であるとする。
　 このとき、「【P】a^2 + b^2 = c^2 である 」ならば「【Q】a, b の少なくとも一方は偶数である 」。

　 そこで、この < 1 > という表現を、さらに変更させてください。こんどは背理法を用いた表現です。

　 < 2 >
　 a, b, c は任意に選んだ自然数であるとする。
　 このとき、「『【P】a^2 + b^2 = c^2 であり 』かつ『【￢Q】a, b の両方が奇数である 』」ならば「 矛盾に至る 」。

　 ￢ という記号は、否定を意味します。

● < 1 > という表現から、通常の証明を行なおうとするときは、【P】から推論を開始させますよね。そして、【Q】という結論が得られるまでの過程を記述しようとします。

　 一方、< 2 > という表現から、背理法による証明を行なおうとするときは、【P】かつ【￢Q】から推論を開始させます。そして、「 矛盾に至る 」という結論が得られるまでの過程を記述しようとします。

● ところで、この証明問題が本当に証明されるのか否かに関係なく、この < 1 > と < 2 > は互いに必要十分条件になっているのです。すなわち、この証明問題に着手する前の時点において、< 1 > と < 2 > の真偽が一致することだけは確かなのです。( 「 偽 ならば 偽 」という命題が真であることに注意してください )

　 その理由は、「 U ならば V 」という形の命題と、「『 U かつ ￢V 』ならば『 矛盾に至る 』」という形の命題は、互いに必要十分条件になっているからです。言い換えれば、「 U ならば V 」という形の命題と、「『 U かつ ￢V 』の否定 」という形の命題は、互いに必要十分条件になっているからです。

　 ですから、仮に < 2 > が真であることが示された場合、自動的に < 1 > も真となります。もちろん、仮に < 1 > が真であることが示された場合、自動的に < 2 > も真となります。仮に < 2 > が偽であることが示された場合、自動的に < 1 > も偽となります。もちろん、仮に < 1 > が偽であることが示された場合、自動的に < 2 > も偽となります。

● 以上の私の記述にまちがいがある場合は、ひらにごめんなさい。

お礼

ありがとうございます。

回答No.1

indigobluet

問題は「a^2+b^2=c^2⇒a,bの少なくとも一方は偶数である」が真であることを証明すればよいので、その対偶を取って
「a,bのどちらも奇数である⇒a^2+b^2≠c^2」を証明すれば問題の証明になります。
ちなみにこの「対偶を証明することによって元の命題を証明する」という考え方は背理法ではありません。
「素数が無限であること」の証明を「素数が有限であると仮定する」ことから始めるように、命題自体を仮定的に否定してそれが矛盾することを示すのが背理法です。

お礼

ありがとうございます。