Preguntas sobre "Todos los caballos son del mismo color" Prueba por inducción completa

Question

Me molesta lo siguiente que se resume en la página 109 de este PDF .

Teorema falso: Todos los caballos son del mismo color.

Prueba por inducción:

$\fbox{$ P(n) $ is the statement: In every set of horses of size $ n $, all $ n $ horses are the same color.}$
$\fbox{Base Case or $ P(1) $:}$ Un caballo es del mismo color que él mismo. Esto es cierto por la inspección.
$\fbox{Induction Step:}$ Supongamos que $P(k)$ para algunos $k \geq 1$ .
$\fbox{Proof of $ P(k + 1) : $}$
Desde $\{H_1, H_2, ... , H_n\}$ es un conjunto de $n$ caballos, la hipótesis de inducción se aplica a este conjunto. Por lo tanto, todos los caballos de este conjunto son del mismo color.
Desde $\{H_2, H_3, ... , H_{n+1}\}$ es también un conjunto de $n$ caballos, el paso de inducción también es válido para este conjunto. Por tanto, todos los caballos de este conjunto son también del mismo color.

Por lo tanto, todos los $n +1$ caballos en $\{H_1, H_2, H_3, ... , H_n , H_{n+1}\}$ son del mismo color. QED.

La cuestión que el instructor trataba de señalar es claramente válida. Para el caso $n = 1$ Sólo hay ${H_1}$ . Por lo tanto, este caso no dice nada sobre los posibles elementos superpuestos de cada conjunto de $(n + 1)$ por ejemplo $H_2$ en la prueba anterior.

Pero se propuso en la discusión en clase que éste era el único problema. Si se hubiera podido demostrar $P(2)$ verdadero, entonces una prueba del formato anterior habría estado bien.

Mi interpretación es que sí, podrías demostrar que todos los caballos son del mismo color, si puedes demostrar que cualquier conjunto de dos caballos será del mismo color. Pero este formato no funcionaría.

¿Por qué no? El problema que veo es que la prueba anterior es para la existencia de al menos un par particular de conjuntos de caballos de tamaños $n$ y $n + 1$ , de manera que en cada conjunto, todos los caballos son del mismo color. En particular, cuando el conjunto de tamaño $n$ es un subconjunto del conjunto de tamaño $n + 1$ . Para demostrar el paso de inducción, ¿no es necesario demostrar que los conjuntos de tamaños $n$ y $n + 1$ no contienen necesariamente los mismos elementos superpuestos?

Podrías demostrar que cualquier caballo puede añadirse a un conjunto de 2 caballos. Toma los dos últimos, y deben ser del mismo color, y así sucesivamente. Sea cual sea el color de los dos primeros, todos los demás caballos deben ser del mismo color.

¿Estoy interpretando mal el ejemplo o estoy cometiendo un error lógico? Gracias de antemano.

Answer 1

Queda claro por la pregunta y por tu discusión con @DonAntonio que en realidad no entiendes el paso de inducción del argumento. Pareces creer que se trata de comparar un conjunto previamente elegido de $n$ caballos con algún nuevo conjunto de $n+1$ caballos, pero no es así. A ver si puedo explicar más claramente cómo funciona.

Asumimos como hipótesis de inducción que si $H$ es cualquier conjunto de $n$ caballos, entonces los caballos en $H$ son todos del mismo color. Ahora dejemos que $H=\{h_1,h_2,\dots,h_{n+1}\}$ sea cualquier conjunto de $n+1$ caballos; nuestro objetivo es demostrar que todos los caballos en $H$ son del mismo color. Para ello, observamos los subconjuntos

$$H_0=\{h_1,\dots,h_n\}\quad\text{and}\quad H_1=\{h_2,\dots,h_{n+1}\}\;.$$

Cada uno de estos subconjuntos contiene $n$ caballos, así que por hipótesis todos los caballos en $H_0$ son del mismo color, y todos los caballos en $H_1$ son del mismo color.

Nota: Los dos $n$ -Los conjuntos de caballos que estamos viendo aquí fueron no que se nos ha dado de antemano: son simplemente dos $n$ -subconjuntos de $H$ . Y de hecho cualquier dos diferentes $n$ -subconjuntos de $H$ funcionará igualmente bien para el argumento.

Ahora bien, si $n\ge 2$ El caballo que he llamado $h_2$ está en ambos $H_0$ y $H_1$ . (De hecho, todos los caballos, excepto $h_1$ y $h_{n+1}$ está en ambos $H_0$ y $H_1$ .) Desde $h_2$ está en $H_0$ y ya sabemos por la hipótesis de inducción que todos los caballos de $H_0$ son del mismo color, se deduce que cada caballo en $H_0$ es del mismo color que $h_2$ . Pero $h_2$ está en $H_1$ también, así que por exactamente el mismo razonamiento concluimos que cada caballo en $H_1$ es del mismo color que $h_2$ . Pero cada caballo en $H$ está en $H_0$ o $H_1$ (o ambos), por lo que cada caballo en $H$ es del mismo color que $h_2$ y, por lo tanto, los caballos en $H$ son todos del mismo color. Esto completa el paso de inducción.

---

No hay absolutamente nada de malo en ese argumento - proporcionó que $n\ge 2$ . En particular, no se trata de empezar con algún conjunto particular de $n$ caballos que se sabe que son del mismo color y tratar de usar ese conjunto para demostrar que los caballos de algún conjunto arbitrario de $n+1$ los caballos son todos del mismo color. El argumento comienza con un conjunto de $n+1$ caballos y procede a examinar dos $n$ -subconjuntos del conjunto dado. Es importante aquí darse cuenta de que la hipótesis de inducción no dice que haya algún conjunto particular de $n$ caballos que son todos del mismo color: dice que en cualquier conjunto de de $n$ caballos, todos los caballos son del mismo color.

El argumento sólo falla cuando $n=1$ . En ese caso falla porque los conjuntos $H_0=\{h_1\}$ y $H_1=\{h_2\}$ ya no se solapan: no hay ningún caballo en ambos conjuntos. Por lo tanto, si bien es cierto que todos los caballos de $H_0$ son del mismo color y que todos los caballos en $H_1$ son del mismo color, ya no podemos inferir que esos dos colores deben ser iguales. Pero si pudiéramos demostrar de alguna manera que en cada conjunto de dos caballos, ambos caballos son del mismo color, el argumento de inducción dado funcionaría perfectamente: siempre estaríamos considerando algún $n\ge 2$ por lo que los conjuntos $H_0$ y $H_1$ se superpondrían.

Answer 2

No estoy seguro de entender del todo tu duda, pero el problema real de eso, y de muchos otros ejemplos de pruebas inductivas falsas que hay, es que cuando tomas los dos conjuntos

$$\{h_1,...,h_n\}\;,\;\;\{h_2,...,h_n,h_{n+1}\}$$

cada uno de tamaño $\,n\,$ y por tanto, por el Ind. Hipótesis, formada por caballos del mismo color, el salto a deducir todos los caballos en conjunto tienen el mismo color requiere que la intersección de ambos conjuntos por encima de no está vacío algo que no se puede probar (¡porque es falso!) si $\,n=2\,$

Así, si tuviéramos la afirmación "cada dos caballos son del mismo color", entonces podríamos demostrar que "todos los caballos son del mismo color"

Answer 3

Aquí hay un problema más básico: la inducción es irrelevante para la prueba.

$P(2)$ es, por sí misma, una formalización de la afirmación de que todos los caballos son del mismo color. No hay ninguna razón para demostrar $P(2)$ para demostrar $P(3)$ para demostrar... $P(n)$ y concluir de esta cadena de implicaciones que todos los caballos son del mismo color; se trataría de demostrar $P(2)$ y en caso de éxito, resumir que "todos los caballos tienen el mismo color".

Si se prueba $P(n)$ fueran de interés por alguna razón, se puede derivar en un solo paso de $P(2)$ sin necesidad de una inducción.

El tamaño del conjunto de caballos suele ignorarse en las presentaciones de este argumento y otros similares. Pero si hay $n$ caballos en el universo, $P(k)$ es una declaración vacía para $k>n$ y es verdadera independientemente del valor de verdad $P(n)$ . Esto demuestra que $P(n)$ es lógicamente más fuerte que $P(n+1)$ y que el paso inductivo de $P(n) $ a $P(n+1)$ es vacuo para grandes $n$ .

Answer 4

Sólo quiero añadir un resumen rápido.

La prueba es "casi" perfecta. Simplemente falla en n=1.

Sí, obviamente cualquier conjunto con 1 caballo tendrá el mismo color. Sin embargo, no se puede extender eso a n=2.

Si puedes probar de alguna manera que cualquier conjunto de 2 caballos tiene el mismo color entonces sí, tienes algo de razón, que cualquier conjunto con cualquier número de caballos tendrá el mismo color.

Answer 5

Como has señalado, $P(1)$ es trivial. Y usted está tratando de demostrar $$P(n)\implies P(n+1)$$ para terminar la prueba. Pero está claro que $P(1)$ hace NO implica $P(2)$ . Por lo tanto, la declaración $$P(n)\implies P(n+1)$$ no es cierto. Y aquí es donde su prueba cae.