סריג-למחצה

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

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

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

סימונים

בערך זה נסמן ב-<math>\R</math> את קבוצת המספרים הממשיים וב-<math>\R^n</math> את המרחב הווקטורי הממשי ה-<math>n</math> ממדי (<math>n</math> מספר טבעי).

בהינתן קבוצה סדורה חלקית כלשהי <math>E</math>, הסימונים <math>\min(E)</math> ו-<math>\max(E)</math> מסמנים את האיבר הקטן ביותר והאיבר הגדול ביותר בקבוצה (אם קיימים). בנוסף, הסימונים <math>\inf(E)</math> ו-<math>\sup(E)</math> מסמנים את האינפימום והסופרמום של הקבוצה (אם קיימים). לבסוף, לכל זוג איברים <math>a,b\in E</math> מסמנים <math>\min(a,b):=\min(\{a,b\})</math>,‏ <math>\max(a,b):=\max(\{a,b\})</math> וכן הלאה.

הגדרות

הגדרה לפי יחס סדר

תהי קבוצה סדורה חלקית <math>(A,\le)</math>. אזי:

• <math>A</math> תקרא סריג-למחצה תחתון אם ורק אם לכל זוג איברים <math>a,b\in A</math> קיים אינפימום.
• <math>A</math> תקרא סריג-למחצה עליון אם ורק אם לכל זוג איברים <math>a,b\in A</math> קיים סופרמום.

עבור סריג-למחצה תחתון, לכל <math>a,b\in A</math> מסמנים <math>a\and b:=\inf(a, b)</math>. באופן דומה עבור סריג-למחצה עליון, לכל <math>a,b\in A</math> מסמנים <math>a\or b:=\sup(a, b)</math>. <math>a\and b</math> נקרא המפגש של <math>a</math> ו-<math>b</math>, ו-<math>a\or b</math> נקרא המצרף של <math>a</math> ו-<math>b</math>.

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

תהי קבוצה כלשהי <math>A</math> ותהי פעולה בינארית <math>\and:A\times A\to A</math> המקיימת את התנאים הבאים:

• אסוציאטיביות: לכל <math>x,y,z\in A</math> מתקיים ש-<math>(x\and y)\and z=x\and (y\and z)</math>
• קומוטטיביות: לכל <math>x,y\in A</math> מתקיים ש-<math>x\and y=y\and x</math>
• אידמפוטנטיות: לכל <math>x\in A</math> מתקיים ש-<math>x\and x = x</math>

הזוג <math>(A,\and)</math> יקרא סריג-למחצה והפעולה <math>\and</math> תקרא מפגש.

לפי הגדרה זו, אין הבדל בהגדרה בין סריג-למחצה עליון או תחתון. אם משתמשים בסימון <math>\or</math> במקום <math>\and</math>, אז קוראים לפעולה הבינארית של הסריג מצרף.

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

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

יחס סדר גורר אלגברה

תהי קבוצה סדורה חלקית <math>(A,\le)</math> שמהווה סריג-למחצה תחתון לפי ההגדרה ליחס סדר חלקי. מגדירים פעולה בינארית <math>\and:A\times A\to A</math> כך שלכל <math>a,b\in A</math>:

<math>a\and b:=\max\left\{s\mid s\le a,s\le b\right\}</math>

לפי ההגדרה לסריג-למחצה תחתון לפי יחס סדר חלקי, פעולה זו מוגדרת היטב לכל <math>a,b\in A</math>. יש להוכיח כי <math>\and</math> מקיימת את התכונות של פעולת מפגש.

אסוציאטיביות: יהי <math>x,y,z\in A</math>. אזי:

<math>(x\and y)\and z=\max\left\{s\mid s\le x\and y,s\le z\right\} =\max\left\{s\mid s\le x,s\le y,s\le z\right\}</math>

<math>x\and (y\and z)=\max\left\{s\mid s\le x,s\le y \and z\right\} =\max\left\{s\mid s\le x,s\le y,s\le z\right\}</math>

לכן בהכרח <math>(x\and y)\and z=x\and (y\and z)</math>.

קומוטטיביות: יהי <math>x,y\in A</math>. אזי:

<math>x\and y=\max\left\{s\mid s\le x,s\le y\right\}=\max\left\{s\mid s\le y,s\le x\right\}=y\and x</math>

אידמפוטנטיות: יהי <math>x\in A</math>. אזי:

<math>x\and x=\max\left\{s\mid s\le x,s\le x\right\}=\max\left\{s\mid s\le x\right\}=x</math>

מכל אלה נובע כי <math>(A,\and)</math> היא סריג למחצה לפי ההגדרה האלגברית.

אלגברה גוררת יחס סדר

תהי סריג-למחצה לפי ההגדרה האלגברית <math>(A,\and)</math>. מגדירים יחס <math>\le</math> על <math>A</math> כך שלכל <math>a,b\in A</math> מתקיים ש-<math>a\le b</math> אם ורק אם <math>a\and b=a</math>. ראשית, יש להוכיח כי היחס <math>\le</math> הוא יחס סדר חלקי.

טרנזיטיביות: יהי <math>x,y,z\in A</math> כך ש-<math>x\le y</math> וגם <math>y\le z</math>. אזי:

<math>x\and z = (x\and y)\and z=x\and(y\and z)=x\and y=x</math>

לכן <math>x\le z</math>.

אנטי-סימטריות: יהי <math>x,y\in A</math> כך ש-<math>x\le y</math> וגם <math>y\le x</math>. מכיוון ש-<math>x\le y</math> מתקיים ש-<math>x\and y =x</math> ומכיוון ש-<math>y\le x</math> מתקיים ש-<math>y\and x=y</math>. מכל זה:

<math>x=x\and y=y\and x = y</math>

רפלקסיביות: יהי <math>x\in A</math>. ידוע כי <math>x\and x=x</math>, לכן בהכרח <math>x\le x</math>.

מכל זה, <math>(A,\le)</math> היא קבוצה סדורה חלקית. כעת יש להוכיח כי היא גם סריג-למחצה תחתון לפי ההגדרה של סדר חלקי.

יהי <math>a,b\in A</math>. יש להוכיח כי <math>c:=a\and b</math> הוא האינפימום שלהם. ניתן להראות כי:

<math>c\and a=(a\and b)\and a=b\and (a\and a)=b\and a = c\Longrightarrow c\le a</math>

<math>c\and b=(a\and b)\and b=a\and (b\and b)=a\and b = c\Longrightarrow c\le b</math>

כלומר, <math>c</math> הוא חסם תחתון משותף של <math>a</math> ושל <math>b</math>. כעת יש להוכיח כי הוא חסם תחתון משותף מקסימלי.

יהי <math>d\in A</math> כך ש-<math>d\le a</math> וגם <math>d\le b</math>. אזי:

<math>d\and c=d\and(a \and b)=(d\and a)\and b=d\and b=d</math>

לכן <math>d\le c</math>.

מכל זה, <math>c</math> הוא האינפימום של <math>a</math> ו- <math>b</math>. הדבר נכון לכל <math>a,b\in A</math>, ולכן <math>(A,\le)</math> הוא סריג-למחצה תחתון.

מ.ש.ל.

תכונות

• כל קבוצה סדורה ביחס סדר מלא היא סריג-למחצה תחתון ועליון, ועל כן היא סריג.
• כל סריג-למחצה תחתון הוא קבוצה מכוונת מטה, וכל סריג למחצה עליון הוא קבוצה מכוונת מעלה. ההפך אינו בהכרח נכון.
• בהינתן סריג-למחצה תחתון, לכל תת-קבוצה סופית לא ריקה שלו יש אינפימום. באופן דומה, בהינתן סריג-למחצה עליון, לכל תת-קבוצה סופית לא ריקה שלו יש סופרמום.
• בהינתן סריג-למחצה תחתון <math>(A,\le)</math>, הקבוצה הסדורה <math>(A,\ge)</math> היא סריג-למחצה עליון כאשר <math>\ge</math> הוא היחס ההופכי ל-<math>\le</math>.

תת-סריג-למחצה

יהי סריג-למחצה <math>(A,\and)</math> תחת ההגדרה האלגברית. קבוצה כלשהי <math>B\subseteq A</math> תקרא תת-סריג-למחצה של <math>A</math> אם ורק אם היא סגורה תחת פעולת המפגש. כלומר, לכל <math>a,b\in B</math> מתקיים ש-<math>a\and b\in B</math>.

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

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

הקבוצה הריקה <math>\emptyset</math> היא תת-סריג-למחצה (באופן ריק) והקבוצה <math>A</math> עצמה היא תת-סריג-למחצה (באופן טריוויאלי).

הומומורפיזם של סריגים-למחצה

יהי שני סריגים-למחצה <math>(A,\and_A)</math> ו-<math>(B,\and_B)</math> לפי ההגדרה האלגברית. פונקציה <math>f\colon A\to B</math> תקרא הומומורפיזם של סריגים-למחצה אם ורק אם לכל <math>x,y\in A</math> מתקיים ש-<math>f(x\and_A y)=f(x)\and_B f(y)</math>. אם <math>f</math> היא פונקציה חד-חד ערכית ועל היא תקרא איזומורפיזם של סריגים-למחצה. כל איזומוריזם של סריגים למחצה הוא בהכרח איזומורפיזם סדר.

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

סריג-למחצה שלם

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

ניתן להכליל את התנאי הזה לקבוצות אינסופיות באופן הבא: בהינתן קבוצה סדורה <math>(A,\le)</math> הקבוצה תקרא סריג-למחצה תחתון שלם אם ורק אם לכל תת-קבוצה שלו (לאו דווקא סופית) שאיננה ריקה יש אינפימום. באופן דומה, הקבוצה תקרא סריג-למחצה עליון שלם אם ורק אם לכל תת-קבוצה שלו (לאו דווקא סופית) שאיננה ריקה יש סופרמום. הקבוצה תקרא סריג שלם אם ורק אם היא סריג-למחצה תחתון שלם וגם סריג-למחצה עליון שלם.

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

אם קבוצה סדורה <math>(A,\le)</math> היא סריג-למחצה תחתון שלם וגם יש לה איבר גדול ביותר (כלומר היא סריג חסום), אז היא סריג-למחצה עליון שלם, ולכן היא סריג שלם. באופן דומה, אם הקבוצה הסדורה היא סריג-למחצה עליון שלם וגם יש לה איבר קטן ביותר, אז היא סריג-למחצה תחתון שלם, ולכן היא סריג שלם.

דוגמאות

• בהינתן קבוצה כלשהי <math>A</math>, קבוצת החזקה <math>\mathcal{P}(A)</math> עם יחס ההכלה <math>\subseteq</math> היא סריג-למחצה תחתון ועליון, ועל כן היא סריג.
• בהינתן קבוצה כלשהי <math>A</math>, הקבוצה <math>\mathcal{X}=\mathcal{P}(A)\setminus\{\emptyset\}</math> עם יחס ההכלה <math>\subseteq</math> היא סריג-למחצה עליון, אך היא אינה בהכרח סריג-למחצה תחתון. כך למשל, אם קיימים שני איברים שונים <math>a,b\in A</math>, מתקיים ש-<math>\{a\},\{b\}\in \mathcal{X}</math> אבל אין איבר שמוכל בשניהם ב-<math>\mathcal{X}</math>.
• בהינתן המרחב הווקטורי <math>\R^n</math>, אפשר להגדיר עליו יחס סדר חלקי <math>\le</math> כך שלכל <math>v,u\in\R^n</math> מתקיים ש-<math>v\le u</math> אם ורק אם <math>v_i\le u_i</math> לכל <math>1\le i\le n</math>. אפשר להראות שלכל <math>v,u\in\R^n</math> קיים אינפימום <math>u\and v</math> וסופרמום <math>u\or v</math> כך שלכל <math>1\le i\le n</math>מתקיים ש-<math>(u\and v)_i=\min(u_i,v_i)</math> ו-<math>(u\or v)_i=\max(u_i,v_i)</math>. מכאן שהקבוצה הסדורה <math>(\R,\le)</math> היא סריג-למחצה עליון ותחתון, ולכן היא סריג.
• מסתכלים על חצי המרחב הדו-ממדי <math>H:=\{(x,y)\in\R^2\mid x+y\ge 0\}</math> עם היחס <math>\le</math> שהוגדר לעיל. <math>(H,\le)</math> הוא סריג-למחצה עליון שאינו סריג למחצה תחתון.
• מסתכלים על קבוצת פונקציות <math>C</math> שמהווה אוסף כל הפונקציות מהקטע <math>[0,1]</math> ל-<math>\R</math> שהן רציפות וקמורות בהחלט. מגדירים על <math>C</math> יחס סדר חלקי כך ש-<math>f\le g</math> אם ורק אם <math>f(x)\le g(x)</math> לכל <math>x\in[0,1]</math>. אזי, <math>(C,\le)</math> היא קבוצה סדורה חלקית שמהווה סריג-למחצה עליון, אך לא סריג-למחצה תחתון.
• תהי שפה מספר ראשון <math>\mathcal{L}</math> ותהי הקבוצה <math>\operatorname{con}(\mathcal{L})</math> אוסף כל התורות העקביות תחת השפה <math>\mathcal{L}</math>. מסתכלים על הקבוצה <math>\operatorname{con}(\mathcal{L})</math> עם יחס ההכלה <math>\subseteq</math>. זהו סריג-למחצה תחתון מכיוון שאם שתי התורות <math>T_1</math> ו-<math>T_2</math> הן עקביות, אז גם <math>T_1\cap T_2</math> היא עקבית (ייתכן שזוהי התורה הריקה). מצד שני לא בהכרח קיימת תורה עקבית שמכילה גם את <math>T_1</math> וגם את <math>T_2</math>. כך למשל, אם <math>T_1=\{p\}</math> ו-<math>T_2=\{\neg p\}</math> כאשר <math>p</math> הוא פסוק כלשהו, לא ניתן לאחד את שתי התורות לתורה עקבית אחת. מכאן ש-<math>(\operatorname{con}(\mathcal{L}),\subseteq)</math> הוא סריג-למחצה תחתון שאינו סריג-למחצה עליון.
• יהי אלפבית כלשהו <math>\Sigma</math> עם אוסף המילים הסופיות שלו (כולל המילה הריקה), <math>\Sigma^*</math> (ראו כוכב קלין). מגדירים על <math>\Sigma^*</math> יחס סדר חלקי <math>\preceq</math> שמשמעו "תת-מילה". כך למשל, אם <math>\Sigma</math> היא האלפבית של השפה האנגלית, אז <math>\text{art}\preceq \text{earth}</math>,‏ <math>\text{table}\preceq \text{comfortable}</math> ו-<math>\text{in}\preceq \text{inside}</math>. ניתן להראות כי <math>(\Sigma^*,\preceq)</math> הוא קבוצה מכוונת מכיוון שלכל זוג מילים קיים חסם תחתון (המילה הריקה) וחסם עליון (שרשור שתי המילים). עם זאת, לא מובטח שלזוג מילים יש אינפימום או סופרמום. כך למשל, לזוג המילים <math>\text{no}</math> ו-<math>\text{on}</math> יש חסמים תחתונים מינימליים (<math>\text{o}</math> ו-<math>\text{n}</math>) וחסמים עליונים מקסימליים (<math>\text{ono}</math> ו-<math>\text{non}</math>), אבל אין להם סופרמום או אינפימום. לכן <math>(\Sigma^*,\preceq)</math> היא קבוצה מכוונת שאיננה סריג-למחצה תחתון או עליון.

ראו גם

• מסנן (מתמטיקה)
• אלגברה בוליאנית (מבנה אלגברי)