Monoidi e induzione
Salve a tutti, sto studiando per l'esame di matematica discreta e mi sono bloccato su metà esercizio. La traccia è la seguente:
Sia $(S, \cdot )$ un monoide, e sia $x$ un elemento di $S$. Provare per induzione che $\forall n,m \in N \cup {0}$ risulta:
(1) $x^m x^n = x^(m+n)$
(2) $(x^m)^n = x^(mn)$
Per il punto (1) ho proceduto nel seguente modo:
Passo base: $m=n=0$ ed è banalmente verificato
Ipotesi induttiva : $x^(m-1) x^(n-1) = x^((m-1)+(n-1)) \Rightarrow x^m x^n = x^(m+n)$
Passo induttivo: $x^m x^n = x^(m+n) \Rightarrow (x^(m-1) x)(x^(n-1) x) = x^((m-1)+(n-1)) x^2$
A questo punto spiego che $x^(m-1) x^(n-1) = x^((m-1)+(n-1)) $ è vera per ipotesi induttiva e
$x x = x^2 $ è banalmente verificato.
Per il punto (1) non sono molto sicuro mentre per il punto (2) non so come procedere, qualcuno potrebbe darmi una mano gentilmente?
Ringrazio tutti in anticipo
Sia $(S, \cdot )$ un monoide, e sia $x$ un elemento di $S$. Provare per induzione che $\forall n,m \in N \cup {0}$ risulta:
(1) $x^m x^n = x^(m+n)$
(2) $(x^m)^n = x^(mn)$
Per il punto (1) ho proceduto nel seguente modo:
Passo base: $m=n=0$ ed è banalmente verificato
Ipotesi induttiva : $x^(m-1) x^(n-1) = x^((m-1)+(n-1)) \Rightarrow x^m x^n = x^(m+n)$
Passo induttivo: $x^m x^n = x^(m+n) \Rightarrow (x^(m-1) x)(x^(n-1) x) = x^((m-1)+(n-1)) x^2$
A questo punto spiego che $x^(m-1) x^(n-1) = x^((m-1)+(n-1)) $ è vera per ipotesi induttiva e
$x x = x^2 $ è banalmente verificato.
Per il punto (1) non sono molto sicuro mentre per il punto (2) non so come procedere, qualcuno potrebbe darmi una mano gentilmente?
Ringrazio tutti in anticipo
Risposte
Ti conviene fare una induzione per volta, per esempio prima su $m$ e poi su $n$.
Devi fare una qualche forma di doppia induzione, se devi dimostrare che (1) e (2) sono veri per ogni \(m,n\in\mathbb N\): questo avviene dividendo l'induzione in due parti: \(P(m,n)\) la proprietà che devi dimostrare. Allora, fissa $n$ e fai induzione su $m$, cioè mostra che \(P(0,n)\) è vera, e che se è vera \(P(k,n)\) per ogni \(k < m\), è vera anche \(P(m,n)\). Poi fai induzione su \(n\), mostrando che \(P(m,0)\) è vera, e che se è vera \(P(m,k)\) per ogni \(k
Oppure, puoi procedere più formalmente come segue: sia \(P(m,n)\) la proprietà che devi dimostrare; definisci una relazione \(\preceq\) sul prodotto \(\mathbb N\times\mathbb N\) ponendo che \(\langle k,\ell\rangle\preceq\langle m,n\rangle\) se e solo se \(kordine lessicografico)
Ora, se dimostri che \(\preceq\) è un buon ordine su \(\mathbb N\times\mathbb N\) (lo è, perché si può dimostrare più in generale che se \(P,Q\) sono insiemi bene ordinati, tale è il loro prodotto lessicografico), supponendo che \(B=\{\langle m,n\rangle\in\mathbb N\times\mathbb N:\neg P(m,n)\}\ne\varnothing\), per la proprietà di buon ordine \(B\) deve avere un elemento \(\preceq\)-minimale \(\langle m,n\rangle\): da qui puoi trovare una contraddizione perché datone uno deve esisterne un altro, e un altro, e un altro...
Oppure, puoi procedere più formalmente come segue: sia \(P(m,n)\) la proprietà che devi dimostrare; definisci una relazione \(\preceq\) sul prodotto \(\mathbb N\times\mathbb N\) ponendo che \(\langle k,\ell\rangle\preceq\langle m,n\rangle\) se e solo se \(k
Ora, se dimostri che \(\preceq\) è un buon ordine su \(\mathbb N\times\mathbb N\) (lo è, perché si può dimostrare più in generale che se \(P,Q\) sono insiemi bene ordinati, tale è il loro prodotto lessicografico), supponendo che \(B=\{\langle m,n\rangle\in\mathbb N\times\mathbb N:\neg P(m,n)\}\ne\varnothing\), per la proprietà di buon ordine \(B\) deve avere un elemento \(\preceq\)-minimale \(\langle m,n\rangle\): da qui puoi trovare una contraddizione perché datone uno deve esisterne un altro, e un altro, e un altro...
Grazie mille per la risposta, praticamente la dimostrazione per induzione termina già quando hai dimostrato P(0,n) e P(m,0)? Ed inoltre cosa cambia se m ed n appartengono a Z? Non si procede più per induzione?
"Spike32":
Grazie mille per la risposta, praticamente la dimostrazione per induzione termina già quando hai dimostrato P(0,n) e P(m,0)?
No, non lo fa.
Ed inoltre cosa cambia se m ed n appartengono a Z? Non si procede più per induzione?
Questo mi fa sospettare tu non abbia molto chiaro cosa sia una dimostrazione per induzione; $ZZ$ non è bene ordinato, te ne rendi conto? Quindi non può valere il principio di induzione, vedi qui.
Questo mi fa sospettare tu non abbia molto chiaro cosa sia una dimostrazione per induzione; $ZZ$ non è bene ordinato, te ne rendi conto? Quindi non può valere il principio di induzione, vedi qui.
Proprio per questo motivo chiedevo come si dovrebbe procedere
"Spike32":Questo mi fa sospettare tu non abbia molto chiaro cosa sia una dimostrazione per induzione; $ZZ$ non è bene ordinato, te ne rendi conto? Quindi non può valere il principio di induzione, vedi qui.
Proprio per questo motivo chiedevo come si dovrebbe procedere
Procedere per fare cosa? In un monoide non sono veri $P(m,n)$ per $m,n\in ZZ$...
"fmnq":
Questo mi fa sospettare tu non abbia molto chiaro cosa sia una dimostrazione per induzione; $ZZ$ non è bene ordinato, te ne rendi conto? Quindi non può valere il principio di induzione, vedi qui.
Proprio per questo motivo chiedevo come si dovrebbe procedere[/quote]
Procedere per fare cosa? In un monoide non sono veri $P(m,n)$ per $m,n\in ZZ$...[/quote]
Ho capito grazie mille per la risposta.
"fmnq":
[quote="Spike32]Devi fare una qualche forma di doppia induzione, se devi dimostrare che (1) e (2) sono veri per ogni m,n∈N: questo avviene dividendo l'induzione in due parti: P(m,n) la proprietà che devi dimostrare. Allora, fissa n e fai induzione su m, cioè mostra che P(0,n) è vera, e che se è vera P(k,n) per ogni k[/quote]
Mentre per dimostrare $P(0,n)$ e $P(m,0)$ come bisogna procedere? Chiedo scusa ma non sono molto ferrato su questo argomento poiché sto studiando dal libro scritto dal mio docente su cui non vi è alcun esempio di esercizio svolto.
"Spike32":
Mentre per dimostrare $P(0,n)$ e $P(m,0)$ come bisogna procedere? Chiedo scusa ma non sono molto ferrato su questo argomento poiché sto studiando dal libro scritto dal mio docente su cui non vi è alcun esempio di esercizio svolto.
Quanto fa $x^{0+m}$? Quanto fa $x^0x^m$?
"fmnq":
[quote="Spike32"]Mentre per dimostrare $P(0,n)$ e $P(m,0)$ come bisogna procedere? Chiedo scusa ma non sono molto ferrato su questo argomento poiché sto studiando dal libro scritto dal mio docente su cui non vi è alcun esempio di esercizio svolto.
Quanto fa $x^{0+m}$? Quanto fa $x^0x^m$?[/quote]
Chiedo scusa non intendevo solo la base dell'induzione, cioè una volta dimostrata la base come procedo con il passo induttivo?
"Spike32":
[quote="fmnq"][quote="Spike32"]Mentre per dimostrare $P(0,n)$ e $P(m,0)$ come bisogna procedere? Chiedo scusa ma non sono molto ferrato su questo argomento poiché sto studiando dal libro scritto dal mio docente su cui non vi è alcun esempio di esercizio svolto.
Quanto fa $x^{0+m}$? Quanto fa $x^0x^m$?[/quote]
Chiedo scusa non intendevo solo la base dell'induzione, cioè una volta dimostrata la base come procedo con il passo induttivo?[/quote]
Lo sai fare, solo che non hai capito cosa devi fare.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo