יחס הופכי

במתמטיקה, ובפרט בתורת הקבוצות, היחס ההופכי ליחס בינארי <math>\mathcal{R}</math> על קבוצה <math>A</math>, הוא היחס המסומן <math>\mathcal{R}^{-1}</math> ומוגדר על ידי <math>x\mathcal{R}^{-1}y\iff y\mathcal{R}x</math>. לדוגמה, היחס ההופכי ליחס <math><</math> על <math>\R</math> הוא היחס <math>></math>.

תכונות של יחסים המשתמרות ביחס ההופכי

• רפלקסיביות.

הוכחה: <math>\forall x,x\mathcal{R}x\,\Rarr\,\forall x,x\mathcal{R}^{-1}x</math>.

• אי-רפלקסיביות.

הוכחה: מההגדרה <math>x\mathcal{R}^{-1}y\iff y\mathcal{R}x</math> נובע כי <math>\neg x\mathcal{R}^{-1}y\iff\neg y\mathcal{R}x</math>, ולכן <math>\forall x,\neg x\mathcal{R}x\,\Rarr\,\forall x,\neg x\mathcal{R}^{-1}x</math>.

• סימטריה. בפרט אם <math>\mathcal{R}</math> סימטרי, אז <math>\mathcal{R}^{-1}=\mathcal{R}</math>.

הוכחה: <math>x\mathcal{R}^{-1}y\iff y\mathcal{R}x\iff x\mathcal{R}y\iff y\mathcal{R}^{-1}x</math>.

• אנטי-סימטריה וכן א-סימטריה.

הוכחה: <math>x\mathcal{R}^{-1}y\land y\mathcal{R}^{-1}x\,\Rarr\,y\mathcal{R}x\land x\mathcal{R}y\,\Rarr\, x=y</math> ולכן יש שימור של אנטי-סימטריה. עבור א-סימטריה: <math>x\mathcal{R}^{-1}y\land y\mathcal{R}^{-1}x\iff y\mathcal{R}x\land x\mathcal{R}y</math> ולכן אם <math>\mathcal{R}</math> א-סימטרי אז <math>\mathcal{R}^{-1}</math> א-סימטרי.

• טרנזיטיביות.

הוכחה: <math>x\mathcal{R}^{-1}y\land y\mathcal{R}^{-1}z\,\Rarr\,y\mathcal{R}x\land z\mathcal{R}y\,\Rarr\,z\mathcal{R}x\Rarr x\mathcal{R}^{-1}z</math>.

תכונות נוספות של היחס ההופכי

• ההופכי של ההופכי הוא היחס עצמו: <math>(\mathcal{R}^{-1})^{-1}=\mathcal{R}</math>. תכונה זו מאפשרת להפוך את כל התכונות לעיל מ"אם ב-<math>\mathcal{R}</math> אז ב-<math>\mathcal{R}^{-1}</math>" ל"ב-<math>\mathcal{R}</math> אם ורק אם ב-<math>\mathcal{R}^{-1}</math>".

הוכחה: לכל <math>x,y</math> מתקיים <math>x(\mathcal{R}^{-1})^{-1}y\iff y\mathcal{R}^{-1}x\iff x\mathcal{R}y</math>

• הפונקציה המתאימה לכל יחס את ההופכי שלו היא פונקציה שומרת הכלה: <math>\mathcal{R}\sube\mathcal{T}\iff\mathcal{T}\sube\mathcal{R}</math>.

הוכחה: לכל <math>x,y</math> מתקיים <math>x\mathcal{R}^{-1}y\,\Rarr\,y\mathcal{R}x\,\Rarr\,y\mathcal{T}x\,\Rarr\,x\mathcal{T}^{-1}y</math> ולכן <math>\mathcal{R}^{-1}\sube\mathcal{T}^{-1}</math>.

• ההופכי מתפלג מעל החיתוך: <math>(\mathcal{R}\cap\mathcal{T})^{-1}=\mathcal{R}^{-1}\cap\mathcal{T}^{-1}</math>.

הוכחה: לכל <math>x,y</math> מתקיים <math>x(\mathcal{R}\cap\mathcal{T})^{-1}y\iff y(\mathcal{R}\cap\mathcal{T})x\iff y\mathcal{R}x\land y\mathcal{T}x\iff x\mathcal{R}^{-1}y\land x\mathcal{T}^{-1}y\iff x(\mathcal{R}^{-1}\cap\mathcal{T}^{-1})y</math>.

• ההופכי מתפלג מעל האיחוד: <math>(\mathcal{R}\cup\mathcal{T})^{-1}=\mathcal{R}^{-1}\cup\mathcal{T}^{-1}</math>.

הוכחה: לכל <math>x,y</math> מתקיים <math>x(\mathcal{R}\cup\mathcal{T})^{-1}y\iff y(\mathcal{R}\cup\mathcal{T})x\iff y\mathcal{R}x\lor y\mathcal{T}x\iff x\mathcal{R}^{-1}y\lor x\mathcal{T}^{-1}y\iff x(\mathcal{R}^{-1}\cup\mathcal{T}^{-1})y</math>.

• ההופכי להרכבת יחסים הוא הרכבת ההופכיים בסדר הפוך: <math>(\mathcal{R}\circ\mathcal{T})^{-1}=\mathcal{T}^{-1}\circ\mathcal{R}^{-1}</math>.

הוכחה: לכל <math>x,y</math> מתקיים <math>x(\mathcal{R}\circ\mathcal{T})^{-1}y\iff y(\mathcal{R}\circ\mathcal{T})x\iff\exist z,y\mathcal{R}z\land z\mathcal{T}x\iff\exist z,z\mathcal{R}^{-1}y\land x\mathcal{T}^{-1}z\iff x(\mathcal{T}^{-1}\circ\mathcal{R}^{-1})y</math>.

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

דוגמאות

• לכל קבוצה <math>A</math>, היחס ההופכי ליחס <math>\sube</math> על <math>\mathcal{P}(A)</math> הוא <math>\supe</math>.
• לכל פונקציה חד-חד-ערכית ועל, היחס ההופכי הוא הפונקציה ההופכית.
• היחס ההופכי ליחס "קיימת פונקציה חד-חד-ערכית" בין קבוצות הוא היחס "קיימת פונקציה על".

ראו גם

• יחס (תורת הקבוצות)
• פונקציה הופכית

קישורים חיצוניים

• תורת הקבוצות על פי הרצאות של פרופ' ענר שלו, עמוד 11.