Autor Tema: Teorema de Gödel

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

14 Junio, 2009, 12:07 pm
Respuesta #60

LauLuna

  • Experto
  • Mensajes: 544
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Como los programas reales sólo pueden hacer cálculos con conjuntos finitos, me da la impresión de que el teorema de Gödel o el problema de la parada no debe de ser fácil de programar en un ordenador.

No sé exactamente lo que quieres decir con lo de cálculos con conjuntos finitos, pero por lo que entiendo, no es correcto. Claramente hay programas que deciden si un número natural es primo, y lo hacen para todo número natural. Como esto es muy evidente, imagino que no te he entendido bien.

No puedo juzgar sobre si es o no fácil programar un ordenador para que demuestre el teorema de Gödel pero desde luego es posible. Todo sistema formal axiomático puede convertirse en un algoritmo que genera teoremas, y siempre es posible introducir (parte de) la metateoría del sistema en otro sistema formal axiomático.

En concreto, el sistema formal que Gustavo Piñeiro está construyendo (al que sólo le faltan ya, creo, los axiomas aritméticos) será capaz de demostrar una fórmula equivalente, bajo la interpretación usual, al primer teorema de incompletitud de Gödel:

"si el sistema es consistente, hay enunciados de su lenguaje indecidibles en el sistema'

Así que si Argentinator se empeña en convertir el sistema en un algoritmo generador de teoremas, lo conseguirá tarde o temprano.

Gustavo, quedamos en que llamamos teoremas sólo a los enunciados demostrables. Bien, casi mejor; esto no altera nada pero es posible que haya que recordarlo luego a lo largo de la demostración.

Un saludo



14 Junio, 2009, 02:47 pm
Respuesta #61

Numerarius

  • Aprendiz
  • Mensajes: 319
  • Karma: +0/-0
  • Sexo: Masculino
Como los programas reales sólo pueden hacer cálculos con conjuntos finitos, me da la impresión de que el teorema de Gödel o el problema de la parada no debe de ser fácil de programar en un ordenador.

No sé exactamente lo que quieres decir con lo de cálculos con conjuntos finitos, pero por lo que entiendo, no es correcto. Claramente hay programas que deciden si un número natural es primo, y lo hacen para todo número natural. Como esto es muy evidente, imagino que no te he entendido bien.


Bueno, el conjunto de los números primos es recursivamente enumerable. Así que, en teoría se podría demosrtrar la propiedad"ser primo" para cualquier número natural.

Pero a lo que me refería es a lo siguiente: para demosrar que existen infinitos números primos, no recorres toda la serie  de los números naturales. Porque el conjunto N es infinito. Así que, por muchos números que recorra el computador, sólo habrás recorrido una parte infinitesimal de los números naturales.

Así que la exstencia de infinitos números primos, se demuestra matemáticamente. La demostración de Euclides era que dados todos los números primos: (1·2·3....n) se construye el número:

x= (1·2·3....·n) + 1. Número que no es divisible por 1, por 2, por 3....ni por n. Así que o x es primo, o existe un número primo entre n y x. 


14 Junio, 2009, 02:56 pm
Respuesta #62

Numerarius

  • Aprendiz
  • Mensajes: 319
  • Karma: +0/-0
  • Sexo: Masculino
argentinator, supongo que sí puede haber un programa que decida, para cadenas finitas, si éstas son teoremas o no. También podría haber un programa que decida si son fórmulas bien formadas o no.

Por ejemplo, esta proposición

\( \exists x \;x= 0 \)

podría ser un teorema (si es que es demostrable en el sistema). En cambio:

\( p\land \lnot\; p \)

Una proposición como ésta es falsa, así que no sería demostrable como teorema  en el sistema, a no ser que el sistema fuera inconsistente. Sin embargo, es una proposición bien formada. Una proposición falsa puede estar bien formada.

En cambio la proposición

(((((((((((((((((((((((((((((8

no está bien formada.
 



14 Junio, 2009, 03:48 pm
Respuesta #63

Gustavo Piñeiro

  • Visitante
supongo que sí puede haber un programa que decida, para cadenas finitas, si éstas son teoremas o no.

No siempre es así, depende de cada teoría. Si los axiomas forman un conjunto recursivo entonces existe un algoritmo que determina si una sucesión finita de signos es una fórmula y si una sucesión finita de fórmulas es una demostración. Pero no necesariamente sucede lo mismo con los teoremas. (Dicho en términos técnicos, los teoremas forman un conjunto recursivamente numerable, pero no siempre un conjunto recursivo. Es decir, existe un algoritmo que va generando los teoremas "uno por uno", pero no necesariamente uno que los "reconozca".)

Gustavo, quedamos en que llamamos teoremas sólo a los enunciados demostrables. Bien, casi mejor; esto no altera nada pero es posible que haya que recordarlo luego a lo largo de la demostración.

Si es necesario, lo recordaremos.

Un saludo,

14 Junio, 2009, 03:57 pm
Respuesta #64

Gustavo Piñeiro

  • Visitante
Algunas definiciones:

Definición: Un conjunto de axiomas es consistente si no existe una fórmula \( P \) tal que \( P \) y \( -P \) sean a la vez demostrables.

Puede probarse que si un conjunto de axiomas no es consistente entonces toda fórmula \( Q \) es demostrable. Esto se debe, básicamente, al hecho de que cualesquiera sean \( P \) y \( Q \), la fórmula \( P\Rightarrow (-P\Rightarrow Q) \) es demostrable.

En un sistema inconsistente todo es demostrable y todo es refutable (refutable significa que su negación sea demostrable). Los sistemas inconsistentes son triviales en el peor sentido de la palabra.

Definición: Un conjunto de axiomas es \( \omega  \)-consistente si no existe una fórmula \( P(x) \) tal que \( P(0) \), \( P(1) \), \( P(2) \),... y \( \exists{x}(-P(x)) \) sean a la vez demostrables.

Aunque la segunda definición involucra un infinito actual, es importante destacar que ambas sólo utilizan conceptos sintácticos (que dependen de manipulaciones de signos, independientemente de su significado).

Es fácil probar que todo conjunto \( \omega  \)-consistente es también consistente, sin embargo no vale la recíproca (podremos dar un  contraejemplo después de demostrar el teorema de Gödel).

Si agregamos la regla de inferencia no finitaria que cité en un comentario anterior (y que invalida el teorema de Gödel) en ese caso sí valdría que todo conjunto consistente es también \( \omega  \)-consistente.

<<                >>

15 Junio, 2009, 08:36 pm
Respuesta #65

LauLuna

  • Experto
  • Mensajes: 544
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Definición: Un conjunto de axiomas es consistente si no existe una fórmula \( P \) tal que \( P \) y \( -P \) sean a la vez demostrables.

Hay un problema con esta definición: la fórmula esa que no debe existir no sabemos exactamente qué relación tiene con el conjunto de axiomas. Deberíamos decir que no existe una fórmula tal que ella y su negación son consecuencias lógicas del conjunto de axiomas. Pero para eso tendríamos que definir 'consecuencia lógica', y tal vez eso no sea necesario.

Quizá sería mejor decir que no existe una fórmula tal que ella y su negación son demostrables en el sistema, pero entonces deberíamos hablar de cuándo es consistente un sistema, no un conjunto de axiomas.

Gustavo, ¿hay alguna razón por la que prefieras hablar de la consistencia de un conjunto de axiomas mejor que de la consistencia de un sistema?

Sucede lo mismo para la definición de omega-consistencia.

Un saludo.


15 Junio, 2009, 08:53 pm
Respuesta #66

Gustavo Piñeiro

  • Visitante
Definición: Un conjunto de axiomas es consistente si no existe una fórmula \( P \) tal que \( P \) y \( -P \) sean a la vez demostrables.

Hay un problema con esta definición: la fórmula esa que no debe existir no sabemos exactamente qué relación tiene con el conjunto de axiomas.

En realidad sí lo sabemos, porque ya definimos qué quiere decir que una fórmula sea demostrable:

Definición: una demostración es una sucesión finita de fórmulas en la que cada una de ellas es, o bien un axioma (propio o lógico), o bien se dedude de fórmulas anteriores por aplicación de las reglas de inferencia.

Definición: una fórmula es demostrable si es la última fórmula en una demostración.


Por otra parte (no encuentro ahora la cita) también dije que usaríamos "conjunto de axiomas" y "sistema de axiomas" como sinóinimos.

Si mis formalismos llevan a confusión, realmente no tengo ningún inconveniente en ceder esta tarea de desarrollarlos a quien desee tomarla. No tiene más que "levantar la mano" y yo gustosamente le cederé mi puesto en esta especie de "estrado virtual" en el que siento que me hallo. :)

Saludos,

Gustavo

15 Junio, 2009, 08:55 pm
Respuesta #67

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

Si mis formalismos llevan a confusión, realmente no tengo ningún inconveniente en ceder esta tarea de desarrollarlos a quien desee tomarla. No tiene más que "levantar la mano" y yo gustosamente le cederé mi puesto en esta especie de "estrado virtual" en el que siento que me hallo. :)



¡No! ¡No cambiemos ahora de chivo expiatorio!  >:D
Si cambiamos mucho las cosas se va a armar una confusión terrible.
Creo que basta conque nos pongamos de acuerdo en el significado de los formalismos que se van a usar.


15 Junio, 2009, 09:49 pm
Respuesta #68

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Hice antes unas preguntas, pero las cambio de lugar para que no se mezclen tanto las cosas:


Axiomas lógicos:
...
Por definición, un axioma lógico es cualquier fórmula que ...
...
4. \( \forall{x}F(x)\Rightarrow{}F(x/t) \).
Una explicación aquí: \( x \) respresenta una variable cualquiera y cuando escribimos \( F(x) \) entendemos que \( x \) es una variable libre en F, \( t \) es un término y \( F(x/t) \) es la fómrula que se obtiene reemplazando toda aparición de la variable \( x \) por el término \( t \). Una restricción: si \( t \) tiene variables, ninguna de éstas puede aparecer afectada por un cuantificador al efectuarse el reemplazo.

Hola.

No me queda muy claro todo esto.
Es claro que la regla es ''reemplazar x por t'', pero no entiendo bien qué pasa con los eventuales cuantificadores.

1er pregunta: Se ha establecido que todo término contiene constantes o variables. En particular x es una variable. ¿Qué pasa si deseo reemplazar x por t, cuando t es un término que ''adentro'' contiene a la misma x?
¿No es esto algo mal definido, no queda algo recurrente e infinito, como producto de reemplazos sin fin?

2da pregunta: En cuanto a la restricción de los cuantificadores...
Si t es un término, es una lista de signos en la que no figura el signo de cuantificación \( \exists{} \).
Así que si pido que las variables que figuran en t no estén afectadas por cuantificadores, entiendo que esos cuantificadores son ''externos'' a t. Así que imagino que se refiere a cuantificadores que podrían aparecer dentro de F.
¿Pero qué significa exactamente la restricción?
Lo que entiendo es que ''una vez efectuado el reemplazo de x por t no debe quedar ninguna variable en t afectada por un cuantificador de los que había en F''.
Creo que lo entiendo, pero aún así no lo veo muy claro.

Una cuestión filosófica:
Para decidir si una expresión es un término o no lo es, tengo que rechazar por ejemplo las expresiones que tengan cuantificadores.
Cuando se da la definición de término, está bien, se hace de modo constructivo.
Pero ¿qué pasa si me dan una expresión t cualquiera, y debo determinar si es o no un término?
Para probarlo, debo pasar uno a uno por sus signos, y si encuentro un símbolo que no corresponde a constantes o variables o paréntesis, concluir que t no es un término.
Sin embargo, no estoy seguro de si la propiedad de ''no ser un término'' forma parte de las reglas que definen lo que es un término.
Me refiero a que yo me doy cuenta con mi propia razón que una expresión no es un término, pero no estoy seguro de si esto se deduce propiamente de las reglas dadas, las cuales se dan en ''positivo'' (o sea, para afirmar cuándo tengo un término), pero no en negativo (cuando deseo probar que algo no es un término).

No sé si entiende esta última duda, o si es demasiado quisquilloso de mi parte.
Pero es que no quiero usar ''razonamientos'' que no están estipulados en el conjunto de reglas que se han aceptado hasta ahora.
No creo que haya hechos que pueda dar por sobreentendidos, porque a la larga puede ser fuente de falacias.


15 Junio, 2009, 11:44 pm
Respuesta #69

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Comenté antes que si se agregara la siguiente regla de inferencia:

De los infinitos enunciados \( P(0), P(1), P(2),... \) se deduce \( \forall{x}P(x) \).

Entonces el teorema anterior sería falso y también sería falso el teorema de Gödel.

Me parece que acá hay cosas que no estoy entendiendo.

Cuando hablás de P(0), P(1), P(2), ¿los números 0, 1, 2, qué vendrían a ser: acaso 0, S0, SS0, etc.?
En todo caso, si tengo una proposición P, con una variable x, parece que entiendo lo que significa P(x).
Según lo que se ha estado hablando, sería una fórmula en la cual aparece la variable x en forma libre.
Ahora por el axioma de reemplazo, para 0, 1, 2, etc., tendría que P(0), P(1), P(2), etc., tienen sentido.
Pero en lugar de x pueden ir cosas como (s+t), (s.t), donde s y t son términos que incluyen variables, constantes, etc.
Me da la sensación de que me está faltando algo, o sobrando. Por ejemplo, no sé qué hacer con P(3+4), mientras aún no sé que 3+4 es 7.

¿Faltan axiomas aritméticos tal vez?


16 Junio, 2009, 12:28 am
Respuesta #70

LauLuna

  • Experto
  • Mensajes: 544
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Si mis formalismos llevan a confusión, realmente no tengo ningún inconveniente en ceder esta tarea de desarrollarlos a quien desee tomarla. No tiene más que "levantar la mano" y yo gustosamente le cederé mi puesto en esta especie de "estrado virtual" en el que siento que me hallo. :)

No, de ningún modo me parece eso recomendable. Creo que vamos muy bien.

Si habías definido 'conjunto axiomas' y 'sistema de axiomas' como sinónimos, entonces pido perdón, no lo recordaba. Tal vez convendría haber dicho algo así como 'si no hay una fórmula P tal que P y no -P sean demostrables en el conjunto de axiomas'; es la ausencia de la palabra 'demostrables' la que me ha confundido un poco.

Pero todo está claro ahora.

16 Junio, 2009, 12:32 am
Respuesta #71

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Los cito a ambos, a ver si se amigan.

Argentinator, técnicamente (en Teoría de Modelos) una teoría es un conjunto C de sentencias en un lenguaje lógico formal con la condición de que C esté cerrado bajo la relación de consecuencia lógica: para todo p y q, si p pertenece a C y q es consecuencia lógica de p, q pertenece a C.

Pero en un sentido más amplio es usual llamar también teorías a los sistemas formales axiomáticos. En algunos de estos sistemas el conjunto de los teoremas es efectivamente una teoría, particularmente en los sistemas de primer orden: como la lógica de primer orden es completa (Gödel 1930), toda consecuencia lógica de los axiomas es también un teorema del sistema. Pero en algunos de ellos, como la aritmética de Peano de segundo orden, el conjunto de los teoremas no es una teoría en el sentido más estricto, porque no toda consecuencia lógica de los axiomas es un teorema.

Como sabes, los sistemas formales axiomáticos están compuestos por axiomas o esquemas axiomáticos y reglas de inferencia.

(Cuando digo sistema es que incluyo a las reglas de inferencia, si éstas son fijadas de antemano, como habitualmente se hace, entonces "sistema de axiomas" y "conjunto de axiomas" son virtualmente sinónimos).

Parece que en sistema se incluyen las reglas de inferencia.
Yo no había notado que había dos cosas distintas.
Por ahora para mí las reglas y axiomas que ha enumerado Gustavo son ''EL'' sistema.  ;)

16 Junio, 2009, 03:42 am
Respuesta #72

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Me voy a contestar yo solo algunas cosas.


1er pregunta:  ¿Qué pasa si deseo reemplazar x por t, cuando t es un término que ''adentro'' contiene a la misma x?
¿No es esto algo mal definido, no queda algo recurrente e infinito, como producto de reemplazos sin fin?


Estudiando el asunto me doy cuenta que caí en la trampa de mi propia estupidez.
Si uno reemplaza una variable por un término, se sigue obteniendo una fórmula sin problema alguno, y si en el reemplazo de x por t resulta que dentro de t figura la misma x, como por ejemplo, si t es el término (x+S(z)).(x.y) no parece haber ningún contrasentido en lo que queda tras el reemplazo de F(x) por F(t).

En todo caso, lo que uno puede apreciar es que el Axioma de Reemplazo dice más de lo que puede percibirse a simple vista, y que no está de más reflexionar cuán extravagante y general puede ser el ''reemplazo'' que se vaya a hacer con cierto término t.

2da pregunta: En cuanto a la restricción de los cuantificadores (en el axioma de reemplazo)...

Me estuve fijando en el libro de Martínez/Piñeiro, y los axiomas están del mismo modo en que Gustavo los ha introducido acá en el foro. En cuanto al Axioma de Reemplazo ya me queda más claro cómo se debe restringir el término t:
En la fórmula F(x) (libre en x) pueden aparecer ciertas variables \( z_1,...,z_m \) afectadas por cuantificadores.
Ninguna de esas variables debe figurar en t.
Es lo mismo que ha dicho Gustavo, pero hasta que no lo escribo yo mismo parece que no me convenzo.

Las dudas que expuse a continuación, esas aún no las he aclarado por mi cuenta.

16 Junio, 2009, 10:53 am
Respuesta #73

LauLuna

  • Experto
  • Mensajes: 544
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Las dudas que expuse a continuación, esas aún no las he aclarado por mi cuenta.

Creo que preguntabas si el conjunto de los términos es recursivo, es decir, si hay un algoritmo que, dada una cadena de símbolos del lenguaje, decida si esa cadena es o no un término.

Sí, si es recursivo. Hay una manera de examinar los símbolos de una cadena uno a uno para decidir si una cadena responde o no a las reglas de formación de términos. Es posible decidir si la cadena es o no un término con un solo símbolo, es decir, una variable ó 0. Es posible decidir (en un número finito de pasos) si la cadena es de la forma St, t+t', txt', donde t y t' son términos.

El hecho de que determinados conjuntos de fórmulas del sistema (el de los términos, el de las variables, el de los enunciados, el de los axiomas, ...) sean recursivos será luego una pieza clave en la demostración del teorema.

Un saludo.

16 Junio, 2009, 09:01 pm
Respuesta #74

Gustavo Piñeiro

  • Visitante
Tal vez convendría haber dicho algo así como 'si no hay una fórmula P tal que P y no -P sean demostrables en el conjunto de axiomas'; es la ausencia de la palabra 'demostrables' la que me ha confundido un poco.

Sin embargo...

Definición: Un conjunto de axiomas es consistente si no existe una fórmula \( P \) tal que \( P \) y \( -P \) sean a la vez demostrables.

..la palabra "demostrables" estaba allí, tan campante al final de la definición. ;)

Otra definición, que faltó en la lista anterior:

Definición: Un conjunto (o un sistema) de axiomas es completo si para todo enunciado \( P \) sucede que, o bien \( P \), o bien \( -P \), es demostrable.

Todo sistema inconsistente es trivialmente completo, pero no es ésa una completitud deseable.

<<                >>

16 Junio, 2009, 09:17 pm
Respuesta #75

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Vuelvo a tener dudas sobre el Axioma de Reemplazo.
¿No permite reemplazos demasiado arriesgados o generales?
Durante largo tiempo creí que se usaba para reemplazar una variable por una constante, o un ''calculito'' que involucra sólo constantes.
Pero el hecho de que se admitan también variables en el reemplazo, me parece extraño, con peligro de caer en alguna incoherencia, aunque no veo en realidad ninguna todavía...

Pasando a otra cosa.
Gustavo, en vuestro libro veo que ahora deberían seguir los axiomas de primer orden de la aritmética y la definición de recursiva de verdad, en ese orden.
¿Se puede dar una noción de verdad sin haber dado antes los axiomas de la aritmética?
Pregunto, porque veo que en la definición de verdad se usan numerales, y me cuesta aceptar que la noción de verdad dependa de la aritmética.

Tampoco entiendo bien el papel que los numerales juegan en todo esto.
Estuve leyendo el libro de "Nagel y Newman, El Teorema de Godel", y hace una distinción entre numerales y números, la cual creí que entendía, pero buscando en la lista de axiomas de "Godel \( \forall{} \)" no encuentro el momento a partir del cual se hace esa distinción (no quiere decir que no la haya). Así que ando algo mareado con el hecho de que se han de usar los mismos números naturales en la definición de verdad.

16 Junio, 2009, 09:53 pm
Respuesta #76

Gustavo Piñeiro

  • Visitante
1er pregunta: Se ha establecido que todo término contiene constantes o variables. En particular x es una variable. ¿Qué pasa si deseo reemplazar x por t, cuando t es un término que ''adentro'' contiene a la misma x?
¿No es esto algo mal definido, no queda algo recurrente e infinito, como producto de reemplazos sin fin?

Ya diste la respuesta en otro comentario. Sólo ratifico lo dicho allí: no hay ningún problema, ni sucede ninguna regresión infinita. En "x = x" podemos reemplazar "x" por, digamos, "x + 0" y obtenemos "x + 0 = x + 0".

2da pregunta: En cuanto a la restricción de los cuantificadores...
Si t es un término, es una lista de signos en la que no figura el signo de cuantificación \( \exists{} \).
Así que si pido que las variables que figuran en t no estén afectadas por cuantificadores, entiendo que esos cuantificadores son ''externos'' a t. Así que imagino que se refiere a cuantificadores que podrían aparecer dentro de F.
¿Pero qué significa exactamente la restricción?

En efecto, en el libro se muestra un ejemplo del sentido de esa restricción. Supongamos el enunciado \( \forall{x}\exists{y}(x\neq{}y) \). Si aplicamos el esquema lógico y reemplazamos x por 0 obtenemos la fórmula (intutivamente verdadera, aunque aún no hemos definido qué es la "verdad"): \( \exists{y}(0\neq{}y) \), pero si reemplazamos x por y (reemplazo "prohibido" porque es una variable afectada por un cuantificador) nos queda \( \exists{y}(y\neq{}y) \), que no querríamos que fuera demostrable.   

Una cuestión filosófica:
Para decidir si una expresión es un término o no lo es, tengo que rechazar por ejemplo las expresiones que tengan cuantificadores.
Cuando se da la definición de término, está bien, se hace de modo constructivo.
Pero ¿qué pasa si me dan una expresión t cualquiera, y debo determinar si es o no un término?
Para probarlo, debo pasar uno a uno por sus signos, y si encuentro un símbolo que no corresponde a constantes o variables o paréntesis, concluir que t no es un término.
Sin embargo, no estoy seguro de si la propiedad de ''no ser un término'' forma parte de las reglas que definen lo que es un término.
Me refiero a que yo me doy cuenta con mi propia razón que una expresión no es un término, pero no estoy seguro de si esto se deduce propiamente de las reglas dadas, las cuales se dan en ''positivo'' (o sea, para afirmar cuándo tengo un término), pero no en negativo (cuando deseo probar que algo no es un término).

"No ser un término", al menos en teoría, está perfectamente definido: una expresión no es un término si no puede ser construida siguiendo las reglas que permiten construir los términos (parece un trabalenguas, pero es así). Otra cuestión es dar un método práctico para determinar si una expresión dada es, o no es, un término. Tal método (o algoritmo, para ser más preciso) existe. No se reduce a ver meramente que no haya cuantificadores ni otros símbolos lógicos, ya que (((((0+ no los tiene y no es un término.

Creo (nunca lo había pensado antes) que ese método debería rastrear los paréntesis anidados que forman la expresión. Debe detectar los símbolos "más profundamente enterrados" entre paréntesis, ver que forman una expresión del tipo corercto (0 + x, 0.x, etc.) y de allí ir rastreabdo símbolos mientras va subiendo por los niveles de paréntesis. No sé si he sido claro (casi seguramente no), pero creo que por allí va la idea.

Saludos,

16 Junio, 2009, 10:06 pm
Respuesta #77

Numerarius

  • Aprendiz
  • Mensajes: 319
  • Karma: +0/-0
  • Sexo: Masculino
Se me ocurre una analogía que, tal vez, podría resultar útil.

La capacidad de reconocer que una fórmula lógica está bien construída se podría comparar (por ejemplo) a la capacidad que tiene un compilador para reconocer un programa en lenguaje Java.

En este sentido, me refería antes a que existen autómatas que reconocen cadenas sintácticamente correctas.

16 Junio, 2009, 10:40 pm
Respuesta #78

Fernando Revilla

  • Administrador
  • Mensajes: 10,849
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Bien, los términos de un lenguaje \( \mathcal{L} \) de primer orden quedan perfectamente determinados por las siguientes reglas:

(i) Las variables \( x_i \) y las constantes \( a_j \) del lenguaje son términos.
(ii) Si \( f_i^n \) es letra de función y \( t_1,\ldots,t_n \) son términos de \( \mathcal {L} \) entonces, \( f_i^n(t_1,\ldots,t_n) \) es un término de \( \mathcal{L} \).
(iii) El conjunto de todos los términos de \( \mathcal{L} \) es el generado por (i) y (ii).

Es decir, las reglas anteriores "deciden" si una expresión de \( \mathcal{L} \) es o no término.

Saludos.

16 Junio, 2009, 10:53 pm
Respuesta #79

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Lo que noto es que cuando vaya a hacer la rutina que reconozca si cierta expresión satisface el Axioma de Reemplazo, no va a ser sencillo. O, al menos, va a haber que andarse con cuidado.
Hasta que no haga el/los programas, no voy a convencerme de que ciertas reglas ''deciden'' o no tal o cual cosa.

Phidias... Eso del ''conjunto de todos los términos'' no lo veo bien en este contexto en que no hay conjuntos.
Esa totalidad no está bien definida.
Uno sólo puede estar seguro de una afirmación del tipo:
"Si t satisface tal y tal, entonces t es un término".
Pero no se puede decir metamatemáticamente algo como:
"Para todo t tal que blablabla: t es un término".

De manera que sólo puedo observar cada t, uno a uno.
Hablar de todos los t es algo que se entiende, pero no es finitario. ¿Prohibido? Creo que sí.