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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Steven Roman, 2008. Lattices and Ordered Sets.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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