סריג חופשי

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

הסריג המודולרי החופשי על ארבע נקודות a,b,c,d הכפופות ליחסים a<b, c<d

לדוגמה, הסריג החופשי הנוצר על ידי זוג נקודות a,b כולל רק ארבע נקודות: $\ a,b,a\wedge b,a\vee b$. הסריג החופשי הנוצר על ידי שלוש נקודות הוא אינסופי, ולכן הסריג החופשי הנוצר על ידי יחס סדר שיש בו שלוש נקודות שאינן ניתנות להשוואה, הוא תמיד אינסופי. לעומת זאת הסריג המודולרי החופשי הנוצר על ידי שלוש נקודות כולל 28 נקודות (וגובהו 8), כפי שחישב ריכארד דדקינד ב-1900. הסריג הדיסטריבוטיבי החופשי הנוצר על ידי שלוש נקודות כולל 18 נקודות. הסריג המודולרי החופשי על ארבע נקודות הוא אינסופי (Birkhoff, 1933), בעוד שסריג דיסטריבוטיבי חופשי הנוצר סופית הוא תמיד סופי (לסריג הדיסטריבוטיבי החופשי על 4 נקודות יש 166 נקודות, וגודלו של הסריג הדיסטריבוטיבי החופשי על n נקודות הוא בקירוב $\ 2^{\binom {n}{[n/2]}}$). בעיית המילה פתירה בסריג החופשי, אבל לא בסריג המודולרי החופשי על חמש נקודות (או יותר).

את הסריג החופשי אפשר לחשב גם כאשר היוצרים מתייחסים זה לזה. למשל, הסריג החופשי על הקבוצה a,b,c שבה a<b כולל 9 נקודות (הסריג המודולרי החופשי על קבוצה זו כולל 8 נקודות, והוא דיסטריבוטיבי). הסריג החופשי על הקבוצה a,b,c,d שבה a<b<c כולל 20 נקודות (בסריג המודולרי החופשי על קבוצה זו יש 13 נקודות). הסריג החופשי על הקבוצה a,b,c,d שבה a<b ו-c<d הוא אינסופי, בעוד שהסריג המודולרי החופשי על קבוצה זו כולל 18 נקודות (תוספת היחס a<d יוצרת מנה שבה רק 12 נקודות).

לקריאה נוספת

• Lattice Theory: first concepts and distributive lattices, George Gratzer, Section 5.