סדר חלקי

שגיאה ביצירת תמונה ממוזערת:

דיאגרמת הסה של איברי קבוצת החזקה של $\{x,y,z\}$ כאשר הסדר החלקי המוגדר עליהם הוא הכלה. איבר המינימום הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \emptyset} ואיבר המקסימום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x,y,z\}}

בתורת הקבוצות, סדר חלקי על קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} הוא יחס בינארי המקיים אחת משתי קבוצות של אקסיומות:

• היחס טרנזיטיבי, אנטי-סימטרי ורפלקסיבי - זהו יחס סדר חלש.
• היחס טרנזיטיבי, א-סימטרי ואי-רפלקסיבי - זהו יחס סדר חזק. (יחס טרנזיטיבי הוא א-סימטרי אם ורק אם הוא אי-רפלקסיבי).

הקבוצה $X$, יחד עם יחס הסדר, נקראת קבוצה סדורה.

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

סימון

מקובל לסמן יחסי סדר בווריאציות על סימן אי-השוויון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle <} , והיפוכו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle >} . הסימון ליחסי סדר חלשים כולל גם רמז לסימן השוויון, כגון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leq, \preceq} , בעוד שהסימון ליחסי סדר חזקים אינו כולל אותו: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle <, \prec} ).

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

שני סוגי היחסים כרוכים זה בזה: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leq} יחס סדר חלש, אז היחס (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \leq b} אבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \neq b} ) הוא יחס סדר חזק. אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle <} יחס סדר חזק, אז היחס (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a < b} או $a=b$) הוא יחס סדר חלש. מאידך, יחס סדר אינו יכול להיות גם חזק וגם חלש (אלא אם מדובר ביחס הריק על הקבוצה הריקה).

באופן כללי יכולים להיות שני איברים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} שאינם ניתנים להשוואה מבחינת היחס, ולכן הוא נקרא גם יחס סדר חלקי. אם עבור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b \in X} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \le b} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b \le a} אז קוראים ליחס $\leq$ סדר ליניארי (או סדר מלא), ולזוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(X, \le\right)} קבוצה סדורה ליניארית, או שרשרת.

דוגמאות

• קבוצת כל המספרים הטבעיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\mathbb{N},\le\right)} עם הסדר הסטנדרטי עליהם, היא קבוצה סדורה ליניארית. כך גם הממשיים.
• יחס החלוקה של מספרים טבעיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mid} מוגדר כך ש-$m\mid n$ אם ורק אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} מחלק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\mathbb{N},\mid\right)} היא קבוצה סדורה חלקית שאינה סדורה ליניארית, שכן לא ניתן, למשל, להשוות בין 5 ו-2, שאינם מחלקים אחד את השני.
• יחס החלוקה אינו יחס סדר על המספרים השלמים כי אינו אנטי-סימטרי: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \mid -1} וגם $-1\mid 1$ אף על פי ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1\ne 1} .

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

קובץ:Hasse diagram of powerset of 3 no greatest or least.svg

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

איבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in X} נקרא איבר מינימלי (איבר מזערי) אם לא קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b \in X} השונה ממנו כך ש-$\!\,b\leq a$..

איבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in X} נקרא איבר מקסימלי (איבר מרבי) אם לא קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b \in X} השונה ממנו כך ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \le b} .

איבר $a\in X$ נקרא מינימום (או לחלופין איבר קטן ביותר או איבר ראשון) אם לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b \in X} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \le b} .

איבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in X} נקרא מקסימום (או לחלופין איבר גדול ביותר או איבר אחרון) אם לכל $b\in X$ מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b \leq a} .

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

קבוצה סדורה ליניארית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(X,\le\right)} שבה יש איבר ראשון לכל תת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X } , נקראת קבוצה סדורה היטב.

כאשר מתקיים $x>y$, ואין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z } כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x>z>y } , אז אומרים ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} מכסה את $y$(ומכאן שבסדר צפוף אין שני איברים שמכסים זה את זה).

ראו גם

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

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

• סדר חלקי, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

32788451סדר חלקי