יחס הופכי

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

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

• סימטריה. בפרט אם ${ℛ}$ סימטרי, אז ${{ℛ}}^{-1}={ℛ}$.

הוכחה: $x{{ℛ}}^{-1}y\iff y{ℛ}x\iff x{ℛ}y\iff y{{ℛ}}^{-1}x$.

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

הוכחה: $\mathrm{\forall }x,x{ℛ}x\Rightarrow \mathrm{\forall }x,x{{ℛ}}^{-1}x$.

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

הוכחה: $x{{ℛ}}^{-1}y\wedge y{{ℛ}}^{-1}z\Rightarrow y{ℛ}x\wedge z{ℛ}y\Rightarrow z{ℛ}x\Rightarrow x{{ℛ}}^{-1}z$.

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

הוכחה: מההגדרה $x{{ℛ}}^{-1}y\iff y{ℛ}x$ נובע כי $\mathrm{\neg }x{{ℛ}}^{-1}y\iff \mathrm{\neg }y{ℛ}x$, ולכן $\mathrm{\forall }x,\mathrm{\neg }x{ℛ}x\Rightarrow \mathrm{\forall }x,\mathrm{\neg }x{{ℛ}}^{-1}x$.

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

הוכחה: $x{{ℛ}}^{-1}y\wedge y{{ℛ}}^{-1}x\Rightarrow y{ℛ}x\wedge x{ℛ}y\Rightarrow x=y$ ולכן יש שימור של אנטי-סימטריה. עבור א-סימטריה: $x{{ℛ}}^{-1}y\wedge y{{ℛ}}^{-1}x\iff y{ℛ}x\wedge x{ℛ}y$ ולכן אם ${ℛ}$ א-סימטרי אז ${{ℛ}}^{-1}$ א-סימטרי.

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

• ההופכי של ההופכי הוא היחס עצמו: $({{ℛ}}^{-1}{)}^{-1}={ℛ}$. תכונה זו מאפשרת להפוך את כל התכונות לעיל מ-"אם ב${ℛ}$ אז ב${{ℛ}}^{-1}$" ל-"ב${ℛ}$ אם ורק אם ב${{ℛ}}^{-1}$".

הוכחה: לכל x,y - $x({{ℛ}}^{-1}{)}^{-1}y\iff y{{ℛ}}^{-1}x\iff x{ℛ}y$

• הפונקציה המתאימה לכל יחס את ההופכי שלו היא פונקציה שומרת הכלה: ${ℛ}\subseteq {𝒯}\iff {𝒯}\subseteq {ℛ}$.

הוכחה: לכל x,y - $x{{ℛ}}^{-1}y\Rightarrow y{ℛ}x\Rightarrow y{𝒯}x\Rightarrow x{{𝒯}}^{-1}y$ ולכן ${{ℛ}}^{-1}\subseteq {{𝒯}}^{-1}$.

• ההופכי מתפלג מעל החיתוך: $({ℛ}\cap {𝒯}{)}^{-1}={{ℛ}}^{-1}\cap {{𝒯}}^{-1}$.

הוכחה:לכל x,y - $x({ℛ}\cap {𝒯}{)}^{-1}y\iff y({ℛ}\cap {𝒯})x\iff y{ℛ}x\wedge y{𝒯}x\iff x{{ℛ}}^{-1}y\wedge x{{𝒯}}^{-1}y\iff x({{ℛ}}^{-1}\cap {{𝒯}}^{-1})y$.

• ההופכי מתפלג מעל האיחוד: $({ℛ}\cup {𝒯}{)}^{-1}={{ℛ}}^{-1}\cup {{𝒯}}^{-1}$.

הוכחה: לכל x,y - $x({ℛ}\cup {𝒯}{)}^{-1}y\iff y({ℛ}\cup {𝒯})x\iff y{ℛ}x\vee y{𝒯}x\iff x{{ℛ}}^{-1}y\vee x{{𝒯}}^{-1}y\iff x({{ℛ}}^{-1}\cup {{𝒯}}^{-1})y$.

• ההופכי להרכבת יחסים הוא הרכבת ההופכיים בסדר הפוך: $({ℛ}\circ {𝒯}{)}^{-1}={{𝒯}}^{-1}\circ {{ℛ}}^{-1}$.

הוכחה: לכל x,y - $x({ℛ}\circ {𝒯}{)}^{-1}y\iff y({ℛ}\circ {𝒯})x\iff \mathrm{\exists }z,y{ℛ}z\wedge z{𝒯}x\iff \mathrm{\exists }z,z{{ℛ}}^{-1}y\wedge x{{𝒯}}^{-1}z\iff x({{𝒯}}^{-1}\circ {{ℛ}}^{-1})y$.

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

דוגמאות

• לכל קבוצה $A$, היחס ההופכי ליחס $\subseteq$ על ${𝒫}(A)$ הוא $\supseteq$.
• לכל פונקציה חד-חד-ערכית ועל, היחס ההופכי הוא הפונקציה ההופכית.
• היחס ההופכי ליחס "קיימת פונקציה חד-חד-ערכית" בין קבוצות הוא היחס "קיימת פונקציה על".

ראו גם

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

יחס הופכי31899140Q1248241