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

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

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

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

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

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

כל יחס 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); הסגור הטרנזיטיבי שלו הוא היחס < ("גדול מ-").

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