อ้างอิง:
ข้อความเดิมของคุณ rigor:
ขอความกรุณาท่านผู้รู้ช่วยเขียนพิสูจน์แบบฝึกหัดข้อนี้ให้ด้วยครับ
Let S be a subset of N such that
(a) 2k ฮ S for all k ฮ N, and
(b) if k ฮ S and k ณ 2, then k-1 ฮ S.
Prove that S = N.
|
ถ้าผมเข้าใจไม่ผิดข้อความที่ต้องการให้พิสูจน์ข้างบนนั้นคือ หลักการของการทำสิ่งที่เรียกว่า "backward induction" ซึ่งมีชื่อเสียงพอควรเพราะได้ถูกนำเอาไปใช้ในการพิสูจน์อสมการ A.M.-G.M. แต่ยังไงคงต้องให้ผู้เชี่ยวชาญด้านอสมการมายืนยันอีกทีครับ
เนื่องจากเราต้องการพิสูจน์สิ่งที่เป็นพื้นฐานระดับนี้ การพิสูจน์ให้ rigorous คงต้องใช้ความระมัดระวังเป็นพิเศษ ถ้าใช้ intuition อย่างเดียวอาจผิดได้ครับ ลองนึกถึงภาพว่าถ้าเราต้องการพิสูจน์ว่า Principle of Mathematical Induction เป็นจริงก็ไม่ใช่ง่ายๆ เพราะเราเห็นจะๆอยู่แล้วว่ามันเป็นจริง (ตามแบบการล้มของโดมิโน) เราถึงต้องไปลากเอาพวก Well-Ordering Principle มาช่วยพิสูจน์ครับ
การพิสูจน์ต่อไปนี้ผมคิดขึ้นเองจึงคงไม่ใช่อันที่ดีที่สุดหรืออันที่เป็นมาตรฐาน แต่ผมก็ค่อนข้างมั่นใจว่า rigorous ยังไงก็ตามขอให้ผู้รู้มาช่วยให้ความกระจ่างด้วยจะดีที่สุด (อย่าเอาแต่อ่านแล้วยิ้มเยาะ - ใครทำงั้นขอให้จู๊ดๆเลย
)
พิสูจน์
เริ่มจากการใช้ induction ธรรมดาพิสูจน์ว่า \(2^n>n\) สำหรับทุก \(n\in\mathbb N\) ซึ่งเดี๋ยวเราจะต้องใช้ความจริงอันนี้ครับ
ต่อไปเป็นการพิสูจน์ข้อความหลักโดยใช้ contradiction
ถ้า \(S\ne\mathbb N\) ดังนั้นจาก Well-Ordering Principle เราจะได้ว่า \(A:=\mathbb N\setminus S\) จะต้องมีสมาชิกที่น้อยที่สุด สมมติให้เป็น \(m\)
ให้สังเกตว่าข้อความ (b) ซึ่งก็คือ\[สำหรับ\;k\ge2,\quad k\in S\quad\Rightarrow
\quad k-1\in S\]สมมูลกับ\[สำหรับ\;k\ge2,\quad k-1\not\in S\quad
\Rightarrow\quad k\not\in S\]และสมมูลกับ\[สำหรับ\;n\ge1,\quad
n\not\in S\quad\Rightarrow\quad n+1\not\in S\]ซึ่งสมมูลกับ\[
สำหรับ\;n\ge1,\quad n\in A\quad\Rightarrow\quad n+1\in A\](ตรงนี้ทำละเอียดหน่อย เผื่ออาจมีใครงงครับ)
จากที่เรารู้ว่า \(m\in A\) และ \(n\in A\Rightarrow n+1\in A\) ดังนั้นโดย induction เราจึงได้ว่า\[m,m+1,m+2,\dots\in A\]นั่นคือ \(n\in A\) สำหรับทุก \(n\ge m\)
ดังนั้นจาก \(2^m>m\) เราจึงได้ว่า \(2^m\in A=\mathbb N\setminus S\) ด้วย ทำให้เกิดข้อขัดแย้งกับข้อความ (a) ที่ว่า \(2^m\in S\) เราจึงสรุปได้ว่าจริงๆแล้ว \(S=\mathbb N\) ครับ
