03 Abril, 2020, 03:00 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Conjunto de testigos  (Leído 2868 veces)
0 Usuarios y 1 Visitante están viendo este tema.
pepito
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.618


Ver Perfil
« : 06 Febrero, 2014, 17:54 »

Hola, ¿cómo andan? Volví después de una larga ausencia con una duda que me aqueja. Me dicen lo siguiente:

Si [texx]\Sigma[/texx] es un conjunto de sentencias en un lenguaje [texx]\mathcal{L}[/texx] y [texx]C[/texx] es un conjunto formado por algunas de las constantes de [texx]\mathcal{L}[/texx], entonces [texx]C[/texx] es un conjunto de testigos para [texx]\Sigma[/texx] en [texx]\mathcal{L}[/texx] si para toda fórmula [texx]\alpha[/texx] en la que ninguna variable ocurre libre salvo eventualmente [texx]x[/texx], hay alguna constante [texx]c\in C[/texx] para la cual [texx]\Sigma\vdash\exists x\alpha\to\alpha_c^x[/texx]

Me dan como ejemplo lo siguiente: [texx]\mathcal{L}[/texx] es un lenguaje con un único relator [texx]<[/texx], ningún funtor, y una constante [texx]c_q[/texx] para cada [texx]q\in\mathbb{Q}[/texx]. [texx]\Sigma[/texx] incluye las siguientes sentencias:

1) [texx]c_q<c_p[/texx] para todos [texx]q,p\in\mathbb{Q}[/texx] tales que [texx]q<p[/texx]
2) [texx]\forall x(\lnot x<x)[/texx]
3) [texx]\forall x\forall y(x<y\lor x=y\lor y<x)[/texx]
4) [texx]\forall x\forall y\forall z(x<y\to(y<z\to x<z))[/texx]
5) [texx]\forall x\forall y(x<y\to\exists z(x<z\land z<y))[/texx]
6) [texx]\forall x\exists y(x<y)[/texx]
7) [texx]\forall x\exists y(y<x)[/texx]

Me dicen que entonces [texx]C=\{c_q:q\in\mathbb{Q}\}[/texx] es un conjunto de testigos para [texx]\Sigma[/texx] en [texx]\mathcal{L}[/texx], y no tengo idea de cómo terminar de probarlo. Lo que pude probar hasta ahora es que si uno elimina cualquier sentencia de [texx]\Sigma[/texx], esto deja de ser cierto, o sea que en la prueba va a haber que usarlas todas. Con lo que hice hasta ahora, para terminar me bastaría probar que para toda fórmula [texx]\alpha[/texx] en la que ninguna variable ocurre libre salvo eventualmente [texx]x[/texx] se tiene

[texx]\Sigma\cup\{\alpha_{c_q}^x:q\in\mathbb{Q}\}\vdash\alpha[/texx]

¿Cómo se podría probar esto último? O si no, ¿cómo se podría probar por otro camino que [texx]C[/texx] es un conjunto de testigos para [texx]\Sigma[/texx] en [texx]\mathcal{L}[/texx]?
En línea

"...parecido pero nada que ver"
pepito
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.618


Ver Perfil
« Respuesta #1 : 11 Febrero, 2014, 23:10 »

Bueno, me parece que lo logré, sólo que las deducciones formales las pensé pero no las escribí, es que si no esto se hace interminable. De paso, lo que sugería en el mensaje original no sirve para nada.

Lema 1: Si [texx]\alpha[/texx] es [texx]\tau_1\vee\ldots\vee\tau_h[/texx] para ciertas fórmulas atómicas [texx]\tau_1\ldots\tau_h[/texx], entonces para cualquier variable [texx]x[/texx] existe una fórmula [texx]\beta[/texx] sin cuantificadores tal que [texx]\Sigma\vdash\forall x\alpha\leftrightarrow\beta[/texx]. Es más, en [texx]\beta[/texx] sólo ocurren las variables que ocurren en [texx]\alpha[/texx] y que no son [texx]x[/texx].

Spoiler: Idea de la demostración (click para mostrar u ocultar)

Observación:

Acá se puede asumir que toda fórmula [texx]\varphi[/texx] sin cuantificadores está compuesta únicamente por fórmulas atómicas, conectores [texx]\vee[/texx] y [texx]\wedge[/texx] y paréntesis (sin [texx]\lnot[/texx] ni [texx]\rightarrow[/texx]). Es decir, si [texx]\varphi[/texx] es una fórmula sin cuantificadores entonces existe una fórmula [texx]\tilde{\varphi}[/texx] compuesta únicamente por fórmulas atómicas, conectores [texx]\vee[/texx] y [texx]\wedge[/texx] y paréntesis tal que [texx]\Sigma\vdash\varphi\leftrightarrow\tilde{\varphi}[/texx]. Si [texx]\varphi[/texx] es atómica, no hay nada que probar. Si [texx]\varphi[/texx] es [texx]\lnot\alpha[/texx] para cierta fórmula atómica [texx]\alpha[/texx], la sentencia 3 permite afirmar esto. Si [texx]\varphi[/texx] es [texx]\lnot\alpha[/texx] para cierta fórmula [texx]\alpha[/texx] que no es atómica, se asume por hipótesis inductiva que esto es cierto para [texx]\alpha[/texx] y se aplican las propiedades distributivas de [texx]\lnot[/texx] respecto a [texx]\vee[/texx] y [texx]\wedge[/texx]. Y si [texx]\varphi[/texx] es [texx]\alpha\rightarrow\beta[/texx], entonces [texx]\varphi[/texx] es [texx](\lnot\alpha)\vee\beta[/texx], y entonces se obtiene el resultado asumiendo por hipótesis inductiva que es cierto para [texx]\lnot\alpha[/texx] y [texx]\beta[/texx].

Es más, usando inducción y las propiedades distributivas de [texx]\vee[/texx] y [texx]\wedge[/texx] es muy fácil ver que para esa [texx]\tilde{\varphi}[/texx] se tiene que [texx]\vdash\tilde{\varphi}\leftrightarrow(\tau_1^1\vee\ldots\vee\tau_{h_1}^1)\wedge\ldots\wedge(\tau_1^r\vee\ldots\vee\tau_{h_r}^r)[/texx] para ciertas fórmulas atómicas [texx]\tau_1^1,\ldots,\tau_{h_1}^1,\ldots,\tau_1^r,\ldots\tau_{h_r}^r[/texx]. Como además

[texx]\vdash\forall x((\tau_1^1\vee\ldots\vee\tau_{h_1}^1)\wedge\ldots\wedge(\tau_1^r\vee\ldots\vee\tau_{h_r}^r))\leftrightarrow\forall x(\tau_1^1\vee\ldots\vee\tau_{h_1}^1)\wedge\ldots\wedge\forall x(\tau_1^r\vee\ldots\vee\tau_{h_r}^r)[/texx]

el lema 1 se puede generalizar a:

Lema 2: Si [texx]\alpha[/texx] es una fórmula sin cuantificadores, entonces para cualquier variable [texx]x[/texx] existe una fórmula [texx]\beta[/texx] sin cuantificadores tal que [texx]\Sigma\vdash\forall x\alpha\leftrightarrow\beta[/texx]. Es más, en [texx]\beta[/texx] sólo ocurren las variables que ocurren en [texx]\alpha[/texx] y que no son [texx]x[/texx].

Y de ahí, por inducción se prueba muy fácilmente lo que resuelve todo este lío:

Proposición: Si [texx]\alpha[/texx] es una fórmula cualquiera en este lenguaje entonces existe una fórmula [texx]\beta[/texx] sin cuantificadores tal que [texx]\Sigma\vdash\alpha\leftrightarrow\beta[/texx]. Es más, en [texx]\beta[/texx] sólo ocurren las variables que ocurren libres en [texx]\alpha[/texx].

Bueno, con ese resultado en mano y usando la observación, las posibilidades para una fórmula [texx]\alpha[/texx] en la que no ocurren variables libres salvo eventualmente [texx]x[/texx] son muy limitadas (esencialmente). Estudiando los pocos casos posibles y aplicando las sentencias de [texx]\Sigma[/texx] ya se puede probar que [texx]C[/texx] es un conjunto de testigos para [texx]\Sigma[/texx] en este lenguaje.
En línea

"...parecido pero nada que ver"
Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.091


Ver Perfil WWW
« Respuesta #2 : 12 Febrero, 2014, 07:22 »

Otra forma de probarlo es la siguiente:

Para cada fórmula [texx]\phi(x_1,\ldots, x_n)[/texx] en la que no aparezcan constantes, se cumple:

[texx]\Sigma\vdash \forall x_1\cdots x_n y_1\cdots y_n(x_1<\cdots < x_n\land y_1<\cdots < y_n\rightarrow (\phi(x_1,\ldots, x_n)\leftrightarrow \phi(y_1,\ldots, y_n))) [/texx],

Esto signfica que el hecho de que [texx]n[/texx] objetos cumplan o no una fórmula sólo depende de cómo están ordenados ellos mismos.

La prueba es por inducción sobre la longitud de [texx]\phi[/texx]. Si [texx]\phi[/texx] es atómica los dos casos posibles, [texx]x_i<x_j[/texx] y [texx]x_i=x_j[/texx] son inmediatos.

Si vale para [texx]\phi[/texx] vale trivialmente para [texx]\lnot \phi[/texx] y para [texx]\phi\lor \psi[/texx], o para cualquier otro conector lógico (con probarlo para uno es suficiente).

El único caso que requiere un poco de atención es [texx]\forall\phi(x,x_1,\ldots, x_n)[/texx]. Para probar este caso suponemos

[texx]x_1<\cdots < x_n\land y_1<\cdots < y_n[/texx] y a su vez suponemos [texx]\forall x\phi(x,x_1,\ldots, x_n)[/texx].

Para probar [texx]\forall y \phi(y,y_1,\ldots, y_n)[/texx] tomamos un [texx]y[/texx] arbitrario y usamos los axiomas de [texx]\Sigma[/texx] para probar que, o bien [texx]y=y_i[/texx] para un [texx]i[/texx], o bien [texx]y<y_1<\cdots <y_n[/texx], o bien [texx]y_1<\cdots < y_n<y[/texx], o bien [texx]y_1<\cdots <y_i<y<y_{i+1}<\cdots <y_n[/texx] para un [texx]i[/texx].

Fijado uno de los casos, los axiomas de [texx]\Sigma[/texx] implican que existe un [texx]x[/texx] que cumple el mismo caso pero con los [texx]x_i[/texx] en lugar de los [texx]y_i[/texx].

Entonces tenemos [texx]\phi(x,x_1,\ldots, x_n)[/texx] y por la hipótesis de inducción aplicada a [texx]\phi[/texx] llegamos a que [texx]\phi(y,y_1,\ldots, y_n)[/texx], luego [texx]\forall y\,\phi(y,y_1,\ldots, y_n)[/texx].

Esto termina la prueba.

Ahora, si suponemos [texx]\exists x\,\alpha[/texx], sean [texx]c_{q_1},\ldots c_{q_n}[/texx] todas las constantes que aparecen en [texx]\alpha[/texx], enumeradas de modo que [texx]q_1<\cdots <q_n[/texx].

Entonces [texx]\alpha \equiv \phi(x,c_{q_1},\ldots, c_{q_n})[/texx], donde [texx]\phi(x,x_1,\ldots, x_n)[/texx] no tiene constantes.

Los axiomas de [texx]\Sigma[/texx] permiten probar, supuesto [texx]\phi(x,c_{q_1},\ldots, c_{q_n})[/texx], que o bien [texx]x<c_{q_1}<\cdots <c_{q_n}[/texx], o bien [texx]c_{q_1}<\cdots < c_{q_n}<x[/texx], o bien existe un [texx]i[/texx] tal que [texx]c_{q_1}<\cdots < c_{q_1}<x<c_{c_{i+1}}<\cdots < c_{q_n}[/texx], y podemos tomar un número racional [texx]q[/texx] tal que [texx]c_q[/texx] esté en el mismo caso. Entonces, particularizando lo que hemos probado antes al caso en que los [texx]y_i[/texx] son las constantes [texx]c_{q_i}[/texx] y [texx]c_q[/texx], concluimos que se cumple [texx]\phi(c_q,c_{q_1},\ldots, c_{q_n})[/texx], es decir, [texx]\alpha^x_{c_q}[/texx], como había que probar.

La prueba se aligera bastante si en lugar de razonar sintácticamente, razonamos semánticamente, es decir, para probar [texx]\Sigma\vdash\exists x\alpha\to\alpha_c^x[/texx] basta ver que la fórmula es verdadera en todo modelo de [texx]\Sigma[/texx], pero un modelo de [texx]\Sigma[/texx] no es más que un conjunto totalmente ordenado sin máximo ni mínimo denso en sí mismo en el que hemos "destacado" un suborden isomorfo a [texx]\mathbb Q[/texx]. Todo lo anterior puede traducirse a un razonamiento sobre un modelo fijo, y el argumento queda mucho más natural.
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.294

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #3 : 12 Febrero, 2014, 07:38 »

Una pregunta a cualquiera de ambos: no entiendo el contexto del problema.
Cuando se habla aquí de, por ejemplo, [texx]\Sigma[/texx] como "conjunto de sentencias", ¿en qué sentido se considera conjunto?
¿Es éste un problema dentro de la teoría formal de conjuntos, o es metamatemático?

La misma duda para los "modelos".
¿Son conjuntos en el sentido usual?
Porque si lo son en sentido metamatemático, me cuesta aceptar que se puede hablar así:

pero un modelo de [texx]\Sigma[/texx] no es más que un conjunto totalmente ordenado sin máximo ni mínimo denso en sí mismo en el que hemos "destacado" un suborden isomorfo a [texx]\mathbb Q[/texx].

Todo lo que estás diciendo sobre los modelos de [texx]\Sigma[/texx] sé expresarlo en la teoría formal de conjuntos, pero no "en el aire". Si pudiera decir todo eso "metamatemáticamente", no necesitaría la teoría de conjuntos para nada, y haría matemática en el aire.

En línea

Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.091


Ver Perfil WWW
« Respuesta #4 : 12 Febrero, 2014, 07:53 »

Yo he dado por hecho que el contexto del problema es la teoría de modelos formalizada en la teoría de conjuntos, de manera que todo lo dicho (tanto por pepito como por mí) debe entenderse como teoremas de ZFC.

Ahora bien, con un poco de cuidado, sería posible considerar todos los razonamientos sin hacer referencia para nada a ninguna teoría de conjuntos. Entonces hay que entender que tenemos un lenguaje formal numerable (que apenas es más complicado que el lenguaje formal en el que se formaliza la teoría de conjuntos, y que puede manejarse metamatemáticamente igual que éste) y un conjunto (o colección, o como quieras llamarlo) de sentencias de dicho lenguaje formal. Tanto el argumento de pepito como el mío puede verse entonces como varios metateoremas sobre dicho lenguaje formal (argumentos que prueban que ciertas familias infinitas de fórmulas son demostrables a partir de cierta familia infinita de axiomas). Ninguno de ellos es esencialmente más complicado que los metateoremas que se demuestran sobre la teoría de conjuntos o sobre la aritmética de Peano, por ejemplo.

En este contexto, el último párrafo de mi mensaje anterior requeriría más precisiones (aunque, ya digo, no lo escribí pensando en este contexto). Si quisiéramos razonar semánticamente, una forma de poner en evidencia qué supone esto concretamente sería plantearlo así: si hubiera una fórmula [texx]\alpha[/texx] para la que no pudiera demostrarse [texx]\exists x\alpha\to\alpha_c^x[/texx], por el teorema de completitud, existiría un modelo numerable [texx]M[/texx] de [texx]\sigma[/texx] en el cual [texx]\exists x\alpha\to\alpha_c^x[/texx] sería falsa, y entonces todo el argumento expuesto en mi mensaje anterior nos llevaría a una contradicción.
En línea
pepito
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.618


Ver Perfil
« Respuesta #5 : 13 Febrero, 2014, 13:32 »

Vi tu prueba, Carlos, y creo entender por dónde va la cosa.

Yo he dado por hecho que el contexto del problema es la teoría de modelos formalizada en la teoría de conjuntos, de manera que todo lo dicho (tanto por pepito como por mí) debe entenderse como teoremas de ZFC.

Creería que sí, aunque no sé mucho de eso la verdad. Esto es de una serie de ejercicios que van guiando al lector hacia los teoremas de lógica proposicional, lógica de primer orden, computabilidad e incompletitud. Para definir los conceptos con los que se va a trabajar se apela a las mismas nociones previas de siempre (conjuntos, funciones, etcétera) y uno se encuentra permanentemente demostrando sus propiedades mediante las mismas técnicas de razonamiento con las que trabajaba en cualquier otra rama de la matemática, como si se tratara de una más de ellas, que no viene "antes" del resto (eso es lo que tengo entendido que significa el que sean teoremas de ZFC). A mí no me preocupa demasiado "usar la lógica para demostrar ciertas propiedades de la lógica" porque no veo todo esto como un intento de fundamentar al razonamiento matemático sino como un intento de estudiarlo. Estudiarlo, en principio, para averiguar sus alcances y sus limitaciones. De esa manera, ante un problema no resuelto uno eventualmente podría aplicar todo este estudio para decir algo como "con el mismo tipo de argumentación con el que vos pretenderías resolverlo, yo puedo demostrar que no se puede resolver", y entonces ya quedaría descartada la posibilidad de resolverlo mediante ese tipo de argumentación, a no ser que ese tipo de argumentación conduzca a contradicciones (como la que se presentaría acá, el que el problema en cuestión pueda y no pueda ser resuelto).

No sé, esa es la idea que me hago por ahora. Igual tengo recién al final de la guía la parte de incompletitud pero a una página de donde estoy ahora el teorema de completitud para lógica de primer orden, así que tendría que ver bien qué significan y en qué contexto se aplica cada uno de ellos.
En línea

"...parecido pero nada que ver"
Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.091


Ver Perfil WWW
« Respuesta #6 : 13 Febrero, 2014, 19:40 »

Ya he indicado en algunos hilos que los planteamientos de los libros y cursos de lógica por lo general me producen urticaria. Creo que, por el camino que describes, terminarás encontrando un círculo vicioso que no podrás despachar con los argumentos que das en el mensaje anterior, pero no es algo que ahora deba preocuparte. Si te lo terminas encontrando, ello debería hacerte cuestionar la forma de concebir los resultados que estás estudiando, pero no los argumentos que estás empleando, así que en ningún caso te encontrarás con que "lo que has estudiado no vale".

Como no me resisto a criticar un poco el ejercicio (es decir, criticar a quien lo haya considerado ilustrativo de algo, no a ti que lo estás siguiendo), me parece que es un ejemplo bastante atípico y, por lo tanto, nada representativo. Se aprovecha de una propiedad de indescirnibilidad de los conjuntos totalmente ordenados densos sin máximo ni mínimo que es muy peculiar y que nada tiene que ver con los sistemas de testigos que se construyen para probar el teorema de completitud. Quiero decir que, en efecto, es un caso en el que se cumple la definición, pero que la explicación de que se cumpla no tiene nada que ver con la explicación de cómo se consigue que se cumpla en otros sistemas deductivos a base de modificarlos un poco. Es como si para ilustrar la fauna de África te muestran un caniche que está ahora en África porque acompaña casualmente a un turista.

Pero bueno, no me hagas caso. Es que cuando veo una ocasión para despotricar sobre los libros de lógica la aprovecho.
En línea
pepito
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.618


Ver Perfil
« Respuesta #7 : 14 Febrero, 2014, 00:29 »

Ya he indicado en algunos hilos que los planteamientos de los libros y cursos de lógica por lo general me producen urticaria.

En defensa del curso puedo decir que nada de lo que puse en el mensaje anterior lo leí allí. Es sólo la idea que se hace alguien que a penas va por la mitad del mismo.

Creo que, por el camino que describes, terminarás encontrando un círculo vicioso que no podrás despachar con los argumentos que das en el mensaje anterior, pero no es algo que ahora deba preocuparte. Si te lo terminas encontrando, ello debería hacerte cuestionar la forma de concebir los resultados que estás estudiando, pero no los argumentos que estás empleando, así que en ningún caso te encontrarás con que "lo que has estudiado no vale".

La verdad, ahora me da mucha intriga saber cuál podría ser ese círculo vicioso. En principio me cuesta encontrar alguna objeción a definir algo que uno entiende que se comporta igual que el razonamiento matemático y estudiarlo, incluso si para ello se aplica esa misma forma de razonamiento. Las conclusiones a las que se llegue serían tan ciertas como cualquier otra dentro de las matemáticas. Bueno, en realidad ahora que lo escribo se me ocurre que tal vez la cosa pase por "¿qué tan ciertas son todas esas otras conclusiones?", o "¿qué es lo que las hace ciertas?". No sé, veremos.

Cuando termine con la parte de lógica de primer orden voy a leer entero tu artículo de la revista. Cierta vez lo había ojeado y me acuerdo que al final hablaba sobre el propósito de la lógica de primer orden (y que no tenía nada que ver con lo que escribo).

Como no me resisto a criticar un poco el ejercicio (es decir, criticar a quien lo haya considerado ilustrativo de algo, no a ti que lo estás siguiendo), me parece que es un ejemplo bastante atípico y, por lo tanto, nada representativo. Se aprovecha de una propiedad de indescirnibilidad de los conjuntos totalmente ordenados densos sin máximo ni mínimo que es muy peculiar y que nada tiene que ver con los sistemas de testigos que se construyen para probar el teorema de completitud. Quiero decir que, en efecto, es un caso en el que se cumple la definición, pero que la explicación de que se cumpla no tiene nada que ver con la explicación de cómo se consigue que se cumpla en otros sistemas deductivos a base de modificarlos un poco. Es como si para ilustrar la fauna de África te muestran un caniche que está ahora en África porque acompaña casualmente a un turista.

Ojo que en el curso se hace una aclaración parecida, aunque no a ese nivel, claro. Dice que este ejemplo definitivamente esta armado a propósito para que dé lo que tiene que dar, pero que no es representativo para el caso general. Me imagino que será para poner un ejemplo concreto de conjunto de testigos, porque si lo que uno hace después es "agregarlos por fuerza bruta", tal vez se termina trabajando con una noción demasiado abstracta sin entender lo que se está haciendo (creo yo).
En línea

"...parecido pero nada que ver"
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.294

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #8 : 14 Febrero, 2014, 08:42 »

El problema a lo mejor no está en el razonamiento, pero sí en que se está hablando de cosas que no tienen mucho sentido.

Por ejemplo, decís que C tiene un testigo [texx]c_q[/texx] para cada [texx]q\in\mathbb Q[/texx].
¿Qué es [texx]\mathbb Q[/texx]?
¿Y qué es el símbolo [texx]\in[/texx]?
¿Y qué es [texx]<[/texx] cuando escribís [texx]p<q[/texx]?

Habiendo seguido algunos años las cosas que escribe Carlos, imagino que eso se puede especificar de igual forma que es posible hacerlo con los números naturales, puesto que si aceptan los naturales "intuitivos", no hay mucha distancia a armarse un modelo de racionales en que esos símbolos tengan algún sentido.
Pero lo peligroso está en no advertir que se está haciendo abuso del formalismo matemático.

Por ejemplo, no podría hacerse lo mismo para reales (creo).
Si en el ejercicio cambiás [texx]\mathbb Q[/texx] por [texx]\mathbb R[/texx], ya no se puede hacer lo mismo, porque eso equivaldría a poder escribir una constante en [texx]\mathcal L[/texx] por cada "número real".
El único modo de introducir símbolos en [texx]\mathcal L[/texx] es en forma iterativa, de uno en uno. ¿Con qué iteración o método claramente establecido vas a introducir un testigo para cada número real?

Para racionales imagino algunas formas, pero para reales no.
Los números reales no están definidos con claridad fuera de una teoría formal.
(Y dentro de una las teorías formales tampoco  :sonrisa_amplia: ).
En línea

Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.091


Ver Perfil WWW
« Respuesta #9 : 14 Febrero, 2014, 11:12 »

Ya he indicado en algunos hilos que los planteamientos de los libros y cursos de lógica por lo general me producen urticaria.

En defensa del curso puedo decir que nada de lo que puse en el mensaje anterior lo leí allí. Es sólo la idea que se hace alguien que a penas va por la mitad del mismo.

No puse ese comentario a raíz de nada de lo que decías en tu mensaje, sino ante el mero hecho de que el problema planteado se considerara ilustrativo de algo relacionado con la prueba del teorema de completitud. No digo que el resultado en sí no sea interesante, sólo que en el contexto de la demostración del teorema de completitud es anecdótico.

La verdad, ahora me da mucha intriga saber cuál podría ser ese círculo vicioso. En principio me cuesta encontrar alguna objeción a definir algo que uno entiende que se comporta igual que el razonamiento matemático y estudiarlo, incluso si para ello se aplica esa misma forma de razonamiento. Las conclusiones a las que se llegue serían tan ciertas como cualquier otra dentro de las matemáticas.

Eso es cierto. No he querido decir que entender lo que estás estudiando como meros teoremas matemáticos sea incorrecto, carente de rigor, o que presente ninguna clase de "agujero lógico". Por el contrario, la lógica matemática (así formalizada, como parte de la teoría de conjuntos) es una disciplina matemática más en pie de igualdad con el álgebra, la topología, etc. y no hay nada que reprocharle.

Bueno, en realidad ahora que lo escribo se me ocurre que tal vez la cosa pase por "¿qué tan ciertas son todas esas otras conclusiones?", o "¿qué es lo que las hace ciertas?". No sé, veremos.

Por ahí van los tiros. El problema de considerar la lógica matemática como una mera rama más de las matemáticas (lo cual es totalmente legítimo y viable) es que impide extraer de ella las conclusiones que sería natural tratar de extraer. Trataré de explicarme:

No existe una definición operativa de "conjunto". Definir un conjunto como una "colección de objetos" tiene el mismo valor operativo que definir una recta como una línea que no se tuerce nunca. Eso no aprovecha para nada, y en su lugar es necesario enunciar una lista de axiomas (tanto en el caso de la geometría como en el de la teoría de conjuntos) que determinen las propiedades de los conceptos básicos "indefinibles de modo que la definición realmente ayude a demostrar algo". En el caso de la teoría de conjuntos, dichos axiomas (o los más habituales) son los de ZFC.

Cuando uno enuncia una teoría axiomática, la pregunta natural es: ¿existen realmente unos objetos que satisfagan los axiomas? o, dicho de otro modo: ¿cuando deducimos cosas de nuestros axiomas, estamos hablando de algo o sólo son palabras sobre objetos inexistentes?

El teorema de completitud proporciona una respuesta parcial a esta pregunta: dice que la condición necesaria y suficiente para que existan unos objetos que cumplan unos axiomas dados es que dichos axiomas no sean contradictorios.

Visto como teorema de ZFC, este teorema tiene aplicaciones interesantes, como cualquier otro teorema matemático relevante, pero, visto así, no tiene sentido usarlo como respuesta (parcial) a la pregunta de si existen unos objetos que cumplen los axiomas de la teoría de conjuntos:

1) Supongamos que la teoría de conjuntos es consistente.

2) Demostramos en ella el teorema de completitud, que nos dice que, admitiendo que sea consistente, existen unos objetos que cumplen los axiomas de la teoría de conjuntos.

Entonces:

3) ¿Tenemos que creernos que existen unos objetos que cumplen los axiomas de la teoría de conjuntos (supuesta consistente) porque en ella hemos demostrado que existen unos objetos que cumplen los axiomas de la teoría de conjuntos?

Eso es como creer que el presunto asesino es inocente porque le preguntamos si ha matado a alguien y nos asegura que no.

Por el contrario (y aquí discrepamos argentinator y yo, no en el sentido de que argentinator afirme lo contrario que yo, sino en el de que no acaba de creérselo) es posible sostener que el teorema de completitud es verdadero sin apoyarse para ello en los axiomas de la teoría de conjuntos. (En realidad, no sólo argentinator discrepa de esto, sino que aquí entramos en el terreno de la filosofía matemática, en la que puedes encontrarte todo un abanico de posturas, desde la más radical hasta la más disparatada, así que toma con cautela lo que digo, pues no puedo decir que con lo que digo sea objetivo.)

Si llegamos a convencernos de que el teorema de completitud no sólo es un teorema de ZFC, sino que es un hecho verdadero sobre lenguajes formales, en un sentido de "verdadero" que no tiene nada que ver con "demostrable en tal o cual teoría axiomática", entonces podemos aplicarlo plenamente a ZFC sin caer en el círculo vicioso del "sé que es inocente porque él asegura que lo es".

En este sentido, el teorema de completitud es el más sutil de los resultados para los que "conviene tener" un argumento que los justifique independiente de toda teoría axiomática, porque sucede que su prueba no es constructiva (y no puede haber ninguna que lo sea). El número de matemáticos dispuestos a aceptar como "verdades absolutas" los resultados con pruebas constructivas es mucho mayor que el de los que aceptan también argumentos no constructivos. Yo desde luego no aceptaría casi ningún argumento no constructivo, pero creo que la prueba del teorema de completitud presenta requisitos suficientes como para que podamos afirmar que el modelo que construye es "algo real, objetiva y unívocamente determinado", no en el sentido de "físicamente real", claro, sino en el mismo sentido en que podemos decir que [texx]7[/texx] es primo, y que eso no depende de ninguna clase de consideración subjetiva. (Obviamente, podríamos llamar "primo" a otra cosa, pero eso sería hacer trampa en este contexto: fijada la definición de "primo", queda inequívocamente determinado qué números son primos y cuáles no, y eso no depende de que tal o cual axiomática sea consistente o no.)

Cuando termine con la parte de lógica de primer orden voy a leer entero tu artículo de la revista. Cierta vez lo había ojeado y me acuerdo que al final hablaba sobre el propósito de la lógica de primer orden (y que no tenía nada que ver con lo que escribo).

Bueno, no creo que ni yo ni nadie pueda decir "el propósito de la lógica de primer orden" es éste o aquél. La lógica de primer orden se puede estudiar con fines diversos, a los que corresponderán otros tantos enfoques diversos. Lo que digo ahí es que a menudo se presenta un curso de lógica como un curso de "formación básica" para un estudiante de matemáticas y que, en cambio, lo que se presenta en esa clase de cursos es una deformación espeluznante de la lógica, que lleva a los alumnos a formarse una idea muy equivocada. De hecho, a menudo se forman la idea de que, en la práctica, la lógica no aprovecha para nada, pues no tiene realmente nada que ver con lo que hace un matemático cotidianamente, y llevan razón (si entendemos por "lógica" lo que se les enseña).

Ojo que en el curso se hace una aclaración parecida, aunque no a ese nivel, claro. Dice que este ejemplo definitivamente esta armado a propósito para que dé lo que tiene que dar, pero que no es representativo para el caso general. Me imagino que será para poner un ejemplo concreto de conjunto de testigos, porque si lo que uno hace después es "agregarlos por fuerza bruta", tal vez se termina trabajando con una noción demasiado abstracta sin entender lo que se está haciendo (creo yo).

Ah, pues eso dice mucho en favor de tu curso. Pero sigo pensando que el ejemplo no ayuda a entender realmente lo que se está haciendo, porque cuando uno reflexiona sobre ese ejemplo en concreto llega a entender la curiosa situación de que en un modelo puede haber unos cuantos objetos "distinguidos" de modo que cualquier propiedad que cumplan objetos cualesquiera la cumplen también esos objetos, lo cual es bastante insólito, mientras que lo que se hace realmente al demostrar el teorema de completitud es algo mucho más natural y directo: asegurarse de tener un nombre (en forma de una constante) para cada uno de los objetos de los que podemos hablar a partir de nuestros axiomas, aunque no sea de forma unívoca (si podemos hablar de tigres, elegimos un nombre para un tigre, aunque pueda haber muchos otros anónimos y no sepamos precisar a cuál nombramos), para después tomar como objetos del modelo que construimos a los propios nombres (salvo una relación de equivalencia para que la igualdad tenga su significado previsto).
En línea
pepito
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.618


Ver Perfil
« Respuesta #10 : 15 Febrero, 2014, 00:35 »

argentinator:

Al principio del curso se aclara que sólo se va a trabajar con lenguajes con cantidades a lo sumo numerables de símbolos. Se menciona que muchos de los resultados también son ciertos para lenguajes no numerables (dando a entender que existen), pero que eso ya requiere "maquinaria más pesada".

Por supuesto que usar la palabra "numerable" ya implica un montón de cosas. La idea que yo me hice de esto desde el principio es esa que mencionás de los naturales "intuitivos". Es que es imposible arrancar sin un conjunto de naturales, desde el momento en que uno dice que un lenguaje tiene, entre otras cosas, constantes [texx]c_0,c_1,c_2,\ldots[/texx]. Ahora, como uno puede explicitar una biyección entre los naturales y [texx]\mathbb{Q}[/texx], se puede reemplazar esos subíndices por racionales sin problemas, y también se entiende los que significa [texx]<[/texx] (para mí). Pero no creo que sea un abuso del formalismo matemático.

Carlos:

cuando uno reflexiona sobre ese ejemplo en concreto llega a entender la curiosa situación de que en un modelo puede haber unos cuantos objetos "distinguidos" de modo que cualquier propiedad que cumplan objetos cualesquiera la cumplen también esos objetos

Es que en una primera lectura eso es esencialmente la definición de conjunto de testigos, más allá de lo que uno vaya a hacer después.

lo cual es bastante insólito

Súper insólito, diría yo. Mi reacción al leer esa definición fue "bueno, pero ¿podré diseñar un lenguaje y ciertas sentencias en él de forma que pueda afirmar que con algunas de las constantes se conforma un conjunto de testigos, o estoy hablando de una situación que nunca voy a poder observar?".

En cuanto al resto, creo entenderte. El ejemplo de los números primos me parece lo más ilustrativo. Es que, te digo la verdad, sin haber estudiado "qué viene primero, si el huevo o la gallina" (o sea, teoría axiomática de conjuntos), por ahora nunca sé (ni me detengo a indagar) cuándo estoy asumiendo que tal o cual teoría es consistente y cuándo estoy simplemente aplicando la capacidad innata que tenemos todos los humanos de reconocer lo universalmente cierto. Tampoco me detengo a indagar si habrá alguna diferencia entre una cosa y la otra. Pero bueno, voy a tener en cuenta todo esto y cuando tenga un entendimiento más amplio te digo qué me parece.
En línea

"...parecido pero nada que ver"
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.294

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #11 : 15 Febrero, 2014, 01:24 »

Cita
aplicando la capacidad innata que tenemos todos los humanos de reconocer lo universalmente cierto

Para mí hablar así es puro autoengaño.
Aún suponiendo que fuera cierto (que yo no me lo creo, ni hace falta tampoco) que el ser humano tiene una capacidad innata para reconocer lo "universalmente cierto", eso no quiere decir que lo que estás afirmando como cierto en determinado contexto sea "universalmente cierto", y por lo tanto no es claro que esté bien justificado "así" eso que estás afirmando.

Por otro lado, no sé si "numerable" intuitivamente hablando quiere decir lo mismo que "numerable" en teoría de conjuntos.
De hecho, no puede ser lo mismo, porque si lo fuera, y dado que se dice (o demuestra) que la teoría de conjuntos tiene un modelo cuyo universo es "numerable", caeríamos en un absurdo.
Es por este tipo de cosas que no me cuadra que se tomen estas cosas con tanta ligereza, cuando en realidad son contextos diferentes, y que funcionan distinto.
En línea

pepito
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.618


Ver Perfil
« Respuesta #12 : 15 Febrero, 2014, 07:10 »

Cita
aplicando la capacidad innata que tenemos todos los humanos de reconocer lo universalmente cierto
Para mí hablar así es puro autoengaño.
Aún suponiendo que fuera cierto (que yo no me lo creo, ni hace falta tampoco) que el ser humano tiene una capacidad innata para reconocer lo "universalmente cierto", eso no quiere decir que lo que estás afirmando como cierto en determinado contexto sea "universalmente cierto", y por lo tanto no es claro que esté bien justificado "así" eso que estás afirmando.

Es que lo decía en un sentido mucho más inocente, como vos mismo dijiste cierta vez:

Cita de: argentinator
Tengo el problema de que no soy capaz de tildar a nadie de "loco".
No razona el que no quiere.

Si yo sé que [texx]p[/texx] implica [texx]q[/texx] y también sé que no ocurre [texx]q[/texx], eso me permite asegurar que no ocurre [texx]p[/texx]. Eso es universalmente cierto, y el que no lo reconoce así es porque no quiere.
En línea

"...parecido pero nada que ver"
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.294

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #13 : 15 Febrero, 2014, 08:59 »

Bueno, no sé si estamos hablando exactamente de "lo mismo".
Mejor plantearé mis propias dudas en otro hilo.
En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.294

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #14 : 15 Febrero, 2014, 09:04 »

(En realidad la última respuesta de pepito da para seguir discutiendo, porque le ví la trampa enseguida... pero no veo que sea una discusión fructífera).
En línea

Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.091


Ver Perfil WWW
« Respuesta #15 : 15 Febrero, 2014, 09:44 »

¿Nunca habéis visto en los dibujos animados que al gato se le aparece un angelito en un hombro y un demonio en el otro, y cada uno le aconseja lo opuesto que el otro? Pues tengo la sensación de que los tres estamos representando esa escena, aunque lo único claro es que pepito es el gato.

Súper insólito, diría yo. Mi reacción al leer esa definición fue "bueno, pero ¿podré diseñar un lenguaje y ciertas sentencias en él de forma que pueda afirmar que con algunas de las constantes se conforma un conjunto de testigos, o estoy hablando de una situación que nunca voy a poder observar?".

Pues a eso me refería. A que tu pregunta es natural y la respuesta que da ese ejemplo es artificial. La respuesta natural es decir: déjate de "milagros" asociados al comportamiento de los números naturales y los órdenes densos y piensa en el caso "normal", que es muy simple y natural: enumera todas las fórmulas que afirman la existencia de un objeto y añade al lenguaje formal una constante para cada una junto con el axioma de que dicha constante satisface lo que su fórmula asociada dice que le pasa a algún objeto.

En cuanto al resto, creo entenderte. El ejemplo de los números primos me parece lo más ilustrativo. Es que, te digo la verdad, sin haber estudiado "qué viene primero, si el huevo o la gallina" (o sea, teoría axiomática de conjuntos), por ahora nunca sé (ni me detengo a indagar) cuándo estoy asumiendo que tal o cual teoría es consistente y cuándo estoy simplemente aplicando la capacidad innata que tenemos todos los humanos de reconocer lo universalmente cierto. Tampoco me detengo a indagar si habrá alguna diferencia entre una cosa y la otra. Pero bueno, voy a tener en cuenta todo esto y cuando tenga un entendimiento más amplio te digo qué me parece.

El problema lo detectó ya Francisco de Goya, cuando pintó los grabados que tituló "El sueño de la razón produce monstruos". Razonando, razonando, puedes llegar a contradicciones relacionadas con "el conjunto de todos los conjuntos", o con "el menor número natural no definible en menos de doce palabras" y en muchas otras situaciones que uno puede en principio calificar de "bobadas" y no pensar más en ellas, pero que en realidad muestran que si "razonamos" sin control alguno no podemos fiarnos de nuestras conclusiones. Frege diseñó con sumo esmero una teoría de conjuntos, con una precisión lógica que raya lo insoportable, y nada de ello impidió que fuera contradictoria, porque permitía definir el conjunto de todos los conjuntos que no se pertenecen a sí mismos.

Eso no significa (y aquí es donde empiezo a cuchichearte al oído que no hagas caso de argentinator mientras te tiro de la manga  :malvado:) que no podamos razonar con seguridad al margen de una teoría axiomática que nos marque exactamente qué podemos decir y qué no. Más aún, afirmo que una teoría axiomática nunca podrá marcar correctamente qué podemos razonar y qué no, porque las teorías axiomáticas son incapaces de capturar "bien" algunas nociones fundamentales, como la de finitud. No creo que merezca la pena que desarrolle aquí esta idea (que necesitaría desarrollar mucho para que pueda ser entendida) porque ya la he desarrollado bastante en varios hilos que se pueden consultar. Quizá el principal sea http://rinconmatematico.com/foros/index.php?topic=36072.0.

Sólo dire, de forma muy resumida, que no es lo mismo razonar sobre objetos como los números naturales, de los que tenemos criterios objetivos para precisar qué significa que una afirmación sobre ellos sea verdadera o falsa (al margen de que podamos decidir cuál es el caso) que sobre objetos como los números reales, sobre los que hay afirmaciones que, no sólo no podemos demostrar que sean verdaderas o falsas, sino que en realidad no tenemos ningún criterio para dar un significado objetivo a que sean verdaderas o que sean falsas. Es para razonar sobre esta clase de objetos, de los que realmente no tenemos ninguna representación objetiva (podemos pensar sobre ellos, pero no "experimentar" sobre ellos, como podemos "experimentar con los números) para lo que resulta imprescindible una teoría axiomática.

Bueno, una aclaración más: no necesitamos una teoría axiomática para razonar sobre objetos geométricos (euclídeos) de tres dimensiones, pero sí que resulta imprescindible una axiomática para razonar sobre objetos geométricos no euclídeos de tres dimensiones o sobre objetos de más de tres dimensiones en cualquier geometría. En esencia, lo que sucede es que una parte de la teoría de conjuntos es "tridimensional euclídea" y podemos enfrentarnos a ella sin axiomas ni nada, y otra es "no euclídea" o "de dimensión alta" y ahí sin axiomas no somos nada.

Por otro lado, no sé si "numerable" intuitivamente hablando quiere decir lo mismo que "numerable" en teoría de conjuntos.

No lo es. Cuando decimos que un conjunto es numerable "de verdad" queremos decir que existe una forma objetiva de asignar a cada uno de sus objetos un número natural, mientras que la definición de "numerable" en teoría de conjuntos añade necesariamente una condición adicional que es totalmente artificial (pero inevitable): dicha asignación tiene que ser codificable mediante un conjunto.

De hecho, no puede ser lo mismo, porque si lo fuera, y dado que se dice (o demuestra) que la teoría de conjuntos tiene un modelo cuyo universo es "numerable", caeríamos en un absurdo.

Claro. Porque podemos asignar un número natural a cada número real del modelo (luego sus números reales son numerables) pero no hay ningún objeto en el modelo (ningún conjunto para esa interpretación de la palabra "conjunto") que codifique esa asignación. Por eso el conjunto de los números reales no es numerable en el sentido de la teoría de conjuntos, porque falla la condición artificial inevitable si uno quiere formalizar la idea de numerabilidad.

Es por este tipo de cosas que no me cuadra que se tomen estas cosas con tanta ligereza, cuando en realidad son contextos diferentes, y que funcionan distinto.

Ciertamente, tomarse esas cosas a la ligera es primero ingenuo y luego insensato, si uno persiste en ello.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!