מתמטיקה דיסקרטית ח (2023 — מרחב למידה אישי

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

יחסים בינאריים: הגדרה וייצוג

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

יחס בינארי (Binary Relation): בהינתן שתי קבוצות A ו-B, יחס בינארי R מ-A ל-B הוא תת-קבוצה של המכפלה הקרטזית A × B. אם A=B, נאמר ש-R הוא יחס על A.

אם זוג סדור (a,b) שייך ל-R, אנו כותבים aRb וקוראים "a קשור ל-b".

ייצוגים של יחסים:

קבוצת זוגות סדורים: הדרך הישירה ביותר, למשל R = {(1,2), (2,3), (3,1)}.
מטריצת שכנות (Adjacency Matrix): אם R הוא יחס על קבוצה סופית A={a1, ..., an}, ניתן לייצג אותו באמצעות מטריצה M בגודל n×n, כאשר M_ij = 1 אם (ai, aj) ∈ R, ו-0 אחרת.
גרף מכוון (Directed Graph / Digraph): כל איבר בקבוצה הוא קודקוד, וקשת מכוונת מ-a ל-b קיימת אם (a,b) ∈ R.

תחום (Domain): קבוצת כל האיברים הראשונים בזוגות הסדורים של R. {a | ∃b, (a,b) ∈ R}.

טווח (Range): קבוצת כל האיברים השניים בזוגות הסדורים של R. {b | ∃a, (a,b) ∈ R}.

תכונות יחסים מרכזיות

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

יחס רפלקסיבי (Reflexive)

לכל איבר a בקבוצה, (a,a) ∈ R. כלומר, כל איבר קשור לעצמו. (דוגמה: יחס שוויון =)

יחס סימטרי (Symmetric)

אם (a,b) ∈ R, אז גם (b,a) ∈ R. אם a קשור ל-b, אז b קשור ל-a. (דוגמה: "שכן של")

יחס אנטי-סימטרי (Anti-symmetric)

אם (a,b) ∈ R וגם (b,a) ∈ R, אז בהכרח a=b. אם a קשור ל-b ו-b קשור ל-a, הם חייבים להיות אותו איבר. (דוגמה: יחס "קטן או שווה מ-" ≤)

יחס טרנזיטיבי (Transitive)

אם (a,b) ∈ R וגם (b,c) ∈ R, אז בהכרח (a,c) ∈ R. אם a קשור ל-b ו-b קשור ל-c, אז a קשור ל-c. (דוגמה: "חבר של חבר הוא חבר" או יחס "קטן מ-" <)

תכונות נוספות:

אי-רפלקסיבי (Irreflexive): לכל איבר a בקבוצה, (a,a) ∉ R. (דוגמה: יחס "קטן מ-" <)
א-סימטרי (Asymmetric): אם (a,b) ∈ R, אז (b,a) ∉ R. יחס א-סימטרי הוא תמיד גם אי-רפלקסיבי וגם אנטי-סימטרי.

יחסי שקילות ויחסי סדר חלקי

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

יחס שקילות (Equivalence Relation): יחס R על קבוצה A המקיים את שלוש התכונות הבאות:

רפלקסיביות
סימטריות
טרנזיטיביות

מחלקת שקילות (Equivalence Class): בהינתן יחס שקילות R על קבוצה A ואיבר a ∈ A, מחלקת השקילות של a, המסומנת [a], היא קבוצת כל האיברים ב-A הקשורים ל-a: [a] = {x ∈ A | xRa}.

חלוקה (Partition): קבוצת תת-קבוצות לא ריקות של A המקיימות: 1. האיחוד שלהן הוא A. 2. חיתוך כל שתי תת-קבוצות שונות הוא ריק. מחלקות השקילות של יחס שקילות יוצרות חלוקה של הקבוצה.

יחס סדר חלקי (Partial Order Relation): יחס R על קבוצה A המקיים את שלוש התכונות הבאות:

רפלקסיביות
אנטי-סימטריות
טרנזיטיביות

קבוצה עם יחס סדר חלקי נקראת קבוצה סדורה חלקית (Partially Ordered Set / Poset).

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

איבר מקסימלי (Maximal Element): איבר x בקבוצה סדורה חלקית כך שאין איבר y שונה מ-x המקיים xRy.

איבר מינימלי (Minimal Element): איבר x בקבוצה סדורה חלקית כך שאין איבר y שונה מ-x המקיים yRx.

חוסם מלעיל (Upper Bound): איבר u בקבוצה סדורה חלקית המקיים xRu לכל x בתת-קבוצה נתונה S.

חוסם מלרע (Lower Bound): איבר l בקבוצה סדורה חלקית המקיים lRx לכל x בתת-קבוצה נתונה S.

סופרמום (Supremum / LUB): החוסם מלעיל הקטן ביותר של תת-קבוצה S.

אינפימום (Infimum / GLB): החוסם מלרע הגדול ביותר של תת-קבוצה S.

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

שאלות לדיון

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

נקודות לתשובת מודל

סימטרי מול אנטי-סימטרי: יחס סימטרי דורש שאם (a,b) קיים, אז גם (b,a) קיים. יחס אנטי-סימטרי דורש שאם גם (a,b) וגם (b,a) קיימים, אז בהכרח a=b. יחס יכול להיות גם סימטרי וגם אנטי-סימטרי רק אם כל הזוגות בו הם מהצורה (a,a). דוגמה: יחס השוויון (=) על כל קבוצה.
יחס שקילות וחלוקה: יחס שקילות מגדיר חלוקה ייחודית של הקבוצה למחלקות שקילות זרות. כל איבר שייך למחלקת שקילות אחת ויחידה, ואיחוד כל מחלקות השקילות הוא הקבוצה כולה.
דיאגרמת הסה: מפשטת את הייצוג הגרפי של יחסי סדר חלקי על ידי הסרת קשתות מיותרות (לולאות עצמיות וקשתות הנובעות מטרנזיטיביות) וסידור היררכי. היא אינה מספיקה כאשר הקבוצה אינסופית או כאשר היחס אינו יחס סדר חלקי.
דוגמה ליחס טרנזיטיבי בלבד: על הקבוצה {1,2,3}, היחס R = {(1,2), (2,3), (1,3)} הוא טרנזיטיבי. הוא אינו רפלקסיבי (אין (1,1) למשל), ואינו סימטרי (יש (1,2) אך אין (2,1)).
איברים מקסימליים/מינימליים וסופרמום/אינפימום: לקבוצה סדורה חלקית יכולים להיות מספר איברים מקסימליים/מינימליים, או אף לא אחד (אם הקבוצה אינסופית ואין חסמים). סופרמום ואינפימום לתת-קבוצה מסוימת אינם מובטחים תמיד, וגם אם קיימים, הם לא בהכרח שייכים לתת-הקבוצה עצמה.

מצאתם טעות או שחסר משהו?