6.9: Descenso infinito
- Page ID
- 108179
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)En esta sección final abordamos una variación importante sobre la inducción matemática. Esta variación está bien ilustrada por el siguiente problema (probablemente familiar).
Problema 267 Escribe por ti mismo la siguiente prueba estándar quees irracional.
i) Supongamos al contrario quees racional. Entoncespara algunos enteros positivos m, n. Demostrar primero que m debe ser parejo.
(ii) Escribir, dondetambién es un número entero. Demuestre que n también debe ser parejo.
iii) ¿Cómo lleva esto a una contradicción?
Problema 267. tiene la forma clásica de una prueba que alcanza una contradicción por descenso infinito.
- Comenzamos con una afirmación que deseamos probar que es cierta. Muchas veces cuando no sabemos cómo empezar, tiene sentido preguntar qué pasaría si la afirmación fuera falsa. Esto garantiza entonces que debe haber algún contraejemplo, que satisfaga la hipótesis dada, pero que no satisfaga la conclusión aseverada.
- El descenso infinito se convierte en una opción cada vez que cada contraejemplo da lugar a algún parámetro entero positivo n (como el denominador en el Problema 267. (i)).
- El descenso infinito se convierte en una realidad, si se puede probar que la existencia del contraejemplo inicial conduce a una construcción que produce un contraejemplo con un valor menordel parámetro n, ya que repetir este paso da lugar entonces a una secuencia infinitamente decrecientede enteros positivos, lo cual es imposible (ya que tal cadena puede tener longitud como máximo n).
- De ahí que la suposición inicial de que la pretensión era falsa debe ser en sí misma falsa —por lo que la pretensión debe ser verdadera (según se requiera)
La prueba por “descenso infinito” es una herramienta invaluable. Pero es importante darse cuenta de que el método es esencialmente una variación en la prueba por inducción matemática. Como primer paso en esta dirección merece la pena reinterpretar el Problema 267. como prueba de inducción.
Problema 268 Vamosser la declaración:
”no se puede escribir como una fracción con denominador positivo”.
i) Explicar por quées verdad.
ii) Supongamos quees cierto para algunos. Utilice la prueba en Problema 267. para demostrar quedebe ser entonces cierto también.
iii) Concluir quees cierto para todos, de dondedebe ser irracional.
Problema 268. muestra que, en el caso particular del Problema 267. se puede traducir la prueba estándar de que”es irracional” en una prueba por inducción. Pero mucho más es cierto. La contradicción que surge en el paso 3. anterior es una aplicación de un principio importante, a saber
El principio del elemento mínimo: Cada conjunto S no vacío de enteros positivos tiene un elemento más pequeño.
El Principio de Menor Elemento es equivalente a El Principio de Inducción Matemática que afirmamos al inicio del capítulo:
El Principio de Inducción Matemática: Si un subconjunto S de los enteros positivos
entonces S contiene todos los enteros positivos.
- contiene el entero “1”, y tiene la propiedad que
- siempre que un entero k esté en el conjunto S, entonces el siguiente enterosiempre está en S también,
Problema 269
a) Asumir el Principio del Elemento Mínimo. Supongamos que un subconjunto T de los enteros positivos contiene el entero “1”, y que cada vez que k está en el conjunto T, entoncestambién está en el conjunto T. Sea S el conjunto de todos los enteros positivos que no estén en el conjunto T. Concluir que S debe estar vacío, y por lo tanto que T contiene todos los enteros positivos.
b) Asumir el Principio de Inducción Matemática. Sea T un conjunto no vacío de enteros positivos, y supongamos que T no tiene un elemento más pequeño. Sea S el conjunto de todos los enteros positivos que no pertenecen al conjunto T. Demostrar que “1” debe pertenecer a S, y que siempre que el entero positivo k pertenece a S, entonces también lo hace. Derivar la contradicción de que T debe estar vacío, contrario a la suposición. Concluir que T debe de hecho tener un elemento más pequeño.
Para redondear este último capítulo se le invita a idear una prueba bastante diferente de la irracionalidad de.
Problema 270 Esta secuencia de construcciones supone que sabemos —por ejemplo, por el Teorema de Pitágoras— que, en cualquier cuadrado
“diagonal: lateral”.
Vamos
i) Explicar por qué. Construir el puntopara completar el cuadrado.
(ii) Unirse. Explicar por qué.
(iii) Supongamos. Concluir que.
iv) Demostrar que, y de ahí que,.
(v) Explicar cómo, si m, n se puede elegir para que sean enteros positivos, la secuencia de pasos anterior establece un “descenso infinito” —lo cual es imposible.