Autor Tema: ¿ Qué aportaría una demostración sencilla de UTF ?

0 Usuarios y 1 Visitante están viendo este tema.

01 Abril, 2016, 12:37 am
Respuesta #10

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pregunto: Se puede demostrar la indecibilidad de una determinada ecuación diofantica ?? Se han dado casos ? Qué métodos se han utilizado ?
Gracias de antemano

Ya te he respondido a casi todo lo que preguntas:

Se puede demostrar que existen ecuaciones diofánticas que no se pueden resolver ni con esas técnicas ni con ningunas otras técnicas. Más concretamente, si admitimos que la teoría de conjuntos es consistente, existen ecuaciones diofánticas que no tienen solución y es imposible demostrar por medio alguno que no tienen solución.

Por lo tanto:

1) Sí, se puede demostrar la indecibilidad de determinadas ecuaciones diofánticas.
2) Se han dado casos. Se pueden escribir ecuaciones diofánticas concretas (aunque en la práctica sería tedioso escribirlas explícitamente, lo normal es explicar cómo se construirían, pero nadie ha estado tan aburrido como para ponerse a escribirlas) de las que se puede demostrar que si no tienen solución no es posible demostrar que no la tienen.

En cuanto a los métodos, lo que te digo se basa en la prueba de los teoremas de incompletitud de Gödel. La idea es que es posible escribir una ecuación diofántica de la que se puede demostrar que tiene solución si y sólo si las matemáticas son contradictorias. Sucede entonces que es muy poco probable que tenga solución (ya que es muy poco probable que las matemáticas que conocemos sean contradictorias) y los teoremas de incompletitud prueban que, en caso contrario, si las matemáticas son consistentes y, por consiguiente, no existe solución, es imposible probarlo. Porque podríamos programar un ordenador de forma que, si le diéramos una demostración de que la ecuación diofántica en cuestión no tiene solución, el ordenador podría construir una demostración rigurosa de que \( 2+2=5 \) a partir de los axiomas aceptados para la matemática, y a partir de ahí el ordenador podría encontrar una solución de la ecuación diofántica.

Sé que suena un poco trabalenguas, pero eso es lo que hay. Trataré de resumirlo de otra manera:

Es posible escribir una ecuación diofántica (un polinomio de varias variables con coeficientes enteros igualado a cero) con las dos propiedades siguientes:

1) Una solución de la ecuación es como una clave que permite descodificar de ella una demostración rigurosa de que 2 + 2 = 5.

2) A partir de una demostración de que la ecuación no tiene solución podemos construir una solución de la ecuación (podemos incluso programar a un ordenador para que lo haga: le damos la demostración, supuesto que exista, y él nos calcula la solución).

Como no es probable que se pueda demostrar que 2 + 2= 5, la ecuación no puede tener solución por 1), pero no es posible demostrarlo, porque si pudiéramos probarlo, entonces 2) nos daría una solución y, de nuevo por 1), una prueba de que 2 + 2 = 5.

01 Abril, 2016, 10:19 am
Respuesta #11

Roman Montoliu

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 95
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
¿Puedes poner aqui un ejemplo de una de tales ecuaciones ? o tal vez sean excesivamente largas como para que quepan ? (lo desconozco)

Saludos

01 Abril, 2016, 11:07 am
Respuesta #12

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Puedes poner aqui un ejemplo de una de tales ecuaciones ? o tal vez sean excesivamente largas como para que quepan ? (lo desconozco)

Se pueden escribir ecuaciones diofánticas concretas (aunque en la práctica sería tedioso escribirlas explícitamente, lo normal es explicar cómo se construirían, pero nadie ha estado tan aburrido como para ponerse a escribirlas) de las que se puede demostrar que si no tienen solución no es posible demostrar que no la tienen.

Esas ecuaciones "codifican" en cierto modo todos los axiomas de la lógica y la matemática y las técnicas válidas de deducción, por lo que no pueden ser más breves que un libro que explique todo eso, aunque sea sucintamente, sin más que lo imprescindible.

De todos modos, yendo algo más lejos en tu pregunta de qué técnicas se utilizan para demostrar estas cosas, puedo añadir que Gödel se quedó a las puertas de demostrar los resultados que te he indicado sobre ecuaciones diofánticas. Lo que le faltó fue un teorema que afirma que una función es recursiva (= calculable mediante un ordenador) si y sólo si es diofántica (lo cual significa que \( f(x_1,\ldots, x_n)= y \) si y sólo si \( (x_1, \ldots, x_n, y) \) es la solución de una cierta ecuación diofántica). A su vez, esto fue demostrado en 1952 por Julia Robinson suponiendo una conjetura que fue demostrada en 1970 por Matiyasevic, a saber, que la función \( n^k \) es diofántica. Esto significa que existe un polinomio \( P(m,n,k,x_1,\ldots, x_n) \) con coeficientes enteros tal que

\( m=n^k\leftrightarrow \exists x_1\cdots x_n\in \mathbb Z\ P(m,n,k,x_1,\ldots, x_n)=0 \).

Este hecho no es trivial en absoluto. Para que te hagas una idea, ese polinomio es de la forma \( P=F_1^2+\cdots + F_{13}^2 \), donde

\( F_1= x^2-(a^2-1)y^2-1 \)

\( F_2=u^2-(a^2-1)v^2-1 \)

\( F_3=s^2-(b^2-1)t^2-1 \)

\( F_4=v-ry^2 \)

\( F_5=b-1-4(p+1)y-a-(q+1)u \)

\( F_6=s-x-cu \)

\( F_7=t-k-4dy \)

\( F_8=y-k-e \)

\( F_9=(y-y'-1)^2+(v-v'-1)^2+(t-t'-1)^2+(x-x'-1)^2 \)

\( F_{10}=(x-y(a-n)-m)^2-f^2(2an-n^2-1)^2 \)

\( F_{11}=m+g+1-2am+n^2+1 \)

\( F_{12}=(w-n-h-1)^2+(w-k-l-1)^2 \)

\( F_{13}=a^2-(w^2-1)(w-1)^2(z+1)^2-1 \)

Y todo esto sólo para expresar mediante una ecuación diofántica la igualdad \( m=n^k \). Imagina qué clase de ecuación diofántica será necesaria para expresar que un número natural \( m \) es, no ya igual a \( n^k \), sino a un código de un axioma de la teoría de conjuntos, por ejemplo.

El problema de si existe una forma de saber si una ecuación diofántica cualquiera tiene o no solución se conoce como "el décimo problema de Hilbert". La demostración de Matiyasevic (y la caracterización diofántica de las funciones recursivas) está aquí:

M. Davis, "Hilbert tenth problem is unsolvable", Am. Math Monthly 80 (1973) 233-269.

Si pones en google:     davis hilbert tenth problem is unsolvable    te sale.

01 Abril, 2016, 12:01 pm
Respuesta #13

Roman Montoliu

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 95
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Gracias por la respuesta tan inmediata. Muchas gracias. Un verdadero placer leerte.
Bien, entiendo por tu respuesta que una ecuación concreta no se ha escrito.
También queda claro que es demostrable la indecibilidad, pues la conclusiones de Godel son un método de demostración.
Te enfoco la cuestión de otro modo: Habría que añadir a la "teoria" nuevas fórmulas (proposiciones) del tipo "la ecuación diofántica E es indecidible", para su posible demostración o refutación.
Entonces, pregunto: ¿Acaso no se podrían obtener nuevas consecuencias aparentemente "absurdas" como las ya obtenidas del tipo siguiente:

"Si la ecuación diofántica E es indecible entonces no se puede demostrar que es indecidible"

(Incluyo parte de la cita de tu respuesta anterior: "... si no tiene solución no es posible demostrar que no la tienen ..."

01 Abril, 2016, 12:38 pm
Respuesta #14

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Bien, entiendo por tu respuesta que una ecuación concreta no se ha escrito.

Pero eso es un mero tecnicismo. Sí se ha descrito el método para construir una ecuación concreta. Simplemente, nadie se ha molestado en meter ese método en un ordenador para que calcule esa ecuación en concreto porque se requeriría un tiempo y mucha paciencia para hacerlo y el resultado serían unos cientos de páginas llenas de letras y números. ¿Qué ganaríamos con verlas?

Es lo mismo que decir que nadie se ha molestado nunca en escribir en fila todos los números del 1 hasta \( 10^{1000} \). Cualquiera puede hacerlo con paciencia, pero ¿quién querría hacer tal cosa?

También queda claro que es demostrable la indecibilidad, pues la conclusiones de Godel son un método de demostración.

Ahí hay un matiz: "indecidible" puede tener un sentido relativo (no demostrable ni refutable a partir de unos axiomas prefijados) o absoluto (no demostrable ni refutable te pongas como te pongas).

Cuando fijas unos axiomas sencillos, como los axiomas de Peano, sí que es posible dar ejemplos de ecuaciones concretas (aunque nadie tenga la paciencia de escribirlas explícitamente) de las que se puede demostrar que no es posible probar ni que tienen ni que no tienen solución a partir de dichos axiomas (lo cual equivale a que en realidad no tienen solución, pues si la tuvieran podría probarse a partir de los axiomas de Peano), y el hecho de que no tengan solución es demostrable, pero no a partir de los axiomas de Peano (lo es, por ejemplo, a partir de los axiomas de la teoría de conjuntos).

Ahora, si hablamos de indecidibilidad en sentido absoluto, entonces no es exactamente cierto que la indecidibilidad es demostrable. Lo que se demuestra es que una ecuación diofántica concreta tiene solución sólo si la teoría de conjuntos es contradictoria, y entonces caben dos opciones:

1) Que la teoría de conjuntos sea contradictoria, y entonces sí que es posible decidir la ecuación, concretamente, es posible encontrarle una solución.

2) Que la teoría de conjuntos sea consistente, y entonces la ecuación no tiene solución, pero no puedes demostrarlo te pongas como te pongas (salvo, obviamente, que admitas como "demostración" tomar un axioma que afirme que no la tiene y demostrarlo a partir de ese axioma, pero nada te garantizará entonces que el axioma es cierto).

Un poco más en general, observa que si una ecuación diofántica es indecicible (= no podemos demostrar si tiene o no solución) entonces no tiene solución (si la tuviera, siempre podría demostrarse que tiene solución encontrándola y comprobando que cumple la ecuación). Todas las ecuaciones diofánticas con solución son decidibles. Para que sea indecidible hace falta que no tenga solución y que no pueda probarse que así ocurre.

Te enfoco la cuestión de otro modo: Habría que añadir a la "teoria" nuevas fórmulas (proposiciones) del tipo "la ecuación diofántica E es indecidible", para su posible demostración o refutación.

No sé si entiendo bien lo que planteas. Como te decía, tomar como axioma que es indecidible es lo mismo que tomar como axioma que no tiene solución. Si realmente una ecuación es indecidible, siempre puedes añadir como axioma que no tiene solución y entonces tienes una teoría "más rica" que permite demostrar más cosas sobre los números naturales. En realidad, también puedes tomar como axioma que sí que tiene solución (aunque sea falso) y lo que te sale es una teoría sin contradicciones, pero un tanto rara (lo que se llama una teoría \( \omega \)-contradictoria).

Entonces, pregunto: ¿Acaso no se podrían obtener nuevas consecuencias aparentemente "absurdas" como las ya obtenidas del tipo siguiente:

"Si la ecuación diofántica E es indecible entonces no se puede demostrar que es indecidible"

(Incluyo parte de la cita de tu respuesta anterior: "... si no tiene solución no es posible demostrar que no la tienen ..."

Bueno, eso sonará raro, pero si lo entiendes bien no tiene nada de absurdo, ni siquiera aparentemente. Una ecuación dada puede tener solución o no. Si la tiene, entonces puede probarse que la tiene (encontrándola y comprobándola), mientras que si no la tiene, hay dos opciones:

1) Que sea posible demostrar que no la tiene. Por ejemplo, la ecuación \( x^2+y^2=-1 \) no tiene soluciones enteras, y es muy fácil demostrarlo (por supuesto, hay casos mucho menos triviales de esta situación.)

2) Que no sea posible demostrar que no la tiene. En tal caso la ecuación es indecidible: ni puedes demostrar que tiene solución (porque no la hay) ni puedes demostrar que no la tiene. Pero no puedes demostrar que sea indecidible, porque eso sería lo mismo que probar que no tiene solución, ya que todas las ecuaciones con solución son decidibles.

Y, sí, si tomamos como axioma que una ecuación dada no tiene solución, aunque no podamos probar que así es, entonces podríamos encontrar otra ecuación diofántica que resulta indecidible incluso contando con ese axioma adicional, y así nos metemos en un camino que no tiene fin. Sólo hay una salida "en falso", y es tomar como axioma que todas ecuaciones que no tienen solución no tienen solución, pero eso es trampa, porque entonces no sabemos qué axiomas estamos tomando. Técnicamente, nuestro conjunto de axiomas no sería recursivo.

01 Abril, 2016, 12:47 pm
Respuesta #15

Roman Montoliu

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 95
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias por todas tus respuestas.

Un cordial saludo

01 Abril, 2016, 01:13 pm
Respuesta #16

elcristo

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,201
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola.

A mí sólo me queda una duda.

Todo esto, ¿Cuándo y dónde se aprende?

Porque sinceramente, estoy terminando el grado y puedo contar con los dedos de una mano las cosas nuevas que he aprendido, y 3 de los dedos son de teoría de Galois (Cosas del grado en Cantabria y de la profesora  :D)

Si hasta 4º más o menos no sabíamos que era una ecuación diofántica, y nos lo contaron de refilón porque salió como curiosidad...

Saludos.

01 Abril, 2016, 01:55 pm
Respuesta #17

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Así a ojo, el 80% de las matemáticas que sé las he estudiado yo por mi cuenta, leyendo libros que poco o nada tenían que ver con las asignaturas de la carrera. El método es: coges un libro que te interese. Si lo entiendes te lo estudias, y si no lo entiendes buscas uno más fácil, y cuando lo hayas entendido vuelves al anterior. Y si encima tienes la ocasión de preguntar las dudas que te vayan surgiendo en un foro como éste (ocasión que yo no tenía cuando estudiaba), pues mejor aún.

01 Abril, 2016, 09:48 pm
Respuesta #18

Roman Montoliu

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 95
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Entro de nuevo en el hilo para ahondar un poco mas en estas discusiones, que creo son también interesantes para muchos.
Creo conocer un método relativamente simple para resolver al menos determinados tipos de ecuaciones diofánticas. Este método podría ser implementado algorítmicamente y por tanto computacionalmente de forma que estaría garantizada la obtención de soluciones para una ecuación dada en un número finito de pasos, caso de tener solución. El proceso también acaba si se obtiene una contradicción, conluyendo que la ecuación no tiene soluciones. Y es aquí cuando me surgen dos dudas relacionadas con la indecibilidad:

1ª) Si la ecuación diofántica fuese indecidible es obvio que la computadora nunca acabaría el proceso, me cuestiono la siguiente pregunta: ¿recíprocamente, se podría afirmar que la ecuación diofántica es indecidible?. Mas concretamente, ¿se podría decir que es indecidible una ecuación diofántica E para la que se cumple:
 
Dadas infinitas proposiciones \( P_1, P_2, ...., P_n, ... \), e infinitos enteros positivos \( 0 < k_1 < ... < k_n < ... \)

 a) Por cada posible solución \(  x=(x_1,...x_m) \) de E existe una y solo una proposición que es cierta.
 b) E tiene solución si \( P_1 \) es cierta o bien si no lo es y lo es \( P_2 \), o bien si esta no lo es y lo es \( P_3  \) y así sucesivamente para todo \( n \in{N} \), y para cada n \(  P_1, P_2,... P_n \)  son falsas.
c) En cada paso n no se obtiene contradicción
d) En cada paso n las tuplas \( (x_1,...,x_m) \) de enteros tales que \( x_i < k_n \) no son solución


(reeditado)

En principio parece que deba serlo.

2ª) De no ser así, entonces: ¿podría existir otro método con el que se pudiese demostrar que la ecuación E no tiene soluciones?

Saludos
(reeditado)

01 Abril, 2016, 11:27 pm
Respuesta #19

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Creo conocer un método relativamente simple para resolver al menos determinados tipos de ecuaciones diofánticas.

Nada impide que existan métodos para resolver determinados tipos de ecuaciones diofánticas.

Este método podría ser implementado algorítmicamente y por tanto computacionalmente de forma que estaría garantizada la obtención de soluciones para una ecuación dada o bien la deducción de que no las tiene en un número finito de pasos.  Y es aquí cuando me surgen dos dudas relacionadas con la indecibilidad:

1ª) Si la ecuación diofántica fuese indecidible es obvio que la computadora nunca acabaría el proceso, me cuestiono la siguiente pregunta: ¿recíprocamente, se podría afirmar que la ecuación diofántica es indecidible?.

Pues eso dependerá de tu método, pero muy general debería ser para que pudiera asegurar que si él no proporciona respuesta, ningún otro método podría hacerlo.

Mas concretamente, ¿se podría decir que es indecidible una ecuación diofántica E para la que se cumple:
 
Dadas infinitas proposiciones P_1, P_2, ...., P_n, ...

 a) Por cada posible solución x_i de E existe una y solo una proposición que es cierta.
 b) E tiene solución si P_1 es cierta o bien si no lo es y lo es P_2, o bien si esta no lo es y lo es P_3 y así sucesivamente para todo n\in{N}, y ninguna proposición P_n es cierta".

Eso es demasiado general, pero no veo nada en lo que planteas que, en principio, tenga que ver con la indecibilidad.


En principio parece que deba serlo.

2ª) De no ser así, entonces: ¿podría existir otro método con el que se pudiese demostrar que la ecuación E no tiene soluciones?

¿Otro método distinto de cuál? Todo lo que planteas es demasiado vago.