قضیه کانتور در نظریه مجموعه | به زبان ساده

در ریاضیات و بخصوص در نظریه اعداد، قضیه کانتور اهمیت ویژه‌ای دارد. در نوشتارهای دیگر فرادرس در مورد عدد اصلی یک مجموعه صحبت کردیم. در آنجا دیدیم که تعداد اعضای یک مجموعه متناهی توسط عدد اصلی آن مشخص می‌شود. ولی زمانی که با یک مجموعه نامتناهی (شمارا یا ناشمارا) مواجه هستیم، شمارش تعداد اعضای مجموعه امکان‌پذیر نیست و به سادگی نمی‌توان عدد اصلی یک مجموعه را مشخص کرد. قضیه کانتور در نظریه مجموعه دقیقا به همین موضوع اشاره دارد و ابزاری برای مرتب‌سازی مجموعه‌ها براساس عدد اصلی آن‌ها ارائه می‌دهد و نشان می‌دهد که چه رابطه‌ای بین عدد اصلی یک مجموعه با عدد اصلی مجموعه توانی آن برقرار است.

برای آشنایی بیشتر با نظریه مجموعه‌ها (Set Theory) و اصطلاحات به کار رفته در این متن، پیشنهاد می‌شود نوشتارهای اصل خوش ترتیبی در نظریه اعداد — به زبان ساده و نظریه اعداد و کاربردهای آن — به زبان ساده را مطالعه کنید. همچنین خواندن مطالب مجموعه متناهی و نامتناهی — به زبان ساده و اعداد طبیعی — به زبان ساده نیز خالی از لطف نیست. به این ترتیب آمادگی لازم برای درک بهتر این متن را پیدا خواهید کرد.

قضیه کانتور در نظریه مجموعه

یکی از قضیه‌های اصلی و پایه در نظریه مجموعه (Set Theory)، «قضیه کانتور» (Cantor's Theorem) است. براساس این قضیه مشخص می‌شود که «عدد اصلی» (Cardinality) برای «مجموعه توانی» (Power Set) هر مجموعه (مثل $$A$$) از عدد اصلی مجموعه $$A$$، به طور اکید بزرگتر است. در این نابرابری، بخصوص روی بزرگتر و علامت اکید، اصرار وجود دارد.

فیلم آموزش مبانی آنالیز ریاضی – جامع و کاربردی در فرادرس

کلیک کنید

این قضیه را «گئورگ کانتور» (Georg Cantor) یا به قولی «جورج کانتور»، در مقاله‌ای در سال ۱۸۹۱ منتشر و اثبات کرد. او در این مقاله نشان داد که اگر $$f$$ یک تابع روی $$X$$ باشد بطوری که مقادیر مثلا صفر و یک را بگیرید (درست مانند تابع نشانگر)، آنگاه تابع $$G(x) = 1- f(x)(x)$$ در برد تابع $$f$$ قرار نخواهد داشت. این قضیه و اثبات آن را در ادامه متن مورد بررسی دقیق‌تر قرار خواهیم داد. همچنین به خصوصیات و ویژگی‌های مربوط به تناقض‌های مطرح شده در قضیه و هم اثبات آن نیز، در این متن، اشاره‌هایی خواهیم کرد.

سال‌ها بعد از کانتور، «فدریک زرملو» (Ernst Friedrich Ferdinand Zermelo) طی مقاله‌ای با عنوان «مطالعاتی روی مبانی نظریه مجموعه» به قضیه‌ای می‌پردازد که آن را «قضیه کانتور» نام‌گذاری کرده و براساس آن، مبانی اولیه نظریه مجموعه را در سال ۱۹۰۸ منتشر کرد. او قضیه، مجموعه و تابع کانتور را بهشت ریاضیات و نظریه مجموعه‌ها نام نهاد.

نمایش یا اثبات قضیه کانتور برای مجموعه‌های متناهی به سادگی با مشخص کردن عدد اصلی مجموعه و مجموعه توانی آن، صورت می‌گیرد. کافی است عمل شمارش اعضای هر یک از این مجموعه‌ها را انجام دهیم. با توجه به اینکه مجموعه تهی نیز زیرمجموعه هر مجموعه محسوب می‌شود، عدد اصلی مجموعه توانی یک مجموعه مثل $$A$$ (با عدد اصلی $$\text{card}(A)=n$$) برابر است با $$\text{card}(P(A))=2^n$$. واضح است که برای هر مقدار نامنفی $$n$$ رابطه زیر برقرار است.

$$\large 2^n > n$$

فیلم آموزش مبانی آنالیز ریاضی – مرور و حل مساله در فرادرس

کلیک کنید

نکته: این موضوع را به کمک استقرا می‌توان اثبات کرد. البته نگاهی به تابع $$2^x$$ و مقایسه آن با $$x$$ نیز روشی دیگر برای نمایش این موضوع است. این کار در تصویر زیر صورت گرفته است. واضح است که برای مقادیر بزرگتر از صفر، همیشه منحنی $$2^x$$ که با رنگ سیاه مشخص شده از $$y=x$$ بزرگتر است.

اهمیت قضیه کانتور در این بین، نمایش این رابطه برای مجموعه‌های نامتناهی (شمارش‌پذیر یا ناشمارا) است. او توانست نشان دهد که برای مجموعه نامتناهی ولی شمارش‌پذیر اعداد طبیعی با عدد اصلی $$\aleph_0$$ و مجموعه توانی اعداد طبیعی با عدد اصلی $$c=2^{\aleph_0}$$، رابطه زیر برقرار است.

$$\large c=2^{\aleph_0} > \aleph_0$$

این موضوع نشان می‌دهد که عدد اصلی مجموعه توانی اعداد طبیعی با عدد اصلی اعداد حقیقی برابر بوده، در نتیجه مجموعه توانی اعداد طبیعی ناشمارا است. به بیان دیگر اگر $$P({\cal{N}})$$ مجموعه توانی اعداد طبیعی باشد، خواهیم داشت:

$$\large c = \text{card}({\cal{R}}) = \text{card} (P({\cal{N}}))$$

بوسیله قضیه کانتور می‌توان یک رابطه ترتیبی بین اعداد کاردینال ایجاد کرد بطوری که طبق یک «رابطه سلسله مراتبی بی‌پایان» (Endless Hierarchy of Infinite Cardinals)، هر مجموعه دارای عدد اصلی بزرگتر از مجموعه قبلی باشد. همچنین این قضیه بیان می‌کرد که بزرگترین عدد اصلی یا کاردینال وجود ندارد، همانطور که بزرگترین بی‌نهایت نیز وجود ندارد.

صورت قضیه کانتور

فرض کنید تابع $$f$$ یک نگاشت از مجموعه $$A$$ به مجموعه توانی (Power Set) باشد. آنگاه این تابع، پوشا (Surjective) نخواهد بود. به این معنی که یک تناظر یک به یک از مجموعه $$P(A)$$ با $$A$$ برقرار نخواهد شد. به عنوان نتیجه می‌توان گفت که $$\text{card}(A) < \text{card}\left( P(A) \right)$$ برای هر مجموعه‌ای مثل $$A$$ برقرار است.

اثبات قضیه کانتور

اثبات این قضیه با توجه به تعریف پوشا بودن تابع مشخص می‌شود. فرض کنید مجموعه $$B$$ به صورت اعضای از مجموعه $$A$$ تعریف شود که به برد تابع $$f$$ تعلق نداشته باشند.

$$\large B = \{x \in A | x \not\in f(x)\}$$

با فرض پوشا بودن تابع $$f$$ باید $$\xi \in A$$ وجود داشته باشد که $$f(\xi) = B$$. اما با توجه به ساختار مجموعه $$B$$ خواهیم داشت:

$$\large \xi \in B \leftrightarrow \xi \notin f(\xi) =B$$

فیلم آموزش مبانی آنالیز ریاضی – مرور، حل مثال و تست کنکور ارشد – بخش یکم در فرادرس

کلیک کنید

که این تناقض ایجاد کرده در نتیجه تابع $$f$$ نمی‌تواند پوشا باشد. از طرفی فرض کنید که تابع $$g$$ یک نگاشت یک به یک (Injective) از $$A$$ به $$P(A)$$ به صورت زیر باشد.

$$\large g: A \rightarrow P(A) : x \rightarrowtail\{x\}$$

به این ترتیب باید داشته باشیم:

$$\large \text{card}(A) < \text{card}P(A))$$

در تصویر زیر یک رابطه سلسله مراتبی برای مجموعه‌ای براساس سه عضو ($$A = \{ x , y , z \}$$) ایجاد شده است. هر سطر از این رابطه سلسله مراتبی، زیرمجموعه‌هایی از مجموعه اصلی را مشخص کرده است که براساس تعداد اعضایشان در یک سطر دیده می‌شوند. برای مثال در سطر اول از پایین، مجموعه تهی (با عدد اصلی صفر) قرار گرفته و در سطر دوم نیز زیرمجموعه‌های تک عضوی با عدد اصلی برابر با ۱ دیده می‌شوند. همچنین زیرمجموعه‌هایی دو عضوی و سه عضوی نیز در بالای این نمودار قرار می‌گیرند. مشخص است که اگر نمودار را از پایین به بالا، در نظر بگیریم، عدد اصلی سطرها به صورت افزایشی بوده و مقدار هر سطر از سطر زیرین بیشتر است. در نهایت نیز عدد اصلی مجموعه اصلی، قرار گرفته است.

توضیحاتی در مورد اثبات قضیه کانتور

براساس تعریف عدد اصلی، اگر یک تابع یک به یک (و نه معکوس پذیر) بین دو مجموعه $$X$$ و $$Y$$ وجود داشته باشد، آنگاه $$\text{card}(X) < \text{card}(Y)$$ است و برعکس. به این ترتیب کافی است نشان دهیم تابعی پوشا بین این دو مجموعه نمی‌توان با شرایط گفته شده، پیدا کرد.

به این ترتیب اثبات با این هدف انجام می‌شود که هیچ نگاشتی از عناصر $$A$$ به زیرمجموعه‌های $$A$$ وجود ندارد که به صورت تابع $$f$$ بیان شود. پس کافی است نشان دهید که یک زیرمجموعه از  $$A$$ (مثل $$x$$) وجود دارد که تحت تابع $$f$$ برای هر $$x \in A$$ با $$f(x)$$ برابر نیست.

نکته: در اینجا فرض کنید تابع $$f(x)$$ هر یک از زیرمجموعه‌های $$A$$ را می‌سازد. این ساختار به «مجموعه قطری کانتور تابع $$f$$» یا (Cantor diagonal set of f) نیز مشهور است.

به این ترتیب برای هر $$x \in A$$، می‌توان $$x \in B$$ در نظر گرفت به شرطی که $$x \not\in f(x)$$ و برعکس. برای هر $$x$$، مجموعه‌های $$B$$ و $$f(x)$$ نمی‌توانند برابر باشند، زیرا $$B$$ براساس عناصر از $$A$$ تشکیل شده که تصویر آن‌ها (تحت تابع $$f$$) با مقدار خودشان برابر نیست.

از طرفی می‌توان $$x \in A$$ را به شکلی در نظر گرفت که یا $$x \in f(x)$$ یا خارج از آن است ($$x \not \in f(x)$$). در حالت اول، $$f(x)$$ نمی‌تواند برابر با $$B$$ باشد زیرا $$x \in f(x)$$ بوده و براساس ساختار مجموعه $$B$$ داریم، $$x \not \in B$$. در حالت دوم نیز $$f(x)$$ برابر با $$B$$ نیست، زیرا $$x \not \in f(x)$$ براساس فرض است و براساس ساختار مجموعه $$B$$ خواهیم داشت $$x \in B$$.

به این ترتیب با استفاده از «برهان خلف» (reductio ad absurdum)، فرض اولیه باید نادرست باشد. به علاوه هیچ $$\xi \in A$$ وجود ندارد که $$f(\xi) = B$$. به بیان دیگر $$B$$، تصویر $$f$$ نیست و $$f$$ نگاشتی از عناصر مجموعه توانی $$A$$ نخواهد بود. در نتیجه $$f$$ یک تابع پوشا نیست.

در نهایت برای اتمام قضیه، باید یک تابع یک به یک از $$A$$ به مجموعه توانی معرفی کنیم. چنین تابعی می‌تواند به صورت نگاشتی از $$x$$ به $$\{x\}$$ یعنی مجموعه تک عضوی از $$x$$ باشد.

قضیه کانتور برای مجموعه‌های نامتناهی شمارش‌پذیر

این بار می‌خواهیم به واسطه یک مجموعه نامتناهی ولی شمارش‌پذیر، اثبات را مورد بررسی قرار دهیم. بدون آنکه کلیت اثبات لطمه‌ای بخورد، فرض کنید که مجموعه $$A$$، همان مجموعه اعداد طبیعی باشد.

$$\large  A = { \cal{N} } = \{ 1 , 2 , \ldots \}$$

فیلم آموزش مبانی منطق و نظریه مجموعه ها در فرادرس

کلیک کنید

همچنین در نظر بگیرید که این مجموعه با مجموعه توانی خود یعنی $$P({\cal{N}})$$ هم‌شمارا (Equinumerous) باشد. بهتر است ابتدا نگاهی به این مجموعه توانی بیاندازیم.

$$\large { \displaystyle { \mathcal {P} }( \mathbb {N} ) = \{ \varnothing , \{ 1 , 2 \} , \{ 1 , 2 , 3 \} , \{ 4 \} , \{ 1 , 5 \},\{ 3 , 4 , 6 \},\{ 2, 4 , 6 , \dots \}, \dots \}}$$

مشخص است که مجموعه توانی شامل بی‌نهایت زیرمجموعه از $${\cal{N}}$$ است. به این ترتیب نمایشی از اعضای مجموعه توانی اعداد طبیعی حاصل می‌شود. حال سعی می‌کنیم بتوانیم یک تناظر بین مجموعه توانی و اعداد طبیعی پیدا کنیم. این کار باید به شکلی صورت گیرد که هیچ یک از اعضای مجموعه توانی بدون عضوی مرتبط از مجموعه اعداد طبیعی باقی نماند. برای مثال ممکن است این تناظر به صورت زیر برقرار شده باشد.

$$\large { \displaystyle \mathbb {N} { \begin{Bmatrix} 1 & \longleftrightarrow & \{ 4 , 5 \} \\ 2 & \longleftrightarrow & \{ 1 , 2 , 3 \} \\ 3 & \longleftrightarrow & \{ 4 , 5 , 6 \} \\ 4 & \longleftrightarrow & \{ 1 , 3 , 5 \} \\ \vdots & \vdots & \vdots \end{Bmatrix}}{ \mathcal {P}}( \mathbb {N} ) }$$

اینطور به نظر می‌رسد که در بعضی از اعضای این نگاشت، یک عدد طبیعی با مجموعه‌ای که شامل آن عدد است مرتبط شده است. مثلا $$2$$ با مجموعه $$\{1, 2, 3 \}$$ ارتباط دارد. برای تنوع به این اعداد در تناظر یاد شده، «اعداد خودخواه» (Selfish Numbers) یا اعداد خودبین، می‌گوییم. به این ترتیب عدد ۲ در رابطه ذکر شده، یک عدد خودخواه است زیرا با عضوی از مجموعه توانی در تناظر است که شامل عدد می‌باشد. در عوض عدد ۱ یا ۳، خودخواه نیستند زیرا در تناظر با مجموعه‌ای هستند که شامل این اعداد نیست. این اعداد را هم «غیرخودخواه» (non-selfish) یا ایثارگر می‌نامیم.

براساس این ایده برای تقسیم اعداد طبیعی در تناظر، تناقضی که به دنبالش بودیم را ایجاد خواهیم کرد. فرض کنید $$B$$ مجموعه‌ای از همه اعداد ایثارگر در اعداد طبیعی است. براساس تعریف مجموعه توانی، $$P({\cal{N}})$$ شامل همه مجموعه‌های حاصل از اعداد طبیعی است بخصوص $$B$$ نیز یکی از اعضای مجموعه توانی خواهد بود.

اگر نگاشت یا تناظر یاد شده، پوشا (surjective) باشد، مجموعه $$B$$ باید شامل یک مقدار باشد که دارای تناظر با یک عضو از مجموعه اعداد طبیعی مثلا $$b$$ باشد. البته این امر مشکل‌ساز است. اگر $$b$$ در $$B$$ بوده و یک عدد خودخواه باشد، با تعریف مجموعه $$B$$ دچار تناقض می‌شود. اگر $$b$$ در $$B$$ نباشد، آنگاه یک عدد ایثارگر است و باید عضوی از مجموعه $$B$$ باشد. در نتیجه هیچ عنصری مانند $$b$$ وجود ندارد که حاصل نگاشت از $$B$$ باشد.

توجه داشته باشید که هیچ عدد طبیعی وجود ندارد که بتواند با $$B$$ تشکیل یک زوج در تناظر بدهد. این موضوع همان فرض وجود تناظر پوشا بین اعداد طبیعی و مجموعه توانی آن را لغو می‌کند.

به این امر هم توجه کنید که ممکن است مجموعه $$B$$، تهی باشد که به معنی آن است که هر عدد طبیعی $$x$$ به یک زیرمجموعه از اعدادی طبیعی شامل $$x$$ نگاشت می‌شود. یعنی همه اعداد به یک مجموعه ناتهی نگاشت شده و هیچ عددی با مجموعه تهی، نگاشت نمی‌شود. از طرفی مجموعه تهی، یک زیرمجموعه از مجموعه اصلی است و در مجموعه توانی حضور دارد. در نتیجه باز هم نگاشت معرفی شده نمی‌تواند تمام مجموعه توانی $$P({\cal{N}})$$ را بپوشاند.

در روند اثبات این قضیه، اثبات کردیم که عدد اصلی مجموعه اعداد طبیعی هرگز با عدد اصلی مجموعه توانی آن برابر نیست. همچنین از قبل می‌دانستیم که عدد اصلی مجموعه توانی هیچگاه از عدد اصلی خود مجموعه کوچکتر نیست، زیرا مجموعه توانی شامل مجموعه‌های تک عضوی از مجموعه اصلی نیز هست. در نهایت تنها حالتی که برای نمایش رابطه بین اعداد اصلی این دو مجموعه باقی می‌ماند، بزرگتر بودن اکید عدد اصلی مجموعه توانی از عدد اصلی مجموعه اعداد طبیعی است.

از آنجایی که بین هر مجموعه نامتناهی شمارا و اعداد طبیعی، یک تناظر یک به یک وجود دارد، قضیه یاد شده برای هر مجموعه نامتناهی شمارا، به همین شیوه قابل اثبات است.

تناقض‌های مرتبط با قضیه کانتور

قضیه کانتور و اثبات آن، رابطه بسیار نزدیکی با دو تناقض در نظریه مجموعه دارد. ابتدا به تناقض کانتور اشاره می‌کنیم که به همراه قضیه کانتور به بررسی «مجموعه جهانی» (Universal Set) یا مجموعه مرجع ($$V$$) می‌پردازد.

قضیه کانتور بیان می‌داد که تعداد اعضای یا عدد اصلی مجموعه توانی $$X$$ از عدد اصلی خود مجموعه $$X$$، بزرگتر است.

$$\large | P(X) | > | X |$$

از طرفی همه عناصر مجموعه توانی $$P(V)$$، مجموعه محسوب می‌شوند که البته یکی از اعضای $$V$$ نیز خواهد بود. در نتیجه:

$$\large | P(V) \leq |V|$$

که امری متناقض به نظر می‌رسد.

فیلم مجموعه آموزش ریاضیات – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

تناقض بعدی از اثبات کانتور استخراج می‌شود. فرض کنید تابع $$f$$ که برای اثبات قضیه کانتور به کار رفت، «تابع همانی» (Identity Function) باشد. در این صورت عناصر قطری مجموعه کانتور، به مجموعه راسل (Russell Set) برای مجموعه $$A$$ تبدیل می‌شوند.

$$\large R_{A} = \left\{ \, x \in A : x \not \in x \, \right \}$$

اثبات قضیه کانتور با در نظر گرفتن اینکه مجموعه مرجع یا مجموعه همه مجموعه‌ها ($$U$$) وجود دارد صورت گرفته و در نتیجه برای مجموعه $$R_U$$ منجر به تناقض می‌شود.

$$\large R_{U}\in R_{U}\iff R_{U} \notin R_{U}$$

به این تناقض، «پارادوکس راسل» (Russell's Paradox) نیز گفته می‌شود.

$$\large R_{U}\in R_{U}\iff (R_{U}\in U\wedge R_{U}\notin R_{U})$$

خلاصه و جمع‌بندی

قضیه کانتور راه را برای بسیار از نظریه‌های دیگر در حوزه ریاضیات و مجموعه‌ها باز کرد. به همین علت نیز در این نوشتار به این قضیه پرداخته و جوانب مختلف آن را مورد بررسی قرار دادیم. واضح است که تصور مجموعه‌هایی که نامتناهی عضو داشته باشند، به راحتی میسر نیست ولی ذهن خلاق ریاضیدان و دانشمند بزرگ آلمانی-روسی «گئورگ کانتور» یا به قولی «جورج کانتور» توانست این محدودیت‌ها را کنار زده و پنجره‌ای به سوی بی‌نهایت باز کند.