ทฤษฎีบทของคันทอร์

จากวิกิพีเดีย สารานุกรมเสรี

ทฤษฎีบทของคันทอร์ (อังกฤษ: Cantor's theorem) กล่าวว่า เซตกำลัง (power set) (เซตของเซตย่อยทั้งหมด) ของเซตใดๆ จะมี จำนวนเชิงการนับ (cardinal number) มากกว่าจำนวนเชิงการนับของเซตนั้น. ทฤษฎีบทของคันทอร์นั้นเป็นที่ประจักษ์สำหรับเซตจำกัดอยู่แล้ว และยังเป็นจริงสำหรับเซตอนันต์ด้วย ซึ่งเซตกำลังของเซตอนันต์นับได้นั้น จะเป็นเซตอนันต์นับไม่ได้

การพิสูจน์[แก้]

ให้ f เป็นฟังก์ชันหนึ่งต่อหนึ่งจาก A ไปยังเซตกำลังของ A. จะต้องแสดงให้เห็นว่า f ไม่เป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง ในการทำเช่นนี้ จะต้องบอกว่ามีเซตย่อยของ A บางเซตที่ไม่อยู่ในภาพ (image) ของ f. ซึ่งเซตย่อยนั้นก็คือ

B=\left\{\,x\in A : x\not\in f(x) \,\right\}

เพื่อแสดงให้เห็นว่า B ไม่อยู่ในภาพของ f, เราจะสมมติให้ B อยู่ในภาพของ f. ดังนั้น จะมี yA ซึ่ง f(y) = B พิจารณาว่า yB หรือไม่. ถ้า yB แล้ว yf(y) , ซึ่งจะทำให้ขัดกับนิยามของ B ที่ว่า yB. ในทางกลับกัน, ถ้า yB แล้ว yf(y) จะได้ yB. เกิดข้อขัดแย้ง

จากการที่ x ปรากฏในนิพจน์ "xf(x) " ถึงสองครั้ง เราจึงเรียกวิธีการนี้ว่าเป็นวิธีแนวทแยง (diagonal argument)