عناصر ماکسیمال و مینیمال

در ریاضیات، به‌خصوص در نظریه ترتیب، یک عنصر ماکسیمال (Maximal Element) از زیرمجموعه $S$ از یک مجموعه مرتب جزئی (poset)، عنصری از $S$ است که از هیچ عنصر دیگری از $S$ کوچکتر نباشد. تعریف عنصر مینیمال (Minimal Element)، دوگان تعریف اخیر است: عنصری از $S$ که از هیچ عنصر دیگر $S$ بزرگتر نباشد.

نمودار هسه از مجموعه مقسوم‌علیه‌های ۶۰ که توسط رابطه «x عاد می‌کند y را» به صورت جزئی مرتب شده‌است. زیرمجموعه قرمز $S=\{1,2,3,4\}$ دارای دو عنصر ماکسیمال ۳ و ۴، یک عنصر مینیمال ۱ که همزمان کوچکترین عنصر نیز می‌باشد.

مفاهیم عناصر ماکسیمال و مینیمال به ترتیب از بزرگترین و کوچکترین عنصر (یا ماکسیمم و مینیمم) ضعیف ترند. ماکسیمم زیرمجموعه $S$ از یک مجموعه مرتب جزئی، عنصری از $S$ است که از هر عنصر $S$ بزرگتر مساوی بوه و مینیمم $S$ نیز به صورت دوگان ماکسیمم تعریف می‌شود. درحالی که مجموعه مرتب جزئی حداکثر یک ماکسیمم و حداکثر یک مینیمم دارد، تعداد هرکدام از عناصر ماکسیمال و مینیمال ممکن است بیش از یکی باشند. مفاهیم عناصر ماکسیمال و ماکسیمم برای مجموعه‌های مرتب کلی یکی می‌شوند، همچنین مینیمال و مینیمم برای چنین مجموعه‌هایی یکی می‌شوند.

به عنوان مثال مجموعه زیر را در نظر بگیرید:

$S=\{\{d,o\},\{d,o,g\},\{g,o,a,d\},\{o,a,f\}\}$

اگر ترتیب شمول (زیرمجموعه بودن) را بر روی آن در نظر بگیریم، عنصر $\{d,o\}$ در مجموعه فوق مینیمال است، چرا که شامل هیچ مجموعه دیگری از $S$ نیست. عنصر $\{g,o,a,d\}$ در آن ماکسیمال است، چرا که هیچ مجموعه دیگری از $S$ آن را دربر ندارد. عنصر $\{d,o,g\}$ نه مینیمال است و نه ماکسیمال، در حالی که $\{o,a,f\}$ هم ماکسیمال است و هم مینیمال. برهمین اساس مجموعه $S$ هیچ ماکسیمم یا مینیممی ندارد.

لم زرن بیان می‌کند که هر مجموعه مرتب جزئی که هر زیرمجموعه مرتب کلی آن (زنجیره‌ها) دارای کران بالا باشد، شامل حداقل یک عنصر ماکسیمال است. این لم معادل با قضیه خوش-ترتیبی و اصل موضوع انتخاب است. لم زرن نتایج مهمی را در سایر شاخه‌های ریاضیات ایجاب می‌کند: قضیه هان-باناخ، قضیه کیرسزبراون، قضیه تیخونوف، وجود پایه همل برای هر فضای برداری و وجود بستار جبری برای هر میدان.

تعریف

$(P,\leq )$ مجموعه جزئاً مرتب و $S\subset P$. آنگاه$m\in S$ است یک عضو بیشین $S$ اگر

برای همه $s\in S$با $m\leq s$ قرار دهیم $m=s.$

تعریف عضو کمین با استفاده از ≤ به جای ≥ حاصل می‌شود.

وجود و منحصر به فرد

یک حصار که فقط از فقط عضوهای بیشین و کمین تشکیل شده است (مثال 3).

عناصر بیشین لزوماً وجود ندارند.

مثال 1: قرار دهید S = [1,∞) ⊂ ℝبرای تمام m∈S ما s=m+1∈S اما m<s) m≤s است ولی m=s نیست).

مثال 2: قرار دهید S = {s∈ℚ: 1≤s²≤2} ⊂ ℚ و به یاد بیاورید که ${\sqrt {2}}$∉ℚ.

به‌طور کلی ≤ فقط یک مرتب جزیی روی S است. اگر m یک عضو بیشین و s∈S باشد، احتمال اینکه نه s≤m و نه m≤s باشد، باقی می‌ماند. این، احتمال اینکه آنجا بسیاری ازعضوهای بیشین هست را باقی می‌گذارد.

مثال 3: در محدوده a1 <b1> a2 <b2> a3 <b3> ... , همه ai عضو کمین هستند و همه biها عضو بیشین هستند، شکل را ببینید.

مثال 4: فرض کنید A یک مجموعه با حداقل 2 عضو و S={{a}: a∈A} زیرمجموعه توانی (P(A شامل مجموعه های تک عضوی (singletons)، با رابطه ی ⊂ یک مرتب جزئی باشد. این یک مرتب جزئی گسسته است – هیچ دو عضوی قابل مقایسه نیستند – و بنابراین {a}∈S عضو بیشین (و کمین) است و برای هر a‘’ ، نه {a‘} ⊂ {a‘‘} و نه {a‘‘} ⊂ {a‘} .

عضو بیشین و بزرگ‌ترین عضو

قدرت مجموعه {xباyباz} تا حدی به دستور ⊂. بزرگترین عنصر {xباyباz} است تنها خود را حداکثر عنصر است.

به نظر می‌رسد که m باید بزرگترین عضو یا ماکسیمم باشد ولی در حقیقت الزاماً اینطور نیست، این تعریف از عضو بیشین تا حدودی ضعیف است. فرض کنید s ∈ S و max S ≤ s بنابراین، با توجه به تعریف بزرگترین عضو، s ≤ max S پس s = max S. به عبارت دیگر، اگر ماکسیمم وجود داشته باشد، همان عضو بیشین (یکتا) است.

معکوس آن درست نیست: عضوهای بیشین می‌توانند وجود داشته باشند درحالیکه هیچ ماکسیممی وجود ندارد. مثال 3 نمونه‌ای از وجود مقدار زیادی اعضای بیشین بدون وجود ماکزیمم است. مجدداً دلیل این مسئله این است که در حالت کلی ≥ فقط یک ترتیب جزئی روی S است. اگر m یک عضو بیشین باشد و s ∈ S، این امکان همچنان باقی می‌ماند که نه m ≤ s و نه s ≤ m.

اگر تعدادی اعضای بیشین وجود داشته باشد، آن‌ها در برخی متن‌ها frontier نامیده شده‌اند. همچنان که در Pareto frontier.

البته زمانی که محدودیت $\leq$ به $S$ یک کل منظوراین مفاهیم حداکثر عنصر و بزرگترین عنصر بوده‌است. اجازه $m\in S$ تواند حداکثر عنصر برای هر $s\in S$ یا $s\leq m$ یا $m\leq s$. در مورد دوم تعریف حداکثر عنصر نیاز به $m=s$ بنابراین نتیجه می‌گیریم که $s\leq m$. به عبارت دیگر $m$ بزرگترین عنصر است.

نهایتاً اجازه دهید اینطور بیان کنیم که برای اینکه S یک مرتب کامل (خطی) باشد، شرط کافی این است مطمئن باشیم که عضو بیشین، بزرگترین عضو است؛ ولی این شرط لازم نیست. برای مثال، هر مجموعهٔ توانی (P(S از مجموعهٔ S فقط یک عضو بیشین خواهد داشت. یعنی خود S، که بزرگترین عضو یکتا هم دارد ولی تقریباً مجموعهٔ توان، مرتب کامل نیست. با شکل مقایسه کنید.

مجموعه‌های جهت دار

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

نتیجه‌گیری مشابهی برای عضوهای کمین نیز صدق می‌کند.

اطلاعات مقدماتی بیشتری در مقاله مرتب کامل وجود دارد.

A subset $L$ of a partially ordered set $P$ is said to be a lower set of $P$ if it is downward closed: if $y\in L$ and $x\leq y$ then $x\in L$. Every lower set $L$ of a finite ordered set $P$ is equal to the smallest lower set containing all maximal elements of $L$.