Autor Tema: Formalización de la lógica

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

21 Octubre, 2020, 07:50 pm
Leído 1800 veces

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 103
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
En el libro de Carlos Ivorra de Lógica matemática, hay una cosa que no entiendo. En el capítulo de La formalización de la lógica, en la página 303, se define una fórmula con dos variables libres y una de la partes de la fórmula dice
\( 2|(n-i)\wedge{s_{i+1}}=Λxs_{i}\vee{2\perp{(n-i)\wedge{s_{i+1}}=∃xs_{i}}} \)

El símbolo \( \perp{} \) equivale a un descriptor tachado.

No entiendo que aparezca un 2 ahí. Entiendo que lo que quiere expresar la fórmula es que cada elemento de la sucesión va alternando cuantificadores existenciales o universales en función de si (n-i) es par o no, verdad? Pero por qué pone un 2 antes del descriptor?

Inmediatamente después se dice todas las variables no acotadas pueden acotarse por el término \( Δ_{1} \)
\( ((Rα)^{\leq{l(α)}})^{n+1}\cup{Rα} \)

Qué significa exactamente esto último? Entiendo que es el rango de α, que serían todas las expresiones que componen α, y por tanto, sería como acotar a través de “solo las variables que estén en α”. Pero el primer término de la unión no es ya eso? Es decir, el rango de α menor o igual a la longitud de α no incluye ya todas las variables de α? Por qué se lo eleva a n+1 luego, siendo n+1 la longitud de s, donde está incluido α? Por qué se añade por unión otra vez el rango de α?

21 Octubre, 2020, 09:23 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 2,358
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
En el libro de Carlos Ivorra de Lógica matemática, hay una cosa que no entiendo. En el capítulo de La formalización de la lógica, en la página 303, se define una fórmula con dos variables libres y una de la partes de la fórmula dice
\( 2|(n-i)\wedge{s_{i+1}}=Λxs_{i}\vee{2\perp{(n-i)\wedge{s_{i+1}}=∃xs_{i}}} \)

El símbolo \( \perp{} \) equivale a un descriptor tachado.

No entiendo que aparezca un 2 ahí. Entiendo que lo que quiere expresar la fórmula es que cada elemento se la sucesión va alternando cuantificadores existenciales o universales en función de si (n-i) es par o no, verdad? Pero por qué pone un 2 antes del descriptor?

No es ningún descriptor. Es un "no divide", \( \not\mid \). En palabras, el fragmento que has puesto quiere decir "(\( 2 \) divide a \( n-i \) y \( s_{i+1} = \forall x s_i \)) o (\( 2 \) no divide a \( n-i \) y \( s_{i+1} = \exists x s_i \))".

Vamos, es lo que dices: que \( \alpha \) se obtiene a partir de una fórmula \( \Delta_0 \) poniendo \( n \) cuantificadores alternados, donde el más externo es un \( \exists \).

Citar
Inmediatamente después se dice todas las variables no acotadas pueden acotarse por el término \( Δ_{1} \)
\( ((Rα)^{\leq{l(α)}})^{n+1}\cup{Rα} \)

Qué significa exactamente esto último? Entiendo que es el rango de α, que serían todas las expresiones que componen α, y por tanto, sería como acotar a través de “solo las variables que estén en α”. Pero el primer término de la unión no es ya eso? Es decir, el rango de α menor o igual a la longitud de α no incluye ya todas las variables de α? Por qué se lo eleva a n+1 luego, siendo n+1 la longitud de s, donde está incluido α? Por qué se añade por unión otra vez el rango de α?

Esto es para la fórmula completa. Hay dos cuantificadores que no están acotados: \( \exists s (s \in SucCad(\mathcal{L}_a) \dots \) y \( \exists x (x \in Var(\mathcal{L}_a) \dots  \).
Para ver que la fórmula completa es \( \Delta_1 \) hay que ver que esos cuantificadores se pueden acotar. Entonces, analizando la fórmula se ve que en el primer cuantificador debe ser \( s \in ((\mathcal{R}\alpha)^{\leq l(\alpha)})^{n+1} \). Es decir, \( s \) es una \( (n+1) \)-tupla de subcadenas de \( \alpha \) (con como mucho \( l(\alpha) \) símbolos cada subcadena). Y similarmente en el segundo cuantificador debe ser \( x \in \mathcal{R}\alpha \), es decir \( x \) es (el nombre de) una variable que aparece en \( \alpha \).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

21 Octubre, 2020, 10:01 pm
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Salvo que te queden dudas, no tengo nada que añadir a lo que te ha respondido geómetracat.

Otra cosa es que conviene que, además de fijarte en los árboles, no olvides ver el bosque: lo que se está probando ahí es simplemente que es posible definir lo que es una fórmula \( \Sigma_n \) mediante una fórmula \( \Delta_1 \), y eso significa simplemente que "ser una fórmula \( \Sigma_n \)" es una propiedad recursiva, es decir, que siempre puedes saber si una fórmula que te dan explícitamente es o no \( \Sigma_n \). En el fondo uno podría decir que le da igual cómo se formaliza la definición. Desde el momento en que está claro que se tiene que poder definir el concepto de "fórmula \( \Sigma_n \)" de modo que siempre se pueda comprobar en la práctica si una fórmula dada lo es o no, la definición tiene que ser \( \Delta_1 \) y encontrarla explícitamente está cerca de la curiosidad morbosa. De todos modos, por si alguien duda, ahí está explícita, por fea que sea.

21 Octubre, 2020, 10:03 pm
Respuesta #3

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,354
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola geométracat y Carlos

Tengo algunas dudas respecto a los cuantificadores acotados y no acotados. Yo tenía entendido que el término "estar acotado" hacía referencia a las variables solamente, ¿se amplía para los cuantificadores?

Por otro lado, y siguiendo la idea de variable acotada, por ejemplo \( \forall x\colon x+y<5 \) se dice que "La \( x \) está acotada, mientras que la \( y \) está libre". ¿Esto está bien?

Con esta idea me pregunto entonces qué valores puede tomar la \( y \) en esa fórmula, por ejemplo si \( x=1 \) queda \( y<4 \), ¿y esto se interpreta como \( \exists y\colon y<4 \) (lo cual es verdadero p.e. \( y=1 \)) o como \( \forall y\colon y<4 \) (es falso, \( y=10 \))? ¿O sino cómo?

Aun no me queda claro lo de los cuantificadores acotados y no acotados, gracias!

Saludos

21 Octubre, 2020, 10:37 pm
Respuesta #4

geómetracat

  • Moderador Global
  • Mensajes: 2,358
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola geométracat y Carlos

Tengo algunas dudas respecto a los cuantificadores acotados y no acotados. Yo tenía entendido que el término "estar acotado" hacía referencia a las variables solamente, ¿se amplía para los cuantificadores?

Creo que estás confundiendo dos conceptos. Una cosa es que una variable esté ligada en una fórmula, que básicamente quiere decir que en la fórmula estás cuantificando sobre esa variable. Y otra cosa distinta son los cuantificadores acotados, que es cuando tienes algo del estilo \( \forall x<n \; \phi \) (en una teoría aritmética) o del estilo \( \forall x \in y \; \phi \) (en una teoría de conjuntos).

Imagino que la confusión viene de la terminología inglesa: variable ligada es "bound variable" y cuantificador acotado es "bounded quantifier". Pero no es lo mismo "bound" que "bounded".

Citar
Por otro lado, y siguiendo la idea de variable acotada, por ejemplo \( \forall x\colon x+y<5 \) se dice que "La \( x \) está acotada, mientras que la \( y \) está libre". ¿Esto está bien?
Sí, si cambias "acotada" por "ligada".

Citar
Con esta idea me pregunto entonces qué valores puede tomar la \( y \) en esa fórmula, por ejemplo si \( x=1 \) queda \( y<4 \), ¿y esto se interpreta como \( \exists y\colon y<4 \) (lo cual es verdadero p.e. \( y=1 \)) o como \( \forall y\colon y<4 \) (es falso, \( y=10 \))? ¿O sino cómo?

Pues no sé en qué contexto estás pensando, pero de entrada diría que de ninguna de las dos. \( y<4 \) es otra fórmula perfectamente válida, con una variable libre.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

21 Octubre, 2020, 10:42 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Tengo algunas dudas respecto a los cuantificadores acotados y no acotados. Yo tenía entendido que el término "estar acotado" hacía referencia a las variables solamente, ¿se amplía para los cuantificadores?

En el lenguaje de la teoría de conjuntos, un cuantificador acotado (o, más precisamente, está acotado en una fórmula) si es de la forma \( \forall x\in y \) o \( \exists x\in y \). En el lenguaje de la aritmética, un cuantificador está acotado si es de la forma \( \forall x\leq  y \) o \( \exists x\leq  y \).

Por otro lado, y siguiendo la idea de variable acotada, por ejemplo \( \forall x\colon x+y<5 \) se dice que "La \( x \) está acotada, mientras que la \( y \) está libre". ¿Esto está bien?

Supongo que te refieres a que la variable \( x \) está ligada y la variable \( y \) está libre.

Con esta idea me pregunto entonces qué valores puede tomar la \( y \) en esa fórmula, por ejemplo si \( x=1 \) queda \( y<4 \), ¿y esto se interpreta como \( \exists y\colon y<4 \) (lo cual es verdadero p.e. \( y=1 \)) o como \( \forall y\colon y<4 \) (es falso, \( y=10 \))? ¿O sino cómo?

Tendrías que aclarar dónde varía ese "para todo x". Si entendemos, por ejemplo, que estás hablando de números naturales, o de números reales, simplemente esa fórmula es falsa sea cual sea el valor que le des a \( y \).

Se me adelantó geómetracat.

21 Octubre, 2020, 11:08 pm
Respuesta #6

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 103
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Gracias por las respuestas, geométracat y Carlos.

Ahora viendo la respuesta, es evidente que el 2| era 2 divide a. Parece mentira a veces como uno no ve cosas tan simples.

Sí, la idea de fórmulas que definen fórmulas la veo en el capítulo. Y el concepto de recursividad en general me parece relevante.

Y me llama la atención aquello que no lo es.

Por ejemplo, que se tenga la \( Σ_{1} \) completitud en Q pero no la \( Π_{1} \) completitud. Es como decir que podemos demostrar la veracidad de la existencia pero que la veracidad de la universalidad no será demostrable en algún caso.

Ya me llamó la atención el problema de la detención y la no recursividad de la función \( Σ \) de la máquina de Turing.

O la recursividad por minimización, que puede no definirse si nunca aparece ese mínimo n que hace 0 la función g. Por eso entiendo

En cierta forma son indicios que nos llevan al concepto de infinito. Por ejemplo, si a una f definida por minimización le añadiésemos que
\( ∀u u<n ¬g(a_{1},...,a_{k},u+1)=0 \)

significaría que ese mínimo n que hace 0 a g no tiene antecesor, o lo que es lo mismo, es infinito. Pero supongo que entonces estaríamos en un modelo no estándar. Y me estoy avanzando demasiado, creo.

21 Octubre, 2020, 11:13 pm
Respuesta #7

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,354
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola a ambos, muchas gracias por sus respuestas

Antes que nada les dejo la parte del apunte de donde lo saqué. En el curso luego no se habla más de estos conceptos sino que todo se asume "sin entrar en mucho detalle".



(Pulsar imagen para expandir)

En el lenguaje de la teoría de conjuntos, un cuantificador acotado (o, más precisamente, está acotado en una fórmula) si es de la forma \( \forall x\in y \) o \( \exists x\in y \).

¿Qué serían \( x \) e \( y \)? ¿Conjuntos, elementos?

Por ejemplo, el siguiente es un resultado clásico en teoría de conjuntos: \( \forall A\colon A\subseteq A \). Aquí sabemos que hablamos de conjuntos por aparecer el \( \subseteq \) y por usar mayúsculas. Sin embargo dicha fórmula tiene implícito el conjunto universal pues en realidad uno demuestra ésto: \( \forall A\subseteq\mathcal{U}\colon A\subseteq A \).

En el ejemplo que puse, si bien no especifiqué cuál era el universo del discurso, es claro que hablamos de los conjuntos numéricos principales.

Tendrías que aclarar dónde varía ese "para todo x". Si entendemos, por ejemplo, que estás hablando de números naturales, o de números reales, simplemente esa fórmula es falsa sea cual sea el valor que le des a \( y \).

¿Por qué "Sea cual sea el valor que le de a \( y \) la fórmula es falsa"?  Aun no logro entender qué rol cumple la variable libre allí, cómo funciona. Como me dijiste "Sea cual sea el valor que le de a \( y \)" entiendo que la \( y \) está cuantificada porque se la puede particularizar en algún valor, pero luego entiendo que no tiene cuantificadores ¿?

geómetracat menciona:

Citar
Con esta idea me pregunto entonces qué valores puede tomar la \( y \) en esa fórmula, por ejemplo si \( x=1 \) queda \( y<4 \), ¿y esto se interpreta como \( \exists y\colon y<4 \) (lo cual es verdadero p.e. \( y=1 \)) o como \( \forall y\colon y<4 \) (es falso, \( y=10 \))? ¿O sino cómo?

Pues no sé en qué contexto estás pensando, pero de entrada diría que de ninguna de las dos. \( y<4 \) es otra fórmula perfectamente válida, con una variable libre.

Tengo claro que cuando uno particulariza la \( x \) en \( \forall x\in\Bbb{R}\colon x+y<5 \) le queda una fórmula con una variable libre. Pero lo que sucede es que \( y<4 \) (cuando \( x=1 \)) es un predicado, y por tanto NO puede tener un valor de verdad. Es decir si definimos \( p(x,y):=x+y<4 \), esto no puede tener valor de verdad hasta tanto y cuanto se convierta en proposición con alguna de estas formas:

1) Se le asignen valores a las variables. Por ejemplo \( p(2,3) \) es falso, mientras que \( p(0,3) \) es verdadero.

2) Se cuantifica el predicado (y aquí entiendo que cada cuantificador debe caer en TODAS las variables). Entonces aquí debería aparecer algo como \( \forall x\in\Bbb{R}\,\exists y\in\Bbb{R}\colon p(x,y) \) lo cual es falso, pero si tenemos \( \exists x\in\Bbb{R}\,\exists y\in\Bbb{R}\colon p(x,y) \) es verdadero.

Entonces mi pregunta es: Cuando tenemos una fórmula que contiene al menos una variable libre, ¿es un predicado y por lo tanto NO es una proposición?



Algo más, geómetracat define a la variable acotada con una letra griega al final (tomemos teoría de conjuntos):

(...) Y otra cosa distinta son los cuantificadores acotados, que es cuando tienes algo del estilo (...) \( \forall x \in y \; \phi \) (en una teoría de conjuntos).

mientras que Carlos no se lo agrega:

En el lenguaje de la teoría de conjuntos, un cuantificador acotado (o, más precisamente, está acotado en una fórmula) si es de la forma \( \forall x\in y \) o \( \exists x\in y \). (...)

¿Son notaciones equivalentes? ¿Qué papel tiene esa \( \phi \) y cuál sería un ejemplo concreto?

Saludos

MODIFICADO

21 Octubre, 2020, 11:22 pm
Respuesta #8

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Por ejemplo, que se tenga la \( Σ_{1} \) completitud en Q pero no la \( Π_{1} \) completitud. Es como decir que podemos demostrar la veracidad de la existencia pero que la veracidad de la universalidad no será demostrable en algún caso.

Pero eso es muy natural, ¿no? Si es cierto que existe un número natural que cumple algo (comprobable en la práctica), vas a poder demostrar que es así: sólo tienes que probar si te sirve el 0, y si no, el 1, y si no, el 2, hasta que lo encuentres, y cuando lo encuentres lo habrás demostrado.

En cambio, si es cierto que todo número natural cumple algo (comprobable en la práctica)  no está claro que puedas demostrarlo. Por lo menos, el razonamiento anterior no te ayuda en nada. De hecho, podemos codificar todas las demostraciones de la teoría de conjuntos como números naturales, y puedes comprobar que 0 no codifica la demostración de ninguna contradicción en ZFC, y que 1 tampoco, y que 2 tampoco, y así, suponiendo que ZFC sea consistente, todo número natural tiene la propiedad de que no codifica la demostración de una contradicción en ZFC, y puedes ir comprobándolo uno por uno, pero eso no te asegura que puedas encontrar una demostración de que todos los números naturales tienen esa propiedad. De hecho, esa demostración no puede existir.

Ya me llamó la atención el problema de la detención y la no recursividad de la función \( Σ \) de la máquina de Turing.

Lo segundo es una consecuencia clara de lo primero. Para calcular \( \Sigma \) tendrías que saber qué máquinas de Turing se detienen y cuáles no. Y si pudieras saber si cualquier máquina de Turing se va a detener o no, podrías construir una máquina de Turing que busque la demostración de una contradicción en ZFC, de modo que sólo se detenga cuando la encuentre. Si supieras si esa máquina en concreto se va a detener o no, sabrías si ZFC es consistente o no. Y eso no puede saberse.

En cierta forma son indicios que nos llevan al concepto de infinito. Por ejemplo, si a una f definida por minimización le añadiésemos que
\( ∀u u<n ¬g(a_{1},...,a_{k},u+1)=0 \)

significaría que ese mínimo n que hace 0 a g no tiene antecesor, o lo que es lo mismo, es infinito. Pero supongo que entonces estaríamos en un modelo no estándar. Y me estoy avanzando demasiado, creo.

No entiendo lo que planteas. Tienes una función definida por minimización y, en algún sentido que se me escapa, supones que no existe ningún \( u \) que anule la función que la define. Si existe un tal \( u \), tu supuesto es contradictorio. Si no existe, la función no está definida.

21 Octubre, 2020, 11:52 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Antes que nada les dejo la parte del apunte de donde lo saqué. En el curso luego no se habla más de estos conceptos sino que todo se asume "sin entrar en mucho detalle".

Bien, te han puesto un ejemplo de fórmula con una variable libre y otra ligada, sin que importe nada más. En particular, sin fijar ningún modelo en particular, y sin que importe que en los modelos más habituales sea falsa. Da igual que la fórmula sea verdadera o falsa para ilustrar las nociones de variable libre y ligada. Pero entonces no tiene sentido entrar a elucubrar sobre qué valores pueden tomar las variables. En primer lugar haría falta fijar un modelo (o al menos una teoría axiomática) que determinara qué clase de objetos recorren las variables.

En el lenguaje de la teoría de conjuntos, un cuantificador acotado (o, más precisamente, está acotado en una fórmula) si es de la forma \( \forall x\in y \) o \( \exists x\in y \).

¿Qué serían \( x \) e \( y \)? ¿Conjuntos, elementos?

En las teorías de conjuntos usuales todo son conjuntos. Los elementos de los conjuntos son también conjuntos. No hay nada más que conjuntos.

Por ejemplo, el siguiente es un resultado clásico en teoría de conjuntos: \( \forall A\colon A\subseteq A \). Aquí sabemos que hablamos de conjuntos por aparecer el \( \subseteq \) y por usar mayúsculas. Sin embargo dicha fórmula tiene implícito el conjunto universal pues en realidad uno demuestra ésto: \( \forall A\subseteq\mathcal{U}\colon A\subseteq A \).

Tienes que especificar el lenguaje formal que consideras y los axiomas que consideras. Por ejemplo, la fórmula \( \forall A\, A\subset A \), puede interpretarse como un teorema de ZFC, en cuyo caso \( A \) es un conjunto simplemente porque en ZFC todo son conjuntos, o también como un teorema de NBG, en cuyo caso \( A \) recorrería todas las clases, tanto las que son conjuntos como las que no.

No sé a qué te refieres exactamente con "conjunto universal". Se le puede dar sentido de varias formas, pero ninguna es estándar. En las teorías de conjuntos usuales, como ZFC, no hay ningún conjunto universal. Si te refieres al universo de un modelo, entonces sería muy retorcido ponerlo explícito en la fórmula.

En el ejemplo que puse, si bien no especifiqué cuál era el universo del discurso, es claro que hablamos de los conjuntos numéricos principales.

¿Qué son conjuntos numéricos principales?

¿Por qué "Sea cual sea el valor que le de a \( y \) la fórmula es falsa"?  Aun no logro entender qué rol cumple la variable libre allí, cómo funciona.

Si consideras la fórmula \( \forall x\, x+y<5 \), no tiene sentido decir si es verdadera o falsa si no fijamos un modelo. Pongamos por ejemplo el modelo \( M \) cuyo universo son los números naturales (daría igual considerar números reales, por ejemplo). Se entiende que \( + \) se interpreta como la suma de números naturales, etc. Ahora necesitas fijar una valoración \( v \) que a cada variable le asigne un objeto de \( M \). Entonces, se cumple \( M\vDash \forall x\,x+y<5[v] \) si y sólo si para todo número natural \( n \), se cumple que \( n+v(y)<5 \), pero eso no es cierto sea cual sea \( v(y) \). Siempre puedes encontrar un número natural \( n \) por ejemplo \( n=6 \), de modo que \( n+v(y)>5 \).

Y esto significa que la fórmula es falsa en el modelo \( M \).

Entonces mi pregunta es: Cuando tenemos una fórmula que contiene al menos una variable libre, ¿es un predicado y por lo tanto NO es una proposición?

Pues no sé. Nunca he manejado esa jerga. En la lógica de primer orden no hay necesidad de jugar con clasificaciones de ese tipo. Lo que hay de fondo es que, en general, para determinar si una fórmula es satisfecha o no en un modelo tienes que fijar una valoración que interprete sus variables libres, aunque no siempre. La fórmula \( x\in y\lor x\notin y \) es verdadera en cualquier modelo, sin que importe que tiene variables libres.

Algo más, geómetracat define a la variable acotada con una letra griega al final (tomemos teoría de conjuntos):

¿Son notaciones equivalentes? ¿Qué papel tiene esa \( \phi \) y cuál sería un ejemplo concreto?

Esa \( \phi \) representa una fórmula. Geómetracat estaba siendo más formal y yo más informal. Es como si te digo que la derivada del seno es el coseno y geómetracat dice que \( (\sin x)' = \cos x \).

Por ejemplo, \( \forall x\in y\, x\subset y \) es un ejemplo de fórmula con un cuantificador acotado. Es la definición de conjunto transitivo. La \( \phi \) de geómetracat es \( \phi\equiv x\subset y \). La fórmula es de tipo \( \forall x\in y\, \phi \), con la \( \phi \) que te he dicho.

Yo había dicho, más informalmente, que ahí hay un cuantificador acotado porque aparece en la forma \( \forall x\in y \), dando por hecho que hay que poner algo detrás para que la fórmula esté completa.