Vamos a explorar un teorema que es una consecuencia directa de las Conjeturas de Weil demostradas por Pierre Deligne, si nos da tiempo veremos un sketch de como demostrar las conjeturas de André Weil en general.
El teorema de Hasse es muy importante en criptografía con curvas elípticas, ya que nos permite aproximar o incluso saber el número de elementos que tiene el grupo que forma una curva elíptica, este número de elementos en función del tamaño del campo finito, esto tiene aplicaciones a la ingeniería en la implementación, y también nos puede decir, si la curva es segura o no , es decir que su grupo no sea isomorfo a algo trivial.
El problema de la demostración de Helmut Hasse en 1936 es que es muy larga y complicada, aquí trataremos de dar los elementos necesarios, pero también extenderemos el teorema a otro espacio el cual nos permitirá analizar la estructura desde los endomorfismos de la curva.
Primero, trabajemos en un campos $latex \mathbb{F}_q$ con $latex q$ impar y con la forma de una curva elíptica $latex E$ en su forma reducida de Weierstrass, es decir $latex y^2 = x^3 + Ax + B$ , pero esta forma reducida de Weierstrass tiene el problema de que $latex j(E)=1728\equiv 0$ mod $latex 3$ lo que nos limita a trabajar con cierta familia (0) de curvas en característica 3, necesitamos que el $latex j$ invariante tome todos los valores de $latex \mathbb{F}_q$ entonces consideraremos las curvas $latex y^2 = x^3 + a_{2}x^2 + a_{4}x + a_6$ , pueden demostrar que el $latex j$ invariante de esta curva ya cubre todas las curvas elípticas de característica impar.
El teorema de Hasse dice.
Teorema (Helmut-Hasse, 1936): Sea $latex E$ una curva elíptica sobre un campo
$latex \mathbb{F}_q$, si $latex N_q$ representan el número de puntos de $latex E$ sobre $latex \mathbb{F}_q$ entonces:
$latex \mid N_q-(q+1)\mid \leq 2\sqrt{q}$
Este teorema se ve muy infensivo, pero no lo es... de hecho de manera preliminar podríamos comenzar a atacarlo
Si la ecuación de $latex E$ es $latex y^2 = x^3 + Ax +B =f(x)$ y $latex q$ es impar, entonces vamos a
suponer que el número de puntos que cumplen $latex f(x)$ están distribuidos uniformemente al ser evaluado $latex f$ $latex \forall x\in \mathbb{F}_q$ , por lo que tenemos que hay una raíz que es un punto de $latex E$ y como $latex q$ es impar, existen $latex \frac{q-1}{2}$ elementos que no son cuadrados en $latex \mathbb{F}^{*}_q$ lo que nos deja con los otros $latex \frac{q-1}{2}$ puntos que sí son cuadrados, pero hay 2 por cada uno ya que en $latex E$ tenemos $latex (\pm y)^2$ por lo que el valor esperado de $latex N_q$ es $latex 1+2\frac{q-1}{2}=q$
Esto nos da la desviación de $latex N_q$ y nos muestra la parte izquierda de la desigualdad de hasse que es $latex \mid N_q-(q+1)\mid$ donde el $latex +1$ es porque se consideran los puntos de $latex \mathbb{F}_q$ sobre la linea proyectiva la cual tiene otro punto adicional en el infinito.
Teoría necesaria.
En el post anterior hablamos del anillo de endomorfismos de una curva, el j-invariante e isogenias.
Te recomiendo lo leas antes, aquí recordaremos algunas cosas pero si crees que falta algo, el artículo anterior tiene más detalles.
Sean $latex E_1, E_2$ dos curvas elípticas definidas sobre $latex \mathbb{K}$ y $latex \psi:E_1\rightarrow E_2$ un homomorfismo separable de curvas elípticas, es decir... que si consideramos el functor contravariante $latex \psi^{*}:\mathbb{K}(E_2)\rightarrow \mathbb{K}(E_1)$ que manda $latex f\mapsto f\circ \psi$ entonces $latex \mathbb{K}(E_1)/\psi^{*}\mathbb{K}(E_2)$ es una extensión de campos separable (i.e. los polinomios minimos de elementos de el campo grande con coeficientes en el campo chico no tienes raíces repetidas) , y definimos el grado del mapeo $latex \psi$ como: $latex \partial\psi=[\mathbb{K}(E_1):\psi^{*}\mathbb{K}(E_2)]$
Motivación de la demostración de Hasse
Sea $latex \psi:E_1 \rightarrow E_2$ un morfismo separable entre curvas elípticas, tenemos que $latex \partial \psi=\sum_{P\in \psi^{-1}(Q)}e_{\psi}(P)$ $latex \forall Q\in E_2$ con $latex e_\psi(P)=\nu_P(\psi^{*}t_{\psi(P)})$ el índice de ramificación [Silverman II , 2.6a], ahora, si usamos [Silverman III 4.10 a,c] tenemos que $latex \psi$ es separable $latex \Rightarrow \psi$ no tiene ramificación lo que implica que $latex e_{\psi}(P)=1$, y como $latex \psi(P+Q)=\psi(P)+\psi(Q)$ es un homomorfismo de grupos tenemos que $latex \psi^{-1}(\infty_{E_2}) = Ker\psi \Rightarrow$ $latex \partial \psi=\sum_{P\in Ker\psi}e_\psi(P) = \sum_{P\in Ker\psi}1 =$ #$latex Ker\psi$
Sabiendo esto, podemos deducir algo interesante sobre la cardinalidad de la curva elíptica $latex E$, si usamos [Silverman III, 5.5] tenemos que si $latex \phi:E\rightarrow E$ es el endomorfismo de Frobenius que actúa en las coordenadas de los puntos elevándolos a la $latex q$ entonces el mapeo
$latex Id-\phi$ es separable y tenemos que $latex \phi(P)=P \Leftrightarrow P\in E(\mathbb{F}_q)$ y usando el párrafo anterior, $latex Ker(Id-\phi)$ consta de todos los puntos $latex \mathbb{F}_q$ racionales de la curva ya que se anulan con la identidad, lo que nos dice que $latex Ker(Id-\phi)=E(\mathbb{F}_q)$ por lo que igual con el párrafo anterior, $latex \partial(Id-\phi)=$#$latex E(\mathbb{F}_q)$
Me he tardado en escribir en mi blog, pero por ahora dejo sólo esta parte, después vamos a terminar la demostración, pero falta relacionar los morfismos de la curva elíptica con elementos de una torcedura cuadrática de la curva, y con eso, construiremos $latex Id-\phi$ pero visto desde puntos en otra curva definida sobre $latex \mathbb{F}_q(s,t)$ tal que $latex s^2 = f(t)$ es decir la misma curva $latex E$ será $latex E^{TW}: f(t)y^2 = f(x)$ y los puntos equivalentes a la identidad y el mapeo de frobenius ahí serán $latex (t,1)$ y $latex (t^q,s^{\frac{q-1}{2}})$ , pero esto será después de establecer este isomorfismo $latex Mor_{\mathbb{F}_q}(E,E) \cong E^{TW}(\mathbb{F}_q(s,t)) \cong E(\mathbb{F}_q(s,t))$ el cual nos permitirá calcular la cardinalidad del Kernel que necesitamos mediante otra función entre puntos sobre la curva con puntos en el campo de funciones racionales utilizando el grado de los puntos Id y Frobenius (los puntos ya no son numeros... son cocientes de polinomios en la torcedura cuadrática).
Espero les haya servido.
Tuesday, November 25, 2014
Wednesday, October 29, 2014
j-invariante y anillo de endomorfismos de curvas elípticas (isogenias)
Ahora, estoy dedicándome a explorar el anillo de endomorfismos de una curva elíptica $latex C$
sobre un campo perfecto (todo polinomio irreducible sobre este campo tenga raíces diferentes) para poder hablar de aplicaciones criptográficas.
Estos campos perfectos por excelencia en criptografía son $latex \mathbb{F}_q$.
Vamos a definir algunas cosas para clasificarlas, ya que anteriormente nos habíamos dedicado a estudiar cada curva por separado, pero ahora queremos considerar TODAS las curvas elípticas sobre un campo $latex \mathbb{K}$ , y ver cuáles son isomorfas, y ver cada clase de curvas isomorfas como la misma curva, como un sólo punto, este espacio es una espacio modular, y generalmente es estudiado como un esquema.
Algo interesante es que en las curvas elípticas es que este espacio tiene dimensión 1, y de hecho es una linea topológicamente hablando.
Como sabemos, una curva elíptica tiene una estructura algebraica y una estructura geométrica, las curvas elípticas son el caso más simple de una variedad abeliana, éstas tienen dimensión 1 (Es decir, al considerar su anillo de coordenadas, su dimensión de Krull es 1, lo cual se traduce a que la cadena más grande de ideales por contención que se puede construir $latex \lbrace J_i \rbrace$ es de altura 1 por lo que $latex J_0 \subset J_1 \subset J_2$ tenemos que $latex J_1 = J_2$ lo que hace al anillo Noetheriano.
Vamos a explorar un poco lo que es una curva elíptica desde el punto de vista más formal, y construiremos relaciones de éstas, clasificaciones, y exploraremos cómo se comporta el anillo de morfismos de la curva en si misma, así como la relación que hay entre la traza y determinante de ciertos endomorfismos con el subgrupo de torsión de la curva en cuestión.
Curva suave de género 1, entonces es elíptica
Todas las curvas de género 1 son elípticas, como lo pueden ver en este post via el teorema de Riemann-Roch , y la construcción de la ecuación en la forma de Weierstrass ahora redefiniremos de una curva elíptica, recordemos que en la estructura algebraica de la curva siempre hay un punto distinguido que nos sirve como identidad visto como variedad abeliana, llamémoslo $latex \mathcal{O}$ , entonces si tenemos que una curva $latex E$ es suave de género g=1 y proyectiva , entonces por el teorema de Riemann-Roch tenemos que si $latex n>2g-2=0$ tenemos que $latex \mathcal{L}(n0)=n-g+2=n$ si $latex n=2$ y $latex n=3$ podemos encontrar dos funciones $latex x,y\in \mathbb{K}(E)$ que tienen exactamente 2 polos en $latex \mathcal{O}$ y $latex y$ tiene 3 polos en $latex \mathcal{O}$ , ahora si $latex n=6$, obtenemos una base para el espacio vectorial $latex \mathcal{L}(6\mathcal{O})$ la cual es $latex \lbrace 1,x,x^2,x^3,y,y^2,xy \rbrace$
La cual nos da la forma usual de la curva elíptica en la forma de Weierstrass como todos la conocemos.
$latex y^2 + f_1xy+f_3y = x^3+f_2x^2 + f_4x + f_6$
tal que $latex f_i \in \mathbb{K}$
Aquí fuimos de álgebra directamente a geometría.
Ahora, ya para geometrizar esto por completo, considera:
$latex \Phi: E \rightarrow \mathbb{P}^{2}_{\mathbb{K}}$
$latex (x,y) \mapsto [x:y:1]$
Ahora, también por lo anterior y Riemann-Roch tenemos que $latex [\mathbb{K}(E):\mathbb{K}(x)]=2$ y que $latex [\mathbb{K}(E):\mathbb{K}(y)]=3$ lo cual implica que $latex [\mathbb{K}(E):\mathbb{K}(x,y)]=1$, por lo que $latex \Phi$ tiene grado 1, como por hipótesis tenemos que $latex E$ es suave, sabemos que su discriminante $latex \Delta\neq 0$ , es decir $latex \Phi(\mathcal{O})=[0:1:0]=\infty$ es el punto al infinito.
Isogenias
La palabra "isogenia" no me gusta, pero no sé cómo traducirla, en inglés se dice "isogeny" , pero bueno, hay poca literatura en español sobre curvas isógenas (o no he buscado bien... o no he buscado más bien en español).
Lo que queremos hacer ahora es definir homomorfismos entre curvas elípticas, es decir queremos comenzar a compararlas de tal manera que ésta comparación respete sus propiedades geometricas y algebraicas.
Sean $latex E$ y $latex F$ dos curvas elípticas sobre $latex \mathbb{K}$ , una isogenia es un mapeo racional $latex \alpha: E\rightarrow F$ que induce homomorfismo de grupos de $latex E(\mathbb{K})$ y $latex F(\mathbb{K})$ (es decir entre los grupos abelianos inducidos por la curva elíptica)
Para entender esta definición, como ya lo había definido en el post antes citado en este post, vamos a redefinir lo que es un campo de funciones de una curva proyectiva en general para saber qué es un mapeo racional.
Sea $latex C(\mathbb{K})$ una curva proyectiva definida por $latex f(x,y,z)=0$ donde $latex f\in \mathbb{K}[x,y,z]$ es irreducible en $latex f\in \bar{\mathbb{K}}[x,y,z]$.
El campo de funciones $latex \mathbb{K}(C)$ son las funciones $latex g/h$ tal que
$latex g,h$ polinomios homogéneos del anillo $latex \mathbb{K}[x,y,z]$ de mismo grado
$latex h\notin (f)$ (el ideal generado por f)
$latex g_1/h_1$ y $latex g_2/h_2$ son equivalentes cuando $latex g_1h_2-g_2h_1 \in (f)$
Si te da miedo lo proyectivo, aquí te dejo la definición afín, pero debes trabajar proyectivamente, aquí te dejo un post anterior sobre el espacio proyectivo.
$latex \mathbb{K}(C)=Frac(\mathbb{K}[C])=Frac(\mathbb{K}[x,y]/(f))$
Decimos que un mapeo racional entre dos curvas proyectivas
$latex \Phi: E \rightarrow F$
$latex P\mapsto [\phi_x(P):\phi_y(P):\phi_z(P)]$
Tal que $latex \phi_i \in \mathbb{K}(E)$
Decimos que el mapeo es regular en $latex P\in E(\bar{\mathbb{K}})$ (puntos de E con coordenadas en la cerradura del campo) si existe $latex g\in\bar{\mathbb{K}}(E)$ tal que $latex [g\phi_x(P):g\phi_y(P):g\phi_z(P)]$ está bien definida y no todos son coordenada 0 ($latex [0:0:0] \notin \mathbb{P}^2$).
Si un mapeo es regular en todos los puntos, decimos que es un morfismo , puede verse en el libro Advanced topics in the arithmetic of elliptic curves (Silverman) que si $latex E$ es suave proyectiva, entonces todo mapeo racional de $latex E$ a una curva proyectiva $latex F$ es un morfismo.
Tambien decimos que un isomorfismo entre curvas elípticas es una isogenia invertible.
Como ejemplos que pueden trabajar en casa, consideren los mapeos sobre una curva $latex E$ sobre el campo $latex \mathbb{F_q}$ con $latex q=p^n$
$latex P\mapsto 2P$
Pueden demostrar que eso realmente es una isogenia
También
$latex \pi:E \rightarrow E$
$latex [x:y,z] \mapsto [x^q:y^q:z^q]$
Donde este mapeo es el endomorfismo de Frobenius y tenemos que
$latex \hat{\pi}:\mathbb{F}_q \rightarrow \mathbb{F}_q$
$latex x\mapsto x^p$
Este mapeo es muy importante , ya que es un automorfismo, y tenemos que
$latex \pi(\mathbb{F}_q)$ deja fijos a los elementos $latex \mathbb{F}_p$
Ahora queremos representar explícitamente las isogenias entre curvas elípticas.
Lema: Si $latex E$ y $latex F$ son curvas elípticas sobre $latex \mathbb{K}$ en su forma estándar de Weierstrass (como en los ejemplos) y si $latex \alpha$ es una isogenia no trivial, entonces tiene la siguiente forma:
$latex \alpha(x,y)=\Big( \frac{u(x)}{v(x)} , \frac{s(x)}{t(x)}y \Big )$
donde
$latex u,v,s,t \in \bar{\mathbb{K}}[x]$
y las fracciones están reducidas (numerador y cocientes son primos relativos)
Esto es fácil demotrarlo, te dejo los hints porque es mucha talacha para que tú lo hagas.
Considera lo que ya sabemos, supón que $latex \alpha$ está definido por el mapeo racional $latex [\alpha_x:\alpha_y:\alpha_z]$, y considera para todo punto afín
$latex [x:y:1] \in E(\bar{\mathbb{K}})$
$latex \alpha(x,y)=\Big ( r_1(x,y), r_2(x,y) \Big )$ donde $latex r_1(x,y)=\alpha_x(x,y,1)/\alpha_z(x,y,1)$ y $latex r_2(x,y)=\alpha_y(x,y,1)/\alpha_z(x,y,1)$
utilizando la relación de $latex E$ que ya conoces entre $latex x,y$ que es $latex y^2=x^3+ax+b$ elimina los factores $latex y^n$ y reescribe $latex r_1(x,y)=\frac{p_1(x)+p_2(x)y}{p_3(x)+p_4(x)y}$, multiplica el numerador y denominador por $latex p_3(x)-p_4(x)y$ y vuelve a reducir los $latex y^n$
Eso te dara otra versión de $latex \alpha$ que también tiene $latex y$, pero considera la simetría de la curva y el inverso de los puntos... sabes que $latex \alpha(x,-y)=-\alpha(x,y)$ por lo que deben haber cosas que se hagan 0, el argumento en $latex \alpha_y$ es similar.
El grado de una isogenia se define bajo esta representación tan cómoda como $latex \partial(\alpha):=max\lbrace u,v\rbrace$, y decimos que la isogenia $latex \alpha$ es separable si la derivada de $latex \frac{u}{v}$ NO es la función 0
El grado jugara un papel importante para despues definir otras cosas y jugar con la funcion zeta elíptica y el teorema de Hasse.
Corolario-Definición
Si $latex \alpha(x,y)$ es una isogenia como en el lema pasado, $latex v,t$ tienen las mismas raíces, y justamente estas raíces corresponden al kernel de $latex \alpha$
Teorema-Definición: Sea $latex \alpha: E\rightarrow F$ una isogenia con $latex \partial(\alpha)=n$ separable, entonces existe una única isogenia $latex \hat\alpha:F\rightarrow E$ tal que $latex \hat\alpha \circ \alpha = [n]$ , y le llamamos isogenia dual de $latex \mathbb{\alpha}$
Cosas que se pueden demostrar es que si $latex \alpha:E\rightarrow F$ y $latex \beta:E\rightarrow F$ entonces $latex \hat{\alpha+\beta}=\hat\alpha+\hat\beta$ y que $latex \alpha + \hat\alpha = 1 + \partial(\alpha)-\partial(1-\alpha)$, lo cual nos lleva a que definamos la traza de un endomorfismo
$latex tr(\alpha)=tr(\hat\alpha)=\alpha+\hat\alpha$
Nota que tenemos que $latex \alpha\cdot \hat\alpha=[\partial(\alpha)]$ (en la misma curva elíptica) por lo que $latex \partial(\hat\alpha) = \partial(\alpha)$
Lo anterior nos lleva a un teorema importante que nos relaciona con un polinomio cuadrático cada endomorfismo.
Teorema:
Sea $latex \alpha \in End_\mathbb{K}(E)$ , entonces $latex \alpha$ y $latex \hat\alpha$ son raíces del polinomio característico
$latex \xi(\lambda)=\lambda^2 - (tr\alpha)\lambda + \partial(\alpha) = 0$
Esto es muy fácil de probar
$latex \alpha^2 -(tr\alpha)\alpha+\partial(\alpha)=\alpha^2 - (\alpha+\hat\alpha)\alpha + \hat\alpha\alpha = 0$ lo mismo para $latex \hat\alpha$.
Ahora... como última parte de esta sección, consideremos el campo de caracteristica p y vamos a restringir los endomorfismos al subgrupo de torsión de la curva elíptica, es decir, sólo los evaluaremos en elementos de $latex E[n]$
y si $latex \alpha \in latex End(E)_\mathbb{K}$ a la restricción de $latex \alpha\mid_{E[n]}$ la redefiniremos como:
$latex \alpha_n$
Esta $latex \alpha_n$ es un endomorfismo del subgrupo abeliano $latex E[n]$ ya que $latex \alpha$ es un morfismo y manda puntos de torsión a puntos de torsión y como vimos anteriormente:
$latex E[n] \cong \mathbb{Z}/n\mathbb{Z} \oplus \mathbb{Z}/n\mathbb{Z}$, considera una base para $latex E[n]$ , llámale $latex (P_1,P_2)$
entonces podemos representar en forma de matriz a $latex \alpha_n=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ donde $latex a,b,c,d \in \mathbb{Z}/n\mathbb{Z}$ y $latex \alpha(P_1)=aP_1\oplus cP_2$ y $latex \alpha(P_2)=bP_1+dP_2$ , la representación de la matriz depende de la base, pero la traza $latex tr \alpha_n$ y $latex det \alpha_n$ no.
Lo que nos deja con este teorema que es MUY importante, ya que es la conexión más importante que hay entre los endomorfismos y las restricciónes a $latex E[n]$
Teorema:
Sea $latex \alpha \in End_\mathbb{K}(E)$ con $latex E$ elíptica sobre $latex \mathbb{K}$ y sea $latex n$ un número positivo primo relativo a la característica de $latex \mathbb{K}$
entonces:
$latex tr \alpha \equiv tr \alpha_n \bmod n$ y $latex \partial(\alpha) \equiv det(\alpha_n) mod n$
Con esto ya estamos bien equipados.
j-Invariante
Ahora, ya que sabemos que todas las curvas de género 1 son elípticas, hay una manera de clasificarlas muy eficientemente, consideremos $latex \mathcal{E}$ como el espacio de todas las curvas elípticas sobre $latex \mathbb{K}$ , entonces existe una función
$latex j: \mathcal{E} \rightarrow \mathbb{K}$
Llamada j-invariante que cumple que:
$latex j(E)=j(F)\Leftrightarrow E \cong F$ sobre $latex \bar{\mathbb{K}}$
Se ha demostrado que la función $latex j$ es suprayectiva, por lo que $latex \mathbb{K}$ es el espacio modular de dimensión 1y tenemos que las fibras $latex j^{-1}(x)$ son clases de $latex \bar{\mathbb{K}}$-isomorfismos de curvas elípticas definidas sobre $latex \mathbb{K}$
Las curvas elípticas que generalmente usamos en criptografía son de la forma
$latex E:=y^2 - x^3 - px -q $
Por lo que podemos expresar el j-invariante de manera más reducida como:
$latex j(E)=1728 \frac{4p^3}{4p^3+27q^2}$
Torsiones cuadráticas de curvas elípticas
Aquí no voy a entrar tanto en detalle porque tengo poca experiencia pero es importante.
Imagina que tenemos las curvas $latex E$ y $latex F$ definids sobre $latex \mathbb{K}$ tal que existe un isomorfismo $latex E\rightarrow F$ sobre $latex \bar{\mathbb{K}}$ pero no sobre $latex \mathbb{K}$ , decimos en este caso que $latex E$ y $latex F$ son torsiones.
Ejemplo:
Considera las curvas $latex E:y^2=x^3+11664$ y $latex F:y^2=x^3+1$
Ambas suaves y lindas definidas sobre $latex \mathbb{Q}$ , estas curvas NO pueden ser isomorfas sobre $latex \mathbb{Q}$ ya que $latex F$ tiene un punto de orden 2 $latex (-1,0)$ y $latex E$ no tienen ningun punto de orden 2 (el punto de orden 2 en este caso como son simetricas son el eje x , tendria que se un punto de weierstrass, lo cual implica que x=0 por lo que $latex y\notin \mathbb{Q}$)
Pero ahora considera las curvas en la extensión cuadrática $latex \mathbb{Q}(\sqrt{2})$,
aquí podemos definir el isomorfismo:
$latex \Psi: E \rightarrow F$
$latex (x,y) \mapsto (2^3 3^6 \sqrt{2}\cdot x , 2^2 3^3\cdot y)$
Por lo que decimos que $latex E$ y $latex F$ son twists cuadráticos.
Por lo anterior... deberían de tener el mismo j-invariante, el cual es claramente 0, por lo que todas las curvas existentes con j-invariante 0 , serán isomorfas a estas que ejemplificamos en alguna extensión del campo en el que estén trabajando.
Subgrupo de torsión y endomorfismo de una curva elíptica
Sabemos que el mapeo que manda a multiplicar por $latex [n]$ los puntos de una curva $latex E$ es un morfismo, al kernel de este mapeo le llamamos subgrupo de torsión y lo denotamos como $latex E[n]$ , y tenemos el siguiente teorema cuando $latex K$ tiene caracteristica p
$latex E[n]\cong \mathbb{Z}/n\mathbb{Z}\oplus \mathbb{Z}/n\mathbb{Z}$ si $latex p=0$ o $latex p\ndiv n$
o
$latex E[n]\cong \mathbb{Z}/n\mathbb{Z}$ o $latex \lbrace 0\rbrace 0$ si $latex p>0$ y $latex n=p^m$
donde $latex \oplus$ es la adición elíptica .
Tenemos que ahora con esto podemos construir una infinidad de elementos ya que $latex [n] \ in End_\mathbb{K}(E)$
esto debería ser para ustedes pero lo pongo.
$latex (\alpha\cdot [n])(P)=\alpha(nP)=\alpha(\bigoplus_{i=1}^n {P}) = \bigoplus_{i=1}^n { \alpha(P) }=n\alpha(P)=([n]\cdot \alpha(P)$
Esto nos dice que $latex \mathbb{Z}$ es un subanillo de $latex End_\mathbb{K}(E)$ , lo puedes observar viendo como se comporta la composición y la suma de $latex [n]$ y $latex [m]$ , verás que forman un anillo esos endomorfismos y son isomorfos a $latex \mathbb{Z}$
Este anillo de endomorfismos no sólo tiene a $latex \mathbb{Z}$ , como vimos, también está el endomorfismo $latex \pi$ de Frobenius (con $latex \mathbb{K}$ de caracteristica p>0 como el caso de criptografía) y pues por lo tanto todas las composiciones y sumas de éste con los isomorfos a $latex \mathbb{Z}$ cuando la curva $latex E$ es supersingular, este anillo de endomorfismos se comporta como un álgebra de cuaternios y no es conmutativo.
Espero les haya interesado, cualquier duda o corrección háganmela saber
Eduardo Ruíz Duarte (beck)
Twitter: @toorandom
sobre un campo perfecto (todo polinomio irreducible sobre este campo tenga raíces diferentes) para poder hablar de aplicaciones criptográficas.
Estos campos perfectos por excelencia en criptografía son $latex \mathbb{F}_q$.
Vamos a definir algunas cosas para clasificarlas, ya que anteriormente nos habíamos dedicado a estudiar cada curva por separado, pero ahora queremos considerar TODAS las curvas elípticas sobre un campo $latex \mathbb{K}$ , y ver cuáles son isomorfas, y ver cada clase de curvas isomorfas como la misma curva, como un sólo punto, este espacio es una espacio modular, y generalmente es estudiado como un esquema.
Algo interesante es que en las curvas elípticas es que este espacio tiene dimensión 1, y de hecho es una linea topológicamente hablando.
Como sabemos, una curva elíptica tiene una estructura algebraica y una estructura geométrica, las curvas elípticas son el caso más simple de una variedad abeliana, éstas tienen dimensión 1 (Es decir, al considerar su anillo de coordenadas, su dimensión de Krull es 1, lo cual se traduce a que la cadena más grande de ideales por contención que se puede construir $latex \lbrace J_i \rbrace$ es de altura 1 por lo que $latex J_0 \subset J_1 \subset J_2$ tenemos que $latex J_1 = J_2$ lo que hace al anillo Noetheriano.
Vamos a explorar un poco lo que es una curva elíptica desde el punto de vista más formal, y construiremos relaciones de éstas, clasificaciones, y exploraremos cómo se comporta el anillo de morfismos de la curva en si misma, así como la relación que hay entre la traza y determinante de ciertos endomorfismos con el subgrupo de torsión de la curva en cuestión.
Curva suave de género 1, entonces es elíptica
Todas las curvas de género 1 son elípticas, como lo pueden ver en este post via el teorema de Riemann-Roch , y la construcción de la ecuación en la forma de Weierstrass ahora redefiniremos de una curva elíptica, recordemos que en la estructura algebraica de la curva siempre hay un punto distinguido que nos sirve como identidad visto como variedad abeliana, llamémoslo $latex \mathcal{O}$ , entonces si tenemos que una curva $latex E$ es suave de género g=1 y proyectiva , entonces por el teorema de Riemann-Roch tenemos que si $latex n>2g-2=0$ tenemos que $latex \mathcal{L}(n0)=n-g+2=n$ si $latex n=2$ y $latex n=3$ podemos encontrar dos funciones $latex x,y\in \mathbb{K}(E)$ que tienen exactamente 2 polos en $latex \mathcal{O}$ y $latex y$ tiene 3 polos en $latex \mathcal{O}$ , ahora si $latex n=6$, obtenemos una base para el espacio vectorial $latex \mathcal{L}(6\mathcal{O})$ la cual es $latex \lbrace 1,x,x^2,x^3,y,y^2,xy \rbrace$
La cual nos da la forma usual de la curva elíptica en la forma de Weierstrass como todos la conocemos.
$latex y^2 + f_1xy+f_3y = x^3+f_2x^2 + f_4x + f_6$
tal que $latex f_i \in \mathbb{K}$
Aquí fuimos de álgebra directamente a geometría.
Ahora, ya para geometrizar esto por completo, considera:
$latex \Phi: E \rightarrow \mathbb{P}^{2}_{\mathbb{K}}$
$latex (x,y) \mapsto [x:y:1]$
Ahora, también por lo anterior y Riemann-Roch tenemos que $latex [\mathbb{K}(E):\mathbb{K}(x)]=2$ y que $latex [\mathbb{K}(E):\mathbb{K}(y)]=3$ lo cual implica que $latex [\mathbb{K}(E):\mathbb{K}(x,y)]=1$, por lo que $latex \Phi$ tiene grado 1, como por hipótesis tenemos que $latex E$ es suave, sabemos que su discriminante $latex \Delta\neq 0$ , es decir $latex \Phi(\mathcal{O})=[0:1:0]=\infty$ es el punto al infinito.
Isogenias
La palabra "isogenia" no me gusta, pero no sé cómo traducirla, en inglés se dice "isogeny" , pero bueno, hay poca literatura en español sobre curvas isógenas (o no he buscado bien... o no he buscado más bien en español).
Lo que queremos hacer ahora es definir homomorfismos entre curvas elípticas, es decir queremos comenzar a compararlas de tal manera que ésta comparación respete sus propiedades geometricas y algebraicas.
Sean $latex E$ y $latex F$ dos curvas elípticas sobre $latex \mathbb{K}$ , una isogenia es un mapeo racional $latex \alpha: E\rightarrow F$ que induce homomorfismo de grupos de $latex E(\mathbb{K})$ y $latex F(\mathbb{K})$ (es decir entre los grupos abelianos inducidos por la curva elíptica)
Para entender esta definición, como ya lo había definido en el post antes citado en este post, vamos a redefinir lo que es un campo de funciones de una curva proyectiva en general para saber qué es un mapeo racional.
Sea $latex C(\mathbb{K})$ una curva proyectiva definida por $latex f(x,y,z)=0$ donde $latex f\in \mathbb{K}[x,y,z]$ es irreducible en $latex f\in \bar{\mathbb{K}}[x,y,z]$.
El campo de funciones $latex \mathbb{K}(C)$ son las funciones $latex g/h$ tal que
$latex g,h$ polinomios homogéneos del anillo $latex \mathbb{K}[x,y,z]$ de mismo grado
$latex h\notin (f)$ (el ideal generado por f)
$latex g_1/h_1$ y $latex g_2/h_2$ son equivalentes cuando $latex g_1h_2-g_2h_1 \in (f)$
Si te da miedo lo proyectivo, aquí te dejo la definición afín, pero debes trabajar proyectivamente, aquí te dejo un post anterior sobre el espacio proyectivo.
$latex \mathbb{K}(C)=Frac(\mathbb{K}[C])=Frac(\mathbb{K}[x,y]/(f))$
Decimos que un mapeo racional entre dos curvas proyectivas
$latex \Phi: E \rightarrow F$
$latex P\mapsto [\phi_x(P):\phi_y(P):\phi_z(P)]$
Tal que $latex \phi_i \in \mathbb{K}(E)$
Decimos que el mapeo es regular en $latex P\in E(\bar{\mathbb{K}})$ (puntos de E con coordenadas en la cerradura del campo) si existe $latex g\in\bar{\mathbb{K}}(E)$ tal que $latex [g\phi_x(P):g\phi_y(P):g\phi_z(P)]$ está bien definida y no todos son coordenada 0 ($latex [0:0:0] \notin \mathbb{P}^2$).
Si un mapeo es regular en todos los puntos, decimos que es un morfismo , puede verse en el libro Advanced topics in the arithmetic of elliptic curves (Silverman) que si $latex E$ es suave proyectiva, entonces todo mapeo racional de $latex E$ a una curva proyectiva $latex F$ es un morfismo.
Tambien decimos que un isomorfismo entre curvas elípticas es una isogenia invertible.
Como ejemplos que pueden trabajar en casa, consideren los mapeos sobre una curva $latex E$ sobre el campo $latex \mathbb{F_q}$ con $latex q=p^n$
$latex P\mapsto 2P$
Pueden demostrar que eso realmente es una isogenia
También
$latex \pi:E \rightarrow E$
$latex [x:y,z] \mapsto [x^q:y^q:z^q]$
Donde este mapeo es el endomorfismo de Frobenius y tenemos que
$latex \hat{\pi}:\mathbb{F}_q \rightarrow \mathbb{F}_q$
$latex x\mapsto x^p$
Este mapeo es muy importante , ya que es un automorfismo, y tenemos que
$latex \pi(\mathbb{F}_q)$ deja fijos a los elementos $latex \mathbb{F}_p$
Ahora queremos representar explícitamente las isogenias entre curvas elípticas.
Lema: Si $latex E$ y $latex F$ son curvas elípticas sobre $latex \mathbb{K}$ en su forma estándar de Weierstrass (como en los ejemplos) y si $latex \alpha$ es una isogenia no trivial, entonces tiene la siguiente forma:
$latex \alpha(x,y)=\Big( \frac{u(x)}{v(x)} , \frac{s(x)}{t(x)}y \Big )$
donde
$latex u,v,s,t \in \bar{\mathbb{K}}[x]$
y las fracciones están reducidas (numerador y cocientes son primos relativos)
Esto es fácil demotrarlo, te dejo los hints porque es mucha talacha para que tú lo hagas.
Considera lo que ya sabemos, supón que $latex \alpha$ está definido por el mapeo racional $latex [\alpha_x:\alpha_y:\alpha_z]$, y considera para todo punto afín
$latex [x:y:1] \in E(\bar{\mathbb{K}})$
$latex \alpha(x,y)=\Big ( r_1(x,y), r_2(x,y) \Big )$ donde $latex r_1(x,y)=\alpha_x(x,y,1)/\alpha_z(x,y,1)$ y $latex r_2(x,y)=\alpha_y(x,y,1)/\alpha_z(x,y,1)$
utilizando la relación de $latex E$ que ya conoces entre $latex x,y$ que es $latex y^2=x^3+ax+b$ elimina los factores $latex y^n$ y reescribe $latex r_1(x,y)=\frac{p_1(x)+p_2(x)y}{p_3(x)+p_4(x)y}$, multiplica el numerador y denominador por $latex p_3(x)-p_4(x)y$ y vuelve a reducir los $latex y^n$
Eso te dara otra versión de $latex \alpha$ que también tiene $latex y$, pero considera la simetría de la curva y el inverso de los puntos... sabes que $latex \alpha(x,-y)=-\alpha(x,y)$ por lo que deben haber cosas que se hagan 0, el argumento en $latex \alpha_y$ es similar.
El grado de una isogenia se define bajo esta representación tan cómoda como $latex \partial(\alpha):=max\lbrace u,v\rbrace$, y decimos que la isogenia $latex \alpha$ es separable si la derivada de $latex \frac{u}{v}$ NO es la función 0
El grado jugara un papel importante para despues definir otras cosas y jugar con la funcion zeta elíptica y el teorema de Hasse.
Corolario-Definición
Si $latex \alpha(x,y)$ es una isogenia como en el lema pasado, $latex v,t$ tienen las mismas raíces, y justamente estas raíces corresponden al kernel de $latex \alpha$
Teorema-Definición: Sea $latex \alpha: E\rightarrow F$ una isogenia con $latex \partial(\alpha)=n$ separable, entonces existe una única isogenia $latex \hat\alpha:F\rightarrow E$ tal que $latex \hat\alpha \circ \alpha = [n]$ , y le llamamos isogenia dual de $latex \mathbb{\alpha}$
Cosas que se pueden demostrar es que si $latex \alpha:E\rightarrow F$ y $latex \beta:E\rightarrow F$ entonces $latex \hat{\alpha+\beta}=\hat\alpha+\hat\beta$ y que $latex \alpha + \hat\alpha = 1 + \partial(\alpha)-\partial(1-\alpha)$, lo cual nos lleva a que definamos la traza de un endomorfismo
$latex tr(\alpha)=tr(\hat\alpha)=\alpha+\hat\alpha$
Nota que tenemos que $latex \alpha\cdot \hat\alpha=[\partial(\alpha)]$ (en la misma curva elíptica) por lo que $latex \partial(\hat\alpha) = \partial(\alpha)$
Lo anterior nos lleva a un teorema importante que nos relaciona con un polinomio cuadrático cada endomorfismo.
Teorema:
Sea $latex \alpha \in End_\mathbb{K}(E)$ , entonces $latex \alpha$ y $latex \hat\alpha$ son raíces del polinomio característico
$latex \xi(\lambda)=\lambda^2 - (tr\alpha)\lambda + \partial(\alpha) = 0$
Esto es muy fácil de probar
$latex \alpha^2 -(tr\alpha)\alpha+\partial(\alpha)=\alpha^2 - (\alpha+\hat\alpha)\alpha + \hat\alpha\alpha = 0$ lo mismo para $latex \hat\alpha$.
Ahora... como última parte de esta sección, consideremos el campo de caracteristica p y vamos a restringir los endomorfismos al subgrupo de torsión de la curva elíptica, es decir, sólo los evaluaremos en elementos de $latex E[n]$
y si $latex \alpha \in latex End(E)_\mathbb{K}$ a la restricción de $latex \alpha\mid_{E[n]}$ la redefiniremos como:
$latex \alpha_n$
Esta $latex \alpha_n$ es un endomorfismo del subgrupo abeliano $latex E[n]$ ya que $latex \alpha$ es un morfismo y manda puntos de torsión a puntos de torsión y como vimos anteriormente:
$latex E[n] \cong \mathbb{Z}/n\mathbb{Z} \oplus \mathbb{Z}/n\mathbb{Z}$, considera una base para $latex E[n]$ , llámale $latex (P_1,P_2)$
entonces podemos representar en forma de matriz a $latex \alpha_n=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ donde $latex a,b,c,d \in \mathbb{Z}/n\mathbb{Z}$ y $latex \alpha(P_1)=aP_1\oplus cP_2$ y $latex \alpha(P_2)=bP_1+dP_2$ , la representación de la matriz depende de la base, pero la traza $latex tr \alpha_n$ y $latex det \alpha_n$ no.
Lo que nos deja con este teorema que es MUY importante, ya que es la conexión más importante que hay entre los endomorfismos y las restricciónes a $latex E[n]$
Teorema:
Sea $latex \alpha \in End_\mathbb{K}(E)$ con $latex E$ elíptica sobre $latex \mathbb{K}$ y sea $latex n$ un número positivo primo relativo a la característica de $latex \mathbb{K}$
entonces:
$latex tr \alpha \equiv tr \alpha_n \bmod n$ y $latex \partial(\alpha) \equiv det(\alpha_n) mod n$
Con esto ya estamos bien equipados.
j-Invariante
Ahora, ya que sabemos que todas las curvas de género 1 son elípticas, hay una manera de clasificarlas muy eficientemente, consideremos $latex \mathcal{E}$ como el espacio de todas las curvas elípticas sobre $latex \mathbb{K}$ , entonces existe una función
$latex j: \mathcal{E} \rightarrow \mathbb{K}$
Llamada j-invariante que cumple que:
$latex j(E)=j(F)\Leftrightarrow E \cong F$ sobre $latex \bar{\mathbb{K}}$
Se ha demostrado que la función $latex j$ es suprayectiva, por lo que $latex \mathbb{K}$ es el espacio modular de dimensión 1y tenemos que las fibras $latex j^{-1}(x)$ son clases de $latex \bar{\mathbb{K}}$-isomorfismos de curvas elípticas definidas sobre $latex \mathbb{K}$
Las curvas elípticas que generalmente usamos en criptografía son de la forma
$latex E:=y^2 - x^3 - px -q $
Por lo que podemos expresar el j-invariante de manera más reducida como:
$latex j(E)=1728 \frac{4p^3}{4p^3+27q^2}$
Torsiones cuadráticas de curvas elípticas
Aquí no voy a entrar tanto en detalle porque tengo poca experiencia pero es importante.
Imagina que tenemos las curvas $latex E$ y $latex F$ definids sobre $latex \mathbb{K}$ tal que existe un isomorfismo $latex E\rightarrow F$ sobre $latex \bar{\mathbb{K}}$ pero no sobre $latex \mathbb{K}$ , decimos en este caso que $latex E$ y $latex F$ son torsiones.
Ejemplo:
Considera las curvas $latex E:y^2=x^3+11664$ y $latex F:y^2=x^3+1$
Ambas suaves y lindas definidas sobre $latex \mathbb{Q}$ , estas curvas NO pueden ser isomorfas sobre $latex \mathbb{Q}$ ya que $latex F$ tiene un punto de orden 2 $latex (-1,0)$ y $latex E$ no tienen ningun punto de orden 2 (el punto de orden 2 en este caso como son simetricas son el eje x , tendria que se un punto de weierstrass, lo cual implica que x=0 por lo que $latex y\notin \mathbb{Q}$)
Pero ahora considera las curvas en la extensión cuadrática $latex \mathbb{Q}(\sqrt{2})$,
aquí podemos definir el isomorfismo:
$latex \Psi: E \rightarrow F$
$latex (x,y) \mapsto (2^3 3^6 \sqrt{2}\cdot x , 2^2 3^3\cdot y)$
Por lo que decimos que $latex E$ y $latex F$ son twists cuadráticos.
Por lo anterior... deberían de tener el mismo j-invariante, el cual es claramente 0, por lo que todas las curvas existentes con j-invariante 0 , serán isomorfas a estas que ejemplificamos en alguna extensión del campo en el que estén trabajando.
Subgrupo de torsión y endomorfismo de una curva elíptica
Sabemos que el mapeo que manda a multiplicar por $latex [n]$ los puntos de una curva $latex E$ es un morfismo, al kernel de este mapeo le llamamos subgrupo de torsión y lo denotamos como $latex E[n]$ , y tenemos el siguiente teorema cuando $latex K$ tiene caracteristica p
$latex E[n]\cong \mathbb{Z}/n\mathbb{Z}\oplus \mathbb{Z}/n\mathbb{Z}$ si $latex p=0$ o $latex p\ndiv n$
o
$latex E[n]\cong \mathbb{Z}/n\mathbb{Z}$ o $latex \lbrace 0\rbrace 0$ si $latex p>0$ y $latex n=p^m$
Qué corolario de este teorema pueden deducir de $latex E[p]$ ?
Pero lo que diremos es que en un campo de caracteristica positiva , si $latex E[p]\cong \mathbb{Z}/p\mathbb{Z}$ le llamamos a la curva $latex E$ ordinaria, y si es $latex E[p]\cong \lbrace 0\rbrace $ supersingular.
Ahora, aquí el anillo de Endomorfismos de la curva $latex E$ los denotamos como $latex End_\mathbb{K}(E)$
y tenemos que las isogenias $latex \alpha:E\rightarrow E$ son endomorfismos, y forman un anillo
bajo las siguientes operaciones
$latex \alpha,\beta \in End_\mathbb{K}(E)$
$latex (\alpha + \beta)(P)=\alpha(P)\oplus\beta(P)$
$latex (\alpha\cdot \beta)(P)=(\alpha \circ \beta)(P)$
Tenemos que ahora con esto podemos construir una infinidad de elementos ya que $latex [n] \ in End_\mathbb{K}(E)$
esto debería ser para ustedes pero lo pongo.
$latex (\alpha\cdot [n])(P)=\alpha(nP)=\alpha(\bigoplus_{i=1}^n {P}) = \bigoplus_{i=1}^n { \alpha(P) }=n\alpha(P)=([n]\cdot \alpha(P)$
Esto nos dice que $latex \mathbb{Z}$ es un subanillo de $latex End_\mathbb{K}(E)$ , lo puedes observar viendo como se comporta la composición y la suma de $latex [n]$ y $latex [m]$ , verás que forman un anillo esos endomorfismos y son isomorfos a $latex \mathbb{Z}$
Este anillo de endomorfismos no sólo tiene a $latex \mathbb{Z}$ , como vimos, también está el endomorfismo $latex \pi$ de Frobenius (con $latex \mathbb{K}$ de caracteristica p>0 como el caso de criptografía) y pues por lo tanto todas las composiciones y sumas de éste con los isomorfos a $latex \mathbb{Z}$ cuando la curva $latex E$ es supersingular, este anillo de endomorfismos se comporta como un álgebra de cuaternios y no es conmutativo.
Espero les haya interesado, cualquier duda o corrección háganmela saber
Eduardo Ruíz Duarte (beck)
Twitter: @toorandom
Monday, October 13, 2014
Leyes fundamentales de la estupidez humana (Carlo M Cipolla)
Esto es algo que me llamó la atención, gracias a Omar Lara que me lo compartió
es un tratado formal sobre la estupidez humana, el artículo completo aquí
Introducción
es un tratado formal sobre la estupidez humana, el artículo completo aquí
Introducción
"La humanidad se encuentra (y sobre esto el acuerdo es unánime) en un estado deplorable. Ahora bien, no se trata de ninguna novedad. Si uno se atreve a mirar hacia atrás, se da cuenta de que siempre ha estado en una situación deplorable. El pesado fardo de desdichas y miserias que los seres humanos deben soportar, ya sea como individuos o como miembros de la sociedad organizada, es básicamente el resultado del modo extremadamente improbable (y me atrevería a decir estúpido) como fue organizada la vida desde sus comienzos.
Desde Darwin sabemos que compartimos nuestro origen con las otras especies del reino animal, y todas las especies -ya se sabe- desde el gusanillo al elefante tienen que soportar sus dosis cotidianas de tribulaciones, temores, frustraciones, penas y adversidades. Los seres humanos, sin embargo, poseen el privilegio de tener que cargar con un peso añadido, una dosis extra de tribulaciones cotidianas provocadas por un grupo de personas que pertenecen al propio género humano. Este grupo es mucho más poderoso que la Mafia, o que el complejo industrial-militar o que la Internacional Comunista. Se trata de un grupo no organizado, que no se rige por ninguna ley, que no tiene jefe, ni presidente, ni estatuto, pero que consigue, no obstante, estar en perfecta sintonía, como si estuviese guiado por una mano invisible, de tal modo que las actividades de cada uno de sus miembros contribuyen poderosamente a reforzar y ampliar la eficacia de la actividad de todos los demás miembros. La naturaleza, el carácter y el comportamiento de los miembros de este grupo constituyen el tema de las páginas que siguen.
Es preciso subrayar a este respecto que este ensayo no es ni producto del cinismo ni un ejercicio de derrotismo social -no más de cuanto pueda serlo un libro de microbiología-. Las páginas que siguen son, de hecho, el resultado de un esfuerzo constructivo por investigar, conocer y, por lo tanto, posiblemente neutralizar, una de las más poderosas y oscuras fuerzas que impiden el crecimiento del bienestar y de la felicidad humana. "
1. Siempre e inevitablemente cada uno de nosotros subestima el número de individuos
estúpidos que circulan por el mundo
2. La probabilidad de que una persona determinada sea una estúpida es independiente
de cualquier otra característica de la misma persona.
3. Una persona estúpida es una persona que causa un daño a otra persona o grupo de
personas sin obtener, al mismo tiempo, un provecho para sí, o incluso obteniendo un
perjuicio.
4. Las personas no estúpidas subestiman siempre el potencial nocivo de las personas
estúpidas. Los no estúpidos, en especial, olvidan constantemente que en cualquier
momento y lugar, y en cualquier circunstancia, tratar y/o asociarse con individuos
estúpidos se manifiesta infaliblemente como costosísimo error.
Carlo M Cipolla
Sunday, October 12, 2014
Otro post más de política (yapp)
Sobre la agresión física a Cárdenas y los ideales inocentes anarquistas
Y pseudo humanistas de libertad de la nueva juventud izquierdista mexicana (o sea yo y muchos más)
Para mí que sí los pateen que se de cuenta la “izquierda“ que tampoco los queremos y que decepcionaron a la clase baja con sus ambiciones derechistas y la misma sed de poder de siempre.
Violencia... Sí， ya es hora de los madrazos，país con 60 millones de paupérrimos... Y Todos somos luchadores sociales en twitter y facebook... Y nos indignamos por unas patadas a otro power-retarded.
No violencia? Ok como a los normalistas... Iguala...
Vivimos con un concepto de libertad y paz muy inocente... Y un tanto estúpido porque no resuelve nada... Te mantiene constante y en 0.
Todos quieren todo para todos y se manifiestan a veces muy enérgicos exigiendo como si te fueran a escuchar.
Es más escuchado el agresor anarquista que el pasivo con pancarta créanme... (Aunque no necesariamente más inteligente)
No se puede todo igual para todos... En serio no con ese idealismo y pseudohumanismo... Si quieres algo cercano a eso hay que comenzar a cambiar los modelos económicos... Madrear gente pa sacar del poder y comenzar a considerar los tabúes como ideas no tan estupidas... Tipo “privatización“... Después de los madrazos las cosas se tienen que reconsiderar... En europa todo está como en méxico se niegan.
Ley de telecomm en europa similar a mx lleva años... Y es para agarrar pedófilos y asesinos... Mientras no se tengan checados a todos no puedes tener sospechosos... Ahora si no quieres eso en tu ley... No te quejes del crimen organizado y acepta el hecho de que jamás resolverán tu caso.
El petróleo en europa está privatizado desde hace décadas y hay bastante en el norte... No tanto como méxico.
Pero vale madre porque las empresas privadas pagan muchos impuestos，hay competencia y mucho empleo.... Por lo tanto baja de precios y el país genera energía eólica y solar por todos lados... Tanta que le sobra y se la venden a países vecinos... Así que no hay que preocuparse sólo por un recurso energético... En méxico deberíamos manifestarnos mejor por poner plantas eólicas en todo el país y placas fotovoltaicas en cada techo por ley.
El no enfocarse sólo en petróleo los hace más ecologistas que todos los que se manifiestan porque no destruyan una playa en méxico，los hace generar más tecnología sin pensar en que es “verde“ porque en esencia cualquier consecuencia ya lo es.
Hay que reconsiderar las ideas que tal vez nuestros padres nos inculcaron para “defender“， los tiempos cambian... Y creo que la inocencia convierte los argumentos en falacias... Hay que saber qué defender.
Así que en resumen... Pateen，sáquenlos del trono los que puedan/podamos....
Respeto?
No... Nunca te respetaron... Te agredieron y mataron a tus abuelos... Padres... O tíos... No merecen ni que los menciones... Y cambia tus paradigmas... Ábrelos más al progresismo... La idea romántica pseudo anarquista que la “joven izquierda“ traemos... Es sólo un modelo en el cual tenemos que considerar como una utopía en el sentido estricto de la palabra. (no imposibilidad) sino el modelo que debemos intentar cada día como individuos y no como sociedad.
Vamos a darle，somos muchos y tenemos buenas ideas... Sólo hay que organizarlas.
Saludos
Y pseudo humanistas de libertad de la nueva juventud izquierdista mexicana (o sea yo y muchos más)
Para mí que sí los pateen que se de cuenta la “izquierda“ que tampoco los queremos y que decepcionaron a la clase baja con sus ambiciones derechistas y la misma sed de poder de siempre.
Violencia... Sí， ya es hora de los madrazos，país con 60 millones de paupérrimos... Y Todos somos luchadores sociales en twitter y facebook... Y nos indignamos por unas patadas a otro power-retarded.
No violencia? Ok como a los normalistas... Iguala...
Vivimos con un concepto de libertad y paz muy inocente... Y un tanto estúpido porque no resuelve nada... Te mantiene constante y en 0.
Todos quieren todo para todos y se manifiestan a veces muy enérgicos exigiendo como si te fueran a escuchar.
Es más escuchado el agresor anarquista que el pasivo con pancarta créanme... (Aunque no necesariamente más inteligente)
No se puede todo igual para todos... En serio no con ese idealismo y pseudohumanismo... Si quieres algo cercano a eso hay que comenzar a cambiar los modelos económicos... Madrear gente pa sacar del poder y comenzar a considerar los tabúes como ideas no tan estupidas... Tipo “privatización“... Después de los madrazos las cosas se tienen que reconsiderar... En europa todo está como en méxico se niegan.
Ley de telecomm en europa similar a mx lleva años... Y es para agarrar pedófilos y asesinos... Mientras no se tengan checados a todos no puedes tener sospechosos... Ahora si no quieres eso en tu ley... No te quejes del crimen organizado y acepta el hecho de que jamás resolverán tu caso.
El petróleo en europa está privatizado desde hace décadas y hay bastante en el norte... No tanto como méxico.
Pero vale madre porque las empresas privadas pagan muchos impuestos，hay competencia y mucho empleo.... Por lo tanto baja de precios y el país genera energía eólica y solar por todos lados... Tanta que le sobra y se la venden a países vecinos... Así que no hay que preocuparse sólo por un recurso energético... En méxico deberíamos manifestarnos mejor por poner plantas eólicas en todo el país y placas fotovoltaicas en cada techo por ley.
El no enfocarse sólo en petróleo los hace más ecologistas que todos los que se manifiestan porque no destruyan una playa en méxico，los hace generar más tecnología sin pensar en que es “verde“ porque en esencia cualquier consecuencia ya lo es.
Hay que reconsiderar las ideas que tal vez nuestros padres nos inculcaron para “defender“， los tiempos cambian... Y creo que la inocencia convierte los argumentos en falacias... Hay que saber qué defender.
Así que en resumen... Pateen，sáquenlos del trono los que puedan/podamos....
Respeto?
No... Nunca te respetaron... Te agredieron y mataron a tus abuelos... Padres... O tíos... No merecen ni que los menciones... Y cambia tus paradigmas... Ábrelos más al progresismo... La idea romántica pseudo anarquista que la “joven izquierda“ traemos... Es sólo un modelo en el cual tenemos que considerar como una utopía en el sentido estricto de la palabra. (no imposibilidad) sino el modelo que debemos intentar cada día como individuos y no como sociedad.
Vamos a darle，somos muchos y tenemos buenas ideas... Sólo hay que organizarlas.
Saludos
Tuesday, September 23, 2014
Cohomología de grupos
Queremos estudiar el la jacobiana $latex \mathbb{J}_{\mathbb{F}_q}(\mathcal{C})$ de una curva $latex \mathcal{C}$ hiperelíptica de género 2 con puntos $latex [f(t),g(t)] \in \mathcal{C}(\mathbb{F}_{q}(t))$, es decir en el campo de funciones racionales en una variable con coeficientes en $latex \mathbb{F}_q$, esto es para darle más estructura a la curva ya que en cierta extensión de $latex \mathbb{F}_q$ tendremos que será isomorfa a $latex \mathcal{C}(\mathbb{F}_q)$ porque ambas tendrán el mismo $latex j-$invariante, a esta nueva curva en la extensión del campo se le llama el twist de $latex \mathcal{C}$, más adelante veremos como usar el $latex \j-$invariante para clasificar curvas, pero primero necesitamos las herramientas necesarias, todo esto con el fin de poder demostrar el teorema de Hasse-Weil de una forma distinta el cual tiene aplicaciones importantes en criptografía con curvas algebraicas.
Sea $latex G$ un grupo finito y sea $latex M$ un grupo abeliano en el cual $latex G$ actúa, denotamos a la acción de $latex \sigma \in G$ en $latex m\in M$ por $latex m \rightarrow m^\sigma$.
Sean $latex m,n\in M$, entonces decimos que $latex M$ es un $latex G-$módulo derecho si la acción de $latex G$ en $latex M$ satisface:
$latex m^e = m$ $latex (m+n)^\sigma = m^\sigma + n^\sigma$ $latex (m^\sigma)^\tau = m^{\sigma\tau}$
Si $latex M,G$ son $latex G-$módulos, un $latex G-$homomorfismo es un homomorfismo de grupos abelianos $latex \phi:M\rightarrow N$ que conmuta con la acción de $latex G$, en símbolos:
$latex \phi(m^\sigma)=\phi(m)^\sigma$ $latex \forall m\in M$ y $latex \sigma \in G$
Definimos el 0-ésimo grupo de cohomología del $latex G-$módulo $latex M$
$latex H^0(G,M)=\lbrace m\in M : m^\sigma = m$ $latex \forall \sigma \in G \rbrace$
Es decir, es el submódulo de $latex M$ que tiene todos los elementos que son invariantes bajo los elementos de $latex G$, recuerden que este $latex G$ puede ser un grupo de automorfismos por ejemplo.
Recordemos que un complejo de co-cadenas es una sucesión de grupos abelianos o de módulos $latex (M_\bullet,d_\bullet)$ que están conectados por homomorfismos $latex d_{i}:M^i \rightarrow M^{i+1}$ llamados operadores de cofrontera, ya que pedimos que $latex d^{n+1}\circ d^n = 0$ $latex \forall n$ , esto es dual con los complejos de cadena, solo que en homología los operadores de frontera decrementan la dimensión mientras que en co cadenas la aumentan.
$latex ... \rightarrow M^{-2} \xrightarrow{d_{-2}} M^{-1} \xrightarrow{d_{-1}} M^0 \xrightarrow{d_0} M^1 \xrightarrow{d_1} ... \rightarrow M^{n-1} \xrightarrow{d_{n-1}}M^n\rightarrow ...$
Una propiedad básica de esto es que si tenemos una sucesión exacta de $latex G-$módulos, otra sucesión exacta.
Es decir
$latex 0\rightarrow P \xrightarrow{\phi} M \xrightarrow{\psi} N \rightarrow 0$
Tenemos que también es exacta
$latex 0\rightarrow H^0(G,P)\rightarrow H^0(G,M)\rightarrow H^0(G,N)$
Pero el mapeo último no será suprayectivo, para medir que "tan no suprayectivo" es, vamos a definir la parte de cohomología de grupos.
Definición: Sea $latex M$ un $latex G-$módulo, el grupo de n-cocadenas de $latex G$ a $latex M$ es:
$latex C^n(G,M)=\lbrace \omega:G^n\rightarrow M \rbrace$
Es decir, son todos los mapeos de $latex G^n$ a $latex M$
Definición: Decimos que el i-ésimo diferencial
$latex d^{i}_{M}:C^i(G,M)\rightarrow C^{i+1}(G,M)$
Es el mapeo.
$latex d^i(f)(g_0,g_1,...,g_i)=$
$latex g_0 f(g_1,...,g_i)+\displaystyle \sum_{j=1}^i {(-1)^j f(g_0,...,g_{j-1}g_j,g_{j+1},...,g_i) } + (-1)^{i+1}f(g_0,...,g_{i-1})$
Esta función está pensada para que funcione como un operador de co-frontera, y que anule su diferencial en una dimensión más baja, asó como en homología, y podamos construir sucesiones exactas, es decir.
$latex d^{i+1} \circ d^i = 0$
Definición: El grupo n-cociclos de $latex G$ a $latex M$ (con coeficientes en $latex M$) es:
$latex Z^n(G,M)=ker(d^n)$
Definición: El grupo de n-cofronteras
$latex B^n(G,M)=im(d^{n-1})$ para $latex n\geq 1$
y para $latex n=0$
$latex B^0(G,M)=0$
Bueno... hasta ahora qué tanto tenemos?
Recordemos que $latex d^{i+1} \circ d^i = 0$ por lo que es fácil notar que $latex C^{\bullet}(G,M)=(C^i(G,M),d^i)$ es un complejo de co-cadenas y entonces como $latex B^i(G,M)\leq Z^i(G,M)$ podemos definir el n-ésimo grupo de cohomología
$latex H^n(G,M)=Z^n(G,M)/B^n(G,M)$
Este grupo medirá qué tan alejado está un complejo de cadenas de ser exacto.
Una cosa importante en cohomología es que convierte una sucesión exacta corta de $latex G-$módulos en una sucesión exacta larga de grupos abelianos.
A nosotros nos interesa mucho $latex H^0(G,M)$ el cuál ya definimos y $latex H^1(G,M)$
Por lo que podemos ver que:
$latex H^0(G,M)=M^G$ es decir son los $latex G-$invariantes
ya que:
Si $latex m\in M$ entonces $latex d^0(m)(g)=gm-m$ por lo que $latex ker(d_0)=M^G$
También tenemos que
$latex Z^1(G,M)=\lbrace f:G\rightarrow M \mid f(gh)=gf(h)+f(g) \rbrace$
Esto es fácil de ver también directamente de la definición... otra cosa que hay que observar es que si la acción de $latex G$ es trivial entonces
$latex H^0(G,M)=M$ y $latex H^1(G,M)=Mor(G,M)$
lo cual también es evidente.
Espero les haya servido.
Eduardo Ruiz Duarte (beck)
twitter: @toorandom
Tuesday, September 02, 2014
A días de iniciar mi PhD en Países Bajos (aka Holanda)
Como algunos sabrán, apliqué en una universidad en los Países Bajos con el fin de poder hacer mi PhD en matemáticas, trabajaré con curvas hiperelípticas de género 2 con el fin de poder encontrar relaciones con números primos usando campos de funciones globales y locales de éstas.
Estaré muy metido con temas relacionados con puntos racionales de curvas algebraicas, tests de primalidad y algoritmos de factorización en primos cierto tipo de números con el fin de poder hacer algún avance en el área de criptografía asimétrica y criptoanálisis algebraico.
Todo esto es que mis herramientas principales (por ahora) vendrán de la geometría algebraica y álgebra conmutativa como son las curvas elípticas, análisis complejo, variedades abelianas, teoría de divisores, jacobianas, funciones Zeta, teorema de Hasse-Weil, Hasse-Minkowski, Mordell-Weil, teorías de Manin-Mumford entre otras que irán surgiendo.
Todo esto es impresionante y me causa mucho placer el investigarlo y comprenderlo, así como visualizarlo con programación, y más con el tutor que voy quién es muy respetado en el área, es algo que tengo que hacer... si no lo hago me arrepentiré por siempre y es algo que he querido hacer desde que tomé mi primera clase de teoría de números y cuando tuve mi primer acercamiento con números primos hace ya algunos años haciendo un programa que los detecta de manera visual, aquí está
Mi consejo para todos los lectores, es:
El statu quo económico y social así como la zona de confort son peligrosas, pero también cómodas, a veces vale la pena abandonarlas para perseguir algo más grande, ya que te puedes frustrar, pero también cuando logren un paso de su meta tampoco crean que será fácil, estoy nervioso, ansioso y un poco asustado, las metas son difíciles por definición, si no lo fueran, simplemente serían acciones cotidianas.
Lo que se tiene como meta, en mi caso es algo que no es fácil (al menos para mí)... no me considero un "genio" sólo alguien muy curioso y tengo que estudiar bastante para comprender lo que necesito, quiero lograrlo, sólo tengo que organizarme.
En el preámbulo de mi doctorado estuve en Budapest en el congreso de criptología de europa central hace un par de meses investigando un endomorfismo en la jacobiana de curvas hiperelípticas de género 2 y afortunadamente sí pude publicar algo y dar una charla y esto que haré considero será la continuación de ello, si a alguien le interesa el artículo está por aquí en la IACR .
Ahora, en la parte humana y cotidiana comienzo a darme cuenta de lo complicado que es psicológicamente el poder mudarme de país, yo tenía mi casa armada en una zona de confort interesante, mis relaciones humanas y amigos limitados a mi poca capacidad social, pero funcionales y con confianza existente, un trabajo estable, que tal vez no me llenaba del todo, pero sí me permitía poder seguir estudiando e investigando.
Materialmente es difícil, todas mis cosas tengo que regalarlas o mal venderlas, pero bueno, supongo que es un entrenamiento para no tener que aferrarme a lo material, y me alegro de lo que doné y regalé al mismo tiempo... ya que a mucha gente le servirá.
También comienza a caerme el veinte de toda la gente a la que ya no veré en mucho tiempo (cuatro años), de lo lejos que estaré, porque no me iré a Estados Unidos o Canadá, estaré a 12 horas de avión de un vuelo caro y aparte a otras 2 horas de tren desde Ámsterdam, en un pueblo de prácticamente estudiantes que se llama Groningen de 198 mil habitantes (imagina que la delegación Benito Juárez que es donde vivo actualmente tiene 385 mil personas) que está muy cerca de la frontera con Alemania al noreste de los Países Bajos.
Es decir, voy a hacer un cambio radical en la vida, en costumbres, dejo de trabajar para un magnate y comienzo a trabajar para mí, dejo a la gente de toda la vida, destruyo bienes materiales, pago deudas y me desfalco, me junto con amigos/as para despedirme, me hacen comidas/cenas de despedida, conozco gente nueva a la que me duele dejar... voy solo, no soy tan sociable, mis relaciones sociales en México han representado un gran logro, hay que volver a comenzar con otra cultura, otro idioma, otra economía y otras responsabilidades ya no será tan fácil obtener lo que quiero materialmente como lo era aquí en México, ahora soy un estudihambre.
Al ver lo que dejo y ver las calles, llenas de gente y atascadas de tránsito en el D.F. me doy cuenta... que sí voy a extrañar mucho de lo que critico, pero también me pregunto... ¿qué realmente es lo que hacemos los seres humanos aquí en el mundo? ¿acaso venimos a ser felices como todos dicen? ... no lo creo... creo que pensar que venimos a ser felices es muy egoísta, pero lo que sí sé es que aunque es egoísta lo hacemos casi todos y lo hago yo, por el hecho de no saber la respuesta... me sorprende ver a tanta gente caminando, tanta gente de la que no sé nada, ni ellos de mí pero con vidas tan complejas como la de cualquiera de nosotros, y me pregunto ¿acaso estoy haciendo las cosas bien?
Saludos
twitter: @toorandom
Eduardo Ruíz Duarte (beck)
Estaré muy metido con temas relacionados con puntos racionales de curvas algebraicas, tests de primalidad y algoritmos de factorización en primos cierto tipo de números con el fin de poder hacer algún avance en el área de criptografía asimétrica y criptoanálisis algebraico.
Todo esto es que mis herramientas principales (por ahora) vendrán de la geometría algebraica y álgebra conmutativa como son las curvas elípticas, análisis complejo, variedades abelianas, teoría de divisores, jacobianas, funciones Zeta, teorema de Hasse-Weil, Hasse-Minkowski, Mordell-Weil, teorías de Manin-Mumford entre otras que irán surgiendo.
Todo esto es impresionante y me causa mucho placer el investigarlo y comprenderlo, así como visualizarlo con programación, y más con el tutor que voy quién es muy respetado en el área, es algo que tengo que hacer... si no lo hago me arrepentiré por siempre y es algo que he querido hacer desde que tomé mi primera clase de teoría de números y cuando tuve mi primer acercamiento con números primos hace ya algunos años haciendo un programa que los detecta de manera visual, aquí está
Mi consejo para todos los lectores, es:
El statu quo económico y social así como la zona de confort son peligrosas, pero también cómodas, a veces vale la pena abandonarlas para perseguir algo más grande, ya que te puedes frustrar, pero también cuando logren un paso de su meta tampoco crean que será fácil, estoy nervioso, ansioso y un poco asustado, las metas son difíciles por definición, si no lo fueran, simplemente serían acciones cotidianas.
Lo que se tiene como meta, en mi caso es algo que no es fácil (al menos para mí)... no me considero un "genio" sólo alguien muy curioso y tengo que estudiar bastante para comprender lo que necesito, quiero lograrlo, sólo tengo que organizarme.
En el preámbulo de mi doctorado estuve en Budapest en el congreso de criptología de europa central hace un par de meses investigando un endomorfismo en la jacobiana de curvas hiperelípticas de género 2 y afortunadamente sí pude publicar algo y dar una charla y esto que haré considero será la continuación de ello, si a alguien le interesa el artículo está por aquí en la IACR .
Ahora, en la parte humana y cotidiana comienzo a darme cuenta de lo complicado que es psicológicamente el poder mudarme de país, yo tenía mi casa armada en una zona de confort interesante, mis relaciones humanas y amigos limitados a mi poca capacidad social, pero funcionales y con confianza existente, un trabajo estable, que tal vez no me llenaba del todo, pero sí me permitía poder seguir estudiando e investigando.
Materialmente es difícil, todas mis cosas tengo que regalarlas o mal venderlas, pero bueno, supongo que es un entrenamiento para no tener que aferrarme a lo material, y me alegro de lo que doné y regalé al mismo tiempo... ya que a mucha gente le servirá.
También comienza a caerme el veinte de toda la gente a la que ya no veré en mucho tiempo (cuatro años), de lo lejos que estaré, porque no me iré a Estados Unidos o Canadá, estaré a 12 horas de avión de un vuelo caro y aparte a otras 2 horas de tren desde Ámsterdam, en un pueblo de prácticamente estudiantes que se llama Groningen de 198 mil habitantes (imagina que la delegación Benito Juárez que es donde vivo actualmente tiene 385 mil personas) que está muy cerca de la frontera con Alemania al noreste de los Países Bajos.
Es decir, voy a hacer un cambio radical en la vida, en costumbres, dejo de trabajar para un magnate y comienzo a trabajar para mí, dejo a la gente de toda la vida, destruyo bienes materiales, pago deudas y me desfalco, me junto con amigos/as para despedirme, me hacen comidas/cenas de despedida, conozco gente nueva a la que me duele dejar... voy solo, no soy tan sociable, mis relaciones sociales en México han representado un gran logro, hay que volver a comenzar con otra cultura, otro idioma, otra economía y otras responsabilidades ya no será tan fácil obtener lo que quiero materialmente como lo era aquí en México, ahora soy un estudihambre.
Al ver lo que dejo y ver las calles, llenas de gente y atascadas de tránsito en el D.F. me doy cuenta... que sí voy a extrañar mucho de lo que critico, pero también me pregunto... ¿qué realmente es lo que hacemos los seres humanos aquí en el mundo? ¿acaso venimos a ser felices como todos dicen? ... no lo creo... creo que pensar que venimos a ser felices es muy egoísta, pero lo que sí sé es que aunque es egoísta lo hacemos casi todos y lo hago yo, por el hecho de no saber la respuesta... me sorprende ver a tanta gente caminando, tanta gente de la que no sé nada, ni ellos de mí pero con vidas tan complejas como la de cualquiera de nosotros, y me pregunto ¿acaso estoy haciendo las cosas bien?
Saludos
twitter: @toorandom
Eduardo Ruíz Duarte (beck)
Wednesday, July 23, 2014
Geometría p-ádica, completación de racionales y estructura de campo
¿Cómo podemos llegar a los números reales desde los números racionales?
Esta estructura es muy importante para estudiar muchos teoremas de geometría algebraica, y sirve como un ejemplo interesante ajeno a los campos usuales, todo estudiante de posgrado orientado a álgebra creo que debe conocerlos, aquí pongo una mini-introducción sólo para que te adentres más.
Tenemos que los números racionales son los cocientes de enteros, es decir:
$latex \mathbb{Q}=\Big \lbrace \frac{a}{b} : a,b\in\mathbb{Z}, b\neq 0 \Big \rbrace$
Ya sabemos como sumar y multiplicar fracciones, y sabemos que cada fracción tiene un inverso (excepto el 0) es decir, $latex (\mathbb{Q},+.\times)$ forma un campo.
Para entender los números p-ádicos necesitamos entender valores absolutos
Valores absolutos
Definición: Sea $latex \mathbb{K}$ un campo y $latex \mathbb{Q}_{+}=\big \lbrace x\in \mathbb{Q} : x\geq 0\big \rbrace$, entonces un valor absoluto en $latex \mathbb{K}$ es una función:
$latex \mid \cdot \mid:\mathbb{K}\rightarrow \mathbb{Q}_{+}$
Que satisface lo siguiente:
* $latex \mid x \mid = 0 \Leftrightarrow x=0$
* $latex \mid xy \mid = \mid x \mid \mid y \mid$
* $latex \mid x+y\mid \leq \mid x \mid + \mid y \mid$ (Desigualdad del triángulo)
Ejemplo usual:
Un valor absoluto para $latex \mathbb{Q}$ es:
$latex \mid \cdot \mid:\mathbb{Q}\rightarrow \mathbb{Q}_{+}$
$latex \mid x \mid =\begin{cases} \enspace x: & x\geq 0 \\ -x: & x < 0 \end{cases}$
Es fácil verificar que satisface las condiciones anteriores.
Ahora démosle más estructura al espacio, viendo cómo podemos comparar elementos.
Espacios Métricos
Decimos que una métrica es una función de distancia, es decir , si $latex \mathbb{X}$ es un conjunto entonces una métrica sobre $latex \mathbb{X}$ es una función:
$latex \delta:\mathbb{X}\times \mathbb{X} \rightarrow \mathbb{Q}_{+}$
Que satisface lo siguiente:
*$latex \delta(x,y)\geq 0$
*$latex \delta(x,y)=\delta(y,x)$
*$latex \delta(x,y)+\delta(y,z)\geq \delta(z,y)$ (desigualdad del triángulo)
Si se fijan hasta aquí, tenemos que si son observadores, $latex \mathbb{Q}$ forma un espacio métrico con la distancia usual , es decir:
$latex (\mathbb{Q},\mid \cdot \mid)$ es un espacio métrico , donde la métrica $latex \delta$ está definida usualmente como:
$latex \delta:\mathbb{Q}\times \mathbb{Q}\rightarrow \mathbb{Q}_{+}$
$latex \delta(x,y)=\mid x-y\mid$
Es decir la distancia que separa a los puntos $latex x,y\in \mathbb{Q}$
Para poder completar todos los huecos de $latex \mathbb{Q}$ necesitamos saber lo que son las sucesiones de Cauchy
Sucesiones de Cauchy
Una sucesión de Cauchy en un espacio métrico $latex \mathbb{X}$ es una sucesión de elementos $latex x_1,x_2,... \in \mathbb{X}$ de tal manera que cada uno de los elementos se van volviendo más cercanos conforme esta sucesión crece.
Es decir
$latex x_1,x_2,x_3,...$ es una sucesión de Cauchy si para todo número real positivo $latex \epsilon$ existe un entero $latex N$ de tal que para todos los números $latex n,m\in \mathbb{N}$ con $latex n,m > N$
$latex \delta(x_m,x_n)=\mid x_m -x_n\mid < \epsilon$
Esto quiere decir que siempre que se te ocurra cualquier real $latex \epsilon > 0$ por más chiquito que quieras, siempre podrás encontrar un índice $latex N$ donde todos los índices $latex n,m$ mayores que $latex N$ están a distancia menor que $latex \epsilon$
Puedes visualizarlo así... si se fijan los elementos $latex x_i$ se van juntando cada vez más y aunque escoja $latex \epsilon = \frac{1}{10^{100^{100}}}$ siempre sucederá que existe una $latex N$ que todos los elementos con índice mayor a $latex N$ están a distancia menor que $latex \epsilon$, entonces si una sucesión cumple esto, decimos que es de Cauchy, un ejemplo es $latex \Big \lbrace \frac{1}{n} \Big \rbrace_{n=1}^{\infty}$
$latex \mathbb{X}$
Ahora para juntar todo esto , veamos que es un espacio métrico completo.
Definición: Decimos que un espacio métrico $latex (\mathbb{X},d)$ es completo si toda sucesión de Cauchy en $latex (\mathbb{X},d)$ converge EN $latex \mathbb{X}$
Antiejemplos:
Es decir , por ejemplo si $latex \mathbb{X}=(0,1]$ vemos que la sucesión anterior $latex \Big \lbrace \frac{1}{n} \Big \rbrace_{n=1}^{\infty}$ converge a $latex 0\notin \mathbb{X}$ por lo que en este caso $latex \mathbb{X}$ no es completo.
Ahora... también tenemos que los números racionales con la métrica usual tampoco son completos es decir $latex (\mathbb{Q},\mid \cdot \mid)$
Es construir una sucesión de Cauchy en $latex \mathbb{Q}$ que no converja, por ejemplo.
$latex \Big \lbrace 3,3.1,3.14,3.141,3.1415,3.14159,3.14159295,...\Big \rbrace$
Esta claramente es una sucesión de números racionales que converge a $latex \pi \notin \mathbb{Q}$
Por lo que $latex \mathbb{Q}$ no es completo con la métrica usual
Ahora, Si un espacio no es completo, podemos completarlo agregando todos los límites de sucesiones de Cauchy de éste, y pueden probar que el completar un campo (en este caso $latex \mathbb{Q}$) el resultado les da otro campo (en este caso $latex \mathbb{R}$)
Resumen
Si quieres obtener $latex \mathbb{R}$ lo que necesitas es a $latex \mathbb{Q}$ , un valor absoluto en éste $latex \mid \cdot \mid$ , una métrica $latex \delta$ y todas las sucesiones de Cauchy en $latex \mathbb{Q}$ con respecto $latex \delta$
Otros Valores Absolutos (p-ádicos)
Hasta ahora todo esto es lo usual y aburrido, la función de valor absoluto ya la conocemos perfectamente, lo que queremos hacer es usar otras funciones de valor absoluto y ver cómo se comportan estos espacios bajo una nueva métrica.
Fijemos un número primo $latex p$ , definiremos un valor absoluto asociado a $latex p$ en $latex \mathbb{Q}$
Sea $latex \alpha \in \mathbb{Q}^{\times}$ entonces tenemos que existen $latex g,h$ primos relativos tal que:
$latex \alpha = p^{n}\frac{g}{h}$
Es decir, todo número racional podemos verlo como múltiplo de $latex p^n$ donde $latex p$ no divide a ninguno de los $latex g,h$ , es decir todos son primos relativos.
Esto es fácil observarlo y demostrarlo, ahora vemos ejemplos , pero definimos el valor absoluto p-ádico para $latex \alpha \in \mathbb{Q}^{\times}$ como:
$latex \mid \alpha \mid_{p}=\mid p^{n}\frac{g}{h}\mid_p = p^{-n}$
Este es un valor absoluto no trivial y cumple todas las reglas de valor absoluto que definimos anteriormente con las leyes de los exponentes, hay que definir $latex \mid 0 \mid_p=0$ y hay que notar que el conjunto de valores absolutos es discreto ya que cae en el conjunto $latex \lbrace p^n : n\in \mathbb{Z}\rbrace \cup \lbrace 0 \rbrace$
Ejemplo:
Consideremos $latex \alpha = \frac{140}{297}=2^{2}\cdot 5 \cdot 7 \cdot 3^{-3} \cdot 11^{-1}$
Entonces:
$latex \mid \alpha \mid_2 = \frac{1}{4}$
$latex \mid \alpha \mid_3 = 27$
Métrica p-ádica en $latex \mathbb{Q}$
Naturalmente tenemos que la métrica p-ádica en los racionales definida como
$latex \delta_p:\mathbb{Q}\times\mathbb{Q} \rightarrow \mathbb{Q}_{+}$
está definida como
$latex \delta_p(x,y)=\mid x-y\mid_p$
Ejemplo contraintuitivo
Aquí las cosas no son tan intuitivas porque podemos ver que por ejemplo si $latex p=7$ $latex 28814$ y $latex 2$ están más cercanos que $latex 3$ y $latex 2$ ya que
$latex \delta_7(28814,2)=\mid 28812\mid_7 = \mid 2^2\times 3 \times 7^4\mid_7 = 7^{-4}=\frac{1}{2401}$
$latex \delta_7(3,2)=\mid 1 \mid_7 = \mid 7^0 \mid_7 = 7^0 = 1$
como $latex 1 > \frac{1}{2401}$ tenemos que $latex 3$ está más alejado del $latex 2$ que $latex 28814$
Completación de $latex \mathbb{Q}$ con la métrica p-ádica
$latex \mathbb{Q}$ no es completo con respecto a esta métrica, veamos un ejemplo
si $latex p=5$
$latex \displaystyle \sum_{n=0}^{\infty}{ 5^n}$
No es un elemento de $latex \mathbb{Q}$ pero ...
la sucesión:
$latex \lbrace 1,1+5,1+5+5^2, 1+5+5^2+5^3,...\rbrace = \lbrace 1,6,31,156\rbrace$
Es una sucesión de Cauchy con la métrica 5-ádica , esta sucesión con la métrica usual NO converge, pero con la métrica 5-ádica sí, de hecho las distancias van siendo $latex 1,\frac{1}{2},\frac{1}{4},\frac{1}{8}...$ .
Entonces para cada primo $latex p$ hay una completación de $latex \mathbb{Q}$ con respecto a su métrica p-ádica asociada
Entonces como sabemos que la completación del campo $latex \mathbb{Q}$ también será un campo.
y este objeto le llamamos campo de los números p-ádicos y lo denotamos como:
$latex \mathbb{Q}_p$
para algún primo $latex p$.
Representación de los números p-ádicos
Tenemos que todo número $latex x\in \mathbb{Q}_p$ puede ser representado como la serie de potencias:
$latex x_{-m}p^{-m}+x_{-m+1}p^{-m+1}+...+x_0+x_1p+x_2p^2+x_3p^3+...$
Esta representación es única cuando $latex x_i \in \mathbb{Z}/p\mathbb{Z}$ es decir , si $latex x_i$ está módulo $latex p$
La colección de las $latex \lbrace x_i \rbrace$ son los dígitos p-ádicos y la notación para escribirlos es de izquierda a derecha
$latex ...x_{3}x_{2}x_{1}x_{0} . x_{-1}x_{-2}...x_{-m+1}x_{-m}$
Geometría de $latex \mathbb{Q}_p$
Para finalizar vamos a ver cómo se ven las bolas de radio $latex r$ con centro en $latex a$ en $latex \mathbb{Q}_p$
es decir , queremos analizar estos objetos:
$latex B(a,r) = \lbrace x\in \mathbb{Q}_p : \mid a-x\mid_p < r\rbrace$
Como $latex r\in \lbrace p^n : n\in \mathbb{Z}$ si $latex p=3$ en $latex \mathbb{Q}_3$
Donde el círculo más grande tiene $latex r=1$ y los 3 circulitos que siguen tienen $latex r=1/3$ y así $latex r=1/3^n$
Pero si ponemos un microscopio, lo que veremos es:
Esta estructura es muy importante para estudiar muchos teoremas de geometría algebraica, y sirve como un ejemplo interesante ajeno a los campos usuales, todo estudiante de posgrado orientado a álgebra creo que debe conocerlos, aquí pongo una mini-introducción sólo para que te adentres más.
Tenemos que los números racionales son los cocientes de enteros, es decir:
$latex \mathbb{Q}=\Big \lbrace \frac{a}{b} : a,b\in\mathbb{Z}, b\neq 0 \Big \rbrace$
Ya sabemos como sumar y multiplicar fracciones, y sabemos que cada fracción tiene un inverso (excepto el 0) es decir, $latex (\mathbb{Q},+.\times)$ forma un campo.
Para entender los números p-ádicos necesitamos entender valores absolutos
Valores absolutos
Definición: Sea $latex \mathbb{K}$ un campo y $latex \mathbb{Q}_{+}=\big \lbrace x\in \mathbb{Q} : x\geq 0\big \rbrace$, entonces un valor absoluto en $latex \mathbb{K}$ es una función:
$latex \mid \cdot \mid:\mathbb{K}\rightarrow \mathbb{Q}_{+}$
Que satisface lo siguiente:
* $latex \mid x \mid = 0 \Leftrightarrow x=0$
* $latex \mid xy \mid = \mid x \mid \mid y \mid$
* $latex \mid x+y\mid \leq \mid x \mid + \mid y \mid$ (Desigualdad del triángulo)
Ejemplo usual:
Un valor absoluto para $latex \mathbb{Q}$ es:
$latex \mid \cdot \mid:\mathbb{Q}\rightarrow \mathbb{Q}_{+}$
$latex \mid x \mid =\begin{cases} \enspace x: & x\geq 0 \\ -x: & x < 0 \end{cases}$
Es fácil verificar que satisface las condiciones anteriores.
Ahora démosle más estructura al espacio, viendo cómo podemos comparar elementos.
Espacios Métricos
Decimos que una métrica es una función de distancia, es decir , si $latex \mathbb{X}$ es un conjunto entonces una métrica sobre $latex \mathbb{X}$ es una función:
$latex \delta:\mathbb{X}\times \mathbb{X} \rightarrow \mathbb{Q}_{+}$
Que satisface lo siguiente:
*$latex \delta(x,y)\geq 0$
*$latex \delta(x,y)=\delta(y,x)$
*$latex \delta(x,y)+\delta(y,z)\geq \delta(z,y)$ (desigualdad del triángulo)
Si se fijan hasta aquí, tenemos que si son observadores, $latex \mathbb{Q}$ forma un espacio métrico con la distancia usual , es decir:
$latex (\mathbb{Q},\mid \cdot \mid)$ es un espacio métrico , donde la métrica $latex \delta$ está definida usualmente como:
$latex \delta:\mathbb{Q}\times \mathbb{Q}\rightarrow \mathbb{Q}_{+}$
$latex \delta(x,y)=\mid x-y\mid$
Es decir la distancia que separa a los puntos $latex x,y\in \mathbb{Q}$
Para poder completar todos los huecos de $latex \mathbb{Q}$ necesitamos saber lo que son las sucesiones de Cauchy
Sucesiones de Cauchy
Una sucesión de Cauchy en un espacio métrico $latex \mathbb{X}$ es una sucesión de elementos $latex x_1,x_2,... \in \mathbb{X}$ de tal manera que cada uno de los elementos se van volviendo más cercanos conforme esta sucesión crece.
Es decir
$latex x_1,x_2,x_3,...$ es una sucesión de Cauchy si para todo número real positivo $latex \epsilon$ existe un entero $latex N$ de tal que para todos los números $latex n,m\in \mathbb{N}$ con $latex n,m > N$
$latex \delta(x_m,x_n)=\mid x_m -x_n\mid < \epsilon$
Esto quiere decir que siempre que se te ocurra cualquier real $latex \epsilon > 0$ por más chiquito que quieras, siempre podrás encontrar un índice $latex N$ donde todos los índices $latex n,m$ mayores que $latex N$ están a distancia menor que $latex \epsilon$
Puedes visualizarlo así... si se fijan los elementos $latex x_i$ se van juntando cada vez más y aunque escoja $latex \epsilon = \frac{1}{10^{100^{100}}}$ siempre sucederá que existe una $latex N$ que todos los elementos con índice mayor a $latex N$ están a distancia menor que $latex \epsilon$, entonces si una sucesión cumple esto, decimos que es de Cauchy, un ejemplo es $latex \Big \lbrace \frac{1}{n} \Big \rbrace_{n=1}^{\infty}$
$latex \mathbb{X}$
Ahora para juntar todo esto , veamos que es un espacio métrico completo.
Definición: Decimos que un espacio métrico $latex (\mathbb{X},d)$ es completo si toda sucesión de Cauchy en $latex (\mathbb{X},d)$ converge EN $latex \mathbb{X}$
Antiejemplos:
Es decir , por ejemplo si $latex \mathbb{X}=(0,1]$ vemos que la sucesión anterior $latex \Big \lbrace \frac{1}{n} \Big \rbrace_{n=1}^{\infty}$ converge a $latex 0\notin \mathbb{X}$ por lo que en este caso $latex \mathbb{X}$ no es completo.
Ahora... también tenemos que los números racionales con la métrica usual tampoco son completos es decir $latex (\mathbb{Q},\mid \cdot \mid)$
Es construir una sucesión de Cauchy en $latex \mathbb{Q}$ que no converja, por ejemplo.
$latex \Big \lbrace 3,3.1,3.14,3.141,3.1415,3.14159,3.14159295,...\Big \rbrace$
Esta claramente es una sucesión de números racionales que converge a $latex \pi \notin \mathbb{Q}$
Por lo que $latex \mathbb{Q}$ no es completo con la métrica usual
Ahora, Si un espacio no es completo, podemos completarlo agregando todos los límites de sucesiones de Cauchy de éste, y pueden probar que el completar un campo (en este caso $latex \mathbb{Q}$) el resultado les da otro campo (en este caso $latex \mathbb{R}$)
Resumen
Si quieres obtener $latex \mathbb{R}$ lo que necesitas es a $latex \mathbb{Q}$ , un valor absoluto en éste $latex \mid \cdot \mid$ , una métrica $latex \delta$ y todas las sucesiones de Cauchy en $latex \mathbb{Q}$ con respecto $latex \delta$
Otros Valores Absolutos (p-ádicos)
Hasta ahora todo esto es lo usual y aburrido, la función de valor absoluto ya la conocemos perfectamente, lo que queremos hacer es usar otras funciones de valor absoluto y ver cómo se comportan estos espacios bajo una nueva métrica.
Fijemos un número primo $latex p$ , definiremos un valor absoluto asociado a $latex p$ en $latex \mathbb{Q}$
Sea $latex \alpha \in \mathbb{Q}^{\times}$ entonces tenemos que existen $latex g,h$ primos relativos tal que:
$latex \alpha = p^{n}\frac{g}{h}$
Es decir, todo número racional podemos verlo como múltiplo de $latex p^n$ donde $latex p$ no divide a ninguno de los $latex g,h$ , es decir todos son primos relativos.
Esto es fácil observarlo y demostrarlo, ahora vemos ejemplos , pero definimos el valor absoluto p-ádico para $latex \alpha \in \mathbb{Q}^{\times}$ como:
$latex \mid \alpha \mid_{p}=\mid p^{n}\frac{g}{h}\mid_p = p^{-n}$
Este es un valor absoluto no trivial y cumple todas las reglas de valor absoluto que definimos anteriormente con las leyes de los exponentes, hay que definir $latex \mid 0 \mid_p=0$ y hay que notar que el conjunto de valores absolutos es discreto ya que cae en el conjunto $latex \lbrace p^n : n\in \mathbb{Z}\rbrace \cup \lbrace 0 \rbrace$
Ejemplo:
Consideremos $latex \alpha = \frac{140}{297}=2^{2}\cdot 5 \cdot 7 \cdot 3^{-3} \cdot 11^{-1}$
Entonces:
$latex \mid \alpha \mid_2 = \frac{1}{4}$
$latex \mid \alpha \mid_3 = 27$
$latex \mid \alpha \mid_5 = \frac{1}{5}$
$latex \mid \alpha \mid_7 = \frac{1}{7}$
$latex \mid \alpha \mid_{11} = 11$
$latex \mid \alpha \mid_{13} = 1$
Métrica p-ádica en $latex \mathbb{Q}$
Naturalmente tenemos que la métrica p-ádica en los racionales definida como
$latex \delta_p:\mathbb{Q}\times\mathbb{Q} \rightarrow \mathbb{Q}_{+}$
está definida como
$latex \delta_p(x,y)=\mid x-y\mid_p$
Ejemplo contraintuitivo
Aquí las cosas no son tan intuitivas porque podemos ver que por ejemplo si $latex p=7$ $latex 28814$ y $latex 2$ están más cercanos que $latex 3$ y $latex 2$ ya que
$latex \delta_7(28814,2)=\mid 28812\mid_7 = \mid 2^2\times 3 \times 7^4\mid_7 = 7^{-4}=\frac{1}{2401}$
$latex \delta_7(3,2)=\mid 1 \mid_7 = \mid 7^0 \mid_7 = 7^0 = 1$
como $latex 1 > \frac{1}{2401}$ tenemos que $latex 3$ está más alejado del $latex 2$ que $latex 28814$
Completación de $latex \mathbb{Q}$ con la métrica p-ádica
$latex \mathbb{Q}$ no es completo con respecto a esta métrica, veamos un ejemplo
si $latex p=5$
$latex \displaystyle \sum_{n=0}^{\infty}{ 5^n}$
No es un elemento de $latex \mathbb{Q}$ pero ...
la sucesión:
$latex \lbrace 1,1+5,1+5+5^2, 1+5+5^2+5^3,...\rbrace = \lbrace 1,6,31,156\rbrace$
Es una sucesión de Cauchy con la métrica 5-ádica , esta sucesión con la métrica usual NO converge, pero con la métrica 5-ádica sí, de hecho las distancias van siendo $latex 1,\frac{1}{2},\frac{1}{4},\frac{1}{8}...$ .
Entonces para cada primo $latex p$ hay una completación de $latex \mathbb{Q}$ con respecto a su métrica p-ádica asociada
Entonces como sabemos que la completación del campo $latex \mathbb{Q}$ también será un campo.
y este objeto le llamamos campo de los números p-ádicos y lo denotamos como:
$latex \mathbb{Q}_p$
para algún primo $latex p$.
Representación de los números p-ádicos
Tenemos que todo número $latex x\in \mathbb{Q}_p$ puede ser representado como la serie de potencias:
$latex x_{-m}p^{-m}+x_{-m+1}p^{-m+1}+...+x_0+x_1p+x_2p^2+x_3p^3+...$
Esta representación es única cuando $latex x_i \in \mathbb{Z}/p\mathbb{Z}$ es decir , si $latex x_i$ está módulo $latex p$
La colección de las $latex \lbrace x_i \rbrace$ son los dígitos p-ádicos y la notación para escribirlos es de izquierda a derecha
$latex ...x_{3}x_{2}x_{1}x_{0} . x_{-1}x_{-2}...x_{-m+1}x_{-m}$
Geometría de $latex \mathbb{Q}_p$
Para finalizar vamos a ver cómo se ven las bolas de radio $latex r$ con centro en $latex a$ en $latex \mathbb{Q}_p$
es decir , queremos analizar estos objetos:
$latex B(a,r) = \lbrace x\in \mathbb{Q}_p : \mid a-x\mid_p < r\rbrace$
Como $latex r\in \lbrace p^n : n\in \mathbb{Z}$ si $latex p=3$ en $latex \mathbb{Q}_3$
Donde el círculo más grande tiene $latex r=1$ y los 3 circulitos que siguen tienen $latex r=1/3$ y así $latex r=1/3^n$
Pero si ponemos un microscopio, lo que veremos es:
que es como un arbol ternario.
Espero les haya servido, estos aparte de ser divertidos son bellos, ahora podríamos hablar en el futuro a detalle de topología con esto.
Eduardo Ruíz Duarte (beck)
twitter: @toorandom
Wednesday, July 16, 2014
Teoremas de incompletud de Gödel (Bases, explicación y definiciones)
Gödel fue un gran matemático, murió de inanición después de que su esposa muriera quien le cocinaba y probaba su comida antes que él. Gödel tenía un grado de paranoia excesiva por envenenamiento, él trabajó con Albert Einstein y descubrió soluciones paradójicas en ecuaciones de relatividad especial. Por esto, es que supongo que su paranoia podría ser producto de haber estado involucrado indirectamente en la bomba atómica, no lo sé. En mi opinión Gödel, es el lógico más importante en toda la historia, descubrió (¿inventó?) un resultado muy fuera de lo estándar, que en mi opinión es muy profundo y en mi perspectiva toca los límites entre la matemática y la filosofía analítica. Esto le hizo ganarse su doctorado con una tésis de doce páginas "Über die Vollständigkeit der Axiome des logischen
Funktionenkalkül" por la universidad de Viena (click aquí).
En general, gracias a él tenemos fundamentos para poder demostrar la veracidad de alguna proposición en matemáticas dadas las reglas del juego (axiomas). Es decir él practicamente fundó la teoría metamátematica que gobierna a las matemáticas como las conocemos.
De los tres resultados más importantes que Gödel obtuvo por ahí de 1930, el que más ha sido objeto de curiosidad, es sólamente el teorema de incompletud. el más profundo. En mi opinión, este resultado no está bien entendido por las personas que "creen entenderlo", yo caía en este subconjunto hace algunos años, hasta que decidí estudiarlo formalmente
De hecho hay dos teoremas de incompletud y en general cuando la gente habla de el "teorema de incompletud" casi siempre se refiere al primero de estos.
Nosotros hoy profundizaremos en esto y en las definiciones que nos llevarán a comprenderlo un poco. Espero ser bastante explícito.
Para ser más formal omitiré el uso de algunos símbolos en matemáticas para no confundir el lenguaje formal que es importante en esto; es decir omitiré la teoría de conjuntos como usualmente la usamos y trataré de expresar todo con la menor cantidad de símbolos.
El teorema de incompletud de Gödel, es como el principio de incertidumbre de Heisenberg, en general se piensa que "existen límites absolutos relacionados con lo que puede ser sabido y medido sobre un fenómeno". Análogamente se dice que los teoremas de Gödel nos dicen que existen verdades matemáticas que jamás podrán ser probadas.
Esto nos lleva a filosofías postmodernistas a veces, y a ideas que apoyan el escepticismo sobre lo que es la verdad... "Nada puede ser completamente sabido realmente"
Un ejemplo absurdo de esto anterior es que existe un libro extraño llamado "Bibliografía el cristianismo y las matemáticas" (sí es en serio) donde se puede ver un ejemplo donde los religiosos usan como herramienta principal el teorema de Gödel para afirmar que si en matemáticas hay cosas que no se pueden demostrar e infieren que también las hay en la religión. Les encanta el teorema de incompletud ya que "implica" la existencia de dios, ya que él es el único que puede decidir todas las verdades.
Por cierto, también podría interesarles una entrada anterior en mi blog donde Gödel construye un sistema axiomático "mínimo" necesario para que se pueda demostrar la existencia de dios, aquí se las dejo. La intenté demostrar con las palabras más sencillas y contiene una mini introducción a lógica modal.
Empecemos un poco ya con estos teoremas de Gödel. No me considero experto en muchas cosas, incluido esto... así que si notan un error, me harán un gran favor al corregirme.
El primer teorema de incompletud de Gödel de manera burda y débil dice lo siguiente, después lo puliremos:
Teorema 1 de incompletud débil: (Kurt Gödel)
Ejemplo de enunciado que no se puede demostrar en la teoría de conjuntos (hipótesis del continuo)
Está demostrado que no se puede demostrar que no existe un cardinal infinito "intermedio" entre $latex \aleph_0$ y $latex 2^{\aleph_0}$
Es decir no se puede demostrar que no existe un conjunto infinito estrictamente más grande que $latex \mathbb{N}$ (los números naturales, enteros positivos) y estrictamente más chico que $latex \mathbb{R}$ (todos los números reales, es decir enteros, cocientes de enteros e irracionales como $latex \pi,e,\phi$ et cétera...).
Si no te queda claro esta idea no-intuitiva de que hay infinitos más grandes que otros, imagina que no existe una función que pueda relacionar biyectivamente a los números naturales con los números reales los cuales son muchos más.
Si te interesa profundizar más en esto puedes ver un post anterior aquí sobre los infinitos, cardinalidad, axioma de elección y axiomas de ZF (Zermelo-Fraenkel).
Vamos a tratar de comprender el teorema de Gödel versión débil a través de definiciones y ejemplos, comencemos...
Lenguajes formales.
Necesitamos entender lo que es un sistema formal, pero para ello, primero necesitamos saber lo que es un lenguaje formal $latex \mathbb{L}$. Para esto necesitamos definir una lista de símbolos, y definir qué secuencias de símbolos son expresiones válidas en el lenguaje $latex \mathbb{L}$ .
Ahora, cuando se habla de aritmética, significa "lo que podemos hacer con los números". Es decir, no sólo lo que te enseñan en el kinder sobre los números, sino más bien en términos de teoría de números.
En el lenguaje formal de la aritmética $latex \mathbb{L}$ tenemos un símbolo para el $latex 1$, también para sumar $latex +$, multiplicar $latex \times$. Más aún, tenemos letras $latex x,y$ que actúan como variables, así como símbolos de igualdad $latex =$ y relaciones de orden como "menor que" < o "mayor que" >.
Menos frecuente, también tenemos partículas lógicas como "Y" $latex (\wedge)$ , "O" $latex (\vee)$, "implica" $latex (\Rightarrow)$, "NO" $latex (\neg)$ y "sí y sólo si" $latex (\Leftrightarrow)$.
También hay cuantificadores como: "para todo $latex n$" $latex (\forall n)$ así como "existe una $latex n$" $latex (\exists n)$.
También habrán paréntesis para evitar ambiguedad en las expresiones, por ejemplo, ya definido nuestro lenguaje, usémoslo para decir algo.
$latex 1< m\wedge \neg(\exists n)(\exists k)(1<n<m \wedge n\times k=m)$
En español:
"$latex m$ es un número mayor que $latex 1$ y no hay $latex n$ ni $latex k$ con $latex n$ menor que $latex m$ cumpliendo que $latex m=n\times k$"
Eso que acabamos de definir es un número primo $latex m$ (un número entero positivo que no tiene factores mayores que $latex 1$), por ejemplo el $latex 7,19,101$ o $latex 31337$.
Ahora, esos símbolos que nos denotan lo que es un número primo, en el lenguaje de la aritmética podemos llamarlo fórmula. Estas fórmulas nos van a servir como un test lógico, que en este caso es una fórmula en función de $latex m$, llamémosla $latex P(m)$. Esta fórmula nos da como resultados "verdadero" o "falso" dependiendo si $latex m$ es primo o no.
Como sabrán... los números primos son muy importantes en la aritmética. Hace 2300 años, Euclides en su libro Elementos probó que que los números primos son infinitos. Esto en nuestro lenguaje formal se puede decir así:
$latex \forall n \exists m (n< m \wedge P(m))$
En español es:
"Para todo número $latex n$ existe un $latex m$ tal que $latex m$ es más grande que $latex n$ y $latex P(m)$ es verdadero (es decir m cumple la fórmula de definición de número primo)".
Más chafa sería que para todo número $latex n$ que se te ocurra, el que sea... siempre podrás encontrar un número más grande que éste que sea primo.
¿Ven el poder de los lenguajes formales? , podemos decir mucho con pocos símbolos.
Otro ejemplo para que quede claro es el concepto de primo gemelo, los cuales son los números naturales $latex n$ tal que $latex n+2$ también es primo. Nadie sabe si existen una infinidad de estos ya que no hay una manera de construirlos. Ejemplos de estos son el $latex 3$ (ya que el $latex 5$ también es primo), incluso el $latex 5$ (porque el $latex 7$ también es primo), pero el $latex 7$ no funciona ya que $latex 7+2=9=3^2$ pero el $latex 11$ sí lo es porque el $latex 13$ es primo.
Si sí existen una infinidad de números primos gemelos, diríamos en nuestro lenguaje, la formula:
$latex \forall n\exists m (n< m \wedge P(m) \wedge P(m+2))$
Es verdadera.
Es decir... para todo $latex n$ que se nos ocurra podemos encontrar un número $latex m$ mayor que $latex n$ que es un primo gemelo.
Esa expresión en el lenguaje de la aritmética NADIE sabe si es verdadera... así como la conjetura fuerte de Goldbach (La débil ya fue resuelta por Helfgott hace unos meses).
Conjetura (Goldbach):
Todo número par mayor que 4 es la suma de 2 números primos impares
Si demostramos algún día la conjetura de Goldbach podremos decir que en $latex \mathbb{L}$ existe el siguiente objeto:
$latex \forall n>4\wedge n=2k (\exists a>2\wedge P(a))(\exists b>2\wedge P(b))(n=a+b)$
Mucho de esto se ataca con el lenguaje de los números complejos que usas en cálculo y análisis como por ejemplo la conjetura de Riemann.
Sistema formal
Ya tienes tu lenguaje formal $latex \mathbb{L}$. Ahora vamos a definir un sistema formal $latex \mathbb S$ en $latex \mathbb{L}$. Esto es definiendo qué proposiciones $latex \mathcal{A}$ de $latex \mathbb{L}$ son axiomas, y qué relaciones entre las proposiciones son reglas de inferencia..
Aquí dije en negritas dos conceptos, "axiomas" y "reglas de inferencia", procedo s definirlos.
Un axioma lo entendemos como una proposición verdadera por sí misma en $latex \mathbb{L}$, y de ésta inferir otras proposiciones. Es decir, son como los bloques de nuestro sistema, no se pueden demostrar y de éstas lograremos construir otras proposiciones. Algunos dicen que son fórmulas del lenguaje $latex \mathbb{L}$ que son evidentes pero yo no coincido NADA con eso. La palabra "evidente" aquí es muy ambigua. Por ejemplo, busca los axiomas de la geometría y demuestra que no se puede deducir uno de otro... no es tan evidente.
Es decir , una proposición que se puede deducir de axiomas NO es un axioma, el axioma es lo más elemental y que todo lo del sistema debe de cumplir. Por ejemplo en $latex \mathbb{L}$, un axioma es $latex x < y\wedge y< z \Rightarrow x < z$.
Una inferencia es lo que hacemos diario para poder relacionar dos situaciones y saber si son equivalentes o no. En nuestro caso, si tenemos dos proposiciones $latex \mathcal{A},\mathcal{B}$ del lenguaje $latex \mathbb{L}$, las reglas de inferencia nos permitirán trazar una linea lógica entre $latex \mathcal{A}$ y $latex \mathcal{B}$, y así saber si son equivalentes o alguna implica la otra. Es decir, si $latex \mathcal{A}\Rightarrow \mathcal{B}$ o $latex \mathcal{B}\Rightarrow \mathcal{A}$ o $latex \mathcal{A} \Leftrightarrow \mathcal{B}$ como ejemplo:
(Lo decapitarán $latex \Rightarrow$ Morirá)
pero... también tenemos que:
$latex \neg$(Morirá $latex \Rightarrow$ Lo decapitarán)
Es decir , si te decapitan es verdadero que vas a morir, pero NO siempre sucede que si vas a morir (todos vamos a morir) es porque te van a decapitar. El cómo estamos pensando esto desde el sentido de la naturaleza humana es lo que es una regla de inferencia.
Más aún. tenemos como axioma en la vida que los seres humanos son finitos cronológicamente. Entonces, podemos con base en eso definir una proposición, una equivalencia.
naces $latex \Leftrightarrow$ mueres
Es decir, si naces mueres, y si mueres es porque naciste,
Entonces, en un sistema formal debemos definir los axiomas en el lenguaje $latex \mathbb{L}$ y nuestras reglas de inferencia para poder encontrar relaciones entre las fórmulas/proposiciones de $latex \mathbb{L}$. Se pide también que se pueda computar si una proposición es un axioma o una combinación de implicaciones lógicas deducidas de las reglas de inferencias que vienen de los axiomas.
Ahora, una demostración en $latex \mathbb{S}$ es una sucesión finita de proposiciones, que cada una de éstas es un axioma o una proposición obtenida de axiomas anteriores conectadas lógicamente por reglas de inferencia. Te puedes imaginar una "gráfica" (o grafo), donde cada vértice es una proposición o teorema de cierto sistema axiomático. Las aristas (dirigidas) entre dos vértices existirán si existe una relación lógica (implicación) entre ellas obtenida con las reglas de inferencia (el razonamiento básico estipulado en tu sistema formal).
Decimos que una proposición $latex \mathcal A$ es demostrable en $latex \mathbb{S}$ si existe una demostración en $latex \mathbb{S}$ que termina en $latex \mathcal{A}$.
Ahora, también decimos que $latex \mathbb{S}$ es consistente si no hay proposiciones $latex \mathcal{A}$ en $latex \mathbb{L}$ tal que ambas $latex \mathcal{A}$ y $latex \neg \mathcal{A}$ son demostrables en $latex \mathbb{S}$.
Decimos que $latex \mathbb{S}$ es formalmente completo para $latex \mathbb{L}$, si toda proposición $latex \mathcal{A}$ de $latex \mathbb{L}$ se puede demostrar siempre $latex \mathcal{A}$ o $latex \neg \mathcal{A}$ (sólo una de ellas!).
Gödel diría esto equivalentemente en su tesis como:
$latex \mathbb{S}$ es formalmente completo si toda proposición de $latex \mathbb{L}$ es decidible en $latex \mathbb{S}$.
Si $latex \mathbb{S}$ no es completo entonces decimos que existen $latex \mathbb{L}$-proposiciones indecidibles en $latex \mathbb{S}$.
Ahora, decimos que el sistema $latex \mathbb{S}$ es verdadero completo para $latex \mathbb{L}$ si toda proposición verdadera de $latex \mathbb{L}$ es demostrable en $latex \mathbb{S}$ .
Es decir si $latex \mathbb{S}$ es consistente (es decir que puedes demostrar la proposición $latex \matcal{A}$ o su negación (sólo una)) y también es verdadero completo para $latex \mathbb{L}$, entonces es formalmente completo. Esto es ya que toda proposición $latex \mathcal{A}$ de $latex \mathbb{L}$ es o verdadera o falsa (si es falsa, tenemos que su negación es verdadera, por lo que existirá ésta en $latex \mathbb{L}$).
Pero $latex \mathbb{S}$ podría ser consistente y formalmente completo pero no necesariamente verdadero completo.
Con estos conceptos, ya podemos entender lo que dice el primer teorema de Gödel, excepto por un detalle.
Recordemos lo que dice el primer teorema de Gödel sin pulir y débil, ya pronto enunciaremos el teorema como él mismo lo pensó.
Teorema débil: (Kurt Gödel), Recapitulando
No sabemos exactamente qué significa "suficientemente fuerte"
El decir que un sistema formal es suficientemente fuerte, significa que incluye el sistema PA, es decir la aritmética de Peano. Éste PA, son reglas sobre la adición, multiplicación, igualdad y relación de orden (menor que). Pero más allá de eso, los axiomas de Peano conllevan a algo más fuerte que es lo que se pide en "suficientemente fuerte", esto es el principio de inducción matemática en $latex \mathbb{S}$. Expresado en $latex \mathbb{L}$, dice lo siguiente para un proposición $latex \mathcal{P}$ en $latex \mathbb{L}$:
$latex \mathcal{P}(1)\wedge (\forall n)(\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)) \Rightarrow (\forall n)\mathcal{P}(n)$
Esta fórmula de $latex \mathbb{L}$ en español dice:
Si $latex 1$ cumple la propiedad $latex \mathcal{P}$, Y si todos los $latex n$ tienen la propiedad $latex \mathcal{P}$ (es decir $latex \mathcal{P}(n)$ es verdadero) e implican que $latex n+1$ también tiene la propiedad $latex \mathcal{P}$, entonces podemos concluir que todos los números tienen la propiedad $latex \mathcal{P}$.
Esto en teoría de números es muy importante ya que nos permite definir un razonamiento para demostrar una infinidad de proposiciones, es decir que dependan de un parámetro $latex n$ que es una variable que toma una infinidad de valores enteros.
Es decir, los matemáticos no nos vamos a poner a demostrar caso por caso porque da flojera y porque es imposible demostrar una infinidad de casos. La propiedad inductiva en los números naturales nos dice que podemos usar una especie de efecto dominó en las propiedades de los números naturales, permitiéndonos poder generalizar la veracidad de un resultado. Eso de manera informal es el principio de inducción y es lo que Gödel pide en que exista en $latex \mathbb{S}$ para ser considerado éste suficientemente fuerte. En otras palabras, que el sistema formal contenga la aritmética de Peano la cual trae consigo el principio de inducción.
Los axiomas de Peano son explícitamente estas 5 reglas que con éstas son suficientes para construir toda la aritmética (de hecho la más importante es la función sucesor de un número natural que construye la suma y de ahí todo lo demás en la aritmética:
Axiomas de Peano (de wikipedia)
a) El 1 es un número natural.1 está en $latex \mathbb{N}$, el conjunto de los números naturales.
b) Todo número natural n tiene un sucesor n* (este axioma es usado para definir posteriormente la suma).
c) El 1 no es el sucesor de algún número natural.
d) Si hay dos números naturales n y m con el mismo sucesor, entonces n y m son el mismo número natural.
e) Si el 1 pertenece a un conjunto K de n naturales, y dado un elemento cualquiera k, el sucesor k* también pertenece al conjunto K, entonces todos los números naturales pertenecen a ese conjunto K. Este último axioma es el principio de inducción matemática.
Aquí está ya el teorema después de todo el background que hemos visto:
Primer teorema de incompetud de Gödel:
Si $latex \mathbb{S}$ es un sistema formal tal que:
i) El lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ contiene el lenguaje de la aritmética
ii) $latex \mathbb{S}$ incluye los axiomas de Peano
iii) $latex \mathbb{S}$ es consistente
Entonces existe una proposición $latex \mathcal{A}$ en $latex \mathbb{L}$ que es verdadera pero no puede ser demostrada en $latex \mathbb{S}$
La demostración es complicada pero a grosso modo, a cada símbolo del lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ le asoció un número natural. Adicionalmente a cada expresión $latex \mathcal{E}$ de $latex \mathbb{L}$ usando los números asociados a sus símbolos le asoció el número natural obtenido de la concatenación de los símbolos que componen $latex \mathcal{E}$, cada uno separado por cero. Él usa el 0 porque no usa ése dígito al asociar naturales a su lenguaje formal $latex \mathbb{L}$.
A estos números les llamamos números de Gödel para la expresión $latex \mathcal{E}$.
Ahora, como las fórmulas en $latex \mathbb{L}$ son sucesiones finitas por definición, los números de Gödel están bien definidos, y cada expresión de $latex \mathbb{L}$ tiene un número de Gödel.
Las demostraciones en $latex \mathbb{S}$ serán sucesiones finitas de proposiciones conectadas por una implicación, por lo que a éstas demostraciones también se les puede asociar un número de Gödel, (concatenación de los números de Gödel de cada proposición con un 0 separándolas), entonces él definió la siguiente propiedad:
n es el número de Gödel de una demostración $latex \mathcal{A}$ en $latex \mathbb{S}$
como:
$latex \Delta_{\mathbb{S}}(n,\mathcal{A})$
La cual es expresada en el lenguaje de la aritmética $latex \mathbb{L}$ como la proposición
$latex (\exists n) \Delta_{\mathbb{S}}(n,\mathcal{A})$
la cual escribimos como fórmula:
$latex \Lambda_{\mathbb{S}}(\mathcal{A})$
Ésta nos dice que $latex \mathcal{A}$ es demostrable de $latex \mathbb{S}$ o sea que si es verdadera es demostrable en la aritmética de Peano, y si $latex \mathcal{A}$ no es demostrable en $latex \mathbb{S}$ escribimos $latex \neg \Lambda_{\mathbb{S}}(\mathcal{A})$ (la cual será verdadera).
Finalmente , Gödel usó una adaptación de lo que se le llama el método de la diagonal para construir una proposición específica (una cadena de números), llámale $latex \mathcal{D}$ tal que los axiomas de Peano demuestran
$latex \mathcal{D} \Leftrightarrow \neg \Lambda_{\mathbb{S}}(\mathcal{D})$
Es decir que hay un número de Gödel sin demostración asociada.
Ésta $latex \mathcal{D}$ es construida con base en una proposición que es autoreferenciada. Con más tiempo en el futuro lo compartiré aquí con detalle.
Gödel culmina demostrando que:
* Si $latex \mathbb{S}$ es consistente entonces $latex \mathcal{D}$ es no demostrable con $latex \mathbb{S}$
Y eso termina la demostración del teorema.
Para terminar este post les dejo el segundo teorema de incompletud
Segundo teorema de incompetud de Gödel:
Si $latex \mathbb{S}$ es un sistema formal tal que:
i) El lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ contiene el lenguaje de la aritmética
ii) $latex \mathbb{S}$ incluye los axiomas de Peano
iii) $latex \mathbb{S}$ es consistente
Entonces la consistencia de $latex \mathbb{S}$ y $latex \Lambda_{\mathbb{S}}(\mathcal{A}\wedge \neg \mathcal{A})$ es NO demostrable en $latex \mathbb{S}$
En general, gracias a él tenemos fundamentos para poder demostrar la veracidad de alguna proposición en matemáticas dadas las reglas del juego (axiomas). Es decir él practicamente fundó la teoría metamátematica que gobierna a las matemáticas como las conocemos.
De los tres resultados más importantes que Gödel obtuvo por ahí de 1930, el que más ha sido objeto de curiosidad, es sólamente el teorema de incompletud. el más profundo. En mi opinión, este resultado no está bien entendido por las personas que "creen entenderlo", yo caía en este subconjunto hace algunos años, hasta que decidí estudiarlo formalmente
De hecho hay dos teoremas de incompletud y en general cuando la gente habla de el "teorema de incompletud" casi siempre se refiere al primero de estos.
Nosotros hoy profundizaremos en esto y en las definiciones que nos llevarán a comprenderlo un poco. Espero ser bastante explícito.
Para ser más formal omitiré el uso de algunos símbolos en matemáticas para no confundir el lenguaje formal que es importante en esto; es decir omitiré la teoría de conjuntos como usualmente la usamos y trataré de expresar todo con la menor cantidad de símbolos.
El teorema de incompletud de Gödel, es como el principio de incertidumbre de Heisenberg, en general se piensa que "existen límites absolutos relacionados con lo que puede ser sabido y medido sobre un fenómeno". Análogamente se dice que los teoremas de Gödel nos dicen que existen verdades matemáticas que jamás podrán ser probadas.
Esto nos lleva a filosofías postmodernistas a veces, y a ideas que apoyan el escepticismo sobre lo que es la verdad... "Nada puede ser completamente sabido realmente"
Un ejemplo absurdo de esto anterior es que existe un libro extraño llamado "Bibliografía el cristianismo y las matemáticas" (sí es en serio) donde se puede ver un ejemplo donde los religiosos usan como herramienta principal el teorema de Gödel para afirmar que si en matemáticas hay cosas que no se pueden demostrar e infieren que también las hay en la religión. Les encanta el teorema de incompletud ya que "implica" la existencia de dios, ya que él es el único que puede decidir todas las verdades.
Por cierto, también podría interesarles una entrada anterior en mi blog donde Gödel construye un sistema axiomático "mínimo" necesario para que se pueda demostrar la existencia de dios, aquí se las dejo. La intenté demostrar con las palabras más sencillas y contiene una mini introducción a lógica modal.
Empecemos un poco ya con estos teoremas de Gödel. No me considero experto en muchas cosas, incluido esto... así que si notan un error, me harán un gran favor al corregirme.
El primer teorema de incompletud de Gödel de manera burda y débil dice lo siguiente, después lo puliremos:
Teorema 1 de incompletud débil: (Kurt Gödel)
En un sistema formal suficientemente fuerte existen proposiciones aritméticas verdaderas que no pueden ser demostradas dentro de ese sistema
Ejemplo de enunciado que no se puede demostrar en la teoría de conjuntos (hipótesis del continuo)
Está demostrado que no se puede demostrar que no existe un cardinal infinito "intermedio" entre $latex \aleph_0$ y $latex 2^{\aleph_0}$
Es decir no se puede demostrar que no existe un conjunto infinito estrictamente más grande que $latex \mathbb{N}$ (los números naturales, enteros positivos) y estrictamente más chico que $latex \mathbb{R}$ (todos los números reales, es decir enteros, cocientes de enteros e irracionales como $latex \pi,e,\phi$ et cétera...).
Si no te queda claro esta idea no-intuitiva de que hay infinitos más grandes que otros, imagina que no existe una función que pueda relacionar biyectivamente a los números naturales con los números reales los cuales son muchos más.
Si te interesa profundizar más en esto puedes ver un post anterior aquí sobre los infinitos, cardinalidad, axioma de elección y axiomas de ZF (Zermelo-Fraenkel).
Vamos a tratar de comprender el teorema de Gödel versión débil a través de definiciones y ejemplos, comencemos...
Lenguajes formales.
Necesitamos entender lo que es un sistema formal, pero para ello, primero necesitamos saber lo que es un lenguaje formal $latex \mathbb{L}$. Para esto necesitamos definir una lista de símbolos, y definir qué secuencias de símbolos son expresiones válidas en el lenguaje $latex \mathbb{L}$ .
Ahora, cuando se habla de aritmética, significa "lo que podemos hacer con los números". Es decir, no sólo lo que te enseñan en el kinder sobre los números, sino más bien en términos de teoría de números.
En el lenguaje formal de la aritmética $latex \mathbb{L}$ tenemos un símbolo para el $latex 1$, también para sumar $latex +$, multiplicar $latex \times$. Más aún, tenemos letras $latex x,y$ que actúan como variables, así como símbolos de igualdad $latex =$ y relaciones de orden como "menor que" < o "mayor que" >.
Menos frecuente, también tenemos partículas lógicas como "Y" $latex (\wedge)$ , "O" $latex (\vee)$, "implica" $latex (\Rightarrow)$, "NO" $latex (\neg)$ y "sí y sólo si" $latex (\Leftrightarrow)$.
También hay cuantificadores como: "para todo $latex n$" $latex (\forall n)$ así como "existe una $latex n$" $latex (\exists n)$.
También habrán paréntesis para evitar ambiguedad en las expresiones, por ejemplo, ya definido nuestro lenguaje, usémoslo para decir algo.
$latex 1< m\wedge \neg(\exists n)(\exists k)(1<n<m \wedge n\times k=m)$
En español:
"$latex m$ es un número mayor que $latex 1$ y no hay $latex n$ ni $latex k$ con $latex n$ menor que $latex m$ cumpliendo que $latex m=n\times k$"
Eso que acabamos de definir es un número primo $latex m$ (un número entero positivo que no tiene factores mayores que $latex 1$), por ejemplo el $latex 7,19,101$ o $latex 31337$.
Ahora, esos símbolos que nos denotan lo que es un número primo, en el lenguaje de la aritmética podemos llamarlo fórmula. Estas fórmulas nos van a servir como un test lógico, que en este caso es una fórmula en función de $latex m$, llamémosla $latex P(m)$. Esta fórmula nos da como resultados "verdadero" o "falso" dependiendo si $latex m$ es primo o no.
Como sabrán... los números primos son muy importantes en la aritmética. Hace 2300 años, Euclides en su libro Elementos probó que que los números primos son infinitos. Esto en nuestro lenguaje formal se puede decir así:
$latex \forall n \exists m (n< m \wedge P(m))$
En español es:
"Para todo número $latex n$ existe un $latex m$ tal que $latex m$ es más grande que $latex n$ y $latex P(m)$ es verdadero (es decir m cumple la fórmula de definición de número primo)".
Más chafa sería que para todo número $latex n$ que se te ocurra, el que sea... siempre podrás encontrar un número más grande que éste que sea primo.
¿Ven el poder de los lenguajes formales? , podemos decir mucho con pocos símbolos.
Otro ejemplo para que quede claro es el concepto de primo gemelo, los cuales son los números naturales $latex n$ tal que $latex n+2$ también es primo. Nadie sabe si existen una infinidad de estos ya que no hay una manera de construirlos. Ejemplos de estos son el $latex 3$ (ya que el $latex 5$ también es primo), incluso el $latex 5$ (porque el $latex 7$ también es primo), pero el $latex 7$ no funciona ya que $latex 7+2=9=3^2$ pero el $latex 11$ sí lo es porque el $latex 13$ es primo.
Si sí existen una infinidad de números primos gemelos, diríamos en nuestro lenguaje, la formula:
$latex \forall n\exists m (n< m \wedge P(m) \wedge P(m+2))$
Es verdadera.
Es decir... para todo $latex n$ que se nos ocurra podemos encontrar un número $latex m$ mayor que $latex n$ que es un primo gemelo.
Esa expresión en el lenguaje de la aritmética NADIE sabe si es verdadera... así como la conjetura fuerte de Goldbach (La débil ya fue resuelta por Helfgott hace unos meses).
Conjetura (Goldbach):
Todo número par mayor que 4 es la suma de 2 números primos impares
Si demostramos algún día la conjetura de Goldbach podremos decir que en $latex \mathbb{L}$ existe el siguiente objeto:
$latex \forall n>4\wedge n=2k (\exists a>2\wedge P(a))(\exists b>2\wedge P(b))(n=a+b)$
Mucho de esto se ataca con el lenguaje de los números complejos que usas en cálculo y análisis como por ejemplo la conjetura de Riemann.
Sistema formal
Ya tienes tu lenguaje formal $latex \mathbb{L}$. Ahora vamos a definir un sistema formal $latex \mathbb S$ en $latex \mathbb{L}$. Esto es definiendo qué proposiciones $latex \mathcal{A}$ de $latex \mathbb{L}$ son axiomas, y qué relaciones entre las proposiciones son reglas de inferencia..
Aquí dije en negritas dos conceptos, "axiomas" y "reglas de inferencia", procedo s definirlos.
Un axioma lo entendemos como una proposición verdadera por sí misma en $latex \mathbb{L}$, y de ésta inferir otras proposiciones. Es decir, son como los bloques de nuestro sistema, no se pueden demostrar y de éstas lograremos construir otras proposiciones. Algunos dicen que son fórmulas del lenguaje $latex \mathbb{L}$ que son evidentes pero yo no coincido NADA con eso. La palabra "evidente" aquí es muy ambigua. Por ejemplo, busca los axiomas de la geometría y demuestra que no se puede deducir uno de otro... no es tan evidente.
Es decir , una proposición que se puede deducir de axiomas NO es un axioma, el axioma es lo más elemental y que todo lo del sistema debe de cumplir. Por ejemplo en $latex \mathbb{L}$, un axioma es $latex x < y\wedge y< z \Rightarrow x < z$.
Una inferencia es lo que hacemos diario para poder relacionar dos situaciones y saber si son equivalentes o no. En nuestro caso, si tenemos dos proposiciones $latex \mathcal{A},\mathcal{B}$ del lenguaje $latex \mathbb{L}$, las reglas de inferencia nos permitirán trazar una linea lógica entre $latex \mathcal{A}$ y $latex \mathcal{B}$, y así saber si son equivalentes o alguna implica la otra. Es decir, si $latex \mathcal{A}\Rightarrow \mathcal{B}$ o $latex \mathcal{B}\Rightarrow \mathcal{A}$ o $latex \mathcal{A} \Leftrightarrow \mathcal{B}$ como ejemplo:
(Lo decapitarán $latex \Rightarrow$ Morirá)
pero... también tenemos que:
$latex \neg$(Morirá $latex \Rightarrow$ Lo decapitarán)
Es decir , si te decapitan es verdadero que vas a morir, pero NO siempre sucede que si vas a morir (todos vamos a morir) es porque te van a decapitar. El cómo estamos pensando esto desde el sentido de la naturaleza humana es lo que es una regla de inferencia.
Más aún. tenemos como axioma en la vida que los seres humanos son finitos cronológicamente. Entonces, podemos con base en eso definir una proposición, una equivalencia.
naces $latex \Leftrightarrow$ mueres
Es decir, si naces mueres, y si mueres es porque naciste,
Entonces, en un sistema formal debemos definir los axiomas en el lenguaje $latex \mathbb{L}$ y nuestras reglas de inferencia para poder encontrar relaciones entre las fórmulas/proposiciones de $latex \mathbb{L}$. Se pide también que se pueda computar si una proposición es un axioma o una combinación de implicaciones lógicas deducidas de las reglas de inferencias que vienen de los axiomas.
Ahora, una demostración en $latex \mathbb{S}$ es una sucesión finita de proposiciones, que cada una de éstas es un axioma o una proposición obtenida de axiomas anteriores conectadas lógicamente por reglas de inferencia. Te puedes imaginar una "gráfica" (o grafo), donde cada vértice es una proposición o teorema de cierto sistema axiomático. Las aristas (dirigidas) entre dos vértices existirán si existe una relación lógica (implicación) entre ellas obtenida con las reglas de inferencia (el razonamiento básico estipulado en tu sistema formal).
Decimos que una proposición $latex \mathcal A$ es demostrable en $latex \mathbb{S}$ si existe una demostración en $latex \mathbb{S}$ que termina en $latex \mathcal{A}$.
Ahora, también decimos que $latex \mathbb{S}$ es consistente si no hay proposiciones $latex \mathcal{A}$ en $latex \mathbb{L}$ tal que ambas $latex \mathcal{A}$ y $latex \neg \mathcal{A}$ son demostrables en $latex \mathbb{S}$.
Decimos que $latex \mathbb{S}$ es formalmente completo para $latex \mathbb{L}$, si toda proposición $latex \mathcal{A}$ de $latex \mathbb{L}$ se puede demostrar siempre $latex \mathcal{A}$ o $latex \neg \mathcal{A}$ (sólo una de ellas!).
Gödel diría esto equivalentemente en su tesis como:
$latex \mathbb{S}$ es formalmente completo si toda proposición de $latex \mathbb{L}$ es decidible en $latex \mathbb{S}$.
Si $latex \mathbb{S}$ no es completo entonces decimos que existen $latex \mathbb{L}$-proposiciones indecidibles en $latex \mathbb{S}$.
Ahora, decimos que el sistema $latex \mathbb{S}$ es verdadero completo para $latex \mathbb{L}$ si toda proposición verdadera de $latex \mathbb{L}$ es demostrable en $latex \mathbb{S}$ .
Es decir si $latex \mathbb{S}$ es consistente (es decir que puedes demostrar la proposición $latex \matcal{A}$ o su negación (sólo una)) y también es verdadero completo para $latex \mathbb{L}$, entonces es formalmente completo. Esto es ya que toda proposición $latex \mathcal{A}$ de $latex \mathbb{L}$ es o verdadera o falsa (si es falsa, tenemos que su negación es verdadera, por lo que existirá ésta en $latex \mathbb{L}$).
Pero $latex \mathbb{S}$ podría ser consistente y formalmente completo pero no necesariamente verdadero completo.
Con estos conceptos, ya podemos entender lo que dice el primer teorema de Gödel, excepto por un detalle.
Recordemos lo que dice el primer teorema de Gödel sin pulir y débil, ya pronto enunciaremos el teorema como él mismo lo pensó.
Teorema débil: (Kurt Gödel), Recapitulando
En un sistema formal suficientemente fuerte existen proposiciones aritméticas verdaderas que no pueden ser demostradas dentro de ese sistema
No sabemos exactamente qué significa "suficientemente fuerte"
El decir que un sistema formal es suficientemente fuerte, significa que incluye el sistema PA, es decir la aritmética de Peano. Éste PA, son reglas sobre la adición, multiplicación, igualdad y relación de orden (menor que). Pero más allá de eso, los axiomas de Peano conllevan a algo más fuerte que es lo que se pide en "suficientemente fuerte", esto es el principio de inducción matemática en $latex \mathbb{S}$. Expresado en $latex \mathbb{L}$, dice lo siguiente para un proposición $latex \mathcal{P}$ en $latex \mathbb{L}$:
$latex \mathcal{P}(1)\wedge (\forall n)(\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)) \Rightarrow (\forall n)\mathcal{P}(n)$
Esta fórmula de $latex \mathbb{L}$ en español dice:
Si $latex 1$ cumple la propiedad $latex \mathcal{P}$, Y si todos los $latex n$ tienen la propiedad $latex \mathcal{P}$ (es decir $latex \mathcal{P}(n)$ es verdadero) e implican que $latex n+1$ también tiene la propiedad $latex \mathcal{P}$, entonces podemos concluir que todos los números tienen la propiedad $latex \mathcal{P}$.
Esto en teoría de números es muy importante ya que nos permite definir un razonamiento para demostrar una infinidad de proposiciones, es decir que dependan de un parámetro $latex n$ que es una variable que toma una infinidad de valores enteros.
Es decir, los matemáticos no nos vamos a poner a demostrar caso por caso porque da flojera y porque es imposible demostrar una infinidad de casos. La propiedad inductiva en los números naturales nos dice que podemos usar una especie de efecto dominó en las propiedades de los números naturales, permitiéndonos poder generalizar la veracidad de un resultado. Eso de manera informal es el principio de inducción y es lo que Gödel pide en que exista en $latex \mathbb{S}$ para ser considerado éste suficientemente fuerte. En otras palabras, que el sistema formal contenga la aritmética de Peano la cual trae consigo el principio de inducción.
Los axiomas de Peano son explícitamente estas 5 reglas que con éstas son suficientes para construir toda la aritmética (de hecho la más importante es la función sucesor de un número natural que construye la suma y de ahí todo lo demás en la aritmética:
Axiomas de Peano (de wikipedia)
a) El 1 es un número natural.1 está en $latex \mathbb{N}$, el conjunto de los números naturales.
b) Todo número natural n tiene un sucesor n* (este axioma es usado para definir posteriormente la suma).
c) El 1 no es el sucesor de algún número natural.
d) Si hay dos números naturales n y m con el mismo sucesor, entonces n y m son el mismo número natural.
e) Si el 1 pertenece a un conjunto K de n naturales, y dado un elemento cualquiera k, el sucesor k* también pertenece al conjunto K, entonces todos los números naturales pertenecen a ese conjunto K. Este último axioma es el principio de inducción matemática.
Aquí está ya el teorema después de todo el background que hemos visto:
Primer teorema de incompetud de Gödel:
Si $latex \mathbb{S}$ es un sistema formal tal que:
i) El lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ contiene el lenguaje de la aritmética
ii) $latex \mathbb{S}$ incluye los axiomas de Peano
iii) $latex \mathbb{S}$ es consistente
Entonces existe una proposición $latex \mathcal{A}$ en $latex \mathbb{L}$ que es verdadera pero no puede ser demostrada en $latex \mathbb{S}$
La demostración es complicada pero a grosso modo, a cada símbolo del lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ le asoció un número natural. Adicionalmente a cada expresión $latex \mathcal{E}$ de $latex \mathbb{L}$ usando los números asociados a sus símbolos le asoció el número natural obtenido de la concatenación de los símbolos que componen $latex \mathcal{E}$, cada uno separado por cero. Él usa el 0 porque no usa ése dígito al asociar naturales a su lenguaje formal $latex \mathbb{L}$.
A estos números les llamamos números de Gödel para la expresión $latex \mathcal{E}$.
Ahora, como las fórmulas en $latex \mathbb{L}$ son sucesiones finitas por definición, los números de Gödel están bien definidos, y cada expresión de $latex \mathbb{L}$ tiene un número de Gödel.
Las demostraciones en $latex \mathbb{S}$ serán sucesiones finitas de proposiciones conectadas por una implicación, por lo que a éstas demostraciones también se les puede asociar un número de Gödel, (concatenación de los números de Gödel de cada proposición con un 0 separándolas), entonces él definió la siguiente propiedad:
n es el número de Gödel de una demostración $latex \mathcal{A}$ en $latex \mathbb{S}$
como:
$latex \Delta_{\mathbb{S}}(n,\mathcal{A})$
La cual es expresada en el lenguaje de la aritmética $latex \mathbb{L}$ como la proposición
$latex (\exists n) \Delta_{\mathbb{S}}(n,\mathcal{A})$
la cual escribimos como fórmula:
$latex \Lambda_{\mathbb{S}}(\mathcal{A})$
Ésta nos dice que $latex \mathcal{A}$ es demostrable de $latex \mathbb{S}$ o sea que si es verdadera es demostrable en la aritmética de Peano, y si $latex \mathcal{A}$ no es demostrable en $latex \mathbb{S}$ escribimos $latex \neg \Lambda_{\mathbb{S}}(\mathcal{A})$ (la cual será verdadera).
Finalmente , Gödel usó una adaptación de lo que se le llama el método de la diagonal para construir una proposición específica (una cadena de números), llámale $latex \mathcal{D}$ tal que los axiomas de Peano demuestran
$latex \mathcal{D} \Leftrightarrow \neg \Lambda_{\mathbb{S}}(\mathcal{D})$
Es decir que hay un número de Gödel sin demostración asociada.
Ésta $latex \mathcal{D}$ es construida con base en una proposición que es autoreferenciada. Con más tiempo en el futuro lo compartiré aquí con detalle.
Gödel culmina demostrando que:
* Si $latex \mathbb{S}$ es consistente entonces $latex \mathcal{D}$ es no demostrable con $latex \mathbb{S}$
Y eso termina la demostración del teorema.
Para terminar este post les dejo el segundo teorema de incompletud
Segundo teorema de incompetud de Gödel:
Si $latex \mathbb{S}$ es un sistema formal tal que:
i) El lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ contiene el lenguaje de la aritmética
ii) $latex \mathbb{S}$ incluye los axiomas de Peano
iii) $latex \mathbb{S}$ es consistente
Entonces la consistencia de $latex \mathbb{S}$ y $latex \Lambda_{\mathbb{S}}(\mathcal{A}\wedge \neg \mathcal{A})$ es NO demostrable en $latex \mathbb{S}$
No profundizaré ahora en esta parte, tal vez en otro post que requiere más maquinaria.
Espero les haya servido de algo, este teorema es de los grandes descubrientos en los artefactos que gobiernan a las matemáticas
Kurt Friedrich Gödel, Abril 28, 1906 - Enero 14, 1978
Eduardo Ruiz Duarte (beck)
twitter: @toorandom
Tuesday, July 08, 2014
Grupos de trenzas
Si estás desde un smartphone haz click aquí para que se vea mejor.
http://b3ck.blogspot.mx/2014/07/grupos-de-trenzas.html?m=0
Vamos a introducir una noción de Artin que generaliza de cierta forma el grupo simétrico $latex S_n$ de permutaciones, los grupos de trenzas son interesantes porque también tienen una noción geométrica intuitiva que nos va a llevar a su presentación algebraica, el grupo de trenzas de orden $latex n$ será denotado por $latex B_n$ (la $latex B$ es por braid), pero vamos a empezar al revés... daremos una noción intuitiva, un ejemplo y al final daremos la definición formal y veremos que hay usos que se le pueden dar en criptografía.
Lo que vamos a estudiar son configuraciones de "hebras" (hilos) que se ven de esta forma, y ver cómo hacerlas interactuar unas con otras para generar una estructura algebraica que como dijimos anteriormente, generaliza al grupo de permutaciones $latex S_n$ también definido por Emil Artin
Imaginemos que tenemos $latex n=4$ hilos, donde los extremos de cada uno de los 4 hilos están fijos con unos clavos, todas las configuraciones que podamos hacer con 4 hilos que no hagan nudos serán elementos de $latex B_4$ veamos a qué me refiero con esto.
Por ejemplo:
es diferente a 
Noten la diferencia de las hebras en cuanto a cuál pasa por encima de la otra.
También podemos ver que dibujándolas, las podemos hacer tan complejas como sean, pero al final siempre habrá una manera de dibujarlas de manera simple, es donde entra la abstracción del concepto ya que por ejemplo:
es lo mismo que
Y no se valen cosas como estos nudos:
Pero ¿por qué le llamamos grupo? , es decir, sabemos que un grupo es una estructura algebraica la cual contiene objetos que pueden interactuar con una operación binaria dando como resultado otros objetos de la misma estructura (cerradura), existe un objeto que es neutro, es decir que deja invariante a todos los elementos bajo la operación binaria y cada uno de los elementos tiene un inverso con esa operación que al usar la operación binaria entre inversos te da como resultado el neutro y es asociativo (como los números enteros bajo la suma)
$latex B_n$ no será abeliano para $latex n>2$ es decir sus elementos no conmutarán, veamos cómo funciona esta operación de $latex B_4$
La manera en la que vamos a sumar dos trenzas $latex \sigma \oplus \tau = \omega \in B_4$ veámosla con un par de ejemplos
$latex \bigoplus$
$latex =$ 
Observen como se hace la suma, que es "siguiendo" la trayectoria de las hebras en $latex \sigma$ , fijense como se cruzan unas con otras, pero bueno este ejemplo es muy intuitivo, algo un poco más interesante que servirá para que demuestren qué sucede con $latex B_2$ es el siguiente.
$latex \bigoplus$ 
$latex =$
Como pueden ver este ejemplo es menos trivial, pueden ver que las dos hebras de arriba se desenrredan
pero las dos de abajo una pasa por encima de otra, y al seguir la trayectoria con $latex \sigma_2$ vemos que pasa por abajo y se hace una trenza en $latex \sigma_3$
Con este ejemplo es fácil ver que $latex B_n$ es infinito con $latex n>1$ ya que las trenzas se pueden enredar cuantas veces quieras, y también se puede ver que $latex B_4$ no es abeliano ya que puedes experimentar un poco con estos ejemplos y verás que te dan elementos diferentes a $latex \omega$ o a $latex \sigma_3$
Pero bueno... ya basta , vamos a representar la infinidad de elementos de $latex B_4$ , para eso es el álgebra no? , no nos da miedo que sean infinitos.
Para poder construir explícitamente la estructura de $latex B_4$ primero tenemos que observar cuáles son las trenzas básicas que nos servirán para representar TODOS los elementos de $latex B_4$ , es decir , de quién son combinaciones.
Consideremos
 |  |  |
Todas las trenzas en $latex B_4$ pueden escribirse como composición de estas trenzas y sus inversos, o sea que si $latex \sigma\in B_4$ entonces su inverso $latex \sigma^{-1}$ será el elemento tal que $latex \sigma\oplus \sigma^{-1}=0$ donde 0 es la trenza que no tiene cruces, es decir todas las hebras son paralelas.
Para ver que cada trenza $latex \tau \in B_4$ es combinación de $latex \sigma_1,\sigma_2,\sigma_3$ y sus inversos, toma una trenza $latex \tau$ arbitraria y comienza a examinar de izquierda a derecha los cruces comenzando de la hebra de hasta arriba, cada que encuentres un cruce de las hebras $latex i$ y $latex i+1$ escribe $latex \sigma_i$ si la hebra $latex i$ pasa por arriba de $latex i+1$ o $latex \sigma_i^{-1}$ si pasa por abajo, y así vas escribiendo todo como la suma de éstos con $latex \oplus$
cuando termines de examinar cada hebra hasta el clavo final de la parte derecha, habrás construido la combinación de estas $latex \sigma_i$'s , y es intuitivo ya que estos generadores son los cruces fundamentales.
Si observas puedes ver que:
-
- (i) $latex \sigma_1\oplus\sigma_3=\sigma_3\oplus\sigma_1$
-
- (ii) $latex \sigma_1\oplus \sigma_2\oplus \sigma_1= \sigma_2\oplus \sigma_1\oplus \sigma_2$
- (ii) $latex \sigma_2\oplus \sigma_3\oplus \sigma_2= \sigma_3\oplus \sigma_2\oplus \sigma_3$
Y si no te percataste es fácil que lo veas con una hoja de papel.
Por lo que ya tenemos cómo es $latex B_4$ pero estas identidades se pueden extender en general para $latex B_n$
por lo que:
$latex B_n :=$ < $latex \sigma_1, \sigma_2,...,\sigma_n \mid \sigma_i \oplus \sigma_{i+1}\oplus \sigma_i = \sigma_{i+1}\oplus \sigma_i \oplus \sigma_{i+1}$ con $latex 1\leq i \leq n-2$ , $latex \sigma_i\oplus \sigma_j = \sigma_j \oplus \sigma_i$ con $latex \mid i-j \mid \geq 2$ >
Este grupo ha sido estudiado para criptografía , por David Garber http://arxiv.org/pdf/0711.3941.pdf
Pero desafortunadamente fue roto hace unos años, pero la teoría no deja de ser interesante, ya que se le puede asociar el grupo fundamental (Topología algebraica) de ciertos espacios, y encontrar de quién es el grupo fundamental es lo interesante.
También es interesante investigar cómo $latex B_3$ está relacionado al grupo especial lineal $latex SL(2,\mathbb{Z})$
Y como pendiente queda el grupo de trenzas con 2 hebras $latex B_2$ , pero pues... éste está generado por 2 elementos que son uno inverso de otro, es decir por 1 elemento... que es la trenza simple con dos hebras.... por lo que sólo se pueden generar trenzas con 2,3,4,... vueltas, pero también las puedes deshacer con su inversa , es decir
$latex B_2 \cong$ < $latex \mathbb{Z},+$> = < $latex1,-1$ >
Este es el único grupo de trenzas no trivial que es abeliano y como pueden ver no tiene mucho chiste.
Espero que les haya gustado, las imágenes las saqué de wikipedia y del artículo de David Garber antes mencionado.
Eduardo Ruíz Duarte
Twitter: @toorandom
Subscribe to:
Posts (Atom)