תורת הקבוצות/יחסים

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

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

הגדרות

הגדרה: בהינתן שתי קבוצות $A,B$ , תת-קבוצה של המכפלה הקרטזית ביניהם ${\mathcal {R}}\subseteq A\times B$ יקרא יחס בינארי בין $A$ ל-$B$ או פשוט יחס אם הקבוצות $A,B$ ברורות מההקשר.

ניתן כמובן גם להכליל את ההגדרה למקרה של $n$ קבוצות:

הגדרה: בהינתן הקבוצות $A_{1},\ldots ,A_{n}$ תת-קבוצה של המכפלה הקרטזית שלהם $R\subseteq A_{1}\times \cdots \times A_{n}$ ייקרא יחס.

כאשר ביחס בינארי $R\subseteq A\times B$ מתקיים כי $A=B$, נאמר בקיצור כי ${\mathcal {R}}$ הוא יחס על $A$.

סימון: כאשר ${\mathcal {R}}$ יחס בינארי ומתקיים כי $(a,b)\in {\mathcal {R}}$ אז לפעמים נקצר ונרשום: $a{\mathcal {R}}b$ .

הגדרה: בהינתן יחס בינארי בין $A$ ל-$B$

1. התחום של ${\mathcal {R}}$ הוא הקבוצה ${\text{Domain}}(R)={\Big \{}a\in A:(a,b)\in R{\Big \}}$
2. הטווח של ${\mathcal {R}}$ הוא הקבוצה ${\text{Range}}({\mathcal {R}})={\Big \{}b\in B:(a,b)\in R{\Big \}}$

דוגמאות

• יהיו $A=\{1,2,3\},B=\{a,b,c\}$ קבוצות. נגדיר יחס בין $A$ ל-$B$ על-ידי:

$${\mathcal {R}}_{1}={\Big \{}(a,1),(b,2),(c,3){\Big \}}$$

• בקבוצת המספרים הטבעיים $\mathbb {N}$ נוכל להגדיר את היחס "עוקב של" על-ידי:

$${\mathcal {R}}_{2}={\Big \{}(n+1,n):n\in \mathbb {N} {\Big \}}$$

(על הקורא לנסות לשכנע את עצמו שזוהי אכן הגדרה שמתאימה לאינטואיציה שלנו.)

• באופן דומה מוגדר היחס "מחלק של" במספרים השלמים כך:

$$|={\Big \{}(n_{1},n_{2})\in \mathbb {Z} ^{2}:\exists k\in \mathbb {Z} ,n_{1}k=n_{2}{\Big \}}$$

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

• בכל קבוצה $A$, ניתן להגדיר את היחס "שווה ל" כך:

$${\mathcal {R}}_{3}={\Big \{}(a,a):a\in A{\Big \}}$$

דוגמה אינטויטיבית אשר מאד עוזרת להבין את נושא היחסים:

• היחס שווה:
• בואו נדמיין לרגע שיש לנו שק המכיל בתוכו כדורים הממוספרים מ-1 עד 3.
• כעת נדמיין שיש לנו קופסא.
• כעת הוציאו משק הכדורים רק את הכדורים השווים לעצמם.
• כעת אתם תשאלו את עצמכם
• "האם 1 שווה ל-1?" כן, אז אתם תוציאו את הכדור 1 ותכניסו לקופסה. באותה מידה ניתן לומר ש-1 עומד ביחס השוויון עם 1. ולכתוב 1R1.
• "האם 2 שווה 2?" כן, אז אתם תוציאו את כדור 2. באותה מידה ניתן לאמר ש2 עומד ביחס השוויון עם 2. 2R2.
• "האם 3 שווה ל-3?" כן, אתם תוציאו את כדור 3. באותה מידה ניתן לומר ש-3 עומד ביחס השוויון עם 3. 3R3.
• כעת בתוך הקופסה, יהיו לנו 3 כדורים.
• ועל מכסה הקופסה נכתוב: {(1,1),(2,2)(3,3)} מכיוון שבקופסה למעשה יש רק את הזוגות העומדים ביחס - שווה.
• כלומר, הכנסנו לקופסא רק את הזוגות השווים לעצמם.

נשים לב שהיחס "שווה" הוא רפלקסיבי (reflect = שיקוף) מכיוון שכל כדור שיש בשק עומד ביחס עם עצמו. 1 עומד עם 1, כי 1 שווה ל-1. ולכן כתבנו (1,1) וכן הלאה.

• היחס גדול מ:
• כעת נדמיין שוב שק עם 3 כדורים הממוספרים מ-1 עד 3.
• כעת תגידו לי איזה כדור גדול מכדור אחר?
• האם 1 גדול מכדור אחר? לא. אז הוא לא ייצא מהשק.
• האם 2 גדול מכדור אחר בשק? כן, ממי? מ-1. כעת נוציא את 2, ונכתוב לעצמנו: 2 גדול מ-1. או פשוט 2R1. או פשוט (2,1).
• האם 3 גדול מכדור אחר בשק? כן, ממי? מ-1 ומ-2. כעת נוציא את 3, ונכתוב לעצמנו: 3 גדול מ-1. או 3R1. או פשוט (3,1).
• ונכתוב לעצמנו: 3 גדול מ-2. או 3R2. או פשוט (3,2).
• לבסוף על הקופסא שלנו נרשום את כל הזוגות שעמדו ביחס:
• {(2,1) (3,1) (3,2)} מכיוון שאלו הזוגות אשר קיימו את היחס גדול מ-.

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

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

יחס ${\mathcal {R}}\subseteq A\times A$ ייקרא:

• רפלקסיבי אם לכל אבר בקבוצה $a\in A$ מתקיים $a{\mathcal {R}}a$.

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

• אי-רפלקסיבי אם לכל אבר בקבוצה $a\in A$ לא מתקיים $a{\mathcal {R}}a$.

לדוגמא: היחס 'גדול מ-' הוא אי-רפלקסיבי בקבוצת המספרים הרציונליים, כיון שאף מספר אינו גדול מעצמו.

• קו-רפלקסיבי אם לכל זוג אברים בקבוצה $a,b\in A$ המקיים $a{\mathcal {R}}b$ מתקיים $a=b$.

לדוגמא: היחס 'שווה' הוא קו-רפלקסיבי בקבוצת המספרים הרציונליים (בעוד שהיחס 'בעל חֶזקה ריבועית שזהה לזו של' הוא קו-רפלקסיבי רק בקבוצת המספרים החיוביים – אך לא בקבוצת המספרים הרציונליים).

• סימטרי אם כל זוג אברים בקבוצה $a,b\in A$ מקיים $a{\mathcal {R}}b\iff b{\mathcal {R}}a$.

לדוגמא: היחס 'שווה' הוא סימטרי בקבוצת המספרים הרציונליים (אם $a=b$ אז $b=a$).

• א-סימטרי (או אנטי-סימטרי חזק) אם כל זוג אברים בקבוצה $a,b\in A$ המקיים $a{\mathcal {R}}b$ אינו מקיים $b{\mathcal {R}}a$.

לדוגמא: היחס 'גדול מ-' הוא א-סימטרי בקבוצת המספרים הרציונליים (אם $b<a$ אז לא מתקיים $a<b$). יחס כזה הוא אנטי-סימטרי חזק (וגם אי-רפלקסיבי).

• אנטי-סימטרי (או אנטי-סימטרי חלש) אם כל זוג אברים בקבוצה $a,b\in A$ המקיים $a{\mathcal {R}}b$ וגם $b{\mathcal {R}}a$ מקיים $a=b$.

לדוגמא: היחס 'גדול או שווה' הוא אנטי-סימטרי בקבוצת המספרים הרציונליים (אם $a\leq b$ וגם $b\leq a$ אז $a=b$).

• טרנזיטיבי אם לכל שלושה אברים בקבוצה $a,b,c\in A$ המקיימים $a{\mathcal {R}}b$ וגם $b{\mathcal {R}}c$ מתקיים $a{\mathcal {R}}c$.

לדוגמא: היחס 'קטן מ-' הוא טרנזיטיבי בקבוצת המספרים הרציונליים (אם $a<b$ וגם $b<c$ אזי $a<c$).

• אי-טרנזיטיבי אם לכל שלושה אברים בקבוצה $a,b,c\in A$ המקיימים $a{\mathcal {R}}b$ וגם $b{\mathcal {R}}c$ לא מתקיים $a{\mathcal {R}}c$.

לדוגמא: היחס 'עוקב של' הוא אי-טרנזיטיבי בקבוצת המספרים הרציונליים (אם $b=a+1$ וגם $c=b+1$ אז לא מתקיים $c=a+1$).

פעולות על יחסים

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

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

הפכיות

לכל יחס ${\mathcal {R}}\subseteq A\times B$, נגדיר את היחס ההפוך כך: $${\mathcal {R}}^{-1}={\Big \{}(b,a):a{\mathcal {R}}b{\Big \}}$$

הרכבה

אם ${\mathcal {R}}\subseteq A\times B$ ו-${\mathcal {T}}\subseteq B\times C$ הם יחסים, אז נגדיר את ההרכבה שלהם כך: ${\mathcal {T}}\circ {\mathcal {R}}={\Big \{}(a,c):\exists b,a{\mathcal {R}}b\land b{\mathcal {T}}c{\Big \}}$

צמצום

יהי ${\mathcal {R}}\subseteq A\times B$ ויהיו $C\subseteq A,B\subseteq D$. נגדיר את הצמצום של ${\mathcal {R}}$ ל-$C\times D$ כך: $${\mathcal {R}}|_{C\times D}={\Big \{}(x,y)\in C\times D:x{\mathcal {R}}y{\Big \}}={\mathcal {R}}\cap (C\times D)$$

יחסים מיוחדים

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

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

פונקציה

הגדרה: יחס בינארי ${\mathcal {R}}\subseteq A\times B$ יקרא פונקציה מ-$A$ ל-$B$ אם מתקיים:

1. אם $(a,b)\in {\mathcal {R}}$ וגם $(a,c)\in {\mathcal {R}}$ אזי $b=c$.
2. ${\text{Domain}}({\mathcal {R}})=A$

אם נרצה לדבר על פונקציה $f$ מ-$A$ ל-$B$ נסמן זאת $f:A\to B$, ולכל $x\in A$ נסמן $f(x)$ את ה-$y\in B$ היחיד המתאים ל-$x$.

דוגמאות

• נגדיר $f:\mathbb {N} \to \mathbb {N}$ על-ידי $f(n)=n+1$. נשים לב שבאותה מידה יכולנו לרשום:

$$f={\Big \{}(n,n+1):n\in \mathbb {N} {\Big \}}$$

• לכל קבוצה לא-ריקה $A$ ואבר בה $a\in A$ , נוכל להגדיר את הפונקציה הקבועה $c_{a}:A\to A$ המוגדרת על-ידי:

$$c_{a}(x)=a$$

יחס שקילות

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

הגדרה: יחס בינארי ${\mathcal {R}}$ ב-$A$ יקרא יחס שקילות אם הוא רפלקסיבי, סימטרי וטרנזיטיבי.

הערה: כשם שהאות $f$ היא סימון מקובל לפונקציה, כך גם הסימנים "~", "=" ועוד בסגנון, לעתים מסמלים יחס שקילות.

דוגמאות

• היחס ${\mathcal {R}}_{3}$ בדוגמאות לעיל, הוא יחס שקילות (על הקורא לוודא שאכן זה כך.)
• יחס הדמיון בין משולשים כפי שנלמד בתיכון, הוא יחס שקילות.
• נקבע מספר טבעי כלשהוא $k$ ונגדיר ב-$\mathbb {Z}$ את היחס

$$\equiv _{k}={\Big \{}(n_{1},n_{2}):k\,|\,(n_{1}-n_{2}){\Big \}}$$

יחסי סדר

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

הגדרה: יחס בינארי ${\mathcal {R}}$ ב-$A$ יקרא יחס סדר חלקי ב-$A$ אם הוא מקיים רפלקסיביות, אנטי-סימטריות וטרנזיטיביות. קבוצה $A$ עם יחס סדר חלקי ${\mathcal {R}}$, נקראת קבוצה סדורה חלקית או בקיצור, קס"ח.

דוגמאות

• יחס הסדר | במספרים השלמים הוא יחס סדר חלקי (על הקורא לוודא זאת.)
• היחס $\leq$ המוכר לכולנו מבית הספר, הוא יחס סדר חלקי במספרים הרציונליים.

כפי שניתן לראות מהדוגמה הראשונה, אם נסתכל ב-$3,5\in \mathbb {Z}$, אזי $3\nmid 5$ וגם $5\nmid 3$, מה שלא היינו מצפים היחס $\leq$ שאנחנו רגילים אליו מההתעסקות במספרים ממשיים. במקרה הזה, נאמר ש-3 ו-5 לא ניתנים להשוואה ביחס |.

הגדרה: בהינתן $A$ קס"ח על-ידי יחס הסדר $R$, אם עבור $a,b\in A$ מתקיים $aRb$ או $bRa$, אזי נאמר כי $a,b$ ניתנים להשוואה על-ידי ${\mathcal {R}}$.

הגדרה: בהינתן $A$ קס"ח על-ידי יחס הסדר ${\mathcal {R}}$, נאמר כי ${\mathcal {R}}$ הוא יחס שלם או יחס לינארי אם כל שני אברים ב-$A$ ניתנים להשוואה על-ידי ${\mathcal {R}}$. במקרה זה נכנה את $A$ קבוצה סדורה לינארית או בקיצור, קס"ל.

הפרק הקודם: קבוצת החזקה

יחסים

הפרק הבא: פונקציות