Teorema. Deje A B ser conjuntos. Considere las siguientes tres afirmaciones:
- f\colon A\to B es uno-a-uno.
- Existe g\colon B\to A tal que gf = \mathrm{id}_A (f ha dejado inversa).
- Para cada conjunto C y cada una de las funciones de h,k\colon C\to A si fh = fk h=k (f se deja cancelable).
Entonces 2\implies3\iff1. Por otra parte, si A es no vacío, entonces el 1\implies2 todos los tres son equivalentes.
Prueba.
2\implies3. Deje h,k\colon C\to A ser tal que fh = fk. Deje g ser la función garantizados por 2. Entonces
h = \mathrm{id}_Ah = (gf)h = g(fh) = g(fk) = (gf)k = \mathrm{id}_Ak = k.
Por lo tanto, f es de izquierda cancelables.
3\implies1. Deje a,a'\in A ser tal que f(a)=f(a'). Tenemos que demostrar que el a=a'. Vamos C=\{0\}, h\colon C\to A ser dado por h(0)=a, e k\colon C\to A ser dado por k(0)=a'. A continuación,fh(0) = f(a) = f(a') = fk(0). por lo fh=fk. Desde f es de izquierda cancelables, llegamos a la conclusión de que h=k. Por lo tanto a = h(0) = k(0) = a', lo que demuestra que el f es uno-a-uno.
1\implies3. Deje C a un y h,k\colon C\to A ser tal que fh = fk. Tenemos que mostrar que h=k. Deje c\in C. A continuación,f(h(c)) = f(k(c)); desde f es uno-a-uno, llegamos a la conclusión de que h(c)=k(c). Desde h(c)=k(c) todos los c\in C, se deduce que el h=k.
1\implies2 si A es no vacío y B son no vacíos. Desde A es no vacío, no existe a_0\in A. Definir g\colon B\to A como sigue:
g(b) = \left\{\begin{array}{ll}
a &\text{if }b\in f(A)\text{ and }f(a)=b;\\
a_0&\text{if }b\notin f(A).
\end{array}\right.
Esto está bien definido, ya que f(a)=f(a')=b implica a=a'. Y si b\in f(A), entonces no existe a\in A tal que f(a)=b. Ahora, vamos a a\in A. A continuación,g(f(a)) = a, lo gf = \mathrm{id}_A, como se desee. \Box
En particular, dada una función de f\colon A\to B, si g existe que hace que el diagrama conmuta, entonces f es uno-a-uno. Por el contrario, si f es uno-a-uno y A es no vacío (o A B están vacíos), entonces podemos encontrar una g que hace el diagrama conmuta.
Aquí está el doble:
Teorema. Deje A B ser conjuntos. Considere las siguientes tres afirmaciones:
- f\colon A\to B es sobre.
- Existe g\colon B\to A tal que fg=\mathrm{id}_B (f tiene derecho a la inversa).
- Para cada conjunto C y cada una de las funciones de h,k\colon B\to C si hf = kf, luego h=k (f es derecho cancelable).
Entonces 2\implies3\iff1. Por otra parte, la implicación de 1\implies2 es equivalente al Axioma de Elección.
Prueba. 2\implies3 C ser un conjunto y deje h,k\colon B\to C ser tal que hf=kf. Deje g ser la función garantizados por 2; entonces:
h = h\mathrm{id}_B = h(fg) = (hf)g =(kf)g = k(fg) = k\mathrm{id}_B = k.
3\implies1. Deje C=\{0,1\} y definen h\colon B\to C h(b)=1 todos los b, y
k(b) = \left\{\begin{array}{ll}
1 & \text{if }b\in f(A);\\
0 &\text{if }b\notin f(A).
\end{array}\right.
A continuación,hf = kf, por lo tanto, por 3 h=k. Por lo tanto, k(b)=1 todos los b\in B, por lo tanto f(A)=B; es decir, f es sobre.
1\implies3. Supongamos que C es un conjunto y h,k\colon B\to C son funciones tales que hf = kf. Deje b\in B; necesitamos mostrar h(b)=k(b). Desde f es sobre, existe a\in A tal que f(a)=b. Por lo tanto,
h(b) = h(f(a)) = hf(a) = kf(a) = k(b).
Por lo tanto, h=k.
Si el Axioma de Elección se mantiene, entonces el 1\implies2: Si f a, entonces para cada a b\in B, la f^{-1}(b) = \{a\in A\mid f(a)=b\} es no vacío. Por el Axioma de elección, existe una función de g\colon B\to \cup_{b\in B} f^{-1}(b) tal que g(b)\in f^{-1}(b) por cada b\in B. Yo reclamo que fg=\mathrm{id}_B. De hecho, por cada b\in B, g(b)\in f^{-1}(b), por lo f(g(b))=b.
Si el 1\implies2 se mantiene, entonces el Axioma de Elección se mantiene. Deje \mathcal{X}=\{A_i\}_{i\in I} ser un vacío de la familia (I\neq\varnothing) de conjuntos no vacíos (A_i\neq\varnothing por cada I\in I). Tenemos que mostrar que existe una función de g\colon I\to\cup_{i\in I}A_i tal que g(i)\in A_i por cada i\in I.
Deje B_i = A_i\times\{i\}. Tenga en cuenta que la familia \mathcal{Y}=\{B_i\}_{i\in I} se compone de pares de distintos conjuntos. Deje Y=\cup_{i\in I}B_i, un definen f\colon Y\to I f(b_i,i) = i (proyección en el segundo componente). El mapa es, desde cada una de las A_i es no vacío, por lo B_i\neq\varnothing. Por nuestra suposición de que el 1\implies2, existe h\colon I\to Y tal que h(i)\in B_i por cada i\in I. Deje \pi_i\colon B_i\to A_i ser la proyección sobre la primera coordenada, \pi_i(b_i,i) = b_i. Definir g\colon I\to \cup_{i\in I}A_i por
g(i) = \pi_i\circ h (i).
Desde h(i)\in B_i=A_i\times\{i\},\pi_i\circ h(i) \in A_i. Esto es válido para cada una de las i, lo g es la opción deseada de la función. \Box
En particular, si el diagrama de desplazamientos, a continuación, g es sobre. Por el contrario, asumiendo el axioma de elección, si g es sobre, entonces podemos encontrar una f que encaja en el diagrama y se hace camino al trabajo.