ชุดพลังงาน

สมาชิกของเซตกำลังของ { x , y , z } เรียงลำดับตามการรวม
พิมพ์	ตั้งค่าการทำงาน
สนาม	ทฤษฎีเซต
คำแถลง	เซตกำลัง คือเซตที่ประกอบด้วยเซตย่อยทั้งหมดของเซตที่กำหนดให้
คำแถลงเชิงสัญลักษณ์	x ∈ P ( S ) ⟺ x ⊆ S

ในทางคณิตศาสตร์เซตกำลัง (หรือpowerset ) ของเซตSคือเซตของเซตย่อย ทั้งหมด ของSรวมทั้งเซตว่างและSเอง ด้วย ^{[ 1 ]}ในทฤษฎีเซตเชิงสัจพจน์ (ดังที่พัฒนาใน สัจพจน์ ZFC เป็นต้น ) การมีอยู่ของเซตกำลังของเซตใดๆ ถูกกำหนดโดยสัจพจน์ของเซตกำลัง [ ^{2 ] เซต} กำลังของSจะถูกแสดงด้วยสัญลักษณ์ต่างๆ เช่นP ( S ) , 𝒫 ( S ) , P ( S ) , หรือ2 ^{S [} a ^{] ​​เซตย่อยใด ๆ} ของP ( S )เรียกว่าตระกูลของเซต เหนือS${\displaystyle \mathbb {P} (S)}$

ถ้าSคือเซต{ x , y , z }แล้วเซตย่อยทั้งหมดของSคือ

• {} ( เซตว่างหรือเขียนแทนด้วยหรือ)${\displaystyle \varnothing }$${\displaystyle \emptyset }$
• { x }
• { y }
• { z }
• { x , y }
• { x , z }
• { y , z }
• { x , y , z }

ดังนั้นเซตกำลังของSคือ{{}, { x }, { y }, { z }, { x , y }, { x , z }, { y , z }, { x , y , z }} . ^{[ 3 ]}

ถ้าSเป็นเซตจำกัดที่มีจำนวนสมาชิก| S | = n (กล่าวคือ จำนวนสมาชิกทั้งหมดในเซตSคือn ) แล้วจำนวนเซตย่อยทั้งหมดของSคือ| P ( S ) | = 2 ⁿข้อเท็จจริงนี้ รวมทั้งเหตุผลที่ใช้สัญลักษณ์2 ^SแทนเซตกำลังP ( S )จะแสดงให้เห็นต่อไปนี้

ฟังก์ชันบ่งชี้หรือฟังก์ชันลักษณะเฉพาะของเซตย่อยAของเซตSที่มีจำนวนสมาชิก| S | = nคือฟังก์ชันจากSไปยังเซตสองสมาชิก{0, 1}ซึ่งเขียนแทนด้วยI _A  : S → {0, 1}และฟังก์ชันนี้บ่งชี้ว่าสมาชิกของSเป็นสมาชิกของAหรือไม่ ถ้าxในSเป็นสมาชิกของAแล้วI _A ( x ) = 1และ0ถ้าไม่ใช่ เซตย่อยA แต่ละเซต ของSถูกระบุหรือเทียบเท่ากับฟังก์ชันบ่งชี้I _Aและ{0,1} ^Sเป็นเซตของฟังก์ชันทั้งหมดจากSไปยัง{0, 1}ประกอบด้วยฟังก์ชันบ่งชี้ทั้งหมดของเซตย่อยทั้งหมดของSกล่าวอีกนัยหนึ่ง{0, 1} ^Sเทียบเท่าหรือเป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงกับเซตกำลังP ( S )เนื่องจากสมาชิกแต่ละตัวในSสอดคล้องกับ0หรือ1ภายใต้ฟังก์ชันใดๆ ใน{0, 1} ^Sดังนั้นจำนวนของฟังก์ชันทั้งหมดใน{0, 1} ^Sคือ2 ⁿ เนื่องจาก สามารถกำหนดเลข2 ^ได้ เป็น {0, 1} ⁽ดูตัวอย่างเช่นลำดับของฟอน นอยมันน์ ) ดังนั้น P ( S )จึงถูกแทนด้วย2Sเห็นได้ชัดว่า^| 2S | = 2 ^{| S |}เป็นจริง โดยทั่วไปแล้วXYคือเซตของฟังก์ชันทั้งหมดจาก^Yไปยัง X ^และ | XY | = | X || ^{Y |}

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

เซตกำลังของเซตSพร้อมด้วยการดำเนินการยูเนียนอินเตอร์เซกชันและคอมพลีเมนต์คือσ-แอลเจบราเหนือSและสามารถมองได้ว่าเป็นตัวอย่างต้นแบบของแอลเจบราแบบบูลีนอันที่จริง เราสามารถแสดงได้ว่าแอลเจบราแบบบูลีนจำกัด ใดๆ ก็ตามนั้น สม isomorphicกับแอลเจบราแบบบูลีนของเซตกำลังของเซตจำกัด สำหรับ แอลเจบราแบบบูลีน อนันต์นั้น สิ่งนี้จะไม่เป็นจริงอีกต่อไป แต่แอลเจบราแบบบูลีนอนันต์ทุกตัวสามารถแสดงได้ในรูปของซับแอลเจบราของแอลเจบราแบบบูลีนของเซตกำลัง (ดูทฤษฎีบทการแสดงแทนของสโตน )

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

ในทฤษฎีเซต X Y ^คือสัญลักษณ์ที่ใช้แทนเซตของฟังก์ชัน ทั้งหมด จากYไปยังXเนื่องจาก " 2 " สามารถนิยามได้ว่าเป็น{0, 1} (ดูตัวอย่างเช่นลำดับของฟอน นอยมันน์ ) ดังนั้น2 ^S (นั่นคือ{0, 1} ^{S )}จึงเป็นเซตของฟังก์ชัน ทั้งหมด จากSไปยัง{0, 1}ดังที่แสดงไว้ข้างต้น 2 SและเซตกำลังของS , P ( S )ถือว่าเหมือนกันในทางทฤษฎีเซต

ความเท่าเทียมกันนี้สามารถนำไปใช้กับตัวอย่างข้างต้นซึ่งS = { x , y , z }เพื่อให้ได้ไอโซมอร์ฟิซึมกับการแสดงเลขฐานสองของตัวเลขตั้งแต่ 0 ถึง2 ⁿ − 1โดยที่nคือจำนวนองค์ประกอบในเซตSหรือ| S | = nก่อนอื่น เซตที่แจงนับ{ ( x , 1), ( y , 2), ( z , 3) ​​}จะถูกกำหนดขึ้น โดยที่ตัวเลขในแต่ละคู่ลำดับแสดงถึงตำแหน่งขององค์ประกอบที่จับคู่กันของSในลำดับของเลขฐานสอง เช่น{ x , y } = 011 ₍₂₎ ; xของSอยู่ที่ตำแหน่งแรกจากด้านขวาของลำดับนี้ และyอยู่ที่ตำแหน่งที่สองจากด้านขวา และ 1 ในลำดับหมายความว่าองค์ประกอบของSที่สอดคล้องกับตำแหน่งของมันในลำดับนั้นมีอยู่ในเซตย่อยของSสำหรับลำดับนั้น ในขณะที่ 0 หมายความว่าไม่มี

สำหรับเซตกำลังทั้งหมดของSเราจะได้:

การแมปแบบหนึ่งต่อหนึ่งจากP ( S ) ไปยังจำนวนเต็ม นั้นเป็นไปโดยพลการ ดังนั้นการแสดงแทนของเซตย่อยทั้งหมดของSจึงไม่ซ้ำกัน แต่ลำดับการเรียงของเซตที่แจงนับไว้จะไม่เปลี่ยนแปลงจำนวนสมาชิกของเซต (เช่น สามารถใช้ {( y , 1), ( z , 2), ( x , 3)}เพื่อสร้างการแมปแบบหนึ่งต่อหนึ่งอีกแบบหนึ่งจากP ( S )ไปยังจำนวนเต็มได้โดยไม่เปลี่ยนแปลงจำนวนการจับคู่แบบหนึ่งต่อหนึ่ง)

อย่างไรก็ตาม การแสดงผลแบบไบนารีที่มีจำนวนจำกัดเช่นนี้ จะเป็นไปได้ก็ต่อเมื่อเซตSสามารถแจงนับได้ (ในตัวอย่างนี้x , yและzถูกแจงนับด้วย1 , 2และ3ตามลำดับ เป็นตำแหน่งของลำดับเลขฐานสอง) การแจงนับเป็นไปได้แม้ว่าSจะมีขนาดอนันต์ (กล่าวคือ จำนวนองค์ประกอบในSเป็นอนันต์) เช่น เซตของจำนวนเต็มหรือจำนวนตรรกยะ แต่เป็นไปไม่ได้ ตัวอย่างเช่น หากSเป็นเซตของจำนวนจริง ในกรณีนี้เราไม่สามารถแจงนับจำนวนอตรรกยะทั้งหมดได้

ทฤษฎีบททวินามมีความเกี่ยวข้องอย่างใกล้ชิดกับเซตกำลัง การ รวมกันที่มี kสมาชิกจากเซตใดเซตหนึ่งก็คือเซต ย่อยที่มี kสมาชิก ดังนั้นจำนวนการรวมกันซึ่งเขียนแทนด้วยC( n , k ) (หรือเรียกว่าสัมประสิทธิ์ทวินาม ) คือจำนวนเซตย่อยที่มีkสมาชิกในเซตที่มีnสมาชิก กล่าวอีกนัยหนึ่งคือ จำนวนเซตที่มีkสมาชิกซึ่งเป็นสมาชิกของเซตกำลังของเซตที่มีnสมาชิก

ตัวอย่างเช่น เซตกำลังของเซตที่มีสมาชิกสามตัว มีดังนี้:

• C(3, 0) = 1เซตย่อยที่มี สมาชิก 0ตัว (เซตย่อยว่าง)
• C(3, 1) = 3เซตย่อยที่มี สมาชิก 1ตัว (เซตย่อยที่มีสมาชิกเพียงตัวเดียว)
• C(3, 2) = 3เซตย่อยที่มี2สมาชิก (ส่วนเติมเต็มของเซตย่อยที่มีสมาชิกเดียว)
• C(3, 3) =เซตย่อย 1 เซตที่มี3สมาชิก (คือเซตดั้งเดิมนั่นเอง)

โดยใช้ความสัมพันธ์นี้ เราสามารถคำนวณ| 2 ^S |โดยใช้สูตร: $${\displaystyle \left|2^{S}\right|=\sum _{k=0}^{|S|}{\binom {|S|}{k}}}$$

ดังนั้น จึงสามารถอนุมานเอกลักษณ์ต่อไปนี้ได้ โดยสมมติว่า| S | = n : $${\displaystyle \left|2^{S}\right|=2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}}$$

ถ้าSเป็นเซตจำกัดนิยามเวียนเกิดของP ( S )จะเป็นดังนี้:

• ถ้าS = {}แล้วP ( S ) = { {} }
• มิฉะนั้น ให้e ∈ SและT = S ∖ { e }แล้วP ( S ) = P ( T ) ∪ { t ∪ { e } : t ∈ P ( T ) }

กล่าวคือ:

• เซตกำลังของเซตว่างคือเซต ที่มีสมาชิกเพียง ตัวเดียวคือเซตว่าง
• สำหรับเซตS ที่ไม่ว่าง เปล่า ให้ e เป็นสมาชิกใดๆ ของเซต S และTเป็นส่วนเติมเต็มสัมพัทธ์ ของ e แล้วเซตกำลังของSคือการรวมกันของเซตกำลังของTและเซตกำลังของTซึ่งแต่ละสมาชิกได้รับการขยายด้วยสมาชิกe${\displaystyle e}$

บางครั้ง เซตของเซตย่อยของSที่มีขนาดสมาชิกน้อยกว่าหรือเท่ากับκจะถูกแทนด้วยP _κ ( S )หรือ[ S ] ^κ และ บางครั้งเซตของเซตย่อยที่มีขนาดสมาชิกน้อยกว่าκ อย่างเคร่งครัด จะถูกแทนด้วย P _{< κ} ( S )หรือ[ S ] ^{< κ}ในทำนองเดียวกัน เซตของเซตย่อยที่ไม่ว่างของS อาจถูก แทน ด้วยP _≥1 ( S )หรือP ⁺ ( S )

เซตสามารถถือได้ว่าเป็นพีชคณิตที่ไม่มีการดำเนินการที่ไม่ใช่แบบธรรมดาหรือสมการนิยาม จากมุมมองนี้ แนวคิดของเซตกำลังของXในฐานะเซตของเซตย่อยทั้งหมดของXสามารถขยายไปสู่เซตของพีชคณิตย่อยทั้งหมดของโครงสร้างพีชคณิตหรือพีชคณิต ได้อย่างเป็นธรรมชาติ ^{[ 4 ] [ 5 ]}

เซตกำลังของเซต เมื่อเรียงลำดับโดยการรวม จะเป็นพีชคณิตบูลีนอะตอมที่สมบูรณ์เสมอ และพีชคณิตบูลีนอะตอมที่สมบูรณ์ทุกตัวเกิดขึ้นจากแลตทิซของเซตย่อยทั้งหมดของเซตบางเซต การวางนัยทั่วไปสำหรับพีชคณิตใดๆ ก็คือ เซตของพีชคณิตย่อยของพีชคณิต เมื่อเรียงลำดับโดยการรวมอีกครั้ง จะเป็นแลตทิซพีชคณิต เสมอ และแลตทิซพีชคณิตทุกตัวเกิดขึ้นจากแลตทิซของพีชคณิตย่อยของพีชคณิตบางตัว^{[ 6 ]}ดังนั้นในแง่นั้น พีชคณิตย่อยจึงมีพฤติกรรมคล้ายคลึงกับเซตย่อย

อย่างไรก็ตาม มีคุณสมบัติสำคัญสองประการของเซตย่อยที่ไม่ถ่ายทอดไปยังพีชคณิตย่อยโดยทั่วไป ประการแรก แม้ว่าเซตย่อยของเซตจะประกอบกันเป็นเซต (รวมถึงแลตทิซ) แต่ในบางคลาส อาจไม่สามารถจัดระเบียบพีชคณิตย่อยของพีชคณิตให้เป็นพีชคณิตในคลาสนั้นได้ แม้ว่าจะสามารถจัดระเบียบเป็นแลตทิซได้เสมอ ประการที่สอง ในขณะที่เซตย่อยของเซตมีความสัมพันธ์แบบหนึ่งต่อหนึ่งกับฟังก์ชันจากเซตนั้นไปยังเซต{0, 1} = 2แต่ก็ไม่มีการรับประกันว่าคลาสของพีชคณิตจะมีพีชคณิตที่สามารถทำหน้าที่เป็น2ในลักษณะนี้ได้

พีชคณิตบางประเภทมีคุณสมบัติทั้งสองอย่างนี้ คุณสมบัติแรกพบได้บ่อยกว่า ส่วนกรณีที่มีทั้งสองคุณสมบัติพร้อมกันนั้นค่อนข้างหายาก พีชคณิตประเภทหนึ่งที่มีทั้งสองคุณสมบัติคือมัลติกราฟเมื่อกำหนดมัลติกราฟสองกราฟGและHโฮโมมอร์ฟิซึมh  : G → Hประกอบด้วยฟังก์ชันสองฟังก์ชัน ฟังก์ชันหนึ่งแมปจุดยอดไปยังจุดยอด และอีกฟังก์ชันหนึ่งแมปขอบไปยังขอบ เซตH ^Gของโฮโมมอร์ฟิซึมจากGไปยังHสามารถจัดเรียงได้เป็นกราฟที่มีจุดยอดและขอบเป็นฟังก์ชันจุดยอดและฟังก์ชันขอบที่ปรากฏในเซตนั้นตามลำดับ ยิ่งไปกว่านั้น ซับกราฟของมัลติกราฟGจะมีความสัมพันธ์แบบหนึ่งต่อหนึ่งกับโฮโมมอร์ฟิซึมกราฟจากGไปยังมัลติกราฟΩซึ่งนิยามได้ว่าเป็นกราฟทิศทางสมบูรณ์บนจุดยอดสองจุด (ดังนั้นจึงมีขอบสี่ขอบ ได้แก่ ขอบวนรอบตัวเองสองขอบและขอบอีกสองขอบที่สร้างเป็นวงจร) เสริมด้วยขอบที่ห้า ได้แก่ ขอบวนรอบตัวเองที่สองที่จุดยอดจุดหนึ่ง ดังนั้น เราจึงสามารถจัดระเบียบกราฟย่อยของGเป็นมัลติกราฟΩ ^Gซึ่งเรียกว่าวัตถุพลังงานของGได้

สิ่งที่พิเศษเกี่ยวกับมัลติกราฟในฐานะพีชคณิตคือการดำเนินการของมันเป็นแบบเอกภาค มัลติกราฟมีองค์ประกอบสองประเภทที่สร้างเซตVของจุดยอดและEของขอบ และมีการดำเนินการเอกภาคสองอย่างs , t  : E → Vที่ให้จุดยอดต้นทาง (เริ่มต้น) และจุดยอดปลายทาง (สิ้นสุด) ของแต่ละขอบ พีชคณิตที่มีการดำเนินการทั้งหมดเป็นแบบเอกภาคเรียกว่าพรีชีฟ พรีชีฟทุกคลาสจะมีพรีชีฟΩที่ทำหน้าที่แทนพีชคณิตย่อยที่2ทำหน้าที่แทนเซตย่อย คลาสดังกล่าวเป็นกรณีพิเศษของแนวคิดทั่วไปของโทโพส พื้นฐาน ในฐานะหมวดหมู่ที่เป็นปิด (และยิ่งไปกว่านั้นยังเป็นปิดแบบคาร์ทีเซียน ) และมีวัตถุΩที่เรียกว่าตัวจำแนกวัตถุย่อยแม้ว่าบางครั้งคำว่า "วัตถุกำลัง" จะถูกใช้เป็นคำพ้องความหมายกับวัตถุเลขชี้กำลังY ^Xแต่ในทฤษฎีโทโพสYจำเป็นต้องเป็นΩ ^{[ 7 ]}

มีฟังก์ชัน เซตกำลังทั้งแบบโคแวเรียนต์และคอนทราแวเรียนต์ คือP : Set → SetและP : Set ^op → Setฟังก์ชันโคแวเรียนต์ถูกนิยามอย่างง่ายกว่าคือ ฟังก์ชันที่ส่งเซตSไปยังP ( S )และมอร์ฟิซึมf : S → T (ในที่นี้คือฟังก์ชันระหว่างเซต) ไปยังมอร์ฟิซึมภาพ นั่นคือ สำหรับA = { x ₁ , x ₂ , ...} ∈ P ( S ), P f ( A ) = { f ( x ₁ ), f ( x ₂ ), ...} ∈ P ( T )ในส่วนอื่นของบทความนี้ เซตกำลังถูกนิยามว่าเป็นเซตของฟังก์ชันจากSไปยังเซตที่มี 2 สมาชิก ในทางรูปธรรม นี่เป็นการนิยามไอโซมอร์ฟิซึมตามธรรมชาติP ≅ Set(-,2 ) ฟังก์ชันเซตกำลังแบบคอนทราแวเรียนต์จะแตกต่างจากเวอร์ชันแบบโคแวเรียนต์ตรงที่มันส่งfไปยัง มอร์ฟิซึมภาพ ก่อนหน้าดังนั้นถ้าf ( A ) = B ⊆ T , P f ( B ) = Aนี่เป็นเพราะฟังก์ชันทั่วไปC(-, c )รับมอร์ฟิซึมh : a → bไปยังการประกอบก่อนหน้าโดยhดังนั้นฟังก์ชันh *: C( b , c ) → C( a , c )ซึ่งรับมอร์ฟิซึมจาก^bไปยังcและนำไปเป็นมอร์ฟิซึมจากaไปยังcผ่านbโดยh [ ^{8 ]}

ในทฤษฎีหมวดหมู่และทฤษฎีโทโพอิพื้นฐานตัวบ่งปริมาณสากลสามารถเข้าใจได้ว่าเป็นตัวผกผันทางขวาของฟังก์ชันระหว่างเซตกำลัง ซึ่งเป็นฟังก์ชัน ภาพผกผันของฟังก์ชันระหว่างเซต ในทำนองเดียวกันตัวบ่งปริมาณเชิงมีอยู่คือ ตัว ผกผันทางซ้าย^{[ 9 ]}

• ทฤษฎีบทของแคนเตอร์
• ครอบครัวของชุดต่างๆ
• ฟิลด์ของเซต
• การผสมผสาน
• คลีน สตาร์

• เดฟลิน, คีธ เจ. (1979). พื้นฐานของทฤษฎีเซตสมัยใหม่ . Universitext. Springer-Verlag . ISBN 0-387-90441-7. Zbl  0407.04003 .
• Halmos, Paul R. (1960). ทฤษฎีเซตแบบง่าย . ชุดหนังสือคณิตศาสตร์ระดับปริญญาตรี. บริษัท van Nostrand. Zbl  0087.04403 .
• Mac Lane, Saunders ; Moerdijk, Ieke (1992), Sheaves in Geometry and Logic , Springer-Verlag, ISBN 0-387-97710-4
• ปุนตัมเบการ์, เอเอ (2007). ทฤษฎีออโตมาตาและภาษาเชิงรูปธรรม . สำนักพิมพ์ทางเทคนิค. ISBN 978-81-8431-193-8.
• Weisstein, Eric W. "Power Set" . mathworld.wolfram.com . เก็บถาวรจากต้นฉบับเมื่อ 2023-04-06 . เรียกดูเมื่อ2020-09-05 .

ลองค้นหาคำว่า "power set"ใน Wiktionary ซึ่งเป็นพจนานุกรมออนไลน์ฟรี

• ตั้งค่าพลังงานที่PlanetMath
• ชุดพลังงานที่ห้องปฏิบัติการn
• วัตถุพลังงานที่ห้องปฏิบัติการn
• อัลกอริทึมเซตกำลังในภาษา C++