مبانی جبر (لم زرن): ثابت کنید بین $S_X$ و $2^X$ تناظر یک به یک برقرار است.

Question

فرض کنید $X$ مجموعه ای نامتناهی و $S_X$(تمام جایگشت های $X$) مجموعه تمام توابع یک به یک و پوشا از $X$ به $X$ باشد. ثابت کنید بین مجموعه های $S_X$ و $2^X$ (دو به توان $X$) یک تناظر یک به یک برقرار است.

Comments

استاد سید احمد فقیهی آفارانی، استاد کارشناسی‌ام بودند. خیلی برایم جالب شد. ولی یک پرسش از شما دارم، مطمئن هستید ایشان در کتابشان حتما خواسته‌اند از لم زرن استفاده کنید؟ چون در متن پرسش که شما نوشته‌اید هیچ تأکیدی بر استفاده از لم زرن نیامده‌است.

---

سلام دوست عزیز بله بنده ار خود ایشون پرسیدم. لم زرن هم گویا کاربرد داره

---

@mohammad_9092
چیزی که در کتابشان خواسته اند با چیزی که خودشان به شما گفته اند فرق دارد.
@ AmirHosein
ایشان در کتابشان به عنوان راهنمایی گفته اند که از مسئله های 13 و 14 استفاده کنید. مسئله 13 مربوط به اثبات هم ارزی $P(X)$ و $2^X$ می باشد. مسئله 14 هم این مسئله می باشد (برای مسئله 14 به عنوان راهنمایی گفتن که از لم زرن استفاده کنید)
https://math.irancircle.com/17451/%D8%A7%D8%AB%D8%A8%D8%A7%D8%AA-%D8%A8%DB%8C%DA%98%DA%A9%D8%B3%DB%8C%D9%88%D9%86-%D8%A8%D9%88%D8%AF%D9%86-%D8%AA%D8%A7%D8%A8%D8%B9

---

@kazomano خود استاد فقیهی افتخار دادند و امضاشدهٔ کتابشان را به من دادند ولی متأسفانه با خودم نیاورده‌ام و در ایران است. برای همین دسترسی به آن ندارم، ولی ممنون که بررسی و اشاره کردید.

Answer 1

در زیر از لم زرن استفاده نکرده‌ام ولی یک بودن عدد اصلی این دو مجموعه را ثابت می‌کند.

ابتدا سمتی که همان روز نخست به ذهنم رسید. سر درس مبانی ریاضی اتوماتا استاد خسروی فکر کنم چنین ایده‌ای مطرح شده‌بود که به ازای هر زیرمجموعه از $X$ یک جایگشت به این شکل که اعضای انتخاب‌شده توسط آن زیرمجموعه را به خودشان ببرد و سایر اعضا را جابجا کند، نظیر کنیم. ممکن است به حالتی فکر کنید که زیرمجموعهٔ برداشته‌شده همهٔ اعضای $X$ غیر از یک عضو را داشته باشد، در آن صورت اگر همه به غیر از یکی ثابت نگه‌داسته‌شوند برای جایگشتمان تک عضو باقیمانده نیز مجبور به ثابت ماندن می‌شود. چون $X$ نامتناهی است افزودن یک عنصر خارج از $X$ به آن، عدد اصلی مجموعه را تغییر نمی‌دهد. بنابراین به جای $X$ می‌توانید از $X'=X\cup\lbrace z\rbrace$ استفاده کنید که مطمئن شوید مشکل پیشین روی نمی‌دهد و در آن حالت عضو باقیمانده را با $z$ در جایگشتمان جابجا می‌کنیم که یک ترانهشت می‌شود. برای یک زیرمجموعه (غیر از حالتی که اشاره شد) یک جایگشت یکتا با آن خاصیت وجود ندارد پس باید هر زیرمجموعه که برداشتیم خودمان یک جایگشت دلخواه با آن ویژگی را ثابت بگیریم و نظیر کنیم (چون مجموعهٔ جایگشت‌های با خاصیت خواسته‌شده -پس از افزودن عنصر اضافی- ناتهی است بنا بر اصل انتخاب این کار ممکن است). پس تا اینجا یک تابع یک‌-به-یک از $P(X)$ به $S_X$ ساختیم. این ثابت می‌کند که $|P(X)|\leq|S_X|$. باید سمت برعکس آن را نیز ثابت کنیم.

اینکه چند روز طول کشید تا سمت برعکس را انجام دهم به این دلیل بود که در ابتدا از اینکه جایگشت‌ها تابع هستند و تابع‌ها رابطه‌ هستند می‌خواستم استفاده کنم که اتفاقا مسیر اشتباهی نبود ولی در تمام این چند روز یک اشتباه بزرگ داشتم. هر عبارت از یک رابطه و در نتیجه یک جایگشت عضوی از $X\times X$ است یعنی $\tau(x)=x'$ متناظر به $(x,x')$ است ولی اشتباه اینجا بود که سپس ذهنم با بی‌دقتی خود جایگشت‌ها را عضو $X\times X$ گرفته بود که اشتباه است! بلکه یک جایگشت اجتماع عبارت‌هایش است پس نه عضو بلکه یک زیرمجموعه از $X\times X$ است. اکنون همه چیز روشن شد. $S_X\subseteq P(X\times X)$ پس $|S_X|\leq 2^{|X\times X|}$ و به یاد آورید که برای یک مجموعهٔ نامتناهی داریم که عدداصلیِ تعداد متناهی مرتبه حاصلضرب دکارتیِ آن در خودش، عدد اصلیِ یکسانی با خودش دارد. پس $|X\times X|=|X|$ و در نتیجه $2^{|X\times X|}=2^{|X|}=|P(X)|$. پس سمت مخالف نامساوی بالا ثابت شد.

$$|P(X)|=|S_X|$$

من از لم زرن استفاده نکردم ولی از آنجا که لم زرن با اصل انتخاب هم‌ارز است حدسم این است که برای قسمت $|P(X)|\leq|S_X|$ از آن باید استفاده کنید.