שיעור תאוריה
תכונות של יחסים
איך מזהים שהנושא מתאים
- נתון יחס R על קבוצה ומבקשים לבדוק תכונות.
- שואלים אם היחס רפלקסיבי, סימטרי, אנטי-סימטרי או טרנזיטיבי.
- צריך להוכיח תכונה או לתת דוגמה נגדית.
- היחס מוגדר באמצעות תנאי כמו איחוד, חיתוך, הפרש או זוגות סדורים.
אינטואיציה
יחס הוא רשימה של חיבורים בין עצמים. למשל, אפשר לתאר מי מכיר את מי, אילו תחנות מחוברות בקו ישיר, או אילו קבוצות מקיימות תנאי משותף. הזוג (a,b) אומר שהחיבור מ-a אל b נמצא ברשימה.
ארבע התכונות שואלות שאלות קבועות על מבנה החיבורים: האם לכל עצם יש חיבור לעצמו, האם כל חיבור עובד גם בכיוון ההפוך, האם חיבור בשני הכיוונים מכריח שמדובר באותו עצם, והאם שרשרת של שני חיבורים מחייבת גם חיבור ישיר בין קצותיה.
כל תכונה היא הבטחה על כל האיברים המתאימים. לכן כמה דוגמאות מוצלחות אינן מוכיחות אותה, אבל דוגמה אחת שמפרה את ההבטחה מספיקה כדי להפריך אותה. הדוגמה חייבת להגיע מקבוצת הבסיס ולקיים את כל ההנחות של התכונה לפני שהיא מכשילה את המסקנה.
סימטריות ואנטי-סימטריות נשמעות דומות אך שואלות שאלות שונות. סימטריות דורשת שכל חיבור יוכל להתהפך. אנטי-סימטריות מאפשרת חיבור בכיוון אחד, אך אומרת שחיבור בשני הכיוונים בין שני עצמים יכול לקרות רק כאשר הם אותו עצם.
הגדרות פורמליות
R ⊆ A×Aיחס R על קבוצת בסיס A הוא קבוצה של זוגות סדורים שאיבריהם מגיעים מ-A. הסימון (a,b)∈R אומר שהזוג המסוים מקיים את התנאי שמגדיר את היחס.
| תכונה | הגדרה |
|---|---|
| רפלקסיבי | לכל a בקבוצת הבסיס, מתקיים (a,a)∈R. |
| סימטרי | אם (a,b)∈R, אז (b,a)∈R. |
| אנטי-סימטרי | אם (a,b)∈R וגם (b,a)∈R, אז a=b. |
| טרנזיטיבי | אם (a,b)∈R וגם (b,c)∈R, אז (a,c)∈R. |
בכל ההגדרות, המשתנים נבחרים מקבוצת הבסיס שעליה הוגדר היחס. בטענות מהצורה "אם ... אז ..." בודקים רק בחירות שמקיימות את ההנחה. למשל, אם אין שני איברים שונים שמתייחסים בשני הכיוונים, היחס יכול להיות אנטי-סימטרי גם בלי שכל זוג אפשרי יופיע בו.
דוגמה נגדית לתכונה היא בחירה של איברים מקבוצת הבסיס שמקיימת את הנחות ההגדרה אך אינה מקיימת את מסקנתה. ברפלקסיביות אין הנחת "אם", ולכן מספיק למצוא a∈A שעבורו (a,a)∉R.
כאשר יחס על Z מוגדר באמצעות התנאי 2|x+y, פירושו שקיים k∈Z כך ש-x+y=2k. אם מופיע גם התנאי x=y, הוא עדיין מבטיח סכום זוגי, מפני שאז x+y=2x.
בטרנזיטיביות, מן העדים x+y=2k ו-y+z=2m צריך לבנות עד עבור סכום הקצוות. מחברים את שני הסכומים ומחסירים את המופע הכפול של האיבר האמצעי:
x+z=(x+y)+(y+z)-2y=2(k+m-y)מאחר ש-k,m,y∈Z, גם k+m-y∈Z. לכן סכום הקצוות זוגי. זהו מנגנון כללי ליחסים שמקשרים מספרים בעלי אותה זוגיות באמצעות סכומם.
שיטת פתרון
- כותבים את קבוצת הבסיס ואת חובת ההוכחה המדויקת לפי הגדרת התכונה. לדוגמה, בטרנזיטיביות צריך להתחיל מ-a,b,c∈A ולהראות שהנחות על שני זוגות מובילות לשייכות של הזוג השלישי.
- להוכחת תכונה בוחרים איברים שרירותיים מקבוצת הבסיס ומניחים רק את ההנחות שמופיעות בהגדרה. להפרכה מציעים איברים מסוימים ובודקים תחילה שכל אחד מהם אכן שייך לקבוצת הבסיס.
- פותחים כל שייכות ליחס לתנאי שמגדיר אותו. אם (a,b)∈R מוגדר באמצעות משוואה, שייכות לקבוצה או קיום של מספר, רושמים את המידע הזה במפורש לפני שמשתמשים בו.
- מבצעים את החישוב בשורות עוקבות. כאשר ההגדרה דורשת קיום של עד, מציגים את העד, מסבירים כיצד הוא נבנה ומוודאים שהוא שייך לתחום הנדרש. למשל, בעדות לזוגיות צריך להראות שהעד החדש הוא מספר שלם.
- אורזים את התוצאה בחזרה להגדרת היחס. לאחר שהוכחנו שהתנאי המגדיר מתקיים עבור (b,a) או (a,c), רושמים במפורש שהזוג שייך ל-R ורק אז מסיקים את התכונה.
- בדוגמה נגדית מאמתים בנפרד את כל הנחות התכונה ואת כישלון המסקנה. לרפלקסיביות מציגים איבר שהזוג העצמי שלו חסר; לסימטריות זוג שהיפוכו חסר; לאנטי-סימטריות שני איברים שונים הקשורים בשני הכיוונים; ולטרנזיטיביות שרשרת ששני קצותיה אינם קשורים.
הערות מוכנות למבחן
- סימטרי ואנטי-סימטרי אינן שלילות זו של זו.
- היחס ≤ על מספרים הוא אנטי-סימטרי: אם a≤b וגם b≤a, אז a=b. הוא אינו סימטרי, משום שמ-a≤b לא נובע בדרך כלל b≤a.
- דוגמה נגדית חייבת להשתמש באיברים מתוך הקבוצה שעליה היחס מוגדר.
- כאשר היחס מוגדר על P(N), מותר לבחור תתי-קבוצות פשוטות כמו ∅ ו-N.