العلاقات والرسوم البيانية

القسم 2.6 العلاقات والرسوم البيانية

الأهداف

بعد إتمام هذا القسم، ينبغي أن تكون قادرًا على القيام بما يلي.

1. اشرح العلاقة بين الرسم البياني والعلاقة.
2. حدّد ما إذا كانت علاقة ما انعكاسية (reflexive) أو متماثلية (symmetric) أو متعدّية (transitive).
3. استخدم علاقة تكافؤ (equivalence relation) لتقسيم مجموعة، واستخدم التقسيم (partition) لتعريف علاقة تكافؤ.

معاينة القسم

استكشف!

فكّر في الأقراص الدوارة الثلاثة أدناه.

إذا اخترت أنت وصديقك كلٌّ منكما قرصًا مختلفًا ودوّرتمهما، فيمكننا النظر في النتائج التسع الممكنة. فمثلًا، بين القرصين $A$ و$B\text{,}$ تكون النتائج $$\begin{equation*} (2,1), (2,6), (2,8), (4,1), (4,6), (4,8), (9,1), (9,6), (9,8)\text{.} \end{equation*}$$ وهذا يوحي بأن القرص $A$ سيفوز خمس مرات من أصل تسع.

قارن بين تركيبات الأقراص الدوارة الأخرى. أيُّ القرصين هو الأفضل؟

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

ورقة العمل: نشاط تمهيدي

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

1.

سنقول إن العددين بين 1 و31 مرتبطان (related)، ونكتب $a \sim b$، إذا كان الفرق بينهما مضاعفًا للعدد 7. فمثلًا، $3 \sim 24\text{,}$ لأن $24-3 = 3\cdot 7\text{,}$ لكن $3 \not\sim 15$ لأن $15-3 = 12$ وهو ليس مضاعفًا للعدد 7.

(a)

أيُّ ممّا يلي صحيح؟ بمعنى آخر، أيُّ أزواج الأعداد التالية مرتبطة حسب ما عرّفناه أعلاه؟

• $\displaystyle 4\sim 14$
• $\displaystyle 7\sim 14$
• $\displaystyle 10 \sim 17$
• $\displaystyle 17\sim 24$
• $\displaystyle 10\sim 24$
• $\displaystyle 20 \sim 10$
• $\displaystyle 31 \sim 3$
• $\displaystyle 25 \sim 25$

(b)

أيُّ من العبارات التالية صحيح بالنسبة إلى علاقة $\sim$ في هذه الحالة؟

• $a \sim a$ لكل عدد $a$
• $a \not\sim a$ لأي عدد $a$
• لأي عددين $a$ و$b\text{,}$ إذا كان $a \sim b\text{,}$ فإن $b \sim a$
• لأي عددين $a$ و$b\text{,}$ إذا كان $a \sim b$ و$b \sim a\text{,}$ فإن $a = b$
• لأي عددين $a$ و$b\text{,}$ إذا كان $a \sim b$ و$b \sim c\text{,}$ فإن $a \sim c$

(c)

سنكتب $[a]$ للدلالة على مجموعة جميع الأعداد المرتبطة بـ$a\text{.}$ فمثلًا، $[7] = \{7, 14, 21, 28\}\text{.}$ أوجد كلَّ ممّا يلي:

• $[1] =$ ;
• $[2] =$ ;
• $[3] =$ ;
• $[4] =$ ;
• $[5] =$ ;
• $[6] =$ .

هل هناك أعداد تنتمي إلى أكثر من مجموعة واحدة من المجموعات $[a]$ أعلاه؟

• نعم
• لا

2.

عندما تقسم مضاعفًا للعدد 7 على 7 تحصل على عدد صحيح. وإذا قسمت عددًا آخر على 7، فيمكنك إمّا كتابة الناتج على صورة عدد عشري أو على صورة خارج قسمة وباقي. فمثلًا، $19 \div 7$ هو $2$ والباقي 5، لأننا يمكننا كتابة $19 = 2\cdot 7 + 5\text{.}$ ويُسمّى هذا الباقي أيضًا الباقي (modulus). وبرمجة بلغة بايثون (وبلغات أخرى كثيرة) تُكتب عملية الباقي على صورة %. فمثلًا، 19 % 7 هي 5. جرّب ذلك مع بضعة أعداد.

a = 19
print(a % 7)

(a)

أوجد جميع الأعداد $a$ بين 1 و31 التي تحقق $5 \mod 7\text{.}$ بمعنى آخر، أوجد جميع $a$ بحيث a % 7 = 5.

(b)

لأن الباقي (modulus) دالة، فإن لكل عدد باقٍ واحد بالضبط عند القسمة على 7. وهذا يعني أن البواقي تُقسِّم الأعداد من 1 إلى 31: ينتمي كل عدد إلى مجموعة واحدة بالضبط من مجموعات الأعداد ذات باقٍ معيّن. وقد وجدنا بالفعل المجموعة الخاصة بالباقي 5. أوجد المجموعات الأخرى.

• a % 7 = 0: ;
• a % 7 = 1: ;
• a % 7 = 2: ;
• a % 7 = 3: ;
• a % 7 = 4: ;
• a % 7 = 6: .

(c)

يمكننا استخدام البواقي لتعريف علاقة على الأعداد من 1 إلى 31. سنقول إن $a \sim b$ إذا كان a % 7 = b % 7. بمعنى آخر، يعدّ العددان مرتبطين إذا كانا ينتميان إلى المجموعة نفسها من التقسيم الذي وجدناه أعلاه.

أيُّ ممّا يلي صحيح؟ بمعنى آخر، أيُّ أزواج الأعداد التالية مرتبطة بهذه علاقة الباقي؟

• $\displaystyle 4\sim 14$
• $\displaystyle 7\sim 14$
• $\displaystyle 10 \sim 17$
• $\displaystyle 17\sim 24$
• $\displaystyle 10\sim 24$
• $\displaystyle 20 \sim 10$
• $\displaystyle 31 \sim 3$
• $\displaystyle 25 \sim 25$

قسم فرعي: العلاقات عمومًا

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

لنأخذ مثال العلاقة بين الطلاب والحصص، وهي علاقة تتحقق عندما يكون الطالب مسجّلًا في تلك الحصة (في فصل دراسي معيّن). وهذه علاقة بين مجموعتين مختلفتين (الطلاب والحصص). ولو استخدمنا رسمًا بيانيًا لتوضيح هذه العلاقة، لكان الرسم البياني ثنائيًا (bipartite)، لأن الطالبَين لا يكونان مرتبطين ببعضهما أبدًا، والحصتَين لا تكونان مرتبطتين ببعضهما أبدًا.

والرسم البياني هو في الحقيقة مجموعة رؤوس (vertices) ومجموعة حواف (edges): $G = (V, E)\text{;}$ وكل عنصر من عناصر المجموعة $E$ هو مجموعة جزئية ذات عنصرين من $V\text{.}$ وإذا أردنا إبراز ثنائية الرسم البياني، فيمكننا أن نقسم $V$ إلى مجموعتَيْه ونكتب $G = ((A, B), E)\text{.}$ وفي هذا التدوين، ليكون الرسم البياني ثنائيًا نريد أن تكون كل حافة زوجًا $(a,b)$ حيث $a$ عنصر في $A$ و$b$ عنصر في $B\text{.}$ بمعنى آخر، كل حافة عنصر في حاصل الضرب الديكارتي (Cartesian product) لـ$A$ و$B\text{,}$ ويُكتب هكذا $$\begin{equation*} A \times B = \{(a,b) \st a \in A,~b \in B\}. \end{equation*}$$ (وهناك طريقة أخرى لقول ذلك، وهي أن $A \times B$ هي «مجموعة جميع الأزواج المرتّبة من عناصر $A$ و$B\text{.}$»)

ملاحظة 2.6.1.

هناك تفصيل دقيق هنا ينبغي أن نشير إليه: الرسم البياني الثنائي (bipartite graph) الذي وصفناه له في الحقيقة حواف موجّهة (directed edges) من $A$ إلى $B$، لأننا ننظر في أزواج مرتّبة (ordered). وتعريفنا للرسم البياني يجعل الحواف مجموعات جزئية غير مرتّبة من الرؤوس، والمجموعات الجزئية غير مرتّبة. ما دام $A$ و$B$ مجموعتين متباعدتين، فلا لبس هنا، لكننا سنرى علاقات تشترك فيها $A$ و$B$ في بعض العناصر، ومع ذلك يهمنا الترتيب. وسنتحدث عن ذلك بعد قليل.

وهذا المثال يوضّح تمامًا ما هي العلاقة الثنائية العامة (binary relation). وفيما يلي تعريف دقيق لها.

تعريف 2.6.2.

العلاقة الثنائية (binary relation) هي مجموعة من الأزواج المرتّبة. ونقول إن العلاقة الثنائية علاقة على المجموعتين $A$ و$B$ بشرط أن تكون الأزواج المرتّبة مجموعة جزئية من $A \times B\text{.}$ ونقول إن العلاقة الثنائية علاقة على مجموعة $A$ بشرط أن تكون الأزواج المرتّبة مجموعة جزئية من $A \times A\text{.}$

لاحظ أن $A \times A$ هو ببساطة مجموعة جميع الأزواج المرتّبة التي إحداثيّاه كلاهما عناصر من $A\text{.}$

مثال 2.6.3.

لتكن $A$ مجموعة من الطلاب، و$B$ مجموعة من الحصص. لنقل $A = \{\text{Al, Bob, Cat, Dirk, Eva}\}$ و$B = \{\text{Calculus, Discrete, Statistics}\}\text{.}$ جميع الطلاب ما عدا Dirk مسجّلون في Calculus، وBob وEva يسجّلان في Discrete، وAl وCat وDirk يسجّلون في Statistics.

يمكننا تعريف علاقة $T$ بـ«يسجّل في» (is taking) على $A$ و$B$، وهي تتحقق بين طالب وحصة تحديدًا إذا كان ذلك الطالب يسجّل في تلك الحصة. اكتب هذه العلاقة كمجموعة جزئية من $A\times B$، وارسم رسمها البياني الثنائي.

الحل. لكتابة العلاقة بدقة، كل ما علينا هو إعطاء مجموعة الأزواج المرتّبة: $$\begin{align*} T = \{\amp (\text{Al}, \text{Calculus}), (\text{Al}, \text{Statistics}),\\ \amp (\text{Bob}, \text{Calculus}), (\text{Bob}, \text{Discrete})\\ \amp (\text{Cat}, \text{Calculus}), (\text{Cat}, \text{Statistics})\\ \amp (\text{Dirk}, \text{Statistics})\\ \amp (\text{Eva}, \text{Calculus}), (\text{Eva}, \text{Discrete})\} \end{align*}$$ ويمكننا رسم هذه العلاقة كرسم بياني ثنائي:

!

مثال 2.6.4.

لتكن $M$ العلاقة «مضاعف لـ» (is a multiple of) على المجموعة $A = \{1,2,3,4,5,6\}\text{.}$ اكتبها على صورة مجموعة من الأزواج المرتّبة. هل تُنشئ هذه العلاقة رسمًا بيانيًا؟

الحل. لنفكّر أولًا في العناصر التي ينبغي أن تكون مرتبطة وتلك التي لا ينبغي. فنحن نعلم أن $6$ مضاعف للعدد $2\text{,}$، إذن العلاقة تتحقق بالنسبة إلى الزوج $(6,2)\text{,}$ لكن $6$ ليس مضاعفًا للعدد $4\text{,}$، إذن الزوج $(6,4)$ لا يحقق العلاقة. وبأدق صورة، نقول إن $(6,2) \in M$ لكن $(6,4) \notin M\text{.}$

لنسرد جميع عناصر $M\text{:}$ $$\begin{align*} M = \{\amp(1,1), (2,1), (2,2), (3,1), (3,3), (4,1), (4,2), (4,4), \\ \amp (5,1), (5,5), (6,1), (6,2) (6,3), (6,6)\}\text{.} \end{align*}$$ وهذه العلاقة ليست رسمًا بيانيًا لسببين: أولًا، العناصر مرتبطة بأنفسها؛ وثانيًا، ترتيب العناصر في العلاقة ليس متماثلًا ($6$ مرتبط بـ$2\text{,}$ لكن $2$ ليست مرتبطة بـ$6\text{,}$ على سبيل المثال).

لكن يمكننا مع ذلك أن نرسم شيئًا يشبه الرسم البياني لتوضيح هذه العلاقة: وبما أن اتجاه العلاقة مهم، سيكون لدينا حواف موجّهة. وهذا وحده سيعطينا رسمًا بيانيًا موجّهًا. ولأن الرؤوس يمكن أن يكون لها حواف تعود إلى نفسها، فإننا نسمّي هذه البنية رسمًا متعدد الحواف (multigraph)، ولذلك يمكن تصوّر العلاقة على أنها رسم متعدد موجّه.

!

العلاقة الثنائية $R$ على المجموعتين $A$ و$B$ يمكن دائمًا «قلبها» لتنتج علاقة على المجموعتين $B$ و$A\text{.}$ بمعنى آخر، تصف $R$ كيف تكون الأشياء في $A$ مرتبطة بالأشياء في $B\text{;}$ والأشياء في $B$ مرتبطة بالأشياء في $A\text{,}$ ولكن بطريقة عكسية (إلى الوراء). وسنسمّي هذه العلاقة الجديدة العلاقةَ العكسية (inverse) لـ$R\text{.}$

تعريف 2.6.5.

لتكن $R\text{,}$ علاقة ثنائية، نعرّف $R\inv$ لتكون العلاقةَ العكسية لـ$R$ على هيئة المجموعة $$\begin{equation*} R\inv = \{(b,a) \st (a,b) \in R\}\text{.} \end{equation*}$$

كانت العلاقة $T$ في مثال 2.6.3 تقول إن طالبًا بعينه مسجّل في حصة بعينها. أما العلاقة العكسية $T\inv$ فتقول إن حصة بعينها فيها طالب بعينه. فمثلًا، $(\text{Calculus}, \text{Al})$ عنصر في $T\inv\text{.}$ ورسوميًا، لن يكون هناك فرق في الصورة، وإن كان بإمكاننا وضع مجموعة الحصص في الأعلى والطلاب في الأسفل.

أما العلاقة $M$ في مثال 2.6.4 فقد أعطتنا أن $6$ مضاعف للعدد $2\text{,}$ لأن $(6,2) \in M\text{.}$ وأما العلاقة العكسية، لدينا $(2,6) \in M\inv\text{,}$ أي إن $2$ عامل قاسم للعدد $6\text{.}$ وقد مثلنا في هذا المثال علاقةً برسم متعدد موجّه. وسيبدو رسم العلاقة العكسية مطابقًا تمامًا، لكن جميع الأسهم ستشير في الاتجاه المعاكس.

وهناك طريقة أخرى لإنشاء علاقة جديدة، وهي دمج علاقتين. فلنفترض أننا إلى جانب علاقة «يسجّل في» الواردة في مثال 2.6.3 نعرّف علاقة «يُدرَّس بواسطة» (is taught by) التي تطابق كل مقرر مع مُدرِّسه. ربما يدرّس الأستاذ X مقرر Calculus. في هذه الحالة، بما أن Al يسجّل في Calculus وأن Calculus يُدرَّسه الأستاذ X، يمكننا أن نستنتج أن Al يسجّل في مقرر مع الأستاذ X.

تعريف 2.6.6.

لتكن $R$ علاقة من المجموعة $A$ إلى $B$، و$S$ علاقة من $B$ إلى $C\text{.}$ تركيب (composition) $R$ و$S$ هو $$\begin{equation*} S \circ R = \{(a,c) \in A \times C \st (a,b) \in R \text{ and } (b,c) \in S \text{ for some } b \in B\} \end{equation*}$$

لاحظ الترتيب الذي كتبنا به العلاقتين: هو $S \circ R\text{,}$ وليس $R \circ S\text{.}$ والسبب في ذلك (قد يبدو معكوسًا) أنه يتفق مع التدوين المعتاد لتركيب الدوال. والدوال ليست إلا نوعًا خاصًا من العلاقات!

مثال 2.6.7.

اكتب العلاقة $P \circ T\text{,}$ أي تركيب العلاقتين في مثال 2.6.3 و$P = \{(\text{Calculus}, \text{Prof X}), (\text{Discrete}, \text{Prof L}), (\text{Statistics}, \text{Prof X}), (\text{Statistics}, \text{Prof S})\} \text{.}$ لاحظ أننا نقول هنا إن مقرر الإحصاء يُدرّسانه الأستاذان X وS معًا.

الحل. العلاقة التي نبحث عنها هي علاقة بين الطلاب والأساتذة. يمكننا أن نبدأ بكل عنصر من عناصر $T$ وأن نمدّه باتباع المقرر حتى الأستاذ (أو الأساتذة) عبر $P\text{.}$ فمثلًا، لنبدأ بـCat، ولاحظ أن $(\text{Cat}, \text{Calculus}) \in T\text{.}$ والآن انظر ممَّ يرتبط Calculus عبر $P\text{:}$ $(\text{Calculus}, \text{Prof X}) \in P \text{.}$ وبذلك يمكننا ضمّهما معًا للاستنتاج أن $(\text{Cat}, \text{Prof X}) \in P \circ T\text{.}$

ويكمن نهج بديل في أن نكتفي بالنظر في أي أزواج من الطلاب والأساتذة يرتبط مقرّر مشترك. فهل ينبغي أن يكون الزوج $(\text{Al}, \text{Prof L})$ عنصرًا في التركيب؟ لا، لأنه لا يوجد مقرر يسجّل فيه Al ويدرّسه الأستاذ L في آنٍ واحد. وعلى العكس من ذلك، يمكننا أن نستنتج $(\text{Al}, \text{Prof X}) \in P \circ T$ لأن هناك مقررًا مشتركًا. وفي الواقع، يمكن أن يكون المقرر المشترك هو Calculus أو Statistics (فلا يهم عدد الخطوات الوسيطة المشتركة، ما دام هناك واحدة على الأقل).

وهذه هي العلاقة الكاملة: $$\begin{align*} P \circ T = \{\amp (\text{Al}, \text{Prof X}), (\text{Al}, \text{Prof S}), (\text{Bob}, \text{Prof X}), (\text{Bob}, \text{Prof L}), \\ \amp (\text{Cat}, \text{Prof X}), (\text{Cat}, \text{Prof S}), (\text{Dirk}, \text{Prof X}), (\text{Dirk}, \text{Prof S}),\\ \amp (\text{Eva}, \text{Prof X}), (\text{Eva}, \text{Prof L})\} \end{align*}$$

وغالبًا ما يحدث شيء مثير للاهتمام عندما تُركَّب علاقة مع عاكستها. ربما تكون قد رأيت شيئًا كهذا بالنسبة إلى الدوال في التفاضل أو الجبر: $f(x) = e^x$ لها دالة عكسية $f\inv(x) = \ln(x)\text{,}$ ونعرف أن $f(f\inv(x)) = e^{\ln(x)} = x\text{.}$ لكن الدوال علاقات يتمتع فيها كل «مُدخَل» بمُخرَج واحد بالضبط، لذا ليس من المستغرب أن يعطي التركيب مع العاكس دالةَ الهوية فحسب. أما إذا كان للمُدخلات عدة مخرجات، وللـمخرجات عدة مُدخلات، فنحصل على شيءٍ أكثر.

مثال 2.6.8.

صِف العلاقة $T\inv \circ T$ (باستخدام علاقتنا المألوفة $T$ من مثال 2.6.3). وماذا يخبرنا هذا عن الطلاب والحصص؟

الحل. باتباع العلاقة، يمكننا أن نبدأ بأن نقول إن Al في Calculus وأن Calculus يدرسها Al، إذن Al مرتبط بـAl. لكن أيضًا، يدرس Bob مقرر Calculus، إذن أصبح Al مرتبطًا أيضًا بـBob. فهل Bob مرتبط بـAl أيضًا؟ نعم، بما أن Bob يسجّل في Calculus وأن Calculus يدرسها Al.

يخبرنا التركيب بأي أزواج من الطلاب تشترك في مقرر واحد على الأقل. وهذه تكاد تكون كل أزواج الطلاب، باستثناء أن Dirk غير مرتبط بـBob أو Eva، لأنهما لا يسجّلان في Statistics، وذاك هو المقرر الوحيد الذي يسجّل فيه.

وبدلًا من كتابة العلاقة (والتي ستكون تقريبًا كل $A \times A$)، إليك التمثيل البياني.

ورغم أننا رسمنا هنا رسمًا متعددًا موجّهًا، فإن الأسهم المتجهة في الاتجاهين تعني أننا كان بإمكاننا أن نرسم رسمًا متعددًا فحسب.

قسم فرعي: صفات العلاقات

من هذه النقطة فصاعدًا، سننظر في العلاقات على مجموعة واحدة فحسب (أي من مجموعة إلى نفسها). ولتسهيل فهم هذه العلاقات، فلننظر في بعض الصفات الأساسية التي قد تتسم بها العلاقة أو لا تتسم بها.

تعريف 2.6.9. انعكاسية وتماثلية ومتعدّية.

لتكن $R$ علاقة على المجموعة $A\text{.}$ نقول:

• $R$ انعكاسية (reflexive) بشرط أن $(a,a) \in R$ لكل $a \in A\text{.}$
• $R$ متماثلية (symmetric) بشرط أن، لكل $a, b \in A\text{,}$ إذا كان $(a,b) \in R$ فإن $(b,a) \in R\text{.}$
• $R$ متعدّية (transitive) بشرط أن، لكل $a, b,c \in A\text{,}$ إذا كان $(a,b) \in R$ و$(b,c) \in R\text{,}$ فإن $(a,c)\in R\text{.}$

لندرس كلًّا من هذه الصفات بعناية.

ومن المفيد أن نأخذ في أثناء ذلك بعض الأمثلة المعيارية لعلاقات على مجموعات. وستُكتب معظم العلاقات التي سننظر فيها هنا باستخدام التدوين الإنفيلي (infix)، أي أننا نضع رمز العلاقة بين الشيئين اللذين تربطهما. فمثلًا، تُكتب علاقة أصغر من (less than) عادةً على صورة $2 \lt 6$ بدلًا من كتابة $(2,6) \in \lt\text{.}$

مثال 2.6.10. علاقات انعكاسية وغير انعكاسية.

تكون العلاقة انعكاسية عندما يكون كل عنصر مرتبطًا بنفسه. والعلاقات التالية انعكاسية:

• علاقة «أصغر من أو يساوي» (less-than-or-equal-to) على أي مجموعة أعداد. هل من الممكن أن يكون $3 \le 3\text{?}$ والأهم من ذلك: هل كل عدد لا أكبر من نفسه؟ وبما أن الإجابة نعم، فإن هذه العلاقة انعكاسية.
• علاقة «ضمن 3» (within 3)، التي تتحقق بين العددين $a$ و$b$ بشرط $|a-b| \le 3\text{.}$ ولإثبات أن هذه العلاقة انعكاسية، نلاحظ ببساطة أن $|a-a| = 0 \le 3\text{.}$
• علاقة «مضاعف لـ» (is a multiple of) من مثال 2.6.4. ولاحظ أن الرسم المتعدد الموجّه الخاص بهذه العلاقة كانت له حلقات (loops) عند كل رأس.

لكن هذه العلاقات ليست انعكاسية:

• علاقة «يجمع إلى الصفر» (sums to zero)، التي تتحقق على العددين $a$ و$b$ إذا كان $a+b = 0\text{.}$ ولاحظ أن $0 + 0 = 0\text{,}$ ومن ثم فإن $(0,0)$ عنصر في العلاقة، لكن كل عدد آخر غير مرتبط بنفسه.
• أي علاقة يصفها رسم بياني. تذكّر أن الرسوم البيانية لا يمكن أن يكون لها حواف تعود إلى رأس واحد، إذن علاقة الحواف على رسم بياني ليست انعكاسية. (أما الرسم المتعدد فقد يكون انعكاسيًا أو لا).

فإن لم يكن أي عنصر مرتبطًا بنفسه (كما في علاقة الحواف لرسم بياني)، فإننا نسمّي العلاقةَ غيرَ انعكاسية (irreflexive). وبطبيعة الحال، بعض العلاقات لا انعكاسية ولا غير انعكاسية.

والتحقق من انعكاسية علاقة نسبيًا سهل. أما الصفتان الأخرى فتُصاغان على صورة مسلمات (implications)، مما يجعلهما أعقد قليلًا.

مثال 2.6.11. علاقات متماثلية وغير متماثلية.

جوهر الأمر، أن العلاقات المتماثلية هي التي تعمل «في الاتجاهين». وبأدق صورة، إذا كان $a$ مرتبطًا بـ$b\text{,}$ فإن $b$ مرتبط أيضًا بـ$a\text{.}$

والعلاقات التالية متماثلية.

• علاقة «ضمن 3»: إذا كان $|a-b| \le 3$ فإن $|b-a| \le 3\text{.}$
• علاقة «يجمع إلى الصفر»: إذا كان $a+b = 0\text{,}$ فمن المؤكد أن $b + a = 0\text{.}$
• لأي رسم بياني، علاقة الحواف متماثلية. وبطبيعة الحال، بالنسبة إلى الرسوم الموجّهة فإن هذا ليس صحيحًا عادةً.

ومن ناحية أخرى، هذه العلاقات ليست متماثلية.

• $\le$ ليست متماثلة. فكل ما نحتاج إليه لإثبات أن علاقة ليست متماثلة هو أن نجد $a$ و$b$ بحيث $a \le b$ لكن $b \not\le a\text{.}$ حسنًا، $3 \le 4\text{,}$ لكن $4 \not\le 3\text{.}$ وقد ثبت ذلك.
• علاقة «مضاعف لـ» ليست متماثلية. $6$ مضاعف للعدد $2$ لكن $2$ ليس مضاعفًا للعدد $6\text{.}$

والعلاقات التي ليست متماثلية قد تكون في الواقع لا-تماثلية (antisymmetric)، أي أن العناصر الوحيدة التي يوجد فيها كل من $(a,b)$ و$(b,a)$ في العلاقة هي تلك التي $a = b\text{.}$ ولاحظ أن هناك علاقات ليست متماثلية ولا لا-تماثلية.

وباستخدام لغة العلاقات العكسية، تكون العلاقة متماثلية إذا وفقط إذا كانت العلاقة مساوية لعاكستها.

مثال 2.6.12. علاقات متعدّية وغير متعدّية.

إذا كان $a$ مرتبطًا بـ$b\text{,}$ وكان $b$ مرتبطًا بـ$c\text{,}$ فهل يعني ذلك أن $a$ مرتبط بـ$c\text{?}$ وإذا كان هذا صحيحًا مهما كان $a\text{,}$ و$b\text{,}$ و$c$، فإننا نقول إن العلاقة متعدّية.

وهذه بعض العلاقات المتعدّية.

• $\le\text{.}$ لنفترض أن $a \le b$ و$b \le c\text{.}$ إذن من الواضح أن $a \le c\text{.}$
• علاقة «مضاعف لـ». وهذه علاقة جيدة لكتابة برهان لها: لنفترض أن $a$ مضاعف للعدد $b$ وأن $b$ مضاعف للعدد $c\text{.}$ إذن $a = bk$ لعدد صحيح $k$ و$b = cj$ لعدد صحيح $j\text{.}$ وبالتعويض، $a = cjk\text{,}$ ومن ثم فإن $a$ مضاعف للعدد $c\text{.}$

لكن العلاقات التالية ليست متعدّية.

• علاقة «ضمن 3» ليست متعدّية. فكل ما نحتاج إليه هو إيجاد ثلاثة أعداد لا تحقق الشرط. وماذا عن $1\text{,}$ $3\text{,}$ و$5\text{?}$ هنا $1$ ضمن 3 من $3\text{,}$ و$3$ ضمن 3 من $5\text{,}$ لكن $|1 - 5| = 4$، إذن العلاقة لا تتحقق بالنسبة إلى $(1,5)\text{.}$
• علاقة «يجمع إلى الصفر» ليست متعدّية. لاحظ أننا لم ندّعَ قط أن $a\text{,}$ و$b\text{,}$ و$c$ يجب أن تكون أعدادًا مختلفة. لنأخذ $a = 5\text{,}$ و$b = -5\text{,}$ و$c = 5\text{.}$ إذن $a+b = 0$ و$b + c = 0\text{,}$، ومن ثم فإن العلاقة تتحقق بالنسبة إلى $(a,b)$ و$(b,c)\text{.}$ لكن $a + c = 10$، إذن العلاقة لا تتحقق بالنسبة إلى $(a,c)\text{.}$

قد تكون علاقة الحواف في رسم بياني متعدّية، وقد لا تكون. فكيف سيبدو رسم بياني إذا كانت علاقة حوافه متعدّية؟

قسم فرعي: علاقات التكافؤ

الآن سنفعل شيئًا نموذجيًا جدًّا في الرياضيات: سننظر في أكثر أنواع العلاقات شيوعًا، ونفحص ما لها من صفات، ثم نصنّف العلاقات الأخرى التي لها هذه الصفات بدورها على أنها فئة خاصة من العلاقات.

والعلاقة التي نعرفها أكثر من غيرها هي المساواة. فما صفات العلاقات التي تمتلكها علاقة المساواة؟ فمن البدهي أن كل شيء مساوٍ لنفسه، إذن المساواة انعكاسية (reflexive). وإذا كان $a = b\text{,}$ فإن $b = a\text{,}$ إذن المساواة متماثلية (symmetric). وإذا كان $a = b$ و$b = c\text{,}$ فإن $a = c\text{,}$ إذن المساواة متعدّية (transitive).

فما العلاقات الأخرى الانعكاسية والمتماثلية والمتعدّية؟ إنها بالضبط تلك العلاقات التي تتصرف كما تتصرف المساواة. ونسمّي هذه العلاقات علاقاتَ تكافؤ (equivalence relations).

تعريف 2.6.13. علاقة التكافؤ.

تُسمّى العلاقةُ التي تكون انعكاسية ومتماثلية ومتعدّية علاقةَ تكافؤ (equivalence relation).

ملاحظة 2.6.14.

مثال آخر على نوع من العلاقات يُذاكَر بنموذج علاقة كلاسيكية هو الترتيب الجزئي (partial order). وهذه علاقة انعكاسية ولا-تماثلية (antisymmetric) ومتعدّية، تمامًا مثل علاقة «أصغر من أو يساوي». ولعلّك لاحظت بالفعل أن علاقة الاحتواء (subset)، المكتوبة $\subseteq\text{,}$، تبدو كثيرًا مثل $\le\text{.}$ وهذا لأن $\subseteq$ أيضًا ترتيب جزئي. وكذلك علاقة «مضاعف لـ» التي رأيناها أعلاه.

وهناك أشياء كثيرة مثيرة للاهتمام يمكننا قولها عن الترتيبات الجزئية والمجموعات التي ترتّبها ترتيبًا جزئيًا، وتُسمّى المجموعاتُ المرتّبةُ جزئيًا (partially ordered sets) أو PoSets. في وقت آخر.

لم تكن أيٌّ من الأمثلة التي نظرنا فيها حتى الآن في هذا القسم علاقةَ تكافؤ، لكنها حاضرة في كل مكان من الرياضيات. وهي شائعة لدرجة أنه من السهل تجاهلها على أنها ليست شيئًا يستحق الحديث عنه أصلًا. فلنرَ بعض الأمثلة.

مثال 2.6.15.

أثبت أن العلاقة $\equiv_2\text{,}$ التي تتحقق بين عددين صحيحين إذا كان الفرق بينهما زوجيًا، هي علاقة تكافؤ. بمعنى آخر، $a \equiv_2 b$ إذا وفقط إذا كان $b-a = 2k$ لعدد صحيح $k\text{.}$

الحل. كل ما علينا هو التحقق من الصفات الثلاث المطلوبة.

1. $\equiv_2$ انعكاسية: لأي عدد صحيح $a\text{,}$ لدينا $a - a = 0$ و$0 = 2k$ مع $k = 0\text{,}$ إذن $a \equiv_2 a\text{.}$
2. $\equiv_2$ متماثلية: لنثبّت عددين صحيحين $a$ و$b\text{,}$ ونفترض أن $a \equiv_2 b\text{.}$ وهذا يعني أن $b-a = 2k$ لعدد صحيح $k\text{.}$ فماذا عن $a - b\text{?}$ حسنًا، لدينا $a-b = 2(-k)\text{,}$ و$-k$ عدد صحيح، إذن لدينا $b \equiv_2 a\text{.}$
3. $\equiv_2$ متعدّية: لنثبّت أعدادًا صحيحة $a\text{,}$ $b\text{,}$ و$c$ ونفترض أن $a \equiv_2 b$ و$b \equiv_2 c\text{.}$ وهذا يعني أن $b-a = 2k$ و$c-b = 2j$ لأعداد صحيحة $k$ و$j\text{.}$ فماذا عن $c - a\text{?}$ حسنًا، $$\begin{equation*} c - a = (c- b) + (b - a) = 2k+2j = 2(k+j)\text{.} \end{equation*}$$ وبما أن $k+j$ عدد صحيح، نرى أن $a \equiv_2 c$ كما هو مطلوب.

مثال 2.6.16.

لنسمِّ رسمين بيانيين «متكافئَي التدرّج» (degree-sequence-equivalent) إذا كان لهما تسلسل الدرجات نفسه. هل هذه علاقة تكافؤ؟

الحل. نعم هي كذلك. فمن الواضح أن كل رسم بياني له تسلسل الدرجات نفسه الذي له، إذن العلاقة انعكاسية. وإذا كان لدى $G_1$ تسلسل الدرجات نفسه الذي لدى $G_2\text{,}$ فإن لدى $G_2$ تسلسل الدرجات نفسه الذي لدى $G_1\text{,}$ إذن العلاقة متعدّية. وأخيرًا، إذا كان لدى $G_1$ تسلسل الدرجات نفسه الذي لدى $G_2\text{,}$ ولدى $G_3\text{,}$ نفس تسلسل الدرجات فإنها جميعًا لها تسلسل الدرجات نفسه، ومن ثم فإن لدى $G_1$ تسلسل الدرجات نفسه الذي لدى $G_3$ (أي إن العلاقة متعدّية).

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

قسم فرعي: أصناف التكافؤ والتقسيمات

بالنظر إلى أي علاقة $R\text{,}$ يمكننا النظر في مجموعة العناصر المرتبطة بعنصر بعينه. بالنسبة إلى علاقة «يسجّل في»، يمكننا أن نسأل: ما الحصص التي يسجّل فيها Al (أي الحصص المرتبطة بـAl). وبالنسبة إلى «مضاعف لـ»، يمكننا أن نسأل: أي الأعداد التي يكون 6 مضاعفًا لها. وإحدى طرائق دراسة العلاقة هي دراسة مجموعات الأشياء المرتبطة بكل عنصر.

تعريف 2.6.17.

لتكن $R$ علاقة على المجموعة $A\text{,}$ وليكن $a$ عنصرًا في $A\text{.}$ صنفُ العلاقة (relation class) للعنصر $a\text{,}$ والمكتوب $[a]$، هو مجموعة جميع العناصر $b$ التي تحقق $(a,b) \in R$ (أي مجموعة العناصر $b$ المرتبطة بـ$a$ بواسطة $R$). بمعنى آخر، $$\begin{equation*} [a] = \{b \in A \st (a,b) \in R\}\text{.} \end{equation*}$$

وحين تكون $R$ علاقة تكافؤ، فإننا نسمّي أصنافَ العلاقات أصنافَ تكافؤ (equivalence classes).

مثال 2.6.18.

أوجد أصناف العلاقة «مضاعف لـ» على المجموعة $A = \{1,2,3,4,5,6\}\text{.}$

الحل. ستكون هناك ستة أصناف للعلاقة، إذن لكل عنصر صنف علاقة. وهي: $$\begin{align*} [1] = \amp \{1\}\\ [2] = \amp \{1,2\}\\ [3] = \amp \{1,3\}\\ [4] = \amp \{1,2,4\}\\ [5] = \amp \{1,5\}\\ [6] = \amp \{1,2,3,6\}. \end{align*}$$ فمثلًا، وجدنا $[4]$ بالنظر في جميع الأزواج $(4,b)$ التي تحقق العلاقة: 4 مضاعف لـ1 و2 و4، ومن ثمّ هذه هي القيم الممكنة لـ$b$ التي وجدناها.

ارجع إلى الرسم المتعدد الموجّه لهذه العلاقة المعروض في حل مثال 2.6.4. فما أصناف العلاقة؟ إنها لا شيء سوى جيران كل رأس (حيث تعني الجارة أنك تتبع الأسهم في الاتجاه الصحيح).

مثال 2.6.19.

أوجد أصناف التكافؤ للعلاقة $\equiv_2$ على الأعداد الصحيحة.

الحل. لا! فمجموعتنا لا نهائية، إذن سيكون لدينا عدد لا نهائي من أصناف العلاقة؟ لكن لنبدأ إذن...

ما الأعداد المرتبطة بالعدد 1؟ تذكّر أننا نريد أعدادًا صحيحة يكون فرقها عن 1 مضاعفًا للعدد 2. إذن 3 بالتأكيد. أيضًا 5، و7، و-1، و-3، و... جميع الأعداد الفردية؟ نعم، لأن الفرق بين أي عددين فرديين زوجي. ويمكننا أيضًا أن نقول إن الفرق بين أي عددين زوجيين زوجي، ومن ثم فإن صنف التكافؤ للعدد 2 سيحتوي على جميع الأعداد الزوجية. وحتى الآن لدينا: $$\begin{align*} [1] = \amp \{\ldots, -3, -1, 1, 3, 5, \ldots\}\\ [2] = \amp \{\ldots, -4, -2, 2, 4, 6, \ldots\} \end{align*}$$

وفي الواقع، أعتقد أننا انتهينا. فبينما $[3]\text{,}$ و$[4]\text{,}$ و$[5]\text{,}$ وما إليها أصناف تكافؤ صحيحة تمامًا، فإن العناصر المرتبطة بـ$3$ ستكون تمامًا العناصر المرتبطة بـ$1\text{,}$ لأن $1 \equiv_2 3\text{.}$ وذلك لأن العلاقة متعدّية! فإذا كان $3 \equiv_2 b\text{,}$ فنحن نعلم أن $1 \equiv_2 b\text{.}$

إذن لدينا صنفا تكافؤ بالضبط. ينتمي كل عدد صحيح إلى واحد من صنفَي التكافؤ هذين بالضبط، وصنف التكافؤ لأي عدد صحيح هو بالضبط الصنف الذي ينتمي إليه.

افحص المثالين أعلاه بعناية. فبالنسبة إلى علاقة «مضاعف لـ»، وهي ليست علاقة تكافؤ، تنتمي بعض العناصر إلى أكثر من صنف علاقة واحد (مختلف). لكن بالنسبة إلى $\equiv_2\text{,}$ وهي علاقة تكافؤ، ينتمي كل عنصر إلى صنف تكافؤ واحد بالضبط. وهذا ليس مصادفة. ولنفهم هذا، سنعرّف مصطلحًا جديدًا.

تعريف 2.6.20.

بالنظر إلى مجموعة $A\text{,}$ غير الفارغة، فإن التقسيم (partition) لـ$A$ هو مجموعة $P$ من المجموعات الجزئية غير الفارغة لـ$A$ بحيث ينتمي كل عنصر من عناصر $A$ إلى عنصر واحد بالضبط من عناصر $P\text{.}$

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

مثال 2.6.21.

أعطِ بعض التقسيمات المختلفة للمجموعة $A = \{1,2,3,4,5\}\text{.}$

الحل. هناك خيارات كثيرة جدًّا هنا! أحد الخيارات هو: $$\begin{equation*} P_1 = \{\{1,2,3\}, \{4,5\}\}\text{.} \end{equation*}$$ وهذا تقسيم لـ$A$ إلى مجموعتين جزئيتين. وتقسيم آخر: $$\begin{equation*} P_2 = \{\{1\}, \{2\}, \{3\}, \{4\}, \{5\}\}\text{.} \end{equation*}$$ وآخر: $$\begin{equation*} P_3 = \{\{1,3,5\}, \{2,4\}\}\text{,} \end{equation*}$$ وهو بالصدفة تقسيم إلى الأعداد الزوجية والفردية. ولدينا أيضًا التقسيم البسيط: $$\begin{equation*} P_4 = \{\{1,2,3,4,5\}\}\text{.} \end{equation*}$$ لاحظ أن ذلك مجموعة واحدة داخل المجموعة $P_4\text{.}$

قد يكون التفكير في عناصر التقسيم على أنها مجموعات جزئية مربكًا بعض الشيء، لأن التقسيم مجموعة، ومجموعة من المجموعات قد يصعب الحديث عنها. أحيانًا نسمّي التقسيم «تجميعة» (collection)، ونسمّي كلَّ عنصر من عناصر التقسيم «جزءًا» (part) أو «كتلة» (block).

والآن الفكرة الكبرى: لأي علاقة تكافؤ، تشكل أصنافُ التكافؤ تقسيمًا، ولكل تقسيم يمكننا تعريف علاقة «ينتميان إلى المجموعة الجزئية نفسها» (are in the same subset) تكون علاقة تكافؤ. وقد رأينا بالفعل أن أصناف التكافؤ لـ$\equiv_2$ تشكل تقسيمًا. فلنسلك الاتجاه الآخر.

مثال 2.6.22.

عرّف علاقة تكافؤ $\sim$ على المجموعة $A = \{1,2,3,4,5\}$ انطلاقًا من التقسيم $P = \{\{1,4\}, \{2,3,5\}\}\text{.}$

الحل. قل إن عنصرين من عناصر $A$ متكافئان بشرط أن ينتميا إلى العنصر نفسه من $P\text{.}$ بمعنى آخر، $1 \sim 4$ و$4\sim 1\text{,}$ و$2 \sim 3\text{,}$ و$2 \sim 5\text{,}$ و$3 \sim 5\text{,}$ و$3\sim 2\text{,}$ و$5\sim 2\text{,}$ و$5\sim 3\text{.}$ ومهلًا. لدينا أيضًا $1\sim 1\text{,}$ و$2\sim 2\text{,}$ وهكذا، إذن كل عدد في المجموعة الجزئية نفسها التي هو فيها.

ومن الواضح بالنظر أن هذه العلاقة انعكاسية ومتماثلية ومتعدّية، إذن هي علاقة تكافؤ.

مبرهنة 2.6.23.

بالنظر إلى أي علاقة تكافؤ $R$ على مجموعة $A\text{,}$ تشكل أصنافُ التكافؤ تقسيمًا لـ$A\text{.}$

وبالنظر إلى أي تقسيم $P = \{B_1, B_2, \ldots, \}$ لمجموعة $A\text{,}$ تكون العلاقة $\equiv_P$ المعرَّفة بأن $a \equiv_P b$ إذا وفقط إذا كان $a$ و$b$ ينتميان إلى الكتلة نفسها من $P\text{,}$ علاقة تكافؤ.

كذلك، فإن أصناف التكافؤ لعلاقة التكافؤ التي ينشئها التقسيم هي التقسيم الأصلي بالضبط، وعلاقة التكافؤ التي ينشئها تقسيم أصناف تكافؤ هي علاقة التكافؤ الأصلية بالضبط.

أسئلة القراءة

1.

انظر العلاقة $R$ المعرَّفة على الأعداد الصحيحة، والمتحققة بين $a$ و$b$ تحديدًا إذا كان $b-a \ge 4\text{.}$ فمثلًا، $(2,7) \in R$ لكن $(8,6) \notin R\text{.}$ فما صفات العلاقات التالية التي تمتلكها $R$؟

• $R$ انعكاسية.
• إذا كانت $R$ انعكاسية، فإن (2,2) تحديدًا ستكون في $R\text{.}$ لكن $2-2 = 0\text{,}$ وهو ليس أكبر من 4 ولا يساويها.
• $R$ غير انعكاسية.
• صحيح. بما أنه لا يوجد عدد صحيح أكبر من نفسه بأربعة أو أكثر، فإن العلاقة لا تتحقق بين أي عنصر ونفسه.
• $R$ متماثلية.
• إذا كانت $R$ متماثلية، فإن لأي $a$ و$b$ بحيث $b-a \ge 4\text{,}$ لدينا أيضًا $a-b \ge 4\text{.}$ لكن هذا غير صحيح. فمثلًا، $(2,10)$ في $R$ لكن $(10,2)$ ليست في $R$. (نحن لا نستخدم الفرق المطلق.)
• $R$ لا-تماثلية.
• صحيح. لا يوجد عددان $a$ و$b$ بحيث يتحقق كل من $b-a \ge 4$ و$a-b \ge 4\text{,}$، ومن ثم فإن فرضية تعريف اللاتماثلية خاطئة دائمًا، مما يجعل العبارة الكاملة في التعريف صحيحة.
• $R$ متعدّية.
• صحيح. إذا كان $b-a \ge 4$ و$c-b \ge 4\text{,}$ فإن $c-a = (c-b) + (b-a) \ge 4+4 = 8\text{,}$ ومن ثم فإن $c-a \ge 4\text{.}$

2.

ليست كل الرسوم البيانية لها علاقة حواف متعدّية. لكن هل بعضُها كذلك؟ إن كان كذلك، فأعطِ مثالًا وفسّر لماذا هو متعدّي. وإن لم يكن كذلك، ففسّر السبب.

3.

بعد قراءة هذا القسم، ما الأسئلة التي تدور في ذهنك؟ اطرح سؤالًا واحدًا على الأقل عن هذا القسم يثير فضولك.