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

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

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

همچنین می‌توان مشبکه‌ها را به عنوان ساختارهای جبری که مشخص کنندهٔ تعدادی هویت برهان‌اند، شناخت. چون هر دو تعریف معادلند، نظریه مشبکه به نظریه ترتیب و جبر جهانی متصل می‌شود. شبه مشبکه‌ها شامل مشبکه‌هایی می‌شوند که به نوبه خود شامل جبر بولی و جبر هیتینگ می‌شود. همه این ساختارهای مشبکه مانند به اندازه توصیف‌های جبری نظریه ترتیب را تصدیق می‌کنند.

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

اگر (L , ≤) یک مجموعه مرتب جزئی باشد و S یک زیر مجموعه یا مساوی دلخواه L باشد، آنگاه u∈L یک کران بالا برای S است اگر به ازای هر∈S s داشته باشیم: s≤u. یک مجموعه ممکن است چند کران بالا داشته باشد یا اصلاً کران بالا نداشته باشد. یک کران بالاu از S را هنگامی کوچکترین کران بالا یا سوپریمم می‌نامیم که به ازای هر کران بالا x داشته باشیم: u≤x یک مجموعه حتماً کوچکترین کران بالا ندارد ولی نمی‌تواند بیش از یکی داشته باشد. از طرفی، l∈L یک کران پایین برای S است اگر به ازای هر ∈S s داشته باشیم: l≤s. یک کران پایین l از S را هنگامی بزرگترین کران پایین یا اینفیمم می‌نامیم که به ازای هر کران پایین x داشته باشیم x≤l. یک مجموعه ممکن است چند کران پایین داشته باشد، یا اصلاً کران پایین نداشته باشد ولی می‌تواند حداکثر یک بزرگترین کران بالا داشته باشد. یک مجموعه مرتب جزئی (L ,≤) را یک شبه مشبکه از بالا کراندار یا ازپایین کراندار می‌نامند اگرهر زیر مجموعه دو عضوی {a,b} از L یک بزرگترین کران پایین و یک کوچکترین کران بالا داشته باشد، که با a∧b و a∨b نشان داده می‌شود. و(L ,≤) یک مشبکه نامیده می‌شود اگر هم یک شبه مشبکه از بالاکراندار و هم یک شبه مشبکه از پایین کراندار باشد. این تعاریف عملگرهای ∨و∧ را می‌سازند. هر دو عملگر نسبت به ترتیب یکنواختند :≤a_2 a_1 و ≤b_2 b_1 نتیجه می‌دهد∨b_2 ≤a_2 a_1∨b_1 و ∧b_2 ≤a_2 a_1∧b_1. با استدلال استقرا ثابت می‌شود که هر زیر مجموعه غیر تهی محدود مشبکه دارای یک سوپریمم و اینفیمم است. با فرض‌ها اضافی، نتیجه‌های بیشتری ممکن است به دست آید.

یک مشبکه کراندار مشبکه‌ای است که یک بزرگترین عضو ۱ و کوچکترین عضو ۰ داشته باشد به صورت: ۰≤x≤1 for every x in l بزرگترین عضو و کوچک‌ترین عضو هم ماکسیموم و مینیموم یا عنصر اول و عنصر آخر نامیده می‌شوند؛ و با ⊤ و ⊥ نشان می‌دهند. هر مشبکه می‌تواند با اضافه کردن بزرگترین و کوچکترین عضو مجازی به یک مشبکه کراندار تبدیل شود، و هر مشبکه غیر تهی محدود کراندار است. با گرفتن سوپریمم تمام اعضا. یک مجموعه مرتب جزئی یک مشبکه کراندار است اگر و تنها اگرمجموعه محدود از اعضا (همچنین تهی) یک سوپریمم و یک اینفیمم داشته باشد. برای هر عضو x از[۱] بدیهی است که :∀a∈∅∶x≤a و ∀a∈∅∶a≤x. پس در نتیجه هر عضو پوزت هم کران بالا و هم کران پایین مجموعه تهی است؛ که نشان می‌دهد که سوپریمم مجموعه تهی، کوچکترین عضو آن و اینفیمم آن بزرگترین عضو است: ∨∅=۰ و ∧∅=۱ وبا وابستگی و جا به جایی سوپریمم و اینفیمم ثابت است: سوپریمم اجتماع مجموعه‌های بی‌نهایت برابر است با سوپریمم سوپریمم مجموعه‌ها و همچنین اینفیمم اجتماع مجموعه‌های بی‌نهایت برابر است با اینفیمم اینفیمم مجموعه‌ها. به طور مثال زیرمجموعه‌های محدود A و B از پوزت L: ∨(A∪B)=(∨A)∧(∨B)

and
 ∧(A∪B)=(∧A) ∧(∧B)

گرفتن B به عنوان مجموعه تهی: ∨(A∪∅)=(∨A)∨(∨∅)=(∨A)∨۰= ∨A

and

∧(A∪∅)=(∧A)∧(∧∅)=(∧A) ∧۱= ∧A که اثبات اصل A∪∅=A است.

عضو y مشبکه پوشاننده عضو دیگر x است اگر y>x، اما عضوی مثل z وجود نداشته باشد که y>z>xاینجا y>x به این معناست که x≤y و x≠y. یک مشبکه (L,≤) درجه دار نام دارد یا مرتبه دار نام دارد اگر دارای یک تابع رتبه r از L به N یا گاهی به Z، سازگار با ترتیب (هرگاه x<y آنگاه r(x)<r(y)) به طوری که هرگاه y، x را بپوشاند، آنگاه r(y)=r(x)+1. مقدار تابع رتبه برای هر عضو مشبکه، رتبه آن عضو نام دارد. با توجه به یک زیر مجموعه از یک مشبکه که H زیر مجموعه L باشد، سوپریمم و اینفیمم محدود به توابع جزئی – تعریف نشده‌اند اگر مقدار آنها در زیر مجموعه H نیست. ساختار حاصل شده روی H یک مشبکه جزئی نام دارد. علاوه بر این تعریف بیرونی به عنوان زیر مجموعه‌ای از ساختارهای جبری دیگر، یک مشبکه جزئی همچنین می‌تواند ذاتاً به عنوان یک مجموعه با دو عملگر دودوئی جزئی که بدیهیات را تأیید می‌کند تعریف شود.

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

مشبکه عمومی یک ساختار جبری، ∨,∧). (L تشکیل شده از یک مجموعه L و دو ::عملگر دودویی ∨,∧ رویL یک شبکه است.

اشکال مشبکه[ویرایش]

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