F : A -> B iniettiva se e solo se | A | < | B |

[Richard_Dedekind]

Salve, mi chiedevo se qualcuno ha un'idea di come dimostrare questa proposizione:

Siano [tex]A,B[/tex] insiemi finiti e sia [tex]f:A\longrightarrow B[/tex] una funzione. Allora [tex]f[/tex] è iniettiva se e solo se [tex]|A|\leq|B|[/tex]

L'implicazione verso sinistra è semplice (basta costruire una immersione da A in B); l'altro verso mi crea perplessità. Pensavo di risolverlo per assurdo ma non lo so formalizzare per bene. Potete aiutarmi?

[j18eos]

Benvenuto!

Gl'insiemi [tex]$A$[/tex] ed [tex]$f(A)$[/tex] come sono?

[Seneca1]

Questa proposizione, così come è scritta, è falsa.

Per confutare la "$f$ iniettiva $Leftarrow$ $|A| <= |B|$" basta prendere due insiemi finiti:

$A = {0, 1 }$ e $B = { a , b , c }$

Sia $f : A -> B$ così definita: $f(0) = a$ , $f(1) = a$

$f$ non è iniettiva.

[Seneca1]

Che $|A| <= |B|$ sia condizione necessaria perché $f$ sia iniettiva è vero.

Puoi supporre per assurdo che sia $|A| > |B|$ e utilizzare il principio della piccionaia.

[Richard_Dedekind]

Mi sono accorto di aver scritto una falsità; infatti la proposizione corretta sarebbe così:

Siano $A,B$ insiemi finiti; allora esiste una funzione [tex]f:A \longrightarrow B[/tex] iniettiva se e solo se $|A| \leq |B|$

Seneca: esattamente quello che avevo tentato di fare (anche se non esplicitamente usando il principio della piccionaia). Provo a formalizzare la dimostrazione dell'implicazione verso destra che avevo fatto.
Supponiamo per assurdo che $f$ sia una iniezione e risulti $|A|>|B|$. Poiché $f$ è iniettiva, se $|A|=n$ allora anche $|f(A)|=n$. Ma $f(A) \subseteq B$ e quindi dovrebbe risultare che $n=|f(A)| \leq |B|<|A|=n$ il che è assurdo. Dunque $|A| \leq |B|$.