You are currently browsing the monthly archive for octubre 2015.

   Hace poco estuve revisando un pequeño problema en el que se pedía aplicar inducción.

Ejercicio 1. Sea {n} un número natural positivo, {n\ge2}. Entonces

\displaystyle  \sum_{k=1}^n\frac1{k^2}<2-\frac1n.

   Vi lo siguiente en un intento de prueba:

\displaystyle  \sum_{k=1}^k\frac1{k^2}+\frac1{(k+1)^2}<2-\frac1{k+1},

sin saber cómo seguir.

   Para obtener la prueba deseada, supongamos que

\displaystyle  \sum_{k=1}^n\frac1{k^2}<2-\frac1n.

Entonces

\displaystyle \begin{aligned} \sum_{k=1}^{n+1}\frac1{k^2}&=&\sum_{k=1}^n\frac1{k^2}+\frac1{(n+1)^2}\\&=&2-\frac1n+\frac1{(n+1)^2}.\end{aligned}

Así, el problema queda reducido a mostrar que

\displaystyle -\frac1n+\frac1{(n+1)^2}\ge-\frac1{n+1},

lo cual es sencillo de realizar con algo de álgebra. El punto es que uno tiene que usar el supuesto que funciona para {n}. Además, cuando usamos {k} como índice de la suma, no deberíamos usar {k} en cualquier lugar como se hizo anteriormente.

Anuncios

   Ahora veremos una relación interesante aplicando la inducción fuerte. Por ejemplo, tenemos que {36=9\times2^2}, {80=5\times2^4}, {17=17\times2^0}, {64=1\times2^6}, etc.

   Así, nos proponemos probar que todo número natural {n} puede ser escrito como producto de un número impar y un número potencia de dos.

   Para probar algo por inducción fuerte, tenemos que probar que <> es verdadera para todo {N}. De manera que nuestra hipótesis de inducción sería: todo número natural {k} que es estrictamente menor que {n} puede puede ser escrito como un producto de un número impar y una potencia de {2}. Y queremos probar que, desde esta hipótesis, podemos concluir que {n} también puede ser escrito como un producto de un número impar y una potencia de {2}.

   Para ello, tenemos dos casos: o bien {n} es impar, o bien {n} es par. Si podemos probar que el resultado se mantiene para ambos casos, habremos concluido satisfactoriamente.

Caso 1. Supongamos que {n} es impar. Entonces podemos escribir {n=n\times2^0}, con lo que concluimos. Así, en el Caso 1, el resultado se mantiene para {n}.

Caso 2. Ahora supongamos que {n} es par, por lo que {n=2k} para algún número natural {k}. Pero entonces {k<n}; de manera que, podemos aplicar nuestra hipótesis de inducción a {k}. Concluimos que… (Acá el lector ya habrá podido finalizar estar parte.) 🙂

   Por lo tanto, tenemos que el resultado se cumple para todos los números naturales por la inducción fuerte.

   En lógica proposicional clásica podemos probar que la siguiente proposición es válida:

\displaystyle  (A \iff B) \lor (A \iff C) \lor (B \iff C),

donde {A}, {B} y {C} representan proposiciones, cada una de la cuales puede ser verdadera o falsa. El punto de la cuestión es que, no importa qué son esas proposiciones o cuáles de ellas (si las hay) son ciertas: la proposición mostrada es verdadera sin importar qué.

   Podemos probar esta proposición mediante una tabla de verdad. Sin embargo, de hecho no es necesario usarla. La proposición {(A\iff B)\lor(A\iff C)\lor(B\iff C)} es verdadera si, y sólo si, al menos uno de los disyuntos {A\iff B}, {A\iff C} y {B\iff C} es verdadero. Así, sabemos que la proposición {A\iff B} es verdadera exactamente cuando {A} y {B} tienen el mismo valor de verdad: ambos son verdaderos o ambos son falsos. Análogamente, la proposición {A\iff C} es verdadera exactamente cuando {A} y {C} tienen el mismo valor de verdad, y {B\iff C} es verdadera exactamente cuando {B} y {C} tienen el mismo valor de verdad.

   Ya que sólo hay dos valores de verdad en la lógica proposicional clásica, no importa como asignemos los valores de verdad a las proposiciones {A}, {B} y {C}, dos de las cuales tiene el mismo valor de verdad. Esto quiere decir que bajo cualquier asignación de valores de verdad a {A}, {B}, y {C}, al menos uno de los tres disyuntos tiene que ser verdadero, y, por lo tanto, toda la proposición también debe ser verdadera.

   Suele suceder que uno puede saber como probar por contradicción una afirmación, pero a la vez no estar seguro de cómo abordarlo. Es usual que escribamos una prueba en la forma «{P\text{ implica }Q}», luego si podemos probar que «{P\text{ y no }Q}» es falso, tenemos que «{P\text{ implica }Q}» debe ser verdadero.

Ejercicio 1. Sea {c} un entero positivo que no es primo. Mostrar que hay algún entero positivo {b} tal que {b\mid c} y {b\leq\sqrt{c}}.

   En este caso, escribimos: si {c} es un entero positivo compuesto, entonces {b|c} y {b\leq\sqrt{c}} para algún entero positivo {b}.

   Uno podría suponer que mientras que se asuma que {b|c} o {b>\sqrt{c}}, esto todavía esa válido como «{\text{no }Q}»; es decir, ¿no tenemos que asumir el recíproco de ambas partes de {Q}?

   Además, cuando {b>\sqrt{c}} y {b|c}, tenemos {br=c} para algún entero {r}, para el cual {r<\sqrt{c}}.

   Cuando negamos una afirmación con cuantificadores, necesitamos dar la vuelta a los cuantificadores. Por ejemplo, lo opuesto de «todo gato es blanco» no es «todo gato no es blanco», sino «hay algún gato que no es blanco».

   En este caso, la negación correcta de «hay algún {b} tal que {b|c} y {b\le\sqrt{c}}», si deseamos mantener la condición que {b} es un divisor, es «para todo {b} tal que {b|c}, {b>\sqrt{c}}». Esta es la afirmación desde la cual podemos probar una contradicción: para todo {b} que satisface esta condición, {\frac{c}{b}} también debe satisfacer esta condición; lo que da la contradicción {c>c}. (Y se quiere la condición que {b>1} o de lo contrario el problema es trivial.)

   Es sencillo ver que, para mostrar que {\mathbb Q} es numerable, es suficiente mostrar la numerabilidad de {\mathbb Q^+} o incluso de {\mathbb Q\cap(0,1]}.

   Hay una manera sencilla de enumerar este último: primero las fracciones con denominados {1}, luego aquellos con denominador {2} (obviando los que ya fueron listados), luego aquellos con denominador {3} (nuevamente, evitando repeticiones), etc. Esta lista empieza con

\displaystyle  \frac11;\frac12;\frac13,\frac23;\frac14,\frac34;\frac15,\frac25,\frac35,\frac45;\dots

   La primera prueba de Cantor de la no numerabilidad de los reales (el argumento de los intervalos anidados) de 1874 procede como sigue:

   Dado cualquier sucesión (inyectiva) {a_1,a_2,\dots} de números reales, deseamos mostrar un número real que no es listado. Tenemos dos casos: hay {i\ne j} con {a_i<a_j}, y tal que no hay {k} con {a_k\in(a_i,a_j)}, en cual caso obviamente se ha culminado; o (más interesante), siempre que {a_i<a_j}, podemos hallar un {a_k} estrictamente entre ellos (el rango de la sucesión es dense sobre sí mismo). Asumamos que estamos en esta situación.

   Definimos dos sucesiones {b_1,b_2,\dots} y {c_1,c_2,\dots} como sigue:

  1. Primero, {b_1=a_1} y {c_1=a_2}.
  2. Por definición, suponer que {a_1>a_2}. El otro caso es tratado similarmente. Sea {b_2=a_i}, donde {i} es el menor tal que {a_i\in(c_1,b_1)}. Entonces definimos {c_2} como {a_j}, donde {j} es el menor tal que {a_j\in(c_1,b_2)}.
  3. En general, dado {c_n<b_n}, definimos {b_{n+1}} como {a_k}, donde {k} es el menor tal que {a_k\in(c_n,b_n)}, y luego definimos {c_{n+1}} como {a_m}, donde {m} es el menor tal que {a_m\in(c_n,b_{n+1})}. Notar que estas sucesiones están bien definidas debido a nuestra hipótesis de densidad.

   La construcción que se acaba de describir asegura que si {I_n=[c_n,b_n]}, entonces:

  1. Para cualquier {n}, tenemos que {a_n\notin I_{n+1}}, y
  2. Los intervalos están anidados y son decrecientes: {I_1\supsetneq I_2\supsetneq I_3\dots}

   Se sigue (de la completitud de los reales) que {\bigcap_n I_n\ne\emptyset}, y (de a.) que cualquier número real en esta intersección no está en el rango de la sucesión {a_1,a_2,\dots}

   Resulta que si llevamos a cabo la construcción de Cantor cuando la sucesión de {a_i} es la enumeración de los números racionales en {(0,1]} con los que comenzamos, entonces {\bigcap_n I_n=\{1/\phi\}}, donde {\phi} es la proporción áurea.

   Hay una agradable enumeración de {\mathbb Q^+} con un significado de combinatoria.

   Los racionales son usados para etiquetar los nodos de un árbol binario completo infinito, y la enumeración resultante simplemente sigue los nodos del árbol lexicográficamente.

\displaystyle  \begin{array}{ccccccccccccccc} & & & & & & & \frac11 \\\\ & & & \frac12 & & & & & & & & \frac21 \\\\ & \frac13 & & & & \frac32 & & & & \frac23 & & & & \frac31 \\\\ \frac14 & & \frac43 & & \frac35 & & \frac52 & & \frac25 & & \frac53 & & \frac34 & & \frac41 \end{array}

Empezamos poniendo {1/1} en la raíz del árbol. Una vez que un nodo ha sido etiquetado con {m/n}, su sucesor izquierdo es etiquetado {m/(m+n)}, y su sucesor derecho es {(m+n)/n}.

¡Y eso es todo! La lista así producida empieza

\displaystyle  \frac11;\frac12,\frac21;\frac13,\frac32,\frac23,\frac31;\dots

   La prueba de que esta es en efecto una lista biyectiva de {\mathbb Q^+} es muy simple; se verifica en el siguiente orden de afirmaciones:

  1. El numerado y el denominador de cualquiera de las fracciones asignadas son primos relativos.
  2. Todo racional positivo es asignado a algún nodo.

   Para esto, procedemos por inducción. Por ejemplo, si hay una fracción {m/n} no en su forma reducida, y usado como una etiqueta, escoger esa fracción que aparece en el menor nivel posible, y notar que la fracción no puede ser {1/1}. Una contradicción es ahora alcanza señalando que {\mathrm{gcd}(m,n)=\mathrm{gcd}(m-n,n)=\mathrm{gcd}(m,n-m)}.

   Similarmente, si {m/n} aparece en más de un nodo, entonces {m\ne n}, y su predecesor inmediato (bien {(m-n)/n} o {m/(n-m)}, dependiendo de si {m>n} o {m<n}) debe también aparecer en más de una vez.

   Finalmente, si alguna fracción no está listada, podemos elegir su denominador {n} menos entre los denominadores de todos las fracciones omitidas, y entonces elegimos su numerador {m} menos entre los numeradores de todas las fracciones omitidas con denominador {n}. Una contradicción sigue debido a que {m\ne n}, y si {m>n}, entonces {(m-n)/n} también debe haber sido omitido, pero {m-n<m}, mientras que si {m<n}, entonces {m/(n-m)} deben haber sido omitida, pero {n-m<n}

   También se muestran las siguientes las siguientes propiedades combinatorias interesantes:

  1. Hay una sucesión {b(0),b(1),b(2),\dots} de enteros positivos tal que la {n}-ésima fracción en la enumeración es sólo {\displaystyle\frac{b(n)}{b(n+1)}} (en su forma reducida). En particular, el denominador de una fracción es el numerador de su sucesor en la enumeración. De manera que {b(0)=1}, {b(1)=1}, {b(2)=2}, {b(3)=1}, {b(4)=3}, {b(5)=2}, {b(6)=3}, etc.
  2. De hecho, {b(n)} es precisamente el número de maneras de escribir {n} como una suma de potencias de {2}, donde cada potencia puede ser usada a lo sumo dos veces. Por ejemplo, {b(6)=3}, debido a que podemos escribir {6} como {2^2+2^1}, como {2^2+2^0+2^0}, o como {2^1+2^1+2^0+2^0}.

   Algunas preguntas naturales:

  1. ¿Qué podemos decir acerca del real (o los reales) que salen cuando el procedimiento de la prueba de Cantor es aplicado para esta enumeración?
  2. ¿Cualquier camino infinito a través del árbol binario define una sucesión de racionales? ¿Qué números reales aparecen como puntos límites de estas sucesiones?

   Hace poco consultaban sobre la posibilidad de extender los números complejos de manera que {\mathbf C\subset\mathbf C[a]}, o si {\mathbf C} es la extensión final en el sentido que no si se extiende cualquier cuerpo se termina en {\mathbf C}.

   Pues bien, dado cualquier cuerpo, siempre podemos construir cuerpos más grandes, Si nuestro cuerpo no es algebraicamente cerrado, podemos añadir nuevas raíces de polinomios, también podemos añadir elementos trascendentes (lo que es equivalente a formar un cuerpo de funciones racionales). De hecho, toda extensión de cuerpo es una extensión algebraica de una extensión puramente trascendental. (Como {\mathbf C} es alegóricamente cerrado, no tiene extensiones algebraicas, por lo que no son finitos.)

   En particular, {\mathbf C(T)} (el cuerpo de las funciones racionales en la variable {T} con coeficientes complejos) es más grande que {\mathbf C} en el sentido de la inclusión de la teoría de conjuntos. Sin embargo, la cerradura algebraica tiene la misma cardinalidad que la propia {\mathbf C}, y por consiguiente es abstractamente isomórfica a {\mathbf C}, lo que quiere decir que hay una manera de embeber {\mathbf C(T)} dentro de {\mathbf C}. Si deseamos obtener otro más grande en el sentido de la cardinalidad, podemos formar el cuerpo de las funciones racionales con coeficientes complejos en {\kappa} variables, donde {\kappa} es un número cardinal más grande que el continuo {\mathfrak{c}=|\mathbf{C}|}. Lo que es ciertamente más grande.

   Notemos que no hay ningún subanillo del anillo de polinomios {\mathbf{C}[T]} que es un cuerpo y que estrictamente contiene al propio {\mathbf C}, pero si lo hubiera, podría contener algún {f(T)} no constante, y por lo tanto contiene el elemento no polinomial {f(T)^{-1}}, lo que es imposible dentro de {\mathbf C[T]}.

   También notemos que los cuerpos de diferentes características son incompatibles: los cuerpos de diferentes características nunca pueden estar contenidas dentro de un cuerpo común. De manera que no sólo tenemos el hecho que no hay un cuerpo al final de todos los cuerpos, pero la la clase de todos los cuerpos se adentra en diferentes direcciones mutuamente exclusivas (uno por cada primo y cero).

   Es usual definir los límites superior e inferior de una sucesión {(a_n)_{n=1}^\infty} de números reales de la siguiente manera:

\displaystyle  \limsup a_n := \lim_{N\rightarrow\infty}\sup\{a_n:n>N\}

y

\displaystyle  \liminf a_n := \lim_{N\rightarrow\infty}\inf\{a_n:n>N\}.

Del lado derecho de ambas definiciones, ¿podemos pensar {\sup\{a_n:n>N\}} y {\inf\{s_n:n>N\}} como una sucesión con {n>N}? ¿Cómo se comportan cuando {n} incrementa? ¿Decrecen confirme {n} crece?

   Consideremos este ejemplo:

\displaystyle  3-\frac12,\quad 5+\frac13,\quad 3-\frac14,\quad 5+\frac15,\quad 3-\frac16,\quad 5+\frac17,\quad 3-\frac18,\quad 5+\frac19,\quad\ldots

   Esta sucesión alterna aproximándose algo a {3} desde abajo y aproximándose algo a {5} desde arriba. Así, su límite inferior es {3} y su límite superior es {5}.

   El ínfimo de toda la sucesión es {3-\frac12}.

   Si uno retira el primer término, o los dos primeros, el ínfimo de los que queda es {3-\frac14}.

   De los restante, si uno retira el primer término, o los dos primeros, el ínfimo de los que queda es {3-\frac16}.

   De los restante, si uno retira el primer término, o los dos primeros, el ínfimo de los que queda es {3-\frac18}.

   De los restante, si uno retira el primer término, o los dos primeros, el ínfimo de los que queda es {3-\frac1{10}}.

… y así sucesivamente. Vemos que estos ínfimos son cada vez más grandes.

   Observando la sucesión de ínfimos, vemos que sus supremo es {3}.

   Así el límite inferior es el supremo de la sucesión de ínfimos de todos las sucesiones restantes de la sucesión inicial, es decir, las colas de la sucesión inicial. Con la notación, tenemos

\displaystyle  \begin{aligned} \liminf_{n\rightarrow\infty} a_n & = \sup_{n=1,2,3,\ldots} \inf_{m=n,n+1,n+2,\ldots} a_m \\ & = \sup_{n=1,2,3,\ldots} \inf\left\{ a_n, a_{n+1}, a_{n+2}, a_{n+3},\ldots \right\} \\ & = \sup\left\{ \inf\left\{ a_n, a_{n+1}, a_{n+2}, a_{n+3},\ldots \right\} : n=1,2,3,\ldots \right\} \\ & = \sup\left\{ \inf\{ a_m : m\ge n\} : n=1,2,3,\ldots \right\}. \end{aligned}

   Así como el límite inferior es el supremo de los ínfimos, tenemos que el límite superior es el ínfimo de los supremos.

   Uno también puede decir que {L=\liminf_{n\rightarrow\infty} a_n} precisamente si para cualquier de los {\varepsilon>0}, sin importar cuan pequeños, hay algún índice {N} arbitrariamente grande de manera que para cada {n\ge N}, {a_n>L-\varepsilon}, y {L} es el mayor número para el cual esto se cumple.