Sean $X,Y$ dos conjuntos no vacíos y sea $f\colon X\to Y$ una función.
Se dice que
- $ f\text{ es inyectiva }\iff \left[ \forall x_{1},x_{2} \in X\colon x_{1}\neq x_{2}\implies f\left(x_{1}\right)\neq f\left(x_{2}\right) \right] $.
- $ f\text{ es inyectiva }\iff \left[ \forall x_{1},x_{2} \in X\colon f\left(x_{1}\right)= f\left(x_{2}\right)\implies x_{1}= x_{2}\right] $.
- $ f\text{ es suryectiva}\iff \left[ \forall y\in Y,\exists x\in X \ni y= f\left(x\right) \right] $.
- $ f\text{ es biyectiva }\iff f\text{ es inyectiva }\wedge f\text{ es suryectiva} $.
¿Existe alguna $f\colon\mathbb{N}\rightarrow\mathscr{P}\left(\mathbb{N}\right)$ suryectiva?
No.
En efecto, suponga que tal función si existe $f\colon\mathbb{N}\to\mathscr{P}\left(\mathbb{N}\right)$ suryectiva. Para el conjunto
\[ A\eqqcolon \left\{ k\in\mathbb{N}\mid k\notin f\left(k\right) \right\} \in\mathscr{P} \left(\mathbb{N}\right). \]
Siendo $f$ suryectiva $\exists n\in\mathbb{N}\ni f\left(n\right)=A$.
- Si $n\in A\implies n\notin f\left(n\right)\implies n\notin A\,\Rightarrow\Leftarrow$.
- Si $n\notin A\implies n\notin f\left(n\right)\implies n\in A\,\Rightarrow\Leftarrow$.
Definición (Conjuntos finitos).
Sea $A$ un conjunto. El conjunto $A$ es finito si $A=\emptyset\vee$ $$ \exists f\colon A\to \left\{1,2,\ldots,n\right\} $$ biyectiva.Lema (1).
Sea $A$ un conjunto con $a_{0}\in A$. $$ \exists\,f\colon A\to \left\{1,2,\ldots,n+1\right\} \text{ biyectiva }\iff \exists\,g\colon A\setminus\left\{a_{0}\right\}\to \left\{1,2,\ldots,n\right\} \text{ biyectiva }. $$Demostración.
($\Leftarrow$) Obvio. Basta definir $$ \begin{aligned} f\colon A & \to\left\{1,\ldots, n+1\right\} \\ x & \mapsto g\left(x\right),\quad x\in A\setminus\left\{a_{0}\right\} \\ a_{0} & \mapsto n+1,\quad\text{caso contrario}. \end{aligned} $$ ($\Rightarrow$) Si $f\left(a_{0}\right)=n+1$, entonces definimos $g=f\big|_{A\setminus\left\{a_{0}\right\}}$. En caso contrario, supongamos que $f\left(a_{0}\right)=m\neq m+1$. Luego, definimos $$ \begin{aligned} h\colon A & \rightarrow\left\{1,\ldots, m+1\right\} \\ x & \mapsto f\left(x\right),\quad x\neq a_{0},a_{1} \\ a_0 & \mapsto n+1, \\ a_1 & \mapsto m. \end{aligned} $$ Así, $g=h\big|_{A\setminus\left\{a_{0}\right\}}$.Teorema.
Sea $f\colon A\rightarrow\left\{1,2\ldots,n\right\}$ biyectiva. Si $B\subsetneq A$, entonces $\nexists\,g\colon B\rightarrow\left\{1,\ldots,n\right\}$ biyectiva.Demostración.
Por inducción sobre $n$. Para $n=1\colon A=\left\{a\right\}$ y $B=\emptyset$. Obvio.Hipótesis de inducción: Supongamos cierto el teorema para $n$. Veamos que se cumple para $n+1$: En efecto, sea $f\colon A\rightarrow\left\{1,2,\ldots, n+1\right\}$ biyectiva y $B\subsetneq A$ ($B=\emptyset$, obvio). Supogamos $B\neq\emptyset$. Sea $a_{0}\in B$ y $a_{1}\in A\setminus B$. Por el lema $1$: $$ \exists\,g\colon A\setminus \left\{a_0\right\}\rightarrow \left\{1,\ldots,n\right\} $$ biyectiva y como $$ B\setminus \left\{a_{0}\right\}\subsetneq A\setminus \left\{a_{0}\right\}. $$ Por la hipótesis de inducción: $$ \nexists\,h\colon B\setminus \left\{a_{0}\right\}\rightarrow \left\{1,2,\ldots,n\right\} \text{biyectiva} $$ Por el lema $1$: $$ \exists\,k\colon B\rightarrow \left\{1,2,\ldots,n+1\right\} \text{biyectiva}. $$
Corolario.
Si $A$ es finito, entonces $\nexists$ biyección de $A$ es un subconjunto propio de $A$. En efecto, supongamos que $\exists\,f\colon A\rightarrow B\subsetneq A$ biyectiva. Como $A$ es finito, entonces $$ \exists\, g\colon A\rightarrow \left\{1,\ldots,n\right\} $$ para algún $n$.Corolario.
$\mathbb{N}$ no es finito.Demostración.
En efecto. Basta observar que $$ \begin{aligned} f\colon\mathbb{N} & \rightarrow \mathbb{N}\setminus\left\{1\right\}\subsetneq \mathbb{N} \\ n & \mapsto n+1 \end{aligned} $$ es biyectiva.Corolario.
Sea $A$ un conjunto finito. El cardinal de $A$ está bien definida.Demostración.
En efecto. Sea $I_k\coloneqq\left\{1,\ldots,k\right\}$. Supongamos que existen $$ \begin{gathered} f\colon A\rightarrow I_{n}\\ g\colon A\rightarrow I_{m}\\ \end{gathered} $$ biyectivas. Se demostrará que $n=m$. Supongamos que $n\lt m$.Corolario.
Si $B\subsetneq A$ y $A$ es un conjunto finito, entonces $B$ es finito y $\left|A\right|\lt\left|B\right|$.Demostración.
En efecto, sin pérdida de generalidad, sea $B=A\setminus\left\{a_{0}\right\}$ con $a_{0}\in A$. Como $A$ es finito, entonces $$ \exists\,f\colon A\rightarrow \left\{1,\ldots,n\right\} $$ biyectiva para algún $n$. Por el lema $1$, $$ \exists\,g\colon A\setminus\left\{a_0\right\}\rightarrow \left\{1,\ldots, n\right\} $$ biyectiva. Es decir, $B$ es finito y $\left|B\right|=n\lt\left|A\right|=n+1$.Corolario.
Sea $B\neq\emptyset$, las siguientes proposiciones son equivalentes:1. $B$ es finito.
2. $\exists\,f\colon I_{n}\rightarrow B$ suryectiva.
3. $\exists\,g\colon B\rightarrow I_{n}$ inyectiva.
Demostración.
($1\Rightarrow2$) Si $B$ es un conjunto finito, entonces $\exists\,h\colon B\rightarrow I_{n}$ biyectiva para algún $n$. $\therefore\exists\,f=h^{-1}\colon I_{n}\rightarrow B$ suryectiva. ($2\Rightarrow3$) Tenemos que $\exists\,f\colon I_{n}\rightarrow B$ suryectiva. Definimos: $$ \begin{aligned} g\colon B & \rightarrow I_{n} \\ b & \mapsto g\left(b\right)= \min \left( f^{-1} \left(\left\{b\right\}\right) \right) \subset I_{n} \\ \end{aligned} $$ Afirmamos que $g$ es inyectiva. Sean $b\neq b^{\prime}$ en $B$, entonces