הצגת המקור של הדף "יחס (תורת הקבוצות)"

{{סימון מתמטי}}
ב[[מתמטיקה]], ובפרט ב[[תורת הקבוצות]], '''יחס''' '''בינארי''' או '''רלציה''' בין קבוצות כלשהן <math>A,B</math> הוא קבוצה של [[זוג סדור|זוגות סדורים]] של איברים, כך שהאיבר הראשון בכל זוג שייך ל-<math>A</math> והשני ל-<math>B </math>. קיימים גם יחסים <math>n</math>-אריים, שהם קבוצות של <math>n</math>-יות מקבוצות נתונות <math>A_1,\ldots,A_n</math>. יחס n-ארי על הקבוצה A הוא יחס n-ארי שבו הקבוצות <math>A_1,\ldots,A_n</math> שוות כולן ל-A.

אם <math>(a,b)\in\mathcal{R}</math> נאמר כי "<math>a</math> עומד ביחס עם <math>b</math>" ונסמן <math>a\mathcal{R}b</math>.

[[שוויון (מתמטיקה)|שוויון]], [[אי-שוויון (מתמטיקה)|אי-שוויון]], וכל [[פונקציה]] במשתנה אחד או יותר, כולם דוגמאות ליחסים.

==הגדרה פורמלית==
יחס <math>\mathcal{R}</math> בין הקבוצות <math>A,B</math> הוא קבוצה המקיימת <math>\mathcal{R}\sube A\times B</math>.

יחס <math>n</math>-ארי <math>\mathcal{R}</math> בין הקבוצות <math>A_1,\ldots,A_n</math> הוא תת-קבוצה <math>\mathcal{R}\sube\prod_{i=1}^nA_i</math>.

==תכונות של יחסים==
יחס <math>\mathcal{R}\sube A\times A</math> ייקרא:
*'''[[יחס רפלקסיבי|רפלקסיבי]]''' אם לכל איבר בקבוצה <math>a\in A</math> '''מתקיים''' <math>a\mathcal{R}a</math>.
:לדוגמה: היחס 'שווה' הוא רפלקסיבי בקבוצת המספרים הרציונליים, כיון שכל מספר שווה לעצמו.
:*'''אי-רפלקסיבי''' אם לכל איבר בקבוצה <math>a\in A</math> '''לא מתקיים''' <math>a\mathcal{R}a</math>.
::לדוגמה: היחס 'קטן מ-' הוא אי-רפלקסיבי בקבוצת המספרים הרציונליים, כיון שאף מספר אינו קטן מעצמו.
:*'''קו-רפלקסיבי''' אם לכל זוג איברים בקבוצה <math>a,b\in A</math> המקיים <math>a\mathcal{R}b</math> '''מתקיים''' <math>a=b</math>.
::לדוגמה: היחס 'שווה' הוא קו-רפלקסיבי בקבוצת המספרים הרציונליים (בעוד שהיחס 'בעל חֶזקה ריבועית שזהה לזו של' הוא קו-רפלקסיבי רק בקבוצת המספרים החיוביים – אך לא בקבוצת המספרים הרציונליים).
*'''[[יחס סימטרי|סימטרי]]''' אם כל זוג איברים בקבוצה <math>a,b\in A</math> '''מקיים''' <math>a\mathcal{R}b\iff b\mathcal{R}a</math>.
:לדוגמה: היחס 'שווה' הוא סימטרי בקבוצת המספרים הרציונליים (אם <math>a=b</math> אז <math>b=a</math>).
:*'''[[יחס אנטי-סימטרי|אנטי-סימטרי]]''' (או '''אנטי-סימטרי חלש''') אם כל זוג איברים בקבוצה <math>a,b\in A</math> המקיים <math>a\mathcal{R}b</math> וגם <math>b\mathcal{R}a</math> '''מקיים <math>a=b</math>'''.
::לדוגמה: היחס 'קטן או שווה' הוא אנטי-סימטרי בקבוצת המספרים הרציונליים (אם <math>a\le b</math> וגם <math>b\le a</math> אז <math>a=b</math>).
:*'''א-סימטרי''' (או '''אנטי-סימטרי חזק''') אם כל זוג איברים בקבוצה <math>a,b\in A</math> המקיים <math>a\mathcal{R}b</math> '''אינו מקיים''' <math>b\mathcal{R}a</math>.
::לדוגמה: היחס 'קטן מ-' הוא א-סימטרי בקבוצת המספרים הרציונליים (אם <math>a<b</math> אז לא מתקיים <math>b<a</math>). יחס כזה הוא אנטי-סימטרי חזק (וגם אי-רפלקסיבי).
*'''[[יחס טרנזיטיבי|טרנזיטיבי]]''' אם לכל שלושה איברים בקבוצה <math>a,b,c\in A</math> המקיימים <math>a\mathcal{R}b</math> וגם <math>b\mathcal{R}c</math> '''מתקיים''' <math>a\mathcal{R}c</math>.
:לדוגמה: היחס 'קטן מ-' הוא טרנזיטיבי בקבוצת המספרים הרציונליים (אם <math>a<b</math> וגם <math>b<c</math> אזי <math>a<c</math>).
:*'''אי-טרנזיטיבי''' אם לכל שלושה איברים בקבוצה <math>a,b,c\in A</math> המקיימים <math>a\mathcal{R}b</math> וגם <math>b\mathcal{R}c</math> '''לא מתקיים''' <math>a\mathcal{R}c</math>.
::לדוגמה: היחס 'עוקב של' הוא אי-טרנזיטיבי בקבוצת המספרים הרציונליים (אם <math>b=a+1</math> וגם <math>c=b+1</math> אז לא מתקיים <math>c=a+1</math>).
*'''[[יחס שקילות]]''' אם <math>\mathcal{R}</math> הוא רפלקסיבי, סימטרי וטרנזיטיבי.
*'''[[סדר חלקי|יחס סדר]]''' אם <math>\mathcal{R}</math> הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי.

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

==דוגמאות ליחסים==
מושג היחס מהווה אבן יסוד להגדרת מושגים בסיסיים רבים במתמטיקה:
*[[פונקציה]] <math>f</math> היא סוג של יחס, המאופיין על ידי התכונות חד-ערכיות: <math>(x,y)\in f\land(x,z)\in f\Rarr y=z</math> וקיום התאמה לכל איבר בקבוצה: <math>\forall x\in X\,\exists y\in Y:(x,y)\in f</math>.
*[[פעולה בינארית]] היא סוג של יחס (זוהי למעשה פונקציה מאוסף הזוגות הסדורים של קבוצה מסוימת אליה עצמה).
*[[סדר חלקי]] (מכונה גם "'''סדר חלקי חלש'''" או "'''סדר חלש'''", ומסומן בדרך כלל ב-<math>\le</math>) הוא יחס רפלקסיבי, אנטי-סימטרי וטרנזיטיבי.
**[[סדר מלא]] הוא סדר חלקי אשר מקיים את תכונת ההשוואה, כלומר לכל <math>a,b</math> בקבוצה הסדורה חלקית <math>(A,\le)</math> מתקיים או <math>a\le b</math> או <math>b\le a</math>.
*[[יחס שקילות]] הוא יחס רפלקסיבי, סימטרי וטרנזיטיבי. יחס שקילות משרה [[חלוקה (תורת הקבוצות)|חלוקה]] על הקבוצה עליה הוא מוגדר, למחלקות שקילות על ידי ההגדרה ששני איברים יהיו באותה [[מחלקת שקילות]], [[אם ורק אם]] הם עומדים ביחס.
*היחס "צאצא ביולוגי", הוא דוגמה ליחס אי-רפלקסיבי (אדם אינו צאצא של עצמו), א-סימטרי (אם אדם א' הוא צאצאו של אדם ב' אז ב' '''אינו''' צאצאו של א') וטרנזיטיבי (אם אדם א' הוא צאצאו של אדם ב' וב' בתורו הוא צאצא של ג', אז א' גם הוא צאצא של ג').

==פעולות על יחסים==
'''הרכבת יחסים''' – לכל שני יחסים <math>\mathcal{R}\sube A\times B,S\sube B\times C</math> ניתן להגדיר יחס שלישי <math>T\sube A\times C</math> כהרכבה של שניהם:
:<math>T=\mathcal{R}\circ S=\Big\{(a,c):\exist b\in B,\,a\mathcal{R}b\land bSc\Big\}</math>
לפי הגדרה זו – [[הרכבת פונקציות]] היא למעשה [[מקרה פרטי]] של הרכבת יחסים. הרכבת יחסים רפלקסיביים או טרנזיטיביים היא רפלקסיבית או טרנזיטיבית בהתאמה.

'''[[יחס הופכי|היחס ההופכי]]''' – עבור היחס <math>\mathcal{R}\sube A\times B</math> נגדיר את היחס ההפוך <math>\mathcal{R}^{-1}\sube B\times A</math> על ידי היפוך הזוגות הסדורים:
:<math>\mathcal{R}^{-1}=\bigl\{(b,a):a\mathcal{R}b\bigr\}</math>
הרכבת יחס עם היחס ההופכי, כמו גם איחודם, מניבה יחס סימטרי.

כל יחס <math>\mathcal{R}</math> על קבוצה <math>A</math> ניתן להשלים באופן מינימלי ליחס רפלקסיבי, סימטרי או טרנזיטיבי על ידי לקיחת החיתוך של אוסף כל היחסים בעלי אותה תכונה שמכילים אותו. כיוון שתכונות אלו נשמרות תחת החיתוך, הקבוצה המתקבלת, המכונה ה'''סגור''' של <math>\mathcal{R}</math> ביחס לתכונה המבוקשת (רפלקסיביות, סימטריות או טרנזיטיביות), היא היחס המינימלי שמכיל את <math>\mathcal{R}</math> ומקיים את אותה תכונה.

לכל יחס בינארי <math>\mathcal{R}</math> על קבוצה <math>X</math> מתאים '''קומפלקס הסדר''' של היחס: זהו [[קומפלקס (קומבינטוריקה)|קומפלקס]] שהתאים שלו הם כל תת-הקבוצות של <math>X</math> שהצמצום של <math>\mathcal{R}</math> אליהן הוא יחס סדר חלש. קומפלקס הסדר הוא [[מרחב כוויץ|כוויץ]] אם ורק אם <math>\mathcal{R}</math> הוא יחס סדר.

==ראו גם==
*[[תורת הקבוצות - מונחים]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
*{{אנציקלופדיה למתמטיקה|Binary_relation}}

{{תורת הקבוצות}}

[[קטגוריה:יחסים מתמטיים|*]]
[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:תורת הקבוצות]]