الرياضيات الجامعية — السنة 2 · Bachelor Year 2

1المجموعات والبنى

يشحذ هذا الفصل الافتتاحي الأسس الموضوعة في مجلد السنة الأولى ويحوّلها إلى أدوات عمل يومية: حساب المجموعات ومجموعات القسمة، ومقارنة المجموعات غير المنتهية (قابلية العد، كانتور–برنشتاين)، والنظرية البنيوية للزمر والحلقات — مبرهنة لاغرانج، والزمرة المتناظرة مع إشارتها، والمثاليات ومبرهنة البواقي الصينية. كل ما هنا يُستعمل بلا انقطاع في بقية الكتاب: الإشارة تبني المحدد (الفصل 2)، وحلقات القسمة تُدير الحساب، وقابلية العد تقوم تحت الطوبولوجيا والاحتمال معًا.

1.1 المجموعات والتطبيقات ومجموعات القسمة

نستعمل بحرية لغة المجموعات والتطبيقات وعلاقات التكافؤ والترتيب التي أُرسيت في مجلد السنة الأولى. وهناك تحسينان يستحقان صياغة صريحة.

قضية 1.1 (صور العائلات وصورها العكسية)

ليكن $f \colon E \to F$ ولتكن $(A_i)_{i \in I}$ و $(B_j)_{j \in J}$ عائلتين من أجزاء $E$ و $F$ على التوالي. عندئذٍ

f^{-1}\Bigl(\bigcup_j B_j\Bigr) = \bigcup_j f^{-1}(B_j), \qquad f^{-1}\Bigl(\bigcap_j B_j\Bigr) = \bigcap_j f^{-1}(B_j), \qquad f^{-1}(F \setminus B) = E \setminus f^{-1}(B),

f\Bigl(\bigcup_i A_i\Bigr) = \bigcup_i f(A_i), \qquad f\Bigl(\bigcap_i A_i\Bigr) \subseteq \bigcap_i f(A_i) \quad (\text{مع المساواة إذا كان } f).

متباينًا

برهان. كل متطابقة هنا ليست إلا فكًّا للتعاريف؛ فمثلًا $x \in f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ لكل $j$ $\iff x \in f^{-1}(B_j)$ لكل $j$ . أما متطابقات الصورة وانعدام المساواة في حالة التقاطع (مع تصحيحها بالتباين) فقد بُرهنت في مجلد السنة الأولى من أجل مجموعتين؛ والحجج نفسها تصلح للعائلات. ∎

مثال 1.2 (حيث يكون احتواء الصور تامًا)

لنأخذ $f \colon \R \to \R$ ، $f(x) = x^2$ ، مع $A_1 = \intcc{-1}{0}$ و $A_2 = \intcc{0}{1}$ . عندئذٍ

f(A_1 \cap A_2) = f(\{0\}) = \{0\}, \qquad f(A_1) \cap f(A_2) = \intcc{0}{1} \cap \intcc{0}{1} = \intcc{0}{1} :

فالاحتواء في القضية 1.1 تامّ إلى أقصى حدّ — إذ إن نقطتي الصورة العكسية $\pm x$ لقيمة مشتركة تقعان في $A_i$ مختلفين. والتباين هو بالضبط ما يمنع هذا الانفصال، ولهذا تُحقق الصور العكسية (التي لا تدمج نقطتين أبدًا) المتطابقات الأربع دون شرط، بينما تفقد الصور تلك المتعلقة بالتقاطع. قاعدة عملية للكتاب كله: مرّر الصور العكسية عبر عمليات المجموعات بلا تردد، وعامِل الصور بحذر.

تعريف 1.3 (مجموعة القسمة)

لتكن $\mathcal{R}$ علاقة تكافؤ على $E$ . تُسمى مجموعة القسمة $E/\mathcal{R}$ مجموعة أصناف التكافؤ؛ والتطبيق الشامل $\pi \colon E \to E/\mathcal{R}$ ، $x \mapsto \mathrm{cl}(x)$ ، هو الإسقاط القانوني.

الخاصية الشمولية (التحليل إلى عوامل): إذا كان $f \colon E \to F$ متوافقًا مع $\mathcal{R}$ (أي $x \mathbin{\mathcal{R}} y \implies f(x) = f(y)$ )، فهناك تطبيق وحيد $\overline f \colon E/\mathcal{R} \to F$ يحقق $f = \overline f \circ \pi$ .

برهان الخاصية الشمولية. الوحدانية: الشرط $f = \overline f \circ \pi$ يُكتب

\overline f\bigl(\mathrm{cl}(x)\bigr) = f(x) \qquad (x \in E),

وبما أن $\pi$ شامل، فإن كل عنصر من $E/\mathcal{R}$ هو $\mathrm{cl}(x)$ ما: فقيم $\overline f$ كلها مفروضة. الوجود: نأخذ الصيغة المعروضة تعريفًا للتطبيق $\overline f$ ؛ وهي غير ملتبسة بالضبط بفضل التوافق — إذ إن $\mathrm{cl}(x) = \mathrm{cl}(y)$ يعطي $x \mathbin{\mathcal{R}} y$ ، ومنه $f(x) = f(y)$ فتتفق القيمتان المرشحتان — وهي تُحلّل $f$ بحكم الإنشاء. ولاحظ تقسيم العمل: شمول $\pi$ يعطي الوحدانية، والتوافق يعطي الوجود. ∎

مثال 1.4

$\Z/n\Z$ هي قسمة $\Z$ على التوافق ترديد $n$ ؛ وعمليات التحقق من حسن التعريف في مجلد السنة الأولى كانت حالات خاصة من الخاصية الشمولية. فمجموعات القسمة تحوّل “الإنشاءات المتوافقة على الممثلين” إلى تطبيقات صريحة — وهذا ما نستعمله باستمرار فيما يلي.

1.2 قابلية العد والقوة

تعريف 1.5 (تساوي القوة، قابلية العد)

تكون مجموعتان متساويتي القوة إذا وُجد تقابل بينهما. وتكون مجموعة قابلة للعد إذا كانت مساوية القوة للمجموعة $\N$ (يُدرج بعض المؤلفين المجموعات المنتهية؛ نقول نحن قابلة للعد على الأكثر بمعنى “منتهية أو قابلة للعد”).

قضية 1.6 (خواص الاستقرار)

كل جزء غير منته من $\N$ قابل للعد؛ ومجموعة تكون قابلة للعد على الأكثر إذا وفقط إذا انغرست في $\N$ إذا وفقط إذا كانت خالية أو صورة شاملة للمجموعة $\N$ .
$\N \times \N$ قابلة للعد؛ وجداء مجموعتين قابلتين للعد على الأكثر قابل للعد على الأكثر.
اتحاد قابل للعد على الأكثر من مجموعات قابلة للعد على الأكثر هو قابل للعد على الأكثر.
$\Z$ و $\Q$ قابلتان للعد.

برهان. (1) نُرتّب جزءًا غير منته $A \subseteq \N$ بأخذ الأصغر تكرارًا: $a_0 = \min A$ ، $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (غير خالية لأن $A$ غير منتهية)؛ فالتطبيق $k \mapsto a_k$ متزايد تمامًا، ومتباين، وشامل على $A$ (فكل $a \in A$ يفوق عددًا منتهيًا فقط من عناصر $A$ ، ومن ثم يُبلَغ). وإذا انغرست $E$ في $\N$ بواسطة $\varphi$ ، فإن $E$ مساوية القوة للمجموعة $\varphi(E) \subseteq \N$ : أي منتهية أو قابلة للعد. وإذا كان $s \colon \N \to E$ شاملًا، فإن $x \mapsto \min s^{-1}(\{x\})$ يغرس $E$ في $\N$ .

(2) التطبيق $(p, q) \mapsto 2^p(2q + 1) - 1$ تقابل $\N^2 \to \N$ (فلكل عدد صحيح موجب تفكيك وحيد إلى فردي وقوة للعدد 2 على الصورة $2^p m$ مع $m$ فردي، بحكم وحدانية التفكيك). أما الجداءات: فنركّب الغرسات.

(3) لتكن مجموعات $E_n$ مع تطبيقات شاملة $s_n \colon \N \to E_n$ (ولا ضير إذا كانت بعض $E_n$ منتهية: نكرر القيم)، فالتطبيق $(n, k) \mapsto s_n(k)$ شامل من المجموعة القابلة للعد $\N^2$ على $\bigcup E_n$ .

(4) $\Z = \N \cup (-\N^*)$ : اتحاد قابل للعد. و $\Q$ صورة شاملة للمجموعة $\Z \times \N^*$ (تطبيق الكسر)، ومن ثم قابلة للعد على الأكثر، وهي غير منتهية. ∎

مثال 1.7 (دالة ازدواج، محسوبة)

التقابل $(p, q) \mapsto 2^p(2q + 1) - 1$ الوارد في البرهان جدير بأن نراه في العمل. وهذه قيمه الأولى:

\begin{array}{c|ccccc} & q = 0 & q = 1 & q = 2 & q = 3 & q = 4\\ \hline p = 0 & 0 & 2 & 4 & 6 & 8\\ p = 1 & 1 & 5 & 9 & 13 & 17\\ p = 2 & 3 & 11 & 19 & 27 & 35\\ p = 3 & 7 & 23 & 39 & 55 & 71 \end{array}

يجمع السطر $p$ الأعداد الصحيحة $n$ التي يقبل من أجلها $n + 1$ القسمة تمامًا على $2^p$ : فكل عدد طبيعي يظهر مرة واحدة بالضبط. وفكّ الترميز صريح كترميزه: من أجل $n = 43$ ، نفكك $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ ، ومنه $(p, q) = (2, 5)$ . والفكرة الختامية: براهين قابلية العد كثيرًا ما تكون خوارزميات متخفية — وهي هنا “أخرِج قوى العدد 2”.

مثال 1.8 (الأعداد الجبرية قابلة للعد)

يكون عدد عقدي جبريًا إذا أعدم كثير حدود غير معدوم بمعاملات ناطقة. ومجموعة الأعداد الجبرية $\overline\Q$ قابلة للعد: فكثيرات الحدود من الدرجة $\leq d$ على $\Q$ تنغرس في $\Q^{d+1}$ ، وهو جداء منته لمجموعات قابلة للعد (القضية 1.6 (2))؛ والاتحاد على $d$ يُعدّد كثيرات الحدود الناطقة غير المعدومة على الصورة $P_0, P_1, P_2, \dots$ ؛ ولكل $P_k$ عدد منته من الجذور؛ و

\overline\Q = \bigcup_{k \in \N}\ \{\text{جذور } P_k\}

هو اتحاد قابل للعد لمجموعات منتهية (القضية 1.6 (3))، وهو غير منته لأنه يحتوي $\Q$ . وباقتران ذلك بعدم قابلية $\R$ للعد (المبرهنة 1.9 أدناه)، نبرهن — دون إبراز عدد واحد — على وجود الأعداد المتسامية وعلى أنها تشكّل الأغلبية غير القابلة للعد: إنها حجة العدّ عند كانتور سنة 1874، وجودٌ بالقوة وحدها.

مبرهنة 1.9 (كانتور؛ عدم قابلية $\R$ للعد)

من أجل كل مجموعة $E$ ، لا يوجد تطبيق شامل $E \to \mathcal{P}(E)$ .
$\R$ غير قابلة للعد.

برهان. (1) بُرهن عليه في مجلد السنة الأولى (المجموعة القطرية $D = \{x : x \notin f(x)\}$ ).

(2) لنفترض أن $(x_n)_{n \in \N}$ يُعدّد $\R$ . نبني قطعًا متداخلة $I_0 \supseteq I_1 \supseteq \dots$ بحيث $\abs{I_n} = 3^{-n}$ و $x_n \notin I_n$ : نقسم القطعة الجارية إلى ثلاثة أثلاث مغلقة؛ فأحد الأثلاث على الأقل يتجنب $x_n$ (لأن نقطة تلتقي اثنين على الأكثر من الثلاثة). ومبرهنة القطع المتداخلة (بأطراف متجاورة) تعطي $\ell \in \bigcap_n I_n$ ؛ لكن $\ell = x_N$ من أجل $N$ ما، و $x_N \notin I_N$ : تناقض. ∎

مبرهنة 1.10 (كانتور–برنشتاين)

إذا انغرست $E$ في $F$ وانغرست $F$ في $E$ ، فإن $E$ و $F$ متساويتا القوة.

برهان. ليكن $f \colon E \to F$ و $g \colon F \to E$ غرستين. من أجل كل نقطة (من $E$ أو $F$ )، نتتبع سلسلة أسلافها من الصور العكسية المتتابعة، $x \mapsto g^{-1}(x) \mapsto f^{-1}(g^{-1}(x)) \mapsto \dots$ — وكل خطوة معرَّفة ما دامت النقطة الجارية تنتمي إلى صورة الغرسة المعنية، وهي عندئذٍ وحيدة بحكم التباين. وهناك ثلاثة مصائر يستبعد بعضها بعضًا: تتوقف السلسلة عند نقطة من $E \setminus g(F)$ (المنشأ في $E$ )، أو تتوقف عند نقطة من $F \setminus f(E)$ (المنشأ في $F$ )، أو لا تتوقف أبدًا. وهذا يقسم $E = E_E \cup E_F \cup E_\infty$ و $F = F_E \cup F_F \cup F_\infty$ حسب المنشأ.

ولنلاحظ الآن: $f$ يرسل $E_E$ على $F_E$ — فسلسلة $f(x)$ هي سلسلة $x$ مسبوقة بخطوة واحدة، ومن ثم يتطابق المنشآن؛ ولكل $y \in F_E$ سلسلة فيها خطوة واحدة على الأقل (لأن منشأه يقع في $E$ )، ومنه $y = f(x)$ مع $x \in E_E$ . والحجة نفسها تعطي تقابلين $f \colon E_\infty \to F_\infty$ و $g \colon F_F \to E_F$ . وباللصق، فإن

h(x) = \begin{cases} f(x) & \text{إذا كان } x \in E_E \cup E_\infty,\\ g^{-1}(x) & \text{إذا كان } x \in E_F, \end{cases}

تقابل من $E$ على $F = F_E \cup F_\infty \cup F_F$ : فهو تقابل على كل قطعة، والقطع الثلاث في المجموعة الهدف منفصلة مثنى مثنى. ∎

مثال 1.11

$\intoo{0}{1}$ و $\intcc{0}{1}$ متساويتا القوة: فالمطابق يغرس في اتجاه، و $x \mapsto \frac{x + 1}{3}$ في الاتجاه الآخر؛ والمبرهنة تصنع التقابل (غير المتصل بالضرورة). وكذلك $\R$ و $\intoo{0}{1}$ (بتقابلات من نمط $\tanh$ ) و $\mathcal{P}(\N)$ (بالنشر الثنائي، التمرين 1.3) كلها متساوية القوة: إنها “قوة المتصل”.

مثال 1.12 (القطعة والمربع)

$\intcc{0}{1}$ و $\intcc{0}{1}^2$ متساويتا القوة — فالبعد غير مرئي للقوة. إحدى الغرستين بديهية: $x \mapsto (x, 0)$ . أما الأخرى فنرسل $(x, y)$ إلى العدد الحقيقي الذي تتشابك أرقامه العشرية مع أرقام $x$ و $y$ ،

(0.x_1x_2x_3\dots,\ 0.y_1y_2y_3\dots) \;\longmapsto\; 0.x_1y_1x_2y_2x_3y_3\dots,

مع اختيار النشر الذي لا ينتهي بالرقم $9$ المتكرر من أجل كل إحداثي: وبهذا الاصطلاح تحدد أرقام الصورة أرقام $x$ و $y$ ، فالتطبيق متباين (ولا يلزم أن يكون شاملًا — إذ لا تحتوي الصور مثلًا على أرقام في المواضع الفردية تنتهي إلى $9$ — ولا ضير في ذلك). ومبرهنة كانتور–برنشتاين (المبرهنة 1.10) تُركّب تقابلًا حقيقيًا. أما الاتصال فميؤوس منه بالطبع: لا يمكن أن يوجد تقابل متصل بينهما — وفصول الفضاءات المترية تشرح السبب (الترابط يميز المستقيم عن المستوي، الفصل 4).

1.3 الزمر

تعريف 1.13 (الزمرة الجزئية المولَّدة؛ الرتبة)

لتكن $G$ زمرة وليكن $A \subseteq G$ . الزمرة الجزئية المولَّدة بالجزء $A$ ، ويُرمز إليها $\langle A \rangle$ ، هي أصغر زمرة جزئية تحتوي $A$ — وهي بالتحديد مجموعة كل الجداءات المنتهية لعناصر $A$ ومقلوباتها. وتكون زمرة دورية إذا كانت مولَّدة بعنصر واحد: $\langle a\rangle = \{a^k : k \in \Z\}$ . ورتبة العنصر $a \in G$ هي $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (وقد تكون غير منتهية)؛ وإذا كانت منتهية فهي أصغر $n \geq 1$ يحقق $a^n = e$ ، ويكون $a^k = e \iff \operatorname{ord}(a) \mid k$ .

برهان توصيف الرتبة. إذا وُجد $a^m = e$ يحقق $m \geq 1$ ، فليكن $n \geq 1$ أصغر عدد يحقق $a^n = e$ . عندئذٍ تكون العناصر $e, a, \dots, a^{n-1}$ مختلفة مثنى مثنى (إذ إن $a^{i} = a^{j}$ مع $0 \leq i < j < n$ يعطي $a^{j-i} = e$ ، وهذا ينقض الأصغرية)، وكل $a^k$ يؤول إلى أحدها بالقسمة الإقليدية $k = nq + r$ : فعدد عناصر $\langle a\rangle$ هو $n$ بالضبط، و $a^k = a^r = e \iff r = 0 \iff n \mid k$ . وإذا لم تكن أي قوة محايدة، فإن جميع $a^k$ ( $k \in \Z$ ) مختلفة (بحجة القسمة نفسها) والرتبة غير منتهية. ∎

مبرهنة 1.14 (لاغرانج)

لتكن $G$ زمرة منتهية ولتكن $H$ زمرة جزئية منها. عندئذٍ يقسم $\abs H$ العدد $\abs G$ . وعلى الخصوص تقسم رتبة كل عنصر $\abs G$ ، ويكون $a^{\abs G} = e$ لكل $a \in G$ .

برهان. العلاقة $x \sim y \iff x^{-1}y \in H$ علاقة تكافؤ (انعكاسية: $e \in H$ ؛ تناظرية: بالمقلوبات؛ متعدية: بالجداءات). وصنف $x$ هو الصنف الجانبي الأيسر $xH = \{xh : h \in H\}$ ، والتطبيق $h \mapsto xh$ تقابل $H \to xH$ (مقلوبه $y \mapsto x^{-1}y$ ): فلجميع الأصناف $\abs H$ عنصرًا. والأصناف تقسم $G$ (مبرهنة التقسيم العامة في مجلد السنة الأولى)، ومنه $\abs G = \abs H \times (\text{عدد الأصناف الجانبية})$ . أما من أجل عنصر: فنطبق هذا على $H = \langle a\rangle$ ؛ فينتج $a^{\abs G} = (a^{\operatorname{ord} a})^{\abs G / \operatorname{ord} a} = e$ . ∎

مثال 1.15 (الأصناف الجانبية في العمل: $A_3$ داخل $\mathfrak{S}_3$ )

لنأخذ $G = \mathfrak{S}_3$ (رتبتها $6$ ) و $H = A_3 = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$ . الأصناف الجانبية اليسرى هي

H = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}, \qquad (1\,2)H = \{(1\,2),\ (2\,3),\ (1\,3)\} :

أي صنفان من ثلاثة عناصر يقسمان $G$ ، تمامًا كما يقتضي العدّ $\abs G = \abs H \times (\text{عدد الأصناف الجانبية})$ — وهو بوضوح التقسيم إلى تبديلات زوجية وفردية. ولاحظ أن $(1\,3)H = (1\,2)H$ رغم أن $(1\,3) \neq (1\,2)$ : فالأصناف الجانبية أصناف لا تُسمّى بممثليها، و $x^{-1}y \in H$ هي المقارنة المشروعة الوحيدة. وهذه الصورة ذات الصنفين هي الصورة العامة للإشارة: فالزمرة $A_n$ وصنفها الجانبي الوحيد المرافق يقسمان $\mathfrak{S}_n$ نصفين، وهذا ما تعدّ به مسألة نهاية الأسبوع الوضعيات القابلة للبلوغ في الأحجية.

مثال 1.16

فائدتان مباشرتان. الزمر ذات الرتبة الأولية دورية: إذا كان $\abs G = p$ أوليًا و $a \neq e$ ، فإن $\operatorname{ord}(a)$ يقسم $p$ ولا يساوي $1$ ، ومنه فهو $p$ : أي $\langle a\rangle = G$ . شبكة الزمر الجزئية للزمرة $\Z/12\Z$ : حسب القضية 1.17 أدناه، هناك زمرة جزئية واحدة بالضبط لكل قاسم من قواسم $12$ — رتبها $1, 2, 3, 4, 6, 12$ ، مولَّدة على التوالي بالأصناف $\overline 0$ و $\overline 6$ و $\overline 4$ و $\overline 3$ و $\overline 2$ و $\overline 1$ . والتنبيه الختامي: عكس مبرهنة لاغرانج خاطئ عمومًا — فرتبة $A_4$ هي $12$ ولا تملك زمرة جزئية رتبتها $6$ ، كما نبرهن في مسألة نهاية الأسبوع في هذا الفصل (المسألة 1.1، السؤال 14). فلاغرانج يُقيّد الرتب الممكنة، لكنه لا يَعِد بها.

شبكة الزمر الجزئية للزمرة ℤ/12ℤ: زمرة جزئية واحدة لكل قاسم من قواسم 12 ()، مع حافة حين تحتوي إحداهما الأخرى بدليل أولي. والاحتواءات تسير عكس قابلية القسمة للمولّد: 4 ⊂eq 2 لأن 4 مضاعف للعدد 2. — شبكة الزمر الجزئية للزمرة $\Z/12\Z$ : زمرة جزئية واحدة لكل قاسم من قواسم $12$ (القضية 1.17)، مع حافة حين تحتوي إحداهما الأخرى بدليل أولي. والاحتواءات تسير *عكس* قابلية القسمة للمولّد: $\langle\overline 4\rangle \subseteq \langle\overline2\rangle$ لأن $4$ مضاعف للعدد $2$ .

قضية 1.17 (الزمر الدورية)

لتكن $G = \langle a \rangle$ دورية رتبتها $n$ .

$G$ متماثلة مع $(\Z/n\Z, +)$ ، بواسطة $\overline k \mapsto a^k$ .
كل زمرة جزئية من $G$ دورية؛ ولكل قاسم $d \mid n$ توجد زمرة جزئية وحيدة رتبتها $d$ ، وهي $\langle a^{n/d}\rangle$ .
يولّد $a^k$ الزمرة $G$ إذا وفقط إذا كان $\gcd(k, n) = 1$ : فعدد مولّدات $G$ يساوي $\varphi(n)$ (دالة أويلر).

برهان. (1) التطبيق $k \mapsto a^k$ من $\Z$ على $G$ متوافق مع الترديد بترديد $n$ ( $a^{k} = a^{k'} \iff n \mid k - k'$ ، حسب توصيف الرتبة)؛ والخاصية الشمولية (التعريف 1.3) تعطي تشاكلًا تقابليًا معرَّفًا جيدًا انطلاقًا من $\Z/n\Z$ .

(2) لتكن $H \leq G$ غير محايدة وليكن $m$ أصغر $\geq 1$ يحقق $a^m \in H$ . تُبيّن القسمة الإقليدية أن $H = \langle a^m\rangle$ (من أجل $a^k \in H$ : يفرض $k = mq + r$ أن $a^r \in H$ ، ومنه $r = 0$ )، وأن $m \mid n$ (بقسمة $n$ على $m$ : $a^{n \bmod m} \in H$ ). عندئذٍ $\abs H = n/m$ ؛ وأخذ $m = n/d$ يحقق كل قاسم $d$ . أما الوحدانية: فكل زمرة جزئية رتبتها $d$ هي، حسب ما تقدم، من الشكل $\langle a^m \rangle$ مع $n/m = d$ — ومن ثم يُفرض $m = n/d$ وتتحدد الزمرة الجزئية.

(3) ندّعي أن $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$ . لنكتب $d = \gcd(k, n)$ . من أجل أي $m \geq 1$ ، يعطي توصيف الرتبة في التعريف 1.13 سلسلة التكافؤات

(a^k)^m = e \iff n \mid km \iff \frac{n}{d} \,\Big|\, \frac{k}{d}\,m \iff \frac{n}{d} \,\Big|\, m ,

والخطوة الأخيرة بمبرهنة غاوس، لأن $\frac nd$ و $\frac kd$ أوليان فيما بينهما. وأصغر $m$ كهذا هو $\frac nd$ : أي $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$ ، وهو يساوي $n$ إذا وفقط إذا $\gcd(k, n) = 1$ . وهناك $\varphi(n)$ صنفًا $k$ كهذه بترديد $n$ . ∎

1.4 الزمرة المتناظرة

تعريف 1.18

$\mathfrak{S}_n$ هي زمرة تبديلات $\intint{1}{n}$ (رتبتها $n!$ ). والدورة $(a_1\,a_2\,\cdots\,a_k)$ ترسل $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ وتثبّت كل ما عداها؛ و $k$ هو طولها، والدورة ذات الطول $2$ تُسمى مبادلة. وتكون دورتان منفصلتين إذا كان حاملاهما (أي مجموعتا النقاط غير الثابتة) منفصلين.

مبرهنة 1.19 (التفكيك إلى دورات)

كل تبديلة $\sigma \neq \mathrm{id}$ جداء دورات منفصلة مثنى مثنى، وذلك بكيفية وحيدة إلى حدّ ترتيب العوامل. والدورات المنفصلة تتبادل، ورتبة $\operatorname{ord}(\sigma)$ هي المضاعف المشترك الأصغر للأطوال.

برهان. لننظر في علاقة “المدار” على حامل $\sigma$ : $x \sim y$ إذا وفقط إذا $y = \sigma^k(x)$ من أجل $k \in \Z$ ما — وهي علاقة تكافؤ. وكل صنف $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (منته، فتعود التكرارات دوريًا — إذ يجب أن يعود أول تكرار إلى $x$ بحكم التباين) يحمل الدورة $(x\ \sigma(x)\ \cdots\ \sigma^{k-1}(x))$ ، و $\sigma$ هو جداء هذه الدورات: فعلى كل مدار لا تؤثر إلا الدورة الموافقة. أما الوحدانية: فكل تفكيك إلى دورات منفصلة يعيد إنتاج المدارات بالضبط (إذ يجب أن تكون الدورة المارّة بالنقطة $x$ هي $(x\ \sigma(x)\ \cdots)$ ). والدورات المنفصلة تتبادل لأنها تحرّك نقاطًا منفصلة؛ وينتج قول الرتبة لأن $\sigma^m = \mathrm{id}$ إذا وفقط إذا كانت قوة $m$ لكل دورة محايدة (بحكم الانفصال)، إذا وفقط إذا قسم كل طول $m$ . ∎

مثال 1.20 (نمط الدورات بوصفه إحصاءً)

كم عدد تبديلات $\mathfrak{S}_9$ ذات نمط الدورات $(4, 3, 2)$ — دورة من الطول $4$ ، ودورة من الطول $3$ ، ومبادلة؟ نختار الحوامل والترتيبات الدورية:

\frac{9!}{4\cdot 3\cdot 2} = \frac{362\,880}{24} = 15\,120 :

نرصّ الرموز التسعة في سطر ( $9!$ طريقة)، ونُقوّس الأربعة الأولى ثم الثلاثة التالية ثم الأخيرين في دورات، ونقسم على الدورانات داخل كل قوس ( $4$ و $3$ و $2$ منها) التي تعطي التبديلة نفسها. (والأطوال هنا مختلفة، فلا قسمة إضافية؛ أما الأطوال المتساوية فتقتضي أيضًا القسمة على تبديلات الأقواس المتساوية.) ورتبة كل تبديلة كهذه $\operatorname{lcm}(4,3,2) = 12$ وإشارتها $(-1)^3(-1)^2(-1)^1 = +1$ (المبرهنة 1.19 ومبرهنة الإشارة أدناه). تقسيم واحد للعدد $9$ ، وصنف تقارن واحد، وإحصاء واحد — فتوافقيات $\mathfrak{S}_n$ هي حساب التقسيمات.

مبرهنة 1.21 (الإشارة)

يوجد تشاكل زمر وحيد $\varepsilon \colon \mathfrak{S}_n \to \{\pm 1\}$ (من أجل $n \geq 2$ ) يأخذ القيمة $-1$ على المبادلات: وهو الإشارة. زيادة على ذلك، $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ حيث $I(\sigma)$ هو عدد الانقلابات (أي الأزواج $i < j$ التي $\sigma(i) > \sigma(j)$ )، وإشارة الدورة ذات الطول $k$ هي $(-1)^{k-1}$ ، ورتبة الزمرة المتناوبة $A_n = \ker\varepsilon$ هي $\frac{n!}{2}$ .

برهان. الوجود. من أجل $\sigma \in \mathfrak{S}_n$ نضع

\varepsilon(\sigma) = \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i} .

تتضاعف القيم المطلقة للعوامل فيعطي جداؤها $1$ (لأن الأزواج غير المرتبة $\{\sigma(i), \sigma(j)\}$ تجري على كل الأزواج)، ومنه $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$ . أما التشاكل: فمن أجل $\sigma, \tau$ ،

\varepsilon(\sigma\tau) = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{j - i} = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{\tau(j) - \tau(i)} \cdot \prod_{i<j} \frac{\tau(j) - \tau(i)}{j - i} = \varepsilon(\sigma)\,\varepsilon(\tau),

والجداء الأوسط يساوي $\varepsilon(\sigma)$ بعد إعادة الترقيم حسب الأزواج $\{\tau(i), \tau(j)\}$ (فكل زوج غير مرتب يظهر مرة واحدة، ويتغير البسط والمقام في الإشارة معًا). وللمبادلة $\tau = (a\,b)$ مع $a < b$ عدد فردي من الانقلابات؛ وبالعدّ الدقيق: الأزواج المنقلبة $(i, j)$ و $i < j$ ، مع $\tau(i) > \tau(j)$ ، هي

(a, j) \ \text{من أجل } a < j < b, \qquad (i, b) \ \text{من أجل } a < i < b, \qquad (a, b) \ \text{نفسه},

أي $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ منها، وهو عدد فردي. (أو بديلًا: نتحقق مباشرة من $(1\,2)$ ، وفيها انقلاب واحد، ثم نُقارن — فللمقارنات إشارة واحدة لأن $\varepsilon$ تشاكل نحو زمرة تبادلية.) ومنه $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$ .

الوحدانية. تولّد المبادلات $\mathfrak{S}_n$ (فكل دورة $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$ ، والمبرهنة 1.19 يُتمّ العمل)؛ والتشاكل نحو $\{\pm1\}$ يتحدد بقيمه على المولّدات.

النتائج. تكتب متطابقة الدورات أعلاه الدورة ذات الطول $k$ جداءَ $k - 1$ مبادلة: فإشارتها $(-1)^{k-1}$ . وأما $A_n$ : فالتشاكل $\varepsilon$ شامل (إذ توجد مبادلات من أجل $n \geq 2$ )، و“الصنفان الجانبيان” $A_n$ و $(1\,2)A_n$ متساويا القوة ويقسمان $\mathfrak{S}_n$ (بحجة لاغرانج): ومنه $\abs{A_n} = \frac{n!}{2}$ . ∎

مثال 1.22

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix} = (1\,3\,5)(2\,6)$ : الرتبة $\operatorname{lcm}(3,2) = 6$ ، والإشارة $(-1)^{2}\cdot(-1)^{1} = -1$ . والإشارة أسرع اختبار للتماثل في الخلط — وهي محرّك المحدد في الفصل 2.

مثال 1.23 (ثلاث طرق إلى إشارة واحدة)

ليكن $\sigma \in \mathfrak{S}_5$ يرسل $1, 2, 3, 4, 5$ إلى $3, 5, 4, 1, 2$ . عبر الدورات: $1 \mapsto 3 \mapsto 4 \mapsto 1$ و $2 \mapsto 5 \mapsto 2$ ، ومنه $\sigma = (1\,3\,4)(2\,5)$ و $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$ . عبر الانقلابات: في قائمة القيم $3, 5, 4, 1, 2$ تكون الأزواج غير المرتبة هي $(3,1)$ و $(3,2)$ و $(5,4)$ و $(5,1)$ و $(5,2)$ و $(4,1)$ و $(4,2)$ : أي سبعة، ومنه $(-1)^7 = -1$ . عبر المبادلات: $\sigma = (1\,4)(1\,3)(2\,5)$ ، ثلاثة عوامل، ومنه $(-1)^3 = -1$ . ثلاث حسابات، وتماثل واحد: فالوحدانية في المبرهنة 1.21 تضمن ألا يختلف أي نظام مسك دفاتر عن غيره — وهذا بالضبط ما يجعل $\varepsilon$ صالحة بوصفها لا متغيّرًا (انظر مسألة نهاية الأسبوع).

ملاحظة 1.24 (إلى أين تمضي الإشارة من هنا)

الإشارة بذرة ثلاثة حصادات لاحقة: فهي تبني المحدد وقاعدة جدائه في الفصل 2؛ وتُشغّل لا متغيّرات التماثل في الأحاجي التوافقية (وتحلّ مسألة نهاية الأسبوع في هذا الفصل أحجية الخمسة عشر بها)؛ والزمر المتناوبة $A_n$ التي تعرّفها تصبح مركزية في مجلد السنة الثالثة، حيث تشرح بساطتها من أجل $n \geq 5$ لماذا لا تُحلّ المعادلات من الدرجة $5$ بالجذور.

1.5 الحلقات والمثاليات ومجموعات القسمة

تعريف 1.25 (المثالي)

لتكن $A$ حلقة تبادلية. المثالي $I \subseteq A$ هو زمرة جزئية جمعية تحقق $a x \in I$ لكل $a \in A$ و $x \in I$ . ونوى تشاكلات الحلقات مثاليات؛ ويكون $I = A$ إذا وفقط إذا $1 \in I$ إذا وفقط إذا احتوى $I$ وحدة. والمثالي المولَّد بالعنصر $x$ هو $xA = \{xa\}$ (ويُسمى مثاليًا رئيسيًا).

مبرهنة 1.26 (مثاليات $\Z$ ومثاليات $K[X]$ )

كل مثالي في $\Z$ هو $n\Z$ من أجل $n \in \N$ وحيد؛ وكل مثالي في $K[X]$ (حيث $K$ حقل) هو $P\,K[X]$ من أجل $P$ موحَّد وحيد (أو معدوم). ومن ثم يوجد القاسم المشترك الأكبر في الحلقتين مع علاقات بيزو: $x\Z + y\Z = \gcd(x,y)\Z$ ، وكذلك من أجل كثيرات الحدود.

برهان. من أجل $\Z$ كان هذا مبرهنة الزمر الجزئية في مجلد السنة الأولى (فالمثالي زمرة جزئية على الخصوص، و $n\Z$ مثالي). ومن أجل $K[X]$ : ليكن $I \neq \{0\}$ مثاليًا وليكن $P \in I$ غير معدوم من درجة دنيا، مُوحَّدًا بعد النظم. من أجل $F \in I$ ، تعطي القسمة الإقليدية $F = PQ + R$ كتابة $R = F - PQ \in I$ مع $\deg R < \deg P$ : فتفرض الأصغرية أن $R = 0$ ، ومنه $I = P\,K[X]$ . أما الوحدانية: فمولّدان موحَّدان يقسم كل منهما الآخر. وقولا بيزو هما تساوي المثالي $x\Z + y\Z$ (أو نظيره لكثيرات الحدود) مع المثالي الرئيسي المولَّد بالقاسم المشترك الأكبر — وهو نفسه تعريف القاسم المشترك الأكبر المستعمل في السنة الأولى، وقد صار الآن قولًا عن المثاليات. ∎

مثال 1.27 (قاسم مشترك أكبر لكثيري حدود، بطريقتين)

لنحسب $\gcd(X^3 - 1,\ X^2 - 1)$ في $\Q[X]$ . بخوارزمية إقليدس:

X^3 - 1 = X\,(X^2 - 1) + (X - 1), \qquad X^2 - 1 = (X + 1)(X - 1) + 0 ,

فالقاسم المشترك الأكبر هو $X - 1$ ، ويعطي التعويض الرجوعي علاقة بيزو

X - 1 = 1\cdot(X^3 - 1) - X\cdot(X^2 - 1).

بالمثاليات: المثالي $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ رئيسي (المبرهنة 1.26)؛ وهو يحتوي $X - 1$ (حسب الصيغة المعروضة) ومحتوى في $(X - 1)\Q[X]$ (لأن المولّدين ينعدمان عند $1$ ، ومن ثم فهما مضاعفان لكثير الحدود $X - 1$ ): فالمولّد الموحَّد هو $X - 1$ . والفكرة الختامية: وجهة نظر المثاليات تحدد القاسم المشترك الأكبر دون قسمة — فالجذور المشتركة تحدد موقع المثالي، وإقليدس لا يفعل سوى التصديق عليه.

تعريف 1.28 (حلقة القسمة $\Z/n\Z$ ، من جديد)

من أجل مثالي $I$ في $A$ ، تكون العلاقة $x \sim y \iff x - y \in I$ علاقة تكافؤ متوافقة مع $+$ و $\times$ ؛ وترث مجموعة القسمة $A/I$ بنية حلقة — هي حلقة القسمة — تجعل $\pi \colon A \to A/I$ تشاكلًا نواته $I$ . ومن أجل $A = \Z$ و $I = n\Z$ نجد $\Z/n\Z$ المعروفة من مجلد السنة الأولى، ولكن بخاصيتها الشمولية الآن: فكل تشاكل يُعدم $I$ يتحلل عبر $A/I$ .

مبرهنة 1.29 (مبرهنة البواقي الصينية، بصيغة الحلقات)

إذا كان $\gcd(m, n) = 1$ ، فإن التطبيق

\Z/mn\Z \longrightarrow \Z/m\Z \times \Z/n\Z, \qquad \overline{x} \longmapsto (x \bmod m,\; x \bmod n)

تماثل حلقات. ومن ثم $\varphi(mn) = \varphi(m)\varphi(n)$ من أجل $m, n$ أوليين فيما بينهما، و

\varphi(n) = n \prod_{p \mid n} \Bigl(1 - \frac 1p\Bigr) \quad (p \text{ أولي}).

برهان. التطبيق تشاكل حلقات معرَّف جيدًا (فأوجه التوافق مباشرة). أما التباين: فإن $x \equiv 0$ بترديد $m$ وبترديد $n$ مع $\gcd(m,n) = 1$ يفرض $mn \mid x$ (بمبرهنة غاوس). وأما الشمول: فللطرفين $mn$ عنصرًا، فيكفي التباين (تساوي القوى المنتهية) — أو صراحةً: انطلاقًا من علاقة بيزو $um + vn = 1$ ، فإن صنف

x = b\,um + a\,vn

يُرسَل إلى $(a \bmod m,\ b \bmod n)$ ، لأن $vn = 1 - um \equiv 1 \pmod m$ يجعل $x \equiv a \pmod m$ ، وبالتناظر بترديد $n$ — وهي الوصفة المستعملة عدديًا في المثال 1.30. وتوافق الوحدات أزواجَ الوحدات (فوحدات حلقة الجداء هي أزواج الوحدات)، ومنه $\varphi(mn) = \varphi(m)\varphi(n)$ . ومن أجل قوة أولية، $\varphi(p^k) = p^k - p^{k-1}$ (فغير الوحدات بترديد $p^k$ هي مضاعفات $p$ )؛ وتُركّب الضربية صيغة الجداء. ∎

مثال 1.30 (قلب التماثل الصيني)

لنأخذ $m = 8$ و $n = 9$ . يُصرَّح بمقلوب التماثل بواسطة العنصرين المتساويي القوى: نبحث عن $u \equiv 1 \pmod 8$ بحيث $u \equiv 0 \pmod 9$ و $v \equiv 0 \pmod 8$ ، وعن $v \equiv 1 \pmod 9$ . من $u = 9k \equiv 1 \pmod 8$ : نجد $k \equiv 1$ ، ومنه $u = 9$ ؛ ومن $v = 8k \equiv 1 \pmod 9$ : نجد $-k \equiv 1$ و $k \equiv 8$ ، ومنه $v = 64$ . عندئذٍ يكون صنف $x = 9a + 64b$ بترديد $72$ هو الحل الوحيد للشرطين $x \equiv a \pmod 8$ و $x \equiv b \pmod 9$ : فمن أجل $a = 3$ و $b = 5$ نجد $27 + 320 = 347 \equiv 59 \pmod{72}$ — وهي بالضبط القيمة الوسطى الموجودة بالتعويض في التمرين 1.8. والفكرة الختامية: يحقق $u$ و $v$ العلاقات $u + v \equiv 1$ و $uv \equiv 0$ و $u^2 \equiv u$ و $v^2 \equiv v$ بترديد $72$ ؛ وهما صورتا $(1, 0)$ و $(0, 1)$ ، وكل تفكيك صيني هو في جوهره تفكيك للواحد $1$ إلى عناصر متساوية القوى ومتعامدة.

مبرهنة 1.31 (أويلر؛ فيرما من جديد)

تشكّل وحدات $\Z/n\Z$ زمرة رتبتها $\varphi(n)$ ؛ ومنه من أجل $\gcd(a, n) = 1$ :

a^{\varphi(n)} \equiv 1 \pmod n \qquad (\text{مبرهنة أويلر}),

ومبرهنة فيرما الصغرى هي الحالة $n = p$ أولي، وقد صارت على بعد سطر واحد من لاغرانج.

برهان. الأصناف القابلة للقلب هي بالضبط أصناف الأعداد الصحيحة الأولية مع $n$ (مجلد السنة الأولى): وعددها $\varphi(n)$ ، وهي تشكّل زمرة بالضرب. ولاغرانج (المبرهنة 1.14): كل عنصر مرفوع إلى رتبة الزمرة يساوي المحايد. ∎

مثال 1.32 (زمرة وحدات بلا مولّد)

للزمرة $(\Z/15\Z)^*$ عدد عناصره $\varphi(15) = \varphi(3)\varphi(5) = 8$ . هل هي دورية؟ لنحسب الرتب مستعملين التماثل الصيني $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (فالوحدة بترديد $15$ زوج من الوحدات): رتبتا العاملين هما $2$ و $4$ ، ومنه تقسم رتبة كل عنصر $\operatorname{lcm}(2, 4) = 4 < 8$ — فلا عنصر يولّدها. وبالتحديد:

2^4 = 16 \equiv 1, \qquad 4^2 = 16 \equiv 1, \qquad 7^4 \equiv 1, \qquad 11^2 = 121 \equiv 1, \qquad 14^2 \equiv 1 \pmod{15} :

رتب هي $4, 2, 4, 2, 2$ ولا تبلغ $8$ أبدًا. وقارِن ذلك بالحالة التمرين 1.10: فالزمرة $(\Z/p\Z)^*$ دورية من أجل $p$ أولي، لأن زمرة الوحدات تقع هناك داخل حقل. وتبقى مبرهنة أويلر صالحة بالأس $\varphi(15) = 8$ ، لكن الأس الشمولي الحقيقي هنا هو $4$ — فأويلر حدّ أعلى، وليس دائمًا الحدّ الأمثل.

تعريف 1.33 (الجبر)

الجبر على $K$ هو فضاء متجهي $K$ على $A$ مزوَّد ببنية حلقة ضربها ثنائي الخطية على $K$ . أمثلة: $K[X]$ و $\mathcal{M}_n(K)$ و $\mathcal{L}(E)$ ، وفضاءات الدوال $\mathcal{F}(X, K)$ ، و $\C$ بوصفه جبرًا على $\R$ . وتشاكلات الجبور هي تشاكلات الحلقات الخطية؛ وتطبيق التقييم $P \mapsto P(u)$ من $K[X]$ نحو $\mathcal{L}(E)$ (أو $\mathcal{M}_n(K)$ ) هو المثال المركزي، وهو محرّك الفصل 3.

مثال 1.34 (تشاكل تقييم ونواته)

لنأخذ $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ وتطبيق التقييم $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$ ، $P \mapsto P(A)$ . بما أن $A^2 = 0$ ، فإن

P(A) = P(0)\,I + P'(0)\,A = \begin{pmatrix} P(0) & P'(0)\\ 0 & P(0)\end{pmatrix},

(إذ لا يبقى من $P$ إلا الحدّان الثابت والخطي). ومنه $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$ : وهو مثالي رئيسي، تمامًا كما تتنبأ به المبرهنة 1.26، ومولَّد بكثير الحدود $X^2$ الموحَّد ذي الدرجة الدنيا في النواة — أي كثير الحدود الأدنى للمصفوفة $A$ ، بطل الفصل 3. والصورة هي الجبر التبادلي ذو البعد اثنين $\{aI + bA\}$ : فتشاكلات التقييم تقلّص $\R[X]$ غير المنتهي البعد إلى جبور صغيرة قابلة للحساب.

ملاحظة 1.35 (آفاق: ثلاثة ألحان ينبغي الإصغاء إليها)

ثلاث أفكار بنيوية من هذا الفصل تتكرر في المجلد كله، في توزيع أوركسترالي أثقل في كل مرة. التحليل عبر مجموعة قسمة (التعريف 1.3): فهو يبني $\Z/n\Z$ هنا، ويعرّف تطبيقات على مجموعات حلول الجمل الخطية في الفصل 2، ويقوم صامتًا تحت كل حجة من نوع “معرَّف جيدًا على الأصناف”. اللامتغيّرات: فالإشارة تشاكل نحو $\{\pm1\}$ لا تستطيع أي نقلة مشروعة أن تراوغه — والمنطق نفسه يعطي قاعدة جداء المحدد (الفصل 2)، ولا تغيّر الأثر بالتشابه، والمقادير المصونة في الفصل 16. العدّ في مقابل بنية: فلاغرانج يعدّ عبر الأصناف الجانبية، والبعد يُعدّ عبر الأسس (الفصل 2)، والتضاعف يُعدّ عبر درجات كثيرات الحدود (الفصل 3)؛ وكلما بدا حدّ ما معجزًا، فثمة تقسيم أو تدريج يقوم بالعدّ.

ملاحظة 1.36 (مزالق شائعة)

أربعة كلاسيكية. (1) يجب التحقق من أن تطبيقًا على مجموعة قسمة معرَّف جيدًا: فالكتابة “ $\overline x \mapsto$ (صيغة في $x$ )” مشروعة فقط إذا كانت الصيغة ثابتة على الأصناف — أي توافق التعريف 1.3، وليست شكلية. (2) العلاقة $\operatorname{ord}(ab) = \operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ خاطئة عمومًا، حتى من أجل عنصرين متبادلين ( $a$ و $a^{-1}$ )؛ والتمرين 1.4 يعطي القول الصحيح في حالة التبادل مع رتبتين أوليتين فيما بينهما، والدورات المنفصلة تعطي الصيغة الصحيحة للتبديلات. (3) تصمد قابلية العد أمام الاتحادات القابلة للعد والجداءات المنتهية، لكن ليس أمام الجداءات القابلة للعد: فالمجموعة $\{0,1\}^{\N}$ غير قابلة للعد (التمرين 1.3) رغم أن لكل عامل عنصرين اثنين. (4) لا تحتاج مبرهنة كانتور–برنشتاين إلا إلى غرستين في الاتجاهين، لكن التقابل الذي تبنيه غير متصل عادة وغير صريح — فلا تنتظر صيغة (المثال 1.11).

ملاحظة 1.37 (أين يُستعمَل هذا الفصل)

في كل مكان تقريبًا. فالإشارة تبني المحددات (الفصل 2)؛ وتشاكل التقييم $P \mapsto P(u)$ والمثاليات الرئيسية في $K[X]$ تنتج كثيرات الحدود الدنيا وتفكيكات النواة في الفصل 3؛ وقابلية العد هي المسرح الذي يؤدي عليه الفصل 21 (الاحتمال على الفضاءات القابلة للعد) والسبب في أن الطوبولوجيا لا تكفّ عن إنتاج مجموعات كثيفة قابلة للعد (الفصل 4). ويُعاد نشر إنشاء القسمة $A/I$ في مجلد السنة الثالثة لبناء الحقول $K[X]/(P)$ ، ومنها نظرية غالوا: فالخاصية الشمولية المبرهَنة هنا تُستعمل هناك حرفيًا.

1.6 تمارين

تمرين 1.1 ★

أي المجموعات التالية قابلة للعد؟ مجموعة الأجزاء المنتهية من $\N$ ؛ ومجموعة كل أجزاء $\N$ ؛ و $\R \setminus \Q$ ؛ ومجموعة كثيرات الحدود ذات المعاملات الناطقة؛ ومجموعة المتتاليات المكوَّنة من $0$ و $1$ والمنعدمة ابتداءً من رتبة ما.

حل

حل التمرين 1.1.

الأجزاء المنتهية من $\N$ : قابلة للعد — فمجموعة أجزاء $\intint{0}{n}$ منتهية، والأجزاء المنتهية تشكّل الاتحاد القابل للعد على $n$ لهذه المجموعات (القضية 1.6 (3))؛ وهي غير منتهية لأنها تحتوي كل المجموعات الأحادية.

كل أجزاء $\N$ : غير قابلة للعد، بمبرهنة كانتور (المبرهنة 1.9 (1) مع $E = \N$ ).

$\R \setminus \Q$ : غير قابلة للعد — وإلا لكانت $\R = \Q \cup (\R\setminus\Q)$ اتحاد مجموعتين قابلتين للعد، وهذا يناقض المبرهنة 1.9 (2).

كثيرات الحدود على $\Q$ : قابلة للعد — فكثيرات الحدود من الدرجة $\leq n$ تنغرس في $\Q^{n+1}$ (جداءات منتهية لمجموعات قابلة للعد)، ثم نأخذ الاتحاد على $n$ .

المتتاليات الثنائية المنعدمة ابتداءً من رتبة ما: قابلة للعد — فهي تتقابل مع الأجزاء المنتهية من $\N$ (الحامل).

تمرين 1.2 ★

في $\mathfrak{S}_7$ ، ليكن $\sigma = (1\,4\,2\,6)(3\,5)$ و $\tau = (2\,3\,7)$ . احسب $\sigma\tau$ و $\tau\sigma$ على صورة دورات منفصلة، ورتب التبديلات الأربع وإشاراتها، و $\sigma^{2026}$ .

حل

حل التمرين 1.2.

نحسب عنصرًا عنصرًا، مع تطبيق العامل الأيمن أولًا. يرسل $\sigma\tau$ العناصر $1 \mapsto \sigma(1) = 4$ ، $\;2 \mapsto \sigma(3) = 5$ ، $\;3 \mapsto \sigma(7) = 7$ ، $\;4 \mapsto \sigma(4) = 2$ ، $\;5 \mapsto \sigma(5) = 3$ ، $\;6 \mapsto \sigma(6) = 1$ ، $\;7 \mapsto \sigma(2) = 6$ :

\sigma\tau = (1\,4\,2\,5\,3\,7\,6),

أي دورة ذات الطول $7$ . وكذلك يرسل $\tau\sigma$ العناصر $1 \mapsto \tau(4) = 4$ ، $\;2 \mapsto \tau(6) = 6$ ، $\;3 \mapsto \tau(5) = 5$ ، $\;4 \mapsto \tau(2) = 3$ ، $\;5 \mapsto \tau(3) = 7$ ، $\;6 \mapsto \tau(1) = 1$ ، $\;7 \mapsto \tau(7) = 2$ :

\tau\sigma = (1\,4\,3\,5\,7\,2\,6),

أي دورة ذات الطول $7$ أيضًا (كما هو متوقع: $\sigma\tau$ و $\tau\sigma$ متقارنان، ومن ثم لهما نمط الدورات نفسه).

الرتب والإشارات: نمط دورات $\sigma$ هو $(4,2)$ : الرتبة $\operatorname{lcm}(4,2) = 4$ ، والإشارة $(-1)^3(-1)^1 = +1$ ؛ و $\tau$ دورة ذات الطول $3$ : الرتبة $3$ ، والإشارة $+1$ ؛ والجداءان دورتان ذواتَا الطول $7$ : الرتبة $7$ ، والإشارة $(-1)^6 = +1$ .

$\sigma^{2026}$ : $2026 = 4 \times 506 + 2$ ، ومنه $\sigma^{2026} = \sigma^2 = (1\,2)(4\,6)$ (نربّع الدورة ذات الطول $4$ ؛ أما المبادلة فيزيلها التربيع).

تمرين 1.3 ★

أنشئ غرسات صريحة تُبيّن أن $\mathcal{P}(\N)$ و $\intcc{0}{1}$ ومجموعة المتتاليات الثنائية $\{0,1\}^{\N}$ متساوية القوة مثنى مثنى (بالنشر الثنائي في الاتجاهين؛ وتستوعب مبرهنة كانتور–برنشتاين إزعاج التمثيل المزدوج).

حل

حل التمرين 1.3.

$\{0,1\}^{\N} \to \mathcal{P}(\N)$ : نرسل كل متتالية إلى حاملها — وهذا تقابل (بالدوال المميّزة)، ولا حاجة إلى أي مبرهنة.

$\{0,1\}^{\N} \to \intcc{0}{1}$ : التطبيق بالأساس $3$ ، أي $(a_n) \mapsto \sum 2a_n 3^{-n-1}$ ، متباين (فمتتاليتان مختلفتان تختلفان أول ما تختلفان عند الرتبة $N$ ؛ ولا تستطيع الذيول تعويض فرق قدره $2\cdot 3^{-N-1}$ ، لأن $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} < 2\cdot3^{-N-1}$ ).

$\intcc{0}{1} \to \{0,1\}^{\N}$ : النشر الثنائي، مع اختيار (مثلًا) النشر الذي لا ينتهي بالرقم $1$ المتكرر: وهو متباين.

وبمبرهنة كانتور–برنشتاين (المبرهنة 1.10) مطبَّقة على الغرستين الأخيرتين، تكون $\intcc{0}{1}$ و $\{0,1\}^{\N}$ متساويتي القوة، ومنه فالمجموعات الثلاث كلها كذلك.

تمرين 1.4 ★

لتكن $G$ زمرة وليكن $a, b \in G$ عنصرين متبادلين رتبتاهما المنتهيتان $m$ و $n$ أوليتان فيما بينهما. برهن على أن $\operatorname{ord}(ab) = mn$ . بيّن بمثال في $\mathfrak{S}_3$ أن التبادل شرط جوهري.

حل

حل التمرين 1.4.

ليكن $c = ab = ba$ و $d = \operatorname{ord}(c)$ . أولًا $c^{mn} = a^{mn} b^{mn} = e$ (التبادل يسمح بتفكيك القوة)، ومنه $d \mid mn$ . وعكسيًا يعطي $c^d = e$ أن $a^d = b^{-d}$ ؛ وهذا العنصر يقع في $\langle a\rangle \cap \langle b\rangle$ ، وهي زمرة جزئية تقسم رتبتها كلًا من $m$ و $n$ (لاغرانج في كل زمرة دورية)، ومن ثم فهي محايدة: $a^d = b^d = e$ ، ومنه $m \mid d$ و $n \mid d$ ، وبالأولية فيما بينهما $mn \mid d$ . ومنه $d = mn$ .

وفي $\mathfrak{S}_3$ : نأخذ $a = (1\,2)$ (رتبتها $2$ ) و $b = (1\,2\,3)$ (رتبتها $3$ )، ورتبتاهما أوليتان فيما بينهما، وهما لا تتبادلان: فرتبة $ab = (2\,3)$ هي $2 \neq 6$ — وفعلًا ليس في $\mathfrak{S}_3$ عنصر رتبته $6$ . فالتبادل شرط جوهري.

تمرين 1.5 ★★

لتكن $G$ زمرة منتهية رتبتها زوجية. برهن على أن $G$ تحتوي عنصرًا رتبته $2$ . (قابِل بين كل عنصر ومقلوبه؛ وعُدّ العناصر المقابَلة بنفسها.)

حل

حل التمرين 1.5.

نقابل بين كل $x \in G$ و $x^{-1}$ . الأزواج $\{x, x^{-1}\}$ التي $x \neq x^{-1}$ ذات عنصرين وتقسم اتحادها؛ والعناصر الباقية هي بالضبط تلك التي $x = x^{-1}$ ، أي $x^2 = e$ . وبما أن $\abs G$ زوجي وأن الأزواج ذات العنصرين تغطي عددًا زوجيًا من العناصر، فإن قوة المجموعة $\{x : x^2 = e\}$ زوجية؛ وهي تحتوي $e$ ، ومن ثم تحتوي عنصرًا آخر $x \neq e$ على الأقل — أي عنصرًا رتبته $2$ .

تمرين 1.6 ★★

برهن على أن $A_n$ (من أجل $n \geq 3$ ) مولَّدة بالدورات ذات الطول $3$ . (جداء مبادلتين هو دورة ذات الطول $3$ أو جداء دورتين ذواتَي الطول $3$ .)

حل

حل التمرين 1.6.

كل عنصر من $A_n$ جداء عدد زوجي من المبادلات (المبرهنة 1.21: نفكك إلى مبادلات؛ والعدد زوجي لأن الإشارة $+1$ ). ويكفي أن نكتب كل جداء مبادلتين بدورات ذات الطول $3$ :

(a\,b)(a\,c) = (a\,c\,b), \qquad (a\,b)(c\,d) = (a\,c\,b)(a\,c\,d) \quad (\text{مختلفة } a,b,c,d),

(بالتحقق عبر التقييم)، و $(a\,b)(a\,b) = \mathrm{id}$ . ومنه فالدورات ذات الطول $3$ تولّد $A_n$ .

تمرين 1.7 ★★

عيّن كل تشاكلات الزمر: من $(\Q, +)$ نحو $(\Z, +)$ ؛ ومن $(\Z/n\Z, +)$ نحو $(\Z/m\Z, +)$ (عُدّها: $\gcd(m,n)$ )؛ ومن $(\Q, +)$ نحو $(\Q_+^*, \times)$ .

حل

حل التمرين 1.7.

$(\Q,+) \to (\Z,+)$ : التشاكل المعدوم وحده. فمن أجل أي $x$ ومن أجل كل $n \geq 1$ ، يقبل $f(x) = n f\bigl(\frac xn\bigr)$ القسمة على $n$ في $\Z$ ؛ والعدد الصحيح الوحيد الذي يقبل القسمة على كل $n$ هو $0$ ، ومنه $f(x) = 0$ لكل $x$ .

$(\Z/n\Z, +) \to (\Z/m\Z, +)$ : يتحدد التشاكل بالقيمة $c = f(\overline 1)$ ، التي يجب أن تحقق $n c \equiv 0 \pmod m$ ، أي أن $c$ مضاعف للعدد $\frac{m}{\gcd(m,n)}$ ؛ وهناك $\gcd(m,n)$ صنفًا كهذه، وكل اختيار يعرّف تشاكلًا فعلًا (نحلّل $k \mapsto kc$ عبر $\Z/n\Z$ بالخاصية الشمولية).

$(\Q, +) \to (\Q_+^*, \times)$ : التشاكل المحايد وحده. فإذا كان $f(x) = y$ ، فمن أجل كل $n$ لدينا $y = f(n \cdot \frac xn) = f(\frac xn)^n$ ، أي إن هذه القيمة قوة $n$ -ية في $\Q_+^*$ . لكن عددًا ناطقًا $y \neq 1$ لا يمكن أن يكون قوة $n$ من أجل كل $n$ : إذ يظهر عدد أولي ما في $y$ بأس غير معدوم $v$ ، و $n \nmid v$ من أجل $n > \abs v$ (فأسس القوى ذوات الأس $n$ مضاعفات للعدد $n$ ، بحكم وحدانية التفكيك). ومنه $f \equiv 1$ .

تمرين 1.8 ★★

باستعمال مبرهنة البواقي الصينية، احسب $\varphi(360)$ ، وجد كل $x$ بحيث $x \equiv 3 \pmod 8$ و $x \equiv 5 \pmod 9$ و $x \equiv 2 \pmod 5$ ، واحسب الرقمين الأخيرين من $3^{2026}$ (أويلر بترديد $100$ ؛ وانتبه: اعمل بترديد $4$ وبترديد $25$ ).

حل

حل التمرين 1.8.

$360 = 2^3 \cdot 3^2 \cdot 5$ : $\varphi(360) = 360\bigl(1 - \tfrac12\bigr)\bigl(1 - \tfrac13\bigr)\bigl(1 - \tfrac15\bigr) = 360 \cdot \tfrac12 \cdot \tfrac23 \cdot \tfrac45 = 96$ .

الجملة: القياسات $8, 9, 5$ أولية فيما بينها مثنى مثنى، وجداؤها $360$ . من $x \equiv 3 \pmod 8$ و $x \equiv 5 \pmod 9$ : نجد $x = 3 + 8k$ مع $3 + 8k \equiv 5 \pmod 9$ ، أي $-k \equiv 2$ ، و $k \equiv -2 \equiv 7 \pmod 9$ : ومنه $x \equiv 3 + 56 = 59 \pmod{72}$ . ثم $59 + 72\ell \equiv 2 \pmod 5$ : $4 + 2\ell \equiv 2$ ، $2\ell \equiv 3 \equiv 8$ ، $\ell \equiv 4 \pmod 5$ : ومنه $x \equiv 59 + 288 = 347 \pmod{360}$ .

الرقمان الأخيران من $3^{2026}$ : بترديد $4$ ، $3^{2026} = 9^{1013} \equiv 1$ . وبترديد $25$ : $\varphi(25) = 20$ و $2026 = 20\cdot101 + 6$ ، ومنه $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$ . نحلّ $x \equiv 1 \pmod 4$ ، $x \equiv 4 \pmod{25}$ : يعطي $x = 4 + 25k \equiv 1 \pmod 4$ أن $k \equiv 1 \pmod 4$ : ومنه $x \equiv 29 \pmod{100}$ . والرقمان الأخيران هما $29$ .

تمرين 1.9 ★★★

برهن على أن كل حلقة تامة منتهية حقل. استنتج أن $\Z/n\Z$ حقل إذا وفقط إذا كان $n$ أوليًا (مرة أخرى).

حل

حل التمرين 1.9.

لتكن $A$ حلقة تامة منتهية وليكن $a \in A$ ، $a \neq 0$ . التطبيق $x \mapsto ax$ متباين ( $ax = ay \implies a(x - y) = 0 \implies x = y$ ، إذ لا قواسم للصفر)؛ وكل تطبيق متباين من مجموعة منتهية إلى نفسها يكون شاملًا (مجلد السنة الأولى، تكافؤ مبدأ الجحور). ومنه $1 = ab$ من أجل $b$ ما: فكل عنصر غير معدوم قابل للقلب، و $A$ حقل.

$\Z/n\Z$ : إذا كان $n$ أوليًا فهي حلقة تامة ( $n \mid ab \implies n \mid a$ أو $n \mid b$ ، بمبرهنة إقليدس المساعدة)، ومنتهية، ومن ثم حقل؛ وإذا كان $n = rs$ مركّبًا فإن $\overline r\,\overline s = \overline 0$ يُبرز قواسم للصفر.

تمرين 1.10 ★★★

(كلاسيكي) ليكن $K$ حقلًا ولتكن $G$ زمرة جزئية منتهية من $(K^*, \times)$ . برهن على أن $G$ دورية. إرشاد: ليكن $m$ أكبر رتبة بين عناصر $G$ ؛ بيّن أن رتبة كل عنصر تقسم $m$ (باستعمال التمرين 1.4 على أجزاء أولية فيما بينها مناسبة)، فتحقق $G$ كلها $x^m = 1$ ؛ ثم عُدّ جذور $X^m - 1$ . وعلى الخصوص فإن $(\Z/p\Z)^*$ دورية.

حل

حل التمرين 1.10.

ليكن $m = \max\{\operatorname{ord}(x) : x \in G\}$ ، وهي مبلوغة عند $a$ .

الادعاء: رتبة كل $x \in G$ تقسم $m$ . لنفترض أن رتبة $x$ ما هي $q$ مع $q \nmid m$ : عندئذٍ توجد قوة أولية $p^k$ تقسم $q$ ولا تقسم $m$ . لنكتب $m = p^j m'$ مع $p \nmid m'$ و $j < k$ . رتبة العنصر $a^{p^j}$ هي $m'$ ؛ ورتبة العنصر $x^{q/p^k}$ هي $p^k$ ؛ والرتبتان أوليتان فيما بينهما والعنصران يتبادلان (لأن $G \subseteq K^*$ تبادلية)، ومنه حسب التمرين 1.4 تكون رتبة جدائهما $p^k m' > p^j m' = m$ : وهذا يناقض الأعظمية.

فتحقق إذن كل $x \in G$ العلاقة $x^m = 1$ : أي أن لكثير الحدود $X^m - 1$ $\abs G$ جذرًا على الأقل في الحقل $K$ ، ومنه $\abs G \leq m$ (فكثير حدود غير معدوم من الدرجة $m$ له $m$ جذرًا على الأكثر، مجلد السنة الأولى). لكن $m = \operatorname{ord}(a) \leq \abs G$ بمبرهنة لاغرانج. ومنه $m = \abs G$ ، وتكون $\langle a \rangle$ ، وقوتها $m = \abs G$ ، هي $G$ كلها: أي إنها دورية.

ومن أجل $K = \Z/p\Z$ : تكون $(\Z/p\Z)^*$ زمرة جزئية منتهية من $K^*$ ، ومن ثم دورية (رتبتها $p - 1$ ).

تمرين 1.11 ★★★

برهن على أن الزمرة $(\Q, +)$ ليست دورية، والأسوأ: أنها ليست حتى مولَّدة بجزء منته. وبرهن في المقابل على أن كل زمرة جزئية من $(\Q, +)$ مولَّدة بجزء منته تكون دورية.

حل

حل التمرين 1.11.

ليست دورية: تتكوّن الزمرة الجزئية $\langle \frac pq\rangle$ من المضاعفات الصحيحة للعدد $\frac pq$ ، وكلها ذات مقام يقسم $q$ (بعد الاختزال)؛ ومن ثم لا تحتوي $\frac{1}{2q}$ . فلا يستطيع مولّد وحيد أن يبلغ المقامات غير المحدودة في $\Q$ .

ليست مولَّدة بجزء منته: تتكوّن الزمرة الجزئية المولَّدة بالعناصر $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ من الأعداد الناطقة التي تقسم مقاماتها $Q = q_1 \cdots q_k$ (فالتراكيب الصحيحة لها مقام يقسم $Q$ ): وهي لا تحتوي $\frac{1}{2Q}$ .

الزمر الجزئية المولَّدة بجزء منته دورية: مع $Q$ كما تقدم، تكون الزمرة الجزئية $H = \langle \frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}\rangle$ محتواة في $\frac{1}{Q}\Z$ . والتطبيق $x \mapsto Qx$ تماثل من $\frac1Q\Z$ على $\Z$ يحمل $H$ إلى زمرة جزئية من $\Z$ ، وهي $n\Z$ من أجل $n$ ما (مجلد السنة الأولى): ومنه فالزمرة $H = \frac{n}{Q}\Z$ دورية، مولَّدة بالعنصر $\frac nQ$ .

تمرين 1.12 ★★

(محك ديدكيند) برهن على أن كل مجموعة غير منتهية تحتوي جزءًا قابلًا للعد، واستنتج أن مجموعة $E$ غير منتهية إذا وفقط إذا كانت مساوية القوة لجزء صحيح منها. (من أجل الاتجاه المباشر، أزِح جزءًا قابلًا للعد خطوة واحدة؛ ومن أجل العكس، تذكّر مبدأ الجحور.)

حل

حل التمرين 1.12.

جزء قابل للعد. لتكن $E$ غير منتهية. نبني $a_0, a_1, a_2, \dots$ بالتراجع: $E$ غير خالية، فنختار $a_0 \in E$ ؛ وإذا اختيرت $a_0, \dots, a_n$ ، فإن $E \setminus \{a_0, \dots, a_n\}$ غير خالية (لأن $E$ غير منتهية)، فنختار $a_{n+1}$ فيها. والعناصر $a_n$ مختلفة مثنى مثنى بحكم الإنشاء، ومنه فإن $A = \{a_n : n \in \N\}$ جزء قابل للعد من $E$ .

مجموعة غير منتهية $\implies$ مساوية القوة لجزء صحيح منها. نعرّف $f \colon E \to E \setminus \{a_0\}$ بالعلاقتين $f(a_n) = a_{n+1}$ و $f(x) = x$ من أجل $x \notin A$ . وهو متباين (فالقطعتان متباينتان وصورتاهما منفصلتان) وشامل على $E \setminus \{a_0\}$ : فكل $a_{n+1}$ مبلوغ، وكل $x \notin A$ مبلوغ. ومنه فإن $E$ مساوية القوة للجزء الصحيح $E \setminus \{a_0\}$ .

العكس. إذا كانت $E$ منتهية وكان $g \colon E \to F$ تقابلًا على $F \subseteq E$ مع $F \neq E$ ، فإن $g$ غرسة من $E$ في نفسها وليست شاملة، وهذا يناقض مبدأ الجحور (مجلد السنة الأولى: كل تطبيق ذاتي متباين على مجموعة منتهية تقابلي). ومنه فكل مجموعة مساوية القوة لجزء صحيح منها تكون غير منتهية.

1.7 مسألة: أحجية الخمسة عشر

أحجية الخمسة عشر لوحة من الحجم $4 \times 4$ تحمل خمس عشرة قطعة منزلقة مرقّمة من $1$ إلى $15$ وخانة فارغة واحدة؛ وتنقل النقلةُ إحدى القطع المجاورة للخانة الفارغة إليها. وفي تسعينيات القرن التاسع عشر روّج سام لويد للأحجية بعرضه $1000 لمن يستطيع أن يبادل بين القطعتين $14$ و $15$ ويعيد كل قطعة أخرى إلى مكانها. ولم يقبض أحد الجائزة قط، وتبرهن مسألة نهاية الأسبوع هذه على شقّي السبب: فإشارة المبرهنة 1.21 تمنع مبادلة لويد، و— وهذا هو الشق الأصعب، الإنشائي — كل ما تسمح به الإشارة قابل للحلّ فعلًا. والصياغة الكاملة هي مبرهنة جونسون–ستوري (1879).

الوضعية المحلولة ووضعية 14–15 عند سام لويد. والسؤال بجائزة $1000: هل تستطيع نقلات مشروعة أن تحوّل اللوحة اليمنى إلى اليسرى؟ — الوضعية المحلولة ووضعية $14$ – $15$ عند سام لويد. والسؤال بجائزة $1000: هل تستطيع نقلات مشروعة أن تحوّل اللوحة اليمنى إلى اليسرى؟

مسألة 1.1

مسألة نهاية الأسبوع — مبرهنة جونسون–ستوري في قابلية الحلّ

رقّم الخانات من $1$ إلى $16$ بترتيب القراءة (من اليسار إلى اليمين، ومن الأعلى إلى الأسفل)، بحيث تقع الخانة $k$ في السطر $i$ والعمود $j$ مع $k = 4(i - 1) + j$ . والخانة $16$ (أسفل اليمين) هي موطن الخانة الفارغة؛ ونعامل الخانة الفارغة كقطعة سادسة عشرة، تُكتب $b$ وتُماهى مع العدد $16$ . وتكون الوضعية تقابلًا $\sigma \colon \intint1{16} \to \intint1{16}$ ، أي خانة $\mapsto$ محتواها؛ والوضعية المحلولة هي $\sigma = \mathrm{id}$ . وفي كل ما يلي، $\varepsilon$ هي إشارة المبرهنة 1.21، وتكون خانتان متجاورتين إذا اشتركتا في حافة من اللوحة.

الجزء الأول — الوضعيات والنقلات والإشارات.

برّر أن الوضعيات هي بالضبط عناصر $\mathfrak{S}_{16}$ ، فيكون عددها $16! = 20\,922\,789\,888\,000$ ، وأن عدد النقلات المشروعة انطلاقًا من وضعية معطاة هو $2$ أو $3$ أو $4$ ، تبعًا لوقوع الخانة الفارغة في زاوية أو على حافة أو في الداخل.
لتكن $\sigma$ وضعية، ولتكن $p = \sigma^{-1}(16)$ خانة الفراغ، ولتكن $c$ خانة مجاورة للخانة $p$ . بيّن أن انزلاق قطعة $c$ إلى $p$ يعطي الوضعية $\sigma' = \sigma \circ \tau$ مع $\tau = (p\ c)$ ، واستنتج أن كل نقلة تقلب الإشارة: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
لوّن اللوحة كرقعة شطرنج: $\chi(k) = (-1)^{i+j}$ من أجل الخانة $k$ في السطر $i$ والعمود $j$ . بيّن أن كل نقلة تقلب $\chi(\text{خانة الفراغ})$ ، واستنتج أن كل متتالية نقلات تعيد الفراغ إلى خانته الابتدائية يكون طولها زوجيًا.
بيّن أن

$I(\sigma) = \varepsilon(\sigma)\, \chi\bigl(\sigma^{-1}(16)\bigr)$

لا متغيّر تحت كل نقلة مشروعة، واحسب $I(\mathrm{id})$ .

الجزء الثاني — جائزة لويد: اللامتغيّر في العمل.

توافق وضعية لويد $\sigma_L$ الوضعية المحلولة إلا في أن الخانتين $14$ و $15$ تحملان القطعتين $15$ و $14$ . احسب $I(\sigma_L)$ واستنتج أن لا متتالية نقلات تربط $\sigma_L$ بالوضعية المحلولة: فجائزة لويد لم تكن في خطر قط.
بيّن أن نصف الوضعيات بالضبط يحقق $I = +1$ : أي $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . (من أجل خانة فراغ ثابتة، قابِل بين الوضعيات بالتركيب مع مبادلة ثابتة لخانتين أخريين.)
بيّن أن كل نقلة تُلغى بنقلة مشروعة، وأن “ $\sigma'$ قابلة للبلوغ من $\sigma$ بنقلات مشروعة” علاقة تكافؤ، وأن صنف $R$ الوضعية المحلولة يحقق $R \subseteq \{I = +1\}$ . استنتج أن هناك صنفين على الأقل.
لنفترض أن الفراغ في موطنه: $\sigma(16) = 16$ . بيّن أن $I(\sigma) = \varepsilon(\rho)$ حيث $\rho \in \mathfrak{S}_{15}$ مقصور $\sigma$ على الخانات $1, \dots, 15$ ، وأن كل وضعية يمكن نقلها بنقلات مشروعة إلى وضعية فراغها في موطنه. استنتج: لبرهان $R = \{I = +1\}$ يكفي أن نحقق كل تبديلة زوجية للخانات الخمس عشرة غير الموطن بمتتالية نقلات تبدأ وتنتهي والفراغ في موطنه.

الجزء الثالث — جولات الفراغ وزمرة البرامج. البرنامج متتالية منتهية من النقلات المشروعة، تبدأ من وضعية فراغها في موطنه، وتكون وضعيتها النهائية بفراغ في موطنه أيضًا. وأثره هو التبديلة $\pi$ للخانات المعرَّفة بما يلي: محتوى الخانة $x$ ينتهي في الخانة $\pi(x)$ .

بيّن أن برنامجًا يُنفَّذ انطلاقًا من $\sigma$ ينتهي عند $\sigma \circ \pi^{-1}$ ؛ وأن تنفيذ برنامجين متتاليين يركّب أثريهما؛ وأن مجموعة $H$ كل الآثار زمرة جزئية من $\mathfrak{S}_{15}$ (تبديلات الخانات $1, \dots, 15$ ) محتواة في الزمرة المتناوبة $A_{15}$ .
(الجولة الأولية) انطلاقًا من الفراغ في موطنه، أزلق الفراغ حول المربّع $2 \times 2$ أسفل اليمين: أي الخانات $16 \to 12 \to 11 \to 15 \to 16$ . بيّن أن الأثر هو الدورة ذات الطول $3$ ، أي $(11\ 12\ 15)$ ، وأن الجولة العكسية تعطي $(11\ 15\ 12)$ . وكلاهما في $H$ .
(الجولة الكبرى) تحقّق من أن

$16 \to 15 \to 14 \to 13 \to 9 \to 5 \to 1 \to 2 \to 3 \to 4 \to 8 \to 7 \to 6 \to 10 \to 11 \to 12 \to 16$

مسير مغلق يمرّ بالخانات الست عشرة كلها (بخطوات بين متجاورين فقط)، وأن أثره هو الدورة ذات الطول $15$

$\zeta = (15\ 12\ 11\ 10\ 6\ 7\ 8\ 4\ 3\ 2\ 1\ 5\ 9\ 13\ 14) .$

وبكتابة $x_0 = 15$ و $x_1 = 12$ و $x_2 = 11$ ، …، و $x_{14} = 14$ لترتيبها الدوري، تحقّق من أن الجولة الأولية العكسية في السؤال 10 هي بالضبط $(x_0\ x_1\ x_2)$ .
برهن على صيغة المقارنة في أي $\mathfrak{S}_n$ : من أجل تبديلة $g$ ودورة ذات الطول $3$ ،

$g\,(a\ b\ c)\,g^{-1} = \bigl(g(a)\ g(b)\ g(c)\bigr),$

ولاحظ أن $H$ ، بوصفها زمرة، مغلقة تحت المقارنة بعناصرها.
استنتج أن $H$ تحتوي كل الدورات المتتالية الخمس عشرة ذات الطول $3$ في الجولة الكبرى:

$s_t = (x_t\ x_{t+1}\ x_{t+2}) \qquad (t \in \Z/15\Z, \text{ بأدلة بترديد } 15).$

الجزء الرابع — توليد الزمرة المتناوبة.

(المبرهنة المساعدة أ) لتكن $s$ و $t$ دورتين ذواتَي الطول $3$ يشترك حاملاهما في نقطتين بالضبط، وليكن حاملاهما $\{a, b, c\}$ و $\{b, c, d\}$ . بيّن أنه بعد تعويض $s$ أو $t$ بمقلوبها عند الاقتضاء (وهذا لا يغيّر شيئًا في الزمرة الجزئية المولَّدة)، يكون الجداء $st$ مبادلة مضاعفة؛ وبيّن أن $A_4$ لا تحتوي زمرة جزئية رتبتها $6$ (فالزمرة الجزئية ذات الدليل $2$ تحتوي كل مربّع؛ عُدّ الدورات ذات الطول $3$ بين المربعات)؛ واستنتج أن $\langle s, t\rangle$ هي الزمرة المتناوبة كاملةً على الحروف الأربعة $\{a, b, c, d\}$ .
(المبرهنة المساعدة ب) لتكن $X$ مجموعة من $k \geq 4$ حرفًا، مع $w \notin X$ ، ولتكن $G$ زمرة جزئية من $\mathfrak{S}_n$ ما تحتوي كل تبديلة زوجية للمجموعة $X$ ودورة واحدة ذات الطول $3$ هي $(u\ v\ w)$ مع $u, v \in X$ . بيّن أنه من أجل كل $a, b \in X$ مختلفة توجد تبديلة زوجية $g$ للمجموعة $X$ تحقق $g(u) = a$ و $g(v) = b$ ، ثم استنتج أن $(a\ b\ w) \in G$ .
استنتج أن الزمرة $G$ في المبرهنة المساعدة ب تحتوي كل تبديلة زوجية للمجموعة $X \cup \{w\}$ (استعمل التمرين 1.6: فالدورات ذات الطول $3$ تولّد). ثم، بتسلسل المبرهنتين المساعدتين أ وب على الدورات المتتالية ذوات الطول $3$ ، أي $s_0, s_1, \dots, s_{12}$ ، في السؤال 13، برهن على أن $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
استنتج أن $H = A_{15}$ : أي أن كل إعادة ترتيب زوجية للقطع الخمس عشرة قابلة للتحقيق ببرنامج، وأن $H$ تحتوي $15!/2 = 653\,837\,184\,000$ عنصرًا.
(مبرهنة جونسون–ستوري، 1879) اجمع الأسئلة 6 و7 و8 و17: الوضعيات القابلة للبلوغ من الوضعية المحلولة هي بالضبط الوضعيات $16!/2 = 10\,461\,394\,944\,000$ التي تحقق $I = +1$ ؛ وللبلوغ صنفان اثنان بالضبط، صنف الوضعية المحلولة وصنف وضعية لويد $\sigma_L$ . (من أجل النقطة الثانية، أعِد تسمية القطعتين $14$ و $15$ : بيّن أن $\sigma \mapsto (14\ 15) \circ \sigma$ يرسل متتاليات النقلات إلى متتاليات نقلات ويبادل بين $\{I = +1\}$ و $\{I = -1\}$ .)

الجزء الخامس — المحكّات والمتغيّرات والنظرة من فوق.

(المحك العملي) اقرأ القطع الخمس عشرة بترتيب قراءة خاناتها، متجاوزًا الفراغ، وليكن $N$ عدد انقلابات هذه القائمة؛ وليكن $r$ سطر الفراغ محسوبًا من الأسفل. بيّن أن $I(\sigma) = (-1)^{N + r + 1}$ ، فتكون $\sigma$ قابلة للحلّ إذا وفقط إذا كان $N + r$ فرديًا.
(فعل الزمر) فعل زمرة $G$ على مجموعة $X$ هو تطبيق $G \times X \to X$ ، $(g, x) \mapsto g \cdot x$ ، يحقق $e \cdot x = x$ و $g \cdot (h \cdot x) = (gh) \cdot x$ ؛ ومدار $x$ هو $G \cdot x$ ، ويكون الفعل حرًا إذا كان $g \cdot x = x$ يفرض $g = e$ . بيّن أن $h \cdot \sigma = \sigma \circ h^{-1}$ يعرّف فعلًا حرًا للزمرة $H$ على مجموعة الوضعيات ذوات الفراغ في الموطن، وأن مداراته هي بالضبط أصناف البلوغ المتبادل بالبرامج، واستنتج من عدد المدارات أن هذه الوضعيات تنقسم إلى $15!\,/\,\abs H = 2$ صنفًا بالضبط.
(عائق $3 \times 3$ ) بيّن أن اللوحة $3 \times 3$ لا تقبل أي مسير مغلق يزور كل خانة مرة واحدة بالضبط: فتفشل استراتيجية الجولة الكبرى في الجزء الثالث من أجل أحجية الثمانية. (لوّن الخانات التسع كرقعة شطرنج.)
(الإصلاح) على اللوحة $3 \times 3$ ذات الخانات من $1$ إلى $9$ بترتيب القراءة وموطنٍ هو $9$ : احسب أثري جولة المحيط $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (وهي دورة ذات الطول $7$ ، أي $\zeta'$ ، تثبّت المركز $5$ ) وجولة الزوايا $9 \to 6 \to 5 \to 8 \to 9$ (وهي دورة ذات الطول $3$ تمرّ بالمركز). وبمقارنة الثانية بقوى $\zeta'$ وتسلسل المبرهنتين المساعدتين أ وب، برهن على أن زمرة برامج أحجية الثمانية هي $A_8$ كاملةً، ومن ثم على أن $9!/2 = 181\,440$ بالضبط من الوضعيات $9! = 362\,880$ قابلة للحلّ.
(لوحة فقيرة) لتكن اللوحة الآن دورة واحدة من $n \geq 4$ خانة تحمل $n - 1$ قطعة. بيّن أن الترتيب الدوري للقطع لا متغيّر، وأن كل صنف بلوغ يحتوي بالضبط $n(n - 1)$ وضعية (فالأصناف هي مدارات زمرة دورية رتبتها $\operatorname{lcm}(n, n-1) = n(n-1)$ )، وأن عدد الأصناف هو $(n - 2)!$ — وهو من أجل $n \geq 5$ أكبر بكثير من $2$ : فعلى لوحة نحيلة لا يلتقط لا متغيّر التماثل شيئًا يُذكر، والهندسة هي الحاكمة.
حكمان بمحك السؤال 19: اللوحة المقلوبة كليًا (القطع $15, 14, \dots, 1$ في الخانات $1$ إلى $15$ ، والفراغ في موطنه)، واللوحة التي فيها الفراغ في الخانة $1$ تتلوه القطع $15, 14, \dots, 1$ في الخانات $2$ إلى $16$ . أيهما قابلة للحلّ؟
(تركيب) للبرهان ركيزتان مستقلتان: لا متغيّر ( $I$ ، مبني على تشاكل الإشارة) يبيّن أن نصف الوضعيات على الأكثر قابل للبلوغ، ومبرهنة توليد صريح ( $H = A_{15}$ ) تبيّن أن نصفها على الأقل قابل للبلوغ. بجملة واحدة لكل منها، قل أين دخل ما يلي: خاصية التشاكل في $\varepsilon$ ؛ ومبرهنة لاغرانج؛ وتوليد $A_n$ بالدورات ذات الطول $3$ ؛ والمقارنة. وصُغ المبدأ الشامل في سطر واحد.

حل

حل المسألة 1.1.

1. تُسند الوضعية إلى كل خانة من الخانات $16$ محتوى من المحتويات $16$ (القطع $1$ – $15$ أو الفراغ $b = 16$ )، مرة واحدة بالضبط لكل منها: أي بالضبط تقابل $\intint1{16} \to \intint1{16}$ ، وهو عنصر من $\mathfrak{S}_{16}$ ؛ وعددها $16! = 20\,922\,789\,888\,000$ . وتُزلق النقلة المشروعة قطعة واحدة مجاورة للفراغ، فيكون عدد النقلات هو عدد جيران خانة الفراغ: $2$ من أجل الخانات الزاوية الأربع، و $3$ من أجل الخانات الحافية الثماني، و $4$ من أجل الخانات الداخلية الأربع.

2. بعد الانزلاق، تحمل الخانة $p$ المحتوى السابق للخانة $c$ وتحمل الخانة $c$ الفراغ؛ وتبقى كل الخانات الأخرى دون تغيير: $\sigma'(p) = \sigma(c)$ ، $\sigma'(c) = \sigma(p) = 16$ ، و $\sigma' = \sigma$ في ما عدا ذلك. وهذا بالضبط $\sigma' = \sigma \circ (p\ c)$ . وبما أن $\varepsilon$ تشاكل وأن $\varepsilon\bigl((p\ c)\bigr) = -1$ : $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

3. تختلف الخانتان المتجاورتان بخطوة واحدة في إحدى الإحداثيتين دون الأخرى، ومن ثم يتغير تماثل $i + j$ : فتأخذ $\chi$ قيمتين متعاكستين على خانتين متجاورتين. وتنقل النقلةُ الفراغ من $p$ إلى $c$ المجاورة، فتقلب $\chi(\text{خانة الفراغ})$ . وعلى امتداد مسير مغلق للفراغ، تنقلب $\chi$ مرة واحدة في كل نقلة وتعود إلى قيمتها الابتدائية: فعدد النقلات زوجي.

4. حسب السؤالين 2 و3، تقلب النقلة الواحدة عاملَي $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$ كليهما؛ فلا يتغير جداؤهما. ومن أجل الوضعية المحلولة: $\varepsilon(\mathrm{id}) = +1$ والفراغ في الخانة $16$ ، أي السطر $4$ والعمود $4$ : ومنه $\chi(16) = (-1)^{8} = +1$ ، فيكون $I(\mathrm{id}) = +1$ .

5. $\sigma_L$ هي مبادلة الخانتين $(14\ 15)$ : $\varepsilon(\sigma_L) = -1$ ؛ وفراغها في موطنه، $\chi(16) = +1$ : ومنه $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$ . وبما أن $I$ تصمد أمام كل نقلة، فلا متتالية نقلات تربط $\sigma_L$ بالوضعية $\mathrm{id}$ . فالجائزة كانت في أمان بنيوي.

6. نثبّت خانة $p$ وخانتين أخريين $c \neq d$ مختلفتين عن $p$ ، ونضع $\tau_0 = (c\ d)$ . وعلى مجموعة الوضعيات ذات الفراغ في $p$ ، يكون التطبيق $\sigma \mapsto \sigma \circ \tau_0$ تقابلًا ذاتيًا من الرتبة اثنين (فهو يحافظ على $\sigma(p) = 16$ لأن $\tau_0$ يثبّت $p$ ) ويقلب $\varepsilon$ ، ومن ثم يقلب $I$ : فهو يقابل الوضعيات ذات $I = +1$ تقابلًا مع تلك ذات $I = -1$ . ومنه فكل موضع من مواضع الفراغ $16$ يسهم بعدد $15!/2$ من الوضعيات تحقق $I = +1$ ، ويكون

\abs{\{I = +1\}} = 16 \cdot \frac{15!}{2} = \frac{16!}{2}.

7. النقلة التي تُزلق قطعة $c$ إلى $p$ تُلغى بإزلاق القطعة نفسها (وهي الآن في $p$ ) عائدةً إلى $c$ : فالتركيب مع $(p\ c)$ مرتين هو المطابق. ومنه: الانعكاسية (بالمتتالية الخالية)، والتناظر (بعكس المتتالية وإلغاء كل نقلة)، والتعدي (بالتلاصق): أي علاقة تكافؤ. وكل $\sigma \in R$ يحقق $I(\sigma) = I(\mathrm{id}) = +1$ حسب السؤال 4، ومنه $R \subseteq \{I = +1\}$ ؛ و $\sigma_L \notin R$ يعطي صنفًا ثانيًا.

8. إذا كان $\sigma(16) = 16$ ، فإن $\sigma$ يبدّل الخانات $1, \dots, 15$ ؛ ولنُسمّ $\rho$ هذا المقصور. وإضافة نقطة ثابتة لا تغيّر نمط الدورات ولا الإشارة (نفكك $\rho$ إلى مبادلات؛ والجداء نفسه صالح في $\mathfrak{S}_{16}$ )، ومنه $\varepsilon(\sigma) = \varepsilon(\rho)$ ، ويعطي $\chi(16) = +1$ أن $I(\sigma) = \varepsilon(\rho)$ . وكل وضعية يمكن نقلها إلى وضعية فراغها في موطنه: فالشبكة مترابطة، فنسير بالفراغ على مسير من خانات متجاورة إلى الخانة $16$ (وكل خطوة نقلة مشروعة). ولنفترض الآن أن كل $\rho \in \mathfrak{S}_{15}$ زوجية محقَّقة ببرنامج. فلتكن $\sigma$ مع $I(\sigma) = +1$ : نسير بالفراغ إلى موطنه فنبلغ $\widetilde\sigma$ (وهي مكافئة للوضعية $\sigma$ )، مع $I(\widetilde\sigma) = +1$ ، أي إن مقصورها $\rho$ زوجي؛ والبرنامج الذي يحقق $\rho$ ينقل $\widetilde\sigma$ إلى $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (انظر السؤال 9). وبالتعدي $\sigma \in R$ ، ومنه $\{I = +1\} \subseteq R$ والمساواة.

9. نقلة واحدة: ينتهي محتوى $c$ في $p$ والفراغ في $c$ : فالأثر هو $\pi = (p\ c)$ ، وفعلًا $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$ . بالتراجع: إذا كان لمتتالية أثر $\pi_1$ وكانت تنقل $\sigma$ إلى $\sigma \circ \pi_1^{-1}$ ، فإن إتباعها بنقلة أثرها $\pi_2 = (p'\ c')$ يعطي $(\sigma \circ \pi_1^{-1}) \circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$ ، وتنتقل المحتويات بالتبديلة $\pi_2 \circ \pi_1$ (أولًا $\pi_1$ ، ثم $\pi_2$ ). فالآثار تتركّب، والبرنامج المنفَّذ انطلاقًا من $\sigma$ ينتهي عند $\sigma \circ \pi^{-1}$ . الزمرة الجزئية: أثر البرنامج الخالي هو $\mathrm{id}$ ؛ والتلاصق يعطي الجداءات؛ وعكس البرنامج (السؤال 7) يعطي المقلوبات. وأثر البرنامج يثبّت الخانة $16$ (فالفراغ يبدأ وينتهي في موطنه)، ومنه $H \leq \mathfrak{S}_{15}$ . الزوجية: برنامج من $k$ نقلة له $k$ زوجي (السؤال 3)، ويفرض $\varepsilon(\sigma \circ \pi^{-1}) = (-1)^k\varepsilon(\sigma)$ أن $\varepsilon(\pi) = +1$ : ومنه $H \subseteq A_{15}$ .

10. نتتبع الانزلاقات الأربعة انطلاقًا من الفراغ في $16$ : النقلة $16 \to 12$ ترسل محتوى $12$ إلى $16$ ؛ والنقلة $12 \to 11$ ترسل محتوى $11$ إلى $12$ ؛ والنقلة $11 \to 15$ ترسل محتوى $15$ إلى $11$ ؛ والنقلة $15 \to 16$ ترسل المحتوى المركون في $16$ (وأصله في $12$ ) إلى $15$ . والحصيلة: $11 \mapsto 12$ ، $12 \mapsto 15$ ، $15 \mapsto 11$ ، والفراغ في موطنه: فالأثر هو $(11\ 12\ 15)$ . والجولة العكسية تلغيه: أثرها $(11\ 12\ 15)^{-1} = (11\ 15\ 12)$ . وكلاهما أثر برنامج، ومن ثم في $H$ .

11. تجاور الخانات المتتالية: ففي كل زوج مذكور تختلف الخانتان بمقدار $1$ في السطر نفسه ( $16{-}15$ ، $15{-}14$ ، $14{-}13$ ؛ $1{-}2$ ، $2{-}3$ ، $3{-}4$ ؛ $8{-}7$ ، $7{-}6$ ؛ $10{-}11$ ، $11{-}12$ ) أو بمقدار $4$ داخل عمود ( $13{-}9$ ، $9{-}5$ ، $5{-}1$ ؛ $4{-}8$ ؛ $6{-}10$ ؛ $12{-}16$ ): أي مسير مغلق عبر الخانات $16$ كلها، طوله $16$ . أما الأثر: فكما في السؤال 10، بكتابة الخانات المزارة $c_0 = 16, c_1 = 15, \dots, c_{15} = 12$ : ينتقل محتوى $c_i$ إلى $c_{i-1}$ من أجل $i = 2, \dots, 15$ ، ويُحمل محتوى $c_1$ ، المركون في $16$ بعد النقلة الأولى، إلى $c_{15}$ بالنقلة الأخيرة. فيرسل الأثر إذن $15 \mapsto 12$ ، و $14 \mapsto 15$ ، $13 \mapsto 14$ ، $9 \mapsto 13$ ، $5 \mapsto 9$ ، $1 \mapsto 5$ ، $2 \mapsto 1$ ، $3 \mapsto 2$ ، $4 \mapsto 3$ ، $8 \mapsto 4$ ، $7 \mapsto 8$ ، $6 \mapsto 7$ ، $10 \mapsto 6$ ، $11 \mapsto 10$ ، $12 \mapsto 11$ : أي بالضبط الدورة ذات الطول $15$ ، وهي $\zeta$ . ويبدأ ترتيبها الدوري بالخانة $x_0 = 15$ ، $x_1 = 12$ ، $x_2 = 11$ ، ويرسل $(x_0\ x_1\ x_2) = (15\ 12\ 11)$ العنصر $15 \mapsto 12 \mapsto 11 \mapsto 15$ — وهو بالضبط $(11\ 15\ 12)$ ، أي الجولة الأولية العكسية.

12. ليكن $\gamma = (a\ b\ c)$ و $x \in \intint1n$ . إذا كان $x = g(a)$ : فإن $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$ ؛ وكذلك $g(b) \mapsto g(c)$ و $g(c) \mapsto g(a)$ . وإذا كان $x \notin \{g(a), g(b), g(c)\}$ ، فإن $g^{-1}(x) \notin \{a,b,c\}$ مثبَّت بالتبديلة $\gamma$ ، ومن ثم يبقى $x$ ثابتًا. ومنه $g\gamma g^{-1} = (g(a)\ g(b)\ g(c))$ . ومن أجل $g, h \in H$ ، نجد $ghg^{-1} \in H$ بحكم بديهيات الزمرة الجزئية.

13. $\zeta \in H$ (السؤال 11) و $s_0 = (x_0\ x_1\ x_2) \in H$ (السؤالان 10–11). وبما أن $\zeta(x_i) = x_{i+1}$ (بأدلة بترديد $15$ )، يعطي السؤال 12 أن

\zeta^{t}\,s_0\,\zeta^{-t} = \bigl(\zeta^t(x_0)\ \zeta^t(x_1)\ \zeta^t(x_2)\bigr) = (x_t\ x_{t+1}\ x_{t+2}) = s_t \in H \qquad (t = 0, 1, \dots, 14).

14. إلى حدّ القلب، لنفترض أن $s = (a\ b\ c)$ و $t = (b\ c\ d)$ (فالدورة ذات الطول $3$ على $\{a,b,c\}$ هي $(a\ b\ c)$ أو مقلوبها؛ وكذلك على $\{b,c,d\}$ ؛ وتعويض مولّد بمقلوبه لا يغيّر $\langle s, t\rangle$ ). عندئذٍ، بتطبيق $t$ أولًا،

st \colon a \mapsto b,\quad b \mapsto a,\quad c \mapsto d,\quad d \mapsto c, \qquad\text{أي}\quad st = (a\ b)(c\ d),

وهي مبادلة مضاعفة. وتتكوّن الزمرة الجزئية $G = \langle s, t\rangle$ من التبديلات الزوجية للحروف الأربعة، ومنه $G \leq A_4$ و $\abs G \mid 12$ ؛ وهي تحتوي عنصرًا رتبته $3$ وآخر رتبته $2$ ، ومن ثم $6 \mid \abs G$ (لاغرانج، المبرهنة 1.14، مطبَّقة على الزمرتين الدوريتين الجزئيتين). ولو كانت في $A_4$ زمرة جزئية $K$ رتبتها $6$ ، لكان دليلها $2$ ، ولكان عندئذٍ $g^2 \in K$ من أجل كل $g \in A_4$ : فمن أجل $g \in K$ هذا واضح؛ ومن أجل $g \notin K$ لا يوجد إلا الصنفان الجانبيان $K$ و $gK$ ، ومن ثم فالصنف $g^2K$ هو $K$ أو $gK$ ، ويفرض $g^2K = gK$ أن $g \in K$ . فكل مربّع يقع إذن في $K$ . لكن كل دورة ذات الطول $3$ ، أي $\gamma$ ، مربّع، إذ $\gamma = (\gamma^2)^2$ ، و $A_4$ تحتوي ثماني دورات ذات الطول $3$ : ومنه $8 > 6$ ، وهو تناقض. ومنه $\abs G = 12$ : أي $G = A_4$ .

15. نمدّد $u \mapsto a$ و $v \mapsto b$ إلى تقابل $g_0$ على $X$ (بإرسال الحروف $k - 2$ الباقية تقابليًا إلى متممة $\{a, b\}$ كيفما اتفق). وإذا كانت $g_0$ فردية، نختار حرفين مختلفين $s_1, t_1 \in X \setminus \{u, v\}$ (وهذا ممكن لأن $k \geq 4$ ) ونعوّض $g_0$ بالتبديلة $g_0 \circ (s_1\ t_1)$ ، وهي زوجية وما تزال ترسل $u \mapsto a$ ، $v \mapsto b$ . ثم نمدّد بالمطابق خارج $X$ : فنحصل على تبديلة زوجية $g \in G$ (فهي تبديلة زوجية للمجموعة $X$ ). عندئذٍ يعطي السؤال 12:

g\,(u\ v\ w)\,g^{-1} = (g(u)\ g(v)\ g(w)) = (a\ b\ w) \in G,

باستعمال $g(w) = w$ .

16. كل دورة ذات الطول $3$ في $X \cup \{w\}$ تقع في $G$ : فالدورات المحمولة في $X$ تبديلات زوجية للمجموعة $X$ ؛ وأما دورة حاملها $\{a, b, w\}$ فهي $(a\ b\ w)$ أو $(b\ a\ w)$ ، وكلتاهما يعطيها السؤال 15. وحسب التمرين 1.6، تولّد الدورات ذات الطول $3$ في المجموعة $X \cup \{w\}$ ذات $(k+1)$ عنصرًا زمرتَها المتناوبة، ومنه فإن $G$ تحتوي كل تبديلة زوجية للمجموعة $X \cup \{w\}$ . التسلسل: ليكن $G = \langle s_0, \dots, s_{12}\rangle$ . تعطي المبرهنة المساعدة أ مطبَّقة على $s_0 = (x_0\ x_1\ x_2)$ و $s_1 = (x_1\ x_2\ x_3)$ (وحاملاهما يشتركان في $\{x_1, x_2\}$ ) كل التبديلات الزوجية للمجموعة $X_4 = \{x_0, x_1, x_2, x_3\}$ . وإذا كانت $G$ تحتوي كل التبديلات الزوجية للمجموعة $X_m = \{x_0, \dots, x_{m-1}\}$ ( $4 \leq m \leq 14$ )، فإن $s_{m-2} = (x_{m-2}\ x_{m-1}\ x_m)$ فيها $u = x_{m-2}, v = x_{m-1} \in X_m$ والحرف الجديد $w = x_m$ : فتعطي المبرهنة المساعدة ب مع الجزء الأول كل التبديلات الزوجية للمجموعة $X_{m+1}$ . وبالتراجع إلى غاية $m = 14$ : $G \supseteq A_{15}$ (كل التبديلات الزوجية للخانات الخمس عشرة)، و $G \subseteq A_{15}$ لأن كل $s_t$ زوجية: ومنه $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .

17. السؤالان 13 و16: $A_{15} = \langle s_0, \dots, s_{12}\rangle \subseteq H$ ؛ والسؤال 9: $H \subseteq A_{15}$ . ومنه $H = A_{15}$ ، ورتبتها $15!/2 = 653\,837\,184\,000$ : فكل إعادة ترتيب زوجية للقطع الخمس عشرة أثرُ برنامج.

18. أرجع السؤال 8 إثبات $R = \{I = +1\}$ إلى تحقيق كل $\rho \in \mathfrak{S}_{15}$ زوجية ببرنامج: وقد تمّ ذلك في السؤال 17. ومع السؤال 6، نجد $\abs R = 16!/2 = 10\,461\,394\,944\,000$ . الصنفان: ليؤثّر $t_0 = (14\ 15)$ على المحتويات: $\varphi(\sigma) = t_0 \circ \sigma$ . فالنقلة المشروعة انطلاقًا من $\sigma$ نقلة مشروعة انطلاقًا من $\varphi(\sigma)$ (فخانة الفراغ لا تتغير: $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$ ، والخانة المنقولة هي نفسها)، و $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \tau$ : ومنه فإن $\varphi$ يرسل متتاليات النقلات إلى متتاليات نقلات، تقابليًا (فهو تقابل ذاتي من الرتبة اثنين). وهو يقلب $I$ : $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$ ، مع خانة الفراغ نفسها. ومنه فإن $\varphi$ يرسل صنف $R = \{I = +1\}$ الوضعية $\mathrm{id}$ تقابليًا على صنف $\varphi(\mathrm{id}) = \sigma_L$ ، وهو من ثم كل $\{I = -1\}$ : أي صنفان اثنان بالضبط. وهذه هي مبرهنة جونسون–ستوري.

19. نرقّم الخانات بترتيب القراءة ولتكن $k = 4(i - 1) + j$ خانة الفراغ. نعدّ انقلابات $\sigma$ (أي أزواج الخانات $x < y$ التي $\sigma(x) > \sigma(y)$ ): تسهم أزواج خانتَي قطعتين بمقدار $N$ ؛ وأما الأزواج التي تشمل الفراغ: فالخانات التي بعد الفراغ تحمل كلها قطعًا $< 16$ ، وكل منها منقلب ( $16 - k$ زوجًا)، والخانات التي قبله لا تنقلب أبدًا. ومنه $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$ . وبما أن $k = 4(i-1) + j \equiv j \pmod 2$ ،

I(\sigma) = (-1)^{N + j}\,(-1)^{i + j} = (-1)^{N + i} = (-1)^{N + r + 1}

باستعمال $i = 5 - r$ . وحسب السؤال 18، تكون $\sigma$ قابلة للحلّ إذا وفقط إذا $I(\sigma) = +1$ إذا وفقط إذا كان $N + r$ فرديًا. وللتحقق: الوضعية المحلولة، $N = 0$ ، $r = 1$ : فردي، فهي قابلة للحلّ؛ ووضعية لويد، $N = 1$ ، $r = 1$ : زوجي، فهي غير قابلة للحلّ.

20. الفعل: $e \cdot \sigma = \sigma \circ \mathrm{id} = \sigma$ و $g \cdot (h \cdot \sigma) = \sigma \circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot \sigma$ ؛ و $\sigma \circ h^{-1}$ وضعية فراغها في موطنه من جديد (لأن $h$ يثبّت الخانة $16$ ). الحرية: يعطي $\sigma \circ h^{-1} = \sigma$ أن $h^{-1} = \mathrm{id}$ (بالتركيب مع $\sigma^{-1}$ ). المدارات = أصناف البرامج: يقول السؤال 9 إن الوضعيات القابلة للبلوغ من $\sigma$ بالبرامج هي بالضبط $\sigma \circ \pi^{-1}$ ، $\pi \in H$ : أي المدار $H \cdot \sigma$ . العدّ: تجعل الحرية $h \mapsto h \cdot \sigma$ متباينًا، فيكون لكل مدار $\abs H = 15!/2$ عنصرًا؛ ومن ثم تنقسم الوضعيات $15!$ ذات الفراغ في الموطن إلى $15!\,/\,(15!/2) = 2$ مدارًا — وهي ظلّ صنفَي جونسون–ستوري في الوضعيات ذات الفراغ في الموطن.

21. الشبكة $3 \times 3$ ثنائية التجزئة بتلوين رقعة الشطرنج: فكل خطوة في مسير تغيّر اللون، ومن ثم يكون طول كل مسير مغلق زوجيًا. ولو وُجد مسير مغلق يزور كلًا من الخانات $9$ مرة واحدة بالضبط لكان طوله $9$ ، وهو فردي: وهذا مستحيل. فإنشاء الجولة الكبرى في الجزء الثالث غير متاح إذن في أحجية الثمانية.

22. جولة المحيط $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (وكل خطواتها بين متجاورين؛ وطولها $8$ ، وهو زوجي): حسب حساب السؤال 11 مع $c_1 = 8, c_2 = 7, c_3 = 4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$ ، يكون الأثر

\zeta' = (8\ 6\ 3\ 2\ 1\ 4\ 7),

أي دورة ذات الطول $7$ تثبّت المركز $5$ (فمحتوى $7$ ينتقل إلى $8$ ، ومحتوى $4$ إلى $7$ ، ومحتوى $1$ إلى $4$ ، ومحتوى $2$ إلى $1$ ، ومحتوى $3$ إلى $2$ ، ومحتوى $6$ إلى $3$ ، ومحتوى $8$ إلى $6$ ). جولة الزوايا $9 \to 6 \to 5 \to 8 \to 9$ : أثرها $(6\ 8\ 5)$ (فمحتوى $5$ ينتقل إلى $6$ ، ومحتوى $8$ إلى $5$ ، ومحتوى $6$ — المركون في $9$ — إلى $8$ ). ونضع $y_t = \zeta'^{\,t}(8)$ : فنجد $y_0 = 8, y_1 = 6, y_2 = 3, y_3 = 2, y_4 = 1, y_5 = 4, y_6 = 7$ . والمقارنة (السؤال 12):

\zeta'^{\,t}\,(6\ 8\ 5)\,\zeta'^{-t} = (y_{t+1}\ y_t\ 5) =: T_t \in H_{3\times3},

لأن $\zeta'$ يثبّت $5$ . وحاملا $T_0 = (y_1\ y_0\ 5)$ و $T_1 = (y_2\ y_1\ 5)$ يشتركان بالضبط في $\{y_1, 5\}$ : فتعطي المبرهنة المساعدة أ كل التبديلات الزوجية للمجموعة $\{y_0, y_1, y_2, 5\}$ . ثم يضيف $T_2 = (y_3\ y_2\ 5)$ العنصر $y_3$ بالمبرهنة المساعدة ب (فحروفه $y_2, 5$ تقع في المجموعة الجارية، و $k = 4$ )، وتضيف $T_3, T_4, T_5$ بدورها $y_4, y_5, y_6$ : فتقع كل التبديلات الزوجية للخانات الثماني غير الموطن في زمرة البرامج، التي تتكوّن هي أيضًا من تبديلات زوجية (فحجة السؤال 9 لا تتعلق باللوحة). ومنه $H_{3\times3} = A_8$ ، ويبيّن استدلال الأسئلة 6 و8 و18 — وهو أيضًا لا يتعلق باللوحة — أن الوضعيات القابلة للبلوغ هي بالضبط تلك التي $I = +1$ : أي نصف $9!$ ، أي $181\,440$ .

23. نُسمّي الخانات $0, \dots, n-1$ حول الدورة. وتبادل النقلةُ الفراغ مع أحد جاريه. ونقرأ القطع بالترتيب الدوري ابتداءً من موضع بُعيد الفراغ: فنحصل على كلمة $w$ تسرد القطع $n - 1$ . وتقديم الفراغ خطوة واحدة يعوّض $(p, w)$ بالزوج $(p + 1, \rho w)$ ، حيث $p$ خانة الفراغ و $\rho$ يدير الكلمة دوريًا بمقدار واحد؛ والنقلة الرجوعية هي المقلوب. فالترتيب الدوري للقطع (أي الكلمة إلى حدّ الدوران) لا متغيّر إذن. وصنف بلوغ $(p, w)$ هو مدار التطبيق $g \colon (p, w) \mapsto (p+1, \rho w)$ ، وهو عنصر رتبته $\operatorname{lcm}(n, n-1) = n(n-1)$ في جداء الزمرتين الدوريتين (انسحابات $\Z/n\Z$ ودورانات مواضع الكلمة $n-1$ )، والمضاعف المشترك الأصغر هو $n(n-1)$ لأن $\gcd(n, n-1) = 1$ : فلكل صنف بالضبط $n(n-1)$ وضعية، ولها جميعًا القلادة نفسها. والأصناف: $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$ . ومن أجل $n \geq 5$ ، $(n-2)! > 2$ : فلا متغيّر التماثل (صنفان في أحسن الأحوال) أعمى عن كل العائق تقريبًا؛ وثراء اللوحة $4 \times 4$ — حيث التماثل هو العائق الوحيد — واقعة هندسية أصيلة، لا شكلية.

24. في اللوحتين ترتيب القطع مقلوب كليًا، ومنه $N = \binom{15}{2} = 105$ في الحالتين (فكل زوج من القطع منقلب). الفراغ في موطنه: $r = 1$ ، و $N + r = 106$ زوجي: فهي غير قابلة للحلّ. الفراغ في الخانة $1$ : الفراغ في السطر الأعلى، و $r = 4$ ، و $N + r = 109$ فردي: فهي قابلة للحلّ. لوحتان لا تختلفان إلا في موضع الثقب تقعان على جانبَي الجدار.

25. خاصية التشاكل: تحوّل “نقلة واحدة = مبادلة واحدة” إلى “نقلة واحدة = قلب إشارة واحد” (السؤالان 2 و4)، فتجعل $I$ قابلة للحساب نقلةً نقلة. لاغرانج: فرض $6 \mid \abs{\langle s, t\rangle}$ في المبرهنة المساعدة أ وحدّد حجم الأصناف الجانبية في استبعاد الرتبة $6$ (السؤال 14). التوليد بالدورات ذات الطول $3$ : حوّل “ $H$ تحتوي ما يكفي من الدورات ذات الطول $3$ ” إلى “ $H$ تحتوي $A_{15}$ كلها” (السؤال 16). المقارنة: صنعت الدورات المتتالية الخمس عشرة ذوات الطول $3$ انطلاقًا من جولة $2 \times 2$ واحدة منقولة بالجولة الكبرى (السؤالان 12–13)، وصنعت الدورات ذوات الطول $3$ ، أي $(a\ b\ w)$ ، في المبرهنة المساعدة ب. المبدأ الشامل: لا متغيّرٌ يبرهن على الاستحالة، وإنشاءٌ صريح يبرهن على الإمكان، ولا تُحلّ المسألة تمامًا إلا حين يلتقي الحدّان — وهنا يلتقيان عند النصف.

المصطلحات المعرَّفة في هذا الفصل

عرض كل المصطلحات (395) في المسرد