f<=g implies f=g

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

f<=g implies f=g

Messaggio da 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... :!:
The only goal of science is the honor of the human spirit.
Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 »

Beh non è difficilissimo... Domani lo testo sui miei compagni di classe :D :twisted:
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Re: f<=g implies f=g

Messaggio da Antimateria »

jordan ha scritto:NB: $ 0 \in \mathbb{N} $
lol
Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn »

Si può dimostrare per induzione o (più divertente) per discesa infinita! :wink:
Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da 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 :?:
Appassionatamente BTA 197!
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

Si tutto ok, sono solo io che mi faccio complessi a trovare soluzioni "evidenti" come sempre..
The only goal of science is the honor of the human spirit.
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

la tua qual era?
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da 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 $.. :roll: :(
The only goal of science is the honor of the human spirit.
Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da 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.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

Si come si vede è la stessa cosa, ma almeno dal mio punto di vista è meno intuitivo della "costruzione diretta" di mod_2..
The only goal of science is the honor of the human spirit.
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da 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.
Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da 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)
Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn »

Antimateria ha scritto:$ \mathrm{Im}\ f \subseteq \mathrm{Im}\ g $
Cosa significano questi strani simboli? :shock:
Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 »

Io ho inteso "immagine di ..."
Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Messaggio da Gatto »

kn ha scritto:
Antimateria ha scritto:$ \mathrm{Im}\ f \subseteq \mathrm{Im}\ g $
Cosa significano questi strani simboli? :shock:
Rispettivamente $ f(\mathbb{N}) $ e $ g(\mathbb{N}) $
"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)
Rispondi