שיעור תאוריה
יחסי סדר חלקי ומלא
איך מזהים שהנושא מתאים
- מבקשים להראות שיחס הוא סדר חלקי או סדר מלא.
- צריך לבדוק רפלקסיביות, אנטי-סימטריות וטרנזיטיביות יחד.
- איברי קבוצת הבסיס הם זוגות או וקטורים, וההשוואה נעשית רכיב-רכיב.
- מבקשים למצוא שני איברים שאינם ניתנים להשוואה.
- מבקשים למצוא איברים מינימליים, מקסימליים, קטן ביותר או גדול ביותר.
- היחס מוגדר באמצעות חלוקה, או שמבצעים הפרש בין שני יחסי סדר.
אינטואיציה
סדר חלקי מאפשר לומר שאיבר אחד אינו גדול מאחר לפי כמה דרישות יחד. למשל, אם משווים שתי חלופות לפי מחיר וזמן, חלופה אחת קודמת לאחרת רק כאשר היא אינה גדולה ממנה בשני המדדים.
ייתכן שחלופה אחת זולה יותר אך איטית יותר. במקרה כזה אף חלופה אינה קודמת לאחרת, ולכן הן אינן ניתנות להשוואה. זה מותר בסדר חלקי.
בסדר מלא כל שני איברים חייבים להיות ניתנים להשוואה. במספרים רגילים התנאי מתקיים, אבל בהשוואה רכיב-רכיב הוא עשוי להיכשל כאשר כל איבר עדיף ברכיב אחר.
ביחס חלוקה אפשר לחשוב על שרשרת של גדלים: איבר קודם לאחר אם האחר מתקבל ממנו בכפולה שלמה. איבר מינימלי פשוט אינו מקבל חץ מאיבר שונה, ואילו איבר קטן ביותר צריך להקדים את כל האיברים. לכן "מינימלי" ו"קטן ביותר" אינם אותו מושג.
הגדרות פורמליות
| מושג | משמעות |
|---|---|
| סדר חלקי | יחס שהוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי. |
| ברי-השוואה | שני איברים a,b שעבורם מתקיים aRb או bRa. |
| סדר מלא | סדר חלקי שבו כל שני איברים בקבוצת הבסיס ברי-השוואה. |
| סדר מכפלה | יחס על זוגות שבו משווים כל רכיב בנפרד ובאותו כיוון. |
| הפרש סימטרי | אוסף האיברים שנמצאים בדיוק באחת משתי קבוצות. |
| איבר מינימלי | איבר שאין איבר שונה ממנו שקודם לו ביחס. |
| איבר מקסימלי | איבר שאין איבר שונה ממנו שבא אחריו ביחס. |
| איבר קטן ביותר | איבר שקודם לכל איבר בקבוצה. אם הוא קיים, הוא יחיד. |
| איבר גדול ביותר | איבר שכל איבר בקבוצה קודם לו. אם הוא קיים, הוא יחיד. |
סדר מכפלה על Z×Z מוגדר כך:
((x,y),(m,n))∈R ⇔ x≤m ∧ y≤nשני התנאים חייבים להתקיים יחד. לכן ייתכנו זוגות שאינם ברי-השוואה, למשל (0,1) ו-(1,0): בכל כיוון אחד הרכיבים עומד בדרישה והרכיב האחר נכשל.
יחס החלוקה מוגדר על קבוצת מספרים כך:
aRb ⇔ a|b ⇔ ∃k∈Z: b=akכאשר כל איברי הקבוצה הם חזקות של אותו ראשוני, המעריכים קובעים את הסדר: אם a=2i ו-b=2j עם i≤j, אז b=a·2j-i, ולכן a|b. לעומת זאת, אם הקבוצה כוללת גם a וגם -a, אנטי-סימטריות נכשלת: כל אחד מחלק את האחר באמצעות הכופל -1, אף שהם שונים.
הפרש סימטרי של יחסים הוא הפרש סימטרי של קבוצות הזוגות:
S₁ΔS₂=(S₁\S₂)∪(S₂\S₁)כל יחס סדר חלקי מכיל את כל הזוגות העצמיים (x,x). לכן אם S₁,S₂ הם סדרים חלקיים על אותה קבוצה, כל זוג עצמי נמצא בשניהם ואינו נמצא בהפרש הסימטרי. על קבוצה לא ריקה, ההפרש הסימטרי אינו רפלקסיבי ולכן אינו סדר חלקי.
אותו חסם רפלקסיבי חל גם על הפרש רגיל. אם S1,S2 סדרים חלקיים על אותה קבוצה, אז כל (x,x) נמצא ב-S2 ולכן מוסר מן S1\S2. על קבוצה לא ריקה התוצאה אינה רפלקסיבית.
שיטת פתרון
- מציינים את קבוצת הבסיס וכותבים את תנאי היחס לכל רכיב.
- לרפלקסיביות לוקחים איבר שרירותי ומשווים כל רכיב לעצמו.
- לאנטי-סימטריות מניחים את היחס בשני הכיוונים. בכל רכיב משתמשים באנטי-סימטריות של ≤ כדי לקבל שוויון, ואז מסיקים שוויון של הזוגות.
- לטרנזיטיביות לוקחים שלושה איברים, פותחים את שתי ההנחות לרכיבים, ומשתמשים בטרנזיטיביות של ≤ בכל רכיב בנפרד.
- לבדיקת סדר מלא מחפשים זוג איברים שכל אחד קטן מן האחר ברכיב שונה. מאמתים ששני כיווני היחס נכשלים.
- בפעולה בין יחסים בודקים תחילה אם הזוגות העצמיים נשמרים. כישלון רפלקסיביות כבר מספיק כדי להפריך סדר חלקי.
הערות מוכנות למבחן
- סדר חלקי אינו דורש שכל שני איברים יהיו ברי-השוואה.
- שוויון זוגות סדורים דורש שוויון של שני הרכיבים המתאימים.
- בדוגמת אי-השוואה צריך לבדוק במפורש ששני כיווני היחס נכשלים.
- הפרש סימטרי מסיר איברים משותפים, ובפרט מסיר זוגות עצמיים המופיעים בשני יחסי סדר.