יחס (תורת הקבוצות)

במתמטיקה, יחס בינארי (רלציה) בין קבוצות A ו‑B הוא קבוצה של זוגות סדורים. הזוג הסדור הוא שני איברים בסדר קבוע, כך שהאיבר הראשון שייך ל‑A והשני ל‑B. יש גם יחסים n‑אריים, שהם קבוצות של n‑יות מכל אחת מהקבוצות A1,…,An. יחס n‑ארי על קבוצה A הוא יחס שבו כל הקבוצות הן A.

אם (a,b) שייך ל‑R אומרים a R b. שוויון, אי‑שוויון ופונקציות הן דוגמאות נפוצות ליחסים.

יחס R בין A ו‑B מוגדר פשוט כקבוצה R⊆A×B. יחס n‑ארי R בין A1,…,An הוא תת‑קבוצה של המכפלה ההדדית ∏Ai.

רפלקסיבי: לכל a ב‑A מתקיים a R a. לדוגמה, יחס השווה רפלקסיבי.

אי‑רפלקסיבי: לכל a ב‑A לא מתקיים a R a. יחס "קטן מ‑" הוא כזה.

קו‑רפלקסיבי: אם a R b אז מתקיים a=b. יחס השווה הוא קו‑רפלקסיבי.

סימטרי: אם a R b אז גם b R a. יחס השווה הוא סימטרי.

אנטי‑סימטרי: אם a R b וגם b R a אז a=b. יחס "קטן או שווה" מקיים זאת.

א‑סימטרי (אנטי‑סימטרי חזק): אם a R b אז לא מתקיים b R a. יחס "קטן מ‑" הוא דוגמה; יחס כזה גם אי‑רפלקסיבי.

טרנזיטיבי: אם a R b וגם b R c אז גם a R c. יחס "קטן מ‑" הוא טרנזיטיבי.

אי‑טרנזיטיבי: גם כש‑a R b ו‑b R c מתקיים, לא בהכרח a R c. יחס ה"עוקב של" (successor) הוא דוגמה.

הרכבה: אם R⊆A×B ו‑S⊆B×C, אפשר להגדיר T=R∘S= {(a,c): יש b כך ש‑a R b ו‑b S c}. זו הרחבה של חיבור פונקציות. הרכבת יחס רפלקסיבי או טרנזיטיבי נותנת יחס בעל אותה תכונה.

היחס ההופכי: ל‑R⊆A×B מגדירים R^{-1}⊆B×A על‑ידי החלפת המקומות של האיברים: R^{-1} = {(b,a): a R b}. הרכבה עם ההופכי או האיחוד שלהן מניבים יחס סימטרי.

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

מבנה קשור: לכל יחס בינארי על X מתאים "קומפלקס הסדר" של היחס. קומפלקס זה הוא כוויץ בדיוק כש‑R הוא יחס סדר.

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

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

רפלקסיבי: כל איבר קשור לעצמו. למשל השווה.

אי‑רפלקסיבי: אף איבר לא קשור לעצמו. "קטן מ" הוא כזה.

סימטרי: אם a קשור ל‑b אז גם b קשור ל‑a. שווה הוא כזה.

אנטי‑סימטרי: אם a קשור ל‑b וגם b קשור ל‑a אז הם זהים.

טרנזיטיבי: אם a קשור ל‑b ו‑b ל‑c אז גם a קשור ל‑c. "קטן מ" מקיים זאת.

חיבור (הרכבה): מחברים שני יחסים דרך קבוצה משותפת. זה כמו לחבר שתי פעולות.

היפוך: הופכים כל זוג (a,b) ל‑(b,a). זה היחס ההופכי.

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