Suriezione tra lo stesso insieme finito, mostra che non possono esserci due input diversi che producono lo stesso output
È possibile dimostrare che non possono esserci due input diversi che producono lo stesso output per la suriezione tra lo stesso insieme finito senza prima dimostrare che anche tale suriezione è un'iniezione.
Lo chiedo perché sto cercando di usare questo risultato per dimostrare che tale suriezione è anche un'iniezione.
Ecco la prova funzionante dell'iniezione.
Obiettivo:$∀n ∈ ℕ, ∀ f, f: n ⟹ n → injective f$
Qui "f: n ⟹ n" denota che f è una suriezione da n a n.
Dimostrare per induzione che n = 0 è vero in modo vacuo.
Per n = k, supponi$∀ f, f: k ⟹ k → injective f$
quindi dobbiamo dimostrare$∀ f, f: k⁺ ⟹ k⁺ → injective f$
Usa escludi mezzo a$∀p ∈ k, f(p) ∈ k$
Caso I:$∀p ∈ k, f(p) ∈ k$
abbiamo$f(k) = k$, o altro$f(k) ∈ k$contraddire la suriezione poiché nulla corrisponde a k.
Quindi abbiamo$f ↾ k : k ⟹ k$dove "↾" denota restrizione.
Per ipotesi di induzione,$injective (f ↾ k)$
Perciò$f = f ↾ k ∪ \{<k, k>\}$è iniettivo.
Caso II:$¬ ∀p ∈ k, f(p) ∈ k$che significa$∃p ∈ k,f(p) = k$
Se possiamo provare$f(k) ∈ k$,allora può essere ridotto al Caso I scambiando i valori su k e p.
Provare$f(k) ∈ k$, Avviso$f(k) ∈ k⁺$
dobbiamo solo dimostrare$f(k) ≠ k$che porta a ciò che il titolo chiede.
Risposte
Scriverò una dimostrazione diretta che una funzione suriettiva tra due insiemi finiti della stessa cardinalità è iniettiva. Dopodiché, discuterò di come si confronta con la tua domanda e il tentativo di prova.
Seguendo la tua configurazione, tratto$n\in\mathbb{N}$come un ordinale finito; Così$n=\{k\in\mathbb{N}:k<n\}$.
Lemma: Se$g:n\to n$è iniettivo, quindi$g$è suriettivo.
Dimostrazione: Let$X$essere l'immagine di$g$. Quindi$g:n\to X$è una biiezione, quindi$|X|=n$. Così$X=n$.
Dimostriamo ora il risultato principale. Permettere$f: n\to n$essere una funzione suriettiva. Vogliamo dimostrarlo$f$è iniettivo. Da$f$è suriettiva, per qualsiasi$k\in n$ce n'è un po'$x_k\in n$tale che$f(x_k)=k$. Da$f$è una funzione, sappiamo che se$k\neq l$poi$x_k\neq x_l$. Così$g:n\to n$tale che$g(k)=x_k$è una funzione iniettiva, e quindi è suriettiva per il Lemma. Infine, supponiamo$x,y\in n$e$f(x)=f(y)$. Da$g$è suriettiva, lo sappiamo$x=x_k$e$y=x_l$per alcuni$k,l\in n$. Così$f(x_k)=f(x_l)$, cioè,$k=l$. Così$x=x_k=x_l=y$. Perciò$f$è iniettivo.
Discussione della tua domanda e tentativo di prova:
Chiedi se possiamo mostrare che due input diversi, diciamo$a$e$b$, per una funzione$f$produrre risultati diversi senza prima mostrarlo$f$è iniettivo. Poiché la definizione di iniettivo è "due input distinti qualsiasi producono output diversi", l'unico modo in cui ciò sarebbe possibile è se avessimo ulteriori informazioni specifiche su$f$,$a$, e$b$. In effetti, se hai un argomento che$f(a)\neq f(b)$, che non utilizza nulla di speciale about$f$,$a$, e$b$, allora quello che hai è una prova che$f$è iniettivo.
Affermo che nella tua dimostrazione non abbiamo informazioni abbastanza specifiche per concludere che il problema a cui ti sei ridotto sia più semplice. Nel tuo caso, stiamo confrontando i seguenti due problemi.
Per ogni$k$e$p\in k$, Se$f:k^*\to k^*$è suriettiva e$f(p)=k$poi$f(k)\neq k$.
Per ogni$k$e distinti$a,b\in k^*$, Se$f:k^*\to k^*$è suriettiva allora$f(a)\neq f(b)$.
Quindi (1) è la situazione specifica a cui arrivi nella tua dimostrazione, mentre (2) dice "qualsiasi funzione suriettiva da$k^*$a$k^*$è iniettiva", che è la domanda generale.
Stai chiedendo se (1) è in qualche modo più facile da mostrare senza mostrare (2). Ma sostengo che (1) e (2) sono essenzialmente equivalenti. Supponiamo infatti di assumere (1). Poi, data suriettiva$f:k^*\to k^*$e distinti$a,b\in k^*$, scegli una permutazione$h$di$k^*$che invia$p$a$a$e$k$a$b$. Scegli un'altra permutazione$g$di$k^*$che invia$f(a)$a$k$. Ritenere$f^*=g\circ f \circ h$. Quindi$f^*$è ancora suriettiva, e$f^*(p)=k$. Così$f^*(k)\neq k$di (1). Spacchettando le scelte, questo dice$g(f(a))\neq g(f(b))$, Così$f(a)\neq f(b)$da$g$è iniettivo. Quindi abbiamo mostrato (2).
Per riassumere, sebbene la domanda che poni abbia l'apparenza estetica di essere più specifica, in realtà è la stessa della domanda generale, dopo averla composta con opportune permutazioni. Pertanto l'unico ricorso che hai per continuare la tua dimostrazione è un argomento di tipo generale per l'iniettività, come quello che ho dato sopra.