ทฤษฎีเซต: Paradox ใน Naive Set Theory

ระบบเซตที่เราใช้ ๆ กันเนี่ย เราเรียกกันว่า Naive Set Theory เพราะมันมีบางอย่างพิเรนทร์อยู่ คิดว่า บางคนคงจะเคยได้ยินชื่อ Russell's Paradox กันมาบ้างแล้ว ... สำหรับใครที่ไม่คุ้น ก็ลองดูนี่ละกัน

Russell's Paradox
ถ้าให้เซต M = { A | A ∉ A } แล้ว M ∈ M หรือ M ∉ M ?

ที่มาของความวุ่นวายนี้ อาจจะเกิดขึ้นเพราะ เซตไม่มีนิยาม ก็ได้

ครั้งนี้ไม่ได้จะเอามาให้ดูแค่ Russell's Paradox หรอกนะ แต่จะบอกว่า มี paradox อีกหลายอัน ที่เกิดจากวลีว่า "เซตของ XXX ทั้งหมด"

ทฤษฎีบทที่สำคัญของ Cantor อันนึง กล่าวไว้ว่า

Cantor's Theorem
สำหรับเซต A ใด ๆ | A | < | 2^A|

เผื่อลืม: 2^A คือ power set ของ A นะ

(นิยามคือ 2^A = { x | x ⊆ A })

วิธีพิสูจน์ ก็ดูได้ที่นี่นะ (มันต้องอาศัยนิยามของ การเปรียบเทียบ cardinal number ด้วย แต่ถือว่า เข้าใจด้วย sense ละกันนะ)

คราวนี้ มาดู paradox อีกอันนึงบ้าง

Set of All Sets (Cantor's Paradox)

ให้ A เป็น เซตของเซตทั้งหมด
จากนิยามของ A และ 2^A ⇒ 2^A ⊆ A ⇒ | A | ≥ | 2^A |
... ขัดแย้งกับ Cantor's Theorem

อีกอัน...

Set of All Cardinal Numbers

ให้ C เป็น เซตของ cardinal number ทั้งหมด
สำหรับแต่ละ i ∈ C ให้ A_i เป็นเซตใด ๆ ที่ | A_i | = i (เลือกมาอันนึง)

ให้ S = ∪_i∈C A_i เราจะรู้ทันทีว่า A_i ⊆ S สำหรับทุก i ∈ C

ที่ i = | 2^S |
จากนิยามของ A_i จะรู้ว่า | A_i | = i = | 2^S |

แต่เนื่องจาก A_i ⊆ S เราจะได้ว่า | A_i | ≤ | S |

ข้อสรุปก็คือ | 2^S | ≤ | S | ... ขัดแย้งกับ Cantor's Theorem

แล้วก็ อีกอันนึง

Set of All Sets Equivalent to a Set

ให้ A เป็นเซตใด ๆ
และ B เป็น เซตของเซตทั้งหมดที่มี cardinal number เท่ากับ | A |

สำหรับทุก i ใด ๆ เราจะรู้ว่า | A | = | A × { i } |
ซึ่งทำให้ A × { i } ∈ B (จากนิยามของ B)
หรือก็คือ { A × { i } }_i∈C ⊆ B สำหรับเซต C ใด ๆ
นอกจากนี้ เรายังรู้แน่ ๆ ว่า | { A × { i } }_i∈C | = | C | ด้วย

พอเราให้ C = 2^B สิ่งที่เกิดขึ้นก็คือ

1. { A × { i } }_i∈C ⊆ B ⇒ | { A × { i } }_i∈C | ≤ | B |
2. | { A × { i } }_i∈C | = | C | = | 2^B |

ก็เลยสรุปได้ว่า | 2^B | ≤ | B | ... ขัดแย้งกับ Cantor's Theorem

แล้ว paradox พวกนี้จะแก้ยังไงหละ? ... ไว้มาต่อกันคราวหน้านะ