مجموعه‌های متناهی، نامتناهی، شمارا و ناشمارا

■ داستانک

روزی روزگاری در گذشته یا همین حالا یا در آیندها در یکی از بیشمار جهان‌ها در شهر سایه‌های بی‌صاحب که ساکنانش نامیرا بودند؛ فرد آ به فرد ب گفت من عددی طبیعی و بزرگتر از صفر را (n∈⁺) را روی کاغذی می‌نویسم و تو هر روز یک و فقط یک بار آن را گمانه‌زنی کن و بگو. اگر گمانه تو درست بود من به تو به اندازه شمار کوه طلا جایزه می‌دهم. آیا روند کارآمدی هست که اجرای آن فرد ب را به جایزه برسد؟

برگرفته از: اسمولین۱

■ مجموعه‌های متناهی و نامتناهی (Finite and infinite sets)

g : ↦ E;									تعریف تابع g
.	.	.	۵	۴	۳	۲	۱	۰	x∈
.	.	.	۱۰	۸	۶	۴	۲	۰	g(x)∈
g(x)=۲x
تابع g یک تناظر ۱:۱ بین اعداد طبیعی و زیرمجموعه سره‌ای از آن، یعنی اعداد زوج، برقرار می‌کند.

ازآنجاکه، برای هر n∈ نظیر آن، ۲n، در E و نیز برای هر عضو e∈E نظیر آن، _۲/e، در وجود دارد، نگاشت g دو سویی است، یعنی بین و یک زیرمجموعه سره آن، در این مثال E، تناظر ۱:۱ وجود دارد و می‌توان نوشت: ⇌E. به‌عبارت‌دیگر، اعضای با اعضای زیرمجموعه سره‌ای از آن جفت شدنی است و این در حالی است که عضوهایی در هست که در E نیست. به گونه دیگر، به‌عنوان یک کل با جزئی از خود هم‌اندازه است. این ویژگی را نامتناهی بودن نامیده. اگر برای مجموعه‌ای چنین زیرمجموعه‌ای وجود نداشته باشد آنگاه آن مجموعه متناهی است.

■ مجموعه نامتناهی (infinite set)

یک مجموعه را مجموعه نامتناهی گوییم اگر بین آن و زیرمجموعه سره‌ای از آن، یک تناظر یک‌به‌یک وجود داشته باشد. به مجموعه‌ای که نامتناهی نیست مجموعه متناهی می‌گویند.

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

☚ یک مجموعه، به فرض X، نامتناهی‌ است اگر یک تابع یک ‌به‌ یک ولی نه پوشا از X در خودش وجود داشته باشد. برای مثال، f(x)=۲x در .

☚ متمم زیرمجموعه‌های متناهی نامتناهی‌اند ولی عکس آن همیشه درست نیست.

■ شمارایی و کاردینال

می‌توان به هر مجموعه متناهی عددی که به‌اندازه تعداد اعضای آن مجموعه باشد را نسبت داد و آن‌ها را مقایسه پذیر نمود. آیا مجموعه‌های نامتناهی نیز مقایسه پذیراند؟ هدف این بند نشان ‌دادن این است که چگونه ریاضیدانان مفهوم مقایسه پذیری را گسترانده تا به‌طور عام برای مجموعه‌ها، متناهی و نامتناهی، کار زدنی باشد.

داستان از شمارایی [شمارش‌پذیری] مجموعه‌ها آغاز می‌شود. به‌طور شهودی، مجموعه‌ای شمارا است که بتوان اعضای آن‌ را توسط اعداد طبیعی فهرست کرد (برشمرد). البته همان‌طور که خواهیم دید مجموعه‌هایی نیز هستند که شمارا نیستند و اعضای آن‌ها را نمی‌توان برشمرد. شمارایی رهنمود ما به مفهوم بی‌نهایت(‌ها) [اعداد نامتناهی / اعداد بی‌نهایت] و حساب آن‌ها خواهد بود. بنابراین اینک تعریف دقیق شمارایی یک مجموعه را مرور می‌کنیم.

■ مجموعه شمارا

مجموعه S را یک مجموعه شمارا [یا شمارش پذیر] گویند اگر و فقط اگر

اگر چنین تابعی، به فرض f، باشد، آنگاه می‌گوییم تابع S ،f را برمی‌شمرد [برشمردن]. در غیر این صورت می‌گوییم S یک مجموعه ناشمارا است [برشمردنی نیست].

■ شمارایی اعداد گویا

در جدول زیر اعداد گویای مثبت فهرست شده‌اند (برشمرده شده‌اند). این نشان می‌دهد ⁺ شمارا است (به همین ترتیب شمارا است و با توجه به ⊂ نامتناهی نیز است).

نمودار بالا که نشان‌دهنده شمارش‌پذیری اعداد گویا است، هم‌چنین نشان می‌دهد مجموعه × شمارا است و می‌توان نشان داد که مجموعه همه nتایی‌های‌ مرتب اعداد طبیعی نیز شمارایند.

■ چند خاصیت درباره مجموعه‌های شمارا

■ نامحدود مجموعه ناشمارا و نامتناهی وجود دارد.

اثبات:

ابتدا ثابت می‌کنیم مجموعه توانی ، یعنی Ƥ() ناشمارا و نامتناهی است.

Ƥ() را Pº می‌نامیم (به خاطر راحتی در نوشتن).

روشن است Pº نامتناهی است و بنابراین فقط ثابت می‌کنیم Pº ناشمارا است.

(توجه داریم که X∈Pº اگر و فقط اگر X⊆.)

۱- می‌گوییم، گیریم تابع f : ↦Pº وجود دارد به قسمی که Pº را بر‌می‌شمارد (یعنی Pº شمارا است.)

پس برای هر عضو Pº مانند X عدد طبیعی n هست به قسمی که: f(n)∈X.

۲- مجموعه D (D⊆ ) را به قسمی می‌گیریم که n∈D اگر و فقط اگر n∉f(n).

۳- اما ازآنجاکه D∈Pº (چون D⊆) و طبق فرض(خلف) f همه

اعضای Pº را برمی‌شمرد پس باید عددی طبیعی مانند d باشد کهf(d)=D.

۴- اما با توجه به ۲ برای هر n∈f(d) ؛n اگر و فقط اگر n∉f(n). و بنابراین به‌ویژه d∈f(d) اگر و فقط اگر d∉f(d)، که این، یک تناقض و لذا فرض خلف باطل است. بنابراین Pº شمارا نیست و همین‌طور است برای Ƥ(Ƥº) و ادامه آن.