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 » 07 nov 2008, 23:59

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: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 08 nov 2008, 00:18

Beh non è difficilissimo... Domani lo testo sui miei compagni di classe :D :twisted:
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

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 » 08 nov 2008, 10:52

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 » 08 nov 2008, 13:47

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 » 08 nov 2008, 22:25

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 » 08 nov 2008, 23:34

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 » 09 nov 2008, 01:12

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 » 09 nov 2008, 01:40

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: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 09 nov 2008, 02:02

È 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.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 09 nov 2008, 02:04

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 » 09 nov 2008, 11:13

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: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 09 nov 2008, 12:56

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)
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 09 nov 2008, 16:31

Antimateria ha scritto:$ \mathrm{Im}\ f \subseteq \mathrm{Im}\ g $
Cosa significano questi strani simboli? :shock:

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 09 nov 2008, 16:42

Io ho inteso "immagine di ..."
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Messaggio da Gatto » 09 nov 2008, 20:04

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