El teorema:
Supongamos que existen funciones inyectiva $A \to B$ $B \to A$ entre los dos conjuntos infinitos $A$$B$. Entonces existe un bijection $A \to B$.
Prueba:
Deje $f: A \to B$ $g: B \to A$ ser inyectiva funciones. Deje $G$ ser el bipartito y el grafo no dirigido con la partición de conjuntos de $A$ $B$ y los bordes $ab$ cuando $f(a) = b$ o $g(b) = a$ todos los $a \in A$$b \in B$. Tenga en cuenta que $f$ $g$ cada uno corresponde a una coincidencia de $A$ $B$ respectivamente. Claramente, si $G$ tiene una perfecta coincidencia (que vamos a probar), entonces existe un bijection $A \to B$.
Debido a $f$ $g$ son inyectiva, cada vértice en $G$ tiene al menos grado $1$ y en la mayoría de grado $2$. Por lo tanto, cada componente $C$ $G$ es una ruta o un ciclo. Si $C$ es un ciclo, porque $G$ es bipartito, se deduce que el $C$ es uniforme y por lo tanto tiene un perfecto maridaje. Por otro lado, si $C$ es un camino, que puede ser finito o infinito. Si $C$ es finito, entonces $C$ debe ser, porque la inyectividad de $f$ $g$ juntos implica que $|A \cap C| = |B \cap C|$, por lo que tiene un perfecto maridaje. De lo contrario, si $C$ es infinito, entonces cualquiera de las $C$ tiene un vértice de grado 1 y todos los demás de grado 2 o tiene todos los vértices con grado 2: en el primer caso tomamos el impares bordes (contando desde el borde del incidente con el vértice de grado 1) y en el segundo caso sólo tomamos la alternancia de los bordes de partida donde queramos.
