Categoria: Strutture algebriche

m:X\times X\times\dots\times X\rightarrow X\\
\text{dove }X\times X\times\dots\times X=\text{insieme di n-ple}\{ (x_1, x_2,...,x_n)|x_i\in X\}

{\color{blue}1)}\text{Opposto:}\\
\R\rightarrow\R\\
x\mapsto-x\\
\ \\
{\color{blue}2)}+:\\
\R\times\R\rightarrow\R\\
(x,y)\mapsto x+y\\
\ \\
{\color{blue}3)}\ \cdot \ :\\
\R\times\R\rightarrow\R\\
(x,y)\mapsto x\cdot y\\
\ \\
{\color{blue}4)}\text{Inverso}:\\
\R^\star\rightarrow\R^\star\\
x\mapsto x^{-1}\\
\text{(dove }\R^\star\text{ è l'insieme dei reali privati dallo 0)}

\alpha: X\times Y\rightarrow Y\\
(x,y)\mapsto\alpha(x,y)\in Y \text{ dove }x\in X, y\in Y

{\color{blue}1)} \ X=\{+,-\},\ Y=\R\\
\alpha:X\times \R\rightarrow\R\\
\text{dove }\alpha(+,x)=x\text{ e }\alpha(-,x)=-x\\
\ \\
{\color{blue}2)}\text{Prodotto scalare per vettore }\cdot \ :\\
\alpha: \R\times\R^2\rightarrow\R^2\\
(x,\vec v) \mapsto x\vec v

\text{Sia M un insieme, con }e\in M \text{ e sia }m:M\times M\rightarrow M\text{ un'operazione binaria }\\
\text{che per comodità indicheremo anche come }m(x,y)=xy\\
(M,e,m) \text{ è un monoide se valgono le seguenti proprietà:}\\
{\color{blue}1)}ex=xe\Rightarrow \text{esiste }e \text{ che è l'elemento neutro}\\
{\color{blue}2)}(xy)z=x(yz)\Rightarrow \text{ vale la proprietà associativa}\\

M=\N , \text{monoide}: (M, 0,+)\\
\text{vediamo la validità delle proprietà richieste perché sia un monoide}\\
a+(b+c)=(a+b)+c\ \checkmark\\
\text{ perché la proprietà associativa vale nei numeri naturali}\\
a+0=0+a=a\ \checkmark\\
\text{perchè 0 è l'elemento della somma nei numeri naturali}\\
\text{quindi } (\N,0,+)\text{ è un monoide}\\

\text{Sia G un insieme, con }e\in G \text{ e sia }m:G\times G\rightarrow G\text{ un'operazione binaria }\\
\text{che per comodità indicheremo anche come }m(x,y)=xy\\
(G,e,m) \text{ è un gruppo se valgono le seguenti proprietà:}\\
{\color{blue}1)}ex=xe\Rightarrow \text{esiste }e \text{ che è l'elemento neutro}\\
{\color{blue}2)}(xy)z=x(yz)\Rightarrow \text{ vale la proprietà associativa}\\
{\color{blue}3)}\forall x \in G \ \exist\  y \in G\ \ \ tc \ \ \ xy=yx=e \Rightarrow\text{esiste l'inverso}

\text{L'inverso è unico: }\ \forall \ x\ \exist!\ x^{-1}

{\color{blue}\text{Supponiamo per assurdo che esistano }y_1,y_2 \ tc\ y_1\neq y_2. \text{ Allora valgono}}\\
{\color{blue}xy_1=y_1x=e}\\
{\color{blue}xy_2=y_2x=e}\\
{\color{blue}\Rightarrow y_1=y_1e=y_1(xy_2)=(y_1x)y_2=ey_2=y_2. }\\
{\color{blue}\text{dove la terza equivalenza vale per la proprietà associativa dei gruppi. Assurdo}\ \ \ \ \ \square}

{\color{blue}1)}\text{Gruppo banale:}\\
\text{è composto solo dall'elemento neutro}\\
G=\{e\}, \text{ quindi la cardinalità è }\#G=1\\
\text{l'unica proprietà dei gruppi che può valere è l'esistenza dell'elemento neutro}\\
ee=e\ \ \ \checkmark\\
\ \\
{\color{blue}2)}G=\{+1,-1\} \text{ con operazine }\cdot \text{ ed elemento neutro }+1,\ \#G=2\\
(+1)\cdot(+1)=+1\\
(-1)\cdot(-1)=+1\\
(+1)\cdot(-1)=-1\\
(-1)\cdot(+1)=-1\\
\text{In generale, se il gruppo è formato solo dall'elemento neutro e da un altro elemento,cioè}\\
G=(a,e )\text{ allora vale necessariamente: }\\
ea=ae=a\\
ee=e\\
aa=e\\
\ \\
{\color{blue}3)}G=\Z, \ \text{gruppo: }(\Z,0,+)\\
\text{vediamo la validità delle proprietà richieste perché sia un gruppo}\\
a+(b+c)=(a+b)+c\ \checkmark\\
\text{ perché la proprietà associativa vale nei numeri interi }\\
a+0=0+a=a\ \checkmark\\
\text{perchè 0 è l'elemento della somma nei numeri interi}\\
\forall a\exist!b \ tc\ a+b=b+a=0\Rightarrow b=-a \ \checkmark\\
\text{perché nei numeri interi abbiamo l'esistenza dell'opposto}\\
\text{quindi } (\Z,0,+)\text{ è un gruppo}\\
 \ \\
{\color{blue}4)}G=\R^\star, \ \text{gruppo: }(\R^\star,1,\cdot)\\
\text{vediamo la validità delle proprietà richieste perché sia un gruppo}\\
a\cdot(b\cdot c)=(a\cdot b)\cdot c\ \checkmark\\
\text{ perché la proprietà associativa vale nei numeri reali}\\
a\cdot1=1\cdot a=a\ \checkmark\\
\text{perchè 1 è l'elemento della moltiplicazione nei numeri reali}\\
\forall a\exist!b \ tc\ a\cdot b=b\cdot a=1\Rightarrow b=a^{-1} \ \checkmark\\
\text{perché nei numeri reali abbiamo l'esistenza dell'inverso}\\
\text{quindi } (\Z,0,+)\text{ è un gruppo}\\

\text{Sia }X=\{1,2,...,n\}\\
\text{Definiamo }S(n)=\{f:X\rightarrow X|f \text{ biunivoca}\}\\
\text{dove quindi }f\in S_n\text{ sono le permutazioni di }X.\\
\text{gruppo: }(S_n,Id _X,\circ)\\
\text{vediamo la validità delle proprietà richieste perché sia un gruppo}\\
f\circ(g\circ h)=(f\circ g)\circ h\ \checkmark\\
\text{ perché la proprietà associativa vale nella composizione di funzioni}\\
f\circ Id_X=Id_X\circ f=f\ \checkmark\\
\text{perchè } Id_X \text{è l'elemento della composizione tra le funzioni}\\
\forall f\exist!g \ tc\ f\circ g=g\circ f=f\Rightarrow g=f^{-1} \ \checkmark\\
\text{perché nelle funzioni biunivoche  abbiamo l'esistenza dell'inverso}\\
\text{quindi }(S_n,Id _X,\circ)\text{ è un gruppo}\\
\text{In generale però la composizione di funzioni non è commutativa, quindi}\\
\text{il gruppo non è abeliano}

\text{In un gruppo qualsiasi }  (ab)^{-1}=a^{-1}b^{-1}

{\color{blue}\text{Sappiamo che }(a^{-1})a=1=a(a^{-1}) \text{ per l'esistenza dell'inverso}}\\
{\color{blue}\text{Inoltre, per l'unicità dell'inverso vale anche che: }(a^{-1})^{-1}=a}\\
{\color{blue}\text{Da queste osservazioni e dalla proprietà associativa del gruppo possiamo calcolare:}}\\
{\color{blue}(b^{-1}a^{-1})(ab)=b^{-1}(a^{-1}a)b=b^{-1}1b=b^{-1}b=1}\\
{\color{blue}(ab)(b^{-1}a^{-1})=a(bb^{-1})a^{-1}=a1a^{-1}=aa^{-1}=1}\\
{\color{blue}\text{Quindi }ab\text{ è invertibile con inverso }b^{-1}a^{-1}}\\
{\color{blue}\text{Per l'unicità dell'inverso abbiamo }(ab)^{-1}=b^{-1}a^{-1}\ \ \ \ \ \ \square}

\text{Un anello è formato da un insieme A, due operazioni interne che indicheremo }\\
\text{con + e }\cdot\text{ insieme ai loro elementi neutri, che indicheremo rispettivamente}\\
\text{con 0 e 1, in modo tale che:}\\
{\color{blue}1)}\ (A,0, +)\text{ sia un gruppo abeliano}\\
{\color{blue}2)}\ (A,1 ,\cdot) \text{sia un monoide} \\
{\color{blue}3)} \text{valgano le proprietò distributive: }\\
{\color{blue}3.a)}(a+b)c=ac+bc\\
{\color{blue}3.b)}c(a+b)=ca+cb\\

(A,1,\cdot)

{\color{blue}1)}(\Z,0,1,+,\cdot)\text{ è un anello commuativo}\\
{\color{blue}2)}(\mathbb{Q},0,1,+,\cdot)\text{ è un anello commutativo}\\
{\color{blue}3)}\text{Vediamo un anello finito:}\\
\text{Consideriamo }\Z/n=\{[0],[1],...,[n-1]\} \text{ classi di equivalenza dei possibili resti di }\\
x\equiv_n y\text{ dove due numeri sono equivalenti se, divisi per n, hanno lo stesso resto}.\\
\text{Consideriamo }(\Z/n,[0],[1],+,\cdot) \\
\text{Vediamo come si comportano le operazioni e se rispettano le proprietà che ci servono }\\
\text{Somma tra le classi di equivalenza: }[a]+[b]=[a+b]\\
(\text{ad esempio   n=7, }\Z/7=\{[0],[1],[2],[3],[4],[5],[6]\}\Rightarrow[4]+[6]=[10]=[3])\\
\text{Quindi }[0] \text{è l'elemento neutro ed abbiamo sia la proprietà associativa}\\
\text{che l'esistenza dell'inverso (derivano dalle proprietà della somma in }\Z)\\
\Rightarrow(\Z/n,[0],+) \text{ è un gruppo}\ \ \ \checkmark\\
\text{Moltiplicazione tra le classi di equivalenza: }[a][b]=[ab]\\
\text{questa operazione è ben definita perchè se abbiamo }[a]=[a'] \text{ e }[b]=[b']\\
a'b'=(a+nh)(b+kn)=ab+n(hb+ak+hkn)\Rightarrow[a'b']=[ab]\\
\text{dato che dalla somma sappiamo che }n[a]=[a\cdot0]=[0]\forall a \in \Z \\
\text{Quindi }[1] \text{è l'elemento neutro ed abbiamo la proprietà associativa}\\
\text{(derivano dalle proprietà del prodotto in }\Z)\\
\Rightarrow(\Z/n,[1],\cdot) \text{ è un monoide}\ \ \ \checkmark\\
(\Z/n,[0],[1],+,\cdot)\text{è un anello}\\
\text{Inoltre, grazie alla commutatività della moltiplicazione}\\
(\Z/n,[1],\cdot)\text{è un monoide commutativo}\Rightarrow(\Z/n,[0],[1],+,\cdot)\text{è un anello commutativo}\\

\text{Un campo è formato da un insieme A, due operazioni interne che indicheremo }\\
\text{con + e }\cdot\text{ insieme ai loro elementi neutri, che indicheremo rispettivamente}\\
\text{con 0 e 1, in modo tale che:}\\
{\color{blue}1)}(A, 0,1,+,\cdot) \text{ è un anello commutativo}\\
{\color{blue}2)}(A^\star,1,\cdot)\text{ è un gruppo, cioè se }\forall x\in A^\star  \exist!x^{-1}\ tc \ xx^{-1}=1

{\color{blue}1)}(\R,0,1,+,\cdot)\text{ è un campo}\\
{\color{blue}2)}(\mathbb{C},0,1,+,\cdot)\text{ è un campo}\\

\text{Sia p un numero primo. Allora }\Z/p \text{ è un campo}\\

{\color{blue}\text{Sia }\Z/p=\{[0],[1],...[p-1]\} \text{ e sia }[a]\neq[0]} \\
{\color{blue}\text{Possiamo supporre } 1\leq a< p \text{ dato che siamo nelle classi di equivalenza}}\\
{\color{blue}\text{Consideriamo la funzione }f:\Z/p\rightarrow \Z/p \text{ definita come}}\\
{\color{blue}f([x])=[ax]}\\
{\color{blue}\text{Proviamo per assurdo che } f \text{ sia iniettiva:}}\\
{\color{blue}\text{supponiamo }0\leq x,\ y < p\text{ e che }f([x])=f([y]), \text{ cioè }[ax]=[ay]}\\
{\color{blue}[ax-ay]=[0]\Rightarrow[a(x-y)]\iff a(x-y)=kp}\\
{\color{blue}\text{Dato che p è primo, allora l'ultima uguaglianza significa che}}\\
{\color{blue}p\text{ divide } a \text{ oppure } p \text{ divide} (x-y). }\\
{\color{blue}p\text{ non può dividere } a \text{ poiché }[a]\neq[0] \text{ e }a< p.}\\
{\color{blue} \text{Abbiamo solo una possibilità: } p\text{ deve dividere }(x-y)\Rightarrow[x]=[y]}\\
{\color{blue}\text{da cui otteniamo l'iniettività di f }\ \ \ \checkmark }\\
{\color{blue}\text{Proviamo anche la suriettività di }f: }\\
{\color{blue}\text{è vero perché }\Z/p \text{ è un insieme finito}\ \ \ \ \checkmark}\\
{\color{blue}\text{Abbiamo ottenuto che la nostra funzione sia biiettiva!}}\\
{\color{blue}\text{Questo significa che esiste la funzione inversa }f^{-1}: \text{ deve esistere}}\\
{\color{blue}[x]\in\Z/p \  tc\ f([x])=1\text { da cui ricaviamo che  }}\\
{\color{blue}\text{ [ax]}=[1]\Rightarrow[a][x]=[1]\Rightarrow[x]=[a^{-1}]\ \ \ \ \checkmark}\\
{\color{blue}\text{Dato che in generale  sappiamo che  }\Z/n \text{ è un anello commutativo, per avere} }\\
{\color{blue}\text{il campo ci mancava proprio soltanto l'esistenza dell'inverso per avere}}\\
{\color{blue}(\Z/p^\star,[1],\cdot) \text{ gruppo ed avere tutte le caratteristiche, quindi abbiamo finito }\ \ \square}

\mathscr{R}\sube A\times B

\mathscr{R}\sube A\times A

1) \forall\ x \in A\Rightarrow\ (x,x)\in \mathscr{R} \text{\ \ (cioè vale la proprietà riflessiva)}\\
2) (x,y)\in \mathscr{R} \text{ e } (y,x)\in \mathscr{R}\Rightarrow x=y\ \ \  \text{(cioè vale la proprietà antisimmetrica)}\\
3)(x,y)\in  \mathscr{R}\text{ e }(y,z)\in  \mathscr{R}\Rightarrow (x,z)\in  \mathscr{R} \text{\ \ (cioè vale la proprietà transitiva)}

\forall x, \ y\in A \Rightarrow (x,y)\in  \mathscr{R} \text{ o } (y, x) \in \mathscr{R}

\forall\  C\neq\empty, \ C\sube A\Rightarrow \text{C ha un minimo} 

\leq

{\color{blue}\text{Vogliamo dimostrare che in ogni sottoinsieme }\N \text{ abbiamo un minimo }}\\
{\color{blue}\text{Sia }B\sube \N \text{ un sottoinsieme}\neq\empty \text{ di }\N.}\\
\ \\
{\color{blue}\text{ Se } 0\in \N,  \text{ allora}\ \ 0=\min B\ \ \checkmark}\\
\ \\
{\color{blue}\text{Se }0\notin B\text{ consideriamo un insieme }K=\{n|\forall\ 0\leq m\leq n\text{ abbiamo }m\notin B\}}\\
{\color{blue}\text{Proviamo che }K \text{ abbia un massimo, cioè che }\exist n_0 \ tc\  \forall n\in K \text{abbiamo }n\leq n_0.}\\
{\color{blue}\text{Lo facciamo per assurdo: supponiamo che }}{\color{blue}\forall m \in K\ \exist\ n'\in K\ tc\ n'>m}.\\
{\color{blue}\text{Per costruzione }0 \in K.}\\
{\color{blue} \text{ Se }n\in K \text{consideriamo }n+1 \text{ e }n'\in K \text{ con }n'>n\Rightarrow n< n+1\leq n'}\\
{\color{blue}\text{ In particolare tutti gli elementi } 0\leq m\leq n'  \text{ appartengono all'insieme } K }\\ 
{\color{blue}\text{ dunque }\forall m \ 0\leq m\leq n+1,\ m\in K}\\
{\color{blue}\text{Quindi  }n+1\ \in \ K \text{e per induzione }K=\N.}\\
{\color{blue}\text{Ma allora }B\neq\empty. \text{ Assurdo }\ \checkmark}\\
\ \\
{\color{blue}\text{Sia }n=\max K. \text{ Allora }n+1\in B \text{ e }n+1=\min B\ \ \ \ \ \square}

\underset{a}{\leq}\\ 
\ \\\text{la relazione definita come:}\
\\ 
\text{dati }n\in\N, m\in\N \text{ allora  }\ \  n \underset{a}{\leq}m\iff \exist q\in \N tc\ nq=m\\
\ \\
\text{(ovvero } n \text{ è in relazione con }m\text{ se e solo se }n\text{ divide }m)

\text{Sia }X \text{un insieme ordinato conrelazione d'ordine}\leq.\\
\ \\
x_0 \text{ è detto  \textbf{minimale} se }\nexists y \in  X\ tc\ y < x_0 \text{ o  equivalentemente}\\
y\leq x_0 \Rightarrow y=x_0\\
x_0 \text{ è detto  \textbf{massimale} se }\nexists y \in  X\ tc\ y > x_0 \text{ o  equivalentemente}\\
y\geq x_0 \Rightarrow y=x_0\\

\mathscr{R}\sube A\times A

1) \forall\ x \in A\Rightarrow\ (x,x)\in \mathscr{R} \text{\ \ (cioè vale la proprietà riflessiva)}\\
2) (x,y)\in \mathscr{R} \Rightarrow (y,x)\in \mathscr{R}\ \forall\ x,y\in A\ \ \  \text{(cioè vale la proprietà simmetrica)}\\
3)(x,y)\in  \mathscr{R}\text{ e }(y,z)\in  \mathscr{R}\Rightarrow (x,z)\in  \mathscr{R} \text{\ \ (cioè vale la proprietà transitiva)}

\mathscr{R}\sube A \times B

\Gamma f\sube A \times B

1) \forall x \in A\  \exist\ y\in B\ tc\ (x,y)\ \ \Gamma f\\
2)(x,y_1)\text{ e }(x,y_2)\in \Gamma f\Rightarrow y_1=y_2

f:A\rightarrow B

x\neq y\Rightarrow f(x)\neq f(y) \forall\ x,y\in A

\forall\  y\in B\ \exist \ x\in A \ tc\ f(x)=y

f:A\rightarrow B\\
g:B\rightarrow C

g\circ f: A\rightarrow C\\
\text{dove }\\
g\circ f(x)=g(f(x))

\exist \ g: B\rightarrow A \ tc\\
 g\circ f=id_A \ \ \ \ { e }\ \ \ \ f\circ g=id_B

f:A\rightarrow B \text{ è biunivoca }\iff\text{ f è suriettiva e iniettiva}

{\color{blue}\Rightarrow) \text{Supponiamo che f sia biunivoca, ovvero che } \exist \ g: B\rightarrow A \ tc}\\
{\color{blue} g\circ f=id_A \ \ \ \ { e }\ \ \ \ f\circ g=id_B}\\
{\color{blue}\text{Iniziamo dimostrando l'iniettività di } f:\text{  consideriamo } f(x)=f(y). }\\
{\color{blue}\text{Applichiamo la funzione } g \text{ ad entrambe ed otteniamo:}}\\
{\color{blue}g(f(x))=g(f(y)) \text{ ma per la nostra ipotesi abbiamo }g\circ f=id_A}\\
{\color{blue}\Rightarrow x=y \text{ quindi } f \text{ è iniettiva }\checkmark}\\
{\color{blue}\text{Dimostriamo la suriettività di } f: \text{sia }y \in B.}\\
{\color{blue}\text{Prendiamo }x =g(y )\text{ e calcoliamo } f(x)=f(g(y))=y \text{ dall'ipotesi}}\\
{\color{blue}f\circ g=id_B\Rightarrow\forall\ y \in B\  \exist x\ tc\ f(x)=y\  \checkmark\ \ \ \ \ \ \ \ \square}\\
\ \\
{\color{blue}\Leftarrow)\text{Sia }f \text{ iniettiva e suriettiva.}}\\
{\color{blue}\text{Dobbiamo trovare } g :A\rightarrow B \ tc\ \ g(y)=x\ \ \ e \ \ \ y=f(x)}\\
{\color{blue}  \ x\text{ esiste perchè }f \text{ è suriettiva}\checkmark}\\
{\color{blue} x \text{ è unica perchè } f \text{ è iniettiva}\checkmark}\\
{\color{blue}\text{quindi  la funzione } g \text{ è ben definita}\ \ \ \ \ \ \ \ \ \square} 

(f\circ g)\circ h= f\circ(g\circ h)