Inexistencia de una función sobreyectiva de un conjunto a sus subconjuntos (teorema de Cantor)

Question

Demuestre que: Sea A un conjunto y sea $P(A)$ sea el conjunto de todos los subconjuntos de $A$ . Entonces no hay suryección $f: AP(A)$ .

Esto es lo que pensé:

si $A=\{a,b\}$ entonces sólo tiene dos elementos donde $P(A)=\{,\{a\},\{b\},\{a,b\}\}$ tiene 4 elementos. Por lo tanto, $f:AP(A)$ no puede ser sobreyectiva. Pero tengo algunos problemas:

1) ¿Cómo es posible que cualquier $f$ para tomar $\{a\}$ del conjunto $A$ a $\{a,b\}$ ? Quizás porque estoy pensando principalmente en funciones con valores reales como $f(x)=2x$ , me parece un poco extraño que una función para llevar un elemento de un conjunto a otro conjunto que tiene más elementos. ¿Es posible?

edit: Ahora pensaba que si $f(x)$ est $\sqrt{x}$ entonces $f(4)=±2$ lo que significa que tomó un elemento de un conjunto a un conjunto que tiene 2 elementos. Pero aún así me parece un poco extraño denotar $f(\{a\})=\{a,b,c,...\}$

2) ¿Cómo puedo construir una prueba explícita para esta pregunta?

Saludos

Answer 1

El teorema de Cantor dice:

Supongamos que $A$ es un conjunto y $f\colon A\to\mathcal P(A)$ es cualquier función, entonces $f$ no es sobreyectiva.

La prueba es bastante sencilla, ¡y constructiva!

Prueba. Supongamos que $f\colon A\to\mathcal P(A)$ es una función, definimos $D=\{a\in A\mid a\notin f(a)\}$ . Esta es una buena definición, ya que $f(a)$ es un subconjunto de $A$ y $a$ es un elemento de $A$ podemos preguntarnos si $a\in f(a)$ . Así que $D$ es el conjunto de los elementos de $A$ que no tienen esta propiedad.

Por supuesto que $D\in\mathcal P(A)$ ya que es claramente un subconjunto de $A$ . Demostraremos que $f(a)\neq D$ para todos $a\in A$ .

1. Si $a\in D$ entonces, por definición de $D$ , $a\notin f(a)$ . Así que $f(a)\neq D$ ya que el elemento $a$ pertenece a D pero no a $f(a)$ .
2. Si $a\notin D$ entonces, por definición de $D$ , $a\in f(a)$ . Con el mismo argumento, de nuevo $f(a)\neq D$ .

De cualquier manera, $D\neq f(a)$ para todos $a\in A$ . Por lo tanto, $f$ no es sobreyectiva. $\square$

---

Tenga en cuenta que para las diferentes funciones tenemos diferentes $D$ 's. Es posible que $D=A$ (por ejemplo, si $f(a)=\varnothing$ para todos $a$ ), o puede ser $\varnothing$ (por ejemplo, si $f(a)=\{a\}$ para todos $a$ ). Sin embargo, independientemente de su valor, no estará en el rango de $f$ .

Answer 2

Busca el Teorema de Cantor. Hay varias versiones de este teorema. La versión básica es que no existe una biyección entre un conjunto $A$ y su conjunto de energía $P(A)$ . Una de las pruebas pasa por demostrar que no hay ninguna suryección desde $A$ a $P(A)$ . Lo que se hace es suponer que existe, de modo que para cada $a$ hay un subconjunto $f(a)$ en el conjunto de energía. Entonces se define un conjunto $B$ diciendo que $x$ está en $B$ si y sólo si $x$ NO está en el conjunto $f(x)$ . Ahora usted pregunta: ¿Es $x$ en $B$ ? Si lo es, no lo es, y si no lo es, sí lo es... e