#abstract_algebra #computer_science

חבורות ציקליות וסדרים

סדרים

נגדיר את הסדר של חבורה $G$ להיות עוצמתה $| G |$ .

הסדר של איבר: הסדר של איבר בחבורה $g \in G$ מסומן כ $o (g) = n$ הוא המספר הטבעי $n$ הקטן ביותר עבורו

g^{n} = e

אם לא קיים $n$ שכזה אז נגדיר את הסדר של האיבר להיות $\infty$ . וכמובן ש הסדר של $e$ הוא תמיד $1$ .

טענה: עבור $a \in G$ מתקיים

o (a) = o (a^{- 1})

הוכחה: נחלק למקרים

מקרה 1: $o (a) = n < \infty$ ולכן $a^{n} = e$ אם כן:

e = e^{n} = (a^{- 1} a)^{n} = (a^{- 1})^{n} a^{n} = (a^{- 1})^{n} e = (a^{- 1})^{n}

המעבר השלישי נכון בגלל שאיבר וההופכי שלו הם חילופיים ואנחנו יודעים שאם $a b = b a$ אז $(a b)^{n} = a^{n} b^{n}$ . סך הכל הראנו שהעלאת ההופכי בחזקת $n$ גם היא שקולה לאיבר היחידה של החבורה.

מקרה 2: $o (a) = \infty$ , נניח בשלילה ש $o (a^{- 1}) = n < \infty$ לפי המקרה הראשון נקבל שיוויון בסתירה לכך שהסדר של $a$ הוא אינסוף.

החבורה הציקלית

לפעמים תת חבורה תהיה תלויה לגמרי מאיבר בודד בחבורה המקורית , כלומר יהיה איבר בודד $a \in G$ שיאפשר לנו באמצעות ביצוע הפעולה של החבורה $G$ שוב ושוב על $a$ להגיע לתת חבורה.

הגדרה: תהי חבורה $G$ ויהי $a \in G$ . תת החבורה הנוצרת על ידי $a$ היא תת החבורה :

⟨ a ⟩ = {a^{k} | k \in Z}

הבחנה

אם אנחנו יודעים שפעולת החבורה היא $+$ אז נגדיר את החבורה הנוצרת על ידי $a$ כך:

⟨ a ⟩ = {k a | k \in Z}

דוגמה-

\forall_{n \in Z} : ⟨ n ⟩ = {k n | k \in Z} = n Z

כלומר $(n Z, +)$ היא תת חבורה של $Z$ .

הגדרת החבורה הציקלית : תהי חבורה $G$ ואיבר $a \in G$ . אם $G = ⟨ a ⟩$ אז נאמר ש $G$ נוצרת על ידי $a$ ונקרא ל $G$ חבורה ציקלית.

דוגמה חשובה

דוגמה חשובה לחבורה ציקלית היא $(Z_{n}, +)$ שהסדר שלה הוא $n$ . והיא ציקלית כי הוא שקולה ל $⟨ 1 ⟩$ .

למשל חבורת השלמים עם פעולת החיבור היא ציקלית של $⟨ 1 ⟩$ .
דוגמה נוספת היא חוג השאריות עם האיבר היוצר $⟨ 1 ⟩$ .

Info

כדאי לשים לב שאפשר שיהיה יותר מאיבר יוצר אחד, למשל עבור חבורה השלמים גם $- 1$ יהיה איבר יוצר ועבור $Z_{10}$ גם $9$ יהיה איבר יוצר, למעשה ישנם 4 איברים יוצרים בחבורה הזאת

הוכחה שתת חבורה ציקלית היא אכן חבורה :
נשים לב שמסגירות הכפל נובע שהיא תת קבוצה וגם $a^{0} = e$ ומהגדרת החזקה. כלומר איבר היחידה שייך לתת החבורה.
כעת, יהיו $b, c \in ⟨ a ⟩$ יתקיים

c = a^{i} b = a^{k}

a^{i} \cdot b^{- 1} = a^{i} (a^{k})^{- 1} = a^{i} \cdot a^{- k} = a^{i - k} \in ⟨ a ⟩

סך הכל זאת אכן תת חבורה לפי הקריטריון המקוצר (נשים לב שהחזקה אכן מספר שלם מסגירות חבורת השלמים לחיבור).

טענה כל חבורה ציקלית היא אבלית:
תהי $G$ חבורה ציקלית ונניח $G = ⟨ a ⟩$ . יהיו $b, c$ ב $G$ . יתקיים:

c = a^{i} b = a^{k}

ולכן

b c = a^{k} a^{i} = a^{k + i} = a^{i + k} = a^{i} a^{k} = c b

טענה כל תת חבורה של חבורה ציקלית היא ציקלית:
תהי $H \leq G$ תת חבורה. נסמן $G = ⟨ a ⟩$ . כל האיברים ב $G$ הם מהצורה $a^{i}$ אז ברור שגם האיברים ב $H$ הם מהצורה הזאת. אם $H$ היא החבורה הטירוויאלית, $H = {e}$ אז ברור שהיא ציקלית עם איבר יוצר $e$ .
אם $H$ לא טריוויאלית אז ניקח את המספר הטבעי הקטן ביותר עבורו $a^{s} \in H$ (בכוונה לקחנו טבעי כי אם $a^{s}$ בתת החבורה כמובן שגם $a^{- s}$ ). נרצה להוכיח ש $a^{s}$ הוא איבר היוצר את $H$ כלומר

H = ⟨ a^{s} ⟩

נעשה זאת בהכלה דו כיוונית.

יהי $a^{k s} \in ⟨ a^{s} ⟩$ , כמובן שמהגדרת פעולת החזקה יתקיים שמדובר בהפעלת פעולת החבורה על האיבר היוצר $k$ פעמים, ומסגירות נובע שבגלל ש $a^{s}$ ב $H$ אז גם $a^{s k}$ .
יהי $a^{i} \in H$ ממשפט החלוקה עם שארית אנחנו יודעים שאפשר לבטא את $i$ בתור $q s + r$ כאשר $r \in [0, s)$ כלומר:

a^{i} = a^{q s + r} = a^{q s} \cdot a^{r} = (a^{s})^{q} \cdot a^{r}

מכאן ניתן להגיד ש

a^{r} = a^{i} \cdot (a^{s})^{q} \in H

נשים לב $r = 0$ כי אם הוא היה שונה מ $0$ אז מצאנו חזקה שקטנה מ $s$ (לפי משפט אנחנו יודעים שהוא קטן ממנו) וטבעית כי $r$ חיובי שיקיים $a^{r} \in H$ בסתירה למינימליות של s.
לכן $r = 0$ ויתקיים:

a^{i} = (a^{s})^{q} \cdot a^{0} = (a^{s})^{q} \cdot e = (a^{s})^{q} \in ⟨ a^{s} ⟩

הבחנה:

$o (a) = | ⟨ a ⟩ |$

לכן לעתים כשנדבר על גודל החבורה נתייחס לסדר שלה. כמובן שאם $G$ חבורה סופית אז כל תת חבורה שנוצרת מ $a \in G$ היא סופית ולכן הסדר הוא גם טבעי

כדי להוכיח את ההבחנה הנ״ל נחלק למקרים שבו הסדר סופי ולמקרה בו הסדר אינסופי.
א) אם הסדר סופי נניח שהוא $n$ אז נרצה להוכיח ש

⟨ a ⟩ = {e, a, \dots, a^{n - 1}}

וגם שכל $a^{i} \neq a^{j}$ . בהכלה דו כיוונית קל לראות למה הקבוצה שלנו מוכלת בחבורה הנוצרת מ $a$ .
בכיוון השני, ניקח $a^{k} \in ⟨ a ⟩$ כאשר $k$ שלם. נוכל לבטא את $k$ באמצעות משפט החלוקה עם שארית על ידי

k = q \cdot n + r

כאשר $0 < r \leq n - 1$ ולכן:

a^{k} = a^{q n + r} = (a^{n})^{q} \cdot a^{r} = e^{q} \cdot a^{r} = a^{r}

המעבר השלישי נובע כי $n$ הסדר של $a$ בחבורה שהוא יוצר ולכן $a^{n} = e$ . אנחנו לא יודעים אומנם אם $r = k$ אבל אנחנו יכולים להגיד ש $a^{r} \in ⟨ a ⟩$ וזה מה שרצינו להוכיח.

נוכיח כעת שכל האיברים ב ${e, a, \dots, a^{n - 1}}$ שונים אחרת זה לא יכול להיות הסדר של $a$ ..
נניח בשלילה שקיים

0 \leq r_{1} \leq r_{2} \leq n - 1 $ $ כ ך ש $ $ a^{r_{1}} = a^{r_{2}}

יתקיים

e = a^{r_{2} - r_{1}} 0 \leq r_{2} - r_{2} \leq n - 1

כלומר מצאנו חזקה חיובית קטנה מ $n$ שעבורה $a^{r_{2} - r_{1}} = e$ בסתירה לכך שהסדר של $a$ הוא $n$ ולכן $r_{1} = r_{2}$ .

ב) אם הסדר הוא אינסופי $o (a) = \infty$ נוכיח שמספר האיברים בחבורה הנוצרת על ידי $a$ הוא גם $\infty$ .

נב״ש ש $| ⟨ a ⟩ | = n$ לכן קיימים $i, j$ כך ש

a^{i} = a^{j}

כלומר

e = a^{i - j}

בסתירה לכך שהסדר של $a$ הוא אינסופי.

משפט עבור חבורה $G$ ו $a \in G$ מתקיים ש $a^{n} = e$ אמ״מ $o (a) | n$ .

מכפלה ישרה של חבורות

נרצה להראות יכולת לבנות חבורות חדשות מחבורות קיימות ולהראות מספר תכונות נחמדות על חבורות אבליות וציקליות כאפשר מפעילים עליהם מכפלה ישרה.

הגדרה: תהיינה $(H, \circ), (G, *)$ חבורות. נגדיר את המכפלה הישרה להיות $⊙$ והיא תקיים

(g_{1}, h_{1}) ⊙ (g_{2}, h_{2}) = (g_{1} * g_{2}, h_{1} \circ h_{2})

כמו כן יתקיים ש $(G \times H, ⊙)$ היא חבורה הנקראת המכפלה הישרה של $G, H$

איבר היחידה במכפלה הישרה

איבר היחידה בחבורת המכפלה הישרה הוא $(e_{G}, e_{H})$ .

האם $Z_{n} \times Z_{n}$ ציקלית עבור $n \geq 2$ ? נוכיח שלא
מהגדרת המכפלה הישרה וחוג השאריות הסדר של כל איבר $(a, b)$ הוא לכל היותר $n$ :

(a, b)^{n} = (a, b) \dots (a, b) = (a + \dots + a, b + \dots + b) = (n a, n b) = (0, 0)

כעת נניח בשלילה שהחבורה הנ״ל אכן ציקלית. אנחנו יודעים שמספר האיברים בקבוצה המורכבת ממכפלה קרטזית כאשר כל קבוצה היא מגודל $n$ יהיה

| Z_{n} \times Z_{n} | = n \cdot n = n^{2}

כלומר אם החבורה היא ציקלית קיים $(a, b)$ שיוצר את החבורה כך ש

| o (⟨ a, b ⟩) | = n^{2}

בסתירה לכך שהסדר של כל איבר חסום על ידי $n$ .

הבחנה

אם כן הראנו שמכפלה של חבורות ציקליות אינה בהכרח ציקלית, לעומת זאת מכפלה ישרה של חבורות אבליות נשארת אבלית