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

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

การพิสูจน์ 

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

เพื่อแสดงให้เห็นว่า 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)

ทฤษฎีเซต
ทฤษฎีบททางคณิตศาสตร์