Autor Tema: Teorema de Gödel

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

04 Septiembre, 2009, 09:56 pm
Respuesta #180

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
La verdad no me aclara mucho, porque pienso que podría ser muy "natural" obtener una igualdad del tipo \( x = x' \).

Podría ser que \( x=x' \) sea algo demostrable si vengo "deduciendo" cosas que se han definido anterioremente.

Pero eso depende de la teoría en que esté trabajando, o cómo venga la cadena de inferencias.
Me parece que usar las mismas variables del antecedente en el consecuente, pero ahora con cuantificadores, no es algo "confiable".

Sigo sin estar convencido de que fórmulas de ese tipo sean teoremas, o demostrables, o siquiera axiomas.

 :banghead:

05 Septiembre, 2009, 01:15 pm
Respuesta #181

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
¿No resulta a simple vista poco razonable que x=x' sea teorema de un sistema tan sensato como la aritmética de Peano?

Supongamos que es un teorema. Entonces, por los axiomas de la igualdad, tendríamos como teoremas todas las fórmulas de la forma

(1)     P(x) -> P(x')

De hecho, aplicando generalización dos veces en (1), tendríamos para cada predicado P:

(2)     para todo x, para todo x', P(x) -> P(x')

Sea P el predicado 'x=0'. Entonces, eliminado el cuantificador dos veces en (2), tendríamos:

(3)     0=0 -> 1=0

y, naturalmente:

(4)     1=0

con lo que el sistema sería inconsistente, puesto que tenemos un axioma que dice que el cero no es el sucesor de ningún número.

En cambio, ¿no es razonable que si hemos demostrados que dos cosas son iguales y hemos demostrado algo (lo que sea) de la primera, podamos demostrar eso mismo de la segunda?


05 Septiembre, 2009, 05:05 pm
Respuesta #182

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino

Sí, es "razonable", pero a lo mejor las reglas dan demasiadas libertades.

El problema es que no estoy acostumbrado a usar expresiones cuantificadas de la manera en que he expuesto.
Me deja confuso porque toda la vida creí que no podía usar en una misma afirmación dos veces una misma variable de maneras distintas.

He estado buscando un razonamiento que me lleve a un "absurdo", partiendo de un teorema aritmético como:
\( \forall{x\forall{y}}(x+y=0\Rightarrow{x=y}) \)
y de ahí tratar de "usar" que \( x=y \) para demostrar el absurdo \( \exists{y\exists{y}}y+1=y.y \).
Pero peleándome con los Axiomas y las reglas no he podido lograrlo, lo cual hace que le tenga más confianza a las reglas, tal como están puestas.

Por otro lado Gustavo dice que el significado del Äxioma no es simplemente "reemplazar una variable por otra".

Ahora explico mejor de dónde vienen mis dudas.

05 Septiembre, 2009, 06:12 pm
Respuesta #183

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
El Axioma está escrito de la siguiente manera

\( x = y \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \)

Esto me hace pensar que ya tengo una fórmula F que consta de variables \( z_1,...,z_n \).
Luego, si \( x=y \), se reemplaza la variable \( z_j \) por \( x \) en el antecedente y por \( y \) en el consecuente.

En ese caso, pareciera que F tiene un "formato" en el que puede reemplazarse cualquier variable por cualquier otra.
Pero cuando se pone una variable entre paréntesis para F, ¿no significa que esta variable es libre en F?
¿Es \( z_j \) libre en \( F \)?
Gustavo ha puesto "fórmulas cualesquiera", y eso me genera bastantes dudas de qué es lo correcto tomar.

Por otra parte, yo puedo "construir" un Axioma a partir del esquema anterior, siempre y cuando yo sepa quién es la fórmula F.
Luego reemplazo en los lugares adecuados por \( x \) e \( y \), y ya está...
Pero ¿qué pasa si no tengo de entrada la fórmula F?
Si alguien me da una expresión cualquiera, y me pide verificar si cumple o no el Axioma 10, tengo que darme cuenta quién es la fórmula \( F \).
Tengo que "reconstruirla".

En la rutina de verificación, llego a reconocer que una expresión dada tiene variables \( x, y \) y fórmulas \( F \) y \( G \), en la forma:
\( (x=y \Rightarrow{F\Rightarrow{G}}) \)

El punto crucial viene cuando investigo la forma de F.
F tiene variables "concretas".
La única manera de "reconstruir" F es asumir que cada ocurrencia de la variable \( x \) en \( F \) provenía de "haber sustituido" alguna \( z_j  \) de \( F \) por \( x \).

A continuación tengo que verificar si \( G \) es la misma proposición \( F \), pero ahora en la posición de la variable hipotética \( z_j \) debe estar la variable \( y \).
Pero si reemplazo todas las ocurrencias de \( x \) en \( F \) por la variable \( y \),
se obtiene efectos muy extraños, que van más allá de la intuición básica del Axioma 10.

Lo que obtengo es una expresión G que no depende x, y si "reconstruyo" la fórmula, puede ocurrir que el "formato" de G sea distinto al de F.
O sea, G puede que incluso en G haya menos variables que en F.
El ejemplo que puse va en ese sentido.
La fórmula F del lazo izquierdo sería de la forma
\( F(x,y) \equiv{}\exists{}{x\exists{}{y}}(x.y=y+1) \)
mientras que la fórmula G tiene el formato:
\( G(x) \equiv{}\exists{}{x\exists{}{y}}(x.x=x+1) \)
 
Y acá está mi disyuntiva:
Si hago el "reconocimento" de fórmulas de manera que tengo en cuenta todas las variables "distintas" que aparecen tanto en F como en G, para luego comprobar si F y G corresponden a la misma fórmula salvo porque tienen una variable reemplazada por otra, resulta que la "rutina de análisis" concluirá que F y G son "fórmulas esencialmente distintas", tienen un formato distinto.

Por eso no me queda muy claro lo que Gustavo dice de que "no es reemplazar una variable por otra",
porque si tengo que aceptar que \( F(x,y) \) coincide con \( G(y) \),
entonces tengo que aceptar en la "rutina" que un "reemplazo directo" de \( x \) por \( y \) es lo (único) que me hace coincidr F(x,y) con \( G(y) \).

Soy capaz de hacer los dos tipos de análisis con la computadora.
El primero de ellos requiere apenas un paso más de verificación, que no resulta muy complicado.
Pero quiero entender si las reglas que puso Gustavo aceptan una forma más general.

Así que si Gustavo anda todavía por ahí, me gustaría preguntarle esto:
En el Axioma 10 las variables en \( F(z_1,...,z_n) \) deben ser libres, o tan solo deben "figurar" en la fórmula?
En este último caso, ¿cuándo se considera que una expresión de la forma siguiente satisface el Axioma 10?
\( x = y \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \Rightarrow{} G(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \)
¿Debo verificar exhaustivamente que \( F \) y \( G \) el mismo "formato", o basta conque sustituya \( x \) por \( y \), y verificar tan sólo si \( F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \) coincide caracter a caracter con \( G(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \).

Aunque si LauLuna sabe la respueta, no hace falta esperar la respuesta de Gustavo.  ;)


Otra cuestión es qué puede significar una expresión como
\( \forall{x\exists{x (x=x)}} \)

Porque algo como \( \exists{x\exists{x F(x)}} \) se entiende como una mera redundancia de cuantificadores...
¿Pero qué pasa cuando se mezclan universal y existencial con una misma variable?


06 Septiembre, 2009, 04:11 pm
Respuesta #184

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
O sea, G puede que incluso en G haya menos variables que en F.
El ejemplo que puse va en ese sentido.
La fórmula F del lazo izquierdo sería de la forma
\( F(x,y) \equiv{}\exists{}{x\exists{}{y}}(x.y=y+1) \)
mientras que la fórmula G tiene el formato:
\( G(x) \equiv{}\exists{}{x\exists{}{y}}(x.x=x+1) \)
 
Y acá está mi disyuntiva:
Si hago el "reconocimento" de fórmulas de manera que tengo en cuenta todas las variables "distintas" que aparecen tanto en F como en G, para luego comprobar si F y G corresponden a la misma fórmula salvo porque tienen una variable reemplazada por otra, resulta que la "rutina de análisis" concluirá que F y G son "fórmulas esencialmente distintas", tienen un formato distinto.

Si te entiendo bien, quieres decir que pasamos de un predicado binario F(x, y) a un predicado monario G(y). Eso no es problema: toma G(y) como G(y, y).

Citar
Por eso no me queda muy claro lo que Gustavo dice de que "no es reemplazar una variable por otra",
porque si tengo que aceptar que \( F(x,y) \) coincide con \( G(y) \),
entonces tengo que aceptar en la "rutina" que un "reemplazo directo" de \( x \) por \( y \) es lo (único) que me hace coincidr F(x,y) con \( G(y) \).

Yo diría que a nivel de programación sí se trata de sustituir variables.

Citar
Así que si Gustavo anda todavía por ahí, me gustaría preguntarle esto:
En el Axioma 10 las variables en \( F(z_1,...,z_n) \) deben ser libres, o tan solo deben "figurar" en la fórmula?

No hay ninguna restricción a la forma en que las variables pueden aparecer.

Citar
Otra cuestión es qué puede significar una expresión como
\( \forall{x\exists{x (x=x)}} \)

Porque algo como \( \exists{x\exists{x F(x)}} \) se entiende como una mera redundancia de cuantificadores...
¿Pero qué pasa cuando se mezclan universal y existencial con una misma variable?

Si cuantificas sobre una variable dos veces en la misma fórmula, simplemente tienes que recordar que a la hora de eliminar cuantificadores todas las ocurrencias de una misma variable que elimines puedes (y debes) sustituirlas por la misma constante. En el ejemplo que has puesto, da igual que cuantifiques sobre la misma variable o sobre dos variables distintas, porque el predicado es precisamente la igualdad. Pero considera este caso:

(1)    para todo x, existe y, x<y

(2)    para todo x, existe x, x<x

El problema ahora es que de (2) puedes pasar a

(3)     existe x, 0<0

Por esto es más razonable exigir de las fórmulas bien formadas que no cuantifiquen dos veces sobre la misma variable a no ser que el alcance de cada cuantificador sea diferente como en

(para todo x, x>0 v x=0) -> (existe un x, x>0 v x=0)

--

Me parece que sí que nos va a hacer falta Gustavo. Argumentaba yo en la respuesta 181 que x=x’  (ó x=y, para el caso) no es un teorema.

Lo que me pregunto ahora es: si eso es así ¿qué hace x=y en el antecedente de los axiomas lógicos 7, 8, 9 y 10 de la respuesta 33?

En la respuesta 34 planteé:

“me pregunto si en los axiomas lógicos para la igualdad 6-10 en lugar de usar metavariables para variables no deberíamos usar metavariables para términos cualesquiera.”

Gustavo me contestó que era suficiente usar metavariables para variables porque, a través del axioma 9, eso implicaba a términos cualesquiera.

No veo eso claro ahora. El axioma 9 usa otra vez una (indemostrable en el sistema) igualdad de variables como antecedente, de modo que no puede usarse para obtener la igualdad de términos que expresa el consecuente. Pero en cualquier caso una fórmula como

SS(0) = S(0)+S(0) -> (SS(0)>0 -> S(0)+S(0)>0)

no será jamás una instancia del axioma 10, porque los términos que en ella aparecen son constantes, no variables, y parece que debiera serlo.

El problema que percibo es, por tanto, que jamás vamos a demostrar la igualdad de dos variables distintas, de manera que las instancias de esos esquemas axiomáticos lógicos van a tener antecedentes que nunca son teoremas, lo que los va a dejar inservibles.

Por tanto, pregunto de nuevo: ¿no deberían los axiomas de la igualdad usar metavariables para términos cualesquiera?



06 Septiembre, 2009, 07:09 pm
Respuesta #185

Gustavo Piñeiro

  • Visitante
Hola,

El Axioma está escrito de la siguiente manera

\( x = y \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \)

Esto me hace pensar que ya tengo una fórmula F que consta de variables \( z_1,...,z_n \).
Luego, si \( x=y \), se reemplaza la variable \( z_j \) por \( x \) en el antecedente y por \( y \) en el consecuente.

En ese caso, pareciera que F tiene un "formato" en el que puede reemplazarse cualquier variable por cualquier otra.
Pero cuando se pone una variable entre paréntesis para F, ¿no significa que esta variable es libre en F?

Me he perdido un poco con todas las disquisiciones. En principio puedo aclarar esto: en la fórmula \( x = y \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \) todas las variables mencionadas se suponen libres.

La intención del axioma es ésta: si se puede probar que \( x = y \) (es decir, que tanto x como y representan en la deducción que se esté haciendo un mismo número) y se puede probar \( F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \) entonces se puede probar \( F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \).

Por inducción en la complejidad de los términos (y usando el axioma 9) se puede probar que la misma fórmula del axioma 10 vale si en lugar de x e y tomamos términos s y t cualesquiera.

El axioma 10 no se aplica al reemplazo de variables afectadas por cuantificadores. Es cierto que de \( \exists{x}P(x) \) se puede deducir \( \exists{y}P(y) \), pero en ello no interviene el axioma 10 sino el axioma 4 y la regla de generalización.

Saludos!

<<                >>

06 Septiembre, 2009, 07:28 pm
Respuesta #186

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Gracias a ambos por sus aclaraciones.

Cita de: LauLuna
No veo eso claro ahora. El axioma 9 usa otra vez una (indemostrable en el sistema) igualdad de variables como antecedente, de modo que no puede usarse para obtener la igualdad de términos que expresa el consecuente. Pero en cualquier caso una fórmula como

SS(0) = S(0)+S(0) -> (SS(0)>0 -> S(0)+S(0)>0)

no será jamás una instancia del axioma 10, porque los términos que en ella aparecen son constantes, no variables, y parece que debiera serlo.

El problema que percibo es, por tanto, que jamás vamos a demostrar la igualdad de dos variables distintas, de manera que las instancias de esos esquemas axiomáticos lógicos van a tener antecedentes que nunca son teoremas, lo que los va a dejar inservibles.

Por tanto, pregunto de nuevo: ¿no deberían los axiomas de la igualdad usar metavariables para términos cualesquiera?

Yo tengo también dudas respecto a esto.
Pero yo haría la pregunta de un modo más general.
Si yo quiero expresar un teorema matemático del estilo:

"Sea \( x = 5 \), entonces \( x+2\cdoty \) es par"

¿Cómo se escribe y/o demuestra eso con las reglas del lenguaje?

Y en general, ¿cómo se trabaja con expresiones que empiezan diciendo "Sea x = n...", donde n es un número constante concreto?

07 Septiembre, 2009, 12:53 am
Respuesta #187

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Por inducción en la complejidad de los términos (y usando el axioma 9) se puede probar que la misma fórmula del axioma 10 vale si en lugar de x e y tomamos términos s y t cualesquiera.

¿Es decir, que de los axiomas 9 y 10 se deduce:

s=t -> (P(s) -> P(t)) 

donde P(t) es el resultado de sustituir s por t uniformemente en P(s)  ?

El axioma 9 nos permite deducir igualdades entre términos si antes hemos probado ciertas igualdades entre variables. Pero es que no veo cómo podríamos probar jamás una igualdad entre variables. No creo que haya variables x e y tales quer 'x=y' sea un teorema.

Por otra parte el axioma 9 nos permite deducir igualdad de términos que sólo se diferencian en variables que antes hemos demostrado iguales. Pero no veo cómo esas igualdades entre términos pueden aumentar la eficacia del axioma 10, dado que en el axioma 10 el antecedente sólo admite igualdades de variables.

Gustavo, perdona mi obcecación, pero es que no lo veo. Ayúdanos un poco más.

Argentinator,

los enunciados del tipo 'sea x=n, entonces ...' son simples condicionales con la forma 'x=n -> ...'.

Ahora bien, si lo que quieres decir es: 'supongamos que x=n, entonces...', entonces ya no se trata de enunciados sino de demostraciones mediante razonamiento hipotético. Esas demostraciones no existen en el sistema; son prescindibles; puede demostrarse que la lógica de primer orden es completa sin ese tipo de razonamiento.

Un saludo.

 

07 Septiembre, 2009, 11:38 pm
Respuesta #188

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Tengo otra duda de tipo general.

Supongamos una fórmula como la siguiente:

\( (x+s(0)=z)\Rightarrow{\exists{x}(x=x)} \)

Es una fórmula algo tonta, pero lo quiero ilustrar es que la misma variable x aparece en la misma fórmula en dos situaciones distintas.
Primero aparece en forma "libre" y después aparece "cuantificada".

Cuando analizo sintácticamente esa fórmula, debo considerar que x es "libre" en esa fórmula. ¿No?

Ahora bien. Al aplicar el Axioma 10 a esa fórmula, siendo x una variable libre, tendré que reemplazar todas sus ocurrencias por una cierta variable y.
¿Qué es lo que debo reemplazar? ¿Sustituyo todas las ocurrencias de x por y, o sólo sustituyo sus apariciones libres (dejando "sin tocar" las apariciones cuantificadas)?
O sea, ¿cuál de las siguientes dos expresiones correspondería al Axioma 10?

\( (x=y)\Rightarrow{}((x+s(0)=z)\Rightarrow{\exists{x}(x=x)})\Rightarrow{}((y+s(0)=z)\Rightarrow{\exists{x}(x=x)}) \)

\( (x=y)\Rightarrow{}((x+s(0)=z)\Rightarrow{\exists{x}(x=x)})\Rightarrow{}((y+s(0)=z)\Rightarrow{\exists{y}(y=y)}) \)



09 Septiembre, 2009, 10:14 pm
Respuesta #189

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Argentinator, en la fórmula que ofreces la variable x está a la vez libre y ligada; evidentemente eso puede pasar en una fórmula si admitimos como fórmulas bien formadas fórmulas con variables libres.

Entiendo que el axioma 10 permite la sustitución en las ocurrencias libres y ligadas, de modo que tus dos fórmulas finales son, a mi entender, instancias del esquema axiomático 10. Pero Gustavo escribió recientemente que el axioma estaba pensado para aplicar la sustitución sólo a las variables libres.

Ahora bien, está claro que si se ha demostrado que dos términos son iguales, es lógicamente válido sustituir uno por otro en todas sus ocurrencias.

Un saludo.