البراهين حول البنى المنفصلة

القسم 1.5 البراهين حول البنى المنفصلة

الأهداف

بعد إتمام هذا القسم، ينبغي أن تتمكّن من إداء ما يلي.

• قراءة تعريفات البنى المنفصلة (discrete structures) وفهمها بحيث تتمكّن من تطبيق التعريفات تطبيقاً صحيحاً.
• كتابة البراهين حول البنى المنفصلة.

معاينة القسم

استكشف!

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

لقد رأينا حتى الآن كيف يمكن للصيغة المنطقية لجملة أن تدلّنا على كيفية بناء الهيكل العظمي للبرهان. لكن هذا لا يأخذنا بعيداً: فلكمال الهيكل العظمي للبرهان لا بدّ من فهم الكائنات والبنى الرياضية التي تتناولها البراهين. وبعض هذا الفهم يأتي من قراءة التعريفات قراءةً متأنّية. غير أن ثمة أيضاً فهماً أقل تجريداً وبديهية يأتي من العمل مع هذه الكائنات والبنى، وهو ما يقود إلى لحظة الإلهام التي تلمّح لك بـ «آه-ها!» فتقترح كيف تُكمل البرهان.

بالمناسبة...

لماذا نكتب البراهين؟ إلى جانب التمرين على أن نصير مُفكِّرين أفضل، فإنّ التعمّق في براهين دقيقة حول البنى المنفصلة وسيلةٌ لتعلّم المزيد عن هذه البنى نفسها. فهي ساحةٌ للعب لاستكشاف الرياضيات، تساعدنا على بناء البديهية تجاه البنى الرياضية. إذن ندرس البنى كي تساعدنا على كتابة براهين عنها، ونكتب براهين عنها كي تساعدنا على فهم البنى. هكذا نبني الأساس بعضه على بعض!

وثمة سبب آخر لتحويل بؤرة اهتمامنا إلى البراهين حول البنى المنفصلة، هو أنّ ذلك يوضح خاصيةً مهمة في الرياضيات: التجريد (abstraction). لقد كنّا نبرهن على وقائع بعينها في مسائل بعينها. بل قد نبدأ في ملاحظة أوجه تشابه بين براهين بعض الجمل. وقد يكون ذلك راجعاً إلى البنى الرياضية الكامنة التي تتناولها المسائل (في الخفاء). فإذا برهنّا على الوقائع العامة لهذه البنى، أمكننا عندئذٍ تطبيق هذه «المبرهنات» على مسائل مختلفة كثيرة.

بعض البنى المنفصلة تناسب أنماطاً خاصة من البراهين، وبعض تقنيات البرهان «المعيارية» تنطبق على بنًى بعينها. سنرى بعضاً من ذلك هنا، لكننا في معظمه نستثمر هذه الفرصة لتذكّر بعض التعريفات والخصائص الأساسية للبنى المنفصلة، ونستخدم البراهين عنها لتفهمها فهماً أفضل.

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

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

1.

تذكَّر أن المجموعة ليست سوى مجموعة عناصر. وفيما يلي تعريفان حول المجموعات:

1. المجموعة $A$ هي مجموعة جزئية (subset) من المجموعة $B\text{,}$ ويُكتب ذلك $A \subseteq B\text{,}$ شريطة أن يكون كل عنصر في $A$ عنصراً في $B\text{.}$
2. المعطاة مجموعتان $A$ و$B\text{,}$ فإنّ اتحاد (union) $A$ و$B\text{,}$ ويُكتب $A \cup B\text{,}$ هو المجموعة التي تضم كل عنصر يكون في $A$ أو في $B$ أو في كليهما.

لنبنِ بعض الأمثلة.

(a)

لتكن $B = \{1, 3, 5, 7, 9\}\text{.}$ أعطِ مثالاً لمجموعة $A$ تضم $3$ عناصر وتكون مجموعة جزئية من $B\text{.}$

فما هو $A \cup B$ للمجموعة $A$ التي أعطيتَها كمثال؟

(b)

أعطِ مثالاً لمجموعتين مختلفتين $A$ و$B$ بحيث $A \cup B = B\text{.}$

$A =$ ; $B =$

وفي المثال الذي أعطيتَه، هل $A \subseteq B\text{?}$

• نعم
• لا

(c)

ابحث عن أمثلة، إن وُجدت، لمجموعتين $A$ و$B$ بحيث $A \cup B \ne B\text{.}$

$A =$ ; $B =$ .

وفي المثال الذي أعطيتَه، هل $A \subseteq B\text{?}$

• نعم
• لا

2.

أيٌّ مما يلي صحيح دائماً؟

• لأي مجموعتين $A$ و$B\text{,}$ لدينا $A \cup B \subseteq B\text{.}$
• وماذا لو كان $A = \{1,2,3\}$ و$B = \{1, 3, 5\}\text{?}$
• لأي مجموعتين $A$ و$B\text{,}$ لدينا $B \subseteq A \cup B\text{.}$
• لأي مجموعتين $A$ و$B\text{,}$ إذا كان $A \subseteq B\text{,}$ فإن $A \cup B \subseteq B\text{.}$
• لأي مجموعتين $A$ و$B\text{,}$ إذا كان $A \cup B = B\text{,}$ فإن $A \subseteq B\text{.}$

3.

لأي دالة $f: \mathbb{N} \to \mathbb{N}$ وأي مجموعة $A \subseteq \mathbb{N}\text{,}$ يمكننا تعريف صورة (image) $A$ على يد $f$ بأنها مجموعة كل مخرجات $f$ عندما يكون المدخل عنصراً من $A\text{.}$ ونكتبها $f(A) = \{f(x) ~:~ x \in A\}\text{.}$

وفيما يلي من المهام، فلنستكشف الدالة $f: \mathbb{N} \to \mathbb{N}$ المعرَّفة بـ $f(x) = x^2 - 3x + 8\text{.}$

(a)

لتكن $A = \{1,2,3\}$ و$B = \{2, 4, 6\}\text{.}$ جدِد $f(A)$ و$f(B)\text{.}$ ثم جدِد $f(A) \cup f(B)\text{.}$

$f(A) =$ ; $f(B) =$ ; $f(A) \cup f(b) =$ .

(b)

الآن جدِد $A \cup B$ و$f(A \cup B)\text{.}$

$A \cup B =$ ; $f(A \cup B) =$ .

(c)

أعطِ مثالاً، إن وُجد، لمجموعتين مختلفتين $A$ و$B$ بحيث $A \subseteq B$ و$f(A) \subseteq f(B)\text{.}$

$A =$; $B =$.

أعطِ مثالاً، إن وُجد، لمجموعتين مختلفتين $A$ و$B$ بحيث $A \subseteq B$ لكن $f(A) \not\subseteq f(B)\text{.}$

$A =$; $B =$.

قسم فرعي: البراهين حول المجموعات

تذكَّر أن المجموعة مجموعة عناصر غير مرتّبة. يمكننا وصف مجموعة بإدراج عناصرها، أو بتحديد خاصية تحقّقها جميع عناصر المجموعة. على سبيل المثال، $$\begin{equation*} A = \{1,2,3,4,5\}\text{,} \end{equation*}$$ أو $$\begin{equation*} B = \{x \in \N \st x \lt 10 \}\text{.} \end{equation*}$$ المجموعة الثانية هنا هي مجموعة الأعداد الطبيعية ($0, 1, 2, \ldots$) الأصغر من 10. لاحظ أن كل عنصر في $A$ هو أيضاً عنصر في $B\text{.}$ وإليك تعريفاً يعبّر عن هذه الفكرة.

تعريف 1.5.1.

المجموعة $A$ هي مجموعة جزئية (subset) من المجموعة $B\text{,}$ ويُكتب ذلك $A \subseteq B\text{,}$ شريطة أن يكون كل عنصر من عناصر $A$ عنصراً أيضاً من عناصر $B\text{.}$

وتُسمّى المجموعة $B$ أحياناً مجموعة شاملة (superset) لـ $A\text{.}$

ونقول إن $A$ مجموعة جزئية فعلية (proper subset) من $B\text{,}$ ويُكتب ذلك $A \subset B\text{,}$ شريطة أن $A \subseteq B$ وأن $A \neq B\text{.}$ بمعنى آخر، إذا كان كل عنصر في $A$ عنصراً في $B\text{,}$ وكان هناك عنصر واحد على الأقل في $B$ ليس في $A\text{.}$

مثال 1.5.2.

لتكن $A = \{x \in \N \st x \lt 5\}$ و$B = \{ x \in \N \st x^2 \lt 10\}\text{.}$ هل $B \subseteq A\text{?}$ وهل $B$ مجموعة جزئية فعلية من $A\text{?}$

الحل. إننا نسأل: هل كل عدد طبيعي أصغر من 5 هو أيضاً عدد طبيعي مربعه أصغر من 10؟ حسناً، يمكننا ببساطة أن نكتب عناصر المجموعتين: $A = \{0,1,2,3,4\}$ و$B = \{0,1,2,3\}$ (بما أن $3^2 = 9$ و$4^2 = 16$). إذن $B \subseteq A\text{.}$ لكن $B \neq A\text{,}$ فبحقيقة الأمر $B \subset A\text{.}$

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

ادّعينا أن كل عنصر في $B$ هو أيضاً عنصر في $A\text{.}$ وتعبير آخر عن ذلك: لكل الأعداد $n\text{,}$ إذا كان $n$ عنصراً في $B\text{,}$ فإن $n$ يكون أيضاً عنصراً في $A\text{.}$ ولما كان هذا التوصيف جملة شرطية، فإنا ننتقل لإعطاء برهان مباشر أو بالـعكس أو بالتناقض لهذه الواقعة. وحيث إنّ البرهان المباشر هنا مقبول تماماً، فلنجرّبه:

البرهان.

ليكن $n$ عنصراً في المجموعة $B\text{.}$ عندئذٍ $n^2 \lt 10\text{,}$ بحكم تعريف $B\text{.}$ وبما أن $4^2 = 16\text{,}$ فلا بدّ أن يكون لدينا $n \lt 4\text{.}$ ومن تعريف $A\text{,}$ ومن الحقيقة $4 \lt 5\text{,}$ نرى أن $n \in A\text{.}$

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

ولتبيين مثال على كيف يمكننا تطبيق تعريف «المجموعة الجزئية» في سياق أعمّ، فلنبرهن على واقعة أساسية عن الاحتواء.

دعوى 1.5.3.

لأي مجموعات $A\text{,}$ $B\text{,}$ و$C\text{,}$ إذا كان $A \subseteq B$ و$B \subseteq C\text{,}$ فإن $A \subseteq C\text{.}$

البرهان.

سنُعطي برهاناً مباشراً. لتكن $A\text{,}$ $B\text{,}$ و$C$ مجموعات، ونفترض أن $A \subseteq B$ وأن $B \subseteq C\text{.}$ وسنبرهن على أن $A \subseteq C\text{.}$

ليكن $x$ عنصراً في $A\text{.}$ وبما أن $A \subseteq B\text{,}$ نعلم أن $x \in B\text{.}$ وبما أن $B \subseteq C\text{,}$ نعلم أن $x \in C\text{.}$ إذن، $A \subseteq C\text{.}$

ولنتقل الآن إلى برهنة واقعة عن الأعداد: كل مضاعف للعدد 9100 هو أيضاً مضاعف للعدد 13. يمكننا تحليل 9100 إلى عوامله، لكن إليك طريقةً أسهل. مجموعة مضاعفات 9100 مجموعة جزئية من مجموعة مضاعفات 91. ومجموعة مضاعفات 91 مجموعة جزئية من مجموعة مضاعفات 13. والآن طبّق الدعوى أعلاه.

برهان الدعوى 1.5.3 هو ما يُسمّى أحياناً برهان تتبّع العناصر (element chasing). فبحكم تعريف المجموعة الجزئية، تعني $A \subseteq B$ أن كل عنصر في $A$ هو عنصر في $B\text{,}$ أو ما يعادلها، لكل $x\text{,}$ إذا كان $x$ عنصراً في $A\text{,}$ فإن $x$ عنصر في $B\text{.}$ وإحدى طرائق إثبات ذلك هي أن «نتتبّع» العنصر $x$ من $A$ إلى $B\text{.}$

مثال 1.5.4.

برهن أن إذا كان $A \subseteq B\text{,}$ فإن $A \cup B \subseteq B\text{.}$ تذكَّر أن $A \cup B$ هو اتحاد المجموعتين $A$ و$B\text{,}$ ويحتوي على جميع العناصر الموجودة في $A$ أو في $B$ أو في كليهما.

الحل. سنكتب برهاناً مباشراً. سنفترض إذن أن $A \subseteq B$ ونبرهن على أن $A \cup B \subseteq B\text{.}$ والنتيجة التي نريدها جملة عن المجموعات الجزئية، فدعنا نبرهن عليها بتتبّع العناصر.

البرهان.

لتكن $A$ و$B$ مجموعتين ونفترض $A \subseteq B\text{.}$ وليكن الآن $x$ عنصراً في $A \cup B\text{.}$ وهذا يعني أن $x$ عنصر في $A\text{,}$ أو أن $x$ عنصر في $B\text{,}$ أو في كليهما. 6 بحكم تعريف الاتحاد.

ناقش الحالات. إذا كان $x$ عنصراً في $A\text{,}$ فبما أن $A \subseteq B\text{,}$ نعلم أن $x$ عنصر في $B\text{.}$ ومن جهة أخرى، إذا لم يكن $x$ عنصراً في $A\text{,}$ فلا بدّ أن يكون $x$ عنصراً في $B$ (بما أن $x$ في $A \cup B$). وفي كلتا الحالتين، $x$ عنصر في $B\text{.}$ إذن، $A \cup B \subseteq B\text{.}$

وفي الحقيقة يمكننا البرهنة على قاعدة أقوى: $A \subseteq B$ إذا وفقط إذا $A \cup B = B\text{.}$ وقد طُلب منك فعل ذلك في التمارين.

قسم فرعي: البراهين حول الدوال

الدالة $f:A \to B$ هي قاعدةٌ تُسند كل عنصر من عناصر المجموعة $A$ (المجال domain) إلى عنصر واحد تماماً من عناصر المجموعة $B$ (مدى الدالة codomain). وهي أيّ قاعدة: لا يلزم وجود صيغة أو مبرِّر لها؛ فنحن نحتاج فقط إلى مقابلة عناصر من $A$ بعناصر من $B\text{.}$ على سبيل المثال، يمكننا أن نجعل $A$ مجموعة الطلاب المسجَّلين في مقرر معيّن للرياضيات المنفصلة، و$B$ مجموعة أشهر السنة. نعرّف الآن الدالة $f:A \to B$ بأنها القاعدة التي تُسند لكل طالب الشهر الذي يقع فيه عيد ميلاده. وبما أن لكل طالب شهراً مُسنداً، ولا أكثر من شهر واحد، فإن هذه دالة.

وإليك تعريفاً لنوعٍ معيّن من الدوال.

تعريف 1.5.5.

الدالة $f:A \to B$ أحادية (injective) (أو واحد إلى واحد) شريطة أن يكون كل عنصر في $B$ صورة عنصر واحد على الأكثر في $A\text{.}$ بمعنى آخر، لا يوجد عنصر في $B$ يكون المخرج لأكثر من مدخل واحد من $A\text{.}$

في المثال أدناه، نستخدم الصيغة ذات السطرين (two-line notation) لوصف دالة. يضمّ الصف العلوي المداخل، ويسرد الصف السفلي المخرجات المقابلة. هكذا يمكن تعريف $f:\{1,2,3,4\} \to \{a,b,c,d\}$ بـ، $$\begin{equation*} f = \twoline{1 \amp 2 \amp 3 \amp 4}{a \amp b \amp c \amp d}\text{,} \end{equation*}$$ وهذا يعني أن $f(1) = a\text{,}$ و$f(2) = b\text{,}$ و$f(3) = c\text{,}$ و$f(4) = d\text{.}$

مثال 1.5.6.

لتكن $A = \{1,2,3\}$ و$B = \{2, 4, 6, 8\}\text{.}$ تأمَّل الدالتين $f:A \to B$ و$g:A \to B$ المعرَّفتين بـ، $$\begin{equation*} f = \twoline{1 \amp 2 \amp 3}{2 \amp 8 \amp 6}, \qquad g = \twoline{1 \amp 2 \amp 3}{4 \amp 6 \amp 4}. \end{equation*}$$ أيُّ هاتين الدالتين أحادية؟

الحل. الدالة $f$ أحادية: كل عنصر في $B$ صورة عنصر واحد على الأكثر في $A\text{.}$ أما الدالة $g$ فليست أحادية: العنصر 4 في $B$ هو صورة كلٍّ من 1 و3 في $A\text{.}$

ولنتأمَّل ثانيةً دالة «الطالب إلى شهر الميلاد». هل يمكن لهذا أن تكون أحادية؟ أو بصيغة أخرى، هل يجب أن يوجد طالبان في المقرر لهما شهر ميلاد واحد (وهذا ما يعني أن الدالة ليست أحادية)؟ يبدو أن الإجابة تعتمد على عدد الطلاب في الصف.

لكن دعنا نتوقف ونفكر في الواقعة الأكثر عمومية عن الدوال التي بين أيدينا. فلنبرهن على الواقعة التالية. وتذكَّر أن $|A|$ تدل على عدد (cardinality) المجموعة $A\text{:}$ وهو عدد عناصر $A\text{.}$

دعوى 1.5.7.

لنفترض أن $f:A \to B$ دالة و$A$ و$B$ كلتاهما مجموعة منتهية. إذا كان $|A| \gt |B|\text{,}$ فإن $f$ ليست أحادية.

البرهان.

سنُقدّم برهان العكس (contrapositive): إذا كانت $f$ أحادية، فإن $|A| \le |B|\text{.}$ ليكن $|B| = n\text{.}$ وبما أن $f$ أحادية، فلا بدّ أن يكون كل عنصر في $B$ مخرجاً لعنصر واحد فقط على الأكثر من $A\text{.}$ ومن ثمّ فإن ما لا يزيد عدده على $n$ من العناصر في $A$ تُسند إلى $B$ على يد $f\text{.}$ لكن تعريف الدالة يشترط أن يُسند كل عنصر من المجال إلى عنصر واحد تماماً من مدى الدالة، ومن ثمّ فلا بدّ أن يكون العدد $n$ هو عدد عناصر $A\text{.}$

هل يذكّرك هذا البرهان ببراهيننا الشبيهة بمبدأ الأدراج (pigeonhole principle)؟ ينبغي أن يذكّرك، إذ إنّ هذا هو تحديداً إحدى الصياغات الدقيقة لمبدأ الأدراج. كان بإمكاننا البرهنة على واقعة الطلاب الذين يشتركون في شهر ميلاد واحد، لكننا الآن نكتفي بتطبيق الدعوى أعلاه وننهي الأمر. وحين تطبّق مبرهنة أو دعوى للبرهنة مباشرة على نتيجة أخرى، فإننا نسمي النتيجة اللاحقة نتيجةً (corollary).

نتيجة 1.5.8.

لنفترض أن في صفٍّ 25 طالباً. عندئذٍ يشترك طالبان على الأقل في شهر الميلاد نفسه.

البرهان.

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

للدوال دائماً مداخل من مجموعة (تُسمّى المجال domain) ومخرجات في مجموعة أيضاً (تُسمّى مدى الدالة codomain). وهذا يقود بطبيعة الحال إلى وقائع يجب النظر إليها بشأن التفاعل بين المجموعات والدوال.

تعريف 1.5.9.

المعطاة دالة $f:X \to Y$ ومجموعة $A \subseteq X\text{,}$ فإننا نعرّف صورة $A$ (image) على يد $f$ بأنها المجموعة $f(A) = \{f(a) \in Y \st a \in A\}\text{.}$ بمعنى أن $f(A)$ هي مجموعة كل مخرجات الدالة عند مداخل في $A\text{.}$

مثال 1.5.10.

لتكن $f: \N \to \N$ معرَّفة بـ $f(n) = 2n\text{.}$ ولتكن $A = \{1,2,3\}\text{.}$ جدِد $f(A)\text{.}$

الحل. قيّم كل عنصر من عناصر $A$ بواسطة $f\text{.}$ $$\begin{equation*} f(1) = 2;\qquad f(2) = 4; \qquad f(3) = 6\text{.} \end{equation*}$$ نريد مجموعة هذه المخرجات. إذن $f(A) = \{2, 4, 6\}\text{.}$

ولنبرهن الآن على شيءٍ ما.

دعوى 1.5.11.

لتكن $f:X \to Y$ دالة، ولتكن $A$ و$B$ مجموعتين جزئيتين من $X\text{.}$ إذا كان $A \subseteq B\text{,}$ فإن $f(A) \subseteq f(B)\text{.}$

البرهان.

لتكن $f\text{,}$ $A\text{,}$ و$B$ كما في الدعوى. نفترض أن $A \subseteq B\text{.}$ ولنتأمَّل الآن عنصراً $y \in f(A)\text{.}$ وبحكم التعريف، هذا يعني أن هناك عنصراً ما $a \in A$ بحيث $f(a) = y\text{.}$ وبما أن $a \in A$ وأن $A \subseteq B\text{,}$ فإن لدينا $a \in B\text{.}$ عندئذٍ بحكم التعريف، $$\begin{equation*} y = f(a) \in f(B)\text{.} \end{equation*}$$ ولأن $y$ كان عنصراً اعتباطياً في $f(A)\text{,}$ فقد برهنّا على أن $f(A) \subseteq f(B)\text{.}$

ولاحظ أن البرهان أعلاه هو أيضاً برهان تتبّع عناصر. وهذا منطقي ما دمت تتذكّر أن $f(A)$ و$f(B)$ ليس سوى اسمين لمجموعتين. فللبرهنة على أن مجموعة مجموعة جزئية من أخرى، نتتبّع العناصر من المجموعة الجزئية إلى المجموعة الشاملة.

قسم فرعي: البراهين حول العلاقات

العلاقة (relation) على مجموعة $A$ هي مجموعة من أزواج مرتّبة من عناصر $A\text{.}$ يمكننا أن نفكر في العلاقة على أنها طريقة لوصف نوعٍ من الصلة بين عناصر $A\text{.}$ على سبيل المثال، قد تكون لدينا علاقة على مجموعة الأشخاص في حفلة تصف من هو صديقٌ لمن. وقد تكون لدينا علاقة على مجموعة الأعداد الطبيعية تصف أيّ الأزواج من الأعداد تربطها العلاقة $x \lt y\text{.}$

وتسري في الرياضيات بأكملها، غالباً دون أن نفكر فيها حتى. فكلما أدلينا جملةً عن عنصرين من عناصر مجموعة، فإننا نعرّف ضمناً علاقة. وتكون الجملة صادقة عندما يكون الزوج داخل العلاقة. على سبيل المثال، الجملة «3 أقل من 5» صحيحة لأن الزوج $(3,5)$ موجود في العلاقة $\lt\text{.}$ وفي الواقع، باستعمال اللغة التي طوّرناها في القسم الفرعي المُكمِّمات والمُميِّزات، يمكننا القول بأن العلاقة ليست سوى مُميِّز (predicate)، حيث تأتي المتغيرات من المجموعة نفسها.

وكثيراً ما تحمل العلاقات رموزاً خاصة مثل «$=$» أو «$\le$» أو «$\perp$». وعندما نتحدث عن علاقة عامة، فإننا إما أن نستخدم $\sim$ ونكتب $x \sim y\text{,}$ أو نستخدم حرفاً كبيراً مثل $R\text{,}$ ونكتب $R(x,y)$ أو $xRy$ أو حتى $(x,y) \in R$ ( وكلها تعني الشيء نفسه).

وعندما ندرس العلاقات، نحاول تحديد الخصائص التي قد تكون لها. وإليك مثالاً على خاصية شائعة جداً.

تعريف 1.5.12.

العلاقة $R$ على مجموعة $A$ متناسِبة (transitive) شريطة أنه لكل $x,y,z \in A\text{,}$ إذا كان $xRy$ و$yRz\text{,}$ فإن $xRz\text{.}$

مثال 1.5.13.

تأمَّل العلاقة $\sim$ على مجموعة الطلاب في مقرر الرياضيات المنفصلة، والتي تتحقق بين طالبين شريطة أن يكون لهما مقرّر آخر مشترك. هل هذه العلاقة متناسِبة؟

الحل. لا، ليس بالضرورة (وإن كان ذلك ممكناً لبعض مجموعات الطلاب). على سبيل المثال، لنفترض أن أليس تشترك مع برويس في مقرر آخر، ولنقل «مدخل إلى البرمجة». كارلوس ليس مسجّلاً في «مدخل إلى البرمجة»، لكنه هو وبرويس مسجّلان كلاهما في «الكيمياء العضوية». عندئذٍ يكون أليس$\sim$برويس وبرويس$\sim$كارلوس، لكن ليس بالضرورة أن يكون أليس$\sim$كارلوس (إذ لا يلزم أن تكون أليس في «الكيمياء العضوية» مع كارلوس).

والبرهنة على أن علاقة ما ليست متناسِبة لا تتطلب أكثر من إيجاد مثال مضادّ (counterexample)، أي إيجاد ثلاثة عناصر $a\text{,}$ $b\text{,}$ و$c$ بحيث $a \sim b\text{,}$ و$b \sim c\text{,}$ ولكن $a \not\sim c$ (وتذكَّر أن الطريقة الوحيدة لتكون جملة شرطية خاطئة هي أن يكون الفرض صحيحاً والنتيجة خاطئة).

وربما كان أكثر إثارةً للاهتمام قليلاً أن نبرهن على أن علاقة متناسِبة.

مثال 1.5.14.

تأمَّل مجموعة جميع الطلاب في صف الرياضيات المنفصلة، وعَرِّف العلاقة $\sim$ التي تتحقق بين طالبين $a$ و$b$ (أي أن $a \sim b$ صحيح)، شريطة أن يكون $a$ أطول من $b\text{.}$ برهن أن هذه العلاقة متناسِبة.

الحل. تعريف المتناسبية هو استلزام، لذا يمكننا أن نجرّب برهاناً مباشراً.

البرهان.

ليكن $a\text{,}$ $b\text{,}$ و$c$ طلاباً اعتباطيين في مقرر الرياضيات المنفصلة. نفترض أن $a \sim b$ و$b \sim c\text{.}$ هذا يعني أن $a$ أطول من $b\text{,}$ وأن $b$ أطول من $c\text{.}$ لكن عندئذٍ لا بدّ أن يكون $a$ أطول من $c$ أكثر مما هما أطول من $b\text{,}$ فلدينا أيضاً أن $a \sim c$ صحيح. إذن فإن $\sim$ متناسِبة على هذه المجموعة.

قسم فرعي: البراهين حول الرسوم البيانية

سنقضي كل الفصل 2 في دراسة البراهين حول الرسوم البيانية (graphs)، لأن هذا مجالٌ من الرياضيات غنيٌّ جداً. وكمعاينة، إليك مثالاً على كيف يمكن أن تسير البراهين حول الرسوم البيانية.

الرسم البياني هو مجموعة $V$ من الرؤوس (vertices) ومجموعة $E$ من الحواف (edges). الحواف هي مجموعات جزئية من عنصرين من الرؤوس، ويمكننا التفكير فيها بأنها تمثّل علاقات بين الرؤوس. لاحظ أن هذا تعريفٌ مجرد للرسم البياني باستخدام المجموعات، لكننا نرسم الرسوم البيانية عادةً بنقاطٍ تمثل الرؤوس تربطها خطوطٌ تمثل الحواف، لأن هذا يعطينا صورةً جميلة لما يجري.

وبما أن الرسوم البيانية تمثّل نوعاً من العلاقات بين العناصر (الرؤوس)، يمكننا استخدام الرسوم البيانية لتمثيل كثيرٍ من مسائل العالم الحقيقي. على سبيل المثال، قد تمثّل رؤوس الرسم البياني أشخاصاً في حفلة. ويمكن لكل حافة أن تمثّل مصافحة يدٍ بين شخصين. فإذا تساءلنا هل من الممكن أن يتصافح كلٌّ من الأشخاص الخمسة عشر في حفلة مع 3 أشخاص تحديداً هناك، فإننا في الحقيقة نسأل: هل يوجد رسم بياني بـ 15 رأساً حيث ينتمي كل رأس إلى 3 حواف؟ (تنتمي إلى؟؟ نعم، لأن الحافة مجموعة جزئية من عنصرين من الرؤوس، فإذا «لامست» حافةً رأساً أو «خرجت» منه، فهذا يعني أن ذلك الرأس ينتمي إلى تلك المجموعة الجزئية المحددة من عنصرين.)

وإليك تعريفاً ذا صلة بهذه الفكرة.

تعريف 1.5.15.

ليكن $v$ رأساً في رسم بياني $G\text{.}$ درجة $v\text{,}$ ويُكتب $d(v)\text{,}$ هي عدد الحواف التي تحتوي $v\text{,}$ أي عدد الحواف الملاصقة لـ $v\text{.}$

مثال 1.5.16.

تأمَّل الرسم البياني $G$ ذو الرؤوس $V = \{1,2,3,4\}$ والحواف $E = \{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}\text{.}$ ما درجة كل رأس في $G\text{?}$

الحل. قد يكون من المفيد تخيّل الرسم البياني:

لدينا $d(1) = 3\text{,}$ و$d(2) = 2\text{,}$ و$d(3) = 2\text{,}$ و$d(4) = 1\text{.}$ ويمكنك أن ترى ذلك بعدّ كم حافةً ملاصقة لكل رأس، أو بعدّ كم حافةً (مجموعة جزئية) ينتمي إليها كل رأس.

إذن هل من الممكن أن يتصافح 15 شخصاً كلٌّ منهم مع ثلاثة أشخاص تماماً في مجموعته؟ حسناً، هل يوجد رسم بياني بـ 15 رأساً، جميعها درجتها 3؟ الجواب لا!

وإحدى الطرق التي يمكنك بها أن ترى ذلك هي أن تسأل: كم حافةً سيحتوي عليها هذا الرسم البياني؟ كل رأس ملاصق لثلاث حواف، فبعدّ الملاصقات نحصل على $15\cdot 3 = 45\text{.}$ لكن كل حافة ملاصقة لرأسين، فقد عدنا كل حافة مرتين. إذن يكون عدد الحواف في مثل هذا الرسم البياني $45/2 = 22.5\text{.}$ لكن عدد الحواف في الرسم البياني لا بد أن يكون عدداً صحيحاً، فلا يوجد مثل هذا الرسم البياني.

وهذا يقترح أننا يمكننا قول شيءٍ أكثر عمومية. والدعوى التالية نتيجةٌ بسيطة لـلمّة المصافحة 2.1.8، التي سنبرهن عليها في القسم 2.1. وهنا نقدم برهاناً كاملاً لهذه الصيغة تحديداً.

دعوى 1.5.17.

في أي رسم بياني، لا بد أن يكون عدد الرؤوس ذات الدرجة الفردية زوجياً.

البرهان.

سنبرهن على ذلك بالتناقض. لنفترض وجود رسم بياني فيه عدد فردي من الرؤوس ذات الدرجة الفردية. تأمَّل مجموع درجات جميع الرؤوس. سيكون مجموع درجات الرؤوس ذات الدرجة الفردية فردياً (لأن مجموع عددٍ فردي من الأعداد الفردية هو فردي). وسيكون مجموع درجات الرؤوس ذات الدرجة الزوجية زوجياً (فأي مجموع لأعداد زوجية لا بد أن يكون زوجياً). ومجموع عدد فردي وآخر زوجي هو فردي. إذن يكون مجموع جميع الدرجات فردياً.

غير أن عدد الحواف في الرسم البياني يساوي نصف مجموع الدرجات (بحكم لمّة 2.1.8، أو ببساطة لأن كل حافة تسهم بواحد في عدّ درجتي رأسين). وبما أن عدد الحواف عددٌ صحيح، نرى أن مجموع الدرجات لا بد أن يكون زوجياً.

وهذا يناقض ما وجدناه في الفقرة السابقة. إذن، في أي رسم بياني، لا بد أن يكون عدد الرؤوس ذات الدرجة الفردية زوجياً.

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

1.

أيٌّ مما يلي هو تعريف الدالة $f:A \to B$ بأنها أحادية؟

• كل عنصر في $B$ هو صورة عنصر واحد على الأكثر في $A\text{.}$
• المجال $A$ مجموعةٌ أكبر من مدى الدالة $B\text{.}$
• لا، بل إن هذا لا يمكن أن يحدث أبداً إذا كانت $f$ أحادية.
• كل عنصر في $A$ يُرسَل إلى عنصر واحد على الأكثر في $B\text{.}$
• هذا ليس سوى جزء من تعريف الدالة.
• مدى الدالة $B$ ليس أصغر من المجال $A\text{.}$
• لا بد أن يكون هذا صحيحاً إذا كانت $f$ أحادية، لكنه ليس جزءاً من تعريف الأحادية.

2.

متى يكون استخدام تتبّع العناصر كجزءٍ من برهان هو الأنسب؟

• عند البرهنة على أن مجموعة مجموعة جزئية من أخرى.
• عند البرهنة على أن دالة ما أحادية.
• عند البرهنة على أن علاقة ما متناسِبة.
• عند البرهنة على أن رسماً بيانياً له عدد فردي من الحواف.

3.

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

افترض أنّ \(B \subseteq A \cap B\text{,}\) وليكن \(b\) عنصرًا من \(B\text{.}\)
---
إذن \(b\) عنصر من \(A \cap B\) لأنّ \(B \subseteq A \cap B\text{.}\)
---
ولأنّ \(A \cap B\) يحوي كلّ العناصر الموجودة في \(A\) و\(B\) معًا، فإنّ \(b\) عنصر من \(A\text{.}\)
---
إذن \(B \subseteq A\text{.}\)
---
إذن \(B \subseteq A \cap B\)
---
إذن \(b\) عنصر من \(B\) لأنّ \(B \subseteq A \cap B\text{.}\)
---
ليكن \(b\) عنصرًا من \(A \cap B\text{.}\)
---
افترض أنّ \(B \subseteq A\text{.}\)
---
افترض أنّ \(A \subseteq B\text{.}\)

سنبرهن أوّلًا على أنّ \((A \cap B) \cup A \subseteq A\text{.}\)
---
ليكن \(x\) عنصرًا من \((A \cap B) \cup A\text{.}\)
---
إذن إمّا أنّ \(x\) عنصر من \(A \cap B\text{,}\) أو أنّ \(x\) عنصر من \(A\text{.}\)
---
فبخاصةٍ يكون \(x\) عنصرًا من \(A\text{.}\)
---
إذن \((A \cap B) \cup A \subseteq A\text{.}\)
---
وثانيًا، سنبرهن على أنّ \(A \subseteq (A \cap B) \cup A\text{.}\)
---
ليكن \(x\) عنصرًا من \(A\text{.}\)
---
إذن \(x\) عنصر من \((A \cap B) \cup A\text{,}\) لأنّ \(x\) في \(A\) أو في المجموعة الأخرى.
---
إذن \(A \subseteq (A \cap B) \cup A\text{.}\)
---
ولأنّ \((A \cap B) \cup A \subseteq A\) و\(A \subseteq (A \cap B) \cup A\text{,}\) فإنّ \((A \cap B) \cup A = A\text{.}\)

افترض أنّ \(B_1 \subseteq B_2\text{.}\)
---
ليكن \(a\) عنصرًا من \(f\inv(B_1)\text{.}\)
---
وهذا يعني أنّ \(f(a)\) عنصر من \(B_1\text{.}\)
---
ولأنّ \(B_1 \subseteq B_2\text{,}\) فإنّ \(f(a)\) عنصر من \(B_2\text{.}\)
---
وهذا يعني بدوره أنّ \(a\) عنصر من \(f\inv(B_2)\text{.}\)
---
إذن \(f\inv(B_1) \subseteq f\inv(B_2)\text{.}\)
---
ليكن \(b\) عنصرًا من \(B_1\text{.}\)
---
إذن \(b\) عنصر من \(B_2\text{.}\)
---
ومن ثمّ \(B_1 \subseteq B_2\text{.}\)