Jos joukossa $X$ on äärellisen monta alkiota niin voimme esittää relaation $W\subseteq X\times X$ verkkona, jossa $X$:n alkiot ovat verkon solmut ja solmusta $x$ solmuun $y$ on kaari jos ja vain jos $[x,y]\in W$.
Esimerkiksi näin:

Relaatio on

Voit lisätä tai poistaa kaareja (eli elementtejä relaatiossa) klikkaamalla ensin kyseisen kaaren lähtösomua ja sitten kohdesolmua.

Suuntaamattomassa verkossa ei tehdä eroa kaaren lähtö- ja kohdesolmun välillä.

Relaatio joukossa, jossa on äärellisen monta alkiota voidaan esittää suunnattuna verkkona mutta jos joukossa on äärettömän monta alkiota, tämä ei yleensä ole toimiva vaihtoehto.

Esimerkiksi $W=\{ [x,y] \,:\, x,\, y \in \R,\,\, x < y\}$ on relaatio joukossa $\R$ ja siten, kuten kaikki relaatiot joukossa $\R$, tason $\R^2$ osajoukko. Mutta kun puhutaan tästä relaatiosta "pienempi kuin" niin tarkoitetaan useimmiten (kuten monessa muussakin tapauksessa) predikaattia $P(x,y)$, joka on tosi kun $[x,y]\in W$ eli kun $x< y$ (jolloin merkintä $P(x,y)$:n sijasta tietenkin kannattaa kirjoittaa $x< y$).

 

Relaatio $W$ joukossa $X$ on

• refleksiivinen jos $[x,x]\in W$ kaikilla $x\in X$.
• symmetrinen jos $[x,y]\in W \to [y,x]\in W$ kaikilla $x$ ja $y\in X$.
• transitiivinen jos $[x,y]\in W \And [y,z]\in W \to [x,z]\in W$ kaikilla $x$, $y$ ja $z\in X$.
• antisymmetrinen jos $[x,y]\in W \And x\neq y \to [y,x]\notin W$ (eli $[x,y]\in W\And [y,x]\in W\to x=y$) kaikilla $x$ ja $y\in X$.
• asymmetrinen jos $[x,y]\in W \to [y,x]\notin W$ kaikilla $x$ ja $y\in X$.
• totaalinen jos $[x,y]\in W \Or [y,x]\in W$ kaikilla $x$ ja $y\in X$.

Lisäksi sanotaan, että $W$ on

• ekvivalenssirelaatio jos $W$ on refleksiivinen, symmetrinen ja transitiivinen,
• osittaisjäjestys jos $W$ refleksiivinen, antisymmetrinen ja transitiivinen,
• täydellinen järjestys jos $W$ on osittaisjärjestys ja täydellinen,
• hyvinjärjestys jos $W$ on täydellinen järjestys ja jokaisessa $X$:n ei-tyhjässä osa-joukossa on pienin alkio.

Usein kirjoitetaan $[x,y]\in W$:n sijasta $xWy$, esimerkiksi $x\prec y$ eikä $[x,y]\in \prec$.

Olkoon $X$ jokin (ei-tyhjä) joukko ja $\mathcal P(X)$ sen kaikkien osajoukkojen muodostama joukko (eli ns. potenssijoukko). Joukossa $\mathcal P(X)$ meillä on relaatio $\subseteq$: $A\subseteq B$ jos ja vain jos $A$ on $B$:n osajoukko. Tämä relaatio on osittaisjärjestys koska se on

• refleksiivinen: $A\subseteq A$,
• antisymmetrinen: Jos $A\subseteq B$ ja $A\neq B$ niin on olemassa $x\in B$ siten että $x\notin A$ jolloin $B\not\subseteq A$,
• transitiivinen: Jos $A\subseteq B$ ja $B\subseteq C$ niin jokainen $A$:n alkio on $B$:n alkio ja koska jokainen $B$:n alkio on $C$:n alkio niin jokainen $A$:n alkio on $C$:n alkio, eli $A\subseteq C$.

Lisäksi tällä relaatiolla on muitakin ominaisuuksia kuten, että jos $A$, $B\in \mathcal P(X)$ niin joukoille $A$ ja $B$ löytyy pienin yläraja, eli joukko $C$ siten, että $A\subseteq C$, $B\subseteq C$ (eli $C$ on yläraja) ja jos $A\subseteq D$ ja $B\subseteq D$ niin $C\subseteq D$ (eli $C$ on pienin yläraja). Selvästikin $C=A\cup B$. Vastaavasti löytyy myös suurin ala-raja, joka (tietenkin?) on $A\cap B$.

Jos $X$ on ei-tyhjä joukko ja $\sim$ on ekvivalenssirelaatio joukossa $X$, niin se jakaa joukon $X$ osajoukkoihin $Y_j\neq \emptyset$, $j\in J$ joita kutsutaan ekvivalenssiluokiksi siten, että

• $\cup_{j\in J} Y_j=X$,
• $Y_j\cap Y_k=\emptyset$ jos $j\neq k$,
• $a\sim b \leftrightarrow$ $a$ ja $b$ kuuluvat samaan joukkoon $Y_j$.

Usein ajatellaan, että kaksi alkiota jotka ovat ekvivalenttia, eli niiden muodostama pari kuuluu relaatioon $\sim$, ovatkin ''samat'' jolloin joukon $X$ sijasta tarkastellaan joukkoa $\set{Y_j\mid j\in J}$, jonka alkiot ovat ekvivalenssiluokat.

Esimerkki: Kokonaisluvut ekvivalenssiluokkina [+]

  

Voidaan puhua esim. luvusta $2$ ilman sekaantumisen vaaraa, mutta jos puhutaan lausekkeesta $x+3$ ei ole välttämättä selvää tarkoitetaanko funktiota, joka antaa tulokseksi argumenttinsa johon on lisätty $3$ vai tämän funktion arvo kun argumentti on $x$. Jos tarkoitetaan funktiota eikä sen arvoa niin voidaan kirjoittaa
$x\mapsto x+3$
@(x)x+2
function(x){return x+3;}
lambda([x],x+3);
tai jotain muuta vastaavaa.

Funktio $f:X\to Y$ on

• injektio jos $f(x_1)=f(x_2) \to x_1=x_2$ kaikilla $x_1,\, x_2\in X$,
• surjektio jos kaikilla $y\in Y$ on olemassa $x\in X$ siten, että $f(x)=y$,
• bijektio jos se on sekä injektio että surjektio.

Ekvivalentti määritelmä on, että $f:X\to Y$ on injektio jos $x_1\neq x_2\to f(x_1)\neq f(x_2)$ kaikilla $x_1$, $x_2\in X$ ja $f$ on surjektio jos arvojoukko $f(X)=\set{f(x)\mid x\in X}$ on sama kuin maalijoukko $Y$ eli $f(X)=Y$.

Esimerkki: Injektio ja/tai surjektio [+]

• Jos $f:X\to Y$ ja $g:Y\to Z$ ovat kaksi funktiota niin $h=g\circ f:X\to Z$ on funktio $h(x)=g(f(x))$.
• Jos $f:X\to Y$, $g:Y\to Z$ ja $h:Z\to W$ ovat funktioita niin $(h\circ g)\circ f= h\circ (g\circ f)$ joten tämä funktio voidaan myös kirjoittaa muodossa $h\circ g\circ f$.
• Jos $f:X\to Y$ sellainen funktio, että on olemassa funktio $g:Y\to X$ siten että $(g\circ f)(x)=x$ ja $(f\circ g)(y)=y$ kaikilla $x\in X$ ja $y\in Y$ niin $f$ on kääntyvä, $g$ on $f$:n käänteisfunktio ja tavallisesti kirjoitetaan $g=f^{-1}$.
• Funktio $f:X\to Y$ on kääntyvä jos ja vain jos se on bijektio.
• Jos $f:X\to Y$ on kääntyvä niin $(f^{-1})^{-1}=f$ eli käänteisfunktio on myös kääntyvä ja sen käänteisfunktio on $f$.

Huomaa, ettei $f^{-1}$ ole sama funktio kuin $h(x)= f(x)^{-1}$, joka edyllyttää että $Y$:n (tai ainakin arvojoukon) elementeillä on käänteisalkioita mikä on esim. tilanne joukossa $\R\setminus \{0\}$ mutta ei joukossa $\Z$.

Olkoon $f$ funktio: $X\to Y$ (missä $X$ ja $Y$ ovat ei-tyhjiä joukkoja). Joukon $B\subseteq Y$ alkukuva kuvauksessa $f$ on silloin \[ f^\leftarrow(B)= \set{x\in X\mid f(x)\in B}. \] Usein käytetty merkintä alkukuvalle on $f^{-1}(B)$ mutta $f^{-1}$ tarkoittaa myös käänteiskuvausta.
$f^\leftarrow$ on siis funktio: $\mathcal P(Y)\to \mathcal P(X)$.

Jos esimerkiksi [+]

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

Jos $A\subseteq X$ niin $f(A)$ tarkoittaa tavallisesti joukkoa $\set{y\in Y\mid \exists x\in A\,(f(x)=y)}= \set{f(x)\mid x\in A}$. Mutta jos esimerkiksi $X=\{a,\{a\}\}$, $Y=\{b,c\}$, $f(a)= b$ ja $f(\{a\})=c$ niin tällä määritelmällä ei ole selvää onko $f(\{a\})= c$ vai $\{b\}$. Tästä syystä olisi järkevää määritellä funktiota $f^\to:\mathcal P(X)\to \mathcal P(Y)$ siten, että \[ f^\to(A)=\set{f(x)\mid x\in A}, \quad A\subseteq X. \]

Nyt pätee esimerkiksi, että $f^\to$ on surjektio jos $f^\leftarrow$ on injektio.

Miksi? [+]

Määrittelemme funktion $F$ seuraavasti: \begin{equation*} F(n)= \begin{cases} 1,& \text{$n=1$ tai $n=2$},\\ F(n-1)+F(n-2), &\text{$n>2$}. \end{cases} \end{equation*} Voidaan osoittaa, että \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*} eli F=@(n)(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5)

Toinen vaihtoehto on laskea funktion arvot suoraan määritelmästä esim. seuraavalla rekursiivisella funktiolla
function f=F(n)
if n==1 || n==2, f=1;
else f=F(n-1)+F(n-2); end
return, endfunction

Jos haluamme laskea esim luvut $F(1), F(2),F(3),\ldots, F(15)$ voimme ensin määritellä F=[1,1]; ja sitten laskea
for j=3:15, F(j)= F(j-1)+F(j-2); end
Mutta silloin esimerkiksi F(20) ei ole lainkaan määritelty.

Edellä on käsitelty ainoastaan yhden muuttujan funktioita. Samalla tavalla voidaan määritellä usean muuttujan funktioita, (laajentamalla ensin relaation käsitettä binäärisestä tapauksesta) mutta tämä ei ole aivan välttämätöntä koska näiden funktioiden kohdalla on olemassa erilaisia lähestymistapoja ja seuraavassa esitetään miten tietty kahden muttujan funktio voidaan määritellä ja sen arvoja laskea eri tavoilla:

• Kahden muuttujan funktiona: $f(x,y)=\sin(x+3\cdot y)$ ja Matlab/Octavessa esim. f=@(x,y)sin(x+3*y) jolloin funktion arvo pisteessä $(1,2)$ on f(1,2).
• Yhden vektorimuuttujan funktiona: $ f([x,y])= \sin(x+3\cdot y)$ tai esim. f=@(X)sin(X(1)+3*X(2)) jolloin funktion arvo pisteessä $(1,2)$ on f([1,2]).
• Yhden (eli esim. ensimmäisen) muuttujan funktioarvoisena funktiona: $x\mapsto (y\mapsto \sin(x+3\cdot y))$ tai esim. f=@(x)@(y)sin(x+3*y) jolloin funktion arvo pisteessä $(1,2)$ on f(1)(2) (Ei toimi Matlabissa!).

Jos meidän pitää laskea polynomin $p(x)=a_n\cdot x^n+ a_{n-1}\cdot x^{n-1}+\ldots + a_1\cdot x+ a_0$ arvo pisteessä $x=x_*$ niin voimme menetellä esimerkiksi seuraavalla tavalla:
Laskemme luvut $b_j$, $j=n,n-1,\ldots,0$ siten, että
$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_*$
jolloin $p(x_*)=b_0$.

Tässä joudumme siis tekemään korkeintaan $n$ yhteenlaskua ja $n$ kertolaskua eli yhteensä $2\cdot n$ laskutoimitusta joten näiden lukumäärä kuuluu joukkoon $O(n)$ jos polynomin aste on korkeintaan $n$.

Jos $p=1$ (pienin luku) tai $p=n$ (suurin luku) niin $n-1$ vertailua riittää mutta mikä on tilanne yleisessä tapauksessa?

Seuraavaksi osoitamme, että jos $1\leq p \leq n$ niin tarvittavien vertailujen lukumäärä kuuluu joukkoon $O(n)$, eli on olemassa vakio $C$ siten, että vertailujen lukumäärä on korkeintaan $Cn$ emmekä välitä kovinkaan paljon siitä mikä tämä vakio on:

• Oletamme että tarvitaan korkeintaan $Ck$ vertailua kun joukossa on $k< n$ lukua.
• Jaamme luvut osajoukkoihin joissa on $5$ lukua: Ei vertailuja.
• Määritämme näiden osajoukkojen mediaanit: $O(n)$ vertailua.
• Määritämme mediaanien mediaani: $C (\frac 15 n+1)$ vertailua.
• Jaamme luvut kahteen joukkoon, riippuen siitä ovatko ne suurempia tai pienempiä kuin mediaanien mediaani: $O(n)$ vertailua.
• Kumpikin näistä joukoista sisältää korkeintaan $(1-\frac 15\cdot \frac 12\cdot 3)n+O(1)= \frac 7{10}n+ O(1)$ lukua!
• Joukkojen alkioiden lukumäärien perusteella tiedämme missä osajoukossa hakemamme luku on ellei se ole mediaanien mediaani ja mikä sen järjestysnumero siinä on joten haemme sen kyseisestä osajoukosta: $C\frac 7{10}n + CO(1)$ vertailua.
• Olemme käyttäneet vertailua missä $c_0$ on vakio.
• Jos $n\leq 20 c_0$ voimme järjestää luvut käyttäen $n^2\leq (20 c_0) n$ vertailua (tosiasiassa $n\log_2(n)$ vertailua riittää) ja siten löytää hakemamme luku joten jos valitsemme $C\geq 20c_0$ niin tarvitsemme korkeintaan $Cn$ vertailua kun $n\leq 20c_0$ ja kun $n>20 c_0$ eli $c_0<\frac 1{20}n$ toteamme, koska $C$:n valinnan seurauksena $ c_0\leq\frac 1{20}C$, että tarvitsemme vertailua ja induktiopäättely toimii.