Mostrar Mensajes

Esta sección te permite ver todos los posts escritos por este usuario. Ten en cuenta que sólo puedes ver los posts escritos en zonas a las que tienes acceso en este momento.

Temas - geómetracat

Páginas: [1]
1
Hola,

Hace tiempo le prometí a manooooh hacer un hilo hablando un poco sobre demostraciones asistidas por ordenador. Últimamente estoy bastante mal de tiempo, así que no me he podido mirar todo lo que hubiera querido estas cosas,
Pero a cambio, traigo algo mucho mejor que lo que hubiera podido escribir: un enlace al "natural number game":
http://wwwf.imperial.ac.uk/~buzzard/xena/natural_number_game/.
Esto es esencialmente un tutorial del lenguaje de programación Lean, estructurado en forma de juego. El objetivo es, comenzando con los axiomas de Peano de los números naturales, demostrar teoremas básicos para la suma, multiplicación, potencia y desigualdades de naturales (por ejemplo, que la suma y el producto de naturales son asociativas y conmutativas, etc). Esto no es muy distinto de lo que uno puede encontrar en un libro de lógica, pero es instructivo (y divertido) demostrar estas cosas usando un lenguaje de programación.

Este juego se enmarca en el llamado proyecto Xena (https://xenaproject.wordpress.com/), dirigido por Kevin Buzzard del Imperial College, que se dedica a formalizar matemáticas en Lean. La formalización de matemáticas es un campo que últimamente parece estar en auge, y donde se han conseguido recientemente cosas bastante impresionantes (por ejemplo, una formalización del forcing y la prueba de la independencia de la hipótesis del continuo).

El juego todavía no está en su versión final. Dentro de unos días o semanas probablemente habrá bastantes más "pantallas", incluyendo "mundos" sobre funciones y lógica proposicional (cuidado: estos lenguajes de programación no están basados en lógica proposicional o de primer orden sino en teorías de tipos dependientes, lo que hace que algunas cosas sean un poco raras si solamente se está acostumbrado a la lógica "usual"). Pero con lo que hay de momento se puede tener una idea de cómo funcionan estas cosas.

Espero que os guste tanto como me ha gustado a mí.

2
Hola,

Hace una semana apareció un preprint donde el matemático H. Huang da una demostración de la conjetura de la sensibilidad (sensitivity conjecture). Este era uno de los problemas abiertos más importantes en la teoría de complejidad computacional (más concretamente, en complejidad de funciones booleanas), y llevaba abierta 30 años.

Esta conjetura es equivalente al siguiente problema de teoría de grafos. Definimos el grafo \( Q_n \) como aquél que sus vértices son todas las sucesiones de longitud \( n \) formadas por ceros y unos (por tanto tiene \( 2^n \) vértices) y dos vértices están unidos por una arista si sus sucesiones de ceros y unos asociadas difieren exactamente en un número. A \( Q_n \) se le suele llamar el grafo hipercubo, porque sus vértices y aristas se corresponen con los vértices y aristas de un hipercubo de dimensión \( n \). Por ejemplo, en la imagen se ven \( Q_1,Q_2,Q_3 \):



Lo que ha demostrado Huang es que si tomamos un subgrafo \( H \) inducido con \( 2^{n-1}+1 \) vértices (esto es, el subgrafo de \( Q_n \) formado por los \( 2^{n-1}+1 \) vértices elegidos y todas las aristas que unen esos vértices en \( Q_n \)), entonces existe algún vértice de H del que salen por lo menos \( \sqrt{n} \) aristas (a otros vértices de \( H \)). Está claro que con un subgrafo de \( 2^{n-1} \) aristas no basta, pues el subgrafo con vértices \( (10 \dots 0), (01 \dots 0), \dots (00 \dots 1) \) tiene \( 2^{n-1} \) vértices pero ninguna arista.

Esto no sería demasiado destacable (al fin y al cabo prácticamente todos los días se resuelven conjeturas, aunque quizás no tan importantes ni que lleven tanto tiempo abiertas) si no fuera por cómo es la prueba.
Normalmente, cuando alguien demuestra una conjetura famosa, a la que le han intentado echar mano muchos expertos en el campo, la demostración suele ser compleja, técnica, larga y difícil de entender para alguien que no esté familiarizado con el campo.
Lo realmente remarcable en este caso es que el paper con la demostración ocupa 6 páginas, la demostración en sí (incluyendo lemas) ocupa página y media, y usa técnicas completamente elementales. Cualquiera que haya cursado álgebra lineal y sepa qué es un vector propio de una matriz puede leer y entender la prueba.

Esto hace plantearse cuántas demostraciones elementales de resultados importantes se les habrán pasado a los expertos y están ahí esperando a que alguien las descubra,

PD: Añado el link al artículo, que se me olvidó. https://arxiv.org/pdf/1907.00847.pdf

4
Lógica / Teorías aritméticas como interpretaciones de AP
« en: 29 Agosto, 2017, 01:51 pm »
Hola,

En el apartado 3.4 del libro de lógica matemática de Carlos Ivorra se da la definición de teoría axiomática y se demuestra que las teorías axiomáticas son las que interpretan a AP. En la demostración de este hecho se afirma que es fácil ver que si \( T \) es una teoría aritmética entonces \( \vdash_T \bigwedge mn \in \mathbb{N} (m+n \in \mathbb{N}) \)  y esto se demuestra por inducción en \( T \).

No consigo ver cómo se demuestra esto en \( T \).  Me gustaría aplicar el principio de inducción a la fórmula \( \varphi(n,m) = m + n \in \mathbb{N} \) pero no puedo hacerlo porque esta fómula no es aritmética. ¿Cómo se demuestra esto?

Saludos y gracias de antemano

5
Hola,

En el libro de teoría de conjuntos de Carlos Ivorra, teorema 6.29, se enuncia el siguiente teorema de Shelah:

Si \( \kappa \) es un cardinal tal que \( 2^\kappa = \kappa^+ \), entonces se cumple \( \Diamond_E \) para todo conjunto estacionario \( E \) en \( \kappa^+ \) tal que \( E \subset \{\delta < \kappa^+ | cf \delta \neq cf \kappa \} \).

Después se afirma que esto implica en particular que para todo cardinal \( \kappa > \omega \) se cumple que \( 2^\kappa = \kappa^+ \) implica \( \Diamond_{\kappa^+} \).

Tengo un problema con la demostración que se ofrece en el libro de esta última implicación. Se dice que si \( \kappa > \omega \), entonces por el teorema 6.13 del libro se tiene que \( E = \{\delta < \kappa^+ | cf \delta = \aleph_0 \} \) es estacionario en \( \kappa^+ \) y por tanto podemos aplicar el teorema de Shelah. Mi pregunta es, ¿no podría pasar que \( cf \kappa = \aleph_0 \), en cuyo caso el teorema de Shelah no se puede aplicar a \( E \)?

Esto no es problema para el teorema, pues en ese caso se puede aplicar el teorema de Shelah a \( E' = \{\delta < \kappa^+ | cf \delta = \aleph_1 \} \) (porque si \( \kappa > \omega \) pero \( cf \kappa = \aleph_0 \) en particular \( cf \kappa^+ = \kappa^+ > \aleph_1 \) luego \( E' \) es estacionario en \( \kappa^+ \)). Pero me pregunto si no hay algo que no estoy viendo y basta considerar el conjunto \( E \) como dice el libro.

Gracias y saludos

6
Teoría de Conjuntos / Propiedad asociativa generalizada
« en: 08 Agosto, 2017, 01:25 pm »
Hola,

En el teorema 4.41 del libro de teoría de conjuntos de Carlos Ivorra se enuncia una propiedad asociativa generalizada bajo las hipótesis de que tenemos una operación \( + \) asociativa y con elemento neutro. ¿Puede ser que falte la hipótesis de que sea conmutativa? Si no, no se cómo darle sentido a \( \displaystyle\sum_{j \in I} a_j \) donde \( I \) es un conjunto finito cualquiera (sin ningún orden en concreto). No sé si es una errata o si se me está escapando algo.

7
Teoría de Conjuntos / Relaciones clausurables
« en: 06 Agosto, 2017, 12:06 pm »
Hola,

Me estoy leyendo el libro de teoría de conjuntos de Carlos Ivorra, y me he encontrado en la sección 3.1 con que se habla de relación clausurable, que si no me equivoco no se ha definido antes en el libro. ¿Alguien me puede dar la definición?

Saludos y gracias.

Páginas: [1]