Binär relation

Inom matematiken är en binär relation $R$ , mellan två mängder $X$ och $Y$ , en delmängd av den cartesiska produkten mellan $X$ och $Y$ :

R\subseteq X\times Y.

"Binär" betyder i detta sammanhang "tvåställig". Det finns även ternära (treställiga) relationer, kvaternära (fyrställiga) relationer och så vidare – som delmängder av cartesiska produkter av tre eller fler mängder – men dessa är sällan förekommande i "vanlig" matematik. Därför används ofta relation som synonymt med binär relation.

Ett element $x\in X$ är relaterat till ett element $y\in Y$ via relationen $R$ om det ordnade paret $(x,y)$ är ett element i mängden $R$ , det vill säga om $(x,y)\in R$ . Istället för att skriva $(x,y)\in R$ kan man skriva $xRy$ vilket utläses: ' $x$ är relaterat till $y$ via $R$ .'

Tre viktiga typer av binära relationer inom matematiken är ekvivalensrelationer, ordningsrelationer och avbildningar.

Ekvivalensrelationer

En ekvivalensrelation $R$ på en mängd $X$ är en delmängd av den cartesiska produkten $X\times X$ som besitter följande tre egenskaper:

(Reflexivitet) Varje element $x\in X$ är relaterat till sig själv: $xRx$
(Symmetri) Elementet $x$ är relaterat till elementet $y$ om och endast om elementet $y$ är relaterat till elementet $x$ : $xRy$ om och endast om $yRx$
(Transitivitet) Om $x$ är relaterad till $y$ , vilken i sin tur är relaterad till $z$ , så är $x$ relaterad till $z$ : $xRy\quad {\textrm {och}}\quad yRz\Longrightarrow xRz.$

Ekvivalensklassen $E_{x}$ , associerad med ett element $x\in X$ , är mängden av alla element $y\in X$ som är relaterade till $x$ :

$E_{x}=\{y\in X:xRy\}.$

Ekvivalensklasserna $E_{x}$ och $E_{y}$ associerade med två distinkta element $x\neq y$ är disjunkta mängder:

$x\neq y\Longrightarrow E_{x}\cap E_{y}=\emptyset .$

Vidare kan mängden $X$ skrivas som unionen av alla dessa ekvivalensklasser:

$X=\cup _{x\in X}E_{x}.$

Denna representation av en mängd är ofta förekommande inom matematiken: Exempelvis inom funktionalanalys är det vanligt att två element i ett $L^{p}$ -rum identifieras om de tillhör samma ekvivalensklass.

Ordningsrelationer

Partiell ordning

Huvudartikel: Partiellt ordnad mängd

En partiell ordningsrelation (partiell ordning) R – som vi för intuitionens skull betecknar med symbolen $\leq$ vilken utläses: "mindre än eller lika med" – på en mängd $X$ är en delmängd av den cartesiska produkten $X\times X$ som besitter följande tre egenskaper:

(Reflexivitet) Varje element $x\in X$ är relaterat till sig själv: $x\leq x$
(Antisymmetri) Om elementet $x$ är relaterat till elementet $y$ och om elementet $y$ är relaterat till elementet $x$ , så är $x=y$ : $x\leq y\quad {\textrm {och}}\quad y\leq x\Longleftrightarrow x=y$
(Transitivitet) Om $x$ är relaterad till $y$ , vilken i sin tur är relaterad till $z$ , så är $x$ relaterad till z: $x\leq y\quad {\textrm {och}}\quad y\leq z\Longrightarrow x\leq z.$

Paret $(X,\leq )$ säges vara en partiellt ordnad mängd.

Total ordning

Huvudartikel: Totalt ordnad mängd, se Linjär ordning

En total ordningsrelation (total ordning, linjär ordning) på en mängd $X$ är en partiell ordningsrelation, $\leq$ , som även besitter egenskapen att, för varje val av två element $x,y\in X$ , antingen är $x\leq y$ eller $y\leq x$ .

Paret $(X,\leq )$ säges vara en totalt ordnad mängd.

Välordning

En välordning-relation (välordning, god ordning(?)) på en mängd $X$ är en total ordningsrelation, $\leq$ , som även besitter egenskapen att varje icke-tom delmängd $A\subseteq X$ har ett unikt minsta element.

Paret $(X,\leq )$ säges vara en välordnad mängd.

Avbildningar

En avbildning av en mängd $X$ på en mängd $Y$ är en delmängd av den cartesiska produkten $X\times Y$ som besitter följande egenskap:

Varje element $x\in X$ är relaterat till ett unikt element $y\in Y$ .

För att göra associationen mellan $x$ och det motsvarande unika elementet $y\in Y$ tydlig, brukar man skriva

y=f(x).

Själva relationen, $f,\,$ mellan $X$ och $Y$ brukar skrivas

f:X\longrightarrow Y

och utläses 'f avbildar X på Y'. Avbildningar går även under namnet funktioner, men ofta reserverar man namnet funktion till en avbildning

f:X\longrightarrow \mathbb {C}

från en mängd $X$ till mängden av komplexa tal $\mathbb {C}$ , eller en delmängd av de komplexa talen. Följande är synonymer för avbildning: transformation, funktionsrelation, abstrakt funktion.

En avbildning,

f:X\longrightarrow Y,\,

associerar inte bara enskilda element i $X$ med enskilda element i $Y$ ; man kan även associera delmängder av $X$ med delmängder av $Y$ : En godtycklig delmängd $A\subseteq X$ associeras med bildmängden

f(A)=\{y\in Y:\exists \,x\in A,\;y=f(x)\}.

Detta utläses som: 'f(A) är lika med mängden av alla element y i Y, som är sådana att det existerar ett element x i A, med egenskapen att y = f(x).' (Se artikeln om predikatlogik för mer information om den så kallade existenskvantorn

\exists

.)

Mängden $X$ kallas för avbildningens

f:X\longrightarrow Y

definitionsmängd och den speciella bildmängden

f(X)\subseteq Y

kallas avbildningens värdemängd.

Det är även möjligt att associera delmängder av $Y$ med delmängder av $X$ : En godtycklig delmängd $M\subseteq Y$ associeras med den så kallade urbilden

f^{-1}(M)=\{x\in X:f(x)\in M\}=\{x\}_{f(x)\in M}.

Notera att dessa två sätt att associera delmängder inte är likvärdiga: Om vi låter $A\subseteq X$ vara en en-punktsmängd, $A=\{a\}$ , så är bildmängden

f(A)=\{f(x)\}_{x\in A}=\{f(a)\}

också en en-punktsmängd; definitionen av begreppet avbildning tvingar fram denna situation. Om vi å andra sidan låter $M\subseteq Y$ vara en en-punktsmängd, $M=\{m\}$ , så är dess urbild

f^{-1}(M)=\{x\in X:f(x)=m\}

inte nödvändigtvis en en-punktsmängd; det kan mycket väl finnas två eller fler element i $X$ som avbildas på elementet $m\in Y$ .

Bild över en injektiv linjär funktion

f:[0,1]\longrightarrow [0,1].

I de fall då urbilden av en en-punktsmängd är en en-punktsmängd, säger man att avbildningen $f\,$ är injektiv: Varje element $m\in f(X)$ i värdemängden associeras då med endast ett element $x\in X$ och vice versa. Ett annat sätt att uttrycka detta på är att säga att avbildningen

f:X\longrightarrow f(X)

är bijektiv. (Notera att vi har ersatt mängden Y med bildmängden f(X).)

I de fall då avbildningens

f:X\longrightarrow Y

värdemängd $f(X)$ sammanfaller med mängden $Y$ , det vill säga då

Y=f(X),\,

säger man att avbildningen

f:X\longrightarrow Y

är surjektiv.

Bild över en surjektiv linjär funktion

f:[0,1]\longrightarrow [0,1].

Den praktiska innebörden av begreppen injektiv och surjektiv

Att en avbildning $f:X\longrightarrow Y$ är surjektiv innebär att det för varje element $y\in Y$ existerar minst en lösning till ekvationen $y=f(x)$ .

Att en avbildning $f:X\longrightarrow Y$ är injektiv innebär att om ekvationen $y=f(x)$ har en lösning, så är den unik.

Om avbildningen $f:X\longrightarrow Y$ är bijektiv – både injektiv och surjektiv – så existerar det för varje element $y\in Y$ en unik lösning $x\in X$ till ekvationen $y=f(x)$ .

I vardagligt språk har egentligen relation samma betydelse som den formaliserade inom mängdteori nedan. Oftast är det relationer mellan människor som avses, se till exempel släktskapsrelation. Ibland används ordet också som synonym till mellanmänskliga förhållanden eller mer allmänt om sådant som rör kärlek, samlevnad och parbildningar mellan människor.

Mängdteori

I mängdteori menas med relation en mängd av ordnade par, det vill säga ett tvåställigt predikat. Man tänker sig att objekten i de ingående paren har en viss relation till varandra. Om man till exempel från en mängd av människor plockar ut alla par (x, y) där x är far till y och samlar dessa i en mängd har man bildat relationen far. Om relationen är en tom mängd finns det inga par av objekt som står i detta förhållande till varandra. Ett specialfall av relation, när det för varje x bara finns ett element y, är funktion.

I en mer generell betydelse kan relation också vara n-ställiga predikat (med n > 1). Ettställiga predikat kallas dock normalt egenskaper och inte relationer.

Exempel på tvåställiga relationer i talteori:

Tvåställiga relationer kan klassificeras efter huruvida de har följande egenskaper:

En relation som är reflexiv, symmetrisk och transitiv är en ekvivalensrelation.
En relation som är reflexiv, antisymmetrisk och transitiv är en partialordning, se "partiellt ordnad mängd".