پرش به محتوا

مشبکه (ترتیب)

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از توری (ترتیب))
یک شبکه دو بعدی

مشبکه (به انگلیسی: Lattice) یا شبکه[۱] ساختاری مجرد است که در شاخه های نظریه ترتیب و جبر مجرد در ریاضیات مورد مطالعه قرار می گیرد. مشبکه مجموعه ای با ترتیب جزئی است که در آن هر دو عنصر دارای سوپریمم (همچنین به آن کوچکترین کران بالایی Least Upper Bound یا مخفف آن lub یا جوین Join هم می گویند) و اینفیمم (همچنین به آن بزرگترین کران پایینی Greatest Lower Bound یا مخفف آن glb یا میت Meet هم می گویند) منحصر بفردی اند. یک مثال مشبکه ها اعداد طبیعی اند که توسط رابطه مقسوم علیهی می توان رابطه ترتیب جزئی روی آن تعریف کرد، به طوری که سوپریمم منحصر به فرد آن کوچکترین مضرب مشترک یا ک.م.م. و اینفیمم منحصر به فرد آن بزرگترین مقسوم علیه مشترک یا ب.م.م. است.

مشبکه ها را نیز می توان به صورت ساختارهای جبری دید که برخی از اصول موضوعه در قالب اتحادهایی را ارضاء می کنند. از آنجا که هر دو تعریف مذکور معادل اند، نظریه مشبکه را هم می توان در نظریه ترتیب و هم در جبر جهانی پیگیری کرد. نیم-مشبکه شامل مشبکه‌ها نیز می شود. نیم-مشبکه‌ها نیز به نوبه خود شامل جبر هیتینگ و جبرهای بولی نیز می شوند. تمام این ساختارهای "شبیه مشبکه" را نیز می توان هم از جنبه نظریه ترتیبی و هم جبری توصیف کرد.

مشبکه‌ها به عنوان مجموعه‌های مرتب جزئی

[ویرایش]

اگر یک مجموعه مرتب جزئی باشد و یک زیر مجموعه دلخواهی از باشد، آنگاه یک کران بالا برای است اگر به ازای هر داشته باشیم: . یک مجموعه ممکن است چند کران بالا داشته باشد یا اصلاً کران بالا نداشته باشد. یک کران بالا از را هنگامی کوچکترین کران بالا یا سوپریمم می‌نامیم که به ازای هر کران بالای دیگری چون داشته باشیم: یک مجموعه حتماً کوچکترین کران بالا ندارد ولی نمی‌تواند بیش از یکی داشته باشد. دوگان بحث فوق: یک کران پایین برای است اگر به ازای هر داشته باشیم: . یک کران پایین از را هنگامی بزرگترین کران پایین یا اینفیمم می‌نامیم که به ازای هر کران پایین دیگری چون داشته باشیم . یک مجموعه ممکن است چند کران پایین داشته باشد، یا اصلاً کران پایین نداشته باشد ولی می‌تواند حداکثر یک بزرگترین کران پایین داشته باشد.

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

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

یک مشبکه کراندار، مشبکه‌ای است که دارای بزرگترین عضو (که به آن ماکسیمم یا عنصر بالا هم گفته شده و آن را با یا نیز نشان می دهند) و کوچکترین عضو (که به آن مینیمم یا عنصر پایین هم گفته شده و آن را با یا نیز نشان می دهند) است به طوری که تمام اعضای آن بین این دو عضو قرار می گیرند:

هر مشبکه را می توان در یک مشبکه کراندار با اضافه کردن عناصر جدیدی به عنوان ماکسیمم و مینیمم نشاند، و هر مشبکه متناهی ناتهی کراندار است. چرا که برای یک مشبکه متناهی می توان جوین و میت تمام عناصر را به ترتیب به صورت و بدست آورد که در آن ها ، سپس این دو را به مشبکه متناهی مورد نظر افزوده و اینگونه به ترتیب ماکسیمم و مینیمم را با مشبکه اجتماع کردیم و اینچنین مشبکه (در صورتی که قبلاً کراندار نبوده است) را کراندار کرده ایم.

یک مجموعه جزئی مشبکه کراندار است اگر و تنها اگر هر زیر مجموعه متناهی از عناصرش دارای جوین و میت باشد. برای هر عنصر از یک پوست (POSET، مجموعه جزئی مرتب) و به طور بدیهی برقرار است (یعنی به انتفای مقدم برقرار است) و لذا هر عضو از پوست هم کران بالا و هم پایین مجموعه تهی است. نتیجتاً جوین مجموعه تهی و میت مجموعه تهی است. این نتیجه گیری با شرکت پذیر بودن و جابجایی بودن میت و جوین سازگار است: جوین اجتماع مجموعه های متناهی برابر جوین جوین های مجموعه هاست، و دوگان آن برای میت هم برقرار است. به طور دقیق تر برای زیرمجموعه های متناهی داریم:

و

حال اگر در اتحادهای بالا تهی باشد اتحادهای زیر بدست می آیند:

و

که با این حقیقت که سازگار است.

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

گویند مشبکه مدرج است (برخی مواقع به آن رتبه‌ای نیز می گویند، اما با پوست رتبه ای یا Ranked POSET اشتباه نشود) اگر بتوان آن را مجهز به تابع رتبه کرد. این تابع با r نامگذاری شده و از به می رود، برخی مواقع هم-دامنه آن است. ویژگی این تابع سازگاری با ترتیب است (یعنی از نتیجه می شود )، چنان که هرگاه عنصر را بپوشاند خواهیم داشت . مقدار تابع رتبه برای یک عنصر مشبکه را رتبه آن عنصر گویند.

برای زیرمجموعه دلخواهی از یک مشبکه چون ، میت و جوین محدود به توابع جزئی (یعنی دیگر بر روی کل دامنه تعریف نمی شوند) می شوند، اینگونه که اگر مقادیر میت و جوین یک عنصر در زیرمجموعه نباشد، میت و جوین آن عنصر تعریف نشده در نظر گرفته می شود. ساختار حاصل روی را مشبکه جزئی گویند. به علاوه این تعریف برونگرا که مشبکه را بر اساس ساختار جبری دیگری (یعنی مشبکه دیگری) تعریف می کند، یک مشبکه جزئی را به صورت ذاتی و درونگرا نیز می توان تعریف کرد، اینگونه که میت و جوین را به صورت توابع جزئی تعریف کنیم که در اصول موضوعه های خاصی صدق کنند.[۲]

مشبکه‌ها به عنوان ساختارهای جبری

[ویرایش]

مشبکه عمومی

[ویرایش]

مشبکه یک ساختار جبری شامل مجموعه ای چون مجهز به دو عمل دوتایی جابجایی شرکت پذیر و روی است، به طوری که برای هر اتحادهی زیر به نام قوانین جذب برقرار باشند:

دو اتحاد زیر که از قوانین جذب نتیجه می شوند نیز در برخی منابع به عنوان اصول موضوعه چنین مشبکه هایی قید می شوند.[یادداشت ۱] به این اتحادها قوانین خودتوانی می گویند:

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

اشکال مشبکه

[ویرایش]

یک مفهوم مناسب از ریخت (شکل) بین دو مشبکه به آسانی از تعریف جبری بالا بر می‌آید. دو مشبکه (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 است.

یادداشت‌ها

[ویرایش]
  1. aa = a ∨ (a ∧ (aa)) = a, and dually for the other idempotent law. Dedekind, Richard (1897), "Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler", Braunschweiger Festschrift: 1–40.

پانویس

[ویرایش]
  1. «شبکه» [ریاضی] هم‌ارزِ «lattice»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر چهارم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۵۹-۱ (ذیل سرواژهٔ شبکه2)
  2. Grätzer 1996, p. 52.
  3. هم ریختی

منابع

[ویرایش]

تک نویس های آزاد آنلاین:

متون مقدماتی برای کسانی که به بلوغ ریاضیاتی نرسیده اند:

  • Donnellan, Thomas, 1968. Lattice Theory. Pergamon.
  • Grätzer, G., 1971. Lattice Theory: First concepts and distributive lattices. W. H. Freeman.

متون استاندارد معاصر که کمی از منابع بالا سخت ترند:

تک نویس های پیشرفته:

در ارتباط با مشبکه های آزاد:

  • R. Freese, J. Jezek, and J. B. Nation, 1985. "Free Lattices". Mathematical Surveys and Monographs Vol. 42. Mathematical Association of America.
  • Johnstone, P.T., 1982. Stone spaces. Cambridge Studies in Advanced Mathematics 3. Cambridge University Press.

در ارتباط با تاریخچه نظریه مشبکه ها:

در مورد کاربرد های نظریه مشبکه ها:

  • Garrett Birkhoff (1967). James C. Abbot (ed.). What can Lattices do for you?. Van Nostrand. Table of contents