لم زرن

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

لم زرن یکی از مفیدترین اصولی است که هم ارز اصل انتخاب است، اصلی است که اولین بار در سال ۱۹۱۴ مطرح شد و به نام لم زرن معروف است، لم زرن به صورت زیر مطرح می‌شود: اگر (A \le) یک مجموعه مرتب جزیی باشد، بطوریکه هر زیر مجموعه کاملا مرتب آن، دارای کران بالا باشد، آنگاه A دارای عضو ماکزیمال است.

اثبات[ویرایش]

با توجه به اصل ماکزیمالی هاسدورف، (A \le) دارای زیر مجموعه کاملا مرتبی مانند B است که نسبت به رابطه شمول \subseteq ماکزیمال است. بنا به فرض، Bدارای یک کران بالا به نام u است. نشان می‌دهیم که u یک عضو ماکزیمال از A است.اگر عضوی مانند x\in A وجود داشته باشد، بطوریکه x\ge u، آنگاه  B\bigcup \lbrace{x}\rbrace، زیر مجموعه کاملا مرتبی از Aاست که شامل زیر مجموعه ماکزیمال کاملا مرتب B می‌باشد. در نتیجه می‌بایست B\bigcup \lbrace{x}\rbrace=B باشد که نتیجه می‌دهد x\le u. این ثابت می‌کند که u عضو ماکزیمال مجموعه (A \le) است.

لم فوق نمونه‌ای از یک خاصیت وجودی است که ادعا می‌کند عضو ماکزیمال در مجموعه مرتب جزئی خاص وجود دارد.اما اثبات این قضیه، روشی را برای تعیین این عضو ماکزیمال ارائه نمی‌دهد. به عنوان کاربرد لم زرن، قضیه زیر را بیان و اثبات می‌کنیم.

قضیه[ویرایش]

اگر A،Bدو مجموعه غیر تهی باشند، آنگاه تابع یک به یکی از Aبه Bو یا یک تابع یک به یک از Bبه A وجود دارد. اثبات فرض می‌کنیم X مجموعه تمام زوجهای مرتب (A_\alpha ,f_\alpha) \  کهA_\alpha \ زیر مجموعه‌ای از A و همچنین F_\alpha: A_\alpha \to B تابعی یک به یک است، باشند. رابطه \leرا روی X به طریق زیر تعریف می‌کنیم :

(A_\alpha ,f_\alpha) \le (A_\beta ,f_\beta) \iff A_\alpha \subseteq A_\beta ,f_\alpha \subseteq f_\beta

مسلما این رابطه ترتیبی جزئی است. به منظور استفاده از لم زرن، باید مطمئن شویم که هر زیر مجموعه کاملا مرتب T=\lbrace (A_\gamma,f_\gamma)|\gamma \in \Gamma \rbrace از X دارای یک کران بالاست. (\bigcup_{\gamma \in \Gamma} A_\gamma,\bigcup_{\gamma \in \Gamma} f_\gamma) یک حدس خوب برای کران بالای مجموعه T، است.

قرار می‌دهیم: A_1=\bigcup_{\gamma \in \Gamma} A_\gamma,f_1=\bigcup_{\gamma \in \Gamma} f_\gamma

آنگاه f_1:A_1 \to B طوری است که اگر(A_\gamma,f_\gamma) \in T,x \in A_\gamma، آنگاه f_1(x)=f_\gamma (x) \ برای اثبات خوش تعریف بودن f_1:A_1 \to B، فرض می‌کنیم که x به زیر مجموعه دیگری مانند A_\delta \ هم باشد(\delta \in \Gamma). آنگاه (A_\gamma,f_\gamma) \le (A_\delta,f_\delta) یا (A_\delta,f_\delta) \le (A_\gamma,f_\gamma)، که در هر حالت داریم f_\gamma(x)=f_\delta (x) \ ، که نشان می‌دهدf_1 \ ، خوش تعریف است. حال نشان می‌دهیم که f_1:A_1 \to B تابعی یک به یک است.برای این منظور فرض می‌کنیم، به ازای x,y \in A_1 خواهیم داشت f_1(x)=f_1(y) \ . آنگاه دو زوج مرتب (A_\gamma,f_\gamma),(A_\delta,f_\delta) \in T \ چنان وجود دارند کهx \in a_\gamma,y_\delta. دوباره مثل قبل : (A_\gamma,f_\gamma) \le (A_\delta,f_\delta) یا (A_\delta,f_\delta) \le (A_\gamma,f_\gamma) بدون اینکه در اثبات خللی وارد شود، فرض می‌کنیم (A_\gamma,f_\gamma) \le (A_\delta,f_\delta).

از فرض اخیر نتیجه می‌شود f_\delta(x)=f_\delta (y) \ ، که و لذا با توجه به یک به یک بودن f_\delta \ داریمx=y.به این ترتیب اثبات یک به یک بودن f_1 \ تکمیل می‌شود. بنابراین: به ازای هر \gamma \in \Gamma، داریم (A_1,f_1) \ge (A_\gamma,f_\gamma). پس (X,\le) \ در شرایط لم زرن صدق می‌کند و در نتیجه Xدارای عضو ماکزیمال است که آن را به صورت (\tilde{A} , \tilde {f}) \ مشخص می‌کنیم.در اینجا دو حالت ممکن است اتفاق بیفتد:

۱- \tilde {A} = A

در این حالت، همان تابع یک به یک مورد نظر است.

۲- \tilde {A} \ne A

در این حالت فرض می‌کنیم x_0 \in A- \tilde{A} و ادعا می‌کنیم که در این حالت، تابع یک به یک \tilde{f} : \tilde{A} \to B در واقع تناظری یک به یک است.(زیرا در غیر این صورت، این تابع پوشا نبود و عضوی مانند Y_0 \in B- \tilde {f}(\tilde {A}) وجود دارد. حال تابع \tilde{f} : \tilde{A} \bigcup x_0 \to B را به صورت \tilde{\tilde{f}} (x_0)=y_0 و\tilde{\tilde{f}} (x)=\tilde{f}(x)، به ازای هر <math>x \in \tilde{A}</math> تعریف می‌کنیم. مسلما \tilde{\tilde{f}}، یک به یک است و (\tilde{A} \bigcup \lbrace x_0 \rbrace , \tilde{\tilde{f}}) >(\tilde{A},\tilde{f}) . نامساوی اخیر با فرض ماکزیمال بودن (\tilde{A},\tilde{f}) در تناقض است. لذا \tilde{f} : \tilde{A} \to B تناظری یک به یک است و در نتیجه \tilde{f^-1} تابع یک به یک مطلوب از B به زیر مجموعه \tilde{A} از A است. به این ترتیب اثبات قضیه تکمیل می‌شود.

نتیجه[ویرایش]

اگر A،B دو مجموعه باشند، آنگاه cardA \le cardB یا cardB \le card A.بنابراین اگر m،n دو عدد اصلی متمایز باشند، داریم، n<m یا m<n.

منابع[ویرایش]

پیوند به بیرون[ویرایش]