\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}

\title{Lektion 03-31}

\begin{document}
\maketitle
\begin{definition}
L\aa t $A$ och $B$ vara tv{\aa} m\"angder. En {\bf funktion} fr\aa n $A$ till $B$ \"ar en regler som till \underline{varje element} $a\in A$ ordnar \underline{precis ett element} $f(a)=b\in B$.

Vi anv\"ander den f\"oljande terminologi:
\begin{itemize}
\item $f(a)$ kallas {\it funktionens v\"arde} i $a$.
\item $A$ kallas den {\it definitionsm\"angden}.
\item $V_f=\{b\in B|b=f(a)\text{ f\"or  n\aa got }a\in A\}\subseteq B$ kallas  {\it v\"ardem\"angden}.
\item $\Gamma_f=\{(a,f(a)|a\in A\}\subset A\times B$ kallas {\it grafen} av $f$
\end{itemize}
\end{definition}

Notera att om $A, B$ \"ar \"andliga m\"angder, kan  man bilda en bipartit graf $G_f=(V,E)$ fr\aa n $f$, genom att definera:
\begin{itemize}
\item $V=V_1\cup V_2$, d\"ar $V_1=A$, $V_2=D_f$.
\item $E=\{ af(a) \}$. S{\aa} $|E|=|\Gamma_f|$.
\end{itemize}

\vspace{.1in}

\noindent{\it Exempel}
\begin{itemize}
\item Betrakta funktionen $f:\zed_n \to \zed_n$, $f([x])=f([x+1])$.
\begin{itemize}
\item $V_f=\zed_n$.
\item $\Gamma_f=\{([n],[n+1])\}\subset \zed_n \times \zed_n$. Rita grafen! 
\end{itemize}
\item Reglen $f(x)=y$ , d\"ar $x^2+y^2=0$ inte definerar  en funktion.
 \item Betrakta funktionen $f:\real^+ \to \real$ defineras av $f(x)=\sqrt{x}$. 
\begin{itemize}
\item $V_f=\{y\in\real\text{ s{\aa} att }y=\sqrt{x}\text{ f\"or n\aa got} x\in\real^+\}=\real ^+$.
\item $\Gamma_f=\{(x,\sqrt{x})\}\subset \real^+ \times \real ^+$ \"ar en kurva.
\end{itemize}
\item Funktionen $id_A:A\to A$, defineras av $f(a)=a$ kallas {\it identitets funktionen} av $A$.
\begin{itemize}
\item $V_{id_A}=A$
\item $\Gamma_{id_A}=\{(a,a)\}$ kallas {\it diagonal} av $A\times A$.
\end{itemize}

\end{itemize}

\vspace{.2in}

\noindent{\it Om $|A|=n$ och $|B|=m$ det finns $m^n$ funktioner fr\aa n $A$ till $B$.}

\vspace{.1in}


F\"or att bilda en funktion  $f$ fr\aa n $A$ till $B$ vi ska ordna precis ett element i $B$ till varje element i $A$. Om $A=\{a_1,..., a_2\}$, definerar $f$ en sekvens $(f(a_1),...,f(a_n))\in B \times ... \times B$ ($n$ g\aa nger). Det betyder att det finns $| B \times ... \times B|=m^n$ m\aa nga funktioner.
\begin{definition}
L\aa t $f:A\to B$ och $g:B\to C$ vara funktioner. Den {\bf sammansatta funktionen} \"ar:
$$g\circ f:A\to C\;\text{ och defineras av }(g\circ f)(a)=g(f(a))$$
\end{definition}
Notera att ordning \"ar viktig. Betrakta funktioner:
$$e^*:\real\to\real,\;\; sin(*):\real\to \real$$
Funktionen $e^*\circ sin(*)=e^{sin(*)}:\real\to \real$ har v\"arde $e^{sin(\pi)}=1$ i $x=\pi$, men funktionen $sin(*)\circ e^*=sin(e^*)::\real\to \real$  har v\"arde $sin(e^{\pi})\neq 1$ i $x=\pi$. Vi s\"ager att tv{\aa} funktioner $f,g:A\to B$ \"ar lika, $f=g$, om $f(a)=g(a)$ f\"or varje $a\in A$. S{\aa} 
$$ e^*\circ sin(*)\neq sin(*)\circ e^*$$
\begin{definition}
L\aa t $f:A\to B$ vara en funktion. Den kallas {\bf injektiv} om
$$ f(a_1)=f(a_2) \Longrightarrow a_1=a_2$$
Det betyder att f\"or varje $b\in B$ det finns  h\"ogst en $a\in A$ s\aa dan att $f(a)=b$.
\end{definition}

\vspace{.1in}

\noindent{\it Exempel}\begin{itemize}
\item Funktionen $f:\real\to \real^+$ som defineras av $f(x)=x^2$ \"ar inte injectiv. Vi ser att $f(2)=f(-2)$, men $2\neq -2$.
\item Funktionen $f:\real\to \real$ som defineras av  $f(x)=x+1$ \"ar injektiv.
Vi ser att $f(a)=f(b)\Longrightarrow a+1=b+1\Longrightarrow a=b$.
\end{itemize}

L\aa t $f:A\to B$ vara en injektiv funktion, d\"ar $|A|=n$ och $|B|=m$. Enligt definition man n\"aste ha att:
$$f\text{ injective }\Longrightarrow n\leq m$$

F\"or att bilda en injektiva funktion f\aa n $A$ till $B$ ska man v\"alja $n$ element i $B$, utan upprepning och med ordning. S{\aa} det finns $\frac{m!}{(m-n)!}$ m\aa nga injektiva funktioner fr\aa n $A$ till $B$.

\begin{definition}
En funktion  $f:A\to B$ kallas {\bf surjektiv} om $D_f=B$. Det betyder att varje element $b\in B$ \"ar v\"arde av funktionen i n\aa gon $a\in A$.

\noindent En funktion som \"ar injektiv och surjectiv kallas {\bf bijektiv}.
Om $f$ \"ar bijektiv s{\aa} \"ar  varje element $b\in B$ v\"arde av funktionen i precis en element $a\in A$.
\end{definition}

Notera att om en function $f:A\to B$, d\"ar $|A|=n$ och $|B|=m$, \"ar surjektive d{\aa} \"ar $n\geq m$. Vi har att:

\noindent {\it Antalet surjektiva funktioner fr\aa n $A$ till $B$ \"ar:
$$\sum_{k=0}^m (-1)^k{m\choose k} (m-k)^n$$}

Vi ska visa denna formula bara f\"or ett exempel:
 
S\"att $A=\{1,2,3,4\}, B=\{b_1,b_2,b_3\}$, hur m\"aanga funktioner som \"ar surjektiva kan man definera?

Vi har $4^3$ funktioner totalt. Om vi best\"ammer antalet funktioner som inte \"ar surjektiva kan vi dra det bort fr\aa n$4^3$ och f{\aa} svaret.
Antag att $D_f\neq \{x,w,y,z\}$ och s\"att $A_i=\{ f\text{ s{\aa} att } b_i\not\in D_F\}$. Antalet funktioner som inte \"ar surjektiva \"ar lika med $|A_1\cup A_2\cup A_3|$.

Enligt inklusions-eklusions principen \"ar:
$$ |A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|+|A_2\cap A_3\cap A_3|$$

Man kan se att $|A_i|= (2)^4$ efetersom vi ska ber\"akna funktioner fr\aa n $A$ till $B\setminus \{b_i\}$. P{\aa} samma s\"att \"ar $|A_i\cap A_j|=(1)^4$ och $
|A_2\cap A_3\cap A_3|=0$.
Vi har altts{\aa} att:
$$|A_1\cup A_2\cup A_3|=3(2)^4-3(1)^4={3\choose 1}(m-1)^n-{3\choose 2}(m-2)^n$$ och svaret \"ar:
$$4^3-{3\choose 1}(m-1)^n-{3\choose 2}(m-2)^n=4^3-{3\choose 1}(2)^4-{3\choose 2}(1)^4$$

Hur n\aa nga bijektiva funktioner fr\aa n $A$ till $B$ finns det?
Om $f:A\to B$ \"ar injektiv (bijektiv+surjektiv) d{\aa} \"ar 
$$|A|=|B|$$

Antag att $|A|=n$. Varje permutation av elementen i $A$ ger en bijektiv funktion. Det finns allts{\aa} $n!$ injektiva funktioner fr\aa n $A$ till $B$.

\vspace{.1in}

Om $|A|=n, |B|=m$ vi har att:

 \vspace{.1in}

\begin{tabular}{|c|c|}\hline
antalet {\it funktioner }fr\aa n $A$ till $B$& $m^n$\\ \hline
antalet {\it injektiva} funktioner fr\aa n $A$ till $B$& $\frac{m!}{(m-n)!}$\\ \hline
antalet {\it surjektiva} funktioner fr\aa n $A$ till $B$&$\sum_{k=0}^m (-1)^k{m\choose k} (m-k)^n$\\ \hline
antalet {\it bijektiva} funktioner fr\aa n $A$ till $B$&$n!$ \\\hline
\end{tabular}

\vspace{.1in}

Antag att funktionen $f:A\to B$ \"ar injektiv d{\aa} kan man definera en funktion $f^{-1}:B\to A$ genom 
$$f^{-1}(b)=a\;\text{ d\"ar } f(a)=b$$
Den kallas den {\bf inversa funktionen}.
Man ser att $f\circ f^{-1}=id_B$ och $f^{-1}\circ f=id_A$

Ibland s\"ager man att en funktion $f:A\to B$ \"ar inverterbar, dvs att den har en invers funktion, om och endast om det finns en funktion $g:B\to A$ s\aa dan att:$$f\circ g=id_B\;\;\text{ och }g\circ f=id_A$$

\vspace{.1in}

\noindent{\it Exempel} Vi har visat att funktionen $f:\zed\to \zed$ som defineras av $f(x)=x+1$ \"ar injektiv. Inversen defineras av $f^{-1}(y)=x$ d\"ar $f(x)=x+1=y$. S{\aa} $x=y-1$.


En funktion fr\aa n $A$ till $B$ karaketerseras av grafen $\Gamma_f$, som \"ar en delm\"angd av $A\times B$ d\"ar varje element \"ar av formen $(a, f(a))$.

Vi ska generalisera definitionen av funktionen genom att betrakta varje delm\"angd.

\begin{definition}
En {\bf relation} $R$ mellan $A$ och $B$ \"ar en delm\"angd av $R\subset A\times B$. Ofta skriver man $a R b$ f\"or $(a,b)\in R$ och  $a \not R b$ f\"or $(a,b)\not \in R$. Om $A=B$ relationen kallas en {\bf bin\"ar relation}.
\end{definition}

\vspace{.1in}

\noindent{\it Exempel} Betrakta m\"angden $A=\{2,3,4,5,6,7\}$. Vi definera en relation genom
$$a R b \Longleftrightarrow a|b$$
Vi ser att $R=\{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6),(7,7)\}$.

\begin{definition}L\aa t $R$ vara en bin\"ar relation p{\aa} $A$.
\begin{itemize}
\item Den kallas {\bf riflexiv} om diagonalen $\Gamma_{id_A}\subset R$, dvs
$$ a R a\;\;\;\text{ f\"or alla }a\in A$$
\item Den kallas {\bf symmetrisk} om 
$$a R b \Longrightarrow b R a$$
\item Den kallas {\bf antisymmetrisk} om 
$$a R b \text{ och }  b R a\Longrightarrow a=b$$
\item Den kallas {\bf transitiv} om 
$$a R b \text{ och }  b R c\Longrightarrow a R c$$
\item Den kallas en {\bf partiell ordning} om den \"ar reflexiv, antisimmetrisk och transitiv.
\item En partiell ordning $R$ kallas en {\bf total partiell ordning} om f\"or alla $a,b$ g\"aller n\aa gon av:
$$ aRb \text{ och } b R a$$
 \item Den kallas en {\bf ekvivalensrelation} om den \"ar reflexiv, simmetrisk och transitiv.
\end{itemize} 
\end{definition}

\vspace{.1in}

\noindent{\it Exempel}
\begin{itemize}
\item Betrakta den f\"oljande bin\"ara relationen p{\aa} $\real$
$$ x R y \Longleftrightarrow x\leq y$$
Den \"ar en total partiell ordning.

Om vi definera $r$ med $x<y$ den blir inte reflexiv.
\item  Betrakta den f\"oljande bin\"ara relationen p{\aa} $\zed^+$
$$ x R y \Longleftrightarrow x|y$$

Den \"ar en partiell ordning, INTE total!
\item Betrakta den f\"oljande bin\"ara relationen p{\aa} $\zed$
$$ x R y \Longleftrightarrow x\equiv_n y$$
Den \"ar en ekvivalensrelation.
\end{itemize}

Om $R$ \"ar en ekvalensrelation p{\aa} $A$, kan man definera ekvivalensklassen:
$$[x]_R=\{a\in A\text{ s\aa dan att }x R a\}$$
Man kan visa att {\it f\"or varje ekvivalensrelation $R$ p{\aa} $A$ utg\"or ekvivalensklasserna en partition av $A$.}

\vspace{.1in}

\begin{definition}L\aa t $\underline{n}=\{1,2,...,n\}$ och l\aa t $A$ vara en m\"angd. Vi s\"ager att:
\begin{itemize}
\item $A$ \"ar \"andlig och har kardinalitet $n$, $|A|=n$ om det finns e bijektion fr\aa n $A$ till $\underline{n}$.
\item $A$ \"ar o\"andlig om det inte finns n\aa gon $n$ s\aa dan att det finns en bijektion fr\aa n $A$ till $\underline{n}$.
\item $A$ \"ar uppr\"akneligt o\"andlig om det finns en bijektion mellan $A$ och $\nat$.
\end{itemize}
\end{definition}

\vspace{.1in}

\noindent{\it Exempel}
\begin{itemize}
\item $\zed$ \"ar  uppr\"akneligt o\"andlig. Betrakta bijetktionen:
\[ f(n)=\left\{ \begin{array}{cc}
\frac{n+1}{2}&\;\text{ f\"or udda }n\\
\frac{-n}{2}&\:\text{ f\"or j\"amna n}
\end{array} \right. \]
\end{itemize}

\vspace{.1in}



\section*{\"Ovning}
\begin{enumerate}
 \item S\"att $A=\{1,2,3,4,5\}, B=\{x,w,y,z\}$ oxh $A_1=\{2,3,5\}$. L\aa t $g: A_1\to B$ vara en funktion. 
\begin{itemize}
\item P{\aa} hur m\aa nga s\"att kan $g$ utvidgas till en funktion fr\aa n $A$ till $B$?
\item Hur m\aa nga funktioner fr\aa n $A$ till $B$ finns det?
\item Hur m\aa nga injektiva funktioner fr\aa n $A$ till $B$ finns det?
\item Hur m\aa nga surjektiva funktioner fr\aa n $A$ till $B$ finns det?
\item Hur m\aa nga bijektiva funktioner fr\aa n $A$ till $B$ finns det?
\end{itemize}
\item Visa att $(g\circ f)\circ h=g\circ (f\circ h)$.
\item (Tentamen 20030820) Definira funktionen $f:\zed \to \zed$ genom:
\[ f(x)=\left\{ \begin{array}{cc}
2x&\;\text{ f\"or udda }x\\
2x+1&\:\text{ f\"or j\"amna x}
\end{array} \right. \]
\"Ar $f$ injektiv, surjektiv, bjektiv?
\item L\aa t $A,B$ vara tv{\aa} \"andliga m\"angder med samma kardinatiteten. Visa att en funktion fr\aa n $A$ till $B$ \"ar injektiv om och endast om den \"ar surjektiv. F\"orklara att det f\"oljer att:
$$\sum_{k=0}^n (-1)^k{n\choose k}(n-k)^n=n!$$
\item Visa att f\"or varje ekvivalensrelation $R$ p{\aa} $A$ utg\"or ekvivalensklasserna en partition av $A$.
\end{enumerate}

\vspace{1in}


\end{document}

