f<=g implies f=g

[jordan]

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

[julio14]

Beh non è difficilissimo... Domani lo testo sui miei compagni di classe

[Antimateria]

NB: $ 0 \in \mathbb{N} $

lol

[kn]

Si può dimostrare per induzione o (più divertente) per discesa infinita!

[mod_2]

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

[jordan]

Si tutto ok, sono solo io che mi faccio complessi a trovare soluzioni "evidenti" come sempre..

[SkZ]

la tua qual era?

[jordan]

Supporre che esistesse un x tale che f(x) < g(x) e andare avanti per i possibili valori assunti da f in x-1, x-2, x-3... concludendo con un assurdo per pigenhole. quindi si otteneva che $ f \ge g $ da cui, dall'ipotesi, $ f=g $..

[julio14]

È 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.

[jordan]

Si come si vede è la stessa cosa, ma almeno dal mio punto di vista è meno intuitivo della "costruzione diretta" di mod_2..

[Antimateria]

La suriettività di g può essere indebolita richiedendo solamente che $ \mathrm{Im}\ f \subseteq \mathrm{Im}\ g $.

La mia ilarità di prima era motivata dal fatto che non ha alcun senso alimentare diatribe sull'appartenenza di 0 ai naturali, in un problema ove essa è banalmente ininfluente.

[julio14]

Beh si equivale a mettere $ $\mathrm{Im}\ g $ come codominio anziché $ $\mathbb{N} $ per il resto è sostanzialmente identico.
(cmq l'ilarità si era capita... per lo meno io non ti avevo considerato un pazzo lol)

[kn]

$ \mathrm{Im}\ f \subseteq \mathrm{Im}\ g $

Cosa significano questi strani simboli?

[julio14]

Io ho inteso "immagine di ..."

[Gatto]

$ \mathrm{Im}\ f \subseteq \mathrm{Im}\ g $

Cosa significano questi strani simboli?

Rispettivamente $ f(\mathbb{N}) $ e $ g(\mathbb{N}) $