مقدمه
در نظریه مجموعه‌ها، معمولاً فقط با اعضای یک مجموعه سروکار نداریم؛ گاهی لازم است خودِ زیرمجموعه‌های یک مجموعه را نیز به‌عنوان اعضای یک مجموعه جدید در نظر بگیریم. مجموعه‌ای که همه زیرمجموعه‌های یک مجموعه را شامل می‌شود، مجموعه توانی نام دارد.
برای مثال، اگر مجموعه‌ای شامل سه عضو باشد، فقط با همان سه عضو سروکار نداریم؛ زیرمجموعه‌های تک‌عضوی، دو عضوی، مجموعه تهی و خود مجموعه نیز همگی در مجموعه توانی آن قرار می‌گیرند. به همین دلیل، مجموعه توانی یکی از مفاهیم بنیادی در نظریه مجموعه‌ها، ترکیبیات، احتمال و بسیاری از شاخه‌های ریاضیات گسسته است.
نکته مهم این است که مجموعه توانی با توان عددی اشتباه گرفته نشود. نمادگذاری آن معمولاً به‌صورت \(\mathcal{P}(A)\) است و به مجموعه‌ای اشاره می‌کند که اعضای آن، زیرمجموعه‌های \(A\) هستند.
پیش‌نیازها
برای درک مجموعه توانی، آشنایی با مفهوم مجموعه، عضو مجموعه و زیرمجموعه کافی است. اگر \(B\) زیرمجموعه \(A\) باشد، می‌نویسیم:
\[ B\subseteq A \]
این نماد یعنی هر عضوی که در \(B\) قرار دارد، در \(A\) نیز وجود دارد.
برای مثال، اگر:
\[ A=\{1,2,3\} \]
آنگاه مجموعه‌های \(\varnothing\)، \(\{1\}\)، \(\{2,3\}\) و خود \(A\)، همگی زیرمجموعه \(A\) هستند.
تعریف دقیق مجموعه توانی
مجموعه توانی یک مجموعه \(A\)، مجموعه‌ای شامل تمام زیرمجموعه‌های \(A\) است. آن را با \(\mathcal{P}(A)\) نمایش می‌دهند:
\[ \mathcal{P}(A)=\{B\mid B\subseteq A\} \]
در این تعریف، متغیر \(B\) یک مجموعه است و شرط \(B\subseteq A\) مشخص می‌کند که فقط زیرمجموعه‌های \(A\) در مجموعه توانی قرار بگیرند.
بنابراین تفاوت مهمی میان \(x\in A\) و \(B\in\mathcal{P}(A)\) وجود دارد. در حالت دوم، \(B\) یک زیرمجموعه از \(A\) است و به‌عنوان یک عضو مجموعه توانی در نظر گرفته می‌شود.
مثال ساده از مجموعه توانی
فرض کنید:
\[ A=\{1,2\} \]
تمام زیرمجموعه‌های \(A\) عبارت‌اند از:
- \(\varnothing\)
- \(\{1\}\)
- \(\{2\}\)
- \(\{1,2\}\)
پس مجموعه توانی برابر است با:
\[ \mathcal{P}(A)=\{\varnothing,\{1\},\{2\},\{1,2\}\} \]
دقت کنید که اعضای \(\mathcal{P}(A)\) خودشان مجموعه هستند. برای نمونه، \(\{1\}\) یک عضو از \(\mathcal{P}(A)\) است، در حالی که عدد \(1\) عضو \(\mathcal{P}(A)\) نیست.
چگونه مجموعه توانی را تشکیل دهیم؟
برای تشکیل مجموعه توانی یک مجموعه متناهی، باید همه زیرمجموعه‌های آن را پیدا کنیم. زیرمجموعه‌ها را می‌توان بر اساس تعداد اعضا دسته‌بندی کرد:
- زیرمجموعه با صفر عضو: \(\varnothing\)
- زیرمجموعه‌های یک‌عضوی
- زیرمجموعه‌های دو عضوی
- و به همین ترتیب
- خود مجموعه به‌عنوان زیرمجموعه‌ای با بیشترین تعداد عضو
برای مثال، اگر:
\[ A=\{a,b,c\} \]
زیرمجموعه‌ها عبارت‌اند از:
\[ \mathcal{P}(A)= \{ \varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \} \]
بنابراین:
\[ |\mathcal{P}(A)|=8 \]
فرمول تعداد اعضای مجموعه توانی
اگر \(A\) یک مجموعه متناهی با \(n\) عضو باشد، تعداد اعضای مجموعه توانی آن برابر است با:
\[ |\mathcal{P}(A)|=2^n \]
این یکی از مهم‌ترین روابط مربوط به مجموعه توانی است.
چرا \(2^n\)؟
برای ساختن یک زیرمجموعه از \(A\)، درباره هر عضو فقط دو انتخاب داریم: یا آن عضو را در زیرمجموعه قرار می‌دهیم یا قرار نمی‌دهیم.
اگر \(A\) دارای \(n\) عضو باشد، برای هر یک از این \(n\) عضو دو انتخاب مستقل وجود دارد. بنابراین تعداد حالت‌های ممکن برابر است با:
\[ \underbrace{2\times2\times\cdots\times2}_{n\text{ بار}}=2^n \]
هر یک از این حالت‌ها دقیقاً یک زیرمجموعه متفاوت ایجاد می‌کند؛ بنابراین تعداد زیرمجموعه‌ها و در نتیجه تعداد اعضای مجموعه توانی \(2^n\) است.
اثبات فرمول \( |\mathcal{P}(A)|=2^n \)
می‌توان این رابطه را با استقرا نیز اثبات کرد.
برای مجموعه تهی داریم:
\[ A=\varnothing \]
تنها زیرمجموعه آن، خود مجموعه تهی است؛ بنابراین:
\[ \mathcal{P}(\varnothing)=\{\varnothing\} \]
و در نتیجه:
\[ |\mathcal{P}(\varnothing)|=1=2^0 \]
حال فرض کنید هر مجموعه \(n\) عضوی دارای \(2^n\) زیرمجموعه باشد. مجموعه‌ای با \(n+1\) عضو را در نظر بگیرید و یکی از اعضای آن را \(a\) بنامید. هر زیرمجموعه یا \(a\) را دارد یا ندارد.
زیرمجموعه‌هایی که \(a\) را ندارند، \(2^n\) حالت دارند و برای هر زیرمجموعه‌ای که \(a\) را ندارد، با افزودن \(a\) یک زیرمجموعه جدید به دست می‌آید. بنابراین تعداد کل زیرمجموعه‌ها برابر است با:
\[ 2^n+2^n=2^{n+1} \]
پس رابطه برای همه مجموعه‌های متناهی برقرار است.
مجموعه توانی مجموعه تهی
یکی از مهم‌ترین مواردی که ممکن است باعث اشتباه شود، مجموعه توانی مجموعه تهی است. چون \(\varnothing\) هیچ عضوی ندارد، برخی تصور می‌کنند مجموعه توانی آن نیز تهی است؛ اما این تصور نادرست است.
مجموعه تهی زیرمجموعه خودش است:
\[ \varnothing\subseteq\varnothing \]
بنابراین:
\[ \mathcal{P}(\varnothing)=\{\varnothing\} \]
در نتیجه:
\[ |\mathcal{P}(\varnothing)|=1 \]
باید بین \(\varnothing\) و \(\{\varnothing\}\) دقت زیادی داشت. اولی مجموعه‌ای بدون عضو است، اما دومی مجموعه‌ای است که یک عضو دارد و آن عضو، مجموعه تهی است.
خواص مهم مجموعه توانی
۱. مجموعه تهی همیشه عضو مجموعه توانی است
برای هر مجموعه \(A\):
\[ \varnothing\subseteq A \]
بنابراین:
\[ \varnothing\in\mathcal{P}(A) \]
۲. خود مجموعه همیشه عضو مجموعه توانی است
هر مجموعه زیرمجموعه خودش است:
\[ A\subseteq A \]
بنابراین:
\[ A\in\mathcal{P}(A) \]
۳. هر عضو مجموعه توانی، زیرمجموعه مجموعه اصلی است
از تعریف مجموعه توانی مستقیماً نتیجه می‌شود:
\[ B\in\mathcal{P}(A)\iff B\subseteq A \]
این رابطه یکی از مهم‌ترین روش‌های تشخیص عضویت در مجموعه توانی است.
۴. مجموعه توانی خودش یک مجموعه است
اگر \(A\) یک مجموعه باشد، \(\mathcal{P}(A)\) نیز مجموعه‌ای است که اعضای آن زیرمجموعه‌های \(A\) هستند. در نتیجه ممکن است یک مجموعه، اعضایی داشته باشد که خودشان مجموعه باشند.
۵. رابطه زیرمجموعه‌ای میان مجموعه‌های توانی
اگر:
\[ A\subseteq B \]
آنگاه هر زیرمجموعه‌ای از \(A\)، زیرمجموعه‌ای از \(B\) نیز هست. بنابراین:
\[ \mathcal{P}(A)\subseteq\mathcal{P}(B) \]
اگر \(A\subsetneq B\)، آنگاه در حالت معمول مجموعه‌های متناهی نیز:
\[ \mathcal{P}(A)\subsetneq\mathcal{P}(B) \]
رابطه مجموعه توانی با تعداد زیرمجموعه‌ها
مجموعه توانی در واقع روش رسمی برای جمع‌آوری تمام زیرمجموعه‌های یک مجموعه است. بنابراین سؤال «یک مجموعه \(n\) عضوی چند زیرمجموعه دارد؟» دقیقاً با سؤال «مجموعه توانی آن چند عضو دارد؟» یکسان است.
برای مجموعه‌ای با \(n\) عضو:
\[ \boxed{|\mathcal{P}(A)|=2^n} \]
برای مثال، جدول زیر چند حالت ابتدایی را نشان می‌دهد:
| تعداد اعضای \(A\) |
تعداد اعضای \(\mathcal{P}(A)\) |
| \(0\) |
\(1\) |
| \(1\) |
\(2\) |
| \(2\) |
\(4\) |
| \(3\) |
\(8\) |
| \(4\) |
\(16\) |
| \(5\) |
\(32\) |
| \(10\) |
\(1024\) |
مثال‌های حل‌شده
مثال ۱: مجموعه توانی یک مجموعه دو عضوی
مجموعه زیر را در نظر بگیرید:
\[ A=\{x,y\} \]
زیرمجموعه‌های آن عبارت‌اند از:
\[ \varnothing,\{x\},\{y\},\{x,y\} \]
بنابراین:
\[ \mathcal{P}(A)=\{\varnothing,\{x\},\{y\},\{x,y\}\} \]
و چون \(A\) دو عضو دارد:
\[ |\mathcal{P}(A)|=2^2=4 \]
مثال ۲: مجموعه توانی یک مجموعه سه عضوی
اگر:
\[ A=\{1,2,3\} \]
آنگاه:
\[ \mathcal{P}(A)= \{ \varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \} \]
تعداد اعضا:
\[ |\mathcal{P}(A)|=2^3=8 \]
مثال ۳: آیا یک مجموعه عضو مجموعه توانی است؟
فرض کنید:
\[ A=\{1,2,3\} \]
آیا \(\{1,3\}\) عضو \(\mathcal{P}(A)\) است؟
برای پاسخ باید بررسی کنیم که آیا:
\[ \{1,3\}\subseteq A \]
برقرار است یا خیر. چون هر دو عضو \(1\) و \(3\) در \(A\) قرار دارند، پاسخ مثبت است:
\[ \{1,3\}\in\mathcal{P}(A) \]
مثال ۴: تشخیص یک عضو نامعتبر
اگر:
\[ A=\{1,2,3\} \]
آیا \(\{1,4\}\) عضو \(\mathcal{P}(A)\) است؟
خیر، زیرا \(4\notin A\). بنابراین:
\[ \{1,4\}\nsubseteq A \]
و در نتیجه:
\[ \{1,4\}\notin\mathcal{P}(A) \]
مثال ۵: تعداد زیرمجموعه‌ها بدون نوشتن همه آنها
مجموعه‌ای با \(8\) عضو را در نظر بگیرید. لازم نیست همه زیرمجموعه‌ها را بنویسیم. مستقیماً از فرمول استفاده می‌کنیم:
\[ |\mathcal{P}(A)|=2^8=256 \]
بنابراین مجموعه \(A\) دقیقاً \(256\) زیرمجموعه دارد.
مثال ۶: چند زیرمجموعه دقیقاً دو عضوی هستند؟
توجه کنید که مجموعه توانی شامل همه زیرمجموعه‌هاست، اما اگر فقط زیرمجموعه‌های دقیقاً دو عضوی را بخواهیم، دیگر \(2^n\) پاسخ سؤال ما نیست.
برای مجموعه‌ای با \(n\) عضو، تعداد زیرمجموعه‌های دقیقاً دو عضوی برابر است با:
\[ \binom{n}{2} \]
برای مثال، در مجموعه‌ای پنج عضوی:
\[ \binom{5}{2}=10 \]
پس \(10\) زیرمجموعه دو عضوی وجود دارد، در حالی که تعداد کل اعضای مجموعه توانی:
\[ 2^5=32 \]
مجموعه توانی و زیرمجموعه‌های با اندازه مشخص
اگر \(A\) دارای \(n\) عضو باشد، همه اعضای \(\mathcal{P}(A)\) در اندازه یکسان نیستند. برخی تهی هستند، برخی یک‌عضوی، برخی دو عضوی و در نهایت خود \(A\) دارای \(n\) عضو است.
تعداد زیرمجموعه‌های \(k\)-عضوی یک مجموعه \(n\)-عضوی برابر است با:
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!} \]
بنابراین تعداد کل اعضای مجموعه توانی را می‌توان به‌صورت زیر نیز نوشت:
\[ |\mathcal{P}(A)| = \sum_{k=0}^{n}\binom{n}{k} = 2^n \]
این رابطه با بسط دوجمله‌ای نیز سازگار است.
مجموعه توانی برای مجموعه‌های نامتناهی
فرمول \(2^n\) برای شمارش تعداد اعضای مجموعه توانی یک مجموعه متناهی به‌کار می‌رود؛ اما مفهوم مجموعه توانی محدود به مجموعه‌های متناهی نیست.
اگر \(A\) نامتناهی باشد، \(\mathcal{P}(A)\) همچنان به‌عنوان مجموعه همه زیرمجموعه‌های \(A\) تعریف می‌شود.
یکی از نتایج بنیادی نظریه مجموعه‌ها، قضیه کانتور است که می‌گوید مجموعه توانی هر مجموعه، از خود آن مجموعه از نظر تعداد اعضا بزرگتر است؛ به بیان دقیق‌تر، هیچ تابع دوسویی از \(A\) به \(\mathcal{P}(A)\) وجود ندارد.
در زبان تعدادهای اصلی:
\[ |A|<|\mathcal{P}(A)| \]
این نتیجه برای مجموعه‌های نامتناهی اهمیت بسیار زیادی دارد و نشان می‌دهد که حتی اگر یک مجموعه نامتناهی باشد، می‌توان مجموعه‌ای با اندازه‌ای بزرگتر از مجموعه توانی آن ساخت.
قضیه کانتور درباره مجموعه توانی
صورت قضیه: برای هر مجموعه \(A\)، هیچ تابع پوشا از \(A\) به \(\mathcal{P}(A)\) وجود ندارد؛ در نتیجه هیچ تناظر یک‌به‌یکی میان \(A\) و \(\mathcal{P}(A)\) برقرار نیست.
ایده اثبات: فرض کنید تابعی مانند \(f:A\to\mathcal{P}(A)\) داشته باشیم. مجموعه زیر را تعریف می‌کنیم:
\[ D=\{a\in A\mid a\notin f(a)\} \]
چون \(D\subseteq A\)، باید \(D\in\mathcal{P}(A)\) باشد. اگر \(f\) پوشا باشد، باید عضوی مانند \(d\in A\) وجود داشته باشد که:
\[ f(d)=D \]
اکنون می‌پرسیم آیا \(d\in D\) است یا خیر.
اگر \(d\in D\) باشد، طبق تعریف \(D\) باید \(d\notin f(d)=D\) باشد که تناقض است. اگر \(d\notin D\) باشد، طبق تعریف \(D\) باید \(d\in f(d)=D\) باشد که باز هم تناقض است.
پس چنین \(d\)ای وجود ندارد و \(f\) نمی‌تواند پوشا باشد. بنابراین مجموعه توانی هیچ مجموعه‌ای را نمی‌توان با خود آن مجموعه به‌صورت تناظر یک‌به‌یک شناسایی کرد.
تفاوت عضو مجموعه و زیرمجموعه در مجموعه توانی
یکی از رایج‌ترین خطاها در مبحث مجموعه توانی، اشتباه گرفتن نمادهای \(\in\) و \(\subseteq\) است.
اگر:
\[ A=\{1,2,3\} \]
آنگاه:
\[ 1\in A \]
اما:
\[ \{1\}\subseteq A \]
و از آنجا که \(\{1\}\) یک زیرمجموعه از \(A\) است:
\[ \{1\}\in\mathcal{P}(A) \]
بنابراین سه گزاره زیر از نظر معنایی متفاوت‌اند:
- \(1\in A\)
- \(\{1\}\subseteq A\)
- \(\{1\}\in\mathcal{P}(A)\)
کاربردهای مجموعه توانی
مجموعه توانی فقط یک تعریف مقدماتی در نظریه مجموعه‌ها نیست. این مفهوم در بسیاری از مباحث ریاضی و علوم کامپیوتر استفاده می‌شود.
- ترکیبیات: برای شمارش تمام انتخاب‌های ممکن از اعضای یک مجموعه.
- احتمال: در مدل‌سازی مجموعه رویدادها، مجموعه همه حالت‌های ممکن و ساختارهای مربوط به آن.
- علوم کامپیوتر: برای نمایش تمام زیرمجموعه‌های ممکن یک مجموعه، از جمله در مسائل مربوط به جست‌وجوی فضای حالت.
- نظریه مجموعه‌ها: برای مطالعه تعدادهای اصلی، مجموعه‌های نامتناهی و قضیه کانتور.
- منطق و ریاضیات گسسته: برای بیان خانواده‌های مجموعه‌ها و ساختارهای مجموعه‌ای.
اشتباهات رایج
اشتباه اول: برابر دانستن مجموعه تهی و مجموعه توانی آن
نادرست است که بنویسیم:
\[ \mathcal{P}(\varnothing)=\varnothing \]
عبارت درست این است:
\[ \mathcal{P}(\varnothing)=\{\varnothing\} \]
اشتباه دوم: فراموش کردن خود مجموعه
چون \(A\subseteq A\)، خود مجموعه \(A\) نیز یکی از اعضای \(\mathcal{P}(A)\) است.
اشتباه سوم: فراموش کردن مجموعه تهی
مجموعه تهی زیرمجموعه هر مجموعه است؛ بنابراین همیشه در مجموعه توانی حضور دارد.
اشتباه چهارم: استفاده نادرست از \(2^n\)
رابطه:
\[ |\mathcal{P}(A)|=2^n \]
زمانی به این شکل به‌عنوان یک عدد متناهی استفاده می‌شود که \(A\) متناهی و \(|A|=n\) باشد. این رابطه به این معنا نیست که هر مجموعه نامتناهی دارای دقیقاً \(2^n\) زیرمجموعه است.
اشتباه پنجم: اشتباه گرفتن \(A\) با \(\{A\}\)
اگر:
\[ A=\{1,2\} \]
آنگاه \(A\) یک مجموعه دو عضوی است، اما \(\{A\}\) مجموعه‌ای یک‌عضوی است که تنها عضو آن خود مجموعه \(A\) است.
نکات مهم
- مجموعه توانی شامل همه زیرمجموعه‌ها است، نه فقط زیرمجموعه‌های حقیقی.
- مجموعه تهی همیشه عضو مجموعه توانی است.
- خود مجموعه نیز همیشه عضو مجموعه توانی است.
- اگر \(A\) دارای \(n\) عضو باشد، \(\mathcal{P}(A)\) دارای \(2^n\) عضو است.
- اعضای مجموعه توانی، خودشان مجموعه هستند.
- \(B\in\mathcal{P}(A)\) دقیقاً معادل \(B\subseteq A\) است.
- \(\varnothing\) و \(\{\varnothing\}\) دو مجموعه متفاوت هستند.
- برای مجموعه‌های نامتناهی نیز مجموعه توانی تعریف می‌شود و قضیه کانتور اندازه آن را از اندازه مجموعه اصلی بزرگتر می‌داند.
جمع‌بندی
مجموعه توانی \(A\)، مجموعه‌ای شامل تمام زیرمجموعه‌های \(A\) است:
\[ \mathcal{P}(A)=\{B\mid B\subseteq A\} \]
دو عضو همیشگی مجموعه توانی، مجموعه تهی و خود مجموعه اصلی هستند:
\[ \varnothing\in\mathcal{P}(A) \qquad\text{و}\qquad A\in\mathcal{P}(A) \]
اگر \(A\) متناهی و دارای \(n\) عضو باشد، تعداد زیرمجموعه‌ها و در نتیجه تعداد اعضای مجموعه توانی برابر است با:
\[ \boxed{|\mathcal{P}(A)|=2^n} \]
در مجموعه‌های نامتناهی نیز مجموعه توانی وجود دارد و قضیه کانتور نشان می‌دهد که هیچ تناظر یک‌به‌یکی میان یک مجموعه و مجموعه توانی آن وجود ندارد. بنابراین مجموعه توانی یکی از مفاهیم کلیدی برای درک ساختار مجموعه‌ها، شمارش زیرمجموعه‌ها و مفهوم اندازه مجموعه‌های نامتناهی است.
موضوعات مرتبط
منابع
- Mathematics LibreTexts، Sets of sets؛ شامل تعریف مجموعه توانی، مثال‌های مجموعه توانی و بررسی مجموعه توانی مجموعه تهی.
- Mathematics LibreTexts، Subsets and Power Sets؛ شامل تعریف رسمی مجموعه توانی و مثال‌های مربوط به زیرمجموعه‌ها.
- University of Western Ontario، Discrete Structures for Computing — Sets and Set Theory؛ شامل تعریف مجموعه توانی و قضیه تعداد زیرمجموعه‌های یک مجموعه متناهی.
- University of Oxford، Introduction to University Mathematics — Sets؛ شامل اثبات رابطه \( |\mathcal{P}(A)|=2^n \) برای مجموعه‌های متناهی.
- University of Florida، Applied Discrete Structures؛ شامل تعریف مجموعه توانی و رابطه تعداد زیرمجموعه‌ها با \(2^n\).
- University of Texas at San Antonio، Sets: Definitions؛ شامل تعریف مجموعه توانی، تعداد زیرمجموعه‌های مجموعه متناهی و اشاره به قضیه کانتور.