افراز مجموعه

افراز بر روی دایره

در نظریه مجموعه‌ها اِفراز یک مجموعه (پارتیشن‌بندی یک مجموعه) الگو:به انگلیسی یعنی تبدیل کردن آن به زیرمجموعه‌هایش به طوری که، اشتراک هر کدام از آن زیرمجموعه‌ها با یکدیگر مجموعه تهی باشد (مجموعه‌های مجزا) و اجتماع تمامی زیر مجموعه‌ها برابر با مجموعه افراز شده باشد.

تعریف

فرض کنید $X$ مجموعه‌ای غیرتهی باشد. منظور از یک افراز $X$ مانند $𝒫$، یک مجموعه از زیرمجموعه‌های ناتهی $X$ است($𝒫\in \mathbb{P}(X)$) به قسمی که:

• اگر $B,A\in 𝒫$ و $A\ne B$، آنگاه $A\cap B=\varnothing$.
• $\bigcup _{C\in 𝒫}=X$

به تعبیر شهودی افراز $X$، یک «تقسیم $X$» به قطعه‌هایی مجزا و ناتهی است.

مثال

مجموعه‌های $P=\{\{1,5\},\{2,4,6\},\{8,9\}\}$ افراز مجموعهٔ $M=\{1,2,4,5,6,8,9\}$ می‌باشند، اما برای $\{1,2,3,4,5,6,7,8,9\}$ افراز درستی نیستند، زیرا ۳ و ۷ عضوی از زیرمجموعه‌های موجود در $P$ نیستند. $\{\{1,2\},\{2,3\}\}$ افرازی از هیچ مجموعه‌ای نمی‌باشند، چون {1,2} و {2,3} مجموعه‌هایی مجزا نیستند.

افرازهای {1, 2, 3} :

• $\left\{\{1,2,3\}\right\}$
• $\{\{1,2\},\left\{3\right\}\}$
• $\{\left\{1\right\},\{2,3\}\}$
• $\{\{1,3\},\left\{2\right\}\}$
• $\{\left\{1\right\},\left\{2\right\},\left\{3\right\}\}$

افراز مجموعهٔ تهی، تنها خود مجموعهٔ تهی است.

تعداد افرازهای یک مجموعهٔ متناهی

برای یافتن تعداد افرازهای یک مجموعهٔ متناهی از عدد بل $B_n$ (به یاد اریک تمپل بل) استفاده می‌شود :

$B_0=1,B_1=1,B_2=2,B_3=5,B_4=15,B_5=52,B_6=203,\dots$