Om mängden $X$ innehålller ändligt många element så kan man beskriva relationen $W\subseteq X\times X$ som en graf i vilken elementen i $X$ är grafens noder och det finns en båge från nod $x$ till nod $y$ om och endast om $[x,y]\in W$.
Till exempel på följande sätt:

Relationen är {[4,2], [4,3], [5,1], [5,5], [5,6]}

Du kan lägga till eller ta ort bågar (dvs. element i relationen) genom att först klicka på bågens startnod och sedan på dess ändnod.

I en icke-riktad graf gör man inte skillnad på bågens start- och ändnod.

En relation i en mängd med ändligt många element kan framställas som en riktad graf men om det finns oändligt många element i mängden är det vanligtvis inte ett fungerande alternativ.

Till exempel $W=\{ [x,y] \,:\, x,\, y \in \R,\,\, x < y\}$ är en relation i mängden $\R$ och därför, som alla relationer i $\R$, en delmängd av planet $\R^2$. Men när man talar om den här relationen "mindre än" så avser man vanligen (som i många andra fall) ett predikat $M(x,y)$, som är sant då $[x,y]\in W$, dvs. då $x< y$ (och då lönar det sig förstås att istället för $M(x,y)$ skriva $x< y$).

 

Relationen $W$ i mängden $X$ är

• reflexiv ifall $[x,x]\in W$för alla $x\in X$.
• symmetrisk ifall $[x,y]\in W \to [y,x]\in W$ för alla $x$ och $y\in X$.
• transitiv ifall $[x,y]\in W \And [y,z]\in W \to [x,z]\in W$ för alla $x$, $y$ och $z\in X$.
• antisymmetrisk ifall $[x,y]\in W \And x\neq y \to [y,x]\notin W$ (dvs. $[x,y]\in W\And [y,x]\in W\to x=y$) för alla $x$ och $y\in X$.
• asymmetrisk ifall $[x,y]\in W \to [y,x]\notin W$ för alla $x$ och $y\in X$.
• total ifall $[x,y]\in W \Or [y,x]\in W$ för alla $x$ och $y\in X$.

Dessutom säger vi att $W$ är en

• ekvivalensrelation ifall $W$ är reflexiv, symmetrisk och transitiv,
• partiell ordning ifall $W$ är reflexiv, antisymmetrisk och transitiv,
• fullständig ordning (eller linjär ordning) ifall $W$ är en partiell ordning och total,
• välordning ifall $W$ är en fullständig ordning och i varje icke-tom delmängd av $X$ finns ett minsta element.

Ofta skriver man $xWy$ i stället för $[x,y]\in W$, till exempel $x\prec y$ och inte $[x,y]\in \prec$.

Låt $X$ vara en (icke-tom) mängd och $\mathcal P(X)$ mängden av alla dess delmängder (den sk. potensmängden). I mängden $\mathcal P(X)$ har vi relationen $\subseteq$: $A\subseteq B$ om och endast om $A$ är en delmängd av $B$. Den här relationen är en partiell ordning eftersom den är

• reflexiv: $A\subseteq A$,
• antisymmetrisk: Om $A\subseteq B$ och $A\neq B$ så finns det ett element $x\in B$ så att $x\notin A$ och då gäller $B\not\subseteq A$,
• transitiv: Om $A\subseteq B$ och $B\subseteq C$ så är varje element i $A$ ett element i $B$ och eftersom varje element i $B$ är ett element i $C$ så är också varje element i $A$ ett element i $C$ så att $A\subseteq C$.

Dessutom har den här partiella ordningen också den egenskapen att ifall $A$, $B\in \mathcal P(X)$ så finns det en minsta övre gräns för mängderna $A$ och $B$, dvs. en mängd $C$ sådan att $A\subseteq C$, $B\subseteq C$ ($C$ är en övre gräns) och ifall $A\subseteq D$ och $B\subseteq D$ så gäller $C\subseteq D$ (det finns ingen "mindre" övre gräns). Det är klart att $C=A\cup B$. på motsvarande sätt finns det en största övre gräns som (naturligtvis?) är $A\cap B$.

Ifall $X$ är en icke-tom mängd och $\sim$ är en ekvivalensrelation i mängden $X$, så delar den mängden $X$ i delmängder $Y_j\neq \emptyset$, $j\in J$ som kallas ekvivalensklasser så att

• $\cup_{j\in J} Y_j=X$,
• $Y_j\cap Y_k=\emptyset$ ifall $j\neq k$,
• $a\sim b \leftrightarrow$ $a$ och $b$ hör till samma mängd $Y_j$.

Ofta användar man sig av en ekvivalensrelation så att två element som är ekvivalenta (dvs. paret bildat av dem hör till relationen $\sim$) är "desamma", så att man istället för mängden $X$ behandlar mängden $\set{Y_j\mid j\in J}$, vars element är ekvivalensklasser.

Exempel: Heltal som ekvivalensklasser [+]

  

Det är (i de flesta fall) klart vad man avser med talet $2$ men när man talar om uttrycket $x+3$ så är det inte nödvändigtvis klart om man avser den funktion, som avbildar $x$ på $x+3$ eller värdet av den här funktionen i punkten $x$. Om man avser funktionen och inte värdet så kan man skriva
$x\mapsto x+3$
@(x)x+2
function(x){return x+3;}
lambda([x],x+3);
eller något annat motsvarande.

Funktionen $f:X\to Y$ är en

• injektion ifall $f(x_1)=f(x_2) \to x_1=x_2$ för alla $x_1,\, x_2\in X$,
• surjektion ifall för varje $y\in Y$ finns ett $x\in X$ så att, $f(x)=y$,
• bijektion om $f$ är både en injektion och en surjektion.

Ekvivalenta definitioner är att $f:X\to Y$ är en injektion ifall $x_1\neq x_2\to f(x_1)\neq f(x_2)$ för alla $x_1$, $x_2\in X$ och $f$ är en surjektion ifall värdemängden $f(X)=\set{f(x)\mid x\in X}$ är den samma som målmängden $Y$, dvs. $f(X)=Y$.

Exempel: Injektion och/eller surjektion [+]

• Om $f:X\to Y$ och $g:Y\to Z$ är två funktioner så är $h=g\circ f:X\to Z$ funktionen $h(x)=g(f(x))$.
• Om $f:X\to Y$, $g:Y\to Z$ och $h:Z\to W$ är funktioner så gäller $(h\circ g)\circ f= h\circ (g\circ f)$ så att den här funktionen också kan skrivas i formen $h\circ g\circ f$.
• Om $f:X\to Y$ är en funktion och det finns en funktion $g:Y\to X$ så att $(g\circ f)(x)=x$ och $(f\circ g)(y)=y$ för alla $x\in X$ och $y\in Y$ så är $f$ inverterbar, $g$ är den inversa funktionen till $f$ (eller $f$:s invers) och vanligtvis skriver man $g=f^{-1}$.
• Funktionen $f:X\to Y$ är inverterbar om och endast om den är en bijektion.
• Om $f:X\to Y$ är inverterbar så gäller $(f^{-1})^{-1}=f$ dvs. den inversa funktionen är också inverterbar och dess invers är $f$.

Observera att $f^{-1}$ inte är samma funktion som $h(x)= f(x)^{-1}$ vilken förutsätter att varje element i $Y$ (eller åtminstone i värdemängden $f(X)$) har en invers vilket är tex. fallet i mängden $\R\setminus \{0\}$ men inte i mängden $\Z$.

Antag att $f: X\to Y$ är en funktion (där $X$ och $Y$ är icke-tomma mängder). Urbilden av mängden $B\subseteq Y$ i avbildningen $f$ är $$f^\leftarrow(B)= \set{x\in X\mid f(x)\in B}.$$ Ofta används beteckningen $f^{-1}(B)$ men $f^{-1}$ är också den inversa funktionen.
$f^\leftarrow$ är alltså en funktion: $\mathcal P(Y)\to \mathcal P(X)$.

Ifall till exempel [+]

$X=Y=\R$ och $f(x)= \sqrt{\abs{x}}$ så är $f^{\leftarrow}(\{2\})=\{-4,4\}$, $f^\leftarrow({-1})= \emptyset$ och $f^\leftarrow([3,\infty[)=]-\infty,-9]\cup [9,\infty[$.

Ifall $A\subseteq X$ så avses med $f(A)$ vanligen mängden $\set{y\in Y\mid \exists x\in A\,(f(x)=y)}= \set{f(x)\mid x\in A}$. Men om tex. $X=\{a,\{a\}\}$, $Y=\{b,c\}$, $f(a)= b$ och $f(\{a\})=c$ så är det med den här definitionen inte klart om $f(\{a\})= c$ eller$\{b\}$. Därför skulle det vara förnuftigt att definiera funktionen $f^\to:\mathcal P(X)\to \mathcal P(Y)$ så att $$f^\to(A)=\set{f(x)\mid x\in A}, \quad A\subseteq X.$$

Nu gäller till exempel att $f^\to$ är en surjektion då $f^\leftarrow$ är en injektion.

Varför? [+]

Vi definierar funktionen $F$ på följande sätt: $$\begin{equation*} F(n)= \begin{cases} 1,& \text{$n=1$ eller $n=2$},\\ F(n-1)+F(n-2), &\text{$n>2$}. \end{cases} \end{equation*}$$ Man kan visa att $$\begin{equation*} F(n)= \frac 1{\sqrt 5}\left (\left (\frac {1+\sqrt 5}2\right)^n-\left (\frac {1-\sqrt 5}2\right)^n\right ), \end{equation*}$$ dvs. F=@(n)(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5)

Ett annat alternativ är att räkna funktionens värde direkt ur definitionen tex. med följande rekursiva funktion
function f=F(n)
if n==1 || n==2, f=1;
else f=F(n-1)+F(n-2); end
return, endfunction

Om vi vill bestämma tex. talen $F(1), F(2),F(3),\ldots, F(15)$ kan vi först definiera F=[1,1]; och sedan räkna
for j=3:15, F(j)= F(j-1)+F(j-2); end
Men då blir tex. F(20) inte alls definierat.

Tillsvidare har endast behandlats funktioner med en variabel. På samma sätt kan man definiera funktioner med flera variabler (genom att först utvidga relationsbegreppet från det binära fallet) men det här är inte nödvändigt eftersom det finns andra sätt och nedan presenteras olika sätt att definiera och räkna ut värdena av en viss funktion med två variabler:

• Som en funktion med två variabler: $f(x,y)=\sin(x+3\cdot y)$ och i matlab/octave tex. f=@(x,y)sin(x+3*y) så att funktionens värde i punkten $(1,2)$ är f(1,2).
• Som en funktion med en vektorvariabel: $f([x,y])= \sin(x+3\cdot y)$ och tex. f=@(X)sin(X(1)+3*X(2)) så att funktionens värde i punkten $(1,2)$ är f([1,2]).
• Som en funktion av en (tex. den första) variabelns funktionsvärda funktion: $x\mapsto (y\mapsto \sin(x+3\cdot y))$ och tex. f=@(x)@(y)sin(x+3*y) så att funktionens värde i punkten $(1,2)$ är f(1)(2) (Fungerar inte i matlab!).

Om vi skall räkna värdet av polynomet $p(x)=a_n\cdot x^n+ a_{n-1}\cdot x^{n-1}+\ldots + a_1\cdot x+ a_0$ i punkten $x=x_*$ så kan vi gå till väga tex. på följande sätt:
Vi räknar ut talen $b_j$, $j=n,n-1,\ldots,0$ så att
$b_n=a_n$
$b_{n-1}= a_{n-1}+b_n\cdot x_*$
$b_{n-2}= a_{n-2}+b_{n-1}\cdot x_*$
$\quad \vdots$
$b_0 = a_0+ b_1\cdot x_*$
så att $p(x_*)=b_0$.

Här gör vi alltså högst $n$ additioner och $n$ multiplikationer dvs. sammanlagt $2\cdot n$ räkneoperationer så detta antal hör till mängden $O(n)$ ifall polynomets gradtal är högst $n$.

Ifall $p=1$ (det minsta talet) eller $p=n$ (det största talet) så räcker det med $n-1$ jämförelser men vad är svaret i det allmänna fallet?

Vi skall nu visa att om $1\leq p \leq n$ så hör antalet jämförelser som behövs till mängden $O(n)$, dvs. det finns en konstant $C$ så att antalet jämförelser är högst $Cn$ och vi bryr oss inte speciellt mycket om vad denna konstant är:

• Vi antar att det behövs högst $Ck$ jämförelser då det i mängden finns $k< n$ tal.
• Vi delar talen i delmängder i vilka det finns högst $5$ tal: Inga jämförelser.
• Vi bestämmer medianerna i dessa mängder: $O(n)$ jämförelser.
• Vi bestämmer medianernas median: $C (\frac 15 n+1)$ jämförelser.
• Vi delar tal i två mängder, beroende på om de är större eller mindre än medianernas median: $O(n)$ jämförelser.
• Bådadera av dessa mängder innehåller högst $(1-\frac 15\cdot \frac 12\cdot 3)n+O(1)= \frac 7{10}n+ O(1)$ tal!
• Antalet element i dessa mängder avgör i vilken av dem talet vi söker finns (om det nu inte är medianernas median) och vilket dess ordningsnummer är så vi kan hitta det i rätt delmängd: $C\frac 7{10}n + CO(1)$ jämförelser.
• Vi har använt $$O(n)+ \frac 15 C n+C+ O(n)+\frac 7{10}Cn + CO(1) \\ = \frac {9}{10}C n + CO(1)+ O(n)= \frac {9}{10}C n + (C+n)c_0,$$ jämförelser där $c_0$ är en konstant (som inte beror på $C$).
• Ifall $n\leq 20 c_0$ kan vi ordna talen genom att göra högst $n^2\leq (20 c_0) n$ jämförelser (men de facto räcker det högst $n\log_2(n)$ jämförelser) och på det sättet hitta talet vi söker så om vi väljer $C\geq 20c_0$ så behöver vi högst $Cn$ jämförelser då $n\leq 20c_0$ och då $n>20 c_0$ dvs. $c_0<\frac 1{20}n$så ser vi, eftersom $c_0\leq\frac 1{20}C$, att vi behöver $$\frac {9}{10}C n +(C+n)c_0\leq \frac {9}{10}C n + \frac 1{20} C n + \frac 1{20} C n= Cn,$$ jämförelser och induktionsresonenmanget fungerar.