Definición inductiva de un conjunto

Question

Soy principiante en teoría de conjuntos y tengo dudas respecto a la inducción matemática. Me encontré con los siguientes ejemplos.

Ejemplo 1:

Encuentra el conjunto dado por la siguiente definición:

1) $3 \in P$

2) Para $x,y \in P, x + y \in P$

3) Sólo los elementos obtenidos de los pasos (1) y (2) están en $P$

Solución: El conjunto $P$ consiste en números enteros positivos que son múltiplos de 3.

Ejemplo 2:

Dar una definición inductiva del conjunto

$P = \{2,3,4,\ldots\} = N - \{0,1\}$

Solución:

1) $2 \in P$ y $3 \in P$

2) Si $x,y \in P$ entonces $x+y \in P$ .

3) Sólo los elementos obtenidos en los pasos 1 y 2 están en $P$ .

¿Podría alguien explicar los dos ejemplos anteriores y cómo escribir este tipo de definiciones? Lo he buscado en google, pero no he conseguido lo que necesito. Gracias de antemano.

Answer 1

Revisemos la primera solución, es un poco más sencilla.

Comenzamos con un conjunto $P_0=\{3\}$ . Esa es la base de la inducción. Supongamos ahora que $P_n$ se definió, tomamos $P_{n+1}$ ser $P_n$ con la adición de todos los elementos de la forma $x+y$ donde $x,y\in P_n$ .

Por fin, $P$ es la unión de los $P_n$ a saber $\bigcup_{n=0}^\infty P_n$ .

Podemos hacer los primeros pasos explícitamente, para tener la sensación:

• $P_0=\{3\}$ Esa es la definición del primer paso.
• $P_1=\{3,3+3\}$ tomamos $P_0$ y añadió $3+3$ que es la única combinación posible de $x+y$ donde $x,y\in P_0$ .
• $P_2=\{3,6,9,12\}$ tomamos $P_1$ y ahora añadimos $3+6$ y $6+6$ . No necesitamos añadir $3+3$ porque ya está ahí.
• $P_3=\{3,6,9,12,15,18,24\}$ añadimos $3+12,6+12,9+12,12+12$ . Obsérvese que esto también incluía otros pares como $6+9,9+9$ etc.

Para demostrar que efectivamente $P$ son todos los múltiplos de $3$ tenemos que argumentar que si $n=3m$ entonces hay algún $k$ tal que $n\in P_k$ . Demostramos esto por inducción, por supuesto, en $m$ .

1. Si $m=1$ entonces $n=3$ y por lo tanto $n\in P_0$ .
2. Supongamos que para $3m$ demostramos que $3m\in P_k$ para algunos $k$ y que $n=3(m+1)$ . Desde $3\in P_k$ tenemos que $3m+3\in P_{k+1}$ y, por lo tanto $n=3(m+1)=3m+3\in P_{k+1}$ .

Ahora tenemos que demostrar que si un número está en $P$ entonces es múltiplo de $3$ . De nuevo lo hacemos por inducción, por ejemplo podemos hacerlo por inducción sobre el índice de $P_k$ a saber:

• Sabemos que $P_0=\{3\}$ y por tanto todos sus elementos son múltiplos de $3$ .

• Supongamos que para $P_k$ es cierto que todos sus elementos son múltiplos de $3$ demostraremos que esto es cierto para $P_{k+1}$ .

  Supongamos que $n\in P_{k+1}$ entonces, por la definición de $P_{k+1}$ hay $x,y\in P_k$ tal que $n=x+y$ . A partir de la hipótesis de inducción para $P_k$ tenemos que $x,y$ son ambos múltiplos de $3$ y, por tanto, su suma, $n$ también es múltiplo de $3$ .

---

Por fin:

Hemos visto cuál es exactamente la definición de $P$ y hemos visto cómo demostrar que efectivamente tiene la propiedad deseada. Demostramos estas cosas cuidadosamente por inducción, utilizando la definición inductiva de las etapas que construyen $P$ .

Answer 2

Primero demostraremos la corrección de las dos soluciones:

1. $P = 3\mathbb{N}$ .

   • Dado $z \in P$ entonces $z = 3$ en cuyo caso $z \in 3\mathbb{N}$ o $z = x+y$ para $x,y\in P$ . Tras un número finito de pasos y sustituciones (como máximo $\frac{z}{3}$ ) vemos que $z = \underbrace{3+\cdots+3}_n = 3n \in 3\mathbb{N}$ .
   • A la inversa, sea dado $3n\in 3\mathbb{N}$ . Para $n=1$ , $3n=3\in P$ . Supongamos que $3(n-1)\in P$ para algunos $n$ entonces $3n = 3+3(n-1)\in P$ por la parte 2 de la definición de $P$ . Por inducción en $n\in\mathbb{N}$ vemos $3\mathbb{N}\subset P$ .

2. $P = \mathbb{N}\setminus\left\{0,1\right\}$

   • Claramente, cualquier suma finita de 2's y 3's está en $\mathbb{N}$ Así que $P\subset\mathbb{N}\setminus\left\{0,1\right\}$
   • A la inversa, dado $z\in\mathbb{N}\setminus\left\{0,1\right\}$ . Considere la mayor $n\in\mathbb{N}$ tal que $z_n:=z-2n>1$ . Si $z_n=2$ entonces $z$ es una suma finita de 2's, tal que $z\in P$ . Si $z_n=3$ entonces $z=2n+3\in P$ . Esto agota todas las posibilidades, ya que si $z_n>3$ entonces $z_{n+1}>1$ lo que contradice la maximalidad de $n$ .

Los ejemplos que has dado no están tan relacionados con la teoría de conjuntos como con la teoría de números. Para inventar tú mismo esos ejemplos, necesitas entender los principios básicos de la recursividad y la inducción. Véase también, http://en.wikipedia.org/wiki/Mathematical_induction

Un ejemplo típico de inducción en teoría de conjuntos es el siguiente: Un conjunto $T$ se llama transitivo si $\forall x\in T: x\subset T$ . Un conjunto se denomina ordinal si es transitiva y está bien ordenada por $\in$ . Sea $S$ sea el conjunto de todos los ordinales finitos. Ahora puedes demostrar que existe una biyección $\mathbb{N}\to S$ . Pista: $0\mapsto \emptyset$ , $1\mapsto\left\{\emptyset\right\}$ , $2\mapsto\left\{\emptyset,\left\{\emptyset\right\}\right\}$ , $\cdots$