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$
$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)
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" < "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 =$   
        $latex \sigma$                                                   $latex \tau$                                    $latex \omega$



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 =$
        $latex \sigma_1$                                                   $latex \sigma_2$                                    $latex \sigma_3$

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

   Braid s1.png      Braid s2.png      Braid s3.png   
$latex \sigma_1$
$latex \sigma_2$
$latex \sigma_3$



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