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

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

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

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

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

הגדרות

הגדרה באמצעות סדר חלקי

תהי קבוצה סדורה $(L,\leq )$. אזי $L$ תקרא סריג אם לכל זוג איברים $a,b\in L$ יש אינפימום וסופרמום. כלומר:

1. קיים $s\in L$ כך ש-$a\leq s$ וגם $b\leq s$ ולכל $t\in L$ כך ש-$a\leq t$ וגם $b\leq t$ מתקיים בהכרח ש-$s\leq t$.
2. קיים $i\in L$ כך ש-$i\leq a$ וגם $i\leq b$ ולכל $j\in L$ כך ש-$j\leq a$ וגם $j\leq b$ מתקיים בהכרח ש-$j\leq i$.

הגדרה באמצעות פעולות אלגבריות

תהי קבוצה $L$ ועליה שתי פעולות בינאריות $\wedge \colon L\times L\to L$ ו-$\vee \colon L\times L\to L$. אזי $(L,\wedge ,\vee )$ תקרא סריג אם ורק אם מתקיימים התנאים הבאים:

1. אסוציאטיביות: לכל $a,b,c\in L$ מתקיים ש-$(a\wedge b)\wedge c=a\wedge (b\wedge c)$ ו-$(a\vee b)\vee c=a\vee (b\vee c)$.
2. קומוטטיביות: לכל $a,b\in L$ מתקיים ש-$a\wedge b=b\wedge a$ ו-$a\vee b=b\vee a$.
3. אידמפוטנטיות: לכל $a\in L$ מתקיים ש-$a\wedge a=a$ ו-$a\vee a=a$.
4. בליעה: לכל $a,b\in L$ מתקיים ש-$(a\wedge b)\vee a=a$ ו-$(a\vee b)\wedge a=a$.

הפעולה $\wedge$ קרויה מפגש (meet) ו-$\vee$ קרויה מצרף (join). ניתן לראות כי הפעולות $\wedge$ ו-$\vee$ דואליות זו לזו (כלומר, אפשר להחליף את הסימנים ביניהן והתכונות לעיל תשארנה אותו הדבר).

שקילות ההגדרות

שתי ההגדרות לעיל לסריג שקולות זו לזו, וניתן להגדיר את האחת מן האחרת.

אם $(L,\leq )$ סריג לפי ההגדרה הראשונה, לכל $a,b\in L$ אפשר להגדיר $a\wedge b:=\inf\{a,b\}$ ו-$a\vee b:=\sup\{a,b\}$. שתי פעולות אלו מוגדרות היטב לפי ההגדרה באמצעות סדר חלקי לסריג, וכן הן מקיימות את ארבע האקסיומות בהגדרה האלגברית.

מצד שני, אם $(L,\wedge ,\vee )$ הוא סריג לפי ההגדרה האלגברית, לכל $a,b\in L$, התנאים הבאים שקולים:

1. $a\wedge b=a$
2. $a\vee b=b$

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

כאשר רוצים להתייחס לסריג באופן שמכבד את שתי ההגדרות, אפשר לסמנו ב-$(L,\wedge ,\vee ,\leq )$.

דוגמאות

• 
  תרשים 1: סריג של תת-הקבוצות של $\{x,y,z\}$ עם יחס הכלה (תורת הקבוצות). השם "סריג" נובע מצורת דיאגרמת הסה המתארת מבנה זה.
• 
  תרשים 2: סריג המחלקים של 60 עם יחס מחלק.
• 
  תרשים 3: סריג החלוקות של $\{1,2,3,4\}$ עם יחס "עידון חלוקה".
• 
  תרשים 4: סריג מספרים טבעיים עם יחס $\,\leq$. כל קבוצה הסדורה בסדר מלא היא סריג.
• 
  תרשים 5: סריג זוגות של מספרים שלמים, מסודרים בגודל לפי רכיבים.

• בדוגמה 1, לכל שתי תת-קבוצות $A,B\subset U$ יש אינפימום $A\wedge B=A\cap B$ וסופרמום $A\vee B=A\cup B$.
• בדוגמה 2, לכל שני מספרים יש אינפימום והוא המחלק המשותף הגדול ביותר (gcd) וסופרמום שהוא הכפולה המשותפת הקטנה ביותר (lcm).
• בדוגמה 4, לכל $a,b\in \mathbb {Z}$ האינפימום הוא $A\wedge B=\inf\{a,b\}=\min\{a,b\}$ והסופרמום הוא $A\vee B=\sup\{a,b\}=\max\{a,b\}$.
• בדוגמה 5, יחס הסדר הוא $(x_{1},y_{1})\leq (x_{2},y_{2})\iff x_{1}\leq x_{2},y_{1}\leq y_{2}$ ואז האינפימום הוא $(x_{\inf },y_{\inf })=\left(\min\{x_{1},x_{2}\},\min\{y_{1},y_{2}\}\right)$ וסופרמום $(x_{\sup },y_{\sup })=\left(\max\{x_{1},x_{2}\},\max\{y_{1},y_{2}\}\right)$.

תכונות

יהי סריג $(L,\wedge ,\vee ,\leq )$ ו-$a,b,c\in L$. אזי:

• $a\leq b\wedge c$ אם ורק אם $a\leq b$ וגם $a\leq c$.
• $a\vee b\leq c$ אם ורק אם $a\leq c$ וגם $b\leq c$.
• $a=b$ אם ורק אם $a\vee b=a\wedge b$.
• $(a\wedge c)\vee (a\wedge b)\leq a\wedge (b\vee c)\ \leq a\leq \ a\vee (b\wedge c)\leq (a\vee c)\wedge (a\vee b)$ (ראו סריג דיסטריבוטיבי למטה).
• אם $a\leq b$ אז:
  • $a\wedge c\leq b\wedge c$
  • $a\vee c\leq b\vee c$.
  • $a\vee (c\wedge b)\leq (a\vee c)\wedge b$ (ראו סריג מודולרי למטה).

אם $A\subseteq L$ היא קבוצה סופית אז יש לה אינפימום וסופרמום ומסמנים אותם ב-$\bigwedge A$ ו-$\bigvee A$ בהתאמה.

בנוסף לכך, אם $A\subseteq B\subseteq L$ כך ש-$A,B$ הן קבוצות סופיות, בהכרח $\bigwedge B\leq \bigwedge A\leq \bigvee A\leq \bigvee B$.

איברים מיוחדים בסריג

יהי סריג $(L,\wedge ,\vee ,\leq )$ ואיבר כלשהו $a\in L$. אזי:

• $a$ ייקרא אי-פריק למצרף אם ורק אם לכל $b,c\in L$ המקיימים $a=b\vee c$ מתקיים בהכרח ש-$a=b$ או $a=c$.
• $a$ ייקרא ראשוני למצרף אם ורק אם לכל $b,c\in L$ המקיימים $a\leq b\vee c$ מתקיים בהכרח ש-$a\leq b$ או $a\leq c$.
• $a$ ייקרא אי-פריק למפגש אם ורק אם לכל $b,c\in L$ המקיימים $a=b\wedge c$ מתקיים בהכרח ש-$a=b$ או $a=c$.
• $a$ ייקרא ראשוני למפגש אם ורק אם לכל $b,c\in L$ המקיימים $b\wedge c\leq a$ מתקיים בהכרח ש-$b\leq a$ או $c\leq a$.

ניתן להוכיח שכל איבר שהוא ראשוני למצרף הוא בהכרח אי-פריק למצרף. באופן זהה, כל איבר שהוא ראשוני למפגש הוא אי-פריק למפגש.

תת-סריג

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

יהי סריג $(L,\wedge ,\vee ,\leq )$ ותהי תת-קבוצה $M\subseteq L$. $M$ תקרא תת-סריג של $L$ אם ורק אם היא סגורה למפגש ומצרף. כלומר, לכל $a,b\in M$ מתקיים ש-$a\wedge b\in M$ ו-$a\vee b\in M$.

כל תת-קבוצה של קבוצה סדורה היא סדורה בעצמה לפי הסדר המושרה. עם זאת, לא כל תת-קבוצה של סריג היא תת-סריג, גם אם הסדר המושרה עליה הוא סדר של סריג (ראו תרשים לדוגמה).

הומומורפיזמים

יהי זוג סריגים $(L,\wedge _{L},\vee _{L})$ ו-$(M,\wedge _{M},\vee _{M})$. פונקציה $\varphi \colon L\to M$ תקרא הומומורפיזם של סריגים אם ורק אם לכל $a,b\in L$ מתקיים ש-$\varphi (a\wedge _{L}b)=\varphi (a)\wedge _{M}\varphi (b)$ ו-$\varphi (a\vee _{L}b)=\varphi (a)\vee _{M}\varphi (b)$. כל הומומורפיזם של סריגים הוא בהכרח שיכון סדר לפי הסדרים הרלוונטיים בין שני הסדרים.

הפונקציה $\varphi \colon L\to M$ תקרא איזומורפיזם של סריגים אם ורק אם היא הומומורפיזם של סריגים שהוא גם פונקציה חד-חד ערכית ועל. ניתן להוכיח שאם $L$ היא סריג ו-$\varphi$ היא איזומורפיזם סדר, אז גם $M$ סריג ולכן $\varphi$ היא איזומורפיזם של סריגים.

סוגי סריגים

סריג חסום

ערך מורחב – סריג חסום

בהינתן סריג $(L,\wedge ,\vee ,\leq )$, סריג זה יקרא סריג חסום אם ורק אם קיימים לו איבר גדול ביותר ואיבר קטן ביותר. לעיתים מסמנים את האיבר הגדול ביותר בסריג ב-$1$ ואת האיבר הקטן ביותר ב-$0$.

כל סריג באשר הוא ניתן לחסום על-ידי הוספת איבר גדול ביותר או קטן ביותר. בפרט, אם מגדירים $L':=\{\downarrow \!x\mid x\in L\}\cup \{\emptyset ,L\}$ כאשר $\downarrow \!x$ הוא הסגור מטה של $x$, ניתן להוכיח כי $L'$ היא סריג חסום לפי היחס $\subseteq$ וכי $L$ משוכנת בה.

הסריג $L$ יקרא סריג עם השלמה אם ורק אם הוא חסום ולכל $x\in L$ קיים $y\in L$ כך ש-$x\wedge y=0$ ו-$x\vee y=1$.

בכל סריג חסום, $0$ הוא אי-פריק למצרף ו-$1$ הוא אי-פריק למפגש.

סריג שלם

ערך מורחב – סריג שלם

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

השלמת דדקינד-מקניל (Dedekind–MacNeille completion) מאפשרת למצוא שיכון סדר מכל קבוצה סדורה חלקית (גם כזו שאינה סריג) לסריג שלם.

קבוצה הסדורה בסדר מלא היא סריג שלם אם ורק אם היא סדורה היטב וגם הסדר הדואלי לה סדור היטב. כל סריג סופי הוא סריג שלם.

סריג מודולרי

התכונות הבאות שקולות עבור סריג L:

• אם $a\leq b$, אז לכל $c$ מתקיים $a\vee (c\wedge b)=(a\vee c)\wedge b$;
• אם $a\leq b$, ומתקיים $a\vee c=b\vee c$ וגם $a\wedge c=b\wedge c$, אז $a=b$.

סריג המקיים תכונות אלה נקרא סריג מודולרי. (כאמור לעיל, בתכונה הראשונה אי-השוויון $\leq$ מתקיים תמיד). המודולריות משותפת לסריגים חשובים רבים, כגון סריג תת-החבורות הנורמליות של חבורה, או סריג תת-המודולים של מודול.

בסריג מודולרי, לכל a,b, הפונקציות $x\mapsto x\wedge a$ ו-$y\mapsto y\vee b$ הן איזומורפיזמים הפוכים זה לזה של הקטעים $[a\wedge b,a]$ ו-$[b,a\vee 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. אם לסריג יש איבר מינימלי 0 והמרחק מ-0 תמיד סופי, אז פונקציית הגובה $h(x)=d(0,x)$ מקיימת $h(a\vee b)+h(a\wedge b)=h(a)+h(b)$ אם ורק אם הסריג מודולרי.

סריג דיסטריבוטיבי

סריג $(L,\wedge ,\vee )$ הוא סריג דיסטריבוטיבי (פילוגי) אם ורק אם הוא מקיים את אחד התנאים השקולים הבאים:

• לכל $a,b,c\in L$ מתקיים ש-$a\vee (b\wedge c)=(a\vee c)\wedge (a\vee b)$.
• לכל $a,b,c\in L$ מתקיים ש-$a\wedge (b\vee c)=(a\wedge c)\vee (a\wedge b)$.

כלומר, פעולת המצרף ופעולת המפגש מקיימות את חוק הפילוג זו ביחס לזו.

לפי משפט ההצגה של בירקהוף (Birkhoff's representation theorem) כל סריג דיסטריבוטיבי סופי $L$ איזומורפי לסריג ${\mathcal {J}}(P)$, כאשר $P$ הוא אוסף כל האיברים האי-פריקים למצרף ב-$L$ (האיברים שמכסים את המינימום הם אי-פריקים), ו-${\mathcal {J}}(P)$ הוא אוסף כל הקבוצות התחתונות ב-$P$ לפי הסדר המושרה עליהן, ביחס להכלה. בפרט, כל סריג דיסטריבוטיבי סופי הוא סריג של קבוצות.

אלגברה בוליאנית

ערך מורחב – אלגברה בוליאנית (מבנה אלגברי)

בהינתן סריג $(L,\wedge ,\vee )$, הסריג ייקרא אלגברה בוליאנית אם ורק אם הוא סריג דיסטריבוטיבי חסום עם השלמה. במקרה זה המשלים של כל איבר הוא יחיד, וניתן להגדיר פעולה אונארית $\neg \colon L\to L$ כך שלכל $a\in L$ מתקיים ש-$\neg a\wedge a=0$,‏ $\neg a\vee a=1$ ו-$\neg (\neg a)=a$. בנוסף, לכל $a,b\in L$ מתקיימים כללי דה-מורגן: $\neg (a\wedge b)=(\neg a)\vee (\neg b)$ ו-$\neg (a\vee b)=(\neg a)\wedge (\neg b)$.

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

סריג למחצה

ערך מורחב – סריג-למחצה

בהינתן קבוצה סדורה $(P,\leq )$, $P$ תקרא סריג-למחצה עליון אם ורק אם לכל זוג איברים קיים סופרמום. $P$ תקרא סריג-למחצה תחתון אם ורק אם לכל זוג איברים קיים סופרמום. ניתן לראות כי $P$ היא סריג אם ורק אם היא גם סריג-למחצה עליון וגם סריג-למחצה תחתון.

לסריגים-למחצה, בדומה לסריגים, קיימת הגדרה אלגברית שקולה:

בהינתן קבוצה $P$ ופעולה בינארית $\bullet \colon P\times P\to P$, $P$ תקרא סריג-למחצה אם ורק אם הפעולה $\bullet$ מקיימת את התנאים הבאים:

1. אסוציאטיביות: לכל $a,b,c\in L$ מתקיים ש-$(a\bullet b)\bullet c=a\bullet (b\bullet c)$
2. קומוטטיביות: לכל $a,b\in L$ מתקיים ש-$a\bullet b=b\bullet a$.
3. אידמפוטנטיות: לכל $a\in L$ מתקיים ש-$a\bullet a=a$.

גם כאן, אפשר לבנות את שתי ההגדרות אחת מן השנייה:

• בהינתן הסדר החלקי של הסריג-למחצה, ניתן לבנות ממנו את הפעולה האלגברית על-ידי $a\bullet b:=\sup\{a,b\}$.
• מצד שני, בהינתן הסריג-למחצה האלגברי, ניתן להגדיר ממנו את יחס הסדר החלקי כך שלכל $a,b\in P$ מתקיים ש-$a\leq b$ אם ורק אם $a\bullet b=b$.

יש לשים לב שבהגדרה האלגברית של סריג-למחצה אין הבדל בין סריג-למחצה עליון לסריג-למחצה תחתון.

מכפלה ישרה של סריגים

בהינתן זוג סריגים $(L,\wedge _{L},\vee _{L})$ ו-$(M,\wedge _{M},\vee _{M})$ ניתן להגדיר את המכפלה הישרה שלהם $(L\times M,\wedge ,\vee )$ כך שלכל $(l_{1},m_{1}),(l_{2},m_{2})\in L\times M$:

$(l_{1},m_{1})\wedge (l_{2},m_{2}):=(l_{1}\wedge _{L}l_{2},m_{1}\wedge _{M}m_{2}),\qquad (l_{1},m_{1})\vee (l_{2},m_{2}):=(l_{1}\vee l_{2},m_{1}\vee _{M}m_{2})$

מכפלה ישרה של סריגים היא אסוציאטיבית: בהינתן שלושה סריגים $L$,‏ $M$ ו-$N$, הסריג $L\times (M\times N)$ איזומורפי ל-$(L\times M)\times N$.

ניתן להוכיח כי $(L\times M,\wedge ,\vee )$ הוא אכן סריג, ושהתכונות הבאות נשמרות:

• $L\times M$ חסום אם ורק אם $L$ ו-$M$ חסומות.
• $L\times M$ עם השלמה אם ורק אם $L$ ו-$M$ עם השלמה.
• $L\times M$ מודולרי אם ורק אם $L$ ו-$M$ מודולריים.
• $L\times M$ פילוגי אם ורק אם $L$ ו-$M$ פילוגיים.

ראו גם

• סריג חופשי
• דיאגרמת הסה

לקריאה נוספת

• Steven Roman, Lattices and Ordered Sets, New York: Springer New York, 2008
• Garrett Birkhoff, Lattice Theory, Rhode Island: American Mathematical Society, 1940

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

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

• סריג, באתר MathWorld (באנגלית)
• תיאוריית הסריג, דף שער בספרייה הלאומית