Rincón Matemático

Matemática => Lógica, Conjuntos, Lenguajes Formales => Lógica => Mensaje iniciado por: JordiMath en 22 Septiembre, 2020, 08:34 pm

Título: Demostración identidad de Bezout
Publicado por: JordiMath en 22 Septiembre, 2020, 08:34 pm
Viendo la demostración de la identidad de Bezout que aparece en el libro de Lógica matemática de Carlos Ivorra, hay una igualdad que no sé de dónde sale.

Adjunto la imagen de la demostración completa donde aparece la línea que no entiendo señalada con una flecha roja.

(https://foro.rinconmatematico.com/index.php?action=dlattach;topic=114352.0;attach=22242)

No sé si es una errata o soy yo que estoy espeso. Tendría sentido que fuese:

\( x(1+qy-us)-t<xy \)

aunque de ahí no sé cómo se inferiría que

\( 1+qy-us<y \)

habiendo ese “-t” ahí.

Y no veo lo de:

\( x(1+qy-us)=x(1+qy)-t \)

porque significaría que

\( xus=t \)

y eso no se deduce en ningún momento en toda la demostración.
Título: Re: Demostración identidad de Bezout
Publicado por: geómetracat en 23 Septiembre, 2020, 12:00 pm
Pues tiene pinta de ser una errata, o al menos yo tampoco veo de dónde sale.

Editado: Lo del spoiler está mal.
Spoiler
Pero puedes deducir la desigualdad que te interesa como sigue. Por un lado tienes que
\( x(1+qy-us) = t+y(qx-vs) < y(qx-vs) \) (porque \( t>0) \).
Y por otro lado, por la elección de \( q \) se tiene que \( qx-vs \leq x \), como se dice en el texto. Juntando ambas desigualdades tienes lo que buscas:
\( x(1+qy-us) < xy \).
[cerrar]
Título: Re: Demostración identidad de Bezout
Publicado por: JordiMath en 23 Septiembre, 2020, 12:08 pm
Modifico respuesta.

Si es t>0 entonces no puede ser

\( t+y(qx-vs)<y(qx-vs) \)

no?
Título: Re: Demostración identidad de Bezout
Publicado por: geómetracat en 23 Septiembre, 2020, 01:01 pm
Tienes razón, se me fue la pinza completamente. Pensaré a ver si lo consigo arreglar.

De todas formas, es una demostración de la identidad de Bézout muy enrevesada. Lo normal es usar un poco de teoría de anillos e ideales, y sale mucho más limpio. Aunque supongo que aquí el interés está en dar una prueba en una teoría aritmética, sin usar \( \Bbb Z \) y cosas así.
Título: Re: Demostración identidad de Bezout
Publicado por: JordiMath en 23 Septiembre, 2020, 01:07 pm
Así es. Se trata de demostrarlo en \( IΣ_{1} \)
Título: Re: Demostración identidad de Bezout
Publicado por: feriva en 23 Septiembre, 2020, 01:45 pm
Tienes razón, se me fue la pinza completamente. Pensaré a ver si lo consigo arreglar.

De todas formas, es una demostración de la identidad de Bézout muy enrevesada.

Pero es muy bonita e ingeniosa, es una de mis demostraciones preferidas :)  (sí es verdad que con mis conocimientos no puedo adentrarme en muchísimas otras, pero dentro de las que he estudiado es de las que más me gustan)
Título: Re: Demostración identidad de Bezout
Publicado por: feriva en 23 Septiembre, 2020, 04:12 pm
JordiMath, de esa demostración (no exactamente tomando como referencia la transcripción de Carlos, pero es la misma) se habló largo y tendido aquí:

https://foro.rinconmatematico.com/index.php?topic=92222.msg373065#msg373065

Saludos.
Título: Re: Demostración identidad de Bezout
Publicado por: JordiMath en 23 Septiembre, 2020, 04:19 pm
Ojo, tal como dice geómetracat se trata de una demostración en una teoría aritmética \( IΣ_{1} \). No sirve la demostración habitual, que es menos enrevesada, como dice él.
Título: Re: Demostración identidad de Bezout
Publicado por: feriva en 23 Septiembre, 2020, 04:34 pm
Ojo, tal como dice geómetracat se trata de una demostración en una teoría aritmética \( IΣ_{1} \). No sirve la demostración habitual, que es menos enrevesada, como dice él.

Ah, perdón, me había parecido la misma pero con símbolos raros; no tenía ni idea de eso, gracias.

Saludos.
Título: Re: Demostración identidad de Bezout
Publicado por: Carlos Ivorra en 24 Septiembre, 2020, 01:34 am
Hola. Acabo de ver el hilo.

En efecto, el problema es que se trata de demostrar la identidad de Bezout en I\( \Sigma_1 \) como medio para acabar definiendo la función \( 2^x \), y a partir de ahí ya es relativamente fácil definir sucesiones finitas en I\( \Sigma_1 \) y a su vez formalizar todas las funciones recursivas, con lo que I\( \Sigma_1 \) se convierte en una teoría en la que uno puede moverse con comodidad. Pero, mientras tanto, las cosas son complicadas.

Ahora es un poco tarde. Lo pensaré en cuanto pueda.
Título: Re: Demostración identidad de Bezout
Publicado por: Carlos Ivorra en 24 Septiembre, 2020, 12:13 pm
Pues no sé cómo escribí ese despropósito. Hace ya varios años y no sé en qué estaría pensando. Veamos:

Queremos probar que

\( 1+qy-us\leq y \). En caso contrario, podríamos expresar

\( t = x(1+(q-1)y-us)+y(vs-(q-1)x)\geq x \),

y tenemos una contradicción, pues \( t<z\leq x \). Aquí usamos que \( (q-1)x\leq vs \), por la elección de \( q \).

Ahora falta probar que \( z\mid y \), que no es análogo, sino más bien dual. La desigualdad difícil es ahora la fácil:

Expresamos \( y=zs+t \) con \( 0<t<z \), deducimos que \( s\neq 0 \) y tratamos de expresar

\( t = y-zs = y-(xu-yv)s = x(yq-us)-y(xq-vs-1)  \),

donde \( q \) es el mínimo que cumple \( yq>us \). Pero hace falta probar que también \( xq\geq vs+1 \). Resulta que ahora es fácil ver que \( xq-vs-1\leq x \), pues en caso contrario

\( xy<y(xq-vs-1)=x(yq-us)-t<x(yq-us) \),

luego \( y<yq-us \), luego \( us<y(q-1) \), en contra de la minimalidad de \( q \).

Así pues, sólo falta probar en este caso que \( xq\geq vs+1 \). En eso estoy, pero ahora tengo que dejarlo. Supongo que saldrá. En cuanto pueda me pongo a ello.
Título: Re: Demostración identidad de Bezout
Publicado por: Carlos Ivorra en 24 Septiembre, 2020, 12:25 pm
¡Bah! Era fácil:

Si \( xq<vs+1 \) podríamos escribir

\( t = x(yq-us)+y(vs+1-xq)>x\geq z \), contradicción.

Bueno, ahora sí que se me ha hecho muy tarde. En cuanto pueda subiré una versión corregida de mi libro de lógica.
Título: Re: Demostración identidad de Bezout
Publicado por: Carlos Ivorra en 24 Septiembre, 2020, 02:18 pm
Ya he subido la nueva versión del libro. En cuanto a esto:

De todas formas, es una demostración de la identidad de Bézout muy enrevesada. Lo normal es usar un poco de teoría de anillos e ideales, y sale mucho más limpio. Aunque supongo que aquí el interés está en dar una prueba en una teoría aritmética, sin usar \( \Bbb Z \) y cosas así.

En efecto, la demostración es fea comparada con la demostración algebraica usual, pero se trata de uno de esos casos en los que la fealdad genera belleza, pues el hecho de que el teorema de Bezout pueda probarse en I\( \Sigma_1 \) (lo cual requiere acotar explícitamente \( u \) y \( v \), además de evitar el uso de números enteros, permite probar que en I\( \Sigma_1 \) se pueden definir todas las funciones recursivas primitivas y, más aún, a la larga se demuestra que toda función definible en I\( \Sigma_1 \) es necesariamente recursiva primitiva. De hecho, se prueba que I\( \Sigma_1 \) es una extensión conservativa de la aritmética recursiva primitiva, por lo que el hecho de que algo sea demostrable en I\( \Sigma_1 \) puede considerarse equivalente a que es demostrable en el sentido finitista más estricto (dentro de lo que es la lógica clásica).

Pero para acabar probando estas cosas hay que pelear un poco con demostraciones "feas". Así es la vida.
Título: Re: Demostración identidad de Bezout
Publicado por: geómetracat en 24 Septiembre, 2020, 04:01 pm
En un primer momento no entendí muy bien a qué venía esa demostración, pero luego vi que era de tu libro de lógica y me imaginé que sería algo así.

Estoy de acuerdo con lo que dices, establecer este tipo de resultado es bastante tedioso pero lo que obtienes después lo compensa con creces.
Título: Re: Demostración identidad de Bezout
Publicado por: JordiMath en 24 Septiembre, 2020, 07:53 pm
Estoy aprendiendo realmente por primera vez la lógica matemática en toda su profundidad y para mí realmente todo esto sí que es como si se abriera otro mundo.

La lógica básica en cuanto a tablas de verdad, implicaciones, bicondicional, etc. sí que la conocía evidentemente, pero no con la profundidad con la que se aprende en el libro de Carlos.

Que a partir de unos pocos axiomas básicos y un sistema deductivo formal con un puñado de reglas de inferencia se llegue a la aritmética, que todos hemos aprendido en la escuela y dominamos de forma intuitiva, realmente me está encantando.

Estudié el grado de matemáticas hasta completar segundo y tuve que dejarlo por motivos personales que no vienen al caso pero no sentí que aprendí matemáticas en mayúsculas. Evidentemente aprendí cosas pero como quien recoge migas esparcidas en el camino y no entiende que proceden del mismo pan. Cuando este año volvió a picarme la curiosidad, decidí no estudiar matemáticas sino aprender matemáticas, que no siempre es lo mismo.

Gracias a los dos por las respuestas.

Carlos, por favor, mira la consulta que hice de la jerarquía de Kleene en este mismo subforo de lógica, que también es de tu libro.
Título: Re: Demostración identidad de Bezout
Publicado por: Carlos Ivorra en 24 Septiembre, 2020, 10:38 pm
La lógica básica en cuanto a tablas de verdad, implicaciones, bicondicional, etc. sí que la conocía evidentemente, pero no con la profundidad con la que se aprende en el libro de Carlos.

Lo que llamas "lógica básica" que parece ser que es la lógica proposicional es una epidemia que causa estragos. Convence a muchos estudiantes de que "eso" es la lógica, cuando "eso" no es más que un juguete con un valor más que dudoso a la hora de fundamentar las matemáticas. Y los estragos son aún más dramáticos cuando uno es víctima de uno de esos libros que tratan la lógica de primer orden, pero dedican casi un capítulo entero a cada posible regla de inferencia, y te encuentras nombres-autopista del tipo "la regla de negación del particularizador en el consecuente en los meses impares de los años bisiestos", seguidos de comentarios y disquisiciones sobre la regla en cuestión.

Que a partir de unos pocos axiomas básicos y un sistema deductivo formal con un puñado de reglas de inferencia se llegue a la aritmética, que todos hemos aprendido en la escuela y dominamos de forma intuitiva, realmente me está encantando.

Lo más interesante es que no sólo puedas llegar a ella, sino que así puedes encontrar sus limitaciones, es decir, llegar a saber lo que no se puede hacer con la aritmética elemental.

Estudié el grado de matemáticas hasta completar segundo y tuve que dejarlo por motivos personales que no vienen al caso pero no sentí que aprendí matemáticas en mayúsculas. Evidentemente aprendí cosas pero como quien recoge migas esparcidas en el camino y no entiende que proceden del mismo pan. Cuando este año volvió a picarme la curiosidad, decidí no estudiar matemáticas sino aprender matemáticas, que no siempre es lo mismo.

Es curioso que en alguna ocasión me he encontrado con algún usuario de este foro al que se le veía agobiado tratando de compaginar su trabajo con los estudios, y que declaraba estudiar por mera curiosidad por las matemáticas, sin interés profesional, y que, sin embargo, ante la sugerencia de estudiar por su cuenta, a su ritmo, sin preocuparse por obtener un título, dejaba claro que quería el título, supongo que porque lo veían como una especie de "mérito". Nunca he entendido eso. A poco que uno tenga un poco de autodisciplina y disponga de los medios para preguntar dudas, estoy convencido de que la mejor forma de estudiar es marcándose uno sus propios objetivos de acuerdo con sus intereses. (Otra cosa es que uno necesite un título por razones obvias, pero, cuando no es así...)

Carlos, por favor, mira la consulta que hice de la jerarquía de Kleene en este mismo subforo de lógica, que también es de tu libro.

Has hecho bien en advertirme. No lo había visto. Ya te he respondido.