יחס טרנזיטיבי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

באופן פורמלי יחס R הוא טרנזיטיבי אם לכל a,b,c המקיימים aRb ו-bRc מתקיים גם aRc.

מבנה[עריכת קוד מקור | עריכה]

לכל יחס טרנזיטיבי ורפלקסיבי R על קבוצה X יש יחס שקילות \ \equiv ויחס סדר חלש \ \leq על מרחב המנה \ X/\!\equiv, כך ש-\ xRy אם ורק אם \ [x]\leq [y]. יחס השקילות הוא החיתוך \ \equiv = R \cap R^{-1}.

תיאור דומה אפשר לתת לכל יחס טרנזיטיבי, בלי להניח רפלקסיביות: לכל יחס טרנזיטיבי R על קבוצה X יש יחס שקילות \ \equiv, יחס סדר חלש \ \leq על מרחב המנה \ X/\!\equiv, ותת-קבוצה \ X_0 \subseteq X שכל אבריה סינגלטונים של \ \equiv, כך ש-\ xRy אם ורק אם \ [x]\leq [y] וכן (\ x\neq y או \ x=y \not \in X_0).

הסגור הטרנזיטיבי[עריכת קוד מקור | עריכה]

כל יחס R ניתן להשלים ליחס טרנזיטיבי, שהוא היחס הטרנזיטיבי המינימלי המכיל את R. ההשלמה הזו נקראת הסגור הטרנזיטיבי של היחס המקורי ומסומנת \ R^{tr}. את הסגור הטרנזיטיבי של היחס R ניתן לקבל כחיתוך כל היחסים הטרנזיטיביים שמכילים את R (כיוון שהיחס המלא \,X\times X הוא טרנזיטיבי - חיתוך זה אינו ריק) או לחלופין על ידי ההגדרה הבאה:

לכל שני איברים x, y מתקיים: \ x R^{tr} y אם ורק אם קיימת שרשרת סופית של איברים \ x=x_0 R x_1 R \dots R x_n=y.

או באופן שקול:

\ R^{tr} = \bigcup_{n\isin\mathbb{N}} R^n

כלומר איחוד כל ההרכבות החוזרות של היחס על עצמו.

לדוגמה, יחס העקיבה המוגדר על המספרים הטבעיים: x עוקב ל-y אם x=y+1, אינו טרנזיטיבי (1 הוא עוקב של 0, ו-2 עוקב של 1 אך 2 אינו עוקב של 0); הסגור הטרנזיטיבי שלו הוא היחס < ("גדול מ-").

ראו גם[עריכת קוד מקור | עריכה]