32.3 เพาเวอร์เซต

ร้านให้เลือกรสไอศกรีมเสริมได้จากมะม่วงกับมะพร้าว ลูกค้าเลือกทั้งสองอย่าง อย่างเดียว หรือไม่เลือกเลยก็ได้ ถ้าเขียนรสเสริมเป็นเซต $\{\text{มะม่วง},\text{มะพร้าว}\}$ ทางเลือกของลูกค้าแต่ละแบบคือสับเซตหนึ่งเซต รายการทางเลือกทั้งหมดจึงเป็นเซตของสับเซต

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

รวบรวมสับเซตทั้งหมด

นิยาม

เพาเวอร์เซตของ $A$ เขียน $\mathcal P(A)$ คือเซตที่มีสับเซตทุกเซตของ $A$ เป็นสมาชิก สมาชิกของเพาเวอร์เซตจึงเป็นเซตเสมอ

นิยามนี้แปลงคำถามเรื่องสับเซตจากหน้า 32.2 ให้เป็นคำถามเรื่องสมาชิก ข้อความ $B\in\mathcal P(A)$ กับ $B\subseteq A$ มีความหมายเดียวกันทุกประการ ประโยชน์คือเราได้เซตใหม่หนึ่งเซตที่เก็บทางเลือกทั้งหมดไว้ด้วยกัน นับได้ และใช้การดำเนินการของเซตกับมันได้

ทำไมจึงได้ 2ⁿ

ถ้า $A$ มีสมาชิก $n$ ตัว การสร้างสับเซตหนึ่งเซตคือการตัดสินสมาชิกทีละตัวว่าใส่หรือไม่ใส่ แต่ละตัวมีสองทางเลือก และการตัดสินของตัวหนึ่งไม่ไปบังคับตัวอื่น จำนวนแบบทั้งหมดจึงเป็น $2\times2\times\cdots\times2$ จำนวน $n$ ตัว คือ $2^n$ รวมเซตว่างซึ่งไม่ใส่สักตัว และ $A$ เองซึ่งใส่ทุกตัว สูตรนี้ใช้กับเซตจำกัด

แผนภาพต้นไม้ข้างล่างแสดงการตัดสินสำหรับ $\{a,b,c\}$ เดินจากซ้ายไปขวา แต่ละทางเดินจบที่สับเซตหนึ่งเซต และไม่มีสองทางเดินใดให้สับเซตเดียวกัน

เส้นทึบสีส้มคือใส่สมาชิกตัวนั้น เส้นประคือไม่ใส่ ทุกชั้นแตกเป็นสองทาง สามชั้นจึงได้

2^3=8

สับเซต ปลายทางล่างสุดคือ

\varnothing

แจกแจงอย่างมีระบบ

เวลาเขียน $\mathcal P(A)$ ให้เรียงตามขนาด เริ่มจากสับเซตที่ไม่มีสมาชิก ตามด้วยที่มีหนึ่งสมาชิก สองสมาชิก จนถึงทั้งหมด วิธีนี้ทำให้ตรวจจำนวนได้และลดการเขียนซ้ำ เพราะในแต่ละขนาดเราแค่ไล่เลือกให้ครบ การแจกแจงต้องรักษาวงเล็บของสมาชิกที่เป็นเซตเอาไว้ เช่น $\{\{1\}\}$ เป็นเซตที่มีสมาชิกหนึ่งตัว ไม่ใช่ $\{1\}$

ตัวอย่าง 1

หา $\mathcal P(A)$ เมื่อ $A=\{a,b\}$

ขนาดศูนย์ มีแบบเดียวคือ $\varnothing$ ห้ามลืม เพราะเซตว่างเป็นสับเซตของทุกเซตตามหน้า 32.2
ขนาดหนึ่ง เลือกสมาชิกทีละตัว ได้ $\{a\}$ และ $\{b\}$
ขนาดสอง เลือกทั้งสองตัว ได้ $\{a,b\}$ ซึ่งคือ $A$ เอง
ครอบด้วยวงเล็บปีกกาอีกชั้น เพราะเพาเวอร์เซตเป็นเซตที่มีสับเซตเหล่านี้เป็นสมาชิก $\mathcal P(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}$
ตรวจจำนวน ได้ $4$ สมาชิก ตรงกับ $2^2=4$

ตัวอย่าง 2

หา $\mathcal P(\{1,2,3\})$ และนับว่าแต่ละขนาดมีกี่เซต

ขนาดศูนย์ $\varnothing$ มี $1$ เซต
ขนาดหนึ่ง $\{1\}$ $\{2\}$ $\{3\}$ มี $3$ เซต
ขนาดสอง เลือกสองตัวจากสาม คิดง่ายๆ ว่าเลือกตัวที่ไม่เอาออกหนึ่งตัว ได้ $\{2,3\}$ $\{1,3\}$ $\{1,2\}$ มี $3$ เซต
ขนาดสาม $\{1,2,3\}$ มี $1$ เซต
รวม $1+3+3+1=8=2^3$ ตรงกับสูตร ถ้าบวกได้ไม่ครบแปด ให้กลับไปดูขนาดที่ขาด

จำนวน $1,3,3,1$ ที่ได้คือจำนวนวิธีเลือกสมาชิก $0,1,2,3$ ตัวจากสามตัว บทที่ 43 เรื่องหลักการนับจะคำนวณจำนวนเหล่านี้ได้โดยตรงโดยไม่ต้องแจกแจง

ลองคิดก่อน

$\mathcal P(\varnothing)$ เป็นเซตว่างหรือไม่

ดูคำตอบ

ไม่เป็น เพราะเซตว่างมีสับเซตคือเซตว่างเอง ดังนั้น $\mathcal P(\varnothing)=\{\varnothing\}$ มีสมาชิกหนึ่งตัว ตรงกับ $2^0=1$ นี่คือกล่องที่มีกล่องเปล่าอยู่ข้างในจากหน้า 32.1

สมาชิกหรือสับเซตของเพาเวอร์เซต

เพาเวอร์เซตมีวงเล็บซ้อนกันหลายชั้น จึงเป็นที่ที่ $\in$ กับ $\subseteq$ สลับกันง่ายที่สุด ใช้หลักเดียวกับหน้า 32.2 คือแจกแจงสมาชิกของเซตทางขวาให้เห็นก่อน แล้วค่อยตอบ

ตัวอย่าง 3

ให้ $A=\{1,2\}$ ตัดสินข้อความ $1\in\mathcal P(A)$ $\{1\}\in\mathcal P(A)$ $\{1\}\subseteq\mathcal P(A)$ และ $\{\varnothing\}\subseteq\mathcal P(A)$

แจกแจงก่อน $\mathcal P(A)=\{\varnothing,\{1\},\{2\},\{1,2\}\}$ สมาชิกทั้งสี่ตัวเป็นเซต ไม่มีตัวไหนเป็นจำนวนเปล่าๆ
$1\in\mathcal P(A)$ เป็นเท็จ เพราะ $1$ เป็นจำนวน ไม่อยู่ในรายการ
$\{1\}\in\mathcal P(A)$ เป็นจริง เพราะ $\{1\}\subseteq A$ จึงอยู่ในรายการ
$\{1\}\subseteq\mathcal P(A)$ ถามว่าสมาชิกของ $\{1\}$ คือ $1$ อยู่ใน $\mathcal P(A)$ หรือไม่ จากข้อ 2 ไม่อยู่ จึงเป็นเท็จ
$\{\varnothing\}\subseteq\mathcal P(A)$ ถามว่า $\varnothing\in\mathcal P(A)$ หรือไม่ อยู่ในรายการตัวแรก จึงเป็นจริง

เงื่อนไขบังคับและเงื่อนไขห้าม

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

ตัวอย่าง 4

เซต $B$ มีสมาชิกห้าตัว รวม $7$ ด้วย สับเซตที่มี $7$ อยู่ด้วยมีกี่เซต

$7$ ถูกบังคับให้อยู่ จึงมีทางเดียว ไม่ได้คูณสองให้ตัวนี้
เหลือสมาชิกอีกสี่ตัวที่ใส่หรือไม่ใส่ได้อิสระ ตัวละสองทาง
ได้ $1\times2^4=16$ เซต
ตรวจด้วยเหตุผลอีกแบบ สับเซตทั้งหมด $2^5=32$ เซต ครึ่งหนึ่งมี $7$ อีกครึ่งไม่มี เพราะจับคู่ได้ทีละคู่โดยเติมหรือดึง $7$ ออก จึงได้ $16$ เท่ากัน

ตัวอย่าง 5

ให้ $A=\{1,2,3,4,5\}$ ต้องการสับเซตที่มี $1$ แต่ไม่มี $5$ มีกี่เซต

$1$ ต้องถูกเลือกและ $5$ ต้องไม่ถูกเลือก สองตัวนี้จึงมีทางเดียว
สมาชิก $2,3,4$ ยังมีสองทางเลือกเป็นอิสระ
จึงมี $2^3=8$ เซต
ตรวจขอบเขต สับเซตที่เล็กที่สุดที่ผ่านเงื่อนไขคือ $\{1\}$ ใหญ่ที่สุดคือ $\{1,2,3,4\}$ ทั้งคู่ต้องถูกนับ ส่วนเซตว่างไม่ถูกนับเพราะไม่มี $1$

ถ้าแจกแจงจริงแล้วไม่พบ $\{1\}$ หรือ $\{1,2,3,4\}$ แสดงว่าวิธีนับยังขาดกรณี การตรวจสับเซตที่เล็กที่สุดและใหญ่ที่สุดจึงเป็นวิธีเช็กเร็วที่ใช้ได้ทุกครั้ง

สับเซตแท้

คำว่า สับเซตแท้ ในบทนี้หมายถึงสับเซตที่ไม่เท่ากับเซตเดิม จึงตัดออกหนึ่งเซตคือ $A$ เอง เซตขนาด $n$ จึงมีสับเซตแท้ $2^n-1$ เซต เช่นเซตที่มีสมาชิก $6$ ตัวมีสับเซตแท้ $2^6-1=63$ เซต เซตว่างยังนับเป็นสับเซตแท้ เว้นแต่ $A$ เองเป็นเซตว่าง

ลองคิดก่อน

$\mathcal P(A)$ มีสมาชิก $32$ ตัว เพื่อนบอกว่า $A$ มีสมาชิก $16$ ตัว เพราะ $32\div2=16$ ถูกหรือไม่

ดูคำตอบ

ไม่ถูก จำนวนสับเซตคือ $2^n$ ไม่ใช่ $2n$ ต้องหา $n$ ที่ทำให้ $2^n=32$ ซึ่งคือ $n=5$ ถ้า $A$ มี $16$ ตัวจริง เพาเวอร์เซตจะมี $2^{16}=65536$ สมาชิก มากกว่า $32$ หลายพันเท่า

หน้าถัดไปกลับมาที่ทั้งสองสาย เรื่องการสร้างเซตใหม่จากสองเซตด้วยคำว่า และ หรือ และ ไม่

สรุป

เพาเวอร์เซตมีสับเซตเป็นสมาชิก $B\in\mathcal P(A)$ หมายถึง $B\subseteq A$
เซตจำกัดขนาด $n$ มีสับเซต $2^n$ เซต เพราะสมาชิกแต่ละตัวใส่หรือไม่ใส่ได้อิสระ
แจกแจงเรียงตามขนาด แล้วตรวจว่ารวมได้ $2^n$
สมาชิกที่ถูกบังคับหรือถูกห้ามไม่มีทางเลือก นับเฉพาะตัวที่เหลือ
สับเซตแท้มี $2^n-1$ เซต
ตรวจทั้งวงเล็บและจำนวนสมาชิกก่อนตอบ