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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

סריגים שלמים[עריכת קוד מקור | עריכה]

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

סריגים למחצה[עריכת קוד מקור | עריכה]

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

הגדרה אלגברית[עריכת קוד מקור | עריכה]

פעולת המצרף מקיימת שלוש תכונות אלגבריות חשובות: היא אסוציאטיבית (\ (a \vee b) \vee c = a \vee (b \vee c)), קומוטטיבית (\ a \vee b = b \vee a), ואידמפוטנטית (\ a \vee a = a). מאידך, בקבוצה עם פעולה בינארית \ \circ שהיא אסוציאטיבית, קומוטטיבית ואידמפוטנטית, אפשר להגדיר יחס סדר (\ a \leq b אם ורק אם \ a \circ b = a), ואז \ a \circ b הוא המצרף של a ו-b. לכן סריג-למחצה אינו אלא קבוצה עם פעולה אסוציאטיבית, קומוטטיבית ואידמפוטנטית.

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

סריגים מודולריים[עריכת קוד מקור | עריכה]

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Lattices and Ordered Sets, Steven Roman.