مشبکه (ترتیب)
مشبکه یا شبکه ساختاری مجرد است که در شاخه های نظریه ترتیب و جبر مجرد در ریاضیات مورد مطالعه قرار می گیرد. مشبکه مجموعه ای با ترتیب جزئی است که در آن هر دو عنصر دارای سوپریمم (همچنین به آن کوچکترین کران بالایی "Least Upper Bound" یا مخفف آن lub یا جوین "Join" هم می گویند) و اینفیمم (همچنین به آن بزرگترین کران پایینی "Greatest Lower Bound" یا مخفف آن glb یا میت "Meet" هم می گویند) منحصر بفردی اند. یک مثال مشبکه ها اعداد طبیعی اند که توسط رابطه مقسوم علیهی می توان رابطه ترتیب جزئی روی آن تعریف کرد، به طوری که سوپریمم منحصر به فرد آن کوچکترین مضرب مشترک یا ک.م.م. و اینفیمم منحصر به فرد آن بزرگترین مقسوم علیه مشترک یا ب.م.م. است.
مشبکه ها را نیز می توان به صورت ساختارهای جبری دید که برخی از اصول موضوعه در قالب اتحادهایی را ارضاء می کنند. از آنجا که هر دو تعریف مذکور معادل اند، نظریه مشبکه را هم می توان در نظریه ترتیب و هم در جبر جهانی پیگیری کرد. نیم-مشبکه شامل مشبکه‌ها نیز می شود. نیم-مشبکه‌ها نیز به نوبه خود شامل جبر هیتینگ و جبرهای بولی نیز می شوند. تمام این ساختارهای "شبیه مشبکه" را نیز می توان هم از جنبه نظریه ترتیبی و هم جبری توصیف کرد.
اگر formula_1 یک مجموعه مرتب جزئی باشد و formula_2 یک زیر مجموعه دلخواهی از formula_3 باشد، آنگاه formula_4 یک کران بالا برای formula_2 است اگر به ازای هر formula_6 داشته باشیم: formula_7. یک مجموعه ممکن است چند کران بالا داشته باشد یا اصلاً کران بالا نداشته باشد. یک کران بالا formula_8 از formula_2 را هنگامی کوچکترین کران بالا یا سوپریمم می‌نامیم که به ازای هر کران بالای دیگری چون formula_10 داشته باشیم: formula_11 یک مجموعه حتماً کوچکترین کران بالا ندارد ولی نمی‌تواند بیش از یکی داشته باشد. دوگان بحث فوق: formula_12 یک کران پایین برای formula_2 است اگر به ازای هر formula_6 داشته باشیم: formula_15. یک کران پایین formula_16 از formula_2 را هنگامی بزرگترین کران پایین یا اینفیمم می‌نامیم که به ازای هر کران پایین دیگری چون formula_10 داشته باشیم formula_19. یک مجموعه ممکن است چند کران پایین داشته باشد، یا اصلاً کران پایین نداشته باشد ولی می‌تواند حداکثر یک بزرگترین کران پایین داشته باشد.
یک مجموعه مرتب جزئی formula_1 را یک جوین-نیم-مشبکه می‌نامند اگر هر زیر مجموعه دو عضوی formula_21 از formula_3 دارای جوین (یا formula_23) باشد و یک میت-نیم-مشبکه است اگر formula_21 مذکور دارای میت (یا formula_25) باشد. حال formula_1 یک مشبکه نامیده می‌شود اگر هم یک جوین-نیم-مشبکه و هم یک میت-نیم-مشبکه باشد. این‌ها عمل های دوتایی formula_27 و formula_28 را تعریف می کنند. هر دو عملگر نسبت به ترتیب داده شده خاصیت یکنوایی دارند، یعنی: formula_29 و formula_30 نتیجه می دهد که formula_31 و formula_32.
با استدلال استقرایی ثابت می‌شود که هر زیر مجموعه ناتهی متناهی مشبکه دارای یک سوپریمم و اینفیمم است. با فرض های اضافی، نتیجه‌های بیشتری ممکن است به دست آید. برای ادامه این بحث، مقاله کامل‌بودن را در نظریه ترتیب ببینید. در آن مقاله این که چگونه می توان تعریف بالا را بر اساس وجود الصاق های گالوایی مناسب بین مجموعه های جزئی مرتب مربوط بازنویسی نمود، مورد بحث قرار گرفته است. رهیافت مذکور برای رهیافت نظریه رسته‌ای به مشبکه ها و همچنین برای تحلیل مفهوم صوری مناسب است.
یک مشبکه کراندار، مشبکه‌ای است که دارای بزرگترین عضو (که به آن ماکسیمم یا عنصر بالا هم گفته شده و آن را با formula_33 یا formula_34 نیز نشان می دهند) و کوچکترین عضو (که به آن مینیمم یا عنصر پایین هم گفته شده و آن را با formula_35 یا formula_36 نیز نشان می دهند) است به طوری که تمام اعضای آن بین این دو عضو قرار می گیرند:
هر مشبکه را می توان در یک مشبکه کراندار با اضافه کردن عناصر جدیدی به عنوان ماکسیمم و مینیمم نشاند، و هر مشبکه متناهی ناتهی کراندار است. چرا که برای یک مشبکه متناهی می توان جوین و میت تمام عناصر را به ترتیب به صورت formula_38 و formula_39 بدست آورد که در آن ها formula_40، سپس این دو را به مشبکه متناهی مورد نظر افزوده و اینگونه به ترتیب ماکسیمم و مینیمم را با مشبکه اجتماع کردیم و اینچنین مشبکه (در صورتی که قبلاً کراندار نبوده است) را کراندار کرده ایم.
یک مجموعه جزئی مشبکه کراندار است اگر و تنها اگر هر زیر مجموعه متناهی از عناصرش دارای جوین و میت باشد. برای هر عنصر formula_10 از یک پوست ("POSET"، مجموعه جزئی مرتب) formula_42 و formula_43 به طور بدیهی برقرار است (یعنی به انتفای مقدم برقرار است) و لذا هر عضو از پوست هم کران بالا و هم پایین مجموعه تهی است. نتیجتاً جوین مجموعه تهی formula_44 و میت مجموعه تهی formula_45 است. این نتیجه گیری با شرکت پذیر بودن و جابجایی بودن میت و جوین سازگار است: جوین اجتماع مجموعه های متناهی برابر جوین جوین های مجموعه هاست، و دوگان آن برای میت هم برقرار است. به طور دقیق تر برای زیرمجموعه های متناهی formula_46 داریم:
و
حال اگر در اتحادهای بالا formula_49 تهی باشد اتحادهای زیر بدست می آیند:
و
که با این حقیقت که formula_52 سازگار است.
گویند که یک عنصر دلخواهی از مشبکه چون formula_53، عنصر دیگری چون formula_10 را پوشش می دهد اگر formula_55، اما هیچ عنصری چون formula_56 وجود نداشته باشد به طوری که formula_57. در اینجا formula_55 به معنای formula_59 و formula_60 است.
گویند مشبکه formula_61 مدرج است (برخی مواقع به آن رتبه‌ای نیز می گویند، اما با پوست رتبه ای یا "Ranked POSET" اشتباه نشود) اگر بتوان آن را مجهز به تابع رتبه کرد. این تابع با "r" نامگذاری شده و از formula_3 به formula_63 می رود، برخی مواقع هم-دامنه آن formula_64 است. ویژگی این تابع سازگاری با ترتیب است (یعنی از formula_65 نتیجه می شود formula_66)، چنان که هرگاه formula_53 عنصر formula_10 را بپوشاند خواهیم داشت formula_69. مقدار تابع رتبه برای یک عنصر مشبکه را رتبه آن عنصر گویند.
برای زیرمجموعه دلخواهی از یک مشبکه چون formula_70، میت و جوین محدود به توابع جزئی (یعنی دیگر بر روی کل دامنه تعریف نمی شوند) می شوند، اینگونه که اگر مقادیر میت و جوین یک عنصر در زیرمجموعه formula_71 نباشد، میت و جوین آن عنصر تعریف نشده در نظر گرفته می شود. ساختار حاصل روی formula_71 را مشبکه جزئی گویند. به علاوه این تعریف برونگرا که مشبکه را بر اساس ساختار جبری دیگری (یعنی مشبکه دیگری) تعریف می کند، یک مشبکه جزئی را به صورت ذاتی و درونگرا نیز می توان تعریف کرد، اینگونه که میت و جوین را به صورت توابع جزئی تعریف کنیم که در اصول موضوعه های خاصی صدق کنند.
مشبکه یک ساختار جبری formula_73 شامل مجموعه ای چون formula_73 مجهز به دو عمل دوتایی جابجایی شرکت پذیر formula_73 و formula_73 روی formula_73 است، به طوری که برای هر formula_73 اتحادهی زیر به نام "قوانین جذب" برقرار باشند:
دو اتحاد زیر که از قوانین جذب نتیجه می شوند نیز در برخی منابع به عنوان اصول موضوعه چنین مشبکه هایی قید می شوند. به این اتحادها "قوانین خودتوانی" می گویند:
این اصول موضوعه ها بیان می دارند که formula_83 و formula_84 هردو نیم-مشبکه اند. قوانین جذب، تنها قوانینی از دو قانون فوق اند که در هردو هم از جوین استفاده شده و هم از میت و این باعث می شود که بین مشبکه و یک جفت ساختار دلخواه نیم-مشبکه تمایز ایجاد شده و بین دو نیم-مشبکه روابط مناسبی برقرار شود. به‌خصوص، هر نیم-مشبکه دوگان دیگری است.
یک مفهوم مناسب از ریخت (شکل) بین دو مشبکه به آسانی از تعریف جبری بالا بر می‌آید. دو مشبکه (L, ∨L, ∧L) و (M, ∨M, ∧M) در نظر بگیرید. یک مشبکه هم ریخت از Lبه M به صورت تابع f: L است که M شامل همهٔ a,bهایی عضو L است. f(a∨Lb) = f(a) ∨M f(b), and f(a∧Lb) = f(a) ∧M f(b). بنابراین f یک هم‌ریخت از دو شبه مشبکه است. هم چنین وقتی که مشبکه‌هایی با ساختارهای بیشتری در نظر گرفته شوند، ریخت‌ها بایستی به بیشترین ساختار نسبت داشته باشند. به ویژه در یک مشبکه هم ریخت محدود (که معمولاً همان «مشبکه همریخت» گفته می‌شود) تابع f بین دو مشبکه کران دار L و M ویژگی زیر را داراست: f(0L) = 0M f(1L) = 1M
طبق ترتیب فرمول بندی نظری این شرایط تنها بیان می‌کند که مشبکه‌ها تابعیست که تلاقی و اتصال‌های دودویی را حفظ می‌کند. برای مشبکه‌های کران دار حفظ کردن کوچکترین و بزرگترین عنصر در واقع همان حفظ تلاقی و اتصال یک مجموعه خالی است. هر هم ریختی مشبکه‌ها الزاماٌ یک رابطه ترتیبی یکنوا است. اما برعکس این مطلب درست نیست. اگرچه ترتیب دو طرفه حفظ شونده یک هم ریخت است اگر وارون ان هم یک ترتیب حفظ شونده باشد.
یک مشبکه یک ریخت در واقع یک مشبکه هم ریخت دو طرفه است. متشابها یک مشبکه درون ریخت یک مشبکه هم ریخت است از یک مشبکه درون خودش. هم چنین یک مشبکه خود ریخت یک مشبکه دو طرفه درون ریخت است. در واقع مشبکه‌ها و هم ریخت‌های آن‌ها یک دسته را تشکیل می‌دهند.
یک زیرمشبکه از مشبکه L یک مجموعه غیر تهی است ازL که در واقع مشبکه ایست با تلاقی و اتصال‌هایی مشابه L یک زیرمشبکه M از یک مشبکه L یک زیر مشبکه برجسته L است اگرx ≤ z ≤ y و x,yموجود در M نشان می‌دهد که zمتعلق به M است برای هر x,y،zعضوL.
در زیر تعدادی از ویژگی‌های مهم یک مشبکه مطرح شده است:
یک مجموعه مرتب جزئی مشبکه کامل نامیده می‌شود اگر همهٔ زیر مجموعه‌هایش هر دوی اتصال و تلاقی را دارا باشند. به ویژه هر مشبکه کامل یک مشبکه کران دار است. در حالیکه مشبکه‌های کران دار هم ریخت در کل فقط اتصال و تلاقی ::متناهی را حفظ می‌کنند مشبکه‌های کامل هم ریخت می‌بایستی ::اتصال و ::تلاقی دلخواه را حفظ کنند. هر مجموعه مرتب جزئی که یک زیر مشبکه کامل است یک مشبکه کامل نیز می‌باشد. شایان ذکر است که مشبکه جزئی در تضاد با مشبکه کامل نیست زیرا کلیهٔ مفهوم‌های مشبکه و مشبکه کامل و مشبکه جزئی تعاریفی محدود هستند.
یک مشبکه کامل مشروط مشبکه ایست که هر زیرمجموعه ناتهی که کران بالا دارد یک نقطه اتصال دارد (منظور از کران بالا کوچکترین کران بالا است) هنگامیکه مشبکه‌ها در عملیات دودویی قرار گیرند این رایج است که سؤال شود کدام یک بر دیگری توزیع پذیر است. توزیع‌پذیری عطف و فصل: a∨(b∧c) = (a∨b) ∧ (a∨c). a∧(b∨c) = (a∧b) ∨ (a∧c).
برای بسیاری از عملیات خاصیت توزیع‌پذیری سنگین بوده و خاصیت پیمانه‌ای به جای ان قرار می‌گیرد. ماهیت پیمانه‌ای بودن: (a ∧ c) ∨ (b ∧ c) = [(a ∧ c) ∨ b] ∧ c
اگر a<=c: a ∨ (b ∧ c) = (a ∨ b) ∧ c
هر مجموعهٔ X برای تولید زیر مشبکه‌های آزاد FX مورد استفاده قرار می‌گیرد. یک زیر مشبکه آزاد شامل تمامی زیر مجموعه‌های متناهی X است.تک نویس های آزاد آنلاین:
متون مقدماتی برای کسانی که به بلوغ ریاضیاتی نرسیده اند:
متون استاندارد معاصر که کمی از منابع بالا سخت ترند:
تک نویس های پیشرفته:در ارتباط با مشبکه های آزاد:
در ارتباط با تاریخچه نظریه مشبکه ها:
در مورد کاربرد های نظریه مشبکه ها: