Distributive lattice

In mathematics, a distributive lattice is a lattice in which the operations of join and meetdistribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

As in the case of arbitrary lattices, one can choose to consider a distributive lattice L either as a structure of order theory or of universal algebra. Both views and their mutual correspondence are discussed in the article on lattices. In the present situation, the algebraic description appears to be more convenient.

A lattice (L,∨,∧) is distributive if the following additional identity holds for all x, y, and z in L:

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z).

Viewing lattices as partially ordered sets, this says that the meet operation preserves non-empty finite joins. It is a basic fact of lattice theory that the above condition is equivalent to its dual:^[1]

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)   for all x, y, and z in L.

In every lattice, if one defines the order relation p≤q as usual to mean p∧q=p, then the inequality x ∧ (y ∨ z) ≥ (x ∧ y) ∨ (x ∧ z) and its dual x ∨ (y ∧ z) ≤ (x ∨ y) ∧ (x ∨ z) are always true. A lattice is distributive if one of the converse inequalities holds, too. More information on the relationship of this condition to other distributivity conditions of order theory can be found in the article Distributivity (order theory).

Sholander (1951)^[2] gives a simplified characterization of distributive lattices only utilizing ${\textstyle a\wedge (a\vee b)=a}$ and ${\textstyle a\wedge (b\vee c)=(c\wedge a)\vee (b\wedge a)}$.

A morphism of distributive lattices is just a lattice homomorphism as given in the article on lattices, i.e. a function that is compatible with the two lattice operations. Because such a morphism of lattices preserves the lattice structure, it will consequently also preserve the distributivity (and thus be a morphism of distributive lattices).

Distributive lattices are ubiquitous but also rather specific structures. As already mentioned the main example for distributive lattices are lattices of sets, where join and meet are given by the usual set-theoretic operations. Further examples include:

• The Lindenbaum algebra of most logics that support conjunction and disjunction is a distributive lattice, i.e. "and" distributes over "or" and vice versa.
• Every Boolean algebra is a distributive lattice.
• Every Heyting algebra is a distributive lattice. Especially this includes all locales and hence all open set lattices of topological spaces. Also note that Heyting algebras can be viewed as Lindenbaum algebras of intuitionistic logic, which makes them a special case of the first example.
• Every totally ordered set is a distributive lattice with max as join and min as meet.
• The natural numbers form a (conditionally complete) distributive lattice by taking the greatest common divisor as meet and the least common multiple as join. This lattice also has a least element, namely 1, which therefore serves as the identity element for joins.
• بفرض عدد صحيح موجب n ، فإن مجموعة جميع القواسم الموجبة لـ n تُشكّل شبكة توزيعية، حيث يُمثّل القاسم المشترك الأكبر (meet) والمضاعف المشترك الأصغر (join). وتُعتبر هذه الشبكة جبرًا منطقيًا إذا وفقط إذا كان n خاليًا من المربعات .
• الفضاء المتجهي المرتب شبكياً هو شبكة توزيعية.
• شبكة يونغ المعطاة بترتيب تضمين مخططات يونغ التي تمثل تقسيمات الأعداد الصحيحة هي شبكة توزيعية.
• نقاط متعدد السطوح التوزيعي ( متعدد سطوح محدب مغلق تحت عمليات الحد الأدنى والحد الأقصى على مستوى الإحداثيات)، حيث تمثل هاتان العمليتان عمليتي الربط والتقاطع للشبكة. ^{[ 3 ]}

في المراحل الأولى لتطوير نظرية الشبكة، ^اعتقد تشارلز س. بيرس أن جميع الشبكات توزيعية، أي أن التوزيعية تتبع من بقية بديهيات الشبكة. ^{[ 4 ] [ 5 ]} ومع ذلك، قدم كل من شرودر ، ^{وفويغت ، ولوروث} ، وكورسلت ، ^{[ 6 ]} وديديكيند براهين على الاستقلال . ^{[ 4} ]

شبكة ماسية M ₃

شبكة خماسية N ₅

مخططات هاس للشبكتين النموذجيتين غير التوزيعيتين. الشبكة المعينية M3 غير توزيعية لأن x _∧ ( y ∨ z ) = x ∧ 1 = x _≠ 0 = 0 ∨ 0 = ( x ∧ y ) ∨ ( x ∧ z ) ، بينما الشبكة الخماسية N5 غير توزيعية لأن x ∧ ( y ∨ z ) = x ∧ 1 = x ≠ z = 0 ∨ z = ( x ∧ y ) ∨ ( x ∧ z ).

توجد صيغ مكافئة مختلفة للتعريف أعلاه. على سبيل المثال، تكون L توزيعية إذا وفقط إذا تحقق ما يلي لجميع العناصر x و y و z في L : $${\displaystyle (x\wedge y)\vee (y\wedge z)\vee (z\wedge x)=(x\vee y)\wedge (y\vee z)\wedge (z\vee x).}$$ وبالمثل، تكون L توزيعية إذا وفقط إذا

${\displaystyle x\wedge z=y\wedge z}$و${\displaystyle x\vee z=y\vee z}$دائماً ما يُلمّح${\displaystyle x=y.}$

أبسط الشبكات غير التوزيعية هي M³ _{، المعروفة} باسم "شبكة المعين"، و N⁵ _{، المعروفة} باسم "شبكة الخماسي". تكون الشبكة توزيعية إذا وفقط إذا لم تكن أي من شبكاتها الفرعية متماثلة مع M³ أو N⁵ ؛ الشبكة الفرعية هي مجموعة جزئية مغلقة تحت عمليتي التقاطع والوصل للشبكة الأصلية. تجدر الإشارة إلى أن هذا لا يعني أن تكون مجموعة جزئية شبكةً تحت الترتيب الأصلي (ولكن ربما مع عمليتي وصل وتقاطع مختلفتين). تُستمد المزيد من الخصائص من نظرية التمثيل في القسم التالي. 

ثمة طريقة أخرى للتعبير عن الحقيقة نفسها، وهي أن كل شبكة توزيعية هي ناتج فرعي مباشر لنسخ من سلسلة ثنائية العناصر ، أو أن العضو الوحيد غير القابل للاختزال الفرعي المباشر في فئة الشبكات التوزيعية هو سلسلة ثنائية العناصر. وكنتيجة لذلك، تتمتع كل شبكة منطقية بهذه الخاصية أيضًا. ^{[ 7 ]}

وأخيرًا، تتضمن خاصية التوزيع عدة خصائص أخرى مفيدة. على سبيل المثال، يكون عنصر الشبكة التوزيعية أوليًا للتقاطع إذا وفقط إذا كان غير قابل للاختزال للتقاطع ، مع أن هذه الأخيرة تُعدّ عمومًا خاصية أضعف. وبحسب الازدواجية، ينطبق الأمر نفسه على العناصر الأولية للوصل والعناصر غير القابلة للاختزال للوصل . ^{[ 8 ]} إذا كانت الشبكة توزيعية، فإن علاقة التغطية الخاصة بها تُشكّل رسمًا بيانيًا وسيطًا . ^{[ 9 ]}

علاوة على ذلك، فإن كل شبكة توزيعية هي أيضًا نمطية .

أشارت المقدمة بالفعل إلى أهم سمة للشبكات التوزيعية: الشبكة توزيعية إذا وفقط إذا كانت متماثلة مع شبكة من المجموعات (مغلقة تحت اتحاد المجموعات وتقاطعها ). (يُطلق على هذا التركيب الأخير أحيانًا اسم حلقة المجموعات في هذا السياق). إن كون اتحاد المجموعات وتقاطعها توزيعيين بالمعنى المذكور أعلاه حقيقة بديهية. أما الاتجاه الآخر فهو أقل وضوحًا، إذ يتطلب نظريات التمثيل المذكورة أدناه. تكمن الفكرة المهمة المستخلصة من هذه السمة في أن المتطابقات (المعادلات) التي تنطبق على جميع الشبكات التوزيعية هي نفسها التي تنطبق على جميع شبكات المجموعات بالمعنى المذكور أعلاه.

تنص نظرية بيركوف للتمثيل في الشبكات التوزيعية على أن كل شبكة توزيعية منتهية متماثلة مع شبكة المجموعات الدنيا للمجموعة المرتبة جزئيًا لعناصرها الأولية المشتركة (أو ما يعادلها: غير القابلة للاختزال المشترك). وهذا يُثبت وجود تقابل (حتى التماثل ) بين فئة جميع المجموعات المرتبة جزئيًا المنتهية وفئة جميع الشبكات التوزيعية المنتهية. ويمكن تعميم هذا التقابل ليشمل ازدواجية الفئات بين تشاكلات الشبكات التوزيعية المنتهية والدوال الرتيبة للمجموعات المرتبة جزئيًا المنتهية. إلا أن تعميم هذه النتيجة على الشبكات غير المنتهية يتطلب إضافة بنية أخرى.

تُعرف نظرية تمثيل أخرى مبكرة باسم نظرية ستون للتمثيل في الشبكات التوزيعية (نسبةً إلى مارشال هارفي ستون ، الذي أثبتها لأول مرة). تُعرّف هذه النظرية الشبكات التوزيعية بأنها شبكات من مجموعات مفتوحة متراصة في فضاءات طوبولوجية معينة . ويمكن اعتبار هذه النتيجة تعميمًا لنظرية ستون الشهيرة للتمثيل في الجبر البولياني، وتخصصًا للإطار العام لازدواجية ستون .

قدمت هيلاري بريستلي تمثيلاً هاماً آخر في نظريتها الخاصة بتمثيل الشبكات التوزيعية . في هذه الصيغة، تُستخدم الشبكة التوزيعية لإنشاء فضاء طوبولوجي مع ترتيب جزئي إضافي على نقاطه، مما ينتج عنه فضاء ستون مرتب (أو فضاء بريستلي ) مرتب (مفصول ترتيبياً بالكامل ). وتُستعاد الشبكة الأصلية كمجموعة من المجموعات السفلية المفتوحة المغلقة لهذا الفضاء.

نتيجةً لنظريتي ستون وبريستلي، يتضح بسهولة أن أي شبكة توزيعية متماثلة في الواقع مع شبكة من المجموعات. مع ذلك، تتطلب براهين كلتا العبارتين نظرية المثالي الأولي البولياني ، وهي صيغة ضعيفة من بديهية الاختيار .

يمكن إنشاء الشبكة التوزيعية الحرة على مجموعة من المولدات G بسهولة أكبر بكثير من الشبكة الحرة العامة. الملاحظة الأولى هي أنه باستخدام قوانين التوزيع، فإن كل حد يتكون من العمليات الثنائية${\displaystyle \lor }$و${\displaystyle \land }$يمكن تحويل مجموعة من المولدات إلى الشكل الطبيعي المكافئ التالي :

${\displaystyle M_{1}\lor M_{2}\lor \cdots \lor M_{n},}$

أين${\displaystyle M_{i}}$هي عبارة عن لقاءات منتهية لعناصر من G. علاوة على ذلك، بما أن كلاً من اللقاء والوصل هما تجميعيتان وتبديليتان ومتطابقتان ، يمكن تجاهل التكرارات والترتيب، وتمثيل وصل اللقاءات مثل الذي سبق كمجموعة من المجموعات:

${\displaystyle \{N_{1},N_{2},\ldots ,N_{n}\},}$

حيث${\displaystyle N_{i}}$هي مجموعات جزئية منتهية من G. ومع ذلك، لا يزال من الممكن أن يشير مصطلحان من هذا القبيل إلى نفس العنصر في الشبكة التوزيعية. يحدث هذا عندما يكون هناك مؤشران j و k بحيث${\displaystyle N_{j}}$هي مجموعة فرعية من${\displaystyle N_{k}.}$في هذه الحالة، يلتقي بـ${\displaystyle N_{k}}$سيكون أقل من مستوى التقاء${\displaystyle N_{j},}$وبالتالي يمكن إزالة المجموعة الزائدة بأمان${\displaystyle N_{k}}$دون تغيير تفسير المصطلح بأكمله. وبالتالي، تُسمى مجموعة من المجموعات الجزئية المنتهية من G غير زائدة عندما تكون جميع عناصرها${\displaystyle N_{i}}$غير قابلة للمقارنة فيما بينها (فيما يتعلق بترتيب المجموعات الفرعية)؛ أي عندما تشكل سلسلة مضادة من المجموعات المنتهية .

تُعرَّف الشبكة التوزيعية الحرة على مجموعة من المولدات G على مجموعة جميع المجموعات غير الزائدة المنتهية من المجموعات الجزئية المنتهية من G. ويُحصل على اتحاد مجموعتين غير زائدتين من خلال إزالة جميع المجموعات الزائدة. وبالمثل، فإن التقاء مجموعتين S و T هو النسخة غير الزائدة من${\displaystyle \{N\cup M\mid N\in S,M\in T\}.}$إن التحقق من أن هذا الهيكل عبارة عن شبكة توزيعية ذات خاصية عالمية مطلوبة هو إجراء روتيني.

يُعطى عدد العناصر في الشبكات التوزيعية الحرة ذات n مولدًا بأعداد ديديكيند . تنمو هذه الأعداد بسرعة، ولا تُعرف إلا لـ n  ≤  9؛ وهي

2، 3، 6، 20، 168، 7581، 7828354، 2414682040998، 56130437228687557907788، 286386577668298411128469151667598498812366 (التسلسل A000372 في OEIS ) .

تشير الأرقام أعلاه إلى عدد العناصر في الشبكات التوزيعية الحرة التي تكون فيها عمليات الشبكة عبارة عن ضمّ وتقاطع لمجموعات منتهية من العناصر، بما في ذلك المجموعة الفارغة. إذا مُنعت عمليات الضم والتقاطع الفارغة، فإن الشبكات التوزيعية الحرة الناتجة تحتوي على عنصرين أقل؛ ويشكل عدد عناصرها المتتالية

0، 1، 4، 18، 166، 7579، 7828352، 2414682040996، 56130437228687557907786، 286386577668298411128469151667598498812364 (التسلسل A007153 في OEIS ) .

• الشبكة التوزيعية الكاملة - شبكة تتوزع فيها الوصلات اللانهائية على نقاط التقاء لانهائية
• نظرية الازدواجية للشبكات التوزيعية
• الفضاء الطيفي

• بوريس، ستانلي ن.؛ سانكابانافار، إتش بي (1981). دورة في الجبر الشامل . سبرينغر-فيرلاغ. ISBN 3-540-90578-2.
• تسلسل OEIS A006982 (عدد الشبكات التوزيعية غير المصنفة التي تحتوي على n عنصرًا)