סדר חלקי

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

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

המונח נוסח לראשונה על-ידי המתמטיקאים ארנסט שרדר וצ'ארלס פרס בשנת 1911.

הגדרה פורמלית

בהינתן קבוצה כלשהי $X$ ויחס $R\subseteq X\times X$, מגדירים כי $R$ הוא יחס סדר חלקי על $X$ אם ורק אם הוא מקיים את התכונות הבאות:

1. טרנזיטיביות: לכל $x,y,z\in X$ כך ש-$(x,y)\in R$ וגם $(y,z)\in R$ מתקיים ש-$(x,z)\in R$.
2. אנטי-סימטריות: לכל $x,y\in X$ כך ש-$(x,y)\in R$ וגם $(y,x)\in R$ מתקיים ש-$x=y$.
3. רפלקסיביות: לכל $x\in X$ מתקיים ש-$(x,x)\in R$.

במקרה זה, הזוג הסדור $(X,R)$ יקרא קבוצה סדורה חלקית או קבוצה סדורה בקיצור.

במקום לסמן יחס סדר חלקי באותיות כפי שנעשה לעיל, מקובל להשתמש בווריאציות על הסימן $\leq$ והיפוכו $\geq$. דוגמאות לסימנים אלו הם $\preceq$,‏ $\sqsubseteq$,‏ $\subseteq$,‏ $\vDash$ וכו'.

בנוסף, כפי שנהוג עם יחסים בינאריים כלליים, במקום לכתוב $(x,y)\in \leq$ כותבים $x\leq y$.

יחסי סדר חלשים וחזקים

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

בהינתן קבוצה כלשהי $X$ ויחס $R\subseteq X\times X$, מגדירים כי $R$ הוא יחס סדר חלקי חזק על $X$ אם ורק אם הוא מקיים את התכונות הבאות:

1. טרנזיטיביות: לכל $x,y,z\in X$ כך ש-$(x,y)\in R$ וגם $(y,z)\in R$ מתקיים ש-$(x,z)\in R$.
2. אנטי-סימטריות חזקה: לכל $x,y\in X$ המקיימים $(x,y)\in R$ בהכרח מתקיים ש-$(y,x)\notin R$

מתנאי האנטי-סימטריות החזקה נובע גם התנאי ש:

3. אנטי-רפלקסיביות: לכל $x\in X$ מתקיים ש-$(x,x)\notin R$

באופן דומה ליחסי סדר חלשים, מקובל לסמן יחסי סדר חזקים בווריאציות על הסימן $<$ והיפוכו $>$. דוגמאות לסימנים אלו הם $\prec$,‏ $\sqsubset$,‏ $\subset$ וכו'. באופן דומה לסדר חלקי חלש, במקום לכתוב $x,y\in <$ כותבים $x<y$.

ניתן להוכיח כי שני המובנים של יחס סדר נובעים זה מזה:

• בהינתן קבוצה $X$ ויחס סדר חלקי חלש $\leq$ מגדירים כי לכל $x,y\in X$ מתקיים ש-$x<y$ אם ורק אם $x\leq y$ וגם $x\neq y$. ניתן להוכיח כי $<$ הוא יחס סדר חלקי חזק על $X$.
• באופן דומה, בהינתן קבוצה $X$ ויחס סדר חלקי חזק $<$ מגדירים כי לכל $x,y\in X$ מתקיים ש-$x\leq y$ אם ורק אם $x<y$ או $x=y$. ניתן להוכיח כי $\leq$ הוא יחס סדר חלקי חלש על $X$.

התאמה זו בין יחסי סדר חלקיים חלשים על $X$ ליחסי סדר חלקיים חזקים על $X$ היא התאמה חד-חד ערכית ועל. מסיבה זו, לרוב מספיק לדון באחד כדי לקבל מידע מלא על האחר. על כן, ערך זה יעסוק מעתה והלאה ביחסי סדר חלקיים חלשים בלבד.

דוגמאות

• היחס "קטן או שווה ל-" $\leq$ על קבוצת המספרים הטבעיים $\mathbb {N}$, המספרים השלמים $\mathbb {Z}$, המספרים הרציונליים $\mathbb {Q}$ או המספרים הממשיים $\mathbb {R}$.
• היחס "מחלק את" $|$ על קבוצת המספרים הטבעיים $\mathbb {N}$.
• בהינתן קבוצה כלשהי $X$, היחס "מוכל ב-" $\subseteq$ על קבוצת החזקה של $X$,‏ ${\mathcal {P}}(X)$.
• בהינתן חבורה כלשהי $G$, אם מסמנים ב-$S(G)$ את אוסף התת-חבורות של $G$, ניתן להראות ש-$S(G)$ קבוצה סדורה תחת היחס החלקי "תת-חבורה של" $\leq$. באופן דומה, אם מסמנים ב-$N(G)$ את אוסף התת-חבורות הנורמליות של $G$, ניתן להראות ש-$N(G)$ אף היא קבוצה סדורה תחת היחס החלקי "תת-חבורה של" $\leq$.
• יהי אלפבית כלשהו $\Sigma$ עם אוסף המילים הסופיות שלו (כולל המילה הריקה), $\Sigma ^{*}$ (ראו כוכב קלין). מגדירים על $\Sigma ^{*}$ יחס סדר חלקי $\preceq$ שמשמעו "תת-מילה". כך למשל, אם $\Sigma$ היא האלפבית של השפה האנגלית, אז ${\text{art}}\preceq {\text{earth}}$,‏ ${\text{table}}\preceq {\text{comfortable}}$ ו-${\text{in}}\preceq {\text{inside}}$. ניתן להראות כי $\preceq$ הוא יחס סדר חלקי על $\Sigma ^{*}$.
• בהינתן קבוצה סדורה כלשהי $(P,\leq )$ וקבוצת אינדקסים $I$, מסתכלים על קבוצת הפונקציות $P^{I}$ (פונקציות מ-$I$ ל-$P$). לכל $f_{1},f_{2}\in P^{I}$ מגדירים ש-$f_{1}\preceq f_{2}$ אם ורק אם לכל $i\in I$ מתקיים ש-$f_{1}(i)\leq f_{2}(i)$. ניתן להראות כי $\preceq$ הוא יחס סדר חלקי על $P^{I}$.

יחסים בין איברים

השוואתיות

בהינתן קבוצה סדורה כלשהי $(X,\leq )$, זוג איברים $x,y\in X$ ייקראו בני-השוואה אם ורק אם מתקיים ש-$x\leq y$ או $y\leq x$.

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

בכל קבוצה סדורה, היחס "בר-השוואה ל-" הוא יחס רפלקסיבי וסימטרי, אך הוא אינו טרנזיטיבי בהכרח. במקורות מסוימים מסמנים את היחס "בר-השוואה ל-" ב-$\sim$. באופן דומה, היחס "אינו בר-השוואה ל-" הוא יחס אנטי-רפלקסיבי וסימטרי, אך הוא אינו טרנזיטיבי בהכרח. במקורות מסוימים מסמנים את היחס "אינו בר-השוואה ל-" ב-$\parallel$.

יחס סדר חלקי שבו כל שני איברים הם בני-השוואה נקרא סדר מלא. משפט ההרחבה של שפילריין (Szpilrajn extension theorem) קובע שלכל קבוצה $X$ שסדורה בסדר חלקי $\leq$, קיים סדר מלא $\leq ^{*}$ כך שלכל $x\leq y$ מתקיים ש-$x\leq ^{*}y$. במילים אחרות, ניתן להוסיף ל-$\leq$ יחסים נוספים על-מנת להפוך אותו לסדר מלא.

כיסוי

בהינתן קבוצה סדורה כלשהי $(X,\leq )$ וזוג איברים $x,y\in X$, מגדירים כי $y$ מכסה את $x$ אם ורק אם מתקיימים התנאים הבאים:

1. $x<y$, כלומר, $x\leq y$ וגם $x\neq y$.
2. לא קיים $z\in X$ כך ש-$x<z<y$. כלומר, לא קיים איבר בין $x$ ל-$y$ ששונה משניהם.

יחס סדר חלקי שבו אין איבר שמכסה איבר אחר נקרא סדר צפוף.

סדר מושרה

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

בהינתן קבוצה $X$ עם יחס סדר חלקי $\leq _{X}$ ותת-קבוצה שלה $Y\subseteq X$, מגדירים $\leq _{Y}:=\{a\leq _{X}b\mid a,b\in Y\}=\leq _{X}\cap (Y\times Y)$. ניתן להוכיח כי $\leq _{Y}$ הוא יחס סדר חלקי על $Y$.

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

ישנן מספר תכונות שנשמרות במעבר מקבוצה לתת-קבוצה שלה:

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

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

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

איבר קטן ביותר ואיבר גדול ביותר

ערך מורחב – האיבר הקטן ביותר והגדול ביותר

דיאגרמת הסה של קבוצת החזקה של $\{x,y,z\}$. היחס בין האיברים בקבוצה סדורה זו הוא יחס ההכלה. ניתן לראות כי הקבוצה הריקה $\emptyset$ והקבוצה $\{x,y,z\}$ מהוות איבר קטן ביותר וגדול ביותר בהתאמה.

בהינתן קבוצה סדורה $(X,\leq )$:

• איבר $a\in X$ נקרא איבר קטן ביותר (גם: מינימום או איבר ראשון) אם לכל $b\in X$ מתקיים ש-$a\leq b$.
• איבר $a\in X$ נקרא איבר גדול ביותר (גם: מקסימום או איבר אחרון) אם לכל $b\in X$ מתקיים ש-$b\leq a$.

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

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

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

איבר מינימלי ואיבר מקסימלי

ערך מורחב – איבר מינימלי ומקסימלי

דיאגרמת הסה של קבוצת החזקה של $\{x,y,z\}$, ללא $\{x,y,z\}$ וללא $\emptyset$. בקבוצה מצומצמת זו, כל האיברים בשורה העליונה הם מקסימליים וכל האיברים בשורה התחתונה הם מינימליים, אך אף אחד מהם הוא לא האיבר הגדול ביותר או הקטן ביותר.

בהינתן קבוצה סדורה $(X,\leq )$:

• איבר $a\in X$ נקרא איבר מינימלי או איבר מזערי אם לכל $b\in X$ המקיים $b\leq a$ מתקיים בהכרח כי $b=a$.
• איבר $a\in X$ נקרא איבר מקסימלי או איבר מרבי אם לכל $b\in X$ המקיים $a\leq b$ מתקיים בהכרח כי $b=a$.

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

חסמים

ערך מורחב – חסם (מתמטיקה)

בהינתן קבוצה סדורה $(X,\leq )$, תת-קבוצה $Y\subseteq X$ ואיבר $m\in X$:

• $m$ יקרא חסם מלמטה של $Y$ אם ורק אם לכל $y\in Y$ מתקיים ש-$m\leq y$.
• $m$ יקרא חסם מלמעלה של $Y$ אם ורק אם לכל $y\in Y$ מתקיים ש-$y\leq m$.

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

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

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

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

אטום וקו-אטום

בהינתן קבוצה סדורה $(X,\leq )$:

• אם ל-$X$ קיים איבר קטן ביותר, נסמנו ב-$0\in X$, איבר $a\in X$ ייקרא אטום אם ורק אם הוא מכסה את $0$.
• אם ל-$X$ קיים איבר גדול ביותר, נסמנו ב-$1\in X$, איבר $a\in X$ ייקרא קו-אטום אם ורק אם $1$ מכסה אותו.

פונקציות בין קבוצות סדורות

פונקציה שומרת סדר

ערך מורחב – פונקציה שומרת סדר

בהינתן זוג קבוצות סדורות $(P,\leq _{P})$ ו-$(Q,\leq _{Q})$ ופונקציה $\varphi :P\to Q$,‏ $\varphi$ תקרא פונקציה שומרת סדר אם ורק אם לכל $x,y\in P$ המקיימים $x\leq _{P}y$ מתקיים גם ש-$\varphi (x)\leq _{Q}\varphi (y)$.

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

שיכון סדר

ערך מורחב – שיכון סדר

הקבוצה הסדורה השמאלית משוכנת לתוך הקבוצה הסדורה הימנית.

בהינתן זוג קבוצות סדורות $(P,\leq _{P})$ ו-$(Q,\leq _{Q})$ ופונקציה $\varphi :P\to Q$,‏ $\varphi$ תקרא שיכון סדר אם ורק אם מתקיימים התנאים הבאים:

1. שמירת סדר: לכל $x,y\in P$ המקיימים $x\leq _{P}y$ מתקיים גם ש-$\varphi (x)\leq _{Q}\varphi (y)$.
2. החזרת סדר: לכל $x,y\in P$ המקיימים $\varphi (x)\leq _{Q}\varphi (y)$ מתקיים גם ש-$x\leq _{P}y$.

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

המשמעות של שיכון סדר היא שבתוך הקבוצה $Q$ קיימת תת-קבוצה שמתנהגת כמו $P$ (מבחינת הסדר שלה). שיכון סדר הוא טרנזיטיבי: אם $P$ משוכנת ב-$Q$ ו-$Q$ משוכנת ב-$R$, אז $P$ משוכנת ב-$R$.

איזומורפיזם סדר

ערך מורחב – איזומורפיזם סדר

משמאל, קבוצת המחלקים הטבעיים של המספר 30; מימין, קבוצת החזקה של הקבוצה $\{x,y,z\}$. ניתן לראות שמבנה הסדר של שתי הקבוצות זהה, ולכן הן איזומורפיות סדר זו לזו

בהינתן זוג קבוצות סדורות $(P,\leq _{P})$ ו-$(Q,\leq _{Q})$ ופונקציה $\varphi :P\to Q$, ‏ $\varphi$ תקרא איזומורפיזם סדר אם ורק אם היא שיכון סדר מ-$P$ ל-$Q$ והיא גם פונקציה חד-חד ערכית ועל.

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

בניית סדרים חלקיים

סדר הופכי

בהינתן קבוצה סדורה $(X,\leq )$, מגדירים את היחס $\geq$ כך שלכל $x,y\in X$, מתקיים ש-$x\geq y$ אם ורק אם $y\leq x$ (זהו בעצם היחס ההופכי של $\leq$). ניתן להוכיח כי $(X,\geq )$ גם היא קבוצה סדורה. הסדר $\geq$ נקרא הסדר ההופכי של $\leq$ (או לחלופין הסדר הדואלי של $\leq$) ומסמנים אותו ב-$X^{\operatorname {op} }$.

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

סדר הופכי הוא אינוולוטי, כלומר ש-$\left(X^{\operatorname {op} }\right)^{\operatorname {op} }=X$.

סכום סודרי

יהי זוג קבוצות סדורות זרות $(X,\leq _{X})$ ו-$(Y,\leq _{Y})$. מסמנים ב-$Z:=X\uplus Y$. מגדירים יחס $\leq _{Z}$ על $Z$ כך שלכל $x,y\in Z$ מתקיים ש-$x\leq _{Z}y$ אם ורק אם מתקיים אחד מהתנאים הבאים:

1. $x,y\in X$ ו-$x\leq _{X}y$
2. $x,y\in Y$ ו-$x\leq _{Y}y$
3. $x\in X$ ו-$y\in Y$

ניתן להוכיח כי $\leq _{Z}$ הוא סדר חלקי על $Z$. סדר חלקי זה נקרא הסכום הסודרי (אורדינלי) של $X$ ו-$Y$ ומסמנים אותו ב-$X\oplus Y$.

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

• אם $X$ ו-$Y$ סדורים בסדר מלא, גם $X\oplus Y$ מסודר בסדר מלא.
• אם $X$ ו-$Y$ סדורים בסדר טוב, גם $X\oplus Y$ מסודר בסדר טוב.

ניתן להוכיח כי הסכום הסודרי הוא אסוציאטיבי. כלומר, לכל שלשת קבוצות סדורות $(P,\leq _{P})$,‏ $(Q,\leq _{Q})$ ו-$(R,\leq _{R})$ מתקיים ש-$P\oplus (Q\oplus R)$ איזומורפי סדר ל-$(P\oplus Q)\oplus R$. לעומת זאת, סכום סודרי הוא לא בהכרח קומוטטיבי. כלומר, באופן כללי, $P\oplus Q$ אינה בהכרח איזומורפית סדר ל-$Q\oplus P$.

סדר לקסיקוגרפי

יהי זוג קבוצות סדורות זרות $(X,\leq _{X})$ ו-$(Y,\leq _{Y})$. מסמנים ב-$Z:=X\times Y$. מגדירים יחס $\leq _{Z}$ על $Z$ כך שלכל $(x_{1},y_{1}),(x_{2},y_{2})\in Z$ מתקיים ש-$(x_{1},y_{1})\leq _{Z}(x_{2},y_{2})$ אם ורק אם מתקיים אחד מהתנאים הבאים:

• $x_{1}<_{X}x_{2}$ (כלומר, $x_{1}\leq _{X}x_{2}$ וגם $x_{1}\neq x_{2}$)
• $x_{1}=x_{2}$ וגם $y_{1}\leq _{Y}y_{2}$.

ניתן להוכיח כי $\leq _{Z}$ הוא סדר חלקי על $Z$. סדר חלקי זה נקרא המכפלה הלקסיקוגרפית של $X$ ו-$Y$, ולעיתים מסמנים אותו ב-$X\cdot Y$. באופן דומה לסכום הסודרי, מכפלה לקסיקוגרפית היא אסוציאטיבית אך לא קומוטטיבית. ניתן להוכיח שהמכפלה הלקסיקוגרפית מתפלגת מעל הסכום הסודרי מימין. כלומר, לכל שלושה קבוצות סדורות $(P,\leq _{P})$,‏ $(Q,\leq _{Q})$ ו-$(R,\leq _{R})$ מתקיים ש-$(P\oplus Q)\cdot R$ איזומורפי סדר ל-$(P\cdot R)\oplus (Q\cdot R)$. עם זאת, לא מתקיים פילוגיות משמאל.

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

• אם $X$ ו-$Y$ סדורים בסדר מלא, גם $X\cdot Y$ מסודר בסדר מלא.
• אם $X$ ו-$Y$ סדורים בסדר טוב, גם $X\cdot Y$ מסודר בסדר טוב.
• אם $X$ ו-$Y$ סדורים בסדר צפוף, גם $X\cdot Y$ מסודר בסדר צפוף.

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

מכפלה ישרה

יהי זוג קבוצות סדורות זרות $(X,\leq _{X})$ ו-$(Y,\leq _{Y})$. מסמנים ב-$Z:=X\times Y$. מגדירים יחס $\leq _{Z}$ על $Z$ כך שלכל $(x_{1},y_{1}),(x_{2},y_{2})\in Z$ מתקיים ש-$(x_{1},y_{1})\leq _{Z}(x_{2},y_{2})$ אם ורק אם $x_{1}\leq _{X}x_{2}$ וגם $y_{1}\leq _{Y}y_{2}$.

ניתן להוכיח כי $\leq _{Z}$ הוא סדר חלקי על $Z$. סדר חלקי זה נקרא המכפלה הישרה של $X$ ו-$Y$, ולעיתים מסמנים אותו ב-$X\times Y$ או $X\star Y$. המכפלה הישרה היא אסוציאטיבית אך לא קומוטטיבית. בנוסף, המכפלה הישרה לא מתפלגת כלל מעל הסכום האורדינלי (לא משמאל ולא מימין).

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

קדם-סדר

ערך מורחב – קדם-סדר

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

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

כל קדם-סדר ניתן להפוך לסדר חלקי באופן הבא:

מגדירים על $X$ את היחס $\sim$ כך ש-$x\sim y$ אם ורק אם $xRy$ וגם $yRx$. ניתן להוכיח כי $\sim$ הוא יחס שקילות על $X$. מגדירים את קבוצת מחלקות השקילות $X':=X/\sim$. מגדירים על $X'$ את היחס $R'$ כך שלכל $[x],[y]\in X'$ מתקיים ש-$[x]R'[y]$ אם ורק אם $xRy$. ניתן להוכיח כי $R'$ מוגדר היטב מכיוון שהוא לא תלוי בבחירת הנציג של מחלקות השקילות, ובנוסף $R'$ הוא יחס סדר חלקי.

ראו גם

• תורת הקבוצות - מונחים

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

• סדר חלקי, באתר MathWorld (באנגלית)
• גדי אלכסנדרוביץ', תורת הקבוצות - יחסי סדר, באתר "לא מדויק", 10 בינואר 2020