Dado $f:\Bbb N\to P(\Bbb N)$ , presentan dos conjuntos de naturales no a imagen y semejanza de $f$ .

Question

Dejemos que $f: \Bbb N \to P(\Bbb N)$ . Presente 2 conjuntos diferentes de números naturales A, B que no estén en Im(f)

Lo que hice:

Primera idea: Definí una función inyectiva f que toma cada n y devuelve su singleton. Ahora cada uno de los miembros de $P(\Bbb N)$ que no es un singleton no está en $Im(f)$ .

¿Basta con esta "prueba"? ¿Hay alguna forma de generalizarla aún más?

Segunda idea: Tomé los números 0 y 1 solamente, si defino una función de un conjunto de {0,1} a P({0,1}) siempre me quedarán 2 conjuntos fuera de la imagen (ya que P({0,1}) tiene 4 conjuntos y {0,1} sólo tiene 2 miembros). He pensado en generalizar esto de alguna manera por inducción, pero no tengo ni idea de cómo.

Gracias por su ayuda.

Answer 1

Poner $$\eqalign{ A&:=\bigl\{2j\ \bigm|\ j\geq 0,\ 2j\notin f(j)\bigr\}\ \cup\ \bigl(\{1\}\cap f(0)\bigr)\ ,\cr B&:=\bigl\{2j+1\ \bigm|\ j\geq 0,\ 2j+1\notin f(j)\bigr\}\ .\cr}$$ Entonces, para cada $j\geq0$ el conjunto $A$ contiene el número $2j$ si $f(j)$ no contiene este número, y del mismo modo el conjunto $B$ contiene el número $2j+1$ si $f(j)$ no contiene este número. Por lo tanto, ambos $A$ y $B$ son diferentes de todos los conjuntos $f(j)$ . Además, el conjunto $A$ contiene el número $1$ si $1\in f(0)$ , en cuyo caso $B$ no contiene $1$ . De ello se desprende que $A\ne B$ .

Answer 2

Una vez que tenga un conjunto $A$ que no está en $\text{Im}(f)$ se puede construir una nueva función $g:\mathbb N \to \mathcal P(\mathbb N)$ cuya imagen $\text{Im}(g)$ es igual a $\text{Im}(f) \cup A$ (¿ves cómo?). Cualquier conjunto de naturales que no pertenezca a $\text{Im}(g)$ no es a imagen y semejanza de $f$ y es diferente de $A$ (¿ves por qué?).