مجموع الطلب

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

في الرياضيات ، الترتيب الكلي أو الترتيب الخطي هو ترتيب جزئي يكون فيه أي عنصرين قابلين للمقارنة. أي أن الترتيب الكلي هو علاقة ثنائية على مجموعة ما ، والتي تلبي الشروط التالية لجميع و في : ${\displaystyle \leq }$ ${\displaystyle X}$${\displaystyle أ،ب}$${\displaystyle c}$${\displaystyle X}$

1. ${\displaystyle a\leq a}$( انعكاسي ).
2. إذا وثم ( متعد ) .${\displaystyle a\leq b}$${\displaystyle b\leq c}$${\displaystyle a\leq c}$
3. إذا وثم ( غير متماثل ) .${\displaystyle a\leq b}$${\displaystyle b\leq أ}$${\displaystyle أ=ب}$
4. ${\displaystyle a\leq b}$أو ( مرتبط بقوة ، كان يسمى سابقًا المجموع).${\displaystyle b\leq أ}$

إن الانعكاسية (1.) تنبع بالفعل من الترابط (4.)، ولكن العديد من المؤلفين يطلبونها صراحةً مع ذلك، للإشارة إلى القرابة مع الرتب الجزئية. ^[1] تُسمى الرتب الكلية أحيانًا أيضًا بالرتب البسيطة ، ^[2] أو المتصلة ، ^[3] أو الرتب الكاملة . ^[4]

المجموعة المزودة بنظام كلي هي مجموعة مرتبة تمامًا ؛ ^[5] تُستخدم أيضًا مصطلحات المجموعة المرتبة ببساطة ، ^[2] المجموعة المرتبة خطيًا ، ^{[3] [5]} والمجموعة غير المرتبة ^{[6] [7] . يُعرَّف مصطلح} السلسلة أحيانًا على أنه مرادف للمجموعة المرتبة تمامًا ، ^[5] ولكنه يشير عمومًا إلى نوع ما من المجموعات الفرعية المرتبة تمامًا لمجموعة مرتبة جزئيًا معينة.

يُطلق على امتداد ترتيب جزئي معين إلى ترتيب كلي اسم الامتداد الخطي لهذا الترتيب الجزئي.

الترتيب الكلي الصارم لمجموعة ما هو ترتيب جزئي صارم حيث يكون أي عنصرين متميزين قابلين للمقارنة. أي أن الترتيب الكلي الصارم هو علاقة ثنائية لمجموعة ما ، والتي تلبي الشروط التالية لجميع و في : ${\displaystyle X}$${\displaystyle X}$ ${\displaystyle <}$ ${\displaystyle X}$${\displaystyle أ،ب}$${\displaystyle c}$${\displaystyle X}$

1. لا ( غير انعكاسي ).${\displaystyle a<a}$
2. إذا لم يكن كذلك ( غير متماثل ).${\displaystyle a<b}$${\displaystyle b<a}$
3. إذا وثم ( متعد ) .${\displaystyle a<b}$${\displaystyle b<c}$${\displaystyle a<c}$
4. إذا ، إذن أو ( متصل ).${\displaystyle a\neq b}$${\displaystyle a<b}$${\displaystyle b<a}$

ينتج عدم التماثل من الانتقالية وعدم الانعكاسية؛ ^[8] وعلاوة على ذلك، ينتج عدم الانعكاسية من عدم التماثل. ^[9]

لأغراض تحديد الحدود، يُطلق أحيانًا على الترتيب الإجمالي كما هو محدد أعلاه ترتيب غير صارم . لكل ترتيب إجمالي (غير صارم) توجد علاقة مرتبطة ، تسمى الترتيب الإجمالي الصارم المرتبط به ، ويمكن تعريفه بطريقتين متكافئتين: ${\displaystyle \leq }$${\displaystyle <}$${\displaystyle \leq }$

• ${\displaystyle a<b}$إذا و ( الاختزال الانعكاسي ).${\displaystyle a\leq b}$${\displaystyle a\neq b}$
• ${\displaystyle a<b}$إن لم يكن ( أي هو المكمل لعكس ) .${\displaystyle b\leq أ}$${\displaystyle <}$${\displaystyle \leq }$

وعلى العكس من ذلك، فإن الإغلاق الانعكاسي للنظام الكلي الصارم هو نظام كلي (غير صارم). ${\displaystyle <}$

• أي مجموعة جزئية من المجموعة المرتبة تمامًا X تكون مرتبة تمامًا لتقييد الترتيب على X.
• الترتيب الفريد للمجموعة الفارغة، ∅ ، هو ترتيب إجمالي.
• أي مجموعة من الأعداد الأساسية أو الأعداد الترتيبية (بشكل أقوى، هذه هي الأعداد ذات الترتيب الجيد ).
• إذا كانت X أي مجموعة و fإذا كانت الدالة الحقنية من X إلى مجموعة مرتبة كليًا، فإن f تحث على ترتيب كلي على X عن طريق وضع x ₁ ≤ x ₂ إذا وفقط إذا كانت f ( x ₁ ) ≤ f ( x ₂ ) .
• إن الترتيب المعجمي للناتج الديكارتي لعائلة من المجموعات المرتبة تمامًا، والمفهرسة بمجموعة مرتبة جيدًا ، هو في حد ذاته ترتيب كلي.
• مجموعة الأعداد الحقيقية المرتبة حسب العلاقات المعتادة "أقل من أو يساوي" (≤) أو "أكبر من أو يساوي" (≥) مرتبة تمامًا. وبالتالي فإن كل مجموعة فرعية من الأعداد الحقيقية مرتبة تمامًا، مثل الأعداد الطبيعية والأعداد الصحيحة والأعداد النسبية . يمكن إظهار أن كلًا منها يمثل "المثال الأولي" الفريد (حتى تماثل الترتيب ) لمجموعة مرتبة تمامًا ذات خاصية معينة، (هنا، يكون الترتيب الكلي A أوليًا لخاصية، إذا كان لدى B الخاصية، كلما كان هناك تماثل ترتيب من A إلى مجموعة فرعية من B ): ^{[10] [ بحاجة لمصدر ]}
  • تشكل الأعداد الطبيعية مجموعة أولية غير فارغة مرتبة بالكامل بدون حد أعلى .
  • تشكل الأعداد الصحيحة مجموعة أولية غير فارغة مرتبة بالكامل بدون حد أعلى أو أدنى .
  • تشكل الأعداد النسبية مجموعة مرتبة كليًا أولية كثيفة في الأعداد الحقيقية. علاوة على ذلك، فإن الاختزال الانعكاسي < هو ترتيب كثيف للأعداد النسبية.
  • تشكل الأعداد الحقيقية مجموعة أولية غير محدودة مرتبة كليًا ومتصلة بطوبولوجيا الترتيب ( الموضحة أدناه).
• الحقول المرتبة هي حقول مرتبة تمامًا بحكم التعريف. وهي تتضمن الأعداد النسبية والأعداد الحقيقية. ويحتوي كل حقل مرتب على حقل فرعي مرتب متماثل مع الأعداد النسبية. وأي حقل مرتب كامل وفقًا لـ Dedekind يكون متماثلًا مع الأعداد الحقيقية.
• يتم ترتيب حروف الأبجدية حسب ترتيب القاموس القياسي ، على سبيل المثال، A < B < C وما إلى ذلك، وهو ترتيب إجمالي صارم.

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

من الأمثلة الشائعة لاستخدام السلسلة للإشارة إلى مجموعات فرعية مرتبة تمامًا هي مبرهنة زورن التي تؤكد أنه إذا كان لكل سلسلة في مجموعة مرتبة جزئيًا X حد أعلى في X ، فإن X تحتوي على عنصر أقصى واحد على الأقل. ^[12] تُستخدم مبرهنة زورن عادةً مع كون X مجموعة من المجموعات الفرعية؛ في هذه الحالة، يتم الحصول على الحد الأقصى من خلال إثبات أن اتحاد عناصر السلسلة في X موجود في X. هذه هي الطريقة المستخدمة عمومًا لإثبات أن فضاء المتجه له قواعد هامل وأن الحلقة لها مثاليات قصوى .

في بعض السياقات، تعتبر السلاسل التي يتم النظر فيها متماثلة الترتيب مع الأعداد الطبيعية بترتيبها المعتاد أو ترتيبها المعاكس . في هذه الحالة، يمكن تحديد السلسلة بتسلسل رتيب ، وتسمى سلسلة تصاعدية أو سلسلة تنازلية ، اعتمادًا على ما إذا كان التسلسل متزايدًا أم متناقصًا. ^[13]

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

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

يمكن أيضًا استخدام "السلسلة" لبعض المجموعات الفرعية المرتبة تمامًا من الهياكل التي ليست مجموعات مرتبة جزئيًا. ومن الأمثلة على ذلك السلاسل المنتظمة من كثيرات الحدود. ومن الأمثلة الأخرى استخدام "السلسلة" كمرادف للمشي في الرسم البياني .

يمكن تعريف المجموعة المرتبة تمامًا على أنها نوع معين من الشبكة ، أي تلك التي لدينا فيها

${\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}}$لجميع أ ، ب .

ثم نكتب a ≤ b إذا وفقط إذا . وبالتالي فإن المجموعة المرتبة تمامًا هي شبكة توزيعية . ${\displaystyle a=a\wedge b}$

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

تشكل المجموعات المرتبة كليًا فئة فرعية كاملة لفئة المجموعات المرتبة جزئيًا ، حيث تكون التشكلات عبارة عن خرائط تحترم الترتيب، أي خرائط f بحيث إذا كانت a ≤ b فإن f ( a ) ≤ f ( b ).

الخريطة التقابلية بين مجموعتين مرتبتين تمامًا والتي تحترم الترتيبين هي تماثل في هذه الفئة.

بالنسبة لأي مجموعة مرتبة تمامًا X، يمكننا تحديد الفواصل المفتوحة

• ( أ ، ب ) = { س | أ < س و س < ب } ،
• (−∞, ب ) = { س | س < ب } ،
• ( أ ، ∞) = { س | أ < س } ، و
• (−∞, ∞) = X .

يمكننا استخدام هذه الفواصل المفتوحة لتحديد طوبولوجيا على أي مجموعة مرتبة، وهي طوبولوجيا الترتيب .

عندما يتم استخدام أكثر من ترتيب واحد على مجموعة، فإننا نتحدث عن طوبولوجيا الترتيب المستحثة بواسطة ترتيب معين. على سبيل المثال، إذا كانت N هي الأعداد الطبيعية، و< أقل من و > أكبر من، فقد نشير إلى طوبولوجيا الترتيب على N المستحثة بواسطة < وطوبولوجيا الترتيب على N المستحثة بواسطة > (في هذه الحالة، قد يكونان متطابقين ولكن ليس بشكل عام).

يمكن إظهار أن طوبولوجيا الترتيب المستحثة بواسطة الترتيب الكلي طبيعية وراثيًا .

يقال إن المجموعة المرتبة تمامًا مكتملة إذا كان لكل مجموعة فرعية غير فارغة لها حد أعلى ، حد أعلى أصغر . على سبيل المثال، مجموعة الأعداد الحقيقية R مكتملة ولكن مجموعة الأعداد النسبية Q ليست كذلك. بعبارة أخرى، لا تنطبق المفاهيم المختلفة للاكتمال (لا ينبغي الخلط بينها وبين كونها "إجمالية") على القيود . على سبيل المثال، على الأعداد الحقيقية، فإن خاصية العلاقة ≤ هي أن كل مجموعة فرعية غير فارغة S من R لها حد أعلى في R لها حد أعلى أصغر (يُسمى أيضًا الحد الأعلى) في R. ومع ذلك، بالنسبة للأعداد النسبية، فإن هذا الحد الأعلى ليس بالضرورة حدًا أعلى، وبالتالي فإن نفس الخاصية لا تنطبق على تقييد العلاقة ≤ للأعداد النسبية.

هناك عدد من النتائج التي تربط خصائص طوبولوجيا الترتيب باكتمال X:

• إذا تم توصيل طوبولوجيا الطلب على X ، فإن X يكون مكتملًا.
• يكون X متصلًا بموجب طوبولوجيا الترتيب إذا وفقط إذا كان مكتملًا ولا توجد فجوة في X (الفجوة هي نقطتان a و b في X مع a < b بحيث لا يوجد c يرضي a < c < b .)
• يكون X كاملاً إذا وفقط إذا كانت كل مجموعة محدودة مغلقة في طوبولوجيا الترتيب مضغوطة.

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

بالنسبة لأي مجموعتين منفصلتين و ، يوجد ترتيب طبيعي في المجموعة ، والذي يسمى مجموع المجموعتين أو في بعض الأحيان فقط : ${\displaystyle (A_{1},\leq _{1})}$${\displaystyle (A_{2},\leq _{2})}$${\displaystyle \leq _{+}}$${\displaystyle A_{1}\cup A_{2}}$${\displaystyle A_{1}+A_{2}}$

بالنسبة لـ ، ينطبق إذا وفقط إذا كان أحد الأمور التالية ينطبق: ${\displaystyle x,y\in A_{1}\cup A_{2}}$${\displaystyle x\leq _{+}y}$

1. ${\displaystyle x,y\in A_{1}}$و${\displaystyle x\leq _{1}y}$
2. ${\displaystyle x,y\in A_{2}}$و${\displaystyle x\leq _{2}y}$
3. ${\displaystyle x\in A_{1}}$و${\displaystyle y\in A_{2}}$

بديهيًا، هذا يعني أن عناصر المجموعة الثانية تضاف إلى عناصر المجموعة الأولى.

بشكل عام، إذا كانت مجموعة الفهرس مرتبة تمامًا، ولكل منها بنية ترتيب خطي، حيث تكون المجموعات منفصلة في أزواج، فإن الترتيب الإجمالي الطبيعي على يتم تعريفه بواسطة ${\displaystyle (I,\leq )}$${\displaystyle i\in I}$${\displaystyle (A_{i},\leq _{i})}$${\displaystyle A_{i}}$${\displaystyle \bigcup _{i}A_{i}}$

بالنسبة لـ ، ينطبق إذا: ${\displaystyle x,y\in \bigcup _{i\in I}A_{i}}$${\displaystyle x\leq y}$

1. إما أن هناك بعض مع${\displaystyle i\in I}$${\displaystyle x\leq _{i}y}$
2. أو هناك بعض في مع ، ${\displaystyle i<j}$${\displaystyle I}$${\displaystyle x\in A_{i}}$${\displaystyle y\in A_{j}}$

نظرية الترتيب الأول للمجموعات الكلية قابلة للحسم ، أي أن هناك خوارزمية لتحديد أي عبارات من الترتيب الأول صالحة لجميع الرتب الكلية. باستخدام قابلية التفسير في S2S ، فإن نظرية الترتيب الثاني الأحادي للمجموعات الكلية القابلة للعد قابلة للحسم أيضًا. ^[16]

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

• الترتيب المعجمي : ( أ ، ب ) ≤ ( ج ، د ) إذا وفقط إذا كان أ < ج أو ( أ = ج وب ≤ د ). وهذا ترتيب كلي.
• ( أ ، ب ) ≤ ( ج ، د ) إذا وفقط إذا كانت أ ≤ ج و ب ≤ د ( ترتيب المنتج ). هذا ترتيب جزئي.
• ( أ ، ب ) ≤ ( ج ، د ) إذا وفقط إذا ( أ < ج وب < د ) أو ( أ = ج وب = د ) (الإغلاق الانعكاسي للضرب المباشر للترتيبات الكلية الصارمة المقابلة). وهذا أيضًا ترتيب جزئي .

يمتد كل ترتيب من هذه الترتيبات إلى الترتيب التالي بمعنى أنه إذا كان لدينا x ≤ y في ترتيب الضرب، فإن هذه العلاقة تنطبق أيضًا على الترتيب المعجمي، وهكذا. يمكن تعريف الثلاثة على نحو مماثل للضرب الديكارتي لأكثر من مجموعتين.

عند تطبيقها على فضاء المتجه R ⁿ ، فإن كلًا مما سبق يجعلها فضاء متجهًا منظمًا .

انظر أيضًا أمثلة للمجموعات المرتبة جزئيًا .

إن الدالة الحقيقية المكونة من n متغير حقيقي محددة على مجموعة فرعية من R ⁿ تحدد ترتيبًا ضعيفًا صارمًا وترتيبًا مسبقًا إجماليًا مقابلًا على تلك المجموعة الفرعية.

العلاقة الثنائية التي هي غير متماثلة، ومتعدية، وانعكاسية (ولكنها ليست بالضرورة كلية) هي علاقة من الدرجة الجزئية .

المجموعة التي لها ترتيب إجمالي متوافق هي مجموعة مرتبة تمامًا .

لا يوجد سوى عدد قليل من الهياكل غير التافهة التي يمكن تعريفها على أنها اختزالات من ترتيب إجمالي. يؤدي نسيان الاتجاه إلى علاقة وسطية . يؤدي نسيان موقع النهايات إلى ترتيب دوري . يؤدي نسيان كلا البيانات إلى علاقة فصل . ^[17]

• بيركهوف، جاريت (1967). نظرية الشبكة . منشورات الندوة. المجلد 25. بروفيدنس: الجمعية الأمريكية للرياضيات.
• Davey, Brian A.; Priestley, Hilary Ann (1990). Introduction to Lattices and Order . Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN  89009753.
• فوكس، ل. (1963). الأنظمة الجبرية المرتبة جزئيًا . مطبعة بيرغامون.
• جورج جراتزر (1971). نظرية الشبكة: المفاهيم الأولى والشبكات التوزيعية. دبليو إتش فريمان وشركاه. ISBN 0-7167-0442-0 
• هالموس، بول ر. (1968). نظرية المجموعة الساذجة . برينستون: نوستراند.
• جون جي هوكينج وجيل إس يونج (1961). الطوبولوجيا. إعادة طبع مصححة، دوفر، 1988. ISBN 0-486-65676-4 
• روسينشتاين، جوزيف ج. (1982). الترتيبات الخطية . نيويورك: أكاديميك بريس.
• شميدت، جونتر ؛ ستروهلين، توماس (1993). العلاقات والرسوم البيانية: الرياضيات المنفصلة لعلماء الكمبيوتر. برلين: دار نشر سبرينغر. رقم ISBN 978-3-642-77970-1.

• "المجموعة المرتبة كليًا"، موسوعة الرياضيات ، EMS Press ، 2001 [1994]