Dimostrazione cardinalità iniezioni e biiezioni

[alboos]

Mi piacerebbe chiarire un dubbio riguardo le dimostrazioni del titolo del thread.

In particolare è stato mostrato che la cardinalità di
# iniezioni $|I(A,B)|=(b!)/((b-a)!)$
# e delle biiezioni è $|B(A,B)|=b! =a!$
entrambe per induzione.

Tuttavia si dice subito che nei due casi, rispettivamente se:
a# $|A|=a>b=|B|$ allora $|I(A,B)|=0$
b# $|B|!=|A|$ allora $|B(A,B)|=0$
e qui nasce il mio dubbio, lo dà per assodato e certo (evidente) ma dovrei in realtà dimostrarlo e solo così poi dimostrare per induzione sui casi possibili $a<=b$ per iniezioni e $a=b$ per biiezioni.

Insomma, la mia domanda sarebbe: come DI(mostro) che sono vere a# e b#? Formalmente e non intuitivamente come ovviamente già mi risulta chiaro e vero.

[megas_archon]

La domanda che fai non è scritta in un italiano molto comprensibile... comunque mi sembra che quello che tu voglia chiedere sia

1. Come si dimostra che se $A$ è un insieme di cardinalità maggiore di $B$, allora non esiste una funzione iniettiva $A\to B$?
2. Come si dimostra che se $A,B$ sono insiemi di cardinalità diversa, allora non esiste nessuna biiezione tra $A$ e $B$?

Tu vuoi una dimostrazione formale di questi due asserti; il problema è che questa dimostrazione non sarà molto soddisfacente, perché alla fin fine seguirà dalla definizione di cardinalità, e in particolare dal fatto che "avere cardinalità maggiore di $B$" significa esattamente "non esiste una funzione iniettiva verso $B$", e "avere la stessa cardinalità di $B$" significa "esiste una biiezione verso $B$".

Tuttavia puoi ridurre il problema a qualcosa di più esplicito, senza perdita di generalità: ad esempio è sufficiente mostrare che 1. è vero per i soli insiemi della forma \(\{1,\dots, n\}\), al variare di \(n\in\mathbb N\).

Questo a rigore crea altri problemi, perché che cos'è $n$? Che cos'è \(\mathbb N\)? Et cetera. Ma fingiamo che questi problemi non esistano e diciamo di aver costruito i naturali alla Von Neumann, cioè dicendo che \(0 := \varnothing\) e \(n+1 := n \cup \{n\}\). In questo senso, le seguenti condizioni sono equivalenti per due numeri naturali $n,m$:

a. \(n \le m\);
b. \(n \subseteq m\);
c. \(n \in m\);
d. esiste una funzione iniettiva $n\to m$.

Alla luce di questo, supponiamo esista una funzione iniettiva \(m\to n\), e che \(n\le m\): allora, $n=m$ per l'antisimmetria della relazione \(\le\) di ordine tra i cardinali. Qui te la cavi con poco perché hai costruito gli insiemi tutti uno dentro l'altro, ma il fatto che rende questa dimostrazione elusiva è proprio che l'antisimmetria di \(\le\) è un teorema, il teorema di Cantor-Schöder-Bernstein.