علاقة الترتيب
علاقة الترتيب علاقة ثنائية على مجموعة، وهي انعكاسية وتخالفية ومتعدية.
الدافع
الترتيب مفهوم مألوف نتعامل معه في الحياة اليومية أيضاً. فنستطيع أن نرتّب أشياء كثيرة بطريقة ما: الكلمات أبجدياً، والطلاب في المدرسة بحسب الطول، والبضائع بحسب السعر. وكل ذلك تصفه علاقة الترتيب التي نرمز لها عادةً بالرمز ≤. ومن الرموز المرتبطة بها < و > و ≥، ومعانيها واضحة.
فماذا نتوقع من مثل هذه العلاقة؟ يتضح من الرمز نفسه أنّ العناصر المتساوية ستكون في علاقة الترتيب، فنحن نريد إذن أن نعرّف خواص العلاقة «أصغر من أو يساوي». ولذلك ينبغي أن تكون هذه العلاقة انعكاسية، أي يجب أن يتحقق a ≤ a.
وماذا بعد؟ من المؤكد أنّ التماثل لن يتحقق: فإذا رتّبنا بحسب السعر، وكانت السيارة أرخص من الخبز (فرضاً)، فمن المؤكد أنّ الخبز لن يكون في الوقت نفسه أرخص من السيارة. فماذا نتوقع عموماً لو حدث أنّ a ≤ b و b ≤ a معاً؟ هل لذلك معنى في أي حالة؟ نعم، إذا كان a = b. فالحالة الوحيدة التي لا يهم فيها ترتيب العنصرين في العلاقة هي أن يكون العنصران متساويين، ولذلك فالترتيب تخالفي.
وأخيراً، إذا عرفنا أنّ السيارة أغلى من الخبز، وأنّ الطائرة أغلى من السيارة، فإننا نتوقع أن تكون الطائرة حتماً أغلى من الخبز. وهذا ما يصفه التعدي.
الترتيب الجزئي
ما عرّفناه قبل قليل هو في الحقيقة ترتيب جزئي فقط، وليس ترتيباً كلياً. فلماذا ليس كلياً؟ لنحاول أن نعرّف ترتيباً على المجموعات. فكيف نقارن بين مجموعتين؟
نقول إنّ المجموعة A أصغر من المجموعة B أو تساويها إذا كان A ⊆ B، أي إذا كانت A مجموعة جزئية من B. ولهذا معنى، فإذا كان A = {1, 2} و B = {1, 2, 3}، أمكننا أن نقول إنّ A أصغر، لأنّ B تضم عناصر A نفسها، وتضم فوق ذلك العدد ثلاثة. فيتحقق مثلاً:
- {a, c} ≤ {a, b, c, d}
- ∅ ≤ {5, n, x}
- {x, e, s} ≤ {x, e, s}
لكنّ الصعوبة تظهر عندما نريد أن نقارن بين المجموعتين A = {a, b} و B = {a, c}. فأيتهما الصغرى وأيتهما الكبرى؟ الصعوبة أنّ المجموعتين كلتيهما تضمان العنصر a، لكنّ العنصر الثاني مختلف فيهما. فلا تكون أي منهما مجموعة جزئية من الأخرى، فلا يتحقق A ≤ B ولا B ≤ A. فهاتان المجموعتان غير قابلتين للمقارنة بترتيبنا.
ولذلك نعرّف المجموعة المرتبة كلياً، وتُسمّى أيضاً السلسلة، بأنها المجموعة التي يكون فيها كل عنصرين قابلين للمقارنة. ومن أمثلتها المجموعات العددية مع الترتيب المعتاد. فلكل عددين حقيقيين a و b يمكننا أن نقرر هل a ≤ b أو b ≤ a.
أمثلة من الحياة اليومية
ومن الأمثلة التي لا تستحق فيها المقارنة الترتيب بحسب الطعم، فتعني العلاقة < «أن يكون أقل لذة». فمن المعقول على الأرجح أن نقارن بين ثمرتين من الفاكهة، كأن نقول «التفاح» < «المانجو» بمعنى أنّ المانجو ألذ من التفاح. أو بين نوعين من الخضار: «الجزر» < «الطماطم» بمعنى أنّ الطماطم ألذ من الجزر.
لكنّ المشكلة أنه يصعب أن نقارن بين لذة الفاكهة ولذة الخضار. فهل المانجو ألذ أم الطماطم؟ وهل التفاح أقل لذة أم الجزر؟ من الأفضل ألّا نبحث في ذلك…
وإذا اقتصرنا في المثال الأخير على الفاكهة مثلاً، أمكننا القول إنّ لدينا مجموعة مرتبة كلياً، لأننا نستطيع أن نقارن بين لذة كل أنواع الفاكهة.
العنصر الأصغري والعنصر الأعظمي، وأصغر عنصر وأكبر عنصر
إذا كانت لدينا مجموعة مرتبة M، فإننا نسمّي العنصر min ∈ M عنصراً أصغرياً إذا لم يوجد x ∈ M بحيث يكون x < min. أي أننا لا نستطيع أن نجد عنصراً أصغر من العنصر min.
ونسمّي العنصر max ∈ M عنصراً أعظمياً إذا لم يوجد x ∈ M بحيث يكون x > max. أي أننا لا نستطيع أن نجد عنصراً أكبر منه.
ويختلف هذان المفهومان عن مفهومي أصغر عنصر وأكبر عنصر.
نسمّي العنصر a ∈ M أصغر عنصر إذا تحقق a ≤ x لكل x ∈ M. فأصغر عنصر a أصغر من جميع العناصر الأخرى في المجموعة M أو يساويها.
ونسمّي العنصر b ∈ M أكبر عنصر إذا تحقق b ≥ x لكل x ∈ M. فأكبر عنصر b أكبر من جميع العناصر الأخرى في المجموعة M أو يساويها.
فما الفرق بين أكبر عنصر والعنصر الأعظمي؟ قد يكون هناك أكثر من عنصر أعظمي، لأنّ المجموعة ليست مرتبة كلياً بالضرورة. فإذا عدنا إلى مثال المقارنة بحسب الطعم، أمكننا القول إنّ المانجو ألذ الفاكهة وإنّ الطماطم ألذ الخضار. لكننا لا نستطيع أن نقارن بينهما، فلا نعرف أيهما ألذ: المانجو أم الطماطم.
فكلا العنصرين إذن أعظمي. فلا نستطيع أن نجد شيئاً ألذ من المانجو، فالمانجو ألذ من كل أنواع الفاكهة الأخرى، ولا يمكننا أن نقارنه بالخضار. وكذلك الطماطم، فهي ألذ من كل الخضار، ولا يمكننا أن نقارنها بالفاكهة.
لكنّ أياً منهما ليس أكبر عنصر، أي ليس الألذ بهذا المعنى. فلكي يكون المانجو الألذ (أكبر عنصر)، يجب أن يكون ألذ من كل شيء، بما في ذلك كل الخضار. لكننا قلنا إننا لا نستطيع أن نقارنه بالخضار، ولذلك لا يمكن أن يكون الألذ على الإطلاق، بل هو فقط عنصر أعظمي بلغة نظرية الترتيب.
ومن السهل على الأرجح أن نرى أنه إذا كان للمجموعة أكبر عنصر، فإنّ هذا العنصر أعظمي أيضاً. فإذا كان العنصر a أكبر من جميع العناصر الأخرى في المجموعة (تعريف أكبر عنصر)، فمن المؤكد أننا لن نجد عنصراً أكبر منه (تعريف العنصر الأعظمي).
ومن الأمثلة على مجموعة لها أكبر عنصر وأصغر عنصر الفترة المغلقة [0, 1]. أما إذا أخذنا الفترة نفسها مفتوحة، فلن يكون لها أكبر عنصر ولا أصغر عنصر: (0, 1).
ولو أردنا عدداً لا نهائياً من العناصر الأصغرية، لأمكننا أن نعرّف الترتيب R على النحو الآتي. نعرّف أولاً مجموعات مساعدة Mx على هذه الصورة: لكل x من الفترة (0, 1) نعرّف المجموعة Mx = {y | y = x + n}، حيث n عدد صحيح غير سالب. فنحصل مثلاً على مجموعات مثل:
نعرّف على كل مجموعة Mx الترتيب المعتاد، ونرمز له بالرمز Rx. ثم نوجد في النهاية اتحاد هذه الترتيبات: R = ∪ Rx. فلا نستطيع في هذا الترتيب أن نقارن إلا داخل السلاسل الأصلية. فيمكننا أن نحدد هل 0.5 ≤ 2.5، لكننا لا نستطيع أن نحدد هل 0.5 ≤ 2.7، لأنّ هذين العددين لم يكونا في المجموعة Mx نفسها، ولذلك فالعلاقة بينهما غير معرّفة.
وفي علاقة الترتيب هذه يكون كل عنصر من الفترة (0, 1) عنصراً أصغرياً.
مخططات هاسه
يمكننا أن نرسم المجموعات المرتبة بمخطط هاسه (Hasse). وهو بيان تمثّل رؤوسه عناصر المجموعة، ويدل الضلع بين الرأسين (a, b) على أنّ a < b وأنه لا يوجد c بحيث يكون a < c < b، أي لا يوجد بين العنصرين a و b أي عنصر آخر. ويجب أيضاً أن يكون الرأس a في الرسم أسفل الرأس b. وهذا مثال على مخطط هاسه:
يمثّل مخطط هاسه هذا المجموعة المرتبة {A, B, C, D, E, F}. وفيه يتحقق A < B و B < E، ويتحقق طبعاً أيضاً A < E، لكن لا يوجد ضلع بين هذين الرأسين، لأنه يوجد الرأس B الذي يحقق A < B < E. أما العنصران E و D فغير قابلين للمقارنة، لأنّ أياً منهما ليس فوق الآخر ولا تحته.
ومع أنّ مخططات هاسه تُرسم عادةً بهذا الترتيب الجميل، فهذا ليس ضرورياً على الإطلاق. فيمكن أن يبدو مخطط هاسه السابق أيضاً كما في الشكل الآتي:
ومن الأمثلة الأخرى المجموعة A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}، وهي القواسم الطبيعية للعدد 60. ويمكن تمثيل ترتيبها بحسب قابلية القسمة كما يلي:
يعني الترتيب بحسب قابلية القسمة أنّ (a, b) ∈ R إذا وفقط إذا كان a يقسم b. ونلاحظ من المخطط أنّ فوق كل عدد الأعداد التي يقسمها. فمثلاً فوق العدد 6 الأعداد 12 و 30 و 60، وفوق العدد 4 الأعداد 12 و 20 و 60، وهكذا. أما العدد 3 فليس فوقه العدد 10، لأنه لا يقسمه. وينبغي الانتباه إلى أنّ العدد 10 يقع في الرسم فوق العدد 3، لكن لا يصل إليه أي خط «من الأسفل إلى الأعلى». فإذا تحركنا من العدد 3 إلى الأعلى فقط، أمكننا أن نصل إلى العددين 15 و 6، ومنهما إلى العدد 30. أما العدد 10 فلا نصل إليه إلا بالنزول إلى الأسفل، وهذا غير مسموح.
المحتويات: العلاقات, العمليات على العلاقات, العلاقة الثنائية, العلاقة الثنائية على مجموعة, علاقة التكافؤ, علاقة الترتيب, الشبكات