กล่าวกันว่าเซตกลุ่มหนึ่งทำลายเซตอีกกลุ่มหนึ่งได้ หากสามารถ "เลือก" สมาชิกใดๆ จากเซตนั้นได้โดยใช้การหาจุดตัดแนวคิดเรื่องเซตที่ถูกทำลายมีบทบาทสำคัญในทฤษฎี Vapnik–Chervonenkis หรือที่รู้จักกันในชื่อทฤษฎี VC การทำลายเซตและทฤษฎี VC ถูกนำมาใช้ในการศึกษาเกี่ยวกับ กระบวนการเชิงประจักษ์รวมถึงในทฤษฎีการเรียนรู้เชิงคำนวณทาง สถิติ ด้วย

สมมติว่าAเป็นเซตและCเป็นกลุ่มของเซต กลุ่มC ทำลายเซตA ก็ต่อ เมื่อ สำหรับแต่ละเซตย่อยaของAจะมีสมาชิกc บางตัว ในCที่ทำให้

${\displaystyle a=c\cap A.}$

ในทำนองเดียวกันCจะทำลายAเมื่อส่วนร่วม ของทั้งสอง เท่ากับเซตกำลังของA : P ( A ) = { c ∩ A | c ∈ C }

เราใช้ตัวอักษร C เพื่ออ้างถึง "กลุ่ม" หรือ "ชุด" ของเซต เช่น ในกลุ่ม Vapnik – Chervonenkis (VC-class) โดยทั่วไปแล้ว เซตAมักถูกสมมติว่าเป็นเซตจำกัดเนื่องจากในกระบวนการเชิงประจักษ์ เราสนใจการแตกกระจายของเซตข้อมูลจำนวนจำกัด

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

ให้Aเป็นเซตของจุดสี่จุดบนวงกลมหนึ่งหน่วย และให้Cเป็นกลุ่มของวงกลมทั้งหมด

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

ดังภาพประกอบด้านล่าง:

• 
  แต่ละจุดสามารถแยกได้ด้วยวงกลม (แสดงทั้งสี่จุด)
• 
  แต่ละกลุ่มย่อยของจุดที่อยู่ติดกันสามารถแยกออกมาได้ด้วยวงกลม (แสดงหนึ่งในสี่แบบ)
• 
  กลุ่มจุดย่อยที่อยู่ด้านตรงข้ามของวงกลมหน่วยไม่ สามารถ แยกออกจากกันได้ด้วยแผ่นดิสก์

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

อย่างไรก็ตาม หากเรากำหนดนิยามใหม่ของ Cให้เป็นกลุ่มของวงกลมวงรี ทั้งหมด เราจะพบว่าเรายังคงสามารถแยกกลุ่มย่อยทั้งหมดจากข้างต้นได้ เช่นเดียวกับจุดที่เคยเป็นปัญหามาก่อน ดังนั้น ชุดจุด 4 จุดเฉพาะนี้จึงถูกทำลายโดยกลุ่มของวงกลมวงรี ดังแสดงในภาพด้านล่าง:

• 
  จุดตรงข้ามของจุดAสามารถแยกออกจากกันได้ด้วยวงรีบางรูป (แสดงวงรีหนึ่งในสองรูป)
• 
  แต่ละเซตย่อยของจุดสามจุดในAสามารถแยกออกจากกันได้ด้วยวงรีบางรูป (แสดงวงรีหนึ่งในสี่รูป)

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

ในการวัดปริมาณความสมบูรณ์ของชุดข้อมูลCเราใช้แนวคิดของสัมประสิทธิ์การแตกกระจาย (หรือที่เรียกว่าฟังก์ชันการเติบโต ) สำหรับชุดข้อมูลC${\displaystyle s\subset \Omega }$,${\displaystyle \Omega }$เนื่องจาก C เป็นปริภูมิใดๆ ซึ่งมักจะเป็นปริภูมิของตัวอย่างเราจึงกำหนดสัมประสิทธิ์การแตกสลายลำดับ^ที่nของCดังนี้

${\displaystyle S_{C}(n)=\max _{\forall x_{1},x_{2},\dots ,x_{n}\in \Omega }\operatorname {card} \{\,\{\,x_{1},x_{2},\dots ,x_{n}\}\cap s,s\in C\}}$

ที่ไหน${\displaystyle \operatorname {card} }$แสดงถึงจำนวนสมาชิกของเซต และ${\displaystyle x_{1},x_{2},\dots ,x_{n}\in \Omega }$คือเซตของ จุด nจุด ใดๆ

${\displaystyle S_{C}(n)}$คือจำนวนเซตย่อยที่ใหญ่ที่สุดของเซตA ใดๆ ที่ประกอบด้วย จุด nจุด ซึ่งสามารถสร้างขึ้นได้โดยการตัดกันระหว่าง A กับเซตต่างๆ ในกลุ่มC

ตัวอย่างเช่น ถ้าเซตAประกอบด้วย 3 จุด เซตกำลังของเซต A คือ${\displaystyle P(A)}$, ประกอบด้วย${\displaystyle 2^{3}=8}$องค์ประกอบ หากCทำลายAค่าสัมประสิทธิ์การทำลาย (3) จะเป็น 8 และ${\displaystyle S_{C}(2)}$จะเป็น${\displaystyle 2^{2}=4}$อย่างไรก็ตาม หากชุดใดชุดหนึ่งเหล่านั้นเกิดขึ้น${\displaystyle P(A)}$ไม่สามารถหาได้จากการตัดกันในcดังนั้น${\displaystyle S_{C}(3)}$ก็จะมีเพียง 7 ชุดเท่านั้น หากไม่สามารถหาชุดใดชุดหนึ่งเหล่านั้นได้${\displaystyle S_{C}(3)}$จะเป็น 0 นอกจากนี้ ถ้า${\displaystyle S_{C}(2)=3}$ตัวอย่างเช่น จะมีองค์ประกอบหนึ่งในเซตของเซต 2 จุดทั้งหมดจากAที่ไม่สามารถได้มาจากการตัดกันกับCซึ่งสรุปได้จากข้อนี้ว่า${\displaystyle S_{C}(3)}$นอกจากนี้ ค่าที่ได้จะน้อยกว่า 8 (กล่าวคือCจะไม่ทำลายA ) เพราะเราได้ค้นพบเซตที่ "หายไป" ในเซตกำลังที่เล็กกว่าของเซต 2 จุดแล้ว

ตัวอย่างนี้แสดงให้เห็นถึงคุณสมบัติบางประการของ${\displaystyle S_{C}(n)}$:

1. ${\displaystyle S_{C}(n)\leq 2^{n}}$สำหรับทุกค่าnเพราะว่า${\displaystyle \{s\cap A|s\in C\}\subseteq P(A)}$สำหรับใดๆ${\displaystyle A\subseteq \Omega }$.
2. ถ้า${\displaystyle S_{C}(n)=2^{n}}$นั่นหมายความว่ามีเซตที่มีขนาดสมาชิกnซึ่งสามารถถูกทำลายโดยCได้
3. ถ้า${\displaystyle S_{C}(N)<2^{N}}$สำหรับบางคน${\displaystyle N>1}$แล้ว${\displaystyle S_{C}(n)<2^{n}}$สำหรับทุกคน${\displaystyle n\geq N}$.

คุณสมบัติข้อที่สามหมายความว่า หากCไม่สามารถทำลายเซตใดๆ ที่มีจำนวนสมาชิกNได้ ก็จะไม่สามารถทำลายเซตที่มีจำนวนสมาชิกมากกว่านั้นได้เช่นกัน

ถ้าAไม่สามารถถูกทำลายโดยCได้ จะมีค่าn ที่น้อยที่สุด ที่ทำให้ค่าสัมประสิทธิ์การทำลาย (n) น้อยกว่า${\displaystyle 2^{n}}$เนื่องจากเมื่อnมีค่ามากขึ้น ก็จะมีชุดข้อมูลที่อาจถูกมองข้ามไปมากขึ้น หรืออีกทางหนึ่ง ก็มีค่าn ที่มากที่สุดค่า หนึ่ง เช่นกัน${\displaystyle S_{C}(n)}$ยังคงอยู่${\displaystyle 2^{n}}$เนื่องจากเมื่อnมีค่าน้อยลง จำนวนชุดที่สามารถละเว้นได้ก็จะน้อยลง กรณีสุดขั้วของเรื่องนี้คือ${\displaystyle S_{C}(0)}$(สัมประสิทธิ์การแตกสลายของเซตว่าง) ซึ่งจะต้องเป็นเสมอ${\displaystyle 2^{0}=1}$ข้อความเหล่านี้สนับสนุนการกำหนดมิติ VCของคลาสCดังนี้:

${\displaystyle VC(C)={\underset {n}{\min }}\{n:S_{C}(n)<2^{n}\}\,}$

หรืออีกทางเลือกหนึ่งคือ ดังนี้

${\displaystyle VC_{0}(C)={\underset {n}{\max }}\{n:S_{C}(n)=2^{n}\}.\,}$

โปรดทราบว่า${\displaystyle VC(C)=VC_{0}(C)+1.}$โดยทั่วไป มิติ VC จะถูกกำหนดดังนี้${\displaystyle VC_{0}}$จำนวนจุดที่เลือกมากที่สุดที่จะยังคงทำลายA (กล่าวคือnเช่นนั้น)${\displaystyle S_{C}(n)=2^{n}}$)

หรืออีกทางหนึ่ง หากสำหรับn ใดๆ มีเซตที่มีขนาดสมาชิกnซึ่งสามารถถูกทำลายโดยCได้แล้ว${\displaystyle S_{C}(n)=2^{n}}$สำหรับทุกค่าnและมิติ VC ของคลาสC นี้ เป็นอนันต์

คลาสที่มีมิติ VC จำกัด เรียกว่า คลาส Vapnik – Chervonenkisหรือคลาส VCคลาสCจะเป็นGlivenko – Cantelli อย่างสม่ำเสมอ ก็ต่อเมื่อเป็นคลาส VC เท่านั้น

• ทฤษฎีบท Sauer–Shelahเชื่อมโยงจำนวนสมาชิกของตระกูลเซตกับขนาดของเซตที่แตกกระจายที่ใหญ่ที่สุดของกลุ่มเซตนั้น

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

• ที่มาของศัพท์ "ชุดแตกกระจาย"โดย เจ. สตีล