Rincón Matemático

Matemática => Lógica, Conjuntos, Lenguajes Formales => Lógica => Mensaje iniciado por: JordiMath en 21 Octubre, 2020, 07:50 pm

Título: Formalización de la lógica
Publicado por: JordiMath en 21 Octubre, 2020, 07:50 pm
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 α?
Título: Re: Formalización de la lógica
Publicado por: geómetracat en 21 Octubre, 2020, 09:23 pm
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 \).
Título: Re: Formalización de la lógica
Publicado por: Carlos Ivorra en 21 Octubre, 2020, 10:01 pm
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.
Título: Re: Formalización de la lógica
Publicado por: manooooh en 21 Octubre, 2020, 10:03 pm
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
Título: Re: Formalización de la lógica
Publicado por: geómetracat en 21 Octubre, 2020, 10:37 pm
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.
Título: Re: Formalización de la lógica
Publicado por: Carlos Ivorra en 21 Octubre, 2020, 10:42 pm
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.
Título: Re: Formalización de la lógica
Publicado por: JordiMath en 21 Octubre, 2020, 11:08 pm
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.
Título: Re: Formalización de la lógica
Publicado por: manooooh en 21 Octubre, 2020, 11:13 pm
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".

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

(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
Título: Re: Formalización de la lógica
Publicado por: Carlos Ivorra en 21 Octubre, 2020, 11:22 pm
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.
Título: Re: Formalización de la lógica
Publicado por: Carlos Ivorra en 21 Octubre, 2020, 11:52 pm
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.
Título: Re: Formalización de la lógica
Publicado por: manooooh en 22 Octubre, 2020, 02:05 am
Hola

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.

Pues para que lo nombren y luego no se use en el resto del curso, ¿qué sentido tuvo ponerlo? Por "usar" me refiero a hacer mención explícita en por lo menos un ejercicio, pero es que ni eso, con un ejemplo terminan esa parte del tema. No me parece adecuado desde el punto de vista del aprendizaje.

Lo que ocurre es que ahora como ayudante veo un poco mejor cómo se enseña esa asignatura. En particular, he notado que en el tema de lógica, nunca usamos predicados de más de 1 variable porque quizás "no sea el objetivo de la materia complicarse las cosas con más variables" y está bien, pero yo como curioso leo "variables libres y ligadas" y en todo el resto de la materia no lo nombran y entonces me pica la curiosidad por saber más.

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.

Claro. Al fin y al cabo que siempre acabaremos ahí.

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.

Sinceramente no creo que usemos algún modelo con nombre y apellido, sino que por lo menos yo veo que usamos una teoría estándar, de libros clásicos introductorios y nada más.

Pero tu última oración creo que da en la tecla de por qué se ven demostraciones de conjuntos sin que se escriba al "conjunto universal" como parte del ejercicio.

¿Qué son conjuntos numéricos principales?

Los naturales, enteros, racionales y reales. En todos ellos podemos definir una suma y un producto habituales sin que nadie nos pregunte, por ejemplo, "Oye, ¿cómo demuestras la propiedad de cerradura en la adición de esos conjuntos numéricos?" sino que se los toma como "base" para otras operaciones más complejas, como por ejemplo en \( \Bbb{Z} \) si se definiera la operación \( a*b=a\cdot b+2 \).

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 \).

Vale, creo que voy entendiendo.

Y si ahora escribo \( \forall x\in\Bbb{R}\,\exists y\in\Bbb{N}\cup\{0\}\, x+y<5 \), ¿esta fórmula tendría un modelo asociado de forma natural, implícita? ¿Cuál sería y cómo lo has deducido? Aquí ya no hay variables libres; todas están ligadas.

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.

Hombre pues claro, una tautología siempre es verdadera (y por lo que te entendí, agregaría "en cualquier modelo"). Lo mismo ocurre con una contradicción como \( x\in y\land x\notin y \).

Lo interesante, creo yo, es estudiar fórmulas de las que de antemano no se sepa cuál será su valor de verdad.

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.

Muchas gracias.

A ver pongo unos ejemplos:

- La fórmula \( \exists x\in\{1,2,3\}\colon x>2 \) tiene a \( x \) como variable ligada (por el \( \exists \)), y el \( \exists \) es un cuantificador acotado pues tiene el \( \in\{1,2,3\} \).

- La fórmula \( \exists x\colon x>2 \) tiene a \( x \) como variable ligada (por el \( \exists \)), ¿y se puede decir que el cuantificador \( \exists \) es un "cuantificador libre" por no tener una pertenencia?

Si existe tal "Cuantificador libre", entonces podríamos armar una tabla de doble entrada como la siguiente (para teoría de conjuntos):

\(
\begin{array}{c|c|c}
\text{Fórmula con...}&\text{Cuantificador libre}&\text{Cuantificador acotado}\\\hline
\text{Variable libre}&x>2&\text{¿\(x>2\)?}\\\hline
\text{Variable ligada}&\exists x\colon x>2&\exists x\in\{1,2,3\}\colon x>2\\
\end{array}
 \)

Me genera dudas el de variable libre y cuantificador acotado, porque al ser variable libre hay ausencia de cuantificador, así que supuse que cuando una variable es libre se puede hablar tanto de cuantificador libre o acotado. ¿Es correcto?

Gracias y saludos
Título: Re: Formalización de la lógica
Publicado por: Carlos Ivorra en 22 Octubre, 2020, 10:22 am
Sinceramente no creo que usemos algún modelo con nombre y apellido, sino que por lo menos yo veo que usamos una teoría estándar, de libros clásicos introductorios y nada más.

Pero tu última oración creo que da en la tecla de por qué se ven demostraciones de conjuntos sin que se escriba al "conjunto universal" como parte del ejercicio.

Pues a mí me da la sensación de que hacéis una mezcla muy poco ortodoxa entre sintaxis y semántica, pero no sé. No conozco los detalles, ni la finalidad con la que tratáis la lógica.

Y si ahora escribo \( \forall x\in\Bbb{R}\,\exists y\in\Bbb{N}\cup\{0\}\, x+y<5 \), ¿esta fórmula tendría un modelo asociado de forma natural, implícita? ¿Cuál sería y cómo lo has deducido? Aquí ya no hay variables libres; todas están ligadas.

Me cuesta responderte, porque todo lo que planteas me resulta demasiado impreciso. Hace falta conjeturar una interpretación posible de lo que quieres decir para dar una respuesta posible. Literalmente, yo veo la fórmula

 \( \forall x\in\Bbb{R}\,\exists y\in\Bbb{N}\cup\{0\}\, x+y<5 \),

y, salvo que me digan otra cosa, entiendo que es una fórmula del lenguaje de la teoría de conjuntos, que deberá ser interpretada en modelos de la teoría de conjuntos. Es posible definir lenguajes y teorías axiomáticas que tengan como modelos naturales los cuerpos, o los cuerpos ordenados, etc., pero entonces sobraría el \( x\in\Bbb{R} \), si es que quieres tomar a \( \Bbb{R} \) como modelo, ya que en tal caso bastaría escribir \( \forall x \), y tendría que tratarse de una teoría en la que fuera posible definir los números naturales, o que contara al menos con un relator que deba interpretarse como la pertenencia a \( \Bbb{N} \), pero todo eso son cosas que habría que aclarar antes de plantearse qué modelos tiene esa sentencia.

Insisto en que no acabo de entender cómo concibes tú estas cosas, paro a mí me resulta muy chocante (chirriante, diría incluso) que escribas una fórmula con notación conjuntista (con pertenencias, uniones, conjuntos numéricos) y a la vez preguntes por modelos naturales para esa fórmula, como si presupusieras que el lenguaje en que está escrita no es el lenguaje de la teoría de conjuntos (que podría no serlo, pero haría falta especificar muchas cosas en tal caso para que se entendiera qué es esa fórmula).

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.

Hombre pues claro, una tautología siempre es verdadera (y por lo que te entendí, agregaría "en cualquier modelo"). Lo mismo ocurre con una contradicción como \( x\in y\land x\notin y \).

Lo interesante, creo yo, es estudiar fórmulas de las que de antemano no se sepa cuál será su valor de verdad.

Yo te ponía un ejemplo de cómo una fórmula puede ser verdadera aunque tenga variables libres. Que te parezca más o menos interesante es otra cosa. No es necesario que sea una tautología. Por ejemplo, \( x^2\geq 0 \) es verdadera cuando tomas como modelo a los números reales.

- La fórmula \( \exists x\in\{1,2,3\}\colon x>2 \) tiene a \( x \) como variable ligada (por el \( \exists \)), y el \( \exists \) es un cuantificador acotado pues tiene el \( \in\{1,2,3\} \).

Los cuantificadores acotados se definen para establecer una jerarquía de fórmulas según su complejidad, de modo que el nivel más bajo de la jerarquía lo forman las fórmulas cuyos cuantificadores están todos acotados. En ese contexto, es frecuente que se exija que la "cota" de cada cuantificador sea una variable y no un término cualquiera, es decir que no valdría \( x\in\{1,2,3\} \) como cota. En algunos contextos se pueden permitir cotas algo más generales, pero no es lo habitual.

- La fórmula \( \exists x\colon x>2 \) tiene a \( x \) como variable ligada (por el \( \exists \)), ¿y se puede decir que el cuantificador \( \exists \) es un "cuantificador libre" por no tener una pertenencia?

Se dice que el cuantificador no está acotado.

Me genera dudas el de variable libre y cuantificador acotado, porque al ser variable libre hay ausencia de cuantificador, así que supuse que cuando una variable es libre se puede hablar tanto de cuantificador libre o acotado. ¿Es correcto?

Si no hay cuantificadores, entonces no hay cuantificadores. No puedes decir que haya cuantificadores no acotados. Como te decía, este concepto se usa para introducir una jerarquía de fórmulas que empieza con las fórmulas de tipo \( \Delta_0 \), que son las que no tienen cuantificadores no acotados. Una fórmula sin cuantificadores es \( \Delta_0 \).
Título: Re: Formalización de la lógica
Publicado por: manooooh en 22 Octubre, 2020, 09:12 pm
Hola

Pues a mí me da la sensación de que hacéis una mezcla muy poco ortodoxa entre sintaxis y semántica, pero no sé. No conozco los detalles, ni la finalidad con la que tratáis la lógica.

Es la asignatura Matemática Discreta en 1er año de Ingeniería. Así que es probable que nos interese más las aplicaciones prácticas como grafos, árboles, recurrencia más allá de las demostraciones. Pero quiero ser el ingeniero más matemático, y eso puede llevarme a buen camino... o no.

Insisto en que no acabo de entender cómo concibes tú estas cosas, paro a mí me resulta muy chocante (chirriante, diría incluso) que escribas una fórmula con notación conjuntista (con pertenencias, uniones, conjuntos numéricos) y a la vez preguntes por modelos naturales para esa fórmula, como si presupusieras que el lenguaje en que está escrita no es el lenguaje de la teoría de conjuntos (que podría no serlo, pero haría falta especificar muchas cosas en tal caso para que se entendiera qué es esa fórmula).

Claro. Debe ser porque confundo "Modelo" con "Conjunto universal/de discurso".

Yo te ponía un ejemplo de cómo una fórmula puede ser verdadera aunque tenga variables libres. Que te parezca más o menos interesante es otra cosa. No es necesario que sea una tautología. Por ejemplo, \( x^2\geq 0 \) es verdadera cuando tomas como modelo a los números reales.

De acuerdo, y una cosa más. ¿Una tautología (ídem contradicción) se dice así porque es una fórmula siempre verdadera (falsa) en al menos un modelo, o en todos los modelos? Quiero pensar que se dice "Esta fórmula es una tautología en este modelo, pero puede que en otro no".

Los cuantificadores acotados se definen para establecer una jerarquía de fórmulas según su complejidad, de modo que el nivel más bajo de la jerarquía lo forman las fórmulas cuyos cuantificadores están todos acotados. En ese contexto, es frecuente que se exija que la "cota" de cada cuantificador sea una variable y no un término cualquiera, es decir que no valdría \( x\in\{1,2,3\} \) como cota. En algunos contextos se pueden permitir cotas algo más generales, pero no es lo habitual.

Entonces si tomamos el ejemplo de conjunto transitivo \( \forall x\in y\, x\subset y \) es una fórmula con un cuantificador acotado, ¿es así porque la \( y \) es una variable (puede tomar diversos valores), en cambio \( \{1,2,3\} \) es un caso particular?

Compararé esa definición con la siguiente propiedad a ver si me ayudas a sacar conclusiones:

a) Definición de conjunto transitivo \( \forall x\in y\, x\subset y \)

b) Propiedad transitiva de la inclusión \( \forall A\,\forall B\,\forall C\, A\subset B\land B\subset C\to A\subset C \)

Demostración de b)
\( \forall x\colon x\in A\to x\in B\to x\in C \)
[cerrar]

1) ¿Son dos fórmulas?

2) ¿Pertenecen al lenguaje de la teoría de conjuntos?

3) ¿a) es un caso general de b)?

4) ¿a) tiene 1 cuantificador acotado y b) tiene 3 cuantificadores no acotados?

5) ¿a) tiene 1 variable ligada y 1 libre y b) tiene 3 variables ligadas?

Muchas gracias.

Saludos
Título: Re: Formalización de la lógica
Publicado por: Carlos Ivorra en 22 Octubre, 2020, 10:57 pm
De acuerdo, y una cosa más. ¿Una tautología (ídem contradicción) se dice así porque es una fórmula siempre verdadera (falsa) en al menos un modelo, o en todos los modelos? Quiero pensar que se dice "Esta fórmula es una tautología en este modelo, pero puede que en otro no".

Puede haber variantes, pero el uso que yo conozco de la palabra "tautología" en el contexto de la lógica de primer orden se restringe a las fórmulas que resultan de sustituir variables proposicionales por fórmulas de primer orden en una tautología del cálculo proposicional.

Así, \( x=y\lor x\neq y \) es una tautología, pero \( x=y\rightarrow y=x \) no lo es, a pesar de que es una fórmula verdadera en todo modelo. Yo a esto lo llamo una fórmula lógicamente válida, pero no una tautología, y diría que la distinción es usual.

En cualquier caso, si entendemos por "tautología" lo que yo llamo fórmulas lógicamente válidas, son las que son verdaderas en todos los modelos. Si una fórmula es verdadera en un modelo, pero en otros no, pues eso, es una fórmula verdadera en ese modelo.

Entonces si tomamos el ejemplo de conjunto transitivo \( \forall x\in y\, x\subset y \) es una fórmula con un cuantificador acotado, ¿es así porque la \( y \) es una variable (puede tomar diversos valores), en cambio \( \{1,2,3\} \) es un caso particular?

No sé a qué llamas en este contexto un "caso particular". Simplemente, \( \{1,2,3\} \) no es una variable. Pero \( y \) no es una variable porque pueda tomar distintos valores. También \( \mathcal Py \) puede tomar distintos valores y no es una variable, ni serviría para acotar cuantificadores.

1) ¿Son dos fórmulas?

Sí.

2) ¿Pertenecen al lenguaje de la teoría de conjuntos?

Sí.

3) ¿a) es un caso general de b)?

No hay ninguna relación entre a) y b).

4) ¿a) tiene 1 cuantificador acotado y b) tiene 3 cuantificadores no acotados?

Sí.

5) ¿a) tiene 1 variable ligada y 1 libre y b) tiene 3 variables ligadas?

Sí.
Título: Re: Formalización de la lógica
Publicado por: manooooh en 23 Octubre, 2020, 12:44 am
Hola

Puede haber variantes, pero el uso que yo conozco de la palabra "tautología" en el contexto de la lógica de primer orden se restringe a las fórmulas que resultan de sustituir variables proposicionales por fórmulas de primer orden en una tautología del cálculo proposicional.

Así, \( x=y\lor x\neq y \) es una tautología, pero \( x=y\rightarrow y=x \) no lo es, a pesar de que es una fórmula verdadera en todo modelo. Yo a esto lo llamo una fórmula lógicamente válida, pero no una tautología, y diría que la distinción es usual.

En cualquier caso, si entendemos por "tautología" lo que yo llamo fórmulas lógicamente válidas, son las que son verdaderas en todos los modelos. Si una fórmula es verdadera en un modelo, pero en otros no, pues eso, es una fórmula verdadera en ese modelo.

No comprendo la distinción entre una fórmula lógicamente válida y una tautología porque no entiendo qué quieres decir con "fórmulas que resultan de sustituir variables proposicionales por fórmulas de primer orden en una tautología del cálculo proposicional".

No sé a qué llamas en este contexto un "caso particular". Simplemente, \( \{1,2,3\} \) no es una variable. Pero \( y \) no es una variable porque pueda tomar distintos valores. También \( \mathcal Py \) puede tomar distintos valores y no es una variable, ni serviría para acotar cuantificadores.

Ah, pues no entiendo qué representa la \( \in y \) en \( \forall x\in y\, x\subset y \). ¿Resulta un metasímbolo o algo así?

No comprendo por qué \( \mathcal Py \) no lo consideramos "variable", porque a cada \( y \) (que entiendo es un conjunto), se le asigna \( \mathcal Py \) formado por todos los subconjuntos de \( y \). Así que si \( y \) es un conjunto (no importa cuál, por eso varía) también lo es su conjunto de partes (depende de qué conjunto sea \( y \)).

No hay ninguna relación entre a) y b).

Ah, yo las veía relacionadas pero se ve que simplemente son dos cosas distintas porque refieren a cosas distintas, no porque una tenga cuantificadores no acotados y el otro uno acotado y cosas del estilo.

Saludos
Título: Re: Formalización de la lógica
Publicado por: Carlos Ivorra en 23 Octubre, 2020, 12:56 am
No comprendo la distinción entre una fórmula lógicamente válida y una tautología porque no entiendo qué quieres decir con "fórmulas que resultan de sustituir variables proposicionales por fórmulas de primer orden en una tautología del cálculo proposicional".

En el cálculo proposicional, las variables representan proposiciones. Por ejemplo, \( p\lor \lnot p \) es una fórmula del cálculo proposicional y es una tautología, porque su tabla de verdad dice que siempre es verdadera. Si en lugar de la variable proposicional \( p \) pones cualquier fórmula de primer orden, como \( x\in \mathbb R \), obtienes una tautología, como \( x\in \mathbb R\lor x\notin \mathbb R \).

En cambio, \( x=y\rightarrow y=x \) no puede obtenerse de ese modo a partir de una tautología de la lógica proposicional. Por eso no es una tautología.

Ah, pues no entiendo qué representa la \( \in y \) en \( \forall x\in y\, x\subset y \). ¿Resulta un metasímbolo o algo así?

Es el relator de pertenencia de toda la vida en teoría de conjuntos. Un conjunto es transitivo cuando todos sus elementos son también subconjuntos suyos.

No comprendo por qué \( \mathcal Py \) no lo consideramos "variable", porque a cada \( y \) (que entiendo es un conjunto), se le asigna \( \mathcal Py \) formado por todos los subconjuntos de \( y \). Así que si \( y \) es un conjunto (no importa cuál, por eso varía) también lo es su conjunto de partes (depende de qué conjunto sea \( y \)).

No he dicho que \( \mathcal Py \) no sea variable, sino que no es una variable. Una variable es \( y \), pero \( \mathcal Py \) es la variable \( y \) precedida de \( \mathcal P \). Lo que te digo es que no puedes acotar un cuantificador con una \( \mathcal P \) ni nada parecido.