הצגת המקור של הדף "חבורה אוליגומורפית"

ב[[מתמטיקה]], ובפרט ב[[תורת החבורות]], '''חבורה אוליגומורפית''' היא [[חבורה (מבנה אלגברי)|חבורה]] ה[[פעולה של חבורה על קבוצה|פועלת]] על מרחב סופי או [[קבוצה בת מנייה|בן-מנייה]] <math>\Omega</math>, כך שמספר המסלולים [[פעולת חבורה|בפעולתה]] הטבעית (לפי רכיב) על <math>\Omega^n</math> הוא סופי לכל <math>n</math> טבעי. חבורות אוליגומורפיות מכלילות חבורות של תמורות בכך שהן מתירות למרחב <math>\Omega</math> שהן פועלות עליו להיות אינסופי, ובכך מאפשרות להכליל תכונות חשובות גם למקרה האינסופי. לחבורות אוליגומורפיות יש יישומים במספר תחומים במתמטיקה, ביניהם [[תורת המודלים]] ו[[קומבינטוריקה]] ספרתית.

==הגדרה==
תהי <math>G</math> חבורת [[תמורה (מתמטיקה)|תמורות]] הפועלת על [[קבוצה סופית]] או בת-מנייה <math>\Omega</math>. <math>G</math> תיקרא '''חבורה אוליגומורפית''' אם לכל <math>n</math> טבעי, ל-<math>G</math> יש מספר סופי של מסלולים בפעולה שלה על <math>\Omega^n</math>, כאשר הפעולה היא לפי רכיבים, כלומר  <math>g(\alpha_{1},...,\alpha_{n})=(g\alpha_{1},...,g\alpha_{n})</math>.

כל חבורות תמורות [[פעולה טרנזיטיבית|טרנזיטיבית]] סופית ניתן לפרק למרכיבים [[פעולה פרימיטיבית|פרימיטיביים]] במספר סופי של צעדים. אי אפשר להכליל זאת באופן ישיר למקרה האינסופי, אבל התנאי שחבורה אוליגומורפית מקיימת מבטיח שאפשר לפרק אותה לרכיבים פרימיטיביים בזמן סופי (כל רכיב בחלוקה של <math>\Omega</math> שנשמר תחת <math>G</math> הוא איחוד של מסלולים, ויש מספר סופי של מסלולים).

==מכפלת זר==
מכפלת זר היא מכפלה חשובה של חבורות תמורות (שאפשר להגדיר לחבורות באופן כללי).

תהי <math>H</math> חבורת תמורות על <math>\Gamma</math>, ו-<math>K</math> חבורת תמורות על <math>\Delta</math>. נגדיר <math>\Omega=\Gamma\times\Delta</math>, נתייחס אליו כאל <math>\Delta</math> סיבים של <math>\Gamma</math>, ונסמן <math>\Gamma_{\delta}=\{(\gamma,\delta):\gamma\in\Gamma\}</math>. לכל <math>\delta\in\Delta</math> ניקח עותק <math>H_{\delta}</math> של <math>H</math> הפועל על <math>\Gamma_{\delta}</math>. כעת המכפלה הקרטזית <math>B=\prod_{\delta\in\Delta}H_{\delta}</math> פועלת על <math>\Omega</math> לפי רכיב, והיא [[תת-חבורה נורמלית]]. <math>K</math> פועלת גם היא על <math>\Omega</math> על ידי הפעלת תמורות על הסיבים <math>\Gamma_{\delta}</math>. נגדיר את '''מכפלת הזר''' <math>G=H \wr K</math> להיות [[מכפלה חצי ישרה|המכפלה החצי-ישרה]] <math>B\rtimes K</math>. <math>B</math> תיקרא ה'''בסיס''' של המכפלה ו-<math>K</math> תיקרא '''ראש''' המכפלה.

אם <math>G</math> חבורה [[פעולה טרנזיטיבית|טרנזיטיבית]] אבל לא [[פעולה פרימיטיבית|פרימיטיבית]] הפועלת על <math>\Omega</math>, יהי <math>\Gamma</math> בלוק של <math>\Omega</math> הנשמר תחת פעולת <math>G</math>, ותהי <math>H</math> חבורת התמורות המושרה מהמייצב שלו. תהי <math>\Delta</math> קבוצת הבלוקים ו-<math>K</math> חבורת התמורות המושרה על <math>\Delta</math> דרך פעולת <math>G</math>. אז <math>G</math> משוכנת באופן טבעי כחבורת תמורות במכפלת הזר <math>H \wr K</math>.

מכפלת זר, יחד עם [[מכפלה ישרה]], מאפשרת לבנות חבורות אוליגומורפיות מיחידות קיימות.

==פונקציות מספר המסלולים==
הסימון <math>\Omega^{n}=(\alpha_{1},...,\alpha_{n})</math> כאשר <math>\alpha_{i}\in\Omega</math> שמופיע בהגדרה, הוא אוסף הסדרות מאורך <math>n</math> עם חזרות ועם חשיבות לסדר. מתברר שדרישת סופיות המסלולים על הסדרות, שקולה לסופיות של מספר המסלולים על [[קומבינטוריקה|חליפות]] מאורך <math>n</math> (בלי חזרות) או [[קומבינטוריקה|צירופים]] מאורך <math>n</math> (בלי חזרות ובלי חשיבות לסדר). הטענה הזו נובעת מכמה חסמים על מספר המסלולים מכל סוג, שאפשר להוכיח בעזרת טיעונים קומבינטוריים פשוטים. מסמנים ב-<math>f_{n}</math>, <math>F_{n}</math> ו-<math>F_{n}^{*}</math> את מספר המסלולים של ׂG על n-צירופים, n-חליפות ו-n-סדרות, מימין לשמאל בהתאמה. לשם נוחות מגדירים <math>f_{0}=F_{0}=F_{0}^{*}=1</math>.

קל לראות כי <math>f_{n}\leq F_{n}\leq n!f_{n}</math>, שהרי כל צירוף בן <math>n</math> איברים ניתן לסדר ב-<math>n!</math> חליפות, הנמצאות בין 1 ל-<math>n!</math> מסלולים שונים. לכן <math>f_{n}</math> סופי אם ורק אם <math>F_{n}</math> סופי. בנוסף מתקיים כי <math> F_{n}^{*}=\sum_{k=1}^{n}S(n,k)F_{k}</math>, כאשר <math>S(n,k)</math> הוא [[מספר סטירלינג]] מסוג שני. לכן <math>F_{n}</math> סופי לכל <math>n</math> אם ורק אם <math>F_{n}^{*}</math> סופי לכל <math>n</math>.

===על-טרנזיטיביות ועל-הומוגניות===
בעזרת פונקציות מספר המסלולים ניתן להכליל בקלות תכונות מוכרות. חבורה אוליגומורפית G תיקרא '''n-הומוגנית''' אם <math>f_{n}=1</math>, ו-'''n-טרנזיטיבית''' אם <math>F_{n}=1</math>. אם G היא n-הומוגנית או n-טרנזיטיבית לכל n טבעי, G תיקרא '''על-הומוגנית''' או '''על-טרנזיטיבית''' בהתאמה. (הגדרות אלו מתיישבות עם הגדרות מוכרות). לפי החסם על מספרי המסלולים, כל חבורה על-טרנזיטיבית היא על-הומוגנית.

לדוגמה, [[החבורה הסימטרית]] <math>S_{\Omega}</math> היא על-טרנזיטיבית (כל תמורה נמצאת בה) ולכן גם על-הומוגנית.

חבורת התמורות ששומרות על הסדר של <math>\mathbb{Q}</math>, המסומנת <math>Aut(\mathbb{Q},<)</math>, היא על-הומוגנית אבל לא על-טרנזיטיבית. יהיו <math>(b_{1},...,b_{n})</math>,<math>(a_{1},...,a_{n})</math> שני n-צירופים, נסדרם כך שיהיו עולים ממש. נוכל לשלוח כל <math>a_{i}</math> ל-<math>b_{i}</math>, וכל קטע <math>(a_{i},a_{i+1})</math> לקטע <math>(b_{i},b_{i+1})</math> על ידי כפל והזזה במספר רציונלי מתאים. נרחיב את התמורה לכל <math>\mathbb{Q}</math> וקיבלנו איבר של החבורה. אז <math>f_{n}=1</math>, זה נכון לכל n ולכן החבורה על-הומוגנית. מצד שני היא לא על-טרנזיטיבית, כי תמורה שומרת סדר לא יכולה להחליף בין שני מספרים שונים, ולכן <math>F_{n}=n!</math>.

עבור חבורה על-טרנזיטיבית, כמסקנה מהחסם הקודם מתקיים <math>F_{n}^{*}=\sum_{k=1}^{n}S(n,k)=B(n)</math>, כאשר <math>B(n)</math> הוא [[מספר בל]].

===תכונות===
פונקציות מספר המסלולים הן [[פונקציה מונוטונית|מונוטוניות]] עולות. לכל חבורה אוליגומורפית, <math>F_{n+1}\geq F_{n}</math>, ומתקיים שוויון אם ורק אם <math>F_{n+1}=1</math>. טענה קצת פחות טריוויאלית היא שמתקיים גם <math>f_{n+1}\geq f_{n}</math>.

אם <math>G\leq H</math>, חבורות אוליגומורפיות, אז <math>f_{n}(G)\geq f_{n}(H)</math>, וכן <math>F_{n}(G)\geq F_{n}(H)</math>, כי מורידים איברים ב-H שמצמצמים את מספר המסלולים. יתרה מכך, <math>f_{n+1}(G)-f_{n}(G)\geq f_{n+1}(H)-f_{n}(H)</math>, כלומר קצב הגידול של מספר המסלולים בתת-חבורה הוא גדול יותר.

ניתן לנסח באלגנטיות טענות על פונקציות מספר המסלולים על ידי שימוש ב[[פונקציה יוצרת|פונקציות יוצרות]].  עבור <math>f_{n}</math> אין חשיבות לסדר, ולכן לכל G ניתן להשתמש בפונקציה היוצרת <math>f_{G}(t)=\sum_{n\geq0}f_{n}(G)t^{n}</math>. עבור <math>F_{n}</math> יש חשיבות לסדר, ולכן אפשר להתבונן בפונקציה היוצרת המעריכית <math>F_{G}(t)=\sum_{n=0}^{\infty}\frac{F_{n}(G)t^{n}}{n!}</math>.

עבור [[מכפלה ישרה]], מתקיים <math>f_{G\times H}(t)=f_{G}(t)*f_{H}(t)</math>, וכן <math>F_{G\times H}(t)=F_{G}(t)*F_{H}(t)</math>.

לדוגמה, אם H על-הומוגנית, אז <math>f_{G\times H}(t)=(\sum_{n\geq0}f_{n}(G)t^{n})*(\sum_{n\geq0}t^{n})</math>, כלומר <math>f_{n}(G\times H)</math> היא סדרת הסכומים החלקיים של <math>f_{n}(G)</math>. בפרט, אם S היא [[החבורה הסימטרית]], ניתן להוכיח (באינדוקציה על k) כי <math>f_{n}(S^{k})=\binom{n+k-1}{k-1}</math>.

עבור מכפלת זר, המצב מורכב יותר. מתקיים כי <math>F_{G \wr H}(t)=F_{H}(F_{G}(t)-1)</math>. בניגוד למכפלה ישרה, את <math>f_{n}(G \wr H)</math> אי אפשר לחשב באופן ישיר מהפונקציות המתאימות של המרכיבים במכפלת זר, אבל ניתן לחשב זאת בכלים קומבינטוריים.

סדרות קומבינטוריות מפורסמות מתבררות להיות פונקציות מספר המסלולים של חבורות אוליגומורפיות. למשל, <math>f_{n}(\mathbb{Z}_{2} \wr Aut(\mathbb{Q},<))</math> הוא [[סדרת פיבונאצ'י|מספר פיבונאצ'י]] ה-n, ו-<math>f_{n}(S \wr S)=\rho(n)</math> כאשר <math>\rho(n)</math> הוא [[פונקציית החלוקה (תורת המספרים)|מספר החלוקות]] של n, ו-S היא החבורה הסימטרית.

==טופולוגיה==
ניתן להגדיר באופן טבעי [[מרחב טופולוגי|טופולוגיה]] על חבורת התמורות הפועלות על <math>\Omega</math> כאשר הוא בן-מנייה. תהי <math>(\alpha_{1},\alpha_{2},...)</math> מנייה של <math>\Omega</math>. נאמר שסדרה של תמורות <math>g_{n}</math> מתכנסת ל-<math>g</math> נקודתית [[אם ורק אם]] לכל k טבעי, עבור כל n [[גדול מספיק]], מתקיים <math>g_{n}(\alpha_{k})=g(\alpha_{k})</math>. כעת ניתן להגדיר על <math>S_{\Omega}</math> את הטופולוגיה של [[התכנסות נקודתית]]. (כלומר [[טופולוגיה מושרית|הטופולוגיה המושרית]] על התמורות של <math>\Omega</math> מ[[טופולוגיית מכפלה|טופולוגיית המכפלה]] של <math>\Omega^\Omega</math>).

בטופולוגיה הזו פעולת הכפל וההיפוך הן [[פונקציה רציפה (טופולוגיה)|רציפות]], ולכן כל חבורה אוליגומורפית G היא [[חבורה טופולוגית]]. G [[קבוצה פתוחה|פתוחה]] ב-<math>S_{\Omega}</math> אם ורק אם היא מכילה את המייצב (הנקודתי) של קבוצה סופית. הקבוצות <math>\{g\in Sym(\Omega):g(\bar{a})=\bar{b}\}</math>, כאשר <math>\bar{a}</math>, <math>\bar{b}</math> הן חליפות מאותו גודל, מהוות [[בסיס (טופולוגיה)|בסיס לטופולוגיה]]. אלו [[קוסט|קוסטים]] של מייצבים (אם החליפות נמצאות באותו מסלול, אחרת זו [[הקבוצה הריקה|קבוצה ריקה]]).

אפשר להגדיר [[מטריקה]] על חבורת התמורות באופן הבא – <math>d(g,h)=\begin{cases}
0 & g=h\\
2^{-i} & g(j)=h(j)\,for\,j<i,\,g(i)\neq h(i)
\end{cases}</math>
המטריקה הזו משרה את הטופולוגיה שהגדרנו, ומשמעותה – שתי תמורות קרובות יותר ככל שהן מסכימות על רישא ארוכה יותר. מרציפות ההיפוך, גם המטריקה <math>d'(g,h)=\max(d(g,h),d(g^{-1},h^{-1}))</math> משרה את אותה טופולוגיה. היתרון שלה הוא שהיא הופכת את <math>S_{\Omega}</math> ל[[מרחב מטרי שלם]].

לכל תת-חבורה של G יש טופולוגיה המושרה מהטופולוגיה של G. העובדה ש-<math>S_{\Omega}</math> הוא מרחב מטרי שלם מאפשרת להשתמש ב[[משפט הקטגוריה של בר]], משפט שימושי להוכחות לא קונסטרוקטיביות בטופולוגיה.

==יישומים בתורת המודלים==
לחבורות אוליגומורפיות יש שימושים רבים ב[[תורת המודלים]]. הודות ל[[משפט לוונהיים-סקולם]] היורד, מותר להניח כי <math>\Omega</math> הוא בן-מנייה מבלי לאבד טענות חזקות.

אם G חבורת תמורות מעל <math>\Omega</math>, אז יש [[מודל (לוגיקה מתמטית)|מבנה]] מעל [[שפה מסדר ראשון|שפה]] יחסית (חסרת קבועים) M כך שמתקיים <math>G\leq Aut(M)</math>, וכן ל-G ול-<math>Aut(M)</math> יש את אותם מסלולים על <math>\Omega^{n}</math>, לכל n.
נוכל לפרק את <math>\bigcup_{n\geq1}\Omega^{n}</math> למסלולים <math>O_{2}...</math>,<math>O_{1}</math>. לכל מסלול <math>O_{i}</math> נגדיר יחס <math>R_{i}</math> עם n משתנים אם <math>O_{i}\subseteq\Omega^{n}</math>. כעת נפרש את <math>R_{i}</math> מעל המודל (איחוד המסלולים) להיות <math>O_{i}</math>. לכן <math>G\leq Aut(M)</math>. כעת, כל <math>n</math>-יה המספקת את <math>R_{i}</math> עושה זאת לערך יחיד של <math>i</math>, לכן אם <math>\bar{a}</math> ו-<math>\bar{b}</math> נמצאים באותו מסלול תחת <math>Aut(M)</math>, הם מספקים את אותו <math>R_{i}</math> ולכן נמצאים באותו מסלול ב-G.
מבנה זה נקרא '''המבנה היחסי הקנוני''' של G.

המודל היחסי הקנוני של חבורה אוליגומורפית שופך אור נוסף על הטופולוגיה שלה. תת-חבורה G של <math>S_{\Omega}</math> היא [[קבוצה סגורה|סגורה]] אם ורק אם <math>G=Aut(M)</math> עבור מבנה M על <math>\Omega</math>. לא כל שכן, ה[[סגור (טופולוגיה)|סגור]] של חבורת תמורות G בטופולוגיה של <math>S_{\Omega}</math>, הוא [[חבורת אוטומורפיזמים|חבורת האוטומורפיזמים]] של המבנה הקנוני שלה.

פיתוח הכלים של חבורות אוליגומורפיות בתורת המודלים ובטופלוגיה מובילים לתוצאות חזקות. אפיון אחד חשוב הוא גרסה של משפט Ryll-Nardzewski - מבנה בן-מנייה M הוא <math>\aleph_{0}</math>-קטגורי (כלומר מבנה מעל [[תורה (לוגיקה מתמטית)|תורה]] <math>\aleph_{0}</math>-קטגורית) אם ורק אם <math>Aut(M)</math> היא חבורה אוליגומורפית.

==לקריאה נוספת==
* Peter J. Camerom, “Oligomorphic Permutation Groups”, London Math. Soc. Lecture Note Series 152
* [https://www.researchgate.net/publication/242492935_Oligomorphic_Permutation_Groups "Peter J. Camerom (1990), “Oligomorphic Permutation Groups]

[[קטגוריה:תורת החבורות]]
[[קטגוריה:חבורות טופולוגיות]]