Lemma di scambio e induzione

Messaggioda marco2132k » 21/07/2019, 14:18

Ciao. Generi \( A=\left\{v_1,\dots,v_n\right\} \) lo spazio vettoriale \( V \), e sia \( B=\left\{w_1,\dots,w_r\right\} \) linearmente indipendente. Allora \( r\leqq n \).

Dimostrazione. L'idea è di provare che \( A^{'}=\left\{w_1,v_2,\dots,v_n\right\} \), \( A^{''}=\left\{w_1,w_2,v_3\dots,v_n\right\} \), ecc. generano ancora lo spazio. Una volta provato che \( \langle A'\rangle=V \), discende \( \langle A^{''}\rangle=V \), e così via.

Ciò che non riesco a formalizzarmi è il "e così via": ho sempre glissato su questa cosa, ma... non mi convince.

Evito di esporre i miei ragionamenti (riformulare in qualche modo l'enunciato), tanto non li legge nessuno :-)
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 324 di 2053
Iscritto il: 18/02/2018, 23:52

Re: Lemma di scambio e induzione

Messaggioda Cantor99 » 21/07/2019, 15:02

Dovrebbe essere il lemma di Steinitz giusto?
Prova a leggere qui https://it.wikipedia.org/wiki/Lemma_di_Steinitz
Cantor99
Senior Member
Senior Member
 
Messaggio: 526 di 1238
Iscritto il: 06/08/2017, 10:52
Località: Dragoni

Re: Lemma di scambio e induzione

Messaggioda marco2132k » 21/07/2019, 16:00

Grazie per la risposta! È esattamente ciò che ho provato a fare io.

Occorre che io provi che per ogni spazio vettoriale \( n \)-generato \( V \), un insieme (finto1) linearmente indipendente ha cardinalità \( r \) non maggiore di \( n \). A occhio, procederei per induzione sul numero di vettori linearmente indipendenti. Il caso \( r=0 \) è banalmente verificato. Sia il claim vero per un naturale \( r>0 \) (sto cioè supponendo che per ogni spazio \( n \)-generato \( V \), ogni insieme finito linearmente indipendente abbia cardinalità minore di \( n \)); considerati \( r+1 \) vettori \( w_{1}^{'},\dots,w_{r+1}^{'} \) linearmente indipendenti, assumere \( r+1>n \) è contraddittorio: abbiamo infatti che esiste almeno un \( w_i^{'} \) tra costoro, tale che \( w_i^{'}=\sum_{j\neq i}\alpha_jv_j \), con ovvio significato dei simboli, dove i \( v_i \) sono i suddetti generatori. Ordunque, per considerazioni di servizio, \( \langle \left\{w_i\right\}\cup\left\{v_j\right\}_{j\neq i}\rangle \) è proprio lo spazio, che si rivela così generato da \( n \) elementi. \( \square \)

La domanda iniziale si può quindi rifrasare come (ed è di fatto quello che volevo chiedere): "È un argomento simile a quello di cui sopra ad essere adoperato ogniqualvolta capitino scritte come `iterando il procedimento \( n \) volte si ottiene come insieme di generatori [...]', che compaiono ad esempio nel link sul lemma di Steinitz?"

Note

  1. Si dimostrerà poi che se \( V \) è finitamente generato, anche ogni insieme linearmente indipendente deve essere finito.
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 325 di 2053
Iscritto il: 18/02/2018, 23:52

Re: Lemma di scambio e induzione

Messaggioda Cantor99 » 21/07/2019, 17:17

Premetto che forse non ho capito fino in fondo la domanda e non so se posso rispondere nel modo più corretto.

In ogni caso, il procedimento di iterare affonda le sue radici nel principio di induzione. Definiamo questa funzione
\[
P : \mathbb{N}_{0}\to \{vero,falso\} \qquad P(r)="\mbox{$\forall S_{r}\subset V_{n}$ l.i, $|S_{r}|=r$ $\Rightarrow$ $r\le n$}"
\]
dove $S_{r}$ è un sistema di vettori e $V_{n}$ è uno spazio vettoriale $n$-dimensionale. Abbiamo $P(0)=\mbox{vero}$ e $P(r)=\mbox{vero}$ ogniqualvolta $P(r-1)=\mbox{vero}$: però, come hai mostrato, $P(r)=\mbox{falso}$ per ogni $r\ge n+1$. Pertanto si è pensato bene di procedere per assurdo e fare uso del principio di induzione.

Dovrebbe essere l'idea opposta della discesa all'infinito https://it.wikipedia.org/wiki/Discesa_infinita
Cantor99
Senior Member
Senior Member
 
Messaggio: 528 di 1238
Iscritto il: 06/08/2017, 10:52
Località: Dragoni

Re: Lemma di scambio e induzione

Messaggioda marco2132k » 21/07/2019, 18:02

Sì, posto \( P(r) \) (o \( P(r-1) \), è lo stesso ovviamente) vero, ho provato che assumere \( P(r+1)=\text{falso} \) genera un assurdo.

Non conoscevo la "discesa all'infinito", grazie per la segnalazione. Mi sembra interessante, provo a pensarci un attimo.
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 326 di 2053
Iscritto il: 18/02/2018, 23:52

Re: Lemma di scambio e induzione

Messaggioda marco2132k » 22/07/2019, 15:59

Voglio un attimo chiarire quel
marco2132k ha scritto:Si dimostrerà poi che se \( V \) è finitamente generato, anche ogni insieme linearmente indipendente deve essere finito


Sia \( V \) uno spazio vettoriale finitamente generato. Dico che un sottoinsieme \( A\subset V \) (eventualmente infinito) è linearmente indipendente se per ogni \( v\in A \) è \( v\not\in\langle A\setminus\{v\}\rangle \).

Allora vale la cosa in giallo. Dimostrazione. Sia \( A \) un sottoinsieme infinito e linearmente indipendente di uno spazio \( V \) finitamente generato da \( m \) vettori. Non è difficile far vedere che anche ogni parte finita di \( A \) è linearmente indipendente; e di qui si ricava un assurdo, perché ogni insieme infinito contiene, per ogni \( n\in\mathbb{N} \), un sottoinsieme di \( n \) elementi. \( \square \).

La mia domanda è, ora: è superflua una tale proposizione? Che detto meglio vuol dire: ciò che viene provato discende in qualche modo che mi sfugge da un altro dei tanti teoremini sul numero di elementi di sottospazi, basi, ecc. che compaiono in un libro di algebra lineare?
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 327 di 2053
Iscritto il: 18/02/2018, 23:52

Re: Lemma di scambio e induzione

Messaggioda marco2132k » 28/07/2019, 23:49

Ci ho riflettuto un attimo, sulla dimostrazione del lemma di scambio, e sono giunto alla gaia conclusione che probabilmente domenica scorsa ero sballato. Credo sia doveroso riportare quella corretta.

Proposizione (Lemma di scambio). Sia \( V \) uno spazio vettoriale finitamente generato sul campo \( C \), da un insieme \( \left\{v_1,\dots,v_n\right\} \) di \( n \) vettori. Allora, ogni sottoinsieme \( \left\{w_1,\dots,w_r\right\}\subset V \) di \( r>m \) elementi è linearmente dipendente.
Dimostrazione. L'idea è di procedere per assurdo, assumendo i \( w_1,\dots, w_r \) linearmente indipendenti, per un \( r>n \). Un generatore \( v_i \) appartiene, in tal caso, allo spazio generato da \( w_1 \) e dai vettori \( v_j \), per \( j\neq i \); a meno di una permutazione degli indici, tale vettore è \( v_1 \). Come d'altronde ogni dimostrazione di questo fatto avanza, ne deriva che l'insieme \( \left\{w_1,v_2,\dots,v_n\right\} \) è un genratore. Nella nostra ipotesi, conviene infatti che si dimostri che \( V \) è ancora generato, per ogni \( 1\leqq k<m \), da un insieme \( \left\{w_1,\dots,w_k,v_{k+1},\dots,v_m\right\} \). Più formalmente, quello che conviene dimostrare è che, per ogni naturale \( k \), se vale la catena di disuguaglianze \( 1\leqq k<m \), i vettori \( w_1\dots,w_k,v_{k+1},\dots,v_m \) ancora generano lo spazio (è un'affermazione sensata, ché i vettori dell'insieme che qui è assunto linearmente indipendente, sono in numero maggiore dei generatori). L'ipotesi per \( k=1 \) già è stata confermata. Se la cosa regge per un \( k \) naturale qualunque, sarà lecito scrivere il vettore \( w_{r+1} \) come
\[
w_{r+1}=\sum_{i=1}^k\alpha_iw_i+\sum_{i=k+1}^n\beta_iv_i
\] per \( \alpha_1,\dots,\alpha_k \) e \( \beta_{k+1},\dots,\beta_n \) elementi di \( C \). Un coefficiente \( \beta_i \) sarà non nullo per considerazioni di servizio, e la conclusione di tale fatto1 è l'appartenenza del vettore \( v_{k+1} \) allo span di \( w_1,\dots,w_{k+1}, v_{k+2},\dots,v_n \). Una contraddizione sembra seguire da sola. \( \square \)

Note

  1. Nel linguaggio dei post, funzione \( P\colon\mathbb{N}\to\left\{\mathrm{vero},\mathrm{falso}\right\} \) che \[ P\colon k\mapsto\begin{cases}\mathrm{vero}&\text{se $ 1\leqq k<n\implies \langle w_1,\dots,w_k,v_{k+1}\dots,v_n\rangle=V $}\\ \mathrm{falso}&\text{altrimenti}\end{cases} \] ha per immagine \( \left\{\mathrm{vero}\right\} \), ed è stato provato per induzione
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 334 di 2053
Iscritto il: 18/02/2018, 23:52


Torna a Geometria e algebra lineare

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite