Sección 04: Reglas para cuantificadores
- Page ID
- 101666
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Para pruebas en QL, utilizamos todas las reglas básicas de SL más cuatro reglas básicas nuevas: tanto reglas de introducción como de eliminación para cada uno de los cuantificadores.
Dado que todas las reglas derivadas de SL se derivan de las reglas básicas, también se mantendrán en QL. Añadiremos otra regla derivada, una regla de reemplazo llamada negación cuantificadora.
Instancias de sustitución
Para establecer de manera concisa las reglas para los cuantificadores, necesitamos una forma de marcar la relación entre las oraciones cuantificadas y sus instancias. Por ejemplo, la frase\(Pa\) es una instancia particular de la reivindicación general ∀\(xPx\).
Para un\(\mathcal{A}\) w, una constante\(\mathcal{c}\), y una variable\(\mathcal{x}\), define una instancia de sustitución de ∀\(\mathcal{xA}\) o\(\mathcal{xA}\) es el wque obtenemos reemplazando cada ocurrencia de\(\mathcal{x}\) in\(\mathcal{A}\) con\(\mathcal{c}\). Llamamos a\(\mathcal{c}\) la constante instanciante.
Para subrayar el hecho de que la variable\(\mathcal{x}\) es reemplazada por la constante instanciante\(\mathcal{c}\), escribiremos las expresiones cuantificadas originales como∀\(\mathcal{x}\)\(\mathcal{Ax}\)\(\mathcal{x}\)\(\mathcal{Ax}\) y. Y vamos a escribir la instancia de sustitución\(\mathcal{Ac}\).
Tenga en cuenta que\(\mathcal{A}\),\(\mathcal{x}\), y\(\mathcal{c}\) son todas metavariables. Es decir, son stand-ins para cualquier w, variable y constante en absoluto. Y cuando escribimos\(\mathcal{Ac}\), la constante\(\mathcal{c}\) puede ocurrir varias veces en el\(\mathcal{A}\) w.
Por ejemplo:
~\(Aa\) →\(Ba\)\(Bf\),\(Af\) → y\(Ak\) →\(Bk\) son todas instancias de sustitución de ∀\(x\) (\(Ax\)→\(Bx\)); las constantes instanciantes son\(a\),\(f\), y\(k\), respectivamente.
~\(Raj\),\(Rdj\), y\(Rjj\) son instancias de sustitución de\(zRzj\); las constantes instanciantes son\(a\),\(d\), y\(j\), respectivamente.
Eliminación universal
Si tienes ∀\(xAx\), es legítimo inferir que cualquier cosa es un\(A\). Se puede inferir\(A\) a,\(A\) b,\(A\) z,\(Ad\) 3. Se puede inferir cualquier instancia de sustitución,\(A\(\mathcal{c}\) para cualquier constante\(\mathcal{c}\).
Esta es la forma general de la regla de eliminación universal (∀E):
Al usar la regla ∀E, se escribe la oración sustituida con la constante\(\mathcal{c}\) reemplazando todas las ocurrencias de la variable\(\mathcal{x}\) en\(\mathcal{A}\). Por ejemplo:
Introducción existencial
Es legítimo inferir\(xPx\) si sabes que algo es un\(P\). Podría ser alguna cosa en particular en absoluto. Por ejemplo, si tienes\(Pa\) disponible en el comprobante, entonces\(xPx\) sigue.
Esta es la regla de introducción existencial (I):
Es importante notar que la variable\(\mathcal{x}\) no necesita reemplazar todas las ocurrencias de la constante\(\mathcal{c}\). Se puede decidir qué ocurrencias reemplazar y cuáles dejar en su lugar. Por ejemplo:
Introducción universal
Se\(xPx\) probaría una afirmación universal como la ∀ si se hubiera probado cada instancia de sustitución de la misma. Es decir, si cada frase\(Pa\),\(Pb\),... estuviera disponible en una prueba, entonces sin duda tendrías derecho a reclamar ∀\(xPx\). Ay, no hay esperanza de probar cada instancia de sustitución. Eso requeriría probar\(Pa\),\(Pb\),...,\(P\) j 2,...,\(Ps\) 7,..., y así sucesivamente a la infinidad. Hay infinitamente muchas constantes en QL, por lo que este proceso nunca llegaría a su fin.
Considera en cambio un argumento simple: ∀\(xMx\),.. ∀\(yMy\)
No hace ninguna diferencia al significado de la oración si usamos la variable\(x\) o la variable\(y\), por lo que este argumento es obviamente válido. Supongamos que comenzamos de esta manera:
Nosotros hemos derivado\(Ma\). Nada nos impide usar la misma justificación para derivar\(Mb\),...,\(Mj\) 2,...,\(Ms\) 7,..., y así sucesivamente hasta que nos quedemos sin espacio o paciencia. Hemos mostrado de manera eficaz la manera\(M\)\(\mathcal{c}\) de probar cualquier constante\(\mathcal{c}\). A partir de esto, f\(yMy\) sigue.
Aquí es importante que haya\(a\) sido sólo alguna constante arbitraria. No habíamos hecho ninguna suposición especial al respecto. Si\(Ma\) fuera una premisa del argumento, entonces esto no mostraría nada de todo\(y\). Por ejemplo:
Esta es la forma esquemática de la regla de introducción universal (∀I):
∗ La constante no\(\mathcal{c}\) debe ocurrir en ninguna suposición no descargada.
Tenga en cuenta que podemos hacer esto para cualquier constante que no ocurra en una suposición no descargada y para cualquier variable.
Tenga en cuenta también que la constante puede no ocurrir en ninguna suposición no descargada, pero puede ocurrir como la suposición de una subprueba que ya hemos cerrado. Por ejemplo, podemos probar ∀\(z\) (\(Dz\)→\(Dz\)) sin premisas.
Eliminación existencial
Una frase con un cuantificador existencial nos dice que hay algún miembro de la UD que satisface una fórmula. Por ejemplo, nos\(xSx\) dice (aproximadamente) que hay al menos uno\(S\). No nos dice qué miembro de la UD satisface\(S\), sin embargo. No podemos concluir inmediatamente\(Sa\),\(Sf\) 23, o cualquier otra instancia de sustitución de la sentencia. ¿Qué podemos hacer? Supongamos que sabíamos\(xSx\) tanto como ∀\(x\) (\(Sx\)→\(Tx\)). Podríamos razonar de esta manera:
Desde\(xSx\), hay algo que es un\(S\). No sabemos qué constantes se refieren a esta cosa, si alguna lo hace, así que llama a esta cosa 'Ishmael'. De ∀\(x\) (\(Sx\)→\(Tx\)), se deduce que si Ismael es un\(S\), entonces es un\(T\). Por lo tanto, Ismael es un\(T\). Porque Ismael es un\(T\), sabemos que\(xTx\).
En este párrafo, introdujimos un nombre para lo que es un\(S\). Le dimos un nombre arbitrario ('Ismael') para que pudiéramos razonar al respecto y derivar algunas consecuencias de que hubiera un\(S\). Dado que 'Ismael' es sólo un nombre falso introducido con el propósito de la prueba y no una constante genuina, no podríamos mencionarlo en la conclusión. Sin embargo, podríamos derivar una frase que no mencione a Ismael; es decir,\(xTx\). Esta frase sí se desprende de las dos premisas.
Queremos que la regla de eliminación existencial funcione de manera similar. Sin embargo, dado que las palabras en inglés como 'Ismael' no son símbolos de QL, no podemos usarlas en pruebas formales. En su lugar, usaremos constantes de QL que de otra manera no aparecen en la prueba.
Una constante que se utiliza para representar lo que sea que satisfaga una afirmación existencial se llama proxy. El razonamiento con el proxy debe ocurrir dentro de una subprueba, y el proxy no puede ser una constante que esté trabajando en otra parte de la prueba.
Esta es la forma esquemática de la regla de eliminación existencial (E):
∗ La constante no\(\mathcal{c}\) debe aparecer en, en\(\mathcal{xAx}\)\(\mathcal{B}\), o en ninguna suposición no descargada.
Dado que la constante proxy es solo un colocador que usamos dentro de la subprueba, no puede ser algo de lo que sepamos algo en particular. Por lo que no puede aparecer en la frase original\(\mathcal{xAx}\) o en una suposición no descargada. Además, no aprendemos nada sobre la constante proxy mediante el uso de la regla E. Por lo que no puede aparecer en\(\mathcal{B}\), la frase que demuestres usando E.
La forma más fácil de satisfacer estos requisitos es elegir una constante completamente nueva al iniciar la subprueba, y luego no usar esa constante en ningún otro lugar de la prueba. Una vez que cierre la subprueba, no vuelva a mencionarla.
Con esta regla, podemos dar una prueba formal de que\(xSx\), en\(x\) conjunto\(Sx\),\(Tx\) conllevan a x\(Tx\).
Observe que esto tiene efectivamente la misma estructura que el argumento en inglés con el que comenzamos, excepto que la subprueba usa la constante proxy '\(i\)' en lugar del nombre falso 'Ishmael'.
Negación de cuantificador
Al traducir del inglés al QL, notamos que\(x\) ¬¬\(\mathcal{A}\) es lógicamente equivalente a ∀\(x\)\(\mathcal{A}\). En QL, son probablemente equivalentes. Podemos probar la mitad de la equivalencia con una prueba bastante espantosa:
Para demostrar que las dos oraciones son genuinamente equivalentes, necesitamos una segunda prueba que asuma\(x\) ¬¬\(\mathcal{A}\) y derive ∀\(x\)\(\mathcal{A}\). Dejamos esa prueba como ejercicio para el lector.
A menudo será útil traducir entre cuantificadores sumando o restando negaciones de esta manera, por lo que agregamos dos reglas derivadas para este propósito. Estas reglas se llaman negación de cuantificador (QN):
\(\mathcal{xA}\)\(\mathcal{x}\)\(\mathcal{A}\)
\(\mathcal{xA}\)\(\mathcal{x}\)¬¬¬¬¬¬¬¬¬¬¬¬\(\mathcal{A}\) QN
Dado que QN es una regla de reemplazo, se puede usar en oraciones enteras o en subfórmulas.