✖

เซตนับได้

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

ขนาดของเซตอนันต์

การหาขนาดของเซตจำกัดทำได้ง่าย เพียงนับจำนวนสมาชิก ดังนั้นเซต M = {a, b, c, d, e} มีขนาด 5 เขียนได้ว่า |M| = 5

สำหรับเซตอนันต์ สถานการณ์ซับซ้อนกว่ามาก จะเปรียบเทียบขนาดของเซตอนันต์ได้อย่างไร ทำได้หรือไม่ หรือเซตอนันต์ทุกเซต “มีขนาดเท่ากัน”

ตัวอย่างเช่น พิจารณาเซตของจำนวนนับและเซตของจำนวนนับที่เป็นจำนวนคู่ คือเซต ℕ = {1, 2, 3, 4, 5, 6, …} และ S = {2, 4, 6, …} เราอยากจะบอกว่าเซตของจำนวนนับใหญ่กว่าเซตของจำนวนคู่ เพราะจำนวนนับมีจำนวนคู่ทุกจำนวนอยู่ด้วย และยังมีสมาชิกอื่นเพิ่มเติม คือจำนวนคี่

จึงอาจเขียนได้ว่า S ⊂ ℕ นั่นคือเซต S เป็นสับเซตแท้ของเซต ℕ และอาจกล่าวว่าถ้า S ⊂ ℕ แล้วเซต ℕ ใหญ่กว่า เพราะมีสมาชิกมากกว่าเซต S

เหตุผลข้อหนึ่งที่วัดขนาดของเซตด้วยความสัมพันธ์การเป็นสับเซตไม่ได้ คือเซตอาจมีขนาดต่างกันแม้ไม่มีเซตใดเป็นสับเซตของอีกเซตหนึ่ง ซึ่งแสดงได้แม้กับเซตจำกัด: A = {1, 3, 4, 9} และ B = {b, u, r, z, m} จะได้ |A| = 4 และ |B| = 5 เซต B ใหญ่กว่าเซต A แต่ A ⊂ B ไม่เป็นจริง สำหรับเซตอนันต์ เห็นได้จากจำนวนคู่และจำนวนคี่ ไม่มีเซตใดเป็นสับเซตของอีกเซตหนึ่ง

ความสัมพันธ์การเป็นสับเซตจึงไม่เหมาะที่จะใช้ตัดสินว่าเซตหนึ่งใหญ่กว่าอีกเซตหนึ่งหรือไม่

ฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึง

ลองใช้อีกวิธีหนึ่ง ให้เซตสองเซต A และ B กล่าวได้ว่าเซตทั้งสองมีขนาดเท่ากัน ถ้ามีฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึง (bijection) ระหว่างเซตทั้งสอง หมายความว่าอย่างไร หมายความว่าเราหยิบสมาชิกหนึ่งตัวจากเซต A และหนึ่งตัวจากเซต B มาจับคู่กันเป็น (a, b) แล้วนำสมาชิกทั้งสองออกจากเซต และทำต่อไปเรื่อย ๆ ถ้าทำให้ทั้งสองเซต “ว่าง” ได้ ก็แสดงว่าพบฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงแล้ว

ตัวอย่างกับเซตจำกัด: A = {a, b, c} และ B = {1, 2, 3} คู่แรกอาจเป็น (a, 1) คู่ถัดไป (b, 2) และสุดท้าย (c, 3) เราใช้สมาชิกของทั้งสองเซตหมดแล้ว จึงพบฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึง ที่สำคัญคือฟังก์ชันนี้ไม่ใช่ฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงเพียงฟังก์ชันเดียว คำตอบต่อไปนี้ก็ใช้ได้เช่นกัน (a, 3), (b, 1), (c, 2)

สำหรับเซตอนันต์จะน่าสนใจขึ้น ลองพิจารณาจำนวนนับที่เป็นจำนวนคี่และจำนวนคู่ โดยสัญชาตญาณเรารู้สึกว่าน่าจะมีจำนวนเท่ากัน ลองดู นำจำนวนคี่ตัวแรกส่งไปยังจำนวนคู่ตัวแรก ได้ (1, 2) ต่อไปจำนวนคี่ตัวที่สองกับจำนวนคู่ตัวที่สอง ได้ (3, 4) ทำเช่นนี้ต่อไป จะได้คู่ (1, 2), (3, 4), (5, 6), (7, 8), … เขียนได้ว่าจำนวนคี่ l แต่ละจำนวนส่งไปยังจำนวนคู่ l + 1 และจำนวนคู่ s แต่ละจำนวนเป็นภาพของจำนวนคี่ s − 1 ดังนั้นจำนวนคี่ทุกจำนวนและจำนวนคู่ทุกจำนวนอยู่ในคู่ใดคู่หนึ่ง เซตของจำนวนคี่และเซตของจำนวนคู่จึงมีขนาดเท่ากัน

จำนวนคู่เทียบกับจำนวนนับ

ต่อไปใช้วิธีเดียวกันเปรียบเทียบเซตของจำนวนนับกับเซตของจำนวนคู่ คือเซต ℕ = {1, 2, 3, 4, 5, 6, …} และ S = {2, 4, 6, …} โดยสัญชาตญาณเราคาดว่าเซตของจำนวนนับจะใหญ่กว่า

แต่ลองหาฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงดู กล่าวได้ว่าจำนวนนับ n แต่ละจำนวนส่งไปยังสองเท่าของตัวเอง คือ 2n จะได้คู่ (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … สำหรับจำนวนนับ n ทุกจำนวนจะมีคู่ (n, 2n) และสำหรับจำนวนคู่ s ทุกจำนวนจะมีคู่ (s/2, s) เราพบฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงแล้ว เซตของจำนวนคู่และเซตของจำนวนนับจึงมีขนาดเท่ากัน คือมีภาวะเชิงการนับเท่ากัน

เรื่องนี้อาจดูน่าสับสน เพราะจำนวนนับน่าจะมีสมาชิกมากกว่าจำนวนคู่ จำนวนนับมีจำนวนคู่ทุกจำนวนและยังมีจำนวนคี่ทุกจำนวนด้วย แต่เราหาฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงได้ เซตทั้งสองจึงมีขนาดเท่ากัน

การเปรียบเทียบกับจำนวนนับ

ที่จริงแล้วจำนวนนับกำหนดขนาดที่เล็กที่สุดของเซตอนันต์ การตรวจว่าเซตอื่นมีขนาดเท่ากับเซตของจำนวนนับหรือไม่มักทำได้ค่อนข้างง่าย เพียงหาฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงไปยังจำนวนนับ ในทางปฏิบัติหมายความว่าเพียงแค่ต้องกำหนดหมายเลขหรือเรียงลำดับสมาชิกของเซต M ได้

กล่าวคือ ถ้าเรียงสมาชิกของเซตได้จนบอกได้ว่าสมาชิกตัวใดเป็นตัวที่หนึ่ง ตัวที่สอง ตัวที่สาม ตัวที่สี่ ตัวที่สิบ เป็นต้น เซตนั้นจะมีขนาดเท่ากับ ℕ เซตเช่นนี้เรียกว่าเซตนับได้

เห็นได้ง่ายว่าจำนวนนับที่เป็นจำนวนคู่และที่เป็นจำนวนคี่เป็นเซตนับได้ เพราะบอกได้ว่าจำนวนคู่หรือจำนวนคี่ตัวที่หนึ่ง ตัวที่สอง ตัวที่สาม เป็นต้น คืออะไร แล้วจำนวนเต็มที่เป็นจำนวนคู่เป็นอย่างไร นั่นคือเซต S = {…, −4, −2, 0, 2, 4, …} เรียงลำดับได้หรือไม่ คำตอบคือได้ เพียงใช้การเรียงแบบเดิม แล้วเขียนจำนวนตรงข้ามต่อท้ายจำนวนคู่บวกแต่ละจำนวนทันที: S = {0, 2, −2, 4, −4, 6, −6, …} จำนวนเต็มก็ทำได้ในทำนองเดียวกัน

ขนาดของจำนวนตรรกยะ

ตัวอย่างที่น่าสนใจกว่าคือจำนวนตรรกยะหรือเศษส่วน เรียงลำดับได้หรือไม่ คำตอบคือได้ แต่ซับซ้อนขึ้นเล็กน้อย สร้างตารางที่มีแถวและหลักมากมายไม่จำกัด แต่ละช่องมีเศษส่วนหนึ่งจำนวน ในหลักที่ n และแถวที่ m เป็นเศษส่วน n/m ดังนั้นในหลักที่ 1 แถวที่ 2 คือ 12 และในหลักที่สามแถวที่สี่คือ 3/4

1/12/13/14/1…1/22/23/24/2…1/32/33/34/3…1/42/43/44/4………………

แล้วจะเรียงลำดับหรือกำหนดหมายเลขให้จำนวนเหล่านี้อย่างไร จะกำหนดหมายเลขทีละแถวหรือทีละหลักไม่ได้ เพราะจะติดอยู่ในแถวหรือหลักนั้นไม่มีที่สิ้นสุด แต่ให้หยิบจำนวนตามแนวทแยง: (แนวทแยงที่หนึ่ง:) 1/1 (แนวทแยงที่สอง:) 2/1, 1/2 (แนวทแยงที่สาม:) 3/1, 2/2, 1/3 (แนวทแยงที่สี่:) 4/1, 3/2, 2/3, 1/4 … ในลำดับนี้ยังมีเศษส่วนที่ซ้ำกันอยู่มาก แต่ไม่เป็นปัญหา ปัญหาที่ใหญ่กว่าคือไม่มีจำนวนลบ ซึ่งแก้ได้ง่าย ทุกครั้งที่เขียนเศษส่วนใด ให้เขียนจำนวนตรงข้ามของเศษส่วนนั้นต่อท้ายทันที สุดท้ายยังขาดศูนย์ที่ตอนต้น เพียงเท่านี้ก็ได้จำนวนตรรกยะทุกจำนวนอยู่ในลำดับแล้ว

โดยรวมจะได้ลำดับ 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

ขนาดของจำนวนจริง

จำนวนจริงมีขนาดเท่ากับจำนวนนับหรือไม่ การตัดสินจะซับซ้อนกว่ากรณีของจำนวนตรรกยะ เราจะใช้การพิสูจน์โดยข้อขัดแย้ง สมมติว่าจำนวนจริงเป็นเซตนับได้และมีฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงไปยังจำนวนนับ นั่นคือสมมติว่าเรียงลำดับได้ และให้การส่งต่อไปนี้เป็นการเรียงลำดับนั้น:

0.3522460…0.2924375…0.7230845…0.1437906…0.0865758…0.7546363…0.3419700……

ในตารางคือจำนวนจริงเจ็ดจำนวนแรกตามการเรียงลำดับของเรา แน่นอนว่าการเรียงลำดับนี้เป็นแบบใดก็ได้ ไม่จำเป็นต้องเรียงตามค่าของจำนวน

ตามสมมติฐาน ตารางอนันต์นี้มีจำนวนจริงทุกจำนวนเรียงอยู่ (ตารางนี้ไม่มีที่สิ้นสุดเช่นกัน ที่แสดงไว้เป็นเพียงเจ็ดรายการแรก) ต่อไปเราจะหาหรือสร้างจำนวนที่เป็นจำนวนจริงแต่ไม่อยู่ในตารางนี้ ถ้าหาจำนวนเช่นนั้นได้ ก็จะขัดแย้งกับข้อที่ว่าตารางมีจำนวนจริงทุกจำนวน และสรุปต่อได้ว่าเซตของจำนวนจริงไม่เป็นเซตนับได้

จำนวนที่ไม่อยู่ในตารางนั้นสร้างได้ดังนี้

0.3522460…0.2924375…0.7230845…0.1437906…0.0865758…0.7546363…0.3419700……

เริ่มด้วยการเขียน 0.… ซึ่งเป็นส่วนต้นของจำนวนจริงจำนวนใหม่ ในตำแหน่งทศนิยมที่หนึ่งให้เป็นเลขโดดที่ไม่ใช่เลขโดดในตำแหน่งที่หนึ่งของจำนวนจริงจำนวนแรกในการเรียงลำดับของเรา (ในตารางแสดงด้วยกรอบ) เลขโดดนั้นคือ 3 จึงเลือก เช่น 1 จะได้จำนวน 0.1…

ทำต่อไป ในตำแหน่งที่สองให้เป็นเลขโดดที่ไม่ใช่เลขโดดในตำแหน่งที่สองของจำนวนจริงจำนวนที่สอง เลขโดดนั้นคือ 9 จึงเลือก เช่น 2 จะได้จำนวน 0.12… ในตำแหน่งที่สามให้เป็นเลขโดดที่ต่างจากเลขโดดตัวที่สามของจำนวนจริงจำนวนที่สาม เลขโดดนั้นคือ 3 จึงเลือก เช่น 7 จะได้ 0.127…

ทำเช่นนี้ต่อไปเรื่อย ๆ ในตำแหน่งที่ n ของจำนวนใหม่จะเป็นเลขโดดที่ต่างจากเลขโดดในตำแหน่งที่ n ของจำนวนที่ n ในการเรียงลำดับของเราเสมอ

ผลที่ได้คืออะไร ผลที่ได้คือจำนวนที่ต่างจากทุกจำนวนในการเรียงลำดับของเราอย่างน้อยหนึ่งเลขโดด พิจารณาผลลัพธ์ชั่วคราวล่าสุด 0.127… จำนวนนี้ต่างจากจำนวนแรกในการเรียงลำดับอย่างน้อยที่เลขโดดตัวแรกแน่นอน เพราะเราสร้างไว้เช่นนั้น ต่างจากจำนวนที่สองอย่างน้อยที่เลขโดดตัวที่สอง ต่างจากจำนวนที่สามที่เลขโดดตัวที่สาม โดยทั่วไป จำนวนใหม่นี้ต่างจากจำนวนที่อยู่ในลำดับที่ n ของการเรียงลำดับอย่างน้อยที่เลขโดดในตำแหน่งที่ n

ดังนั้นจะไม่พบจำนวนที่สร้างขึ้นใหม่นี้ในตาราง ซึ่งควรจะแทนฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงระหว่างจำนวนนับกับจำนวนจริง จำนวนจริงจึงมีมากกว่าจำนวนนับ จำนวนจริงไม่เป็นเซตนับได้ แต่เป็นเซตนับไม่ได้

แหล่งข้อมูลเพิ่มเติม

สารบัญ: เซต, ยูเนียน อินเตอร์เซกชัน ผลต่าง และคอมพลีเมนต์ของเซต, เซตนับได้, ปฏิทรรศน์ในทฤษฎีเซต