מילה (תורת החבורות)

בתורת החבורות מילה היא רצף של אותיות מתוך אלף-בית נתון, או האותיות ההפוכות להן. למשל, אם האלף-בית כולל את x, y ו-z, אז $xyyx^{-1}zzzx^{-1}$ היא מילה. הצבה של איברים בחבורה G במקום אותיות האלף-בית מגדירה הצבה בכל מילה. מילים ממלאות תפקיד חשוב בתורת ההצגות ובתורת החבורות החופשיות, והן מושאי לימוד מרכזיים בתורת החבורות הקומבינטורית.

הגדרות

תהא G חבורה, ו- S תת-קבוצה של G. מילה ב- S היא כל ביטוי מהצורה

$s_{1}^{\varepsilon _{1}}s_{2}^{\varepsilon _{2}}\cdots s_{n}^{\varepsilon _{n}}$

כאשר s₁,...,s_n איברים ב-S, הנקראים יוצרים, וכל ε_i הוא ±1. המספר n ידוע כאורך המילה.

כל מילה ב- S מייצגת איבר ב-G, כלומר את מכפלת הביטוי. על פי מוסכמה, איבר היחידה יכול להיות מיוצג על ידי המילה הריקה, שהיא המילה הייחודית באורך אפס.

מוסכמות כתיבה

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

$xxy^{-1}zyzzzx^{-1}x^{-1}\,$

יכולה להיכתב בתור

$x^{2}y^{-1}zyz^{3}x^{-2}.\,$

הביטוי הנ"ל אינו מילה בפני עצמו — הוא פשוט סימון קצר יותר למילה המקורית.

כאשר עוסקים במילים ארוכות, זה יכול להיות מועיל להשתמש בקו-עליון כדי לציין איברים הופכיים ב-S . באמצעות סימון קו-על, המילה לעיל תיכתב באופן הבא:

$x^{2}{\overline {y}}zyz^{3}{\overline {x}}^{2}.\,$

מילים מצומצמות

ניתן לפשט כל מילה שבה יוצר מופיע לצד ההופכי שלו (xx⁻¹ או x ⁻¹x) על ידי השמטת זוג התווים המיותר:

$y^{-1}zxx^{-1}y\;\;\longrightarrow \;\;y^{-1}zy.$

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

מילה מצומצמת היא מילה שלא מכילה זוגות של איברים אשר ניתן לצמצם. ניתן לפשט כל מילה למילה מצומצמת על ידי ביצוע רצף של צמצומים:

$xzy^{-1}xx^{-1}yz^{-1}zz^{-1}yz\;\;\longrightarrow \;\;xyz.$

התוצאה אינה תלויה בסדר בו מבוצעים הצמצומים.

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

פעולות על מילים

המכפלה של שתי מילים מתקבלת על ידי שרשור:

$\left(xzyz^{-1}\right)\left(zy^{-1}x^{-1}y\right)=xzyz^{-1}zy^{-1}x^{-1}y.$

גם אם שתי המילים מצומצמות, ייתכן שהמכפלה לא מצומצמת.

המילה ההופכית של מילה מסוימת מתקבלת על ידי לקיחת האיבר ההופכי של כל יוצר, והיפוך סדר ההופעה שלהם:

$\left(zy^{-1}x^{-1}y\right)^{-1}=y^{-1}xyz^{-1}.$

ניתן לצמצם את המכפלה של מילה עם המילה ההופכית שלה למילה הריקה:

$zy^{-1}x^{-1}y\;y^{-1}xyz^{-1}=1.$

ניתן להעביר יוצר מההתחלה לסוף של מילה על ידי הצמדה :

$x^{-1}\left(xy^{-1}z^{-1}yz\right)x=y^{-1}z^{-1}yzx.$

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

תת-קבוצה S של קבוצה G נקראת קבוצה יוצרת אם כל איבר ב-G ניתן ליצוג על ידי מילה ב-S.

כאשר S אינה קבוצה יוצרת של G, קבוצת האיברים המיוצגת על ידי מילים ב-S היא תת-חבורה של G, המכונה תת-החבורה של G הנוצרת על ידי S ומסומנת בדרך כלל $\langle S\rangle$. זוהי תת-החבורה הקטנה ביותר של G המכילה את האלמנטים של S.

תבניות נורמליות

תבנית נורמלית עבור קבוצה G עם הנוצרת על ידי S היא בחירה של מילה מצומצמת אחת ב-S עבור כל איבר ב-G. לְדוּגמָה:

• המילים 1, i, j, ij הן תבנית נורמלית לחבורת הארבעה של קליין עם {S = {i,  j ו-1 מיוצג על ידי המילה הריקה (איבר היחידה של החבורה).
• המילים 1, r, r ², ..., r ^n-1, s, sr, ..., sr ^n-1 הם תבנית נורמלית לחבורה הדיהדרלית Dih_n עם {S = {s,  r ו-1 שוב מיוצג על ידי המילה הריקה.
• קבוצת המילים מהצורה x^myⁿ עבור m,n∈Z הם תבנית נורמלית למכפלה הישירה של החבורות הציקליות ⟨x⟩ ו-⟨y⟩ עם {S = {x,  y.
• קבוצת המילים המצומצמות ב-S הן התבנית הנורמלית הייחודית לחבורה החופשית על S.

יחסים והצגות

תהא S קבוצה יוצרת עבור חבורה G, יחס הוא זוג מילים ב-S המייצגות את אותו אלמנט ב-G. יחסים נכתבים בדרך כלל כמשוואות, למשל $x^{-1}yx=y^{2}.\,$. קבוצה ${\mathcal {R}}$ של יחסים מגדירים את G אם כל יחס ב- G נובע לוגית מהיחסים ב-${\mathcal {R}}$ ומתוך אקסיומות החבורה. הצגה של G היא זוג $\langle S\mid {\mathcal {R}}\rangle$, עבור S קבוצה יוצרת של G ו-${\mathcal {R}}$ היא קבוצה מגדירה של יחסים.

לדוגמה, ניתן להגדיר את חבורת הארבעה של קליין על ידי ההצגה

$\langle i,j\mid i^{2}=1,\,j^{2}=1,\,ij=ji\rangle .$

כאשר 1 מציין את המילה הריקה, המייצגת את איבר היחידה.

חבורות חופשיות

תהא S קבוצה כלשהי, הקבוצה החופשית על S היא הקבוצה המיוצגת על ידי $\langle S\mid \;\rangle$. כלומר, הקבוצה החופשית על S היא הקבוצה הנוצרת על ידי האלמנטים של S, ללא יחסים נוספים. כל איבר בחבורה החופשית יכול להיכתב באופן ייחודי כמילה מצומצמת ב-S.

ראו גם

• בעיה מילולית (מתמטיקה)
• בעיית המילה בחבורות

לקריאה נוספת

• Epstein, David; Cannon, J. W.; Holt, D. F.; Levy, S. V. F.; Paterson, M. S.; Thurston, W. P. (1992). Word Processing in Groups. AK Peters. ISBN 0-86720-244-0..
• Novikov, P. S. (1955). "On the algorithmic unsolvability of the word problem in group theory". Trudy Mat. Inst. Steklov (ברוסית). 44: 1–143.
• Robinson, Derek John Scott (1996). A course in the theory of groups. Berlin: Springer-Verlag. ISBN 0-387-94461-3.
• Rotman, Joseph J. (1995). An introduction to the theory of groups. Berlin: Springer-Verlag. ISBN 0-387-94285-8.
• Schupp, Paul E; Lyndon, Roger C. (2001). Combinatorial group theory. Berlin: Springer. ISBN 3-540-41158-5.
• Solitar, Donald; Magnus, Wilhelm; Karrass, Abraham (2004). Combinatorial group theory: presentations of groups in terms of generators and relations. New York: Dover. ISBN 0-486-43830-9.
• Stillwell, John (1993). Classical topology and combinatorial group theory. Berlin: Springer-Verlag. ISBN 0-387-97970-0.