Autor Tema: ¿Cómo saber cuando un caso base es válido?

0 Usuarios y 1 Visitante están viendo este tema.

26 Abril, 2018, 09:31 am
Leído 6049 veces

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
Supongamos que, en una demostración por inducción, podemos demostrar que dado un \( n\in\Bbb N \) \( P(n)\implies P(n+1) \), y luego definimos ad hoc que \( P(0) \) es cierto, y ocurre que demostrar que otro caso base distinto del cero es difícil.

Obviamente esa demostración por inducción no es correcta (en principio es dudoso que el paso inductivo pueda demostrarse en tal contexto). Pero supongamos que tenemos una situación donde demostrar \( P(0) \) es trivial pero demostrar otro caso base no es fácil, y donde no está del todo claro si \( P(0) \) es cierto por convención o por razones algebraicas, ¿hay algún modo sencillo de saber si un caso base dudoso es realmente válido?

Un ejemplo de esto me ha ocurrido recientemente, de ahí la pregunta, es éste:

Sea \( \Bbb J(n) \) el conjunto de intervalos (acotados) en \( \Bbb R^n \), los cuales se definen como el producto cartesiano de \( n \) intervalos acotados en la línea real, incluyendo al conjunto vacío como intervalo. Entonces quiero demostrar que, dada una colección finita \( I,J_1,J_2,\ldots,J_m\in\Bbb J(n) \) entonces existe una colección finita \( H_1,H_2,\ldots,H_ñ\in\Bbb J(n) \) tal que

\( \displaystyle I\setminus\left(\bigcup_{k=1}^m J_k\right)=\bigsqcup_{k=1}^ñ H_k\tag1 \)

donde la "unión cuadrada" de la derecha en \( (1) \) quiere decir que los conjuntos \( H_k \) son disjuntos. Entonces utilizando inducción en \( m \) el caso base \( m=0 \) es trivial, y sin embargo el caso base \( m=1 \) no lo es en absoluto. Y además demostrar el paso inductivo es muy sencillo, por tanto no queda del todo claro si la demostración es correcta o no, a pesar de que la unión vacía no parece ser una convención, como parecen indicar diferentes fuentes, es un caso tan particular que parece que podría no ser una base inductiva válida.

Para despejar dudas, la demostración del paso inductivo es la siguiente: supongamos que la hipótesis se cumple para todo \( 1\le k\le m \), entonces

\( \displaystyle I\setminus\left(\bigcup_{k=1}^{m+1}J_k\right)=\left(I\setminus\left(\bigcup_{k=1}^m J_k\right)\right)\setminus J_{m+1}=\left(\bigsqcup_{j=1}^r H_j\right)\setminus J_{m+1}\\=\left(\bigsqcup_{j=1}^r H_j\right)\cap J_{m+1}^\complement=\bigsqcup_{j=1}^r(H_j\cap J_{m+1}^\complement)=\bigsqcup_{j=1}^r(H_j\setminus J_{m+1}) \)

Entonces aplicando la hipótesis de nuevo en \( H_k\setminus J_{m+1} \) terminamos la demostración.



Con otra formalización del problema parece que el caso base de \( m=0 \) es válido. Pero la cuestión no es ésa sino conocer si hay algún medio para verificar que un caso base dudoso es válido o no lo es.

26 Abril, 2018, 11:22 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La cuestión no es saber si el caso \( m=0 \) es válido o no es válido. Si lo consideras dudoso, entonces el problema es el mismo que se da ante cualquier situación dudosa, es decir, disipar la duda. Se trata de ver si el caso base cumple o no en sentido estricto lo que pretendes demostrar, y eso no es un problema particular de las inducciones, sino que en cualquier contexto matemático vas a tener que ser capaz de decidir si cualquier afirmación que uses es correcta o no.

En este caso en concreto, podemos decir que el caso \( m=0 \) es trivialmente válido, pues se entiende que una unión con \( 0 \) términos es el conjunto vacío, y lo que tiene que probarse es que \( I\setminus\emptyset =I \) se expresa como unión disjunta de intervalos, lo cual es cierto, como la unión de la familia de intervalos formada sólo por \( I \). Luego no hay nada "dudoso" en este caso base.

Pero la cuestión es ahora si el argumento que prueba \( P(n)\rightarrow P(n+1) \) es válido cuando \( n=0 \). Si lo es, ya tienes el teorema probado, pero si no lo es, entonces tendrás que probar \( P(1) \) aparte (lo cual es equivalente a probar \( P(0)\rightarrow P(1) \) mediante un argumento separado, ya que el general no vale).

En efecto, en este caso vemos que el argumento general que has dado no se aplica a \( m=0 \). Lo copio, lo pego y lo particularizo:

\( \displaystyle I\setminus\left(\bigcup_{k=1}^{1}J_k\right)=\left(I\setminus\left(\bigcup_{k=1}^0 J_k\right)\right)\setminus J_{1}=I\setminus J_{1}\\=I\cap J_{1}^\complement=I\cap J_{1}^\complement=I\setminus J_{1} \)

Y vemos que ahora necesitas aplicar que el resultado es válido para \( m=1 \), cuando sólo sabes que lo es en \( m=0 \). Por eso no es válido el razonamiento, no porque haya nada dudoso en el caso \( m=0 \), sino porque el argumento que empleas para probar \( P(n)\rightarrow P(n+1) \) se vuelve circular cuando \( m=0 \), lo que requiere probar aparte el caso \( P(1) \).

26 Abril, 2018, 12:45 pm
Respuesta #2

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
Muchísimas gracias Carlos, me lo has dejado clarísimo. Ahora entiendo mejor este tipo de demostraciones.

 :aplauso: :aplauso: :aplauso:

26 Abril, 2018, 01:05 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Un ejemplo típico de algo análogo es lo que en la Wikipedia aparece como Paradoja del Caballo. La morajela es que si se toma como caso base \( n_0 \), hay que estar seguros de que el paso inductivo \( P(n)\to P(n+1) \) es correcto para cualquier \( n\geq n_0 \).

Saludos.

26 Abril, 2018, 04:06 pm
Respuesta #4

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
Hola

 Un ejemplo típico de algo análogo es lo que en la Wikipedia aparece como Paradoja del Caballo. La morajela es que si se toma como caso base \( n_0 \), hay que estar seguros de que el paso inductivo \( P(n)\to P(n+1) \) es correcto para cualquier \( n\geq n_0 \).

Saludos.

Ah, no conocía esa paradoja, muy ilustrativa.

Sí, repasando la teoría del principio inductivo me había saltado la parte que dice que \( P(n)\implies P(n+1) \) debe ser cierto para todo \( n \) mayor o igual al caso base. La verdad es que hasta ahora no me había encontrado ningún caso donde eso no ocurriese habiendo un caso base válido.