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

ทฤษฎีบทของคันทอร์ (อังกฤษ: 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. ดังนั้น จะมี y ∈ A ซึ่ง f(y) = B พิจารณาว่า y ∈ B หรือไม่. ถ้า y ∈ B แล้ว y ∈ f(y) , ซึ่งจะทำให้ขัดกับนิยามของ B ที่ว่า y ∉ B. ในทางกลับกัน, ถ้า y ∉ B แล้ว y ∉ f(y) จะได้ y ∈ B. เกิดข้อขัดแย้ง

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