انضم إلينا وتعرف على المزيد

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 112 صور
الموسوعة الحرة
العلاقات الثنائية المتعدية 
  • v
  • ت
  • هـ
متماثلمضاد للتناظرمتصلمؤسس بشكل جيدلديه روابطلديه لقاءاتانعكاسيغير انعكاسيغير متماثل
توتال، سيميكونكسمضاد للانعكاس
علاقة التكافؤعلامة صح خضراءY✗✗✗✗✗علامة صح خضراءY✗✗
طلب مسبق (طلب شبه رسمي)✗✗✗✗✗✗علامة صح خضراءY✗✗
طلب جزئي✗علامة صح خضراءY✗✗✗✗علامة صح خضراءY✗✗
إجمالي الطلبات المسبقة✗✗علامة صح خضراءY✗✗✗علامة صح خضراءY✗✗
إجمالي الطلب✗علامة صح خضراءYعلامة صح خضراءY✗✗✗علامة صح خضراءY✗✗
الطلب المسبق✗✗علامة صح خضراءYعلامة صح خضراءY✗✗علامة صح خضراءY✗✗
ترتيب شبه جيد✗✗✗علامة صح خضراءY✗✗علامة صح خضراءY✗✗
ترتيب جيد✗علامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY✗✗علامة صح خضراءY✗✗
شعرية✗علامة صح خضراءY✗✗علامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY✗✗
الانضمام إلى شبه الشبكة✗علامة صح خضراءY✗✗علامة صح خضراءY✗علامة صح خضراءY✗✗
شبكة اللقاءات✗علامة صح خضراءY✗✗✗علامة صح خضراءYعلامة صح خضراءY✗✗
ترتيب جزئي صارم✗علامة صح خضراءY✗✗✗✗✗علامة صح خضراءYعلامة صح خضراءY
ترتيب ضعيف صارم✗علامة صح خضراءY✗✗✗✗✗علامة صح خضراءYعلامة صح خضراءY
إجمالي الطلب الصارم✗علامة صح خضراءYعلامة صح خضراءY✗✗✗✗علامة صح خضراءYعلامة صح خضراءY
متماثلمضاد للتناظرمتصلمؤسس بشكل جيدلديه روابطلديه لقاءاتانعكاسيغير انعكاسيغير متماثل
التعريفات، للجميعأ،ب{\displaystyle a,b}وS≠∅:{\displaystyle S\neq \varnothing :} أRب⇒بRأ{\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}أRب و بRأ⇒أ=ب{\displaystyle {\begin{aligned}aRb{\text{ و }}&bRa\\\Rightarrow a={}&b\end{aligned}}}أ≠ب⇒أRب أو بRأ{\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}مينSموجود{\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}أ∨بموجود{\displaystyle {\begin{aligned}a\vee b\\{\text{يوجد}}\end{aligned}}}أ∧بموجود{\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}أRأ{\displaystyle aRa}لا أRأ{\displaystyle {\text{not }}aRa}أRب⇒لا بRأ{\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}
علامة صح خضراءيشير الرمز Y إلى أن خاصية العمود صحيحة دائمًا بالنسبة لعنصر الصف (في أقصى اليسار)، بينما يشير الرمز ✗ إلى أن الخاصية غير مضمونة بشكل عام (قد تكون صحيحة أو خاطئة). على سبيل المثال، يُشار إلى أن كل علاقة تكافؤ متناظرة، ولكن ليس بالضرورة مضادة للتناظر، بالرمز Y في عمود "متناظر" والرمز ✗ في عمود "مضاد للتناظر". علامة صح خضراء

تتطلب جميع التعريفات ضمنيًا العلاقة المتجانسةR{\displaystyle R}يكون متعدياً : للجميعأ،ب،ج،{\displaystyle a,b,c,}لوأRب{\displaystyle aRb}وبRج{\displaystyle bRc}ثمأRج.{\displaystyle aRc.} قد يتطلب تعريف المصطلح خصائص إضافية غير مدرجة في هذا الجدول.

يُصوّر مخطط هاس هذا مجموعة مرتبة جزئيًا بأربعة عناصر: a و b والعنصر الأقصى a∨{\displaystyle \vee }b يساوي مجموع a و b ، والعنصر الأصغر a∧{\displaystyle \wedge }b يساوي نقطة التقاء a و b . نقطة التقاء عنصر أقصى/أدنى مع عنصر آخر هي نفس العنصر الأقصى/الأدنى، والعكس صحيح. وبالتالي، فإن كل زوج في هذه المجموعة المرتبة جزئيًا له نقطة التقاء ونقطة التقاء، ويمكن تصنيف هذه المجموعة على أنها شبكة .

في الرياضيات ، وتحديداً في نظرية الترتيب ، ضم مجموعة جزئيةS{\displaystyle S}من مجموعة مرتبة جزئياًP{\displaystyle P}هو الحد الأعلى (الحد الأدنى الأعلى) لـS،{\displaystyle S,}يُشار إليه⋁S،{\textstyle \bigvee S,}وبالمثل، فإن لقاءS{\displaystyle S}هو الحد الأدنى (أكبر حد أدنى)، ويرمز له بـ⋀S.{\textstyle \bigwedge S.}بشكل عام، لا يشترط وجود عنصري الربط والتقاطع لمجموعة جزئية من مجموعة مرتبة جزئياً. ويُعتبر الربط والتقاطع متناظرين فيما يتعلق بانعكاس الترتيب.

تُسمى المجموعة المرتبة جزئيًا التي تحتوي جميع أزواجها على وصلة "شبه شبكة وصل" . وبالمثل، تُسمى المجموعة المرتبة جزئيًا التي تحتوي جميع أزواجها على نقطة التقاء " شبه شبكة التقاء" . أما المجموعة المرتبة جزئيًا التي تُصنف كشبه شبكة وصل وشبه شبكة التقاء في آنٍ واحد، فتُسمى " شبكة" . والشبكة التي تحتوي كل مجموعة جزئية فيها، وليس كل زوج فقط، على نقطة التقاء ووصلة، تُسمى " شبكة كاملة" . كما يُمكن تعريف شبكة جزئية ، لا تحتوي جميع أزواجها على نقطة التقاء أو وصلة، ولكن العمليات (عند تعريفها) تُحقق بديهيات معينة. [ 1 ]

إن عملية الانضمام/التقاء لمجموعة جزئية من مجموعة مرتبة كليًا هي ببساطة العنصر الأقصى/الأدنى لتلك المجموعة الجزئية، إذا كان هذا العنصر موجودًا.

إذا كانت مجموعة جزئيةS{\displaystyle S}من مجموعة مرتبة جزئياًP{\displaystyle P}إذا كانت المجموعة أيضًا مجموعة موجهة (إلى الأعلى) ، فإن وصلها (إن وُجد) يُسمى وصلة موجهة أو قيمة عليا موجهة . وبالمثل، إذاS{\displaystyle S}إذا كانت مجموعة موجهة للأسفل، فإن نقطة التقائها (إن وجدت) هي نقطة التقاء موجهة أو حد أدنى موجه .

التعريفات

نهج الترتيب الجزئي

يتركأ{\displaystyle A}لتكن مجموعة ذات ترتيب جزئي≤،{\displaystyle \,\leq ,\,}ودعx،y∈أ.{\displaystyle x,y\in A.} عنصرم{\displaystyle m}لأ{\displaystyle A}يُطلق عليه اسملقاء (أوالحد الأدنى الأكبر أوالحد الأدنى ) منx و y{\displaystyle x{\text{ و }}y}ويرمز إليه بـx∧y،{\displaystyle x\wedge y,}إذا تحققت الشروط التالية:

  1. م≤x و م≤y{\displaystyle m\leq x{\text{ و }}m\leq y}(إنه،م{\displaystyle m}يمثل الحد الأدنى لـx و y{\displaystyle x{\text{ و }}y}).
  2. لأيw∈أ،{\displaystyle w\in A,}لوw≤x و w≤y،{\displaystyle w\leq x{\text{ و }}w\leq y,}ثمw≤م{\displaystyle w\leq m}(إنه،م{\displaystyle m}أكبر من أو يساوي أي حد أدنى آخر لـx و y{\displaystyle x{\text{ و }}y}).

ليس بالضرورة أن يكون الالتقاء موجودًا، إما لأن الزوج ليس له حد أدنى على الإطلاق، أو لأن أيًا من الحدود الدنيا ليس أكبر من جميع الحدود الأخرى. ومع ذلك، إذا كان هناك التقاء لـx و y،{\displaystyle x{\text{ و }}y,}إذن فهو فريد من نوعه، لأنه إذا كان كلاهمام و م′{\displaystyle m{\text{ و }}m^{\prime }}أكبر الحدود الدنيا لـx و y،{\displaystyle x{\text{ و }}y,}ثمم≤م′ و م′≤م،{\displaystyle m\leq m^{\prime }{\text{ and }}m^{\prime }\leq m,}وبالتاليم=م′.{\displaystyle m=m^{\prime }.}[ 2 ] إذا لم تكن جميع أزواج العناصر منأ{\displaystyle A}إذا تم عقد اجتماع، فسيظل من الممكن اعتبار هذا الاجتماع عملية ثنائية جزئية علىأ.{\displaystyle A.}[ 1 ]

إذا كان اللقاء قائماً، فسيتم الإشارة إليه.x∧y.{\displaystyle x\wedge y.}إذا كانت جميع أزواج العناصر منأ{\displaystyle A}إذا تم عقد اجتماع، فإن الاجتماع هو عملية ثنائية علىأ،{\displaystyle A,}ومن السهل ملاحظة أن هذه العملية تحقق الشروط الثلاثة التالية: لأي عناصرx،y،z∈أ،{\displaystyle x,y,z\in A,}

  1. x∧y=y∧x{\displaystyle x\wedge y=y\wedge x}( خاصية التبديل )،
  2. x∧(y∧z)=(x∧y)∧z{\displaystyle x\wedge (y\wedge z)=(x\wedge y)\wedge z}( الترابطية )، و
  3. x∧x=x{\displaystyle x\wedge x=x}( التكرار ).

يتم تعريف عمليات الربط بشكل مزدوج مع ربطx و y،{\displaystyle x{\text{ and }}y,}إذا كان موجودًا، ويرمز إليه بـx∨y.{\displaystyle x\vee y.} عنصرج{\displaystyle j}لأ{\displaystyle A}هوانضم (أوالحد الأعلى الأدنى أو(الأعلى ) منx و y{\displaystyle x{\text{ and }}y}فيأ{\displaystyle A}إذا تحققت الشروط التالية:

  1. x≤ج و y≤ج{\displaystyle x\leq j{\text{ and }}y\leq j}(إنه،ج{\displaystyle j}يمثل الحد الأعلى لـx و y{\displaystyle x{\text{ and }}y}).
  2. لأيw∈أ،{\displaystyle w\in A,}لوx≤w و y≤w،{\displaystyle x\leq w{\text{ and }}y\leq w,}ثمج≤w{\displaystyle j\leq w}(إنه،ج{\displaystyle j}أقل من أو يساوي أي حد أعلى آخر لـx و y{\displaystyle x{\text{ and }}y}).

نهج الجبر الشامل

بحسب التعريف، عملية ثنائية∧{\displaystyle \,\wedge \,}على مجموعةأ{\displaystyle A}يُعتبر اللقاء ناجحاً إذا استوفى الشروط الثلاثة أ ، ب ، ج .(أ،∧){\displaystyle (A,\wedge )}ثم يكون ذلك عبارة عن شبكة شبه تقاطع . علاوة على ذلك، يمكننا حينها تعريف علاقة ثنائية≤{\displaystyle \,\leq \,}في الفقرة أ ، من خلال ذكر أنx≤y{\displaystyle x\leq y}إذا وفقط إذاx∧y=x.{\displaystyle x\wedge y=x.} في الواقع، هذه العلاقة هي ترتيب جزئي علىأ.{\displaystyle A.} في الواقع، بالنسبة لأي عناصرx،y،z∈أ،{\displaystyle x,y,z\in A,}

  • x≤x،{\displaystyle x\leq x,}منذx∧x=x{\displaystyle x\wedge x=x}بواسطة ج ؛
  • لوx≤y و y≤x{\displaystyle x\leq y{\text{ and }}y\leq x}ثمx=x∧y=y∧x=y{\displaystyle x=x\wedge y=y\wedge x=y}بواسطة ؛ و
  • لوx≤y و y≤z{\displaystyle x\leq y{\text{ and }}y\leq z}ثمx≤z{\displaystyle x\leq z}.منذ ذلك الحينx∧z=(x∧y)∧z=x∧(y∧z)=x∧y=x{\displaystyle x\wedge z=(x\wedge y)\wedge z=x\wedge (y\wedge z)=x\wedge y=x}بواسطة ب .

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

تكافؤ المناهج

لو(أ،≤){\displaystyle (A,\leq )}هي مجموعة مرتبة جزئياً ، بحيث يكون كل زوج من العناصر فيأ{\displaystyle A}إذا كان هناك لقاء، فبالتأكيدx∧y=x{\displaystyle x\wedge y=x}إذا وفقط إذاx≤y،{\displaystyle x\leq y,}لأنه في الحالة الأخيرة بالفعلx{\displaystyle x}يمثل الحد الأدنى لـx و y،{\displaystyle x{\text{ and }}y,}ومنذ ذلك الحينx{\displaystyle x}تكون القيمة القصوى هي الحد الأدنى إذا وفقط إذا كانت حدًا أدنى. وبالتالي، فإن الترتيب الجزئي المحدد بواسطة التقاطع في منهج الجبر الشامل يتطابق مع الترتيب الجزئي الأصلي.

على العكس من ذلك، إذا(أ،∧){\displaystyle (A,\wedge )}هو شبه شبكة التقاء ، والترتيب الجزئي≤{\displaystyle \,\leq \,}يُعرَّف كما في منهج الجبر الشامل، وz=x∧y{\displaystyle z=x\wedge y}بالنسبة لبعض العناصرx،y∈أ،{\displaystyle x,y\in A,}ثمz{\displaystyle z}هو الحد الأدنى الأكبر لـx و y{\displaystyle x{\text{ and }}y}بالنسبة إلى≤،{\displaystyle \,\leq ,\,}منذ z∧x=x∧z=x∧(x∧y)=(x∧x)∧y=x∧y=z{\displaystyle z\wedge x=x\wedge z=x\wedge (x\wedge y)=(x\wedge x)\wedge y=x\wedge y=z} وبالتاليz≤x.{\displaystyle z\leq x.} بصورة مماثلة،z≤y،{\displaystyle z\leq y,}وإذاw{\displaystyle w}وهو حد أدنى آخر لـx و y،{\displaystyle x{\text{ and }}y,}ثمw∧x=w∧y=w،{\displaystyle w\wedge x=w\wedge y=w,}ومن ثم w∧z=w∧(x∧y)=(w∧x)∧y=w∧y=w.{\displaystyle w\wedge z=w\wedge (x\wedge y)=(w\wedge x)\wedge y=w\wedge y=w.} وبالتالي، يوجد لقاء محدد بالترتيب الجزئي المحدد باللقاء الأصلي، ويتطابق اللقاءان.

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

لقاءات المجموعات الفرعية العامة

لو(أ،∧){\displaystyle (A,\wedge )}إذا كانت الشبكة شبه تقاطع، فيمكن توسيع التقاطع إلى تقاطع مُعرَّف جيدًا لأي مجموعة منتهية غير فارغة ، باستخدام التقنية الموضحة في العمليات الثنائية المتكررة . بدلاً من ذلك، إذا كان التقاطع يُعرِّف أو يُعرَّف بترتيب جزئي، فإن بعض المجموعات الفرعية منأ{\displaystyle A}في الواقع، توجد قيم دنيا فيما يتعلق بهذا، ومن المعقول اعتبار هذه القيمة الدنيا بمثابة نقطة التقاء المجموعة الجزئية. بالنسبة للمجموعات الجزئية المنتهية غير الفارغة، تُعطي الطريقتان النتيجة نفسها، وبالتالي يمكن اعتبار أي منهما تعريفًا لنقطة الالتقاء. في حالة كون كل مجموعة جزئية منأ{\displaystyle A}في الواقع، هناك لقاء.(أ،≤){\displaystyle (A,\leq )}هي شبكة كاملة ؛ لمزيد من التفاصيل، انظر الاكتمال (نظرية الترتيب) .

أمثلة

إذا كانت مجموعة طاقة ما2X{\displaystyle 2^{X}}يتم ترتيبها جزئياً بالطريقة المعتادة (بواسطة⊆{\displaystyle \,\subseteq }ثمّ تكون عمليات الربط عبارة عن اتحادات، واللقاءات عبارة عن تقاطعات؛ بالرموز،∨=∪ و ∧=∩{\displaystyle \,\vee \,=\,\cup \,{\text{ and }}\,\wedge \,=\,\cap \,}(حيث يمكن استخدام تشابه هذه الرموز كوسيلة تذكيرية لتذكر ذلك)∨{\displaystyle \,\vee \,}يشير إلى نقطة الوصل/الحد الأعلى و∧{\displaystyle \,\wedge \,}يشير إلى اللقاء/الآخر [ الملاحظة 1 ] ).

وبشكل أعم، لنفترض أنF≠∅{\displaystyle {\mathcal {F}}\neq \varnothing }هي عائلة من المجموعات الجزئية لمجموعة ماX{\displaystyle X}ذلك مرتبة جزئيا بواسطة⊆.{\displaystyle \,\subseteq .\,} لوF{\displaystyle {\mathcal {F}}}مغلق بموجب اتحادات وتقاطعات تعسفية، وإذاأ،ب،(Fأنا)أنا∈أنا{\displaystyle A,B,\left(F_{i}\right)_{i\in I}}ينتمي إلىF{\displaystyle {\mathcal {F}}}ثم أ∨ب=أ∪ب،أ∧ب=أ∩ب،⋁أنا∈أناFأنا=⋃أنا∈أناFأنا، و ⋀أنا∈أناFأنا=⋂أنا∈أناFأنا.{\displaystyle A\vee B=A\cup B,\quad A\wedge B=A\cap B,\quad \bigvee _{i\in I}F_{i}=\bigcup _{i\in I}F_{i},\quad {\text{ and }}\quad \bigwedge _{i\in I}F_{i}=\bigcap _{i\in I}F_{i}.} لكن إذاF{\displaystyle {\mathcal {F}}}إذا لم يتم إغلاقها بموجب النقاباتأ∨ب{\displaystyle A\vee B}موجود في(F،⊆){\displaystyle ({\mathcal {F}},\subseteq )}إذا وفقط إذا كان هناك حل فريد⊆{\displaystyle \,\subseteq }-الأصغرج∈F{\displaystyle J\in {\mathcal {F}}}بحيثأ∪ب⊆ج.{\displaystyle A\cup B\subseteq J.} على سبيل المثال، إذاF={{1}،{2}،{1،2،3}،R}{\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\mathbb {R} \}}ثم{1}∨{2}={1،2،3}{\displaystyle \{1\}\vee \{2\}=\{1,2,3\}}أما إذاF={{1}،{2}،{1،2،3}،{0،1،2}،R}{\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\{0,1,2\},\mathbb {R} \}}ثم{1}∨{2}{\displaystyle \{1\}\vee \{2\}}لا يوجد لأن المجموعات{0،1،2} و {1،2،3}{\displaystyle \{0,1,2\}{\text{ and }}\{1,2,3\}}هي الحدود العليا الوحيدة لـ{1} و {2}{\displaystyle \{1\}{\text{ and }}\{2\}}في(F،⊆){\displaystyle ({\mathcal {F}},\subseteq )}قد يكون هذا هو الحد الأعلى الأدنى{1}∨{2}{\displaystyle \{1\}\vee \{2\}}لكن{0،1،2}⊈{1،2،3}{\displaystyle \{0,1,2\}\not \subseteq \{1,2,3\}}و{1،2،3}⊈{0،1،2}.{\displaystyle \{1,2,3\}\not \subseteq \{0,1,2\}.} لوF={{1}،{2}،{0،2،3}،{0،1،3}}{\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{0,2,3\},\{0,1,3\}\}}ثم{1}∨{2}{\displaystyle \{1\}\vee \{2\}}غير موجود لأنه لا يوجد حد أعلى لـ{1} و {2}{\displaystyle \{1\}{\text{ and }}\{2\}}في(F،⊆).{\displaystyle ({\mathcal {F}},\subseteq ).}

انظر أيضاً

ملحوظات

  1. 1 2 غراتزر، جورج (21 نوفمبر 2002). نظرية الشبكة العامة: الطبعة الثانية . سبرينغر ساينس آند بيزنس ميديا. ص  52. ISBN 978-3-7643-6996-5.
  2. ↑ هاكتل، غاري د.؛ سومينزي، فابيو (1996). خوارزميات توليف المنطق والتحقق منه . دار نشر كلوير الأكاديمية. ص 88. ISBN  0792397460.
  1. ↑ يمكن تحديد أن القيم العليا والدنيا في هذا المثال البسيط والنموذجي(2X،⊆){\displaystyle (2^{X},\subseteq )}نكون∪ و ∩،{\displaystyle \,\cup \,{\text{ and }}\,\cap \,,}على التوالي. تشابه الرمز∨{\displaystyle \,\vee \,}ل∪{\displaystyle \,\cup \,}و من∧{\displaystyle \,\wedge \,}ل∩{\displaystyle \,\cap \,}وبالتالي يمكن استخدامها كأداة تذكيرية لتذكر أنه في السياق الأكثر عمومية،∨{\displaystyle \,\vee \,}يشير إلى الحد الأعلى (لأن الحد الأعلى هو حد من الأعلى، تمامًا مثلأ∪ب{\displaystyle A\cup B}هو "أعلى"أ{\displaystyle A}وب{\displaystyle B}) بينما∧{\displaystyle \,\wedge \,}يشير إلى الحد الأدنى (لأن الحد الأدنى هو حد من الأسفل، تمامًا مثلأ∩ب{\displaystyle A\cap B}هو "أدناه"أ{\displaystyle A}وب{\displaystyle B}ويمكن استخدام هذا أيضًا لتذكر ما إذا كانت التقاءات/الوصلات تُشار إليها بواسطة∨{\displaystyle \,\vee \,}أو عن طريق∧.{\displaystyle \,\wedge .\,}يشير الحدس إلى أن " ضم " مجموعتين معًا يجب أن ينتج عنه اتحادهماأ∪ب،{\displaystyle A\cup B,}والذي يبدو مشابهاً لـأ∨ب،{\displaystyle A\vee B,}لذا يجب الإشارة إلى "الضم" بواسطة∨.{\displaystyle \,\vee .\,}وبالمثل، يجب أن " تلتقي " مجموعتان عند تقاطعهما.أ∩ب،{\displaystyle A\cap B,}والذي يبدو مشابهاً لـأ∧ب،{\displaystyle A\wedge B,}لذا يجب الإشارة إلى كلمة "meet" بواسطة∧.{\displaystyle \,\wedge .\,}

مراجع