מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים

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

יחסים ותכונותיהם הבסיסיות

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

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

תכונות יסוד של יחסים

הבנת התכונות הבאות היא קריטית לניתוח סוגי יחסים שונים:

רפלקסיביות (Reflexivity): יחס R על קבוצה A הוא רפלקסיבי אם לכל a ∈ A מתקיים (a,a) ∈ R. (כל איבר קשור לעצמו).
אי-רפלקסיביות (Irreflexivity): יחס R על קבוצה A הוא אי-רפלקסיבי אם לכל a ∈ A מתקיים (a,a) ∉ R. (אף איבר אינו קשור לעצמו).
סימטריות (Symmetry): יחס R על קבוצה A הוא סימטרי אם לכל a,b ∈ A, אם (a,b) ∈ R אז גם (b,a) ∈ R. (אם a קשור ל-b, אז b קשור ל-a).
אנטי-סימטריות (Antisymmetry): יחס R על קבוצה A הוא אנטי-סימטרי אם לכל a,b ∈ A, אם (a,b) ∈ R וגם (b,a) ∈ R, אז בהכרח a = b. (אם a קשור ל-b ו-b קשור ל-a, הם חייבים להיות אותו איבר).
טרנזיטיביות (Transitivity): יחס R על קבוצה A הוא טרנזיטיבי אם לכל a,b,c ∈ A, אם (a,b) ∈ R וגם (b,c) ∈ R, אז בהכרח (a,c) ∈ R. (אם a קשור ל-b ו-b קשור ל-c, אז a קשור ל-c).

סימטריות

אם יש חץ מ-a ל-b, חייב להיות חץ מ-b ל-a. דוגמה: "חבר של".

אנטי-סימטריות

אם יש חץ מ-a ל-b ומ-b ל-a, אז a=b. דוגמה: "קטן או שווה ל-".

הבחנה חשובה

יחס יכול להיות גם סימטרי וגם אנטי-סימטרי (למשל, יחס השוויון), או אף אחד מהם.

סוגי יחסים מיוחדים: יחסי שקילות וסדר חלקי

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

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

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

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

יחס סדר חלקי (Partial Order Relation): יחס R על קבוצה A הוא יחס סדר חלקי אם הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי.

קבוצה סדורה חלקית (Partially Ordered Set - Poset): קבוצה A יחד עם יחס סדר חלקי R עליה, מסומנת (A,R).

פונקציות ותכונותיהן

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

פונקציה (Function): יחס f מ-A ל-B הוא פונקציה אם לכל a ∈ A קיים b ∈ B יחיד כך ש-(a,b) ∈ f. מסומן f: A → B. A הוא התחום (Domain), B הוא הקו-דומיין (Codomain). טווח הפונקציה (Range) הוא קבוצת כל האיברים ב-B שיש להם מקור ב-A.

תכונות פונקציות

חד-חד-ערכית (Injective / One-to-one): פונקציה f: A → B היא חד-חד-ערכית אם לכל x₁, x₂ ∈ A, אם f(x₁) = f(x₂) אז x₁ = x₂. (לכל איבר בטווח יש לכל היותר מקור אחד).
על (Surjective / Onto): פונקציה f: A → B היא על אם לכל y ∈ B קיים x ∈ A כך ש-f(x) = y. (כל איבר בקו-דומיין הוא גם בטווח).
חד-חד-ערכית ועל (Bijective / One-to-one correspondence): פונקציה f: A → B היא חד-חד-ערכית ועל אם היא גם חד-חד-ערכית וגם על.

חד-חד-ערכית

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

על

כל איבר ב-B מקבל לפחות חץ אחד. אין איברים ב-B שאינם מקבלים חץ.

חד-חד-ערכית ועל

כל איבר ב-B מקבל בדיוק חץ אחד. זו התאמה מושלמת בין A ל-B.

הרכבת פונקציות ופונקציה הופכית

הרכבת פונקציות מאפשרת לבנות פונקציות מורכבות יותר. פונקציה הופכית קיימת רק עבור פונקציות ביג'קטיביות.

הרכבת פונקציות (Function Composition): בהינתן f: A → B ו-g: B → C, הרכבתן g ∘ f: A → C מוגדרת ע"י (g ∘ f)(x) = g(f(x)).

פונקציה הופכית (Inverse Function): אם f: A → B היא חד-חד-ערכית ועל, אז קיימת פונקציה הופכית יחידה f⁻¹: B → A כך שלכל y ∈ B, f⁻¹(y) = x אם ורק אם f(x) = y.

הבחנות חשובות וטעויות נפוצות

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

סימטריות מול אנטי-סימטריות: אלו אינן תכונות מנוגדות! יחס יכול לקיים את שתיהן (למשל, יחס השוויון), אף אחת מהן, או רק אחת מהן.
הוכחות קיום מול הוכחות לכל: בהוכחת תכונות כמו רפלקסיביות או טרנזיטיביות, יש להראות שהתכונה מתקיימת לכל האיברים הרלוונטיים. בהוכחת "על", יש להראות שקיים מקור לכל איבר בקו-דומיין.
הגדרת פונקציה: ודאו שכל איבר בתחום משויך לאיבר יחיד בקו-דומיין. אם לא, זהו יחס, אך לא פונקציה.
הוכחת חד-חד-ערכיות: הנקודה הקלאסית היא להתחיל בהנחה f(x₁) = f(x₂) ולסיים בהוכחה x₁ = x₂.

שאלות לדיון

תהי הקבוצה A = {1, 2, 3, 4} והיחס R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4)}. קבעו אילו מתכונות היסוד (רפלקסיביות, סימטריות, אנטי-סימטריות, טרנזיטיביות) R מקיים, ונמקו. האם R הוא יחס שקילות? האם הוא יחס סדר חלקי?
הגדירו יחס R על קבוצת המספרים השלמים Z כך ש-xRy אם ורק אם x ≡ y (mod 5). הוכיחו ש-R הוא יחס שקילות ומצאו את מחלקות השקילות שלו.
תהי הפונקציה f: R → R המוגדרת ע"י f(x) = x² + 1. האם f חד-חד-ערכית? האם f על? נמקו תשובותיכם. אם לא, ציינו תחום וקו-דומיין חלופיים עבורם f תהיה חד-חד-ערכית ועל.
כיצד ניתן להבחין בין יישומים מעשיים שבהם נשתמש ביחסי שקילות לבין יישומים שבהם נשתמש ביחסי סדר חלקי? תנו דוגמאות.

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

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

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