אשנב למתמטיקה

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

הגדרת יחס ותכונותיו היסודיות

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

יחס בינארי: יהיו A ו-B קבוצות. יחס R מ-A ל-B הוא תת-קבוצה של A × B. אם R הוא יחס מ-A ל-A, נאמר ש-R הוא יחס על A. נסמן (a,b) ∈ R גם כ-aRb.

ליחסים יש תכונות מפתח המאפיינות אותם:

רפלקסיביות: יחס R על קבוצה A הוא רפלקסיבי אם לכל a ∈ A מתקיים aRa. (כל איבר מתייחס לעצמו).

דוגמה: יחס השוויון (=) על קבוצת המספרים השלמים הוא רפלקסיבי, כי לכל מספר x, מתקיים x=x.
סימטריות: יחס R על קבוצה A הוא סימטרי אם לכל a, b ∈ A, אם aRb אז bRa. (אם a קשור ל-b, אז b קשור ל-a).

דוגמה: יחס "הוא אח של" על קבוצת האנשים הוא סימטרי (אם אורי הוא אח של דני, אז דני הוא אח של אורי).
טרנזיטיביות: יחס R על קבוצה A הוא טרנזיטיבי אם לכל a, b, c ∈ A, אם aRb ו-bRc אז aRc. (אם a קשור ל-b ו-b קשור ל-c, אז a קשור ל-c).

דוגמה: יחס "קטן מ-" (<) על קבוצת המספרים השלמים הוא טרנזיטיבי (אם x
אנטי-סימטריות: יחס R על קבוצה A הוא אנטי-סימטרי אם לכל a, b ∈ A, אם aRb ו-bRa אז a=b. (הקשר יכול להתקיים בשני הכיוונים רק אם האיברים זהים).

דוגמה: יחס "קטן או שווה ל-" (≤) על קבוצת המספרים השלמים הוא אנטי-סימטרי (אם x ≤ y ו-y ≤ x, אז x=y).

יחסי שקילות ומחלקות שקילות

יחסי שקילות הם סוג מיוחד של יחסים המאפשרים לנו לקבץ איברים "שווים" זה לזה בהיבט מסוים.

יחס שקילות: יחס R על קבוצה A המקיים את שלוש התכונות הבאות: רפלקסיביות, סימטריות וטרנזיטיביות.

יחס שקילות מחלק את הקבוצה לתת-קבוצות זרות הנקראות מחלקות שקילות.

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

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

קבוצת מנה: בהינתן יחס שקילות R על קבוצה A, קבוצת המנה, המסומנת A/R, היא קבוצת כל מחלקות השקילות של R. כלומר, A/R = {[a] | a ∈ A}.

מחיצות של קבוצה

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

מחיצה של קבוצה: מחיצה של קבוצה A היא אוסף P של תת-קבוצות לא ריקות של A, {A_i | i ∈ I}, המקיים את התנאים הבאים:

איחוד כל התת-קבוצות הוא הקבוצה A: ∪_i∈I A_i = A.
התת-קבוצות זרות בזוגות: לכל i ≠ j, A_i ∩ A_j = ∅.

התת-קבוצות A_i נקראות "חלקים" או "בלוקים" של המחיצה.

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

יחסי סדר חלקי ואיברי מינימום/מקסימום

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

יחס סדר חלקי: יחס R על קבוצה A המקיים את שלוש התכונות הבאות: רפלקסיביות, אנטי-סימטריות וטרנזיטיביות. קבוצה עם יחס סדר חלקי נקראת קבוצה סדורה חלקית (Poset).

דוגמה: יחס "מוכל או שווה" (⊆) על קבוצת החזקה של קבוצה נתונה הוא יחס סדר חלקי.

ביחסי סדר חלקי, לא כל זוג איברים חייב להיות בר-השוואה. איברים שאינם ניתנים להשוואה נקראים "בלתי ניתנים להשוואה".

ביחסי סדר חלקי, אנו מבחינים בין סוגים שונים של איברים "קיצוניים":

איבר מינימלי

איבר a בקבוצה סדורה חלקית (A, R) הוא איבר מינימלי אם אין איבר b ∈ A שונה מ-a כך ש-bRa. ייתכנו מספר איברים מינימליים.

איבר מקסימלי

איבר a בקבוצה סדורה חלקית (A, R) הוא איבר מקסימלי אם אין איבר b ∈ A שונה מ-a כך ש-aRb. ייתכנו מספר איברים מקסימליים.

איבר מינימום (ראשון)

איבר a בקבוצה סדורה חלקית (A, R) הוא איבר מינימום אם לכל b ∈ A מתקיים aRb. אם קיים, איבר מינימום הוא יחיד, והוא בהכרח איבר מינימלי.

איבר מקסימום (אחרון)

איבר a בקבוצה סדורה חלקית (A, R) הוא איבר מקסימום אם לכל b ∈ A מתקיים bRa. אם קיים, איבר מקסימום הוא יחיד, והוא בהכרח איבר מקסימלי.

שאלות לדיון

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

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

סימטריות מול אנטי-סימטריות: סימטריות דורשת שאם aRb אז bRa. אנטי-סימטריות דורשת שאם aRb ו-bRa אז a=b. יחס "חבר של" הוא סימטרי. יחס "קטן או שווה" הוא אנטי-סימטרי.
פישוט קבוצה באמצעות יחס שקילות: יחס שקילות מקבץ איברים "זהים" או "שקולים" למחלקות שקילות. במקום להתייחס לכל איבר בנפרד, ניתן להתייחס למחלקות השקילות כאל יחידות חדשות, ובכך "לפשט" את הקבוצה המקורית. לדוגמה, יחס שקילות "בעל אותו צבע" על קבוצת כדורים יחלק את הכדורים למחלקות לפי צבעם.
יחס שקילות ויחס סדר חלקי בו-זמנית: יחס כזה חייב להיות רפלקסיבי, טרנזיטיבי, סימטרי ואנטי-סימטרי. התנאים סימטריות ואנטי-סימטריות יחד גוררים שאם aRb, אז bRa (מסימטריות), ואז a=b (מאנטי-סימטריות). לכן, היחס היחיד שיכול לקיים את שניהם הוא יחס השוויון (=), שבו aRb מתקיים רק כאשר a=b.
דוגמה לקבוצה סדורה חלקית עם מספר איברים מינימליים ללא איבר מינימום: קחו את הקבוצה A = {2, 3, 4, 6, 12} עם יחס החלוקה '|' (x|y אם x מחלק את y). האיברים המינימליים הם 2 ו-3, מכיוון שאין איבר אחר בקבוצה שמחלק אותם. אין איבר מינימום, כי אין איבר יחיד שמחלק את כל שאר האיברים בקבוצה (לדוגמה, 2 לא מחלק את 3).

Spotted an error or something missing?