mateforum.ro

Fie \( f,g :\mathbb{N}\to \mathbb{N} \), astfel incat \( f \) e injectiva si \( g \) e surjectiva. Demonstrati ca daca \( f(n)\leq g(n),\ \forall n \in \mathbb{N} \) atunci \( f=g \).

Gheorghe Ekstein, Concurs RMT

Se demonstreaza prin inductie dupa k propozitia:

P(k): ,,Exista \( n_k\in \mathbb{N} \) astfel incat \( f(n_k)=g(n_k)=k \) pentru orice k natural''

Asadar pentru m natural exista \( n_m \in\mathbb{N} \) astfel incat

\( f(n_m)=g(n_m)=f(m) \) si cum f este injectiva rezulta \( n_m=m \) , deci

\( f(m)=g(m) \) \( (\forall) m\in \mathbb{N} \)

Eu m-am gandit in felul urmator:
Fie \( A=\{g(n) \in \mathbb{N} : f(n)<g(n)\} \) pe care o presupunem nevida. Atunci exista un cel mai mic element \( c \) din \( A \) care nu e 0. Deci pentru orice \( m\leq c-1 \) exista \( k_m\in \mathbb{N},\ g(k_m)=m=f(k_m) \). Atunci \( f(k_c)<g(k_c)=c \) si toate numerele pana la \( c-1 \) sunt ocupate, ceea ce contrazice injectivitatea lui \( f \).