Archivo de la categoría: Matemáticas

Posts de matemáticas, la ciencia más cercana a las artes.

Álgebra Lineal II: Polinomio característico de familias especiales

2 respuestas

Introducción

En la entrada anterior dimos la definición de polinomio característico. Vimos que siempre es un polinomio mónico y que su grado es exactamente del tamaño de la matriz. También, vimos cómo calcular el polinomio mínimo en algunos casos particulares. En esta entrada veremos varias propiedades que nos van a facilitar el calcular el polinomio característico (y por tanto los eigenvalores) en un amplio rango de matrices diferentes.

Comenzaremos estudiando el polinomio mínimo de las triangulares superiores. Luego, veremos cómo calcular el polinomio de matrices nilpotentes. No solo nos harán la vida más fácil los resultados a continuación, si no que los usaremos en la teoría más adelante.

Matrices triangulares superiores y transpuestas

El caso de las matrices triangulares superiores es muy sencillo, como veremos a través del siguiente problema.

Problema. Sea A=[a_{ij}] una matriz triangular superior. Demuestra que

    \begin{align*}\chi_A(X)=\prod_{i=1}^{n}(X-a_{ii}).\end{align*}

Solución. La matriz X I_n-A sigue siendo triangular superior, y sus entradas diagonales son precisamente X-a_{ii}. Usando que el determinante de una matriz triangular superior es el producto de sus entradas diagonales y usando la definición se sigue que

    \begin{align*}\chi_A(X)=\det(X I_n-A)=\prod_{i=1}^{n} (X-a_{ii}).\end{align*}

\square

Ejemplo. Si queremos calcular el polinomio característico de la matriz

    \begin{align*}A=\begin{pmatrix}1 & -\pi & \sqrt{2}\\0 & -2 & 10^{10}\\0 & 0 &3\end{pmatrix}.\end{align*}

entonces podemos aplicar el problema anterior y deducir inmediatamente que

    \begin{align*}\chi_A(X)=(X-1)(X+2)(X-3).\end{align*}

¡Qué complicado hubiera sido calcular el determinante a pie!

\square

Por otro lado, recordando la demostración que dice que los eigenvalores de la transpuesta de una matriz son iguales a los de la matriz original era de esperarse que el polinomio característico también «se portara bien» bajo transposición.

Problema. Demuestra que las matrices A y ^{t}A tienen el mismo polinomio característico para cualquier A\in M_n(F).

Solución. Notamos que ^{t}(X I_n-A)= XI_n-\ ^{t}A. Como una matriz y su transpuesta tienen el mismo determinante se tiene que

    \begin{align*}\chi_A(X)&=\det(XI_n-A)\\&=\det(\ ^{t}(XI_n-A))\\&= \det(XI_n-\ ^{t}A)\\&=\chi_{^t A}(X).\end{align*}

\square

Estrictamente hablando, estamos haciendo un poquito de trampa en la demostración anterior (y de hecho en varias que involucran a la variable X). Las propiedades de determinantes que hemos visto (como que una matriz y su transpuesta tienen el mismo determinante) las obtuvimos partiendo de la hipótesis de que las entradas vienen de un campo F. Pero cuando agregamos a la variable X, ahora las entradas vienen más bien de un anillo: el anillo de polinomios en F[X]. Aunque esto parezca un problema, en realidad no lo es. Las propiedades que usamos pueden mostrarse también en ese contexto.

Veamos ahora cómo podemos aplicar el resultado anterior en un ejemplo concreto.

Ejemplo. Queremos calcular el polinomio característico de la matriz

    \begin{align*}A= \begin{pmatrix} 0 & 0 &0\\ -4 & 9 & 0\\ -1 & -1 & 2.\end{pmatrix}\end{align*}

Para esto notamos que

    \begin{align*}^t A=\begin{pmatrix} 0 & -4 & -1\\ 0 & 9 & -1\\ 0 & 0 & 2\end{pmatrix}\end{align*}

que es triangular superior. Usando el primer problema

    \begin{align*}\chi_{^t A}(X)= X(X-9)(X-2).\end{align*}

Finalmente por el último problema

    \[\chi_{A}(X)=\chi_{^t A}(X)=X(X-9)(X-2).\]

\square

El término de la traza

Como vimos en la entrada anterior, en el polinomio \det(XA+B) aparecen los términos \det(A) y \det(B). El siguiente problema aplica esto al polinomio característico e incluso deducimos otro término: la traza.

Problema. Demuestra que el polinomio característico de A\in M_n(F) es de la forma

    \begin{align*}\chi_A(X)= X^n- \operatorname{Tr}(A)X^{n-1}+\dots+(-1)^n \det A.\end{align*}

Solución. Regresemos a la definición

    \begin{align*}\det (X I_n-A)=\sum_{\sigma\in S_n} \operatorname{sign}(\sigma)\left(X\delta_{1\sigma(1)}-a_{1\sigma(1)}\right)\cdots \left(X \delta_{n\sigma(n)}-a_{n\sigma(n)}\right).\end{align*}

Haciendo la expansión salvajemente podemos recuperar al menos los primeros términos:

    \begin{align*}(X\delta_{1\sigma(1)}-a_{1\sigma(1)})\cdots (X\delta_{n\sigma(n)}-a_{n\sigma(n)})&=X^{n}\prod_{i=1}^{n} \delta_{i\sigma(i)}\\&- X^{n-1}\sum_{j=1}^{n}\left(\prod_{k\neq j} \delta_{k\sigma(k)}\right)a_{j\sigma(j)}+\dots.\end{align*}

Más aún, nota cómo el producto \prod_{j=1}^{n}\delta_{j\sigma(j)} es distinto de cero si y sólo si j=\sigma(j) para todo j: es decir si \sigma es la identidad. Esto muestra que \chi_A(X) es mónico de grado n, como ya habíamos mencionado en la entrada anterior.

Además, el término constante está dado por

    \begin{align*}\chi_A(0)&=\det(0\cdot I_n-A)\\&=\det(-A)\\&=(-1)^{n}\det(A)\end{align*}

. Alternativamente pudimos haber usado la primera proposición de esta entrada para concluir estos hechos.

Nos falta estudiar el término de grado n-1. Si j\in \{1,2,\dots, n\}, entonces \prod_{k\neq j}\delta_{j\sigma(j)} es distinto de cero solo si \sigma(k)=k para todo k\neq j: pero \sigma es una permutación, en particular una biyección, lo que fuerza que \sigma(j)=j también y entonces \sigma sea la identidad. Entonces el término de X^{n-1} en

    \[(X\delta_{1\sigma(1)}-a_{1\sigma(1)})\cdots (X\delta_{n\sigma(n)}-a_{n\sigma(n)})\]

es distinto de cero sólo cuando \sigma es la identidad. En ese caso es precisamente

    \[-\sum_{j=1}^{n} a_{jj}=-\operatorname{Tr}(A).\]

\square

Ejemplo. Si A es la matriz del primer problema de esta entrada, tenemos que

    \begin{align*}\chi_A(X)&=(X-1)(X+2)(X-3)\\&= X^3-2 X^2+\dots +6.\end{align*}

Nota cómo el término de X^2 es en efecto -\text{Tr}(A)= -(1-2+3) y el último es -\det(A).

\square

Matrices nilpotentes

El caso de las matrices nilpotentes es todavía más sencillo.

Problema. Sea A\in M_n(F) una matriz nilpotente. Es decir, existe k\geq 1 tal que A^{k}=O_n.

  1. Demuestra que

        \begin{align*}\chi_A(X)=X^{n}.\end{align*}

  2. Demuestra que \operatorname{Tr}A^{m}=0 para todo m\geq 1.

Solución.

  1. Sea k\geq 1 tal que A^{k}=O_n (existe pues A es nilpotente). Entonces

        \begin{align*}X^{k}I_n&=X^{k}I_n-A^{k}\\&=(XI_n-A)(X^{k-1}I_n+X^{k-2}A+\dots +A^{k-1}).\end{align*}


    Tomando el determinante de ambos lados y recordando que abre productos llegamos a

        \begin{align*}X^{nk}&=\det(X^{k}I_n)\\&= \chi_{A}(X)\cdot \det(X^{k-1}I_n+\dots +A^{k-1}).\end{align*}


    De aquí, concluimos que \chi_{A}(X) tiene que dividir a X^{nk}, pero sabemos que \chi_A(X) es mónico y de grado n. Concluimos entonces que \chi_A(X)=X^{n}.
  2. Puesto que A^{m} también es una matriz nilpotente, el inciso anterior nos dice que

        \begin{align*}\chi_{A^{m}}(X)=X^{n}.\end{align*}


    Pero sabemos por la sección sobre la traza que el término de X^{n-1} es -\operatorname{Tr}(A^{m}). Como este término no aparece, concluimos que la traza es cero.

\square

Ejemplo. Para calcular el polinomio característico de la matriz

    \begin{align*}A=\begin{pmatrix}5 & -3 &2\\15 & -9 & 6\\10 & -6 &4\end{pmatrix}\end{align*}

podríamos notar (aunque no sea obvio a simple vista) que A^2=O_3. Luego, por el problema anterior, \chi_A(X)=X^3.

\square

Un último caso particular

Acabamos con una última familia de matrices con polinomio característico simple. Esta familia está descrita por su forma, y será de particular importancia para el teorema de Cayley-Hamilton.

Problema. Para escalares a_0,\dots, a_{n-1}\in F consideramos la matriz

    \begin{align*}A=\begin{pmatrix}0 & 0 & 0 & \dots & 0 & a_0\\1 & 0 & 0 & \dots & 0 & a_1\\0 & 1 & 0 & \dots & 0 & a_2\\\dots & \dots & \dots & \dots & \dots &\dots\\0 & 0 & 0 & \dots & 1 &a_{n-1}\end{pmatrix}.\end{align*}

en M_n(F).

Demuestra que

    \begin{align*}\chi_A(X)=X^{n}-a_{n-1}X^{n-1}-\dots -a_0.\end{align*}

Solución. Sea P(X)=X^{n}-a_{n-1}X^{n-1}-\dots-a_0. Considera la matriz

    \begin{align*}B=X I_n-A=\begin{pmatrix} X & 0 & 0 &\dots &0& -a_0\\ -1 & X & 0 &\dots & 0 &-a_1\\ 0 & -1 & X &\dots& 0&-a_2\\ \dots & \dots & \dots & \dots &\dots &\dots\\ 0 & 0 & 0 & \dots & -1 & X-a_{n-1}\end{pmatrix}.\end{align*}

Sumando el segundo renglón multiplicado por X al primer renglón, luego sumándole también al primer renglón el tercero multiplicado por X^2, el cuarto por X^3, y así sucesivamente hasta sumar el último renglón multiplicado por X^{n-1} llegamos a la matriz

    \begin{align*}C=\begin{pmatrix}0 & 0 & 0 & \dots &0& P(X)\\-1 & X & 0 & \dots &0 & -a_1\\0 & -1 & X & \dots & 0 & -a_2\\\dots & \dots & \dots & \dots & \dots &\dots\\0 & 0 & 0 & \dots & -1 & X-a_{n-1}\end{pmatrix}.\end{align*}

Recordamos que el determinante es invariante bajo sumas de renglones, por lo que

    \begin{align*}\chi_A=\det B=\det C.\end{align*}

Expandiendo el determinante de C en el primer renglón obtenemos sencillamente

    \begin{align*}\det C&=(-1)^{n+1}P(X) \cdot \begin{vmatrix} -1 & X & \dots & 0\\ 0 & -1 & \dots & 0\\ \dots &\dots & \dots & \dots \\ 0 & 0 & \dots & -1 \end{vmatrix}\\&= (-1)^{n+1} P(X)(-1)^{n-1}\\&=P(X).\end{align*}

Para la segundaigualdad usamos que el determinante es el de una matriz triangular superior con puros -1 como entradas. Para la última, usamos que n+1+n-1=2n siempre es un número par, así que queda -1 elevado a un número par. Esto concluye la prueba.

\square

Una de las consecuencias de la proposición anterior es que para cualquier polinomio mónico P de grado n en F[X], existe una matriz en M_n(F) tal que su polinomio característico es P.

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  1. Encuentra una matriz A tal que \chi_A(X)=X^5-5X^3+X^2-2X+2. Sugerencia: Usa el último problema.
  2. Demuestra que el polinomio característico de una matriz A=[a_{ij}] triangular inferior está dado por \prod_{i=1}^{n}(X-a_{ii}).
  3. Demuestra que 0 es eigenvalor de una matriz si y sólo si su determinante es cero.
  4. Calcula el polinomio característico de la siguiente matriz con entradas reales:

        \begin{align*}A= \begin{pmatrix} 5 & 5 & 5 \\ 6 & 6 & 6\\ -11 & -11 & -11\end{pmatrix}.\end{align*}

    Sugerencia: ¿Quién es A^2?
  5. ¿Es cierto que si F es cualquier campo y A es una matriz con entradas en F, entonces el hecho de que \operatorname{Tr}(A)=0 implica que A sea nilpotente? Sugerencia: Piensa en F_2.
  6. Da una demostración alternativa al último problema de esta entrada usando inducción matemática sobre el tamaño de la matriz.

Más adelante

En la próxima entrada veremos unos últimos aspectos teóricos del polinomio característico antes de lanzarnos de lleno al teorema de Cayley-Hamilton y su demostración.

Álgebra Lineal II: Polinomio característico

Deja un comentario

Introducción

En el transcurso de esta unidad hemos construido varios de los objetos algebraicos que nos interesan. En primer lugar, dejamos claro qué quería decir evaluar un polinomio en una matriz o transformación lineal. Esto nos llevó a preguntarnos por aquellos polinomios que anulan a una matriz o transformación lineal. De manera natural, descubrimos que aquellos polinomios que anulan son múltiplos de un polinomio especial asociado a la matriz o transformación lineal llamado polinomio mínimo.

De manera un poco separada, comenzamos a estudiar los eigenvalores, eigenvectores y eigenespacios de una transformación lineal y en la entrada anterior nos enfocamos en varias de sus propiedades principales. Uno de los resultados clave que encontramos es que los eigenvalores de una matriz o transformación lineal son las raíces del polinomio mínimo que estén en el campo en el que estemos trabajando.

Aunque este resultado sea interesante de manera teórica, en la práctica debemos hacer algo diferente pues no es tan sencillo encontrar el polinomio mínimo de una matriz o transformación lineal. Es por esto que ahora estudiaremos con profundidad otro objeto que resultará fundamental en nuestro estudio: el polinomio característico. Ya nos encontramos con él anteriormente. Si A es una matriz en M_n(F), dicho polinomio en la variable \lambda es el determinante \det(\lambda I_n-A).

Esta entrada es más bien una introducción, así que nos enfocaremos en probar las cosas más básicas de este objeto. Lo primero, y más importante, es verificar que en efecto es un polinomio (y con ciertas características específicas). También, aprovecharemos para calcularlo en varios contextos (y campos) diferentes.

Definición de polinomio característico

Comencemos con una matriz A\in M_n(F). Vimos que encontrar los eigenvalores de A se reduce a encontrar las soluciones de la ecuación

    \begin{align*}\det(\lambda I_n-A)=0\end{align*}

en F. Vamos a estudiar más a detalle la expresión de la izquierda.

El siguiente teorema va un poco más allá y de hecho estudia expresiones un poco más generales.

Teorema. Sean A,B\in M_n(F) dos matrices. Existe un polinomio P\in F[X] tal que para todo x\in F se cumple

    \begin{align*}P(x)=\det(xA+B).\end{align*}

Si denotamos a este polinomio por P(X)=\det(XA+B), entonces

    \begin{align*}\det(XA+B)=\det(A)X^{n}+\alpha_{n-1}X^{n-1}+\dots+\alpha_1 X+\det B\end{align*}

para algunas expresiones polinomiales \alpha_1,\dots, \alpha_{n-1} con coeficientes enteros en las entradas de A y B.

Demostración. Consideremos el siguiente polinomio en la variable X y coeficientes en F, es decir, el siguiente polinomio en F[X]:

    \begin{align*}P(X)=\sum_{\sigma\in S_n} \operatorname{sign}(\sigma)\left(a_{1\sigma(1)} X+b_{1\sigma(1)}\right)\cdots \left(a_{n\sigma(n)}X+b_{n\sigma(n)}\right).\end{align*}

Por construcción, P es un polinomio cuyos coeficientes son expresiones polinomiales enteras en las entradas de A y B. Más aún, se cumple que P(x)=\det(xA+B) para x\in F (podría ser útil revisar la entrada sobre determinantes para convencerte de ello). El término constante lo obtenemos al evaluar en X=0, pero eso no es más que P(0)=\det(0\cdot A+B)=\det(B). Finalmente para cada \sigma\in S_n tenemos que el primer término de cada sumando es

    \begin{align*}\operatorname{sign}(\sigma)(a_{1\sigma(1)}X+b_{1\sigma(1)})\cdots (a_{n\sigma(n)} X+b_{n\sigma(n)})= \operatorname{sign}(\sigma) a_{1\sigma(1)}\cdots a_{n\sigma(n)}X^{n}+\dots\end{align*}

En efecto, los términos «ocultos en los puntos suspensivos» todos tienen grado a lo más n-1. Agrupando todos los sumandos y comparando con la definición del determinante llegamos a que

    \[P(X)=\det(A)X^{n}+\ldots,\]

es decir el término de orden n es en efecto \det(A).

\square

Del teorema se sigue que si A y B tienen entradas enteras o racionales, \det(XA+B) tiene coeficientes enteros o racionales respectivamente.

Enseguida podemos definir (gracias al teorema) el siguiente objeto:

Definición. El polinomio característico de la matriz A\in M_n(F) es el polinomio \chi_A\in F[X] definido por

    \begin{align*}\chi_A(X)=\det(X\cdot I_n-A).\end{align*}

Una observación inmediata es que, de acuerdo al teorema, el coeficiente principal de \chi_A(X) tiene coeficiente \det(I_n)=1. En otras palabras, acabamos de demostrar la siguiente propiedad fundamental del polinomio característico.

Proposición. El polinomio característico de una matriz en M_n(F) siempre tiene grado exactamente n y además es un polinomio mónico, es decir, que el coeficiente que acompaña al término de grado n es iguala 1.

Veamos un ejemplo sencillo.

Ejemplo. Si queremos calcular el polinomio característico de

    \begin{align*}A=\begin{pmatrix} 1 & -1\\ 1 &0\end{pmatrix}\in M_2(\mathbb{R})\end{align*}

entonces usamos la definición

    \begin{align*}\chi_A(X)&=\det(X\cdot I_2-A)\\&=\begin{vmatrix} X-1 & 1\\ -1 & X\end{vmatrix}\\&= X(X-1)+1.\end{align*}

Y así los eigenvalores de A son las raíces reales de \chi_A(X). Es decir, tenemos que resolver

    \begin{align*} 0=x(x-1)+1=x^2-x+1.\end{align*}

Sin embargo, el discriminante de esta ecuación cuadrática es (-1)^2-4(1)(1)=-3, el cual es un real negativo, por lo que no tenemos eigenvalores reales. Si estuviéramos trabajando en \mathbb{C} tendríamos dos eigenvalores complejos:

    \begin{align*}x_{1,2}= \frac{1\pm i\sqrt{3}}{2}.\end{align*}

De aquí, ¿cómo encontramos los eigenvectores y eigenespacios? Basta con resolver los sistemas lineales homogéneos de ecuaciones (A-x_1I_2)X=0 para encontrar el x_1-eigenespacio y (A-x_2)X=0 para encontrar el x_2-eigenespacio.

\square

Algunos cálculos de polinomios característicos

Ya que calcular polinomios característicos se reduce a calcular determinantes, te recomendamos fuertemente que recuerdes las propiedades que tienen los determinantes. Sobre todo, aquellas que permiten calcularlos.

¡A calcular polinomios característicos!

Problema. Encuentra el polinomio característico y los eigenvalores de A dónde A es

    \begin{align*}A=\begin{pmatrix}0 & 1 & 0 & 0\\2 & 0 & -1 & 0\\0 & 7 & 0 &6\\0 & 0 & 3 & 0\end{pmatrix}\in M_4(\mathbb{R}).\end{align*}

Solución. Usamos la expansión de Laplace respecto al primer renglón:

    \begin{align*}\chi_A(X)&=\det(XI_4-A)\\&= \begin{vmatrix}X & -1 & 0 & 0\\-2 & X & 1 & 0\\0 & -7 & X & -6\\0 & 0 & -3 & X\end{vmatrix}\\&= X\begin{vmatrix} X & 1 & 0\\ -7 & X & -6\\ 0 & -3 & X\end{vmatrix}+ \begin{vmatrix}-2 & 1 & 0\\ 0 & X& -6\\ 0 &-3 & X\end{vmatrix}\\&= X(X^3-11X)-2(X^2-18)\\&= X^4-13X^2+36.\end{align*}

Después, para encontrar los eigenvalores de A tenemos que encontrar las raíces reales de la ecuación

    \begin{align*}x^4-13x^2+36=0.\end{align*}

Sin embargo, no hay que desalentarse por ver una ecuación de grado 4. Si hacemos el cambio y=x^2 podemos llevar nuestro problema a resolver

    \begin{align*}y^2-13y+36=0.\end{align*}

¡Es una ecuación de segundo orden! Esta la podemos resolver usando ‘la chicharronera’ y obtenemos como soluciones y_1=4 y y_2=9. Pero todavía tenemos que resolver x^2=y_1 y x^2=y_2. Al resolver estas últimas dos ecuaciones obtenemos que x=\pm 2,\pm 3 son los eigenvalores de A.

\square

Problema. Calcula el polinomio característico y los eigenvalores de la matriz

    \begin{align*}A=\begin{pmatrix} 1 & 0 & 1\\ 1 & 1 & 0\\ 1 & 0 &1 \end{pmatrix}\in M_3(F_2).\end{align*}

Solución. Nota que estamos trabajando en el campo de dos elementos F_2, por lo que -1=1. Usando la definición:

    \begin{align*}\chi_A(X)&=\det(XI_3-A)\\&= \begin{vmatrix} X-1 & 0 & -1\\ -1 & X-1 & 0\\ -1 & 0 &X-1\end{vmatrix}\\&= \begin{vmatrix} X+1 & 0 & 1\\ 1 & X+1& 0 \\ 1 & 0 &X+1\end{vmatrix}.\end{align*}

Aquí estamos usando repetidamente -1=1. Usamos otra vez la expansión de Laplace en el primer renglón para llegar a

    \begin{align*}\chi_A(X)&= (X+1)\begin{vmatrix} X+1 & 0 \\ 0 & X+1\end{vmatrix}+\begin{vmatrix} 1 & X+1\\ 1 & 0\end{vmatrix}\\&= (X+1)^3-(X+1).\end{align*}

Luego, si queremos encontrar los eigenvalores de A tenemos que resolver

    \begin{align*}(x+1)^3-(x+1)=0.\end{align*}

Si bien existen varias maneras de resolver la ecuación, podemos simplemente sustituir los únicos valores posibles de x : 0 o 1. Sustituyendo es fácil ver que ambos satisfacen la ecuación, por lo que los eigenvalores de A son 0 y 1.

\square

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Demuestra que 0 es un eigenvalor de una matriz A si y sólo si \det(A)=0.
  • ¿Una matriz compleja de tamaño n tiene necesariamente n eigenvalores distintos?
  • Calcular el polinomio característico y los eigenvalores de

        \begin{align*}A=\begin{pmatrix} 1 & 2 & 0\\ 0 & 1 &2\\ 2 & 0 & 1\end{pmatrix}\in M_3(F_3).\end{align*}

  • Usando la fórmula del determinante para matrices de tamaño 2, encuentra un criterio simple para saber si una matriz con entradas reales de tamaño 2 tiene dos, uno o ningún eigenvalor real.
  • Da un criterio simple para saber si una matriz de tamaño 2 con entradas complejas tiene eigenvalores puramente imaginarios.

Más adelante

En la próxima entrada calcularemos el polinomio característico de una variedad de matrices importantes: triangulares superiores, nilpotentes, etc. Esto nos permitirá entender mejor al polinomio característico y lidiar con muchos casos para facilitarnos los cálculos más adelante.

Álgebra Superior I: Propiedades de la negación, conjunción y disyunción

Deja un comentario

Introducción

En la entrada pasada vimos que con conectores podemos construir nuevas proposiciones a partir de otras. Y nombramos a tres de ellas: la negación, la conjunción y la disyunción.

Ahora, discutiremos sobre algunas consecuencias que tiene juntar unas con otras y diremos en términos formales qué significa que una proposición sea «igual» a otra.

Equivalencia de proposiciones

Volvamos a retomar un ejemplo que ya habíamos revisado anteriormente.

P\neg P\neg(\neg P)
01 0
101 

Habíamos dicho que al coincidir las columnas de \neg ( \neg P) con P entonces \neg(\neg P) = P, pues bien, en matemáticas esto se leerá como \neg(\neg P) es equivalente a P. Esto nos quiere decir que en cualquier caso en que \neg(\neg P) sea verdad, sucede que P es verdad. De igual forma, cada vez que suceda que \neg(\neg P) es falso, P también lo será.

Podemos pensar eso con el siguiente ejemplo. Pensemos en que nuestra proposición P es: «El 2 es un número impar». En este caso \neg(\neg P) corresponde a: «No es cierto que 2 no es un número impar». Si la proposición P es verdadera, entonces la equivalencia nos diría que \neg(\neg P) también lo es. Es decir, si es verdadero que 2 es un número impar, entonces también es verdadero que «No es cierto que 2 no es un número impar». Aunque nosotros sepamos que 2 es un número par (y por ende la proposición P es falsa), una persona que no tuviera el conocimiento de este hecho pero que sepa lógica, podría saber que si P es verdadero \neg(\neg P) también es verdadero. O si \neg(\neg P) es verdadero, P también es verdadero.

Ahora, nota que acabamos de hacer una definición, pues nombramos a dos proposiciones que tienen la misma tabla de verdad como equivalentes, así como lo mencionamos en la entrada de los tipos de enunciados, nombramos a un concepto matemático a algo que cumple ciertas propiedades.

Definición. Dos proposiciones P y Q son equivalentes si sus tablas de verdad coinciden y lo escribiremos como P=Q.

Esta «igualdad» en las proposiciones nos será muy útil, pues en la matemática nos ayudará a ver algunos resultados de otra manera, por ejemplo, como \neg(\neg P) = P Entonces como sabemos que es falso que 2 es impar, en consecuencia también sabemos que es falso que «No sea cierto que 2 no es impar» y esto lo sabemos sin tener que verificar algo más, pues el hecho de que sean equivalentes, basta saber que una sea verdad para que la otra sea verdad, o que una sea falsa para que la otra también lo sea. Y además, en matemáticas también esta definición nos ayudará a demostrar algunos resultados en el futuro.

Nota además que si P y Q son equivalentes, y Q y R son equivalentes (es decir P=Q, Q=R) entonces P y R también son equivalentes. Esto en símbolos es: si P=Q y Q=R entonces P=R. Esto es debido a que decir que P y Q son equivalentes significa que tienen la misma tabla de verdad, entonces si Q y R son equivalentes, entonces Q tiene la misma tabla de verdad que R, pero además Q tiene la misma tabla de verdad que P, entonces P tiene que tener la misma tabla de verdad que R. A esto se le conoce como la propiedad transitiva. No es importante que recuerdes este nombre, sin embargo después volveremos a estudiar esta propiedad con más calma. Y para recordar mejor esto, piensa en que funciona similar a la igualdad entre números, por ejemplo 2+2=4 y 4=2^2, entonces 2+2=2^2.

Algunas propiedades de la conjunción y la disyunción

Hemos hablado un poco sobre la negación, pero ahora cambiemos el foco a la disyunción y la conjunción. Para empezar, recordemos que la disyunción P\land Q solo es verdadera cuando tanto P como Q son verdaderas, y en la entrada anterior verificamos que Q \land P es equivalente a P \land Q. Sin embargo, también nos va a interesar el caso en donde tenemos más de dos proposiciones, pero para ello, recuerda que mencionamos a la disyunción como un conector entre dos proposiciones, así que para unir a más de dos proposiciones mediante las disyunción, tendremos que agruparlos.

Piensa el agrupamiento como piensas la suma: si quieres sumar 2+3+4, lo más habitual es sumar primero 2+3 que resulta en cinco, y después sumárselo a 4, de manera que podemos escribir la suma como 2+3+4=(2+3)+4. Algo similar va a pasar con las proposiciones, pues podemos pensar a P \land Q \land R como (P \land Q) \land R. Ahora piensa en la suma 2+3+4, el resultado de esta suma es 9 y nosotros decidimos agrupar 2+3 y después sumar el resultado con 4. Pero esto es lo mismo que haber agrupado primero 3+4 y después sumarlo a 2, esto no es coincidencia, pues la suma tiene una propiedad que se llama asociatividad que nos dice que (2+3)+4=2+(3+4). ¿Pasará lo mismo con la disyución? Veamos que sí.

Para esto, fíjate que queremos ver si P \land (Q \land R)=(P \land Q) \land R es decir, queremos ver si P \land (Q \land R) es equivalente a (P \land Q) \land R. Y recuerda que nuestra definición nos dice que dos proposiciones son equivalentes si tienen la misma tabla de verdad. Y ahora fíjate en la tabla:

PQRQ \land RP \land ( Q\land R)P \land Q(P \land Q) \land R
0000000
0010000
0100000
0111000
1000000
1010000
1100010
1111111

Como puedes notar, las columnas P \land (Q \land R) y (P \land Q) \land R coinciden, es decir, coinciden en sus tablas de verdad, por lo tanto son equivalentes.

Con este ejemplo, vimos cómo la disyunción tiene la propiedad asociativa, es decir, cuando combinamos tres o más proposiciones mediante la disyunción, no importa el orden en que apliquemos el conector (no importa dónde pongamos los paréntesis). Lo mismo pasará con la conjunción que de igual manera es asociativa.

También podemos juntar estos dos conectores, por ejemplo, piensa que tenemos tres proposiciones P, Q, R donde,

P = \text{Toda persona es mortal}

Q = \text{2 es un número impar}

R = \text{2 es un número par}

¿Qué significaría la proposición P \lor (Q \land R)? Si lo escribieramos en palabras, sería «Toda persona es mortal o 2 es un número par e impar a la vez». Sabemos que toda persona es mortal, y también sabemos que 2 no puede ser impar y par a la vez (por ahora parece que sabemos que 2 es un número par, en otros cursos profundizarás más en lo que significa ser par), entonces nuestra proposición está formada por dos componentes, la proposición P y la proposición Q \land R. Como un número no puede ser par e impar a la vez, entonces la segunda proposición es falsa. Pero la primera proposición P es verdadera, entonces la proposición P \lor (Q \land R) es verdadera, porque para la conjunción solo basta que alguna de las dos sea verdadera. Vamos a ir un poco más allá. ¿Será que esta es la única forma de escribir la proposición? Pues resulta que no, y que esta proposición tiene una propiedad que se llama la propiedad distributiva para los conectores, y esta nos dice que P \lor (Q \land R) = (P \lor Q) \land (P \lor R), si te resulta un poco confuso esto, puedes pensarlo por ahora como la distribución de una multiplicación con la suma, es decir la operación 2 \times (1+3) = (2 \times 1) + (2 \times 3), en donde nuestra conjunción \lor junta a P con Q y a P con R y la disyunción \land los distribuye.

Para convencerte de esto, veamos sus tablas de verdad.

PQRQ \land RP \lor ( Q\land R)P \lor QP \lor R(P \lor Q) \land (P \lor R)
00000000
00100010
01000100
01111111
10001111
10101111
11001111
11111111

Y nota que las columnas coloreadas corresponden a las proposiciones y son iguales, entonces P \lor (Q \land R) = (P \lor Q) \land (P \lor R). Lo mismo sucede si cambiamos el orden de los conectores, es decir P \land (Q \lor R) = (P \land Q) \lor (P \land R), así podemos distribuir los conectores disyuntivos y conjuntivos como más nos convenga.

Agregando la negación a la mezcla

Por último, vamos a incluir a la negación en nuestra mezcla de conjunciones y disyunciones. ¿Qué pasará cuando tenemos proposiciones del estilo \neg (P \land Q) y \neg (P \lor Q)? Sería lógico pensar en un inicio que igual la negación se va a distribuir, pero eso no es cierto. Para esto, piensa en el siguiente ejemplo:

    \[P = \text{32 es un número perfecto}\]

    \[Q = 2^7-1 \text{ es un número primo}\]

Aquí hablamos de dos cosas que quizá aún no sepas: números perfectos y números primos, no te preocupes por lo que signifiquen, en otros cursos los verás con más detalle, aunque te puedo decir que solo una de estas dos afirmaciones es correcta (¿Puedes adivinar cuál es?), entonces la disyunción es falsa, por lo que la negación de la disyunción es verdadera. Lo que acabamos de decir es que P \land Q es falsa y por consecuente \neg (P \land Q) es verdadera. Si sucediera que la negación fuera distributiva, entonces \neg (P \land Q) sería equivalente a \neg P \land \neg Q pero esto no es cierto, porque \neg P es falso, y \neg Q es verdadero, nota que entonces \neg P \land \neg Q es falso. Acabamos de llegar a una contradicción, es decir, primero dijimos que \neg (P \land Q) es verdadera y después observamos que si la negación se distribuyera, sería falso, pero recuerda que una proposición es verdadera o falsa, no puede ser verdadera y falsa al mismo tiempo, entonces alguna de las dos suposiciones que hicimos es incorrecta.

Nuestro error fue haber distribuido la negación sin cuidado. Resulta que la negación no cumple esa propiedad, pero «casi» es distibutiva, esas comillas en el casi, se deben a que al negar una conjunción o disyunción, estas se «invierten». Veamos sus reglas:

    \[\neg (P \land Q) = \neg P \lor \neg Q\]

    \[\neg (P \lor Q) = \neg P \land \neg Q\]

En nuestro ejemplo, esto quiere decir que es lo mismo decir «No es cierto que 32 sea un número perfecto y 2^7-1 sea un número primo» a decir «No es cierto que 32 es un número perfecto, o no es cierto que 2^7-1 es un número primo». Para que lo entiendas más claro, revisa la tabla de verdad:

PQP \land Q\neg (P \land Q)\neg P\neg Q\neg P \lor \neg Q
0001111
0101101
1001011
1110000

Observa que las tablas de verdad coinciden, lo que quiere decir que son equivalentes. Lo mismo puedes verificar para comprobar que \neg (P \lor Q) = \neg P \land \neg Q. A estas propiedades se les conoce como leyes de DeMorgan (más adelante volverás a oír ese nombre).

Ahora, para recapitular lo que vimos en esta entrada:

  • Hablamos de la equivalencia de proposiciones que ocurre cuando dos proposiciones coinciden en su tabla de verdad.
  • Observamos tres propiedades de los conectores: la asociatividad, la distributividad y las leyes de DeMorgan.

Todo esto nos da herramienta suficiente para ya empezar a hablar de lógica proposicional, pero esto apenas empieza…

Tarea Moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  1. Demuestra que \neg ( \neg (\neg P)) es equivalente a \neg P.
  2. Recuerda que dijimos que podemos asociar la disyunción como queramos, ahora verifica que lo mismo pasa con la conjunción, es decir P \lor (Q \lor R) = (P \lor Q) \lor R.
  3. Verifica con la tabla de verdad que P \land (Q \lor R) = (P \land Q) \lor (P \land R)
  4. Verifica con la tabla de verdad que \neg (P \lor Q) = \neg P \land \neg Q.

Más adelante…

En esta entrada hablamos sobre las propiedades que tienen tres conectores, pero recuerda que no son los únicos, aún nos faltan revisar dos conectores muy importantes: la implicación y la doble implicación. Estas dos las vamos a ver con más calma en la siguiente entrada.

Entradas relacionadas

Geometría Analítica I: Propiedades de suma y producto escalar

2 respuestas

Introducción

En la actual entrada se estudian propiedades de las dos operaciones (suma vectorial y producto escalar) que se definieron anteriormente. Utilizaremos los axiomas de \mathbb{R} para probar algunas de estas propiedades y las ejemplificaremos.

Propiedades de suma y producto escalar

Aunque nosotros nos enfocaremos por el momento en \mathbb{R}^2, el siguiente teorema se puede demostrar para \mathbb{R}^n, donde este último es el conjunto de todos los vectores

    \[x=(x_1,x_2,\ldots, x_n),\]

con x_i \in \mathbb{R}, i=1,2,\ldots,n. Conforme vayas desarrollando tu intuición matemática, te darás cuenta que realizar la generalización no es tan compleja. Recuerda que la idea es que podemos utilizar los axiomas de \mathbb{R} para demostrar propiedades de las operaciones en \mathbb{R}^2.

Teorema. Para todos los vectores x, y, z \in \mathbb{R}^2 y para todos los números s, t \in \mathbb{R} se cumple que:

  1. (x+y)+z=x+(y+z)
  2. x+y=y+x
  3. x+0=x
  4. x+(-x)=0
  5. s(tx)=(st)x
  6. 1x=x
  7. t(x+y)=tx+ty
  8. (s+t)x=sx+tx

Por contexto se entiende que el 0 de los puntos 3 y 4 corresponde al vector (0,0), aunque en notación no haya distinción. Además en 4, estamos usando la definición -x:=(-1)x. Aunque todo el teorema está enunciado en términos algebraicos, más adelante, en esta misma entrada, habrá algunos interactivos para que obtengas la intuición geométrica de estas propiedades.

Demostración. Para no caer en repetición del uso de ciertas herramientas, a continuación demostraremos sólo algunos de los ocho puntos. Puedes demostrar los restantes como tarea moral y pensar también en la generalización para \mathbb{R}^n. Comencemos.

Sean x=(x_1,x_2), y=(y_1,y_2), z=(z_1,z_2) vectores arbitrarios en \mathbb{R}^2.

1. Debemos demostrar la igualdad (x+y)+z=x+(y+z) en vectores.

    \begin{align*}(x+y)+z&=((x_1,x_2)+(y_1,y_2))+(z_1,z_2)\\&=(x_1+y_1,x_2+y_2)+(z_1,z_2)\\&=((x_1+y_1)+z_1, (x_2+y_2)+z_2)\\&=(x_1+(y_1+z_1),x_2+(y_2+z_2))\\&=(x_1,x_2)+((y_1,y_2)+(z_1,z_2)\\&=(x+y)+z=x+(y+z).\end{align*}

Para cada una de las igualdades anteriores existe una justificación. El primer renglón se da meramente por la definición de cada vector. La siguientes dos igualdades resultan de la definición de suma de vectores que, como la definimos, debe ser realizada coordenada a coordenada. Ahora, por asociatividad de la suma de los números reales, el renglón 4 es válido. El penúltimo parece un as sacado de la manga pero en realidad es de nuevo pensar en la definición de suma de vectores: tenemos una igualdad entre la suma de dos vectores y la suma de sus entradas formando el vector suma. Por último sólo sustituimos las entradas por el vector que representan.

5. Debemos demostrar la igualdad s(tx)=(st)x con s,t números reales y x vector.

Por definición del vector x tenemos:

s(tx)=s(t(x_1,x_2))

Por definición del producto escalar se cumplen los siguientes dos pasos:

=s(tx_1,tx_2)
=(s(tx_1),s(tx_2))

Por la asociatividad del producto en \mathbb{R} pasa que:

=((st)x_1,(st)x_2)

De nuevo parece que el siguiente paso es otro as, pero piensa en la definición del producto escalar leyéndolo de derecha a izquierda:

=(st)(x_1,x_2)
s(tx)=(st)x.

7. Debemos demostrar la igualdad t(x+y)=tx+ty con t número real y x,y vectores.

(1)   \begin{align*}t(x+y)&=t((x_1,x_2)+(y_1,y_2))\\&=t(x_1+y_1,x_2+y_2)\\&=(t(x_1+y_1),t(x_2+y_2))\\&=(tx_1+ty_1,tx_2+ty_2)\\&=(tx_1,tx_2)+(ty_1,ty_2)\\&=t(x_1,x_2)+t(y_1,y_2)\\&=tx+ty.\end{align**}

Resumamos los pasos. El primer paso es por definición de ambos vectores, el siguiente por definición de suma vectorial y el tercero por definición de multiplicación escalar. En este punto, en cada entrada del vector tenemos únicamente números reales por lo que podemos usar distributividad en \mathbb{R}. Para finalizar recordemos la definición de la suma vectorial y la multiplicación escalar leyendo ambas de derecha a izquierda.

8. Debemos demostrar la igualdad (s+t)x=sx+tx con s y t reales y x vector.

Por definición de x tenemos:

(s+t)x=(s+t)(x_1,x_2)

Por definición del produco escalar:

=((s+t)x_1,(s+t)x_2)

Por distributividad de los números reales:

=(sx_1+tx_1,sx_2+tx_2)

Por definición de la suma vectorial:

=(sx_1,sx_2)+(tx_1,tx_2)

Por definición del producto escalar:

(s+t)x=s(x_1,x_2)+t(x_1,x_2)

\square

Demostramos algunas de las propiedades. Para el resto de ellas hay que seguir las mismas ideas. Si te das cuenta, lo único que utilizamos en esta demostración fueron los axiomas de los números reales, la definición de las operaciones usadas y algo de intuición para saber qué paso sigue.

Intuición geométrica de las propiedades

Si recuerdas, Descartes asoció el álgebra a la geometría y al menos en este curso, el álgebra que desarrollemos tiene un significado geométrico. A continuación describiremos algunos de los puntos que demostramos e ilustraremos otros con ayuda de GeoGebra.

1. (x+y)+z=x+(y+z). En el siguiente interactivo están representados tres vectores X, Y, Z. En negro se encuentra el vector X+Y+Z. Se utiliza el método del paralelogramo de dos formas distintas: Primero, sumando X+Y y al resultado sumandole Z. La segunda suma primero a Y+Z y al resultado se suma X. Es notorio que por ambos caminos se llega al mismo punto correspondiente a X+Y+Z.

5. s(tx)=(st)x. En el siguiente interactivo puedes utilizar los deslizadores para cambiar los valores de s,t \in \mathbb{R}. Parece que sólo un vector con dos etiquetas de distinto color se mueve, pero son dos vectores (uno por cada etiqueta) ambos dependientes de s y t como lo indica cada lado de la igualdad. Que sólo puedas ver claramente uno, indica que hicimos lo correcto pues son dos vectores iguales.

Para los siguientes dos casos sólo describiremos lo que pasa y lo óptimo sería que lograras usar GeoGebra para hacer la representación gráfica de ellos.

7. t(x+y)=tx+ty. Nos indica que el resultado de sumar dos vectores primero y después multiplicarlos por un escalar es el mismo que primero multiplicar cada vector por él y luego sumar los resultados.

8. (s+t)x=sx+tx. Nos indica que el resultado de sumar los dos escalares primero y después multiplicar el resultado por el vector, es lo mismo que multiplicar el vector por cada escalar y sumar los resultados.

Existe un término para denotar a un conjunto con dos operaciones (suma vectorial y producto escalar), que cumple con las ocho propiedades del teorema que acabamos de demostrar: Espacio vectorial. Así, este teorema se resume al decir que \mathbb{R}^2 es un espacio vectorial.

Ecuaciones con vectores

Ahora veamos cómo podemos usar estas propiedades en la resolución de problemas. Nos serán de mucha ayuda cuando tengamos ecuaciones constituidas por vectores, ¿es posible resolverlas igual que cuando se tienen variables numéricas? Resulta que hay cosas que sí podemos realizar de la misma manera, como «pasar del otro lado» un vector sumando o restando y dividir por escalares, veámoslo en el siguiente ejemplo.

Ejemplo. Sean x, u, v \in \mathbb{R}^2, donde u=(5,3) y v=(-3,1). ¿Es posible encontrar al vector x que cumpla con

-3u+2x=v-x?

Nuestra variable es el vector x, el paso más lógico es despejarlo. Sumando 3u+x de ambos lados tenemos

3x=v+3u.

Podemos ahora dividir ambos lados por el escalar 3 y obtener

x=\frac{v+3u}{3}

Esto tiene sentido pues si bien tenemos un vector entre un escalar, podemos re-pensar esto como el vector multiplicado por 1/3. En este punto podemos sustituir los valores correspondientes para v y u para así obtener al x que buscamos

x=\frac{(-3,1)+3(5,3)}{3}
=\frac{(12,10)}{3}
x=(4,10/3)

\square

Aunque haya cosas que podemos hacer de manera equivalente a los reales en casos como el mostrado en el ejemplo, hay otras que no son viables como dividir entre un vector. Aún así, podemos obtener herramientas que nos auxilien. Para cerrar esta entrada enunciaremos y demostraremos dos lemas que servirán para trabajar con operaciones vectoriales.

Lema 1. Si x \in \mathbb{R}^2 y t \in \mathbb{R} son tales que tx=0 (por contexto 0=(0.0)), entonces t=0 o x=0.

Demostración.

  • Supongamos que t\neq 0. P. D. x=(0,0).

Como t \neq 0, entonces existe su inverso multiplicativo t^{-1} tal que t^{-1}t=1. Multiplicando t^{-1} en ambos lados de la ecuación tx=0 tenemos:

t^{-1}(tx)=t^{-1}0
(t^{-1}t)x=t^{-1}0=0
x=0

En el primer renglón sólo multiplicamos por t^{-1}; el segundo es válido por el punto 5 del teorema anterior, y lo último se da por lo enunciado arriba: t^{-1}t=1.

Esto ya prueba lo que queremos, pero también podríamos hacer la prueba «al revés», pensando en qué sucede cuando x\neq 0.

  • Supongamos ahora que x \neq 0 P.D. t=0.

Sea x=(x_1,x_2), entonces

tx=t(x_1,x_2)
=(tx_1,tx_2)=0=(0,0)

Esto se encuentra igualado al vector 0 por lo cual tienen que ser iguales entrada a entrada

tx_1=0 y tx_2=0

ahora, existen 3 casos que cumplen x \neq 0. Uno, que x_1 \neq 0 pero x_2=0. De manera análoga, el segundo es que x_1=0 pero x_2 \neq 0. Por último que tanto x_1 como x_2 sean ambos distintos de cero.

Sin perdida de generalidad, supongamos el caso 1. Como x_1 \neq 0, entonces

tx_1=0 \rightarrow t=0,

pues esto se satisface para los números reales. La demostración del segundo caso es análoga, sólo se debe tomar x_2. La demostración del tercer caso se puede hacer igual que el primero, o el segundo.

\square

Lema 2. Si x \in \mathbb{R}^2 es distinto de cero y t, s \in \mathbb{R} son tales que tx=sx, entonces t=s.

Demostración.

Sea x=(x_1,x_2) un vector arbitrario, podemos escribir a tx=sx como

t(x_1,x_2)=s(x_1,x_2)
\Rightarrow (tx_1,tx_2)=(sx_1,sx_2)

Para que se cumpla la igualdad tienen que ser iguales entrada a entrada

\Rightarrow tx_1=sx_1 y tx_2=sx_2.

Como x no es el vector cero, alguno de x_1 ó x_2 es distinto de cero. En este punto ya estamos operando únicamente con números reales, por lo que podemos «cancelar » x_1 ó x_2 (el que no sea cero). De aquí, concluimos que s=t, como queremos.

\square

Tarea moral

  • Realiza la demostración de los puntos faltantes en el teorema enunciado en esta entrada.
  • Realiza la representación gráfica de estos y también de los puntos que sólo fueron explicados. Puedes usar GeoGebra si así lo deseas.
  • Extiende la demostración del Lema 3 para cuando x \in \mathbb{R}^3. ¿Qué sucede en \mathbb{R}^n.
  • Considera los vectores u=(-9,17) y v=(51,-3) en \mathbb{R}^2. Encuentra el vector x \in \mathbb{R}^2 tal que 3x-5u=7v-x.
  • Si es posible, encuentra a,b \in \mathbb{R} tales que au+bv=w, con u y v los vectores del ejemplo visto en esta entrada y w=(37,-5). Si no es posible, argumenta porqué.

Más adelante…

Las propiedades aquí vistas nos servirán como herramienta a lo largo del curso. Como ya las demostramos, tendremos la libertas de usarlas más adelante. Esto será de suma utilidad para cuando definamos objetos geométricos como rectas, planos, circunferencias, y queramos hablar de sus propiedades.

Álgebra Superior II: Principio de inducción y teoremas de recursión

Deja un comentario

Introducción

Inducción y recursión son dos conceptos similares con los que seguramente te has topado en tu formación matemática, e incluso tal vez antes. Muchas veces se llegan a confundir ambos conceptos, ya que ambos tienen una fuerte relación con el 5° axioma de Peano.

Aunque lo detallaremos a lo largo de la entrada, el principio de Inducción es una propiedad de los números naturales, que nos sirve para demostrar que todos los naturales satisfacen una propiedad. Es decir, es una estrategia de demostración. En contraste, la recursión es un resultado que justifica el hecho de poder dar una definición para todos los naturales, basándonos en la definición de su antecesor. En otras palabras, es una estrategia de definición.

Al final de la entrada demostraremos el teorema de recursión débil, en cuya prueba, podremos apreciar cómo es que depende directamente del Principio de inducción.

Pruebas por inducción

Recordemos el 5° axioma de Peano, el cual probamos en la entrada pasada que se satisface en nuestro modelo:

Si S\subset \mathbb{N} satisface que

  • 0\in S y
  • si n\in S, implica que \sigma(s)\in S,

entonces S=\mathbb{N}.

Como hemos mencionado en entradas anteriores, esta proposición es muy similar al principio de Inducción que probablemente hayas ocupado desde el curso de Álgebra Superior I. Más aún, en la entrada pasada, seguimos la misma estrategia que en otros cursos, a la hora de ocupar el 5° axioma. Efectivamente, la equivalencia entre ambos resultados es casi inmediata, y como ejemplo ilustrativo, probaremos el Principio de Inducción a partir del 5° axioma de Peano.

Proposición (Principio de Inducción): Sea P(n) una propiedad, es decir, una proposición matemática que depende de un entero n. Si se tiene que:

  1. P(0) es verdadera y
  2. cada vez que P(n) es cierto, también lo es P(n+1),

entonces P(n) es cierta para todos los números naturales.

Demostración. Sea P(n) una propiedad que satisface 1. y 2. y consideremos el conjunto S:=\{n\in\mathbb{N}: P(n)\text{es verdadera}\}.

Como P(0) es verdadera, entonces 0\in S.

Tomemos n\in S, entonces P(n) es verdadera, y por 2., tenemos que P(n+1) es verdadera; es decir, n+1\in S. Por el 5° Axioma de Peano, se tiene que S=\mathbb{N}, por lo que por la definición de S, se tiene que P(n) es cierta para cada n\in \mathbb{N}

\square

Definiciones por recursión

Una de nuestras primeras ideas para poder construir a \mathbb{N}, fue intentar construir a mano cada elemento. Para esto, dimos una definición de lo que significaba el 0 y el sucesor de un número. Después empezamos a iterar una y otra vez la función sucesor para obtener el sucesor del último número encontrado. Discutimos por qué es que esta idea no sería el mejor camino (sólo nos permite llegar hasta una cantidad finita de naturales), por lo tuvimos que introducir el Axioma del Infinito para resolver el problema. Veamos la analogía entre esta idea y el siguiente ejemplo intuitivo.

Ejemplo: Definamos la función factorial de un número natural, como:

  • 0!=1
  • (n+1)!=(n!)(n+1)

Entonces, 3!:=(2!)(3)=(1!)(2)(3)=(0!)(1)(2)(3)=(1)(1)(2)(3)=6.

Recordemos que al definir a los naturales, necesitábamos conocer un número para poder definir su sucesor. Aquí sucede lo mismo: en la definición de factorial necesitamos conocer quién es el factorial de un número para poder definir el factorial de su sucesor. A este tipo de definiciones se les conoce como definiciones recursivas, ya que para definir algo para un número, necesitamos tener conocimiento del valor de la función en los números anteriores.

Queda una pregunta muy importante. Si a los naturales no los pudimos definir de manera recursiva, ¿por qué podemos afirmar que la función factorial sí existe? A continuación enunciaremos algunos teoremas que nos garantizarán que sí podemos hacer este tipo de definiciones recursivas en nuestro modelo. Daremos una versión fuerte y una versión débil. Demostraremos la versión débil, pues basta para mucho de lo que queremos definir en los naturales (sumas, productos, potencias).

Las siguientes secciones son un poquito técnicas. Si las puedes seguir por completo, es fantástico. Pero incluso si no es así, basta con que en el fondo te quedes con la idea importante detrás: sí se vale definir de manera recursiva. Más adelante podrás regresar a este tema y entenderlo por completo.

Los teoremas de la recursión

Antes de la demostración principal de esta entrada, enunciaremos los teoremas que nos importan y hablaremos de manera intuitiva de lo que dicen. Hay dos versiones que veremos: una fuerte y una débil. Aunque parece que dicen cosas diferentes, en realidad son equivalentes. Será muy claro que la versión fuerte «implica» a la débil. Pero luego, en los problemas de tarea moral, se esbozará cómo ver que la versión débil se puede utilizar para demostrar la fuerte.

Teorema (Recursión Fuerte): Sea X un conjunto y x_{0}\in X. Supongamos que tenemos varias funciones (una por cada natural i)

    \[\{f_{i}:X\to X\}_{i\in\mathbb{N}\setminus \{0\}.\]

Entonces existe una única función g:\mathbb{N}\to X tal que:

  • g(0)=x_{0}
  • g(\sigma(n))=f_{\sigma(n)}(g(n)).

¿Qué es lo que quiere decir este teorema? Para responder esta pregunta veamos el siguiente diagrama:

Nuestro diagrama empieza en 0, el cual queremos que sea mandado a algún x_{0}\in X, para la definición de los demás números, ocupamos la segunda característica que esperamos que g satisfaga. Por ejemplo g(1)=g(\sigma(0))=f_{1}(g(0))=f_{1}(x_{0}). Este análisis coincide con lo que nos presenta el primer cuadro de flechas del diagrama anterior, que nos presenta los dos caminos que debe satisfacer g, para que sea la función que queremos. Como da lo mismo si «primero aplicamos \sigma y luego g«, a que si «primero aplicamos g y luego f_1«, decimos que el primer cuadrado del diagrama conmuta.

Análogamente, ya que conocemos la definición de g(1) podemos fijarnos en el segundo cuadro, para poder definir g(2) (de nuevo, conmuta) y seguir «recursivamente» para cualquier número natural.

Ejemplo: ¿Qué conjunto, y qué funciones necesitamos para definir el factorial?

Consideremos X=\mathbb{N}, definiremos intuitivamente (ya que aún no lo hemos definido formalmente), f_{i}:\mathbb{N}\longrightarrow \mathbb{N}, como f_{i}(n)=i\cdot n, es decir, el producto por i.

El teorema de Recursión Fuerte, nos dice que existe una única función g tal que

  • g(0)=1
  • g(\sigma(n))=f_{\sigma(n)}(g(n))=\sigma(n)\cdot g(n)

Denotemos n!:=g(n). Entonces tenemos que \sigma(n)!=n!\cdot \sigma(n), justo como queremos.

\square

El teorema de Recursión Débil y su demostración

El teorema de Recursión Débil tiene un enunciado parecido al teorema de recursión fuerte y puede ser visto como una consecuencia directa del teorema anterior pues se obtiene de la versión fuerte tomando f_{1}=f_{2}=\ldots=f_{n}=\ldots

Teorema (Recursión Débil): Sea X un conjunto y x_{0}\in X. Supongamos que tenemos una función f:X\to X. Entonces existe una única función g:\mathbb{N}\to X tal que:

  • g(0)=x_{0}
  • g(\sigma(n))=f(g(n)).

Para concluir con esta entrada, probaremos el teorema de Recursión Débil. Antes de hacer esto introducimos un concepto auxiliar y una propiedad de los naturales.

Recordemos que como conjunto, m=\{0,1,...,m-1\}, lo que sugiere la siguiente definición.

Definición: Si n,m\in \mathbb{N}, decimos que n<m si n\in m.

Puede probarse que esta relación en \mathbb{N} es un orden total, y que sastisface la siguiente propiedad.

Teorema (Principio el Buen Orden): Sea S\subset\mathbb{N} un conjunto no vacío, es decir S\neq \emptyset. Entonces S tiene un elemento mínimo. Es decir, existe n\in S tal que n<m para todo m\in S\setminus\{n\}.

La prueba del Principio del Buen Orden y más propiedades de < serán estudiadas con mayor detalle en entradas posteriores. Con esto en mente demostramos el teorema de Recursión Débil.

Demostración. Recordemos que por definición, toda función con dominio A y codominio B, es un subconjunto de A\times B, por lo que una buena idea es analizar el conjunto \wp(\mathbb{N}\times X), definamos

    \[\Re:=\{R\in\wp(\mathbb{N}\times X)\mid (0,x_{0})\in R \text{ y si }(n,x)\in R\text{, entonces }(\sigma(n),f(x))\in R\}\]

Esta definición se ve terriblemente complicada. Pero la intuición es clara: \Re tiene a todas las posibles colecciones de parejas de \mathbb{N}\times X que cumplen lo que queremos. El problema es que muchas de ellas no son funciones y tenemos que «arreglar esto».

Probablemente, notarás alguna similitud entre el conjunto \Re y el conjunto de los subconjuntos inductivos (que se menciona en La construcción de los naturales). Siguiendo esta analogía, definiremos g:=\bigcap \Re (podemos hacer esta intersección ya que \Re no es vacío pues \mathbb{N}\times X está en \Re).

  • Demostremos que g\in \Re:

Por las propiedades de la intersección, tenemos que g\subset\mathbb{N}\times X, por lo que g\in \wp(\mathbb{N}\times X). Veamos que (0,x_{0})\in g. Sea R\in\Re arbitrario, entonces (0,x_{0})\in R, por lo que (0,x_{0})\in\bigcap \Re=g. Por último, si (n,x)\in g, demostremos que (\sigma(n),f(x))\in g, para esto, sea R\in \Re arbitrario, como (n,x)\in g, entonces (n,x)\in R, por lo que (\sigma(n),f(x))\in R. Es decir, (\sigma(n), f(x))\in\bigcap \Re=g. Por todo lo anterior, g\in\Re.

  • Veamos ahora que Dom(g)=\mathbb{N}:

Usemos el quinto axioma de Peano, como (0,x_{0})\in g, entonces 0\in Dom(g). Supongamos ahora que n\in Dom(g) y demostremos que \sigma(n)\in Dom(g), por la hipótesis de inducción, existe x\in X tal que (n,x)\in g, y como g\in\Re, tenemos que (\sigma(n),f(x))\in g, pero esto quiere decir que \sigma(n)\in Dom(g). Entonces Dom(g) es inductivo, entonces Dom(g)=\mathbb{N}.

  • Demostremos ahora que g sí es función. Para esto, tenemos ver que «cada natural se va a un sólo elemento», en símbolos, si (n,x),(n,y)\in g entonces n=m

Aquí es donde ocuparemos el Principio del Buen Orden. Consideremos S:=\{n\in\mathbb{N}\mid (n,x),(n,y)\in g \text{ y } x\neq y \}. Procedamos por contradicción, supongamos que S\neq\emptyset, entonces, S tiene un elemento mínimo, denotémoslo por n.

Si n=0, entonces existe x\in X tal que (0,x)\in X y x\neq x_{0}. Entonces consideremos g'=g\setminus\{(0,x)\}. Notemos que g'\in\Re, ya que (0,x_{0})\in g', ya que (0,x_{0})\neq (0,x). Además si (k,a)\in g', entonces (k,a)\in g, por lo que (\sigma(k),f(a))\in g, y como 0 nunca es el sucesor de otro número, tenemos que (\sigma(k),f(a))\neq(0,x), por lo tanto (\sigma(k),f(a))\in g', es decir, g'\in \Re, lo que implica que g=\bigcap \Re\subset g'=g\setminus\{(0,x)\} lo cual es absurdo, por lo que n\neq 0.

Como n\neq 0, debemos tener que existe m tal que \sigma(m)=n ¿Por qué?. Y como n es el mínimo en S, tenemos que m\not\in S, es decir, existe un único x\in X tal que (m,x)\in g, esto implica que (\sigma(m),f(x))=(n,f(x))\in g, y como n\in S, debe existir y\in X, y\neq f(x) tal que (n,y)\in g. Análogamente a como lo hicimos antes, consideremos g'=g\setminus (n,y) y veamos que g'\in \Re. Como (n,y)\neq(0,x_{0}), tenemos que (0,x_{0})\in g'. Más aún, si (k,a)\in g', demostremos que (\sigma(k),f(a))\in g', para esto supongamos que no.

Como (k,a)\in g', tenemos que (k,a)\in g, por lo que (\sigma(k),f(a))\in g, esto implica que (\sigma(k),f(a))=(n,y) ya que este es el único elemento de g que no está en g'. Como \sigma(k)=n=\sigma(m), concluimos, por la inyectividad de \sigma, que k=m. Esto quiere decir que (k,a)=(m,a)\in g, pero recordando que x es el único elemento relacionado con m, concluimos que x=a, en síntesis, (k,a)=(m,x), por lo que (\sigma(k),f(a))=(\sigma(m),f(x))=(n,f(x))\neq(n,y). Esto implica que (\sigma(k), f(a))\in g', contradiciendo nuestra suposición de que no lo estaba.

Entonces hemos probado que (0,x_{0})\in g' y que cada vez que (k,a)\in g', también lo está (\sigma(k), f(a)). Esto quiere decir que g'\in\Re, y como lo hicimos anteriormente, tendremos que g=\bigcap \Re\subset g'=g\setminus\{(n,y)\}, lo cual es una contradicción. Esto quiere decir, que suponer que S tiene un elemento mínimo, es absurdo, por lo que S=\emptyset. Lo que traducido quiere decir que para todo n\in\mathbb{N}, existe un único x\in X tal que (n,x)\in g. Es decir, que g sí es una función.

  • Demostremos que g satisface las dos propiedades del Teorema.

Ya vimos que g\in \Re, por lo que g(0)=x_{0}. Sea ahora n\in \mathbb{N} y x=g(n), de nuevo, como g\in\Re, tenemos que g(\sigma(n))=f(x)=f(g(n)).

  • Por último, demostremos la unicidad de g

Si h:\mathbb{N}\longrightarrow X es otra función que satisface las características del Teorema, consideremos A=\{n\in\mathbb{N}\mid h(n)=g(n)\}, como h(0)=x_{0}=g(0). Tenemos que 0\in A. Supongamos que n\in A. Tendríamos entonces que h(\sigma(n))=f(h(n))=f(g(n))=g(\sigma(n)), es decir que \sigma(n)\in\A, por lo que A es inductivo, y por consiguiente, A=\mathbb{N}. En resumen, h y g, coinciden en dominio, codominio y regla de correspondencia, entonces h=g, como debíamos probar.

\square

La demostración del teorema de Recursión Fuerte requiere de algunos detalles adicionales, pero puede deducirse del teorema de Recursión Débil. Dejamos esto como uno de los problemas de la tarea moral.

Tarea Moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  1. Demuestra el 5° Axioma de Peano a partir del Principio de Inducción
  2. Demuestra que si n\neq 0 entonces existe m tal que \sigma(m)=n.
  3. ¿Qué función g, satisface que g(0)=1 y g(\sigma(n))=2\cdot g(n)? ¿Qué función f estamos ocupando?
  4. ¿Qué conjunto y que función nos permitiría definir la sucesión de Fibonacci a_{n+2}=a_{n+1}+a_{n} usando el Teorema de Recursión?
  5. Demuestra el Teorema de Recursión Fuerte, usando el Débil. Sugerencia: Considera, F(n,x):\mathbb{N}\times X\longrightarrow \mathbb{N}\times X, como F(n,x)=(\sigma(n),f_{\sigma(n)}(x))

Más adelante…

El teorema de Recursión será la mayor herramienta que tendremos para poder darle una forma más familiar a los números naturales, ya que las operaciones de suma y multiplicación, que veremos en la siguiente entrada, tendrán una definición recursiva.

Y así como el teorema de la Recursión nos permitirá definir, usaremos continuamente el principio de Inducción para poder demostrar las numerosas propiedades que estas operaciones tienen.

Entradas Relacionadas