Autor Tema: ¡Ejercicios sobre teoría de la cuantificación!

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

09 Noviembre, 2012, 12:53 pm
Leído 4551 veces

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Buenas buenas!
Expongo las características de un lenguajes K y sus propiedades demostradas, y luego pregunto mis dudas.  :)

Lenguaje de primer orden K
Axiomas lógicos
(A1) \( \mathcal{A}\rightarrow (\mathcal{B}\rightarrow \mathcal{A}) \).
(A2) \( (\mathcal{A}\rightarrow (\mathcal{B}\rightarrow \mathcal{C}))\rightarrow ((\mathcal{A}\rightarrow \mathcal{B})\rightarrow (\mathcal{A}\rightarrow \mathcal{C})) \).
(A3) \( (\neg\mathcal{B}\rightarrow \neg \mathcal{A})\rightarrow (\mathcal{A}\rightarrow \mathcal{B}) \).
(A4) \( \forall{x_i}\mathcal{A}(x_i)\rightarrow \mathcal{A}(t) \) es una wf de K y \( t \) es un término de K que es libre para \( x_i \) en \( \mathcal{A}(x_i) \).
(A5) \( \forall{x_i}(\mathcal{A}\rightarrow \mathcal{B})\rightarrow (\mathcal{A}\rightarrow \forall{x_i}\mathcal{B}) \) si \( \mathcal{A} \) es una wf de K que no contiene ocurrencias libres de \( x_i \).

Reglas de Inferencia
1. Modus Ponens: \( \mathcal{B} \) se sigue de \( \mathcal{A} \) y \( \mathcal{A}\rightarrow \mathcal{B} \).
2. Generalización: \( \forall{x_i}\mathcal{A} \) se sigue de \( \mathcal{A} \).
[cerrar]

Metateoremas demostrados:
A. Toda wf \( \mathcal{A} \) de K que sea una instancia de una tautología es un teorema de K, y puede ser probada usando sólamente los axiomas (A1)-(A3) y MP (modus ponens).
B. Cualquier predicado de primer orden K es consistente.
C. Si \( \mathcal{B} \) no depende de \( \mathcal{A} \) en una deducción que muestra que \( \gamma, \mathcal{A}\vdash \mathcal{B} \) entonces \( \gamma\vdash\mathcal{B} \).
depender de
Sea \( \mathcal{A} \) una wf y \( \gamma \) un conjunto de wf, y asuma que nosotros tenemos una deducción \( \mathcal{B}_1,..., \mathcal{B}_n \) de \( \gamma \), junto con la justificación de sus pasos deductivos. Diremos que una wf \( \mathcal{B}_i \) depende de \( \mathcal{A} \) si y sólo si (1) \( \mathcal{B}_i \) es \( \mathcal{A} \) y la justificación es que \( \mathcal{B}_i \) pertenece a \( \gamma \) o (2) \( \mathcal{B}_i \) es justificado como una consecuencia directa de MP o Gen (generalización) de alguna wf precedente en la secuencia, donde al menos una de estas depende de \( \mathcal{A} \).
[cerrar]
D. (Teorema de deducción) Asuma que en alguna deducción se muestra que \( \gamma, \mathcal{A}\vdash\mathcal{B} \). no se aplica Gen a alguna wf que depende de \( \mathcal{A} \) de modo que quede cuantificada alguna variable libre de \( \mathcal{A} \). Entonces \( \gamma \vdash \mathcal{A}\rightarrow\mathcal{B} \).

Hasta ahí se da la teoría para el siguiente ejercicio que no sé cómo hacer:
i) Sea K una teoría de primer orden y sea \( K^\sharp \) una teoría axiomática con los siguientes axiomas: (a)\( \forall x_i ... \forall x_n \mathcal{A} \) donde \( \mathcal{A} \) es cualquier axioma de K y \( x_1, ..., x_n \) variables cualesquiera (ninguna si n=0)  y (b) \( \forall x_1 ... \forall x_n (\mathcal{A}\rightarrow \mathcal{B})\rightarrow (\forall x_1...\forall x_n \mathcal{A} \rightarrow \forall x_1... \forall x_n \mathcal{B}) \) donde \( \mathcal{A} \) y \( \mathcal{B} \) son wf cualesquiera y \( y_1,..., y_n \) son variables cualesquiera. Además \( K^\sharp \) tiene como su única regla de inferencia al modus ponens. Demuestre que K tiene los mismos teoremas de \( K^\sharp \).

E. (Regla de particularización A4 -¿por qué A4?) Si \( t \) es libre en \( x \) en \( \mathcal{A}(x) \) entonces \( \forall x \mathcal{A}(x) \vdash \mathcal{A}(t) \).
F. (Regla de existencia E4 -¿por qué E4?) Sea \( t \) es un término libre para \( x \) en una wf \( \mathcal{A}(x,t) \) y sea \( \mathcal{A}(t,t) \) obtenida de \( \mathcal{A}(x,t) \) por el reemplazo de todas las ocurrencias libres de \( x \) por \( t \). Entonces \( \mathcal{A}(t,t)\vdash \exists{x}\mathcal{A}(x,t) \).
G. Prueba por contradicción.

Con esto pregunto los siguientes ejercicios:

ii) \( \vdash \exists{y} [A_1^1(y)\rightarrow\forall{y}A_1^1(y) ] \) (no entiendo de este siquiera qué me dice)
iii) \( \vdash (\forall x \mathcal{A}\vee \forall x \mathcal{B})\rightarrow \forall x (\mathcal{A}\vee\mathcal{B}) \)

Y bien, eso es todo.  ;D

¡Gracias por las respuestas y comentarios!
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

09 Noviembre, 2012, 03:23 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Veamos i)

Vamos a probar que si \( \mathcal A \) es un teorema de K y \( x_1,\ldots, x_n \) son variables cualesquiera, entonces \( \forall x_1\ldots x_n\mathcal A \) es un teorema de \( K^\sharp \)

Lo probamos por inducción sobre la longitud de una demostración de \( \mathcal A \) en K.

Si \( \mathcal A \) se demuestra en un sólo paso, es que es un axioma de K, luego \( \forall x_1\ldots x_n\mathcal A \) es un axioma de\( K^\sharp \).

Si el resultado es cierto para fórmulas demostrables en menos de \( n \) pasos y \( \mathcal A \) se demuestra en n pasos, entonces, hay tres posibilidades:

\( \color{red}\mathcal A \) es un axioma de K, caso ya tratado.

\( \color{red}\mathcal A \) se deduce de dos fórmulas anteriores, \( \mathcal B \)  y \( \mathcal B\rightarrow \mathcal A \) por modus ponens.

Entonces, por hipótesis de inducción \( \forall x_1\cdots x_n\mathcal B \) y \( \forall x_1\cdots x_n(\mathcal B\rightarrow \mathcal A) \) son teoremas de \( K^\sharp \)). Entonces

\( \forall x_1\cdots x_n(\mathcal B\rightarrow \mathcal A)\rightarrow (\forall x_1\cdots x_n\mathcal B\rightarrow \forall x_1\cdots x_n\mathcal A) \) es un axioma de \( K^\sharp \), luego aplicando MP dos veces obtenemos \( \forall x_1\ldots x_n\mathcal A \) en \( K^\sharp \).

\( \mathcal A \) es de la forma \( \forall x\mathcal B \), donde \( \mathcal B \) es una fórmula anterior de la deducción. Entonces, por hipótesis de inducción (aplicada a las variables \( x_1,\ldots, x_n,x \)) tenemos que \( \forall x_1\cdots x_n x\mathcal B \) es un teorema de \( K^\sharp \), pero esta fórmula es \( \forall x_1\cdots x_n \mathcal A \).

Esto termina la prueba.

Ahora hay que probar que si \( \mathcal A \) es un teorema de \( K^\sharp \) entonces es también un teorema de K. De nuevo lo probamos por inducción sobre la longitud de una deducción. El único paso delicado es demostrar que todos los axiomas de \( K^\sharp \) son teoremas de K. Una vez probado esto, el resto es trivial, pues si \( \mathcal A \) se deduce por modus ponens de \( \mathcal B \) y \( \mathcal B\rightarrow \mathcal A \), entonces por hipótesis de inducción estas fórmulas son teoremas de K, luego también \( \mathcal A \), usando modus ponens en K.

Trata de probar la parte correspondiente a los axiomas y si no te sale lo pensamos.

ii) dice que existe un y tal que si y cumple algo, entonces todo y cumple ese algo. El argumento de fondo es el siguiente: o bien todo y cumple algo, o bien existe un y que no cumple ese algo. Si todo y cumple algo, entonces la implicación \( A(y)\rightarrow \forall y A(y) \) es cierta, luego cualquier y cumple lo pedido.

Si existe un y tal que \( \lnot A(y) \), entonces la implicación \( A(y)\rightarrow \forall yA(y) \) es cierta (porque la hipótesis es falsa), y entonces ese y cumple lo pedido.

Para probar iii) tendrás que suponer la hipótesis, luego suponer \( \lnot \mathcal A \), de ahí deducir \( \lnot \forall x\mathcal A \), de ahí deducir que \( \forall x\mathcal B \), de ahí concluir \( \mathcal B \), con lo que habrás probado \( \lnot \mathcal A\rightarrow \mathcal B \), lo cual equivale a \( \mathcal A\lor\mathcal B \), y luego generalizas.

09 Noviembre, 2012, 06:50 pm
Respuesta #2

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Muchas gracias por la respuesta!

Si el resultado es cierto para fórmulas demostrables en menos de \( n \) pasos y \( \mathcal A \) se demuestra en n pasos, entonces, hay tres posibilidades:

¿Aquí no son n+1 pasos?

\( \mathbb A \) es un axioma de K, caso ya tratado.
El cambio de notación entre \( \mathcal A \) y \( \mathbb A \) me confundió un rato.

Bueno, para la otra parte:

Hay que probar que \( \forall x_i ... \forall x_n \mathcal{A} \) para cada axioma de K. Pero si \( \mathcal{A} \) es un axioma de K tenemos por generalización n veces en n variables distintas que \( \forall x_i ... \forall x_n \mathcal{A} \). Lo que probaría que este axioma en \( K^\sharp \) es un teorema en K.
Para probar que \( \forall x_1\cdots x_n(\mathcal B\rightarrow \mathcal A)\rightarrow (\forall x_1\cdots x_n\mathcal B\rightarrow \forall x_1\cdots x_n\mathcal A) \) es un teorema en K. Es como sigue:

1) \( \forall x_1\cdots x_n(\mathcal B\rightarrow \mathcal A) \)  hipótesis.
2) \( \forall x_1\cdots x_n\mathcal B \)  hipótesis.
3) \( \mathcal B \) 2, particularización aplicado n veces.
4) \( \mathcal B\rightarrow \mathcal A \) 1, particularización aplicado n veces.
5) \( \mathcal A \) 3,4 MP
6) \( \forall x_1\cdots x_n\mathcal A \) 5, Gen aplicado n veces sobre las \( x_1\cdots x_n \) variables.
así probamos que \( \forall x_1\cdots x_n(\mathcal B\rightarrow \mathcal A), \forall x_1\cdots x_n\mathcal B \vdash \forall x_1\cdots x_n\mathcal A \), y puesto que no se aplicaron generalizaciones sobre variables libres de las hipótesis podemos concluir que: \( \vdash\forall x_1\cdots x_n(\mathcal B\rightarrow \mathcal A)\rightarrow (\forall x_1\cdots x_n\mathcal B\rightarrow \forall x_1\cdots x_n\mathcal A) \). Y finaliza la demostración.
Ahora si \( \mathcal A \) es teorema de \( K^\sharp \) y tiene sólo un paso entonces es axioma, que con lo anteriormente demostrado, queda demostrado que es teorema de K. Ahora, supuesto hasta n-1, y que \( \mathcal A \) sea deducido en n pasos. Así, si \( \mathcal A \) no es axioma, debió ser deducido de dos wf deducidas en menos de n-1 pasos por MP, de la forma \( \mathcal B \rightarrow \mathcal A \) y \( \mathcal B \). Por hipótesis de inducción, tanto \( \mathcal B \rightarrow \mathcal A \) como \( \mathcal B \) son teoremas de K, y como en K, también es válido MP, tenemos \( \mathcal A \).
Esto finaliza la demostración.
¿Esto es correcto?

\( \mathcal A \) es de la forma \( \forall x\mathcal B \), donde \( \mathcal B \) es una fórmula anterior de la deducción. Entonces, por hipótesis de inducción (aplicada a las variables \( x_1,\ldots, x_n,x \)) tenemos que \( \forall x_1\cdots x_n x\mathcal B \) es un teorema de \( K^\sharp \), pero esta fórmula es \( \forall x_1\cdots x_n \mathcal A \).

Esto termina la prueba.

Como en \( K^\sharp \) para \( \forall x_1\cdots x_n \mathcal A \) se admite el valor \( n=0 \), donde tendremos \( \mathcal A \) así el mismo \( \mathcal A \) es teorema de \( K^\sharp \), ¿no?

Y para iii):
\( \vdash (\forall x \mathcal{A}\vee \forall x \mathcal{B})\rightarrow \forall x (\mathcal{A}\vee\mathcal{B}) \)
1) \( \forall x \mathcal{A}\vee \forall x \mathcal{B} \) hipótesis
2) \( \neg\mathcal{A} \) hipótesis
3) \( \neg\mathcal{A}\rightarrow\exists\red{x}\black{\neg\mathcal A} \) regla de existencia E4 (¿eh?)
4) \( \exists\red{x}\black{\neg\mathcal{A}} \) 2,3 MP
5) \( \neg\forall\red{x}\black{\neg\neg \mathcal A} \) definición de \( \exists \)
6) \( \neg\forall\red{x}\black{A} \) 5, equivalencia
7) \( \forall x \mathcal{B} \) 1,6 eliminación de disyunción.
8)\( \mathcal{B} \) 7, particularización.
se demostró \( \forall x \mathcal{A}\vee \forall x \mathcal{B}, \neg\mathcal{A} \vdash \mathcal B \), como no hubo generalizaciones en variables libres de las hipótesis sucede que \( \forall x \mathcal{A}\vee \forall x \mathcal{B}\vdash \neg\mathcal A \rightarrow\mathcal B \), de esto último:
10) \( \neg\mathcal A \rightarrow\mathcal B \) demostrado.
11) \( \mathcal A\vee\mathcal B  \) 10, equivalencia.
12) \( \forall x \mathcal A\vee\mathcal B \) 11, Gen.
así queda demostrado \( \forall x \mathcal{A}\vee \forall x \mathcal{B}\vdash \forall x \mathcal A\vee\mathcal B \), y nuevamente como no se generalizó sobre variables libres, tenemos \( \vdash \forall x \mathcal{A}\vee \forall x \mathcal{B}\rightarrow\forall x \red{(}\black{\mathcal A\vee\mathcal B)} \)  ;D

¿Esto es correcto así?

¡Gracias!


PD: Perdón si hay algún error de redacción.

Pregunta: ¿Hay forma de usar el LaTex de manera que los mensajes que justifican los pasos se vean mejor?, digo ahí se ven muy pegados al paso mismo, y no se ve bien.
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

09 Noviembre, 2012, 07:58 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¡Muchas gracias por la respuesta!

A mandar.  :)

¿Aquí no son n+1 pasos?

Lo he supuesto para fórmulas demostrables en menos de n pasos (es decir, a lo sumo \( n-1 \)) y lo pruebo para fórmulas demostrables en n pasos. Si lo prefieres, puedes suponerlo para fórmulas demostrables hasta en \( n \) pasos y probarlo para fórmulas demostrables en \( n+1 \) pasos. Es lo mismo.

El cambio de notación entre \( \mathcal A \) y \( \mathbb A \) me confundió un rato.

Perdone usted. Era una errata. Traté de adaptarme a tu notación, pues yo uso letras griegas para las fórmulas, pero me lié entre \mathcal y \mathbb.


Aquí me pierdo:

¿Esto es correcto?
\( \mathcal A \) es de la forma \( \forall x\mathcal B \), donde \( \mathcal B \) es una fórmula anterior de la deducción. Entonces, por hipótesis de inducción (aplicada a las variables \( x_1,\ldots, x_n,x \)) tenemos que \( \forall x_1\cdots x_n x\mathcal B \) es un teorema de \( K^\sharp \), pero esta fórmula es \( \forall x_1\cdots x_n \mathcal A \).

Esto termina la prueba.

Como en \( K^\sharp \) para \( \forall x_1\cdots x_n \mathcal A \) se admite el valor \( n=0 \), donde tendremos \( \mathcal A \) así el mismo \( \mathcal A \) es teorema de \( K^\sharp \), ¿no?

Cuando preguntas si es correcto, ¿te refieres a tu prueba precedente o al pasaje mío que citas? Creo que tanto lo uno como lo otro es correcto. Y la última frase no sé en qué contexto debo entenderla. ¿Pretende ser un razonamiento alternativo al pasaje mío que citas? Si es así no entiendo lo que planteas.

En tu demostración de iii escribes fórmulas con cuantificadores que no van seguidos de ninguna variable, eso no es correcto. Revísalo. El enunciado de tu regla E4 me parece muy raro. No entiendo por qué aparece t dos veces. Entre lo uno y lo otro, me cuesta decirte algo sobre la forma en que aplicas la regla. Por lo demás, ésa es la idea. Trata de revisar estas dos cosas y te lo vuelvo a mirar.

Pregunta: ¿Hay forma de usar el LaTex de manera que los mensajes que justifican los pasos se vean mejor?, digo ahí se ven muy pegados al paso mismo, y no se ve bien.

Pues supongo que con paciencia podrías hacer tablas muy apañadas, pero no sé si merecería la pena.

09 Noviembre, 2012, 08:43 pm
Respuesta #4

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Aquí me pierdo:

¿Esto es correcto?
\( \mathcal A \) es de la forma \( \forall x\mathcal B \), donde \( \mathcal B \) es una fórmula anterior de la deducción. Entonces, por hipótesis de inducción (aplicada a las variables \( x_1,\ldots, x_n,x \)) tenemos que \( \forall x_1\cdots x_n x\mathcal B \) es un teorema de \( K^\sharp \), pero esta fórmula es \( \forall x_1\cdots x_n \mathcal A \).

Esto termina la prueba.

Como en \( K^\sharp \) para \( \forall x_1\cdots x_n \mathcal A \) se admite el valor \( n=0 \), donde tendremos \( \mathcal A \) así el mismo \( \mathcal A \) es teorema de \( K^\sharp \), ¿no?

Cuando preguntas si es correcto, ¿te refieres a tu prueba precedente o al pasaje mío que citas? Creo que tanto lo uno como lo otro es correcto. Y la última frase no sé en qué contexto debo entenderla. ¿Pretende ser un razonamiento alternativo al pasaje mío que citas? Si es así no entiendo lo que planteas.
Me refiero al precedente, y sí es muy evidente que se presta a confusiones. Lo siento.
El razonamiento no pretende ser uno alternativo al que usted dio. Sólo es un comentario relacionado con "retirar" cada \( \forall \) y obtener así que un teorema en K, lo es también en \( K^\sharp \). Pues, sea había demostrado que si \( \mathcal A \) es teorema en K, lo es \( \forall x_1\cdots x_n \mathcal A \) en \( K^\sharp \). Que es distinto a lo pedido, pero que también es sólo una particularización de este resultado que es permitida en \( K^\sharp \).

En tu demostración de iii escribes fórmulas con cuantificadores que no van seguidos de ninguna variable, eso no es correcto. Revísalo. El enunciado de tu regla E4 me parece muy raro. No entiendo por qué aparece t dos veces. Entre lo uno y lo otro, me cuesta decirte algo sobre la forma en que aplicas la regla. Por lo demás, ésa es la idea. Trata de revisar estas dos cosas y te lo vuelvo a mirar.
Lo primero creo ya haberlo corregido. Con respecto a los resultados de la regla E4, también en el texto (Logic for the Mathematicians, Mendelson) se tienen los siguientes corolarios que creo que fueron los que realmente usé:

Cito:Como caso particular de la regla E4 tenemos \( \mathcal A(t)\vdash\exists x\mathcal A(x) \) siempre que \( t \) sea libre para \( x \) en \( \mathcal A(x) \). En particular, cuando \( t \) es \( x \) mismo, \( \mathcal A(x)\vdash\exists x \mathcal A(x) \).

Ese sería el metateorema usado, es más, la que se usó fue la última frase de esa cita, si no me equivoco.

 ;D
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

09 Noviembre, 2012, 09:29 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El razonamiento no pretende ser uno alternativo al que usted dio. Sólo es un comentario relacionado con "retirar" cada \( \forall \) y obtener así que un teorema en K, lo es también en \( K^\sharp \). Pues, sea había demostrado que si \( \mathcal A \) es teorema en K, lo es \( \forall x_1\cdots x_n \mathcal A \) en \( K^\sharp \). Que es distinto a lo pedido, pero que también es sólo una particularización de este resultado que es permitida en \( K^\sharp \).

Ah, perdón. Es cierto. Cuando empecé la demostración eso era lo último que pensaba decir, pero al final me olvidé y no lo dije.

Cito:Como caso particular de la regla E4 tenemos \( \mathcal A(t)\vdash\exists x\mathcal A(x) \) siempre que \( t \) sea libre para \( x \) en \( \mathcal A(x) \). En particular, cuando \( t \) es \( x \) mismo, \( \mathcal A(x)\vdash\exists x \mathcal A(x) \).

Ese sería el metateorema usado, es más, la que se usó fue la última frase de esa cita, si no me equivoco.

Lo veo bien. Lo único que te comentaría es que, tal y como enuncias la regla E4 (o su corolario) puedes pasar directamente de 2) a 4), pues la regla no está enunciada como una implicación que después te obligue a usar MP, sino que te dice directamente que de 2) se deduce 4).

13 Noviembre, 2012, 05:24 pm
Respuesta #6

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Hubo algo que se me olvidó mencionar, por culpa del resto:  :P
ii) dice que existe un y tal que si y cumple algo, entonces todo y cumple ese algo. El argumento de fondo es el siguiente: o bien todo y cumple algo, o bien existe un y que no cumple ese algo. Si todo y cumple algo, entonces la implicación \( A(y)\rightarrow \forall y A(y) \) es cierta, luego cualquier y cumple lo pedido.
Esto me aclara a qué se refiere, pero no es una demostración y aún no se me ocurre nada. Es más es que no he podido manejar todavía lo suficientemente bien los \( \exists \) como eliminarlos, para hacerlos aparecer y demás. Creo que en unas pocas horas tengo ejercicios relacionados que no he podido resolver por ese mismo problema.
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

14 Noviembre, 2012, 10:06 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hubo algo que se me olvidó mencionar, por culpa del resto:  :P
ii) dice que existe un y tal que si y cumple algo, entonces todo y cumple ese algo. El argumento de fondo es el siguiente: o bien todo y cumple algo, o bien existe un y que no cumple ese algo. Si todo y cumple algo, entonces la implicación \( A(y)\rightarrow \forall y A(y) \) es cierta, luego cualquier y cumple lo pedido.
Esto me aclara a qué se refiere, pero no es una demostración y aún no se me ocurre nada. Es más es que no he podido manejar todavía lo suficientemente bien los \( \exists \) como eliminarlos, para hacerlos aparecer y demás. Creo que en unas pocas horas tengo ejercicios relacionados que no he podido resolver por ese mismo problema.

Bueno, estos problemas no tienen mucho que ver con la lógica, sino con las reglas lógicas que te permites usar. Lo ideal sería que supieras (o que demostraras en general) que si tienes \( \exists y \alpha \) y a continuación escribes \( S_y^z\alpha \) (eliminas el particularizador) y en lo sucesivo no generalizas respecto a variables libres en  \( S_y^z\alpha \) y llegas a una fórmula \( \beta \) que no tiene libre la variable \( z \), entonces \( \beta \) es consecuencia de tus premisas (es decir, que es lícito eliminar el particularizador en esas condiciones).

Usando esto, la prueba sería así:

\( \exists y\lnot A(y) \) (hipótesis)

\( \lnot A(y) \) (eliminación del particularizador) A partir de aquí está prohibido generalizar respecto de \( y \), porque \( y \) no es un objeto arbitrario, sino uno específico.

\( A(y)\rightarrow \forall y A(y) \)  (se sigue de lo anterior, por ejemplo porque equivale a \( \lnot A(y)\lor \forall y A(y) \))

\( \exists y(A(y)\rightarrow \forall y A(y)) \) (introducción del particularizador)

Como esta última fórmula no tiene libre la variable \( y \), hemos probado que

\( \exists y\lnot A(y)\rightarrow (\exists y(A(y)\rightarrow \forall y A(y))) \).

\( \lnot\exists y\lnot A(y) \) (hipótesis)

\( \forall y A(y) \)

\( A(y)\rightarrow \forall y A(y) \)

\( \exists y(A(y)\rightarrow \forall yA(y)) \) (introducción del particularizador)

\( \lnot\exists y\lnot A(y)\rightarrow (\exists y(A(y)\rightarrow \forall yA(y))) \)

Las dos conclusiones anteriores implican que

\( (\exists y\lnot A(y)\lor \lnot \exists y\lnot A(y))\rightarrow  (\exists y(A(y)\rightarrow \forall yA(y)) \)

y de aquí se sigue la conclusión, por el tercio excluso y MP.

14 Noviembre, 2012, 02:03 pm
Respuesta #8

specu

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 62
  • Karma: +0/-0
  • Sexo: Masculino
    • Especulación pura
Otro camino para llegar a \( \exists{x}(Fx \to \forall{y}Fy) \) es tener en cuenta la equivalencia entre \( \neg \forall{x}\phi \) y \( \exists{x}\neg\phi \).

Así, primero podría probarse \( \forall{x}Fx \to \forall{y}Fy \), que es lo mismo que \( \neg\forall{x}Fx \lor \forall{y}Fy \) y que \( \exists{x}\neg Fx \lor \forall{y}Fy \). De ahí llegamos a \( \exists{x}( \neg Fx \lor \forall{y}Fy) \) y a \( \exists{x}(Fx \to \forall{y}Fy) \).

Saludos