f<=g implies f=g
f<=g implies f=g
Date due funzioni $ f:\mathbb{N} \to \mathbb{N} $ iniettiva e $ g:\mathbb{N} \to \mathbb{N} $ suriettiva tali che $ f(n) \le g(n) \forall n \in \mathbb{N} $.
Mostrare che $ f=g $.
NB: $ 0 \in \mathbb{N} $
Source: un banale libro di matematica per liceo...
Mostrare che $ f=g $.
NB: $ 0 \in \mathbb{N} $
Source: un banale libro di matematica per liceo...
The only goal of science is the honor of the human spirit.
- Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
Re: f<=g implies f=g
loljordan ha scritto:NB: $ 0 \in \mathbb{N} $
Provo con l'induzione
Siano $ $k_i$ $ un numero intero non negativo.
Voglio dimostrare che $ $f(k_i)=g(k_i)$ $ per qualunque $ $k_i$ $
Passo base
Siccome la funzione $ $g$ $ è suriettiva allora raggiunge ogni numero intero non negativo in particolare ci sarà la $ $g$ $ di un numero $ $k_0$ $ tale che $ $g(k_0)=0$ $. Abbiamo che $ $f(k_0) \le g(k_0)=0$ $, essendo $ $f$ $ una funzione che va da $ $\mathbb{N}$ $ a $ $\mathbb{N}$ $, $ $f(k_0)$ $ deve essere per forza uguale a 0.
Passo induttivo
Supponiamo che per tutti gli $ $i \le n$ $ valga $ $f(k_i)=g(k_i)=i$ $ e dimostriamo che anche per $ $n+1$ $ vale $ $f(k_{n+1})=g(k_{n+1})=n+1$ $.
La funzione $ $f$ $ è iniettiva per ipotesi e in particolare $ $f(k_{n+1})$ $ non può dare un valore uguale a uno qualsiasi dei $ $0,1,2,3, \cdots , n $ $ ma deve essere nello stesso tempo $ $\le g(k_{n+1})=n+1$ $ e quindi deve essere $ $f(k_{n+1})=n+1=g({k_{n+1}})$ $.
Le due funzioni sono uguali per qualunque intero non negativo e quindi sono uguali.
Tutto ok o ho sparato qualche eresia
Siano $ $k_i$ $ un numero intero non negativo.
Voglio dimostrare che $ $f(k_i)=g(k_i)$ $ per qualunque $ $k_i$ $
Passo base
Siccome la funzione $ $g$ $ è suriettiva allora raggiunge ogni numero intero non negativo in particolare ci sarà la $ $g$ $ di un numero $ $k_0$ $ tale che $ $g(k_0)=0$ $. Abbiamo che $ $f(k_0) \le g(k_0)=0$ $, essendo $ $f$ $ una funzione che va da $ $\mathbb{N}$ $ a $ $\mathbb{N}$ $, $ $f(k_0)$ $ deve essere per forza uguale a 0.
Passo induttivo
Supponiamo che per tutti gli $ $i \le n$ $ valga $ $f(k_i)=g(k_i)=i$ $ e dimostriamo che anche per $ $n+1$ $ vale $ $f(k_{n+1})=g(k_{n+1})=n+1$ $.
La funzione $ $f$ $ è iniettiva per ipotesi e in particolare $ $f(k_{n+1})$ $ non può dare un valore uguale a uno qualsiasi dei $ $0,1,2,3, \cdots , n $ $ ma deve essere nello stesso tempo $ $\le g(k_{n+1})=n+1$ $ e quindi deve essere $ $f(k_{n+1})=n+1=g({k_{n+1}})$ $.
Le due funzioni sono uguali per qualunque intero non negativo e quindi sono uguali.
Tutto ok o ho sparato qualche eresia
Appassionatamente BTA 197!
È la discesa infinita di cui (credo) parlava kn, si può fare così (anche se non si usano i piccioni): sia $ $x_0 $ il più piccolo intero per cui $ $f(x_0)<g(x_0) $, per la surriettività di g esiste $ $x_1 $ tale che $ $g(x_1)=f(x_0) $ inoltre $ $g(x_1)\ge f(x_1) $ e per l'iniettività $ $g(x_1)>f(x_1) $ quindi $ $f(x_0)>f(x_1) $, assurdo.
- Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
Rispettivamente $ f(\mathbb{N}) $ e $ g(\mathbb{N}) $kn ha scritto:Cosa significano questi strani simboli?Antimateria ha scritto:$ \mathrm{Im}\ f \subseteq \mathrm{Im}\ g $
"Fu chiaro sin dall'inizio che ogni qual volta c'era un lavoro da fare, il gatto si rendeva irreperibile." (George Orwell - La fattoria degli animali)