Pubblicità

Sottospazi vettoriali e Lemma di Steinitz

Consideriamo:

V \text{ un } \mathbb K\text{ spazio vettoriale e sia } A\sube V\\
\text{Definiamo}\\
\mathscr{L}(A)=\{\vec v\in V|\exist \ \vec v_1,..,\vec v_n\in A, \lambda_1,...\lambda_n\in\mathbb K\ tc\ \vec v=\lambda_1\vec v_1+...+\lambda_n\vec v_n\}

Definiamo il sottospazio vettoriale:

W\sube V \text{si dice sottospazio vettoriale dello spazio vettoriale }V \text{ se:}\\
1)0\vec v\in W\\
2)\forall \ \vec v_1,\vec v_2 \in W,\forall \lambda,\mu \in \mathbb K\text{ si ha }\lambda\vec v_1+\mu\vec v_2\in W

In particolare un sottospazio è un insieme dello spazio vettoriale di partenza che può essere a sua volta considerato uno spazio vettoriale restringendo ad esso le operazioni di partenza.

Vediamo qualche proprietà

Proposizione:

\mathscr{L}(A) \text{ è il più piccolo sottospazio di }V \text{ contenente }A

Dimostrazione:

{\color{blue}\text{Se }W\sube V\text{ è sottospazio e }A\sube W \text{, allora presi }\vec v_1,...,\vec v_n\in A ,\ \lambda_1,...,\lambda_n\in\mathbb K}\\
{\color{blue}\text{abbiamo }\lambda_1\vec v_1+...+\lambda_n\vec v_n\in W \text{ per la definizone di sottospazio vettoriale}}\\
{\color{blue}\text{che abbiamo dato in precedenza.}}\\
{\color{blue}\text{Questo dimostra che }\mathscr{L}(A) \sube W. \checkmark}\\
{\color{blue}\mathscr{L}(A) \text{ è esso stesso un sottospazio vettoriale, infatti se}}\\
{\color{blue}\vec v=\lambda_1\vec v_1+...+\lambda_n\vec v_n\in \mathscr{L}(A) \text{ e }}\\
{\color{blue}\vec w=\lambda'_1\vec v'_1+...+\lambda'_n\vec v_m\in \mathscr{L}(A) \text{ allora abbiamo:}}\\
{\color{blue}\alpha\vec v+\beta \vec w=(\alpha\lambda_1)\vec v_1+...+(\alpha\lambda_n)\vec v_n+(\beta\lambda'_1)\vec v_1+..+(\beta\lambda'_m)\vec v_m}\\
{\color{blue}0\vec v=0'\vec v\ \ \forall\in A\Rightarrow0\vec v\in \mathscr{L}(A)\checkmark\ \ \ \ \square}

Proposizione

\text{Se }A\sube \mathscr{L}(B)\ \text{ allora }\mathscr{L}(A) \sube\mathscr{L}(B)  

Dimostrazione:

{\color{blue}\text{Se abbiamo }A\sube \mathscr{L}(B),\text{ allora }\mathscr{L}(B) \text{ è un sottospazio}}\\
{\color{blue}\text{che contiene }A,\text{ quindi }\mathscr{L}(A) \sube\mathscr{L}(B)  }\\
{\color{blue}\text{dalla proposizione precedente}\ \ \ \ \square}
{\color{blue}}

Teorema (Lemma di Steinitz)

\text{Sia }V\text{ un }\mathbb K-\text{spazio vettoriale. Siano }\vec v_1,...,\vec v_n \text{ vettori indipendenti di }V\\
\text{ e }\vec w_1,...,\vec w_m \text{ un insieme di generatori di }V.\text{ Allora  }n\leq m

Dimostrazione:

{\color{blue}\text{Sia }\vec v_1\text{ il più piccolo dei }\vec v_1,..,\vec v_n \ tc\ \vec v_1\ne0}\\
{\color{blue}\text{(sappiamo che esiste perchè stiamo considerando un sistema di vettori indipendenti)}}\\
{\color{blue}\text{Procediamo nella dimostrazione attraverso diversi passi:}}\\
\ \\
{\color{blue}\exist \lambda_1,...,\lambda_m\ tc\ \vec v_1=\lambda_1\vec w_1+...+\lambda_m\vec w_m\text{ dato che }V= \mathscr{L}(\vec w_1,...,\vec w_m)}\\
{\color{blue}\text{Supponiamo }\lambda_1\ne0 \ (\text{qualche  }\lambda \text{ deve essere }\ne0,\text{ altrimenti avrei }\vec v_1=0)}\\
{\color{blue}\vec w_1=\lambda^{-1}_1\vec v_1-\lambda^{-1}_1\lambda_2\vec w_2-...-\lambda^{-1}_1\lambda_m\vec w_m.}\\
{\color{blue}\text{Quindi }\vec w_1\in \mathscr{L}(\vec v_1,...,\vec w_m).}\\
{\color{blue}\text{Allora }\mathscr{L}(\vec w_1,...,\vec w_m)\sube\mathscr{L}(\vec v_1,...,\vec w_m)\sube V.}\\
{\color{blue}\text{Da questo abbiamo }V=\mathscr{L}(\vec v_1,...,\vec w_m)\ \ \ \ \checkmark}\\
\ \\
{\color{blue}\text{Sostituiamo di aver sostituito }\vec w_1,...,\vec w_i \text{ con  }\vec v_1,...,\vec v_i,\text{  con }i\geq1 \text{cioè supponiamo che }}\\
{\color{blue}\mathscr{L}(\vec v_1,...,\vec v_i,\vec w_{i+1},..,\vec w_m)= V\ \ \ \checkmark}\\
\ \\
{\color{blue}\text{Dimostriamo come si possano rinumerare i }\vec w \text{ rimanenti in modo } tc}\\
{\color{blue}\mathscr{L}(\vec v_1,...,\vec v_i,\vec v_{i+1}\vec w_{i+2},..,\vec w_m)= V:}\\
{\color{blue}\text{Consideriamo }\vec v_{i+1}=\lambda_1\vec v_1+...+\lambda_i\vec v_i+\lambda_{i+1}\vec w_{i+1}+...+\lambda_m\vec w_m.}\\
{\color{blue}\text{Almeno uno dei coefficienti }\lambda_{i+1},...\lambda_m \text{ è non nullo, dato che }\vec v_1,...,\vec v_n }\\
{\color{blue}\text{sono linearmente indipendenti.}}\\
{\color{blue}\text{Come prima supponiamo }\lambda_{i+1}\ne0.\text{ Allora }}\\
{\color{blue}\vec w_{i+1}=\lambda^{-1}_{i+1}\vec v_{i+1}-\lambda^{-1}_{i+1}\lambda_1\vec v_1-...-\lambda^{-1}_{i+1}\lambda_{i}\vec v_i-\lambda^{-1}_{i+1}\lambda_{i+2}\vec w_{i+2}-...-\lambda^{-1}_{i+1}\lambda_{m}\vec w_{m}}\\
{\color{blue}\text{Allora }\vec w_{i+1}\in\mathscr{L}(\vec v_1,...,\vec v_i,\vec v_{i+1}\vec w_{i+2},..,\vec w_m)}\\
{\color{blue}\Rightarrow\mathscr{L}(\vec v_1,...,\vec v_i,\vec v_{i+1}\vec w_{i+2},..,\vec w_m)=V\ \ \ \ \checkmark}\\
\ \\
{\color{blue}\text{Il procedimento continua finché non rimangono più vettori da sostituire.}}\\
{\color{blue}\mathscr{L}(\vec v_1,...,\vec v_i,\vec v_{n}\vec w_{n+1},..,\vec w_m)\Rightarrow n\leq m}\\
{\color{blue}\text{Infatti, supponendo per assurdo che }n > m \text{, ad un certo punto avremmo }}\\
{\color{blue}\text{come insieme di generatori } \mathscr{L}(\vec v_1,...,\vec v_m)\text{ e sarebbe possibile esprimere}}\\
{\color{blue}\vec v_j \text{ con }m+1\leq j \leq n \text{ come }\lambda_1\vec v_1+...+\lambda_m\vec v_m }\\
{\color{blue}\text{Assurdo, perchè }\vec v_1,...,\vec v_n \text{sono linearmente indipendenti }\checkmark \ \ \ \square}


Corollario (Equicardinalità delle basi)

\text{Supponiamo che }V\text{ sia finitamente generato }V=\mathscr{L}(\vec w_1,...,\vec w_m).\\
\text{Allora esistono basi finite di }V \text{ e queste hanno sempre lo stesso numero di elementi}.

Dimostrazione:

{\color{blue}\text{Sappiamo che esistano basi finite perché se } \vec w_1,...,\vec w_m \text{ sono generatori di }V. }\\
{\color{blue}\text{Da questo insieme possiamo estrarre una base grazie al teorema di esistenza delle basi}.}\\
{\color{blue}\text{Supponiamo che }\mathbb B(\vec v_1,...,\vec v_n ) \text{ e }\mathbb B'(\vec v'_1,...,\vec v'_n )\text{ siano due basi di }V, \text{ allora queste sono}}\\
{\color{blue}\text {sia un insieme di vettori indipendenti, sia un insieme di generatori. }}\\
{\color{blue}\text{Allora, dal lemma di Steinitz, abbiamo }n\leq m, \ m\leq n\Rightarrow n=m\ \ \ \square}

Grazie a questo corollario, possiamo chiamare la dimensione dello spazio vettoriale V il numero di elementi di una sua qualunque base.

Proposizione (Completamento della base)

\text{Siano }\vec v_1,...,\vec v_n \text{ un insieme di vettori indipendenti di }V  \text{e }\vec w_1,..,\vec w_m\\
\text{insieme di generatori di }V.\\
\text{Allora possiamo completare  }\vec v_1,...,\vec v_n\text{ a base di }V \text{ prendendo i vettori aggiuntivi di}\\
\vec w_1,..\vec w_n  

Dimostrazione:

{\color{blue}\text{Possiamo utilizzare lo stesso procedimento a scarti successivi che abbiamo utilizzato}}\\
{\color{blue}\text{nella dimostrazione del lemma di Steiniz, possiamo supporre } \vec v_1,...,\vec v_n,\vec w_1,...,\vec w_m }\\
{\color{blue}\text{un insieme di generatori.}}\\
{\color{blue}\text{Ora ci basta scegliere un insieme tra questi un insieme massimale di vettori indipendenti}}\\
{\color{blue}\text{che contenga anche }\vec v_1,..,\vec v_n \text{ ed avremo la base di }V \text{ cercata}\ \ \ \ \square}

Corollario

\text{Sia } \dim V=n \text{ e sia}\mathbb B=(\vec v_1,...,\vec v_n)\text{ insieme di vettori linearmente indipendenti.}\\
\text{Allora }\mathbb B \text{ è una base}.

Dimostrazione:

{\color{blue}\text{Consideriamo una base di }V \ \vec w_1,...,\vec w_n.}\\
{\color{blue}\text{col procedimento di scambio visto nelle dimostrazioni precedenti, otteniamo che anche} }\\
{\color{blue}\vec v_1,...,\vec v_n \text{ è una base di }V\ \ \ \ \ \ \square}

Corollario

\text{Sia }\mathbb B=(\vec v_1,..,\vec v_n )\text{ un insieme di generatori e sia }\dim V=n\\
\text{Allora }\mathbb B\text{ è una base di }V.

Dimostrazione:

{\color{blue}\text{Dato che }\mathbb B =(\vec v_1,...,\vec v_n) \text{ è un insieme di generatori, supponiamo}}\\
{\color{blue}\text{di estrarne una base }\vec v'_1,...,\vec v'_{n'}, \ tc \ n'\leq n.}\\
{\color{blue}\text{Ma per ipotesi sappiamo che }\dim V=n \text{ e, per come abbiamo definito la dimensione}}\\
{\color{blue}\text{di un sottospazio vettoriale, questo signfica che }}\\
{\color{blue}n=\#\text{elementi di una qualunque base di }V.}\\
{\color{blue}\text {Quindi }n=n' \text{ e non posso tralasciare alcun elemento di }\mathbb B}\\
{\color{blue}\Rightarrow \mathbb B \text{ è una base\ \ \ \ \ }\square}

Corollario

\text{Sia }W \text{ sottospazio di }V. \\
\text{Allora vale }\dim W\leq\dim V .\\
\text{Se inoltre supponiamo }\dim W=\dim V, \text{ allora }W=V

Dimostrazione:

 {\color{blue}\text{Supponiamo di avere }\dim W =n' \text{ e }\vec v_1,...\vec v_{n'} \text{ base di }W .}\\
{\color{blue}\text{Allora }\vec v_1,...,\vec v_{n'}\text{ è un insieme di vettori linearmente indipendenti per }V}\\
{\color{blue}\text{ quindi possiamo completare tale insieme a base di }V \Rightarrow n'\leq n\ \checkmark}\\
\ \\
{\color{blue}\text{Se avessimo }n'=n\text{ questo significherebbe che }\vec v_1,..,\vec v_{n'} \text{sarebbe già base di }V}\\
{\color{blue}\text{cioè }W=\mathscr{L}(\vec v_1,...,\vec v_{n'})=V\ \ \ \checkmark \ \ \ \square}

Spazio vettoriale

Uno spazio vettoriale è una struttura algebrica formata da diverse componenti:

  • Un insieme (i cui elementi sono vettori)
  • Un campo
  • Due operazioni lineari (somma e prodotto per uno scalare)

Rigorosamente abbiamo la definizione:

\text{ Sia }\mathbb K \text{ un campo e sia }V\text{un insieme con 0 un elemento fissato. Una struttura di}\\
\text{ campo vettoriale }V\text{ su }\mathbb K\text{ con elemento 0 dato da }0v \text{ è una coppia di operazioni}\\
\text{una interna ed una esterna}\\
+:V\times V\rightarrow V \ tc\ (V,0v,+)\ \ \text{sia un gruppo abeliano}\\
\cdot: \mathbb K\times V\rightarrow V\ \ \ \text{dove } (\lambda,\vec v) \mapsto\lambda\vec v\ \ \ \ (\text {operazione esterna})

Vediamo un esempio:

\text{Su  }\R\text{ visto come insieme agisce }(\R^n,0,+)\text{ come gruppo, i cui elementi si possono}\\
\text{indicare con }\vec v=(a_1,...,a_n) \\
\text{Operazione interna:}\\
+:\R^n\times \R^n\rightarrow\R^n\ \ \ \  (\vec a,\vec b)\mapsto\vec a +\vec b=(a_1+b_1,...,a_n+b_n)\\
\cdot: \R\times \R^n\rightarrow\R^n\ \ \ \ (\lambda,\vec v)\mapsto\lambda\vec v=(\lambda v_1,...,\lambda v_n)\\
\ \\
\text{Proprietà delle operazioni}:\\
\text{consideriamo }1\in\R, \ \vec v, \ \vec w\in \R^n,\lambda,\mu\in \R.\text{ Allora}\\
{\color{blue}1)}1\cdot\vec v=\vec v\\
{\color{blue}2)}\lambda(\mu\vec v)=(\lambda\mu)\vec v\\
{\color{blue}3)}(\lambda+\mu)\vec v=\lambda\vec v+\mu\vec w\\
{\color{blue}4)}\lambda(\vec v+\vec w)=\lambda\vec v+\lambda\vec w\\
\ \\

Combinazione lineare di vettori:

\text{Dati gli scalari }\lambda_1,...,\lambda_n \in \mathbb K \text{ ed i vettori }\vec v_1,..,\vec v_n \in V \\
\text{si definisce cominazione lineare  di }\vec v_1,...,\vec v_n \text{ con coefficienti }\lambda_1,...,\lambda_n\text{ l'espressione}\\
\lambda_1\vec v_1+...+\lambda_n\vec v_n 

Dipendenza lineare:

\text{Una n-pla di vettori }\vec v_1,...,\vec v_n \text{ con }\vec v_i \in V\text{ si dice  linearmente dipendente se}\\
\exist \lambda_1...\lambda_n\in \mathbb K \ tc\\
(\lambda_1,...,\lambda_n)\ne (0,..,0) \ \ \ \ \text{ e }\ \ \  \lambda_1\vec v_1+...+\lambda_n\vec v_n=0

Cosa significa geometricamente la dipendenza lineare tra due vettori non nulli?

Due vettori non nulli sono linearmente dipendenti se sono proporzionali, cioè si trovano sulla stessa retta.

Da questo possiamo dedurre che lo spazio di dimensione minima in grado di contenere due vettori linearmente dipendenti è la retta, mentre se consideriamo due vettori linearmente indipendenti dobbiamo considerare almeno il piano.

Base di uno spazio vettoriale:

\text{Una n-pla di vettori } \vec v_1,...,\vec v_n  \text{ si dice base di }V \text{se}\\
\forall \vec v \in V \exist! \lambda_1,...,\lambda_n \in \mathbb K \ tc\ \vec v=\lambda_1\vec v_1+...+\lambda_n \vec v_n

Osserviamo che, in generale, uni spazio vettoriale ha infinite basi diverse.

Vediamo qualche esempio:

{\color{blue}1)}V=\{0\vec v\}\text{ non ha basi. Questo perché}\\
0\vec v=\lambda 0\vec v \ \forall\lambda\ \text{ cioè non è unico!}\\
\ \\
{\color{blue}2)}\text{Consideriamo }V=\mathbb K^1=\mathbb K\\
\text{Sia }v \in V,  v\ne0. \text{ Allora }\mathbb B=( v) \text{ è base di }V\\
\text{Infatti }\forall   w\in V \text{abbiamo }  w=\lambda v \text{ con }\lambda= v^{-1}  w \\
\text{Dove sappiamo che esiste } v^{-1} ,\text{ dato che }  v\ne0\\
\ \\
{\color{blue}3)}\text{Consideriamo }V=\Z/2=\{[0],[1]\} \\
 \text{in questo caso abbiamo un'unica base dato che }[1] \text{ è l'unico elemento }v\ne0\\
\ \\
{\color{blue}4)}\text{Consideriamo }V=\mathbb K ^2=\{(x,y)|x,y \in \mathbb K\}\\
\text {abbiamo infinite basi, ma quella che utilizzeremo più spesso è la base canonica}\\
 \mathcal{E}=(e_1,e_2), \text{dove }e_1=(1,0), \ e_2=(0,1).\\
\text{In generale per ottenere una base ci basta considerare due vettori}\\
\text{ linearmente indipendenti}\\
\ \\

Consideriamo un ultimo esempio:

\text{Come ultimo esempio consideriamo:}\\
\mathbb K \text{ un campo, }\mathbb K[x]=\text{polinomio di variabile  } x \text{ con coefficienti in }\mathbb K \\
\{a_0+a_1x+...+a_nx^n|n\in \N,a_i\in \mathbb K\}\\
\text{Vediamo come questo campo, insieme all'operazione interna data dalla somma tra }\\
\text{ i polinomi e all'operazione esterna data dalla moltiplicazione di un polinomio}\\
\text{per un elemento }c\in \mathbb K\\
\text{Consideriamo}\\
p(x)=a_0+a_1x+...+a_nx^n\\
q(x)=b_0+b_1x+...+b_nx^n\\
c\in \mathbb K\\
(p+q)(x)=(a_0+b_0)+(a_1+b_1)x+...\ \ \ \ \in \mathbb K[x] \ \checkmark\\
c\cdot p(x)=c\cdot a_0+c\cdot a_1x+.....\in \mathbb K[x]\ \ \checkmark\\
\text{Quuindi }\mathbb K[x] \text{ è uno spazio vettoriale}

Per quanto riguarda la base per questo spazio vettoriale diamo la

Proposizione

\mathbb K[x] \text{ non ha base finita}

Dimostrazione:

{\color{blue}\text{Si fa per assurdo:  sia }\mathbb B=(p_1(x),...,p_n(x))\text{ un'ipotetica base finita di }\mathbb K[x]}\\
{\color{blue}\text{Sia }\deg p(x)=\max\{i|p(x)=a_0+a_1x+...+a_nx^n, a_i\ne0\}}\\
{\color{blue}\text{e sia }M =\max\{\deg \ p_1,...,\deg \ p_n\}\text{ che quindi sarà il grado massimo della }}\\
{\color{blue}\text{combinazione lineare della base.}}\\
{\color{blue}\text{Questo significa che possiamo scrivere }}\\
{\color{blue}p_1(x)=a_{1,0}+a_{1,1}x^1+...+a_{1,M}x^M}\\
{\color{blue}p_2(x)=a_{2,0}+a_{2,1}x^1+...+a_{2,M}x^M}\\
{\color{blue}\colon}\\
{\color{blue}p_n(x)=a_{n,0}+a_{n,1}x^1+...+a_{n,M}x^M}\\
{\color{blue}\text{dove qualunque }a_{i,j} \text {potrebbe essere =0}}\\
{\color{blue}\text{Allora, per come abbiamo definito la base, ogni }p(x) \text{deve essere combinazione}}\\
{\color{blue}\text{lineare  di }p_1(x),...,p_n(x), \text{ cioè }} 
{\color{blue}p(x)=\lambda_1p_1(x)+\lambda_2p_2(x)...+\lambda_np_n(x)=}\\
{\color{blue}=(\lambda_1a_{1,0}+...+\lambda_na_{n,0})+(\lambda_1a_{1,1}+...+\lambda_2a_{n,1})x+...+(\lambda_n a_{1,M}+...+\lambda_na_{n,M})x^M}\\
{\color{blue}\text{Da questo si vede che }\deg p(x)\leq M}\\
{\color{blue}\text{Ma allora, se prendiamo un polinomio di grado  }>M, \text{ questo non  potrà}}\\
{\color{blue}\text{essere generato dai } p_1,...p_n.}\\
 {\color{blue}\text{ Assurdo per come abbiamo definito una base}\ \ \ \ \ \square}
\text{Un esempio di base infinita per i polinomi potrebbe essere :}\\
\mathbb B=\{1,x,x^2,...,x^n,...\}

Come possiamo estendere la definizione di base ad un caso infinito?

\text{Una famiglia indicizzata }\mathbb B=\{\vec v_i|i\in I\} \text{ di  vettori di } V \text{si dice una base}\\
\text{ per } V \text{ se }\forall x\ne0,\vec v\in V,\exist!n\in \N \ i_1,...i_n \in I, \lambda_1,...,\lambda_n\in \mathbb K \ tc\\
\vec v=\lambda_1v_{i_1}+...\lambda _n\vec v_{i_n}\\
\text{In pratica stiamo chiedendo che qualunque vettore } \vec v \text{ possa essere scritto in modo}\\
\text{unico come combinazione lineare di un numero finito di elementi della base }\mathbb B

Come ultima definizione, vediamo la differenza tra una base ed un insieme di generatori:

\text{Una famiglia indicizzata }\mathbb B=\{\vec v_i|i\in I\} \text{ di  vettori di } V \text{si dice un  }\\
\text{ insieme di genaroti per } V \text{ se }\forall \vec v\  \in V\  \exist \lambda_1,...\lambda_n \in \mathbb K \ tc\\
\vec v=\lambda_1\vec v_{i_1}+...+\lambda_n\vec v_{i_n}\\
\text{La differenza tra basi e generatori è sull'unicità nella scrittura:}\\
\text{nel caso delle basi i }\lambda_i \text{ sono unici, mentre nel caso dei generatori}\\
\text{non lo sono.}

Vediamo qualche proprietà delle basi:

Teorema (esistenza di una base)

\text{Sia }V \text{ un }\mathbb K \text{-spazio vettoriale e sia }A \text{ un insieme di generatori di }V.\\
\text{Allora esiste una base }\mathbb B\sube A.\\
\text{In particolare, se poniamo }V=A \text{ abbiamo l'esistenza di una base per }V

Dimostrazione:

{\color{blue}\text{Consideriamo l'insieme }X=\{\mathbb B\sube A|\mathbb B\text{ è indipendente}\}}\\
{\color{blue}\text{e definiamo l'ordinamento per inclusione }\leq \text{ su }X \text{ come}}\\
{\color{blue}\mathbb B\leq \mathbb B' \Rightarrow \mathbb B \sube\mathbb B'}\\
{\color{blue}\text{Vogliamo applicare all'insieme }X \text{ il lemma di Zorn: }}\\
{\color{blue}\text{verifichiamo che se }C\sube X \text{ è una catena, cioè un sottoinsieme completamente}}\\
{\color{blue}\text{completamente ordinato, allora }C \text{ ammette maggioranti.}}\\
{\color{blue}\text{Dato }C\sube X, \text{consideriamo }\mathbb B_C=\underset{\mathbb B\in C}{\cup}\mathbb B, \text { allora ogni }\mathbb B\in C \text{ è }\mathbb B\sube\mathbb B_C.}\\
{\color{blue}\text {Dimostriamo che }\mathbb B_C\in X \text{, cioè che }\mathbb B_C\text{ è un insieme indipendente: }}\\
{\color{blue}\text{siano  }\vec v  _1,...,\vec v_n\in \mathbb B_C,\text{ allora possiamo dire che }}\\
{\color{blue}\exist\  \mathbb B_1,...,\mathbb B_n \text{ elementi di  }C \ tc \ \vec v_1\in \mathbb B_1,...\vec v_n \in\mathbb B_n}\\
{\color{blue}\text{osserviamo che }\mathbb B_1,...\mathbb B_n \text{ sono tutti confrontabili fra loro poichè }\mathbb B_i \in C }\\
{\color{blue}\text{ e } C,\leq \text{ è una catena.}}\\
{\color{blue}\text{A meno di riordinare gli indici, possiamo supporre che }\mathbb B_1\leq\mathbb B_2\leq...\leq\mathbb B_n.}\\
{\color{blue}\text{Allora  }\vec v_1,...,\vec v_n\in \mathbb B_n. }\\
{\color{blue}\text{Poichè }\mathbb B_n\in C\sube X, \mathbb B_n \text{ è indipendente, quindi }\vec v _1,...,\vec v_n \text{ sono indipendenti.}}\\
{\color{blue}\text{Quindi abbiamo ottenuto che } \vec v_1,...,\vec v_n \text{ distinti, scelti a piacere, in }}\\
{\color{blue}\mathbb B_C \text{ sono indipendenti} \Rightarrow \mathbb B_C \text{ è indipendente per costruzione.}}\\
{\color{blue}\text{Inoltre, ogni catena }C \sube X \text{ ha dei maggioranti}\Rightarrow \text{per il lemma di Zorn}}\\
{\color{blue}\text{ammette massimali. Sia }\mathbb B\in X \text{un insieme di vettori indipendenti }}\\
{\color{blue}\text{tale che sia massimale e contenuto in }A}\\
{\color{blue}\text{Allora }\mathbb B\text{ è base di }V \text {estratta dall'insieme }A\ \ \ \ \ \square}

Proposizione (massimalità delle basi)

\text{Se }\mathbb B\text{ è una base di vettori di  }V \text{ e }\mathbb B'  \text{ è un insieme di vettori indipendenti }\\
tc \ \mathbb B\sube \mathbb B'\text{, allora   }\mathbb B =\mathbb B'.

Dimostrazione:

{\color{blue}\text{Dividiamo la dimostrazione in due parti:}}\\
\ \\
{\color{blue}1)\text{Sia }\mathbb B\text { una base di } V, \text{ allora dimostriamo che }\mathbb B \text{ è un insieme}}\\
{\color{blue}\text{ indipendente e massimale tra le famiglie indipendenti}.}\\
\ \\
{\color{blue}\text{Iniziamo mostrando la parte più immediata: l'indipendenza in }\mathbb B. }\\
{\color{blue}\text{Per come abbiamo definito una base abbiamo}} \\
{\color{blue}0\vec v=\lambda_1\vec v_{1_i}+...+\lambda_{n_i} \text{con i }\lambda_i \text{unici}}\\
{\color{blue}\Rightarrow \lambda_1=\lambda_2...=\lambda_n=0\ \forall\vec v_i \in \mathbb B.}\\
{\color{blue}\text{Ma questa è esattamente la condizione per l'indipendenza}\Rightarrow }\\
{\color{blue}\mathbb B \text{ è composto da vettori linearmente indipendenti}\ \ \ \ \checkmark}\\

\ \\
{\color{blue}\text{Consideriamo quindi } \mathbb B\sube\mathbb B', \text{ con }\mathbb B \text{ indipendente}.}\\
{\color{blue}\text{Se fosse }\mathbb B \subsetneqq \mathbb B',\text{allora sia }\vec v \in \mathbb B'\setminus\mathbb B.\text{ Poiché }\mathbb B \text{ è base, allora devono esistere } }\\
{\color{blue}\text{ dei vettori: } \{ \vec v_{1_i},...,\vec v_{n_i}\}\in\mathbb B \text{ e }\lambda_1...\lambda_n\in\mathbb K \ tc }\\
{\color{blue}\vec v=\lambda_1\vec v_{1_i}+...+\lambda_{n_i}\Rightarrow 1\cdot\vec v-\lambda_1\vec v_{1_i}-...-\lambda_{n_i}=0\Rightarrow }\\
{\color{blue}1\cdot\vec v-\lambda_1\vec v_{1_i}-...-\lambda_{n_i}\in\mathbb B'}\\
{\color{blue}\text{ma questo contraddice l'indipendenza di }\mathbb B'. \ \ \ \ \ \checkmark }\\
\ \\
{\color{blue}\text{Abbiamo dimostrato il punto }1)}\\
\ \\
{\color{blue}\text{Ora  scambiamo iporesi e tesi:}}\\
\ \\
{\color{blue}2)\text{Sia }\mathbb B \text{ una famiglia  indipendente e  massimale di }\vec v }\\
{\color{blue}\text{allora }\mathbb B\text{  è una base }}\\
\ \\
{\color{blue}\text{Supponiamo }\vec v=0\vec v, \text{ con }\vec v\in \mathbb B\text{ questo implica che, se}}\\
{\color{blue}\vec v=\lambda_1\vec v_{i_1}+...+\lambda_n\vec v_{i_n}\Rightarrow \lambda_1=...=\lambda_n=0 \text{ per l'indipendenza di }\mathbb B\Rightarrow }\\
{\color{blue}\text{in questo caso abbiamo l'unicità dei }\lambda_i \ \ \ \ \checkmark}\\
{\color{blue}\text{Se, al contrario, }\vec v\ne0\vec v\text{, allora }\vec v\in \mathbb B\text{ oppure }\vec v\text{ combinazione lineare di elementi di }\mathbb B}\\
{\color{blue}\text{Infatti, se valesse }\vec v\notin\mathbb B, \text{ avremmo }\mathbb B'=\mathbb B\cup\{\vec v\}}\\
{\color{blue}\text{Ma questo insieme }\mathbb B' \text{ non può essere indipendente, dato che per ipotesi}}\\
{\color{blue}\mathbb B \text{è insieme massimale fra le famiglie indipendenti}\Rightarrow}
{\color{blue}\exist \lambda\vec v+\lambda_1\vec v_{i_1}+...+\lambda_n \vec v _{i_n}=0}\\
{\color{blue}\text{con la n-pla }(\lambda_1,...,\lambda_n)\ne(0,...,0)}\\
{\color{blue}\text{Se fosse }\lambda=0\Rightarrow (\lambda_1,...,\lambda_n)\ne0\text{ e    varrebbe }\lambda_1\vec v_{i_1}+...+ \lambda_n\vec v _{i_n}=0}\\
{\color{blue}\text{che sarebbe assurdo dato che per ipotesi i vettori di }\mathbb B \text{sono linearmente indipendenti}.}\\
{\color{blue}\text{Dunque deve valere }\lambda\ne0\Rightarrow \vec v=-\lambda^{-1}\lambda_1\vec v_{i_1}-...-\lambda^{-1}\lambda_n\vec v_{i_n}\Rightarrow}\\
{\color{blue} \vec v \text{ è combinazione lineare di elementi di }\mathbb B.}\\
{\color{blue}\text{Questo quindi comporta che }\mathbb B \text{ sia un insieme di generatori per }V.}\\
{\color{blue}\text{Per concludere la parte due della dimostrazione ci basta dimostrare che ogni espressione}}\\
{\color{blue}\vec v=\lambda_1\vec v_{i_1}+...+ \lambda_n\vec v _{i_n}, \text{ con }(\vec v_{i_1},...,\vec v_{i_n}) \in \mathbb B\text{è unica.}}\\
{\color{blue}\text{ Se per assurdo avessimo due espressioni per indicare tale vettore, otterremmo}}\\
{\color{blue}\lambda_1\vec v_{i_1}+...+ \vec v _{i_n}=\mu_1\vec v_{i_1}+...+ \mu_n\vec v _{i_n}}\\
{\color{blue}\text{varrebbe }(\lambda_1-\mu_1)\vec v_{i_1}+...+ (\lambda_n-\mu_n)\vec v _{i_n}=0\vec v}\\
{\color{blue}\text{Ma allora, per l'indipendenza di }\mathbb B \text{ otterremmo}}\\
{\color{blue}(\lambda_1-\mu_1)=...=(\lambda_n-\mu_n)=0\Rightarrow \lambda1=\mu_1,...,\lambda _n=\mu_n\Rightarrow \mathbb B \text{ è una base }\ \ \ \checkmark}\\
\ \\
{\color{blue}\text{Da questo otteniamo la tesi della nostra proposizione, dato che abbiamo dimostrato }} \\
{\color{blue}\text{che una base è un insieme massimale di vettori linearmente indipendenti e che} }\\
{\color{blue}\text{ se anche  }\mathbb B' \text{ lo è, allora deve essere a sua volta una base. }}\\
{\color{blue}\text{Ma se }\mathbb B\sube \mathbb B'\text{ allora l'unica possibilità è proprio che le due basi coincidano }\ \ \square}

Strutture algebriche

Vediamo i principali esempi di queste strutture algebriche ovvero insiemi dotati di operazioni

  • Operazione interna su X: è una funzione
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\}

Vediamone qualche esempio di operazione interna:

{\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)}
  • Operazione esterne di un insieme X su un insieme Y: è un’applicazione
\alpha: X\times Y\rightarrow Y\\
(x,y)\mapsto\alpha(x,y)\in Y \text{ dove }x\in X, y\in Y

Vediamo qualche esempio di operazione esterna:

{\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
  • Monoide
\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}\\

Esempi di monoidi:

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}\\
  • Gruppo
\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}

Proposizione

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

Dimostrazione:

{\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}

Esempi di gruppi:

{\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}\\

Osserviamo come in tutti gli esempi precedenti nei gruppi vale anche la proprietà commutativa. In questo caso si parla di gruppi abeliani.

Esempio di gruppo non abeliano

\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}

Teorema

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

Dimostrazione:

{\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}
  • Anello
\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\\

Un anello è commutativo se lo è il suo monoide

(A,1,\cdot)

Esempi di anelli commutativi:

{\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}\\
Rappresentazione geometrica della somma tra le classi di equivalenza
  • Campo
\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

Esempi di campi:

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

Teorema

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

Dimostrazione:

{\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}

Classi di relazioni

Dati due insiemi A e B studiamo i principali tipi di relazioni

\mathscr{R}\sube A\times B
  • Relazioni di ordinamento: sono relazioni dall’insieme A ad stesso A
\mathscr{R}\sube A\times A

Abbiamo un ordinamento parziale se valgono le seguenti proprietà

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)}

In particolare un ordinamento parziale è un ordinamento totale se vale anche che

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

ovvero tutti gli elementi sono confrontabili tra loro.

Un altro caso particolare è un buon ordinamento se è un ordinamento parziale e vale che

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

In particolare anche A ha un minimo.

Vediamo qualche esempio: per i numeri naturali la relazione

\leq

è un ordinamento totale.

Inoltre è anche un buon ordinamento.

Dimostrazione:

{\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}

Se vogliamo un esempio di ordinamento non totale possiamo considerare

\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)

Questa non è una relazione d’ordine totale perché non tutti gli elementi sono confrontabili tra loro (ci basti pesare a due numeri primi tra loro come 3 e 7).

Ora che abbiamo gli ordinamenti, definiamo i minimali e i massimali:

\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\\

In una relazione d’ordine totale il minimale è detto minimo mentre il massimale è detto massimo.

Graficamente possiamo visualizzare la differenza come:

Minimali e minimi
  • Relazioni di equivalenza: sono relazioni dall’insieme A ad A stesso
\mathscr{R}\sube A\times A

per cui valgano le proprietà:

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)}

Relazioni e funzioni

Consideriamo due insiemi A e B.

Una relazione tra gli elementi di A e B è un sottoinsieme

\mathscr{R}\sube A \times B

del prodotto cartesiano.

Una funzione è un tipo particolare di relazione definita il grafico

\Gamma f\sube A \times B

tale che

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

In questo caso indichiamo la funzione con

f:A\rightarrow B

e chiamiamo A dominio e B codominio.

Proprietà delle funzioni:

Diciamo che una funzione f è

  • Iniettiva se
x\neq y\Rightarrow f(x)\neq f(y) \forall\ x,y\in A
  • Suriettiva se
\forall\  y\in B\ \exist \ x\in A \ tc\ f(x)=y

Composizione tra funzioni:

Siano date due funzioni

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

la composizione tra f e g è la funzione

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

Una funzione f si dice biunivoca o biiettiva se

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

Ve\diamo una prima proposizione

Proposizione

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

Dimostrazione

{\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} 

Vediamo le proprietà della composizione delle funzioni

  • IdA è l’elemento neutro della composizione
  • Vale la proprietà associativa, cioè
(f\circ g)\circ h= f\circ(g\circ h)
  • Non vale la proprietà commutativa