סריג (מבנה סדור)

בתורת הקבוצות, סריג הוא קבוצה עם יחס סדר חלקי, שבו לכל שני איברים $a,b$ יש אינפימום וסופרמום. פירושו של דבר שיש איבר גדול ביותר מבין כל אלה המקיימים $x\leq a,b$ , ואיבר קטן ביותר מבין כל אלה המקיימים $a,b\leq x$ .

בצורה זו מתקבלות שתי פעולות בינאריות על איברי הקבוצה הסדורה:

• פעולת המצרף (join) המחזירה לכל זוג איברים את הסופרמום של שניהם. פעולה זו מסומנת $a\lor b$ .
• פעולת המפגש (meet) המחזירה לכל זוג איברים את האינפימום של שניהם. פעולה זו מסומנת $a\land b$ .

אחת הדוגמאות הבסיסיות לסריג הוא אוסף תתי־הקבוצות של קבוצה $X$ , עם פעולות האיחוד והחיתוך כמצרף ומפגש. גם אוסף תת-הקבוצות הסופיות הוא סריג. כל יחס סדר מלא הוא סריג כי בו המצרף של שני איברים הוא הגדול מביניהם, והמפגש של שני איברים הוא הקטן מביניהם.

סריגים שלמים

בסריג אפשר להגדיר מצרף ומפגש של כל קבוצה סופית. אם לכל קבוצה יש אינפימום וסופרמום הסריג נקרא שלם. כל סריג שלם הוא חסום: יש בו איבר קטן ביותר (הסופרמום של הקבוצה הריקה), ואיבר גדול ביותר (האינפימום שלה). סריג תתי־הקבוצות של $X$ הוא סריג שלם; לא כל אלגברה בוליאנית היא שלמה. הסריג שמגדיר יחס סדר מלא הוא שלם, אם ורק אם הסדר וההפכי לו שניהם יחסי סדר טובים.

סריגים־למחצה

אם לכל שני איברים קיים מצרף, אבל לא בהכרח מפגש, הקבוצה מכונה סריג-למחצה עליון, ובאופן דומה- אם לכל זוג איברים קיים מפגש, אבל לא בהכרח מצרף, הקבוצה מכונה סריג־למחצה תחתון. היפוך של יחס הסדר מחליף בין שני טיפוסי הסריגים־למחצה.

הגדרה אלגברית

פעולת המצרף מקיימת שלוש תכונות אלגבריות חשובות:

1. אסוציאטיביות $(a\lor b)\lor c=a\lor (b\lor c)$
2. קומוטטיביות $a\lor b=b\lor a$
3. אידמפוטנטיות $a\lor a=a$

מאידך, בכל קבוצה עם פעולה בינארית $\bullet$ המקיימת את שלוש התכונות האלה, אפשר להגדיר יחס סדר ($a\leq b$ אם ורק אם $a\bullet b=a$), שביחס אליו $a\bullet b$ הוא המצרף של $a,b$ . לכן יש התאמה מלאה בין סריגים־למחצה לבין קבוצות עם פעולה אסוציאטיבית, קומוטטיבית ואידמפוטנטית. למשל, פעולת החיתוך של קבוצות $A\bullet B=A\cap B$ היא אסוציאטיבית, קומוטטיבית ואידמפוטנטית; ויחס הסדר שהיא מגדירה, $A\leq B$ אם ורק אם $A\cap B=A$ , אינו אלא יחס ההכלה הרגיל.

באופן דומה לזה, יש התאמה מלאה בין סריגים לבין אלגברות בוליאניות.

סריגים מודולריים

בכל סריג, אם $a\leq b$ , אז לכל $c$ מתקיים $a\lor (c\land b)\leq (a\lor c)\land b$ . אם זהו תמיד שוויון, הסריג נקרא מודולרי. המודולריות משותפת לסריגים חשובים רבים, כגון סריג תתי־החבורות הנורמליות של חבורה, או סריג תתי־המודולים של מודול.

אומרים כי איבר $a$ בקבוצה סדורה מכסה את האיבר $b$ , אם $b<a$ ולא קיים $b<x<a$ . אם המצרף עם $x$ שומר על היחס "מכסה או שווה" (ובאופן שקול: אם $a\lor b$ מכסה את $b$ כל אימת ש־$a$ מכסה את $a\land b$), אז הסריג נקרא מודולרי־למחצה עליון. אם המפגש עם $x$ שומר על היחס "מכסה או שווה", אז הסריג הוא מודולרי־למחצה תחתון. כל סריג מודולרי הוא גם מודולרי למחצה עליון ותחתון. ולהפך: אם אין בסריג שרשראות אינסופיות, והוא מודולרי־למחצה עליון ותחתון, אז הוא מודולרי.

כאשר אין בסריג שרשראות אינסופיות, מן המודולריות למחצה (מאחד הטיפוסים) נובע שכל השרשראות המקסימליות מ־$a$ ל־$b$ הן באותו אורך. אם $a\leq b$ , אפשר להגדיר את המרחק $d(a,b)$ כארכה של השרשרת הקצרה ביותר מ־$a$ ל־$b$ . סריג הוא מודולרי־למחצה עליון, אם ורק אם $d(a\land b,a)\geq d(b,a\lor b)$ לכל $a,b$ ; ומודולרי אם ורק אם $d(a\land b,a)=d(b,a\lor b)$ לכל $a,b$ .

ראו גם

• סריג חופשי

לקריאה נוספת

• Steven Roman, 2008. Lattices and Ordered Sets.

קישורים חיצוניים

מדיה וקבצים בנושא סריג בוויקישיתוף