تقسيم مجموعة

في الرياضيات ، تقسيم المجموعة هو تجميع عناصرها في مجموعات فرعية غير فارغة ، بحيث يتم تضمين كل عنصر في مجموعة فرعية واحدة فقط.

تُعرّف كل علاقة تكافؤ على مجموعة ما تجزئةً لهذه المجموعة، وتُعرّف كل تجزئة علاقة تكافؤ. تُسمى المجموعة التي تحتوي على علاقة تكافؤ أو تجزئة أحيانًا بـ" مجموعة جزئية" ، خاصةً في نظرية الأنواع ونظرية البرهان .

إن تقسيم المجموعة X هو مجموعة من المجموعات الفرعية غير الفارغة من X بحيث يكون كل عنصر x في X موجودًا في واحدة فقط من هذه المجموعات الفرعية ^{[ 2 ]} (أي أن المجموعات الفرعية هي مجموعات غير فارغة ومنفصلة بشكل متبادل ).

وبصورة مكافئة، فإن عائلة من المجموعات P هي تقسيم لـ X إذا وفقط إذا تحققت جميع الشروط التالية: ^{[ 3 ]}

• لا تحتوي العائلة P على المجموعة الفارغة (أي${\displaystyle \emptyset \notin P}$).
• اتحاد المجموعات في P يساوي X ( أي${\displaystyle \textstyle \bigcup _{A\in P}A=X}$يُقال إن المجموعات في P تستنفد أو تغطي X. انظر أيضًا الأحداث الشاملة بشكل جماعي والتغطية (في علم الطوبولوجيا) .
• تقاطع أي مجموعتين مختلفتين في P يكون فارغًا ( أي${\displaystyle (\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset }$يُقال إن عناصر المجموعة P منفصلة مثنى مثنى أو متنافية. انظر أيضًا التنافي المتبادل .

المجموعات في${\displaystyle P}$تُسمى هذه الأجزاء بالكتل أو الأجزاء أو الخلايا الخاصة بالتقسيم. ^{[ 4 ]} إذا${\displaystyle a\in X}$ثم نمثل الخلية التي تحتوي${\displaystyle a}$بواسطة${\displaystyle [a]}$أي بمعنى آخر،${\displaystyle [a]}$هي رمز للخلية في${\displaystyle P}$والذي يحتوي${\displaystyle a}$.

كل قسم${\displaystyle P}$يمكن تحديدها بعلاقة تكافؤ على${\displaystyle X}$أي العلاقة${\displaystyle \sim _{\!P}}$بحيث يكون لأي${\displaystyle a,b\in X}$لدينا${\displaystyle a\sim _{\!P}b}$إذا وفقط إذا${\displaystyle a\in [b]}$(بمعنى آخر، إذا وفقط إذا${\displaystyle b\in [a]}$). الترميز${\displaystyle \sim _{\!P}}$يُثير هذا المفهوم فكرة إمكانية بناء علاقة التكافؤ من التقسيم. وعلى العكس، يمكن تعريف كل علاقة تكافؤ بتقسيم. ولهذا السبب يُقال أحيانًا بشكل غير رسمي أن "علاقة التكافؤ هي نفسها التقسيم". إذا كان P هو التقسيم المُعرَّف بعلاقة تكافؤ مُعطاة،${\displaystyle \sim }$ثم يكتب بعض المؤلفين${\displaystyle P=X/{\sim }}$يشير هذا الترميز إلى فكرة أن التقسيم هو المجموعة X مقسمة إلى خلايا. كما يوحي الترميز بأنه يمكن بناء التقسيم انطلاقاً من علاقة التكافؤ.

• المجموعة الفارغة${\displaystyle \emptyset }$يحتوي على قسم واحد فقط، وهو${\displaystyle \emptyset }$(ملاحظة: هذا هو القسم، وليس أحد أعضاء القسم.)
• لأي مجموعة غير فارغة X ، فإن P = { X } هو تقسيم لـ X ، ويسمى التقسيم التافه .
  • على وجه الخصوص، كل مجموعة أحادية { x } لها قسم واحد بالضبط، وهو { { x } } .
• بالنسبة لأي مجموعة جزئية غير فارغة A من مجموعة U ، فإن المجموعة A مع مكملتها تشكل تجزئة لـ U ، وهي { A ، U ∖ A } .
• تحتوي المجموعة {1، 2، 3} على هذه الأقسام الخمسة (قسم واحد لكل عنصر):
  • { {1}, {2}, {3} } ، تُكتب أحيانًا 1 | 2 | 3.
  • { {1, 2}, {3} } , أو 1 2 | 3.
  • { {1, 3}, {2} } , أو 1 3 | 2.
  • { {1}, {2, 3} } , أو 1 | 2 3.
  • { {1, 2, 3} } , أو 1 2 3.
• ما يلي ليس تقسيمات للمجموعة {1، 2، 3} :
  • { {}, {1, 3}, {2} } ليست تجزئة (لأي مجموعة) لأن أحد عناصرها هو المجموعة الفارغة .
  • { {1, 2}, {2, 3} } ليست تجزئة (لأي مجموعة) لأن العنصر 2 موجود في أكثر من كتلة واحدة.
  • { {1}, {2} } ليست تجزئة للمجموعة {1, 2, 3} لأنه لا يوجد أي من كتلها يحتوي على 3؛ ومع ذلك، فهي تجزئة للمجموعة {1, 2} .

لأي علاقة تكافؤ على مجموعة X ، فإن مجموعة فئات التكافؤ الخاصة بها تُشكّل تجزئةً لـ X. وبالعكس، من أي تجزئة P لـ X ، يُمكننا تعريف علاقة تكافؤ على X بوضع x ~ y تحديدًا عندما يكون x و y في نفس الجزء من P. وبالتالي، فإن مفهومي علاقة التكافؤ والتجزئة متكافئان جوهريًا. ^{[ 5 ]}

تضمن بديهية الاختيار، لأي تجزئة لمجموعة X ، وجود مجموعة جزئية من X تحتوي على عنصر واحد فقط من كل جزء من أجزاء التجزئة. وهذا يعني أنه عند وجود علاقة تكافؤ على مجموعة ما، يمكن اختيار عنصر تمثيلي معياري من كل فئة تكافؤ.

التقسيم α لمجموعة X هو تحسين للتقسيم ρ لمجموعة X ، ونقول إن α أدق من ρ وأن ρ أوسع من α ، إذا كان كل عنصر من α مجموعة جزئية من عنصر ما في ρ . بعبارة أخرى ، هذا يعني أن α تجزئة إضافية لـ ρ . في هذه الحالة، يُكتب أن α ≤ ρ .

تُعدّ علاقة "أدق من" هذه على مجموعة تجزئات X ترتيبًا جزئيًا (لذا فإنّ الرمز "≤" مناسب). لكل مجموعة من العناصر حدّ أعلى أصغر (يُسمى "الوصل") وحدّ أدنى أكبر (يُسمى "الالتقاء")، بحيث تُشكّل شبكة ، وبشكل أكثر تحديدًا (بالنسبة لتجزئات مجموعة منتهية) فهي شبكة هندسية وقابلة للحل الفائق . ^{[ 6 ] [ 7 ]} تحتوي شبكة تجزئات مجموعة من 4 عناصر على 15 عنصرًا، وهي موضحة في مخطط هاس على اليسار.

يُعرَّف التقاء وانضمام التقسيمين α و ρ على النحو التالي. الالتقاء${\displaystyle \alpha \wedge \rho }$هي التقسيم الذي تكون كتلُه عبارة عن تقاطعات بين كتلة من α وكتلة من ρ ، باستثناء المجموعة الفارغة. بعبارة أخرى، كتلة من${\displaystyle \alpha \wedge \rho }$هو تقاطع كتلة من α وكتلة من ρ غير منفصلتين عن بعضهما البعض. لتعريف الوصلة${\displaystyle \alpha \vee \rho }$، تُشكل علاقة بين الكتل A من α والكتل B من ρ بالعلاقة A ~ B إذا لم تكن A و B منفصلتين. عندئذٍ${\displaystyle \alpha \vee \rho }$هو التقسيم الذي تكون فيه كل كتلة C عبارة عن اتحاد لمجموعة من الكتل المتصلة بهذه العلاقة.

استنادًا إلى التكافؤ بين الشبكات الهندسية والماترويدات ، فإن هذه الشبكة من تجزئات مجموعة منتهية تتوافق مع ماترويد تتكون فيه المجموعة الأساسية للماترويد من ذرات الشبكة، أي التجزئات التي${\displaystyle n-2}$مجموعات أحادية ومجموعة واحدة ثنائية العناصر. تتطابق هذه التقسيمات الذرية تطابقًا تامًا مع حواف الرسم البياني الكامل . يُعدّ إغلاق الماترويد لمجموعة من التقسيمات الذرية أدقّ تقريب مشترك بينها جميعًا؛ من الناحية النظرية للرسوم البيانية، هو تقسيم رؤوس الرسم البياني الكامل إلى المكونات المتصلة للرسم البياني الفرعي المُشكّل من مجموعة الحواف المُعطاة. وبهذه الطريقة، تتطابق شبكة التقسيمات مع شبكة المستويات للماترويد الرسومي للرسم البياني الكامل.

مثال آخر يوضح تحسين التقسيمات من منظور علاقات التكافؤ. إذا كانت D هي مجموعة أوراق اللعب في مجموعة أوراق لعب قياسية مكونة من 52 ورقة، فإن علاقة "نفس اللون" على D - والتي يمكن الإشارة إليها بـ ~ _C - لها فئتان من التكافؤ: المجموعتان {الأوراق الحمراء} و{الأوراق السوداء}. التقسيم الثنائي المقابل لـ ~ _C له تحسين ينتج عنه علاقة "نفس النوع" ~ _S ، والتي لها أربع فئات من التكافؤ: {البستوني}، {الماس}، {القلوب}، و{السباتي}.

يُقال إن تجزئة المجموعة N = {1, 2, ..., n } ذات علاقة التكافؤ ~ غير متقاطعة إذا كانت تتمتع بالخاصية التالية: إذا كانت أربعة عناصر a و b و c و d من N، حيث a < b < c < d، تحقق الشرطين a ~ c و b ~ d ، فإن a ~ b ~ c ~ d . ويُشتق الاسم من التعريف المكافئ التالي: تخيل العناصر 1، 2، ...، n من N ممثلةً برؤوس n لمضلع منتظم ذي n ضلع (بترتيب عكس عقارب الساعة). يمكن تصور التجزئة برسم كل مربع كمضلع (رؤوسه هي عناصر المربع). وتكون التجزئة غير متقاطعة إذا وفقط إذا لم تتقاطع هذه المضلعات.

تشكل شبكة التقسيمات غير المتقاطعة لمجموعة محدودة مجموعة فرعية من شبكة جميع التقسيمات، ولكنها ليست شبكة فرعية، لأن عمليات الربط بين الشبكتين لا تتفق.

اكتسبت شبكة التقسيم غير المتقاطعة أهمية بسبب دورها في نظرية الاحتمالات الحرة .

العدد الإجمالي لتقسيمات مجموعة مكونة من _n عنصرًا هو عدد بيل Bₙ _. أعداد بيل الأولى هي B₀ = 1، _B₁ = ₁ ، B₂ = 2، B₃ ₌ 5، B₄ = 15 ، B₅ = 52، و _B₆ = 203 ₍ المتتالية A000110 في OEIS ) . تحقق أعداد بيل العلاقة التكرارية التالية _:

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}}$

ولها دالة توليد أسية

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}.}$

يمكن أيضًا حساب أعداد بيل باستخدام مثلث بيل ، حيث تُنسخ القيمة الأولى في كل صف من نهاية الصف السابق، وتُحسب القيم اللاحقة بجمع عددين: العدد الموجود على يسار الموضع والعدد الموجود أعلى يساره. تتكرر أعداد بيل على جانبي هذا المثلث. تُشير الأرقام داخل المثلث إلى عدد الأقسام التي يكون فيها عنصر معين هو أكبر عنصر منفرد .

عدد تقسيمات مجموعة مكونة من n عنصر إلى k جزء (غير فارغة) بالضبط هو عدد ستيرلينغ من النوع الثاني S ( n , k ).

عدد التقسيمات غير المتقاطعة لمجموعة مكونة من n عنصرًا هو عدد كاتالان

${\displaystyle C_{n}={1 \over n+1}{2n \choose n}.}$

• الغلاف الأصلي
• تصميم الكتلة
• تحليل التجميع
• قائمة مواضيع التقسيم
• التغليف (الطوبولوجيا)
• مبدأ MECE
• علاقة التكافؤ الجزئي
• جبر التقسيم
• تحسين التقسيم
• مجموعة منتهية نقطيًا
• أنماط القافية حسب تقسيم المجموعة
• الترتيب الضعيف (تقسيم المجموعة المرتبة)

• بروالدي، ريتشارد أ. (2004). مدخل إلى التوافقية (  الطبعة الرابعة). بيرسون برنتيس هول. ISBN 0-13-100119-1.
• شيشتر، إريك (1997). دليل التحليل وأسسه . دار النشر الأكاديمية. رقم ISBN 0-12-622760-8.