4.4: Reglas de Introducción y Eliminación para Cuantificadores
- Page ID
- 116745
\( \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}\)Como saben, hay dos cuantificadores (\(\exists\)y\(\forall\)). Cada uno de estos tiene una regla de introducción y una regla de eliminación, por lo que hay\(4\) reglas para presentar en esta sección. Las pruebas en pueden utilizar ambas reglas, más todas las reglas de (como las reglas de negación y los teoremas básicos, incluidas las reglas de introducción y eliminación), y también cualquier otro teorema que haya sido previamente probado.
4.4A. \(\exists\)-introducción
Tenemos que determinar cómo probar una conclusión del formulario\(\exists x \in X, \dots\). Por ejemplo, en un misterio de asesinato, tal vez el inspector Thinkright reúne a los sospechosos en una habitación y les dice: “Alguien en esta habitación tiene el pelo rojo”. Eso es una\(\exists\) -declaración. (Con una clave de simbolización apropiada, en la que\(P\) está el conjunto de todas las personas en la habitación, y\(R(x)\) es el predicado “\(x\)tiene el pelo rojo”, es la aseveración\(\exists p \in P, R(p)\).) ¿Cómo convencería el Inspector a un escéptico de que la afirmación es cierta? La forma más fácil sería exhibir un ejemplo explícito de una persona en la habitación que tiene el pelo rojo. Por ejemplo, si Jim está en la habitación, y tiene el pelo rojo, el Inspector podría decir:
“Mira, Jim está sentado justo ahí junto a la puerta, y ahora, cuando me quite la peluca, puedes ver por ti mismo que tiene el pelo rojo. Entonces tengo razón en que alguien en esta habitación tiene el pelo rojo”.
En general, la forma más sencilla de probar\(\exists p \in P, R(p)\) es verdad es encontrar un ejemplo específico de una\(p\) que haga\(R(p)\) realidad. Esa es la esencia de la regla\(\exists\) -intro.
Aquí hay un principio para recordar:
La prueba de una aseveración que comienza
“existe\(x \in X\), tal que”.
por lo general se basará en la declaración. “Let”\(x = \square\),
donde la caja se llena con un elemento apropiado de\(X\).
La mayoría de los matemáticos no están familiarizados con la terminología de reglas de introducción y reglas de eliminación. En lugar de decir que esta es la regla\(\exists\) -introducción, la llamarían “prueba construyendo un ejemplo”, o “dando un ejemplo explícito”, u otras palabras en el mismo sentido.
Aquí hay algunas pruebas que usan\(\exists\) -introducción, pero no podemos hacer mucho con una sola regla del cuantificador —los ejemplos serán más interesantes cuando tengamos más reglas con las que trabajar.
Demostrar que hay un número natural\(n\), tal que\(n^2 = 64\).
Solución
Prueba.
Vamos\(n = 8 \in \natural\). Entonces\(n^2 = 8^2 = 64\).
Demostrar que hay un número real\(c\), tal que\(5c^2 - 5c + 1 < 0\).
Solución
Prueba.
Vamos\(c = 1/2 \in \mathbb{R}\). Entonces\[\begin{aligned} 5c^2 - 5c + 1 = 5 \left(\frac{1}{2}\right)^2 - 5 \left(\frac{1}{2}\right) + 1 = \frac{5}{4} - \frac{5}{2} + 1 = -\frac{1}{4} < 0 . & \end{aligned}\]
Vamos\(N = \{1,3,5,7\}\). Demostrar que existe\(n \in N\), tal que\(n^3-11n^2+31n \neq 21\).
Solución
Prueba.
Vamos\(n = 5 \in N\). Entonces\[\begin{aligned} n^3-11n^2+31n = 5^3-11(5^2)+31(5) = 125 - 11(25) + 155 = 125 - 275 + 155 = 5 \neq 21 . \end{aligned}\]
- Demostrar que hay un número real\(r\), tal que\(2r^2 + 9r + 4 = 0\).
- Vamos\(B = \{1,3,5,7\}\). Demostrar que existe\(b \in B\), tal que\(3b + 1 = (b-1)^2\).
- Demostrar que existen números naturales\(m\) y\(n\), tal que\(m^2 = n^3 + 1 > 1\).
- Mostrar que hay un entero\(n\), tal que\(3n^2 = 5n + 2\).
- Supongamos que\(a\) es un número real. Mostrar que hay un número real\(x\), tal que\(7x - 5 = a\).
\(\exists\)-eliminación
Quizás el inspector Thinkright sepa que uno de los hombres encendió un partido a medianoche, pero no sabe quién era. El Inspector podría decir,
“Sabemos que uno de los hombres encendió un partido a medianoche. Llamemos a este misterioso caballero 'señor X'. Porque los partidos diestros no están permitidos en la isla, sabemos que el señor X es zurdo. De ahí que el señor X no sea mayordomo, porque todos los mayordomos de este pueblo son diestros.”.
y así sucesivamente, y así sucesivamente, contándonos cada vez más sobre el señor X, basado sólo en el supuesto de que encendió un cerillo a medianoche.
La situación en las pruebas matemáticas es similar. Supongamos que sabemos que existe un elemento del conjunto\(A\). Entonces sería útil tener un nombre para este misterioso elemento, para que podamos hablar de ello. Pero un matemático no llamaría al elemento “Mr. X”: si es un elemento del conjunto\(A\), entonces probablemente lo llamaría\(a\) (o\(a_1\) si va a haber otros elementos de\(A\) para hablar). En general, la idea de la regla\(\exists\) -eliminación es:
Si\(\exists x \in X\),\(P(x)\) se sabe que es verdad, entonces podemos
dejar\(x\) ser un elemento de\(X\), tal que\(P(x)\) es cierto.
En el resto de la prueba, podemos asumir sólo dos cosas sobre\(x\): eso\(x \in X\), y eso\(P(x)\) es cierto.
Demostrar que si existe\(a \in \mathbb{R}\), tal que\(a^3 + a + 1 = 0\), entonces existe\(b \in \mathbb{R}\), tal que\(b^3 + b - 1 = 0\).
Solución
Prueba.
Supongamos que existe\(a \in \mathbb{R}\), tal que\(a^3 + a + 1 = 0\). Vamos\(b = -a\). Luego\(b \in \mathbb{R}\), y\ [\ begin {alineado}
b^ {3} +b-1 & =( -a) ^ {3} + (-a) -1\\
&=-a^ {3} -a-1\\
&=-\ izquierda (a^ {3} +a+1\ derecha)\\
&=-0\\
&=0
\ end {alineado}\]
(Cuarta Línea: por el definición de\(a\))
según se desee.
Asumir\(A\) y\(B\) son conjuntos de números reales.
- Demostrar que si existe\(a \in A\), tal que\(2a > 5\), entonces existe\(b \in A\), tal que\(b > 0\).
- Demostrar que si existe\(x \in \mathbb{R}\), tal que\(x - 2 \in A\), entonces existe\(y \in \mathbb{R}\), tal que\(3y \in A\).
- Demuéstralo si\(A \cap B \neq \emptyset\), entonces\(A \neq \emptyset\).
\(\forall\)-eliminación
Quizás el inspector Thinkright sepa que Jeeves es mayordomo en el pueblo, y que todos los mayordomos del pueblo son diestros. Bueno, entonces es obvio para el Inspector que Jeeves es diestro. Este es un ejemplo de\(\forall\) -eliminación: si sabes que algo es cierto sobre cada elemento de un conjunto, entonces es cierto sobre cualquier elemento particular del conjunto. \[\text { If } \forall x \in X, P(x) \text { is true, and } a \in X \text {, then } P(a) \text { is true. }\]
Supongamos
- \(C \subset \mathbb{R}\), y
- \(\forall x \in \mathbb{R}, \bigl( (x^2 = 9) \Rightarrow (x \in C) \bigr)\).
Espectáculo\(\exists c \in \mathbb{R}, c \in C\).
Solución
Prueba.
Vamos\(c = 3 \in \mathbb{R}\). Entonces\(c^2 = 3^2 = 9\), y dejando\(x = c\) entrar Hipótesis (2) nos dice que\[( c^2 = 9) \Rightarrow ( c \in C) .\] Por lo tanto\(c \in C\).
Asumir\(A \neq \emptyset\) y\(A \subset B\). Demostrar\(\exists b, (b \in B)\).
Solución
Prueba.
Porque no\(A\) es el conjunto vacío, sabemos que tiene al menos un elemento; es decir, tenemos\(\exists x, (x \in A)\). De ahí, podemos dejar\(a\) ser algún elemento de\(A\). Ahora, vamos\(b = a\). Porque\(A \subset B\), sabemos que cada elemento de\(A\) es un elemento de\(B\). En particular, ya que\(b = a \in A\), esto significa que\(b \in B\).
Al aplicar\(\forall\) -eliminación, la variable no necesita llamarse “\(x\),” (podría ser\(y\)\(z\) o cualquier otra variable), y la constante no necesita llamarse “\(a\)” (podría ser cualquier elemento de \(X\)). Sin embargo, si la variable ocurre más de una vez en la fórmula, es importante reemplazar todas sus ocurrencias con\(a\). Por ejemplo, si\(a \in X\), entonces, desde\(\forall x \in X, \bigl( A(x) \Rightarrow B(x) \bigr)\), podemos concluir\(A(a) \Rightarrow B(a)\), pero no\(A(a) \Rightarrow B(x)\) o\(A(x) \Rightarrow B(a)\).
- Asumir\(\forall x \in \mathbb{R}, (x^2 \in Z)\). Espectáculo\(16 \in Z\).
- Asumir\(A \subset B\) y\(A \neq \emptyset\). Espectáculo\(B \neq \emptyset\).
- Asumir
- para cada\(x \in A\), ya sea\(x \in B\), o\(x < 0\), y
- existe\(a \in A\), tal que\(a > 0\).
Espectáculo\(B \neq \emptyset\).
\(\forall\)-introducción
Si el inspector Thinkright necesita verificar que todos los mayordomos de la ciudad han visto las aurora boreal, probablemente obtendría una lista de todos los mayordomos, y los verificaría uno por uno. Ese es un enfoque válido, pero podría llevar mucho tiempo si la lista es muy larga. En matemáticas, tal comprobación uno por uno a menudo no solo consume mucho tiempo, sino imposible. Por ejemplo, el conjunto\(\natural\) es infinito, entonces, si queremos mostrar\(\forall n \in \natural, (\text{$2n$ is even})\), entonces nunca terminaríamos si intentáramos pasar por todos los números naturales uno por uno. Entonces tenemos que lidiar con muchos números a la vez.
Considera la siguiente deducción simple:
Hipótesis:
Cada mayordomo de la ciudad se levantó antes de las 6 de la mañana de hoy
Todos los que se levantaron antes de las 6am de hoy, vieron la aurora.
Conclusión:
Todos los mayordomos de la ciudad vieron la aurora.
Esto es claramente una deducción válida en inglés. Vamos a traducirlo para analizar cómo pudimos llegar a una conclusión sobre todos los mayordomos, sin verificar cada uno de ellos individualmente. Aquí hay una clave de simbolización:
\(B\): El conjunto de todos los mayordomos de la ciudad.
\(P\): El conjunto de todas las personas.
\(U(x)\):se levantó antes de las 6am de hoy.
\(S(x)\):vio la aurora.
Ahora podemos traducir nuestra deducción en inglés, de la siguiente manera:
Hipótesis:
\(\forall b \in B, U(b)\).
\(\forall p \in P, \bigl( U(p) \Rightarrow S(p) \bigr)\).
Conclusión:\(\forall b \in B, S(b)\).
¿Cómo justificamos la conclusión? Bueno, supongamos por un momento que empecemos a revisar a cada mayordomo de la ciudad, y eso\(j\) representa a Jimmy, quien es uno de los mayordomos de la ciudad. Entonces nuestra primera hipótesis nos permite concluir\(U(j)\). Dado que Jimmy es una persona, nuestra segunda hipótesis nos permite concluir eso\(U(j) \Rightarrow S(j)\). Entonces, usando\(\Rightarrow\) -eliminación, concluimos\(S(j)\). Pero no había nada especial en nuestra elección de Jimmy. Todo lo que sabemos de él, es que es mayordomo en la localidad. Entonces podríamos usar exactamente el mismo argumento para deducir\(S(b)\) para cualquier mayordomo\(b\) del pueblo.
Es así como justificamos una\(\forall\) -introducción. Si podemos probar que la conclusión deseada es cierta para un elemento arbitrario de un conjunto, cuando no asumimos nada sobre el elemento excepto que pertenece al conjunto, entonces la conclusión debe ser cierta para cada elemento del conjunto.
Escribimos la deducción anterior de la siguiente manera:
Supongamos que todos los mayordomos de la ciudad se levantaron antes de las 6 También asumir que todos los que se levantaron antes de las 6 de la mañana de hoy, vieron la aurora. Entonces cada mayordomo de la ciudad vio la aurora.
- Prueba
-
Vamos a\(b\) representar a un mayordomo arbitrario en la ciudad. Entonces, como todos los mayordomos se levantaron antes de las 6 de la mañana, sabemos que se\(b\) levantó antes de las 6 de la mañana. Por hipótesis, esto implica que\(b\) vio la aurora. Dado que\(b\) es un mayordomo arbitrario en la ciudad, concluimos que cada mayordomo en la ciudad vio la aurora.
Este razonamiento lleva a la regla\(\forall\) -introducción: para probar que cada elemento de un conjunto\(X\) tiene una cierta propiedad, basta con mostrar que un elemento arbitrario de\(X\) tiene la propiedad deseada. Por ejemplo, si queremos probar\(\forall b \in B, P(b)\), entonces nuestra prueba debe comenzar con la frase “Dejemos\(b\) ser un elemento arbitrario de”\(B\). (No obstante, esto se puede abreviar como: “Dado\(b \in B\),...”) Después de esto, nuestra tarea será demostrar que eso\(P(b)\) es cierto, sin asumir nada de\(b\) otra cosa que no sea un elemento de\(B\).
La prueba de una aseveración que comienza “para todos”\(x \in X\)
, suele comenzar con “Let\(x\) be an arbitrario element of\(X\)"
(o, para abreviar, “\(x \in X\)Given”).
Es importante no asumir nada de\(x\) otra cosa que no sea que sea un elemento de\(X\). Si eliges\(x\) ser un elemento particular de\(X\) que tenga alguna propiedad especial, entonces tu deducción no será válida para todos los elementos del conjunto.
Supongamos que quisiéramos justificar la siguiente deducción:
A todos los mayordomos de la ciudad no les gusta Jimmy, y Jimmy es mayordomo en la ciudad.
Por lo tanto, a todos los mayordomos de la ciudad no les gustan.
Entonces basta con mostrar, para un mayordomo arbitrario\(b\), que\(b\) no le gusta\(b\). Podríamos probar la siguiente prueba:
Solución
Intento de prueba.
\(b\)Déjese ser Jimmy, que es mayordomo en la ciudad. Entonces, como a todos los mayordomos de la ciudad no les gusta Jimmy, sabemos que\(b\) no le gusta Jimmy. Ya que\(\text{Jimmy} = b\), esto significa\(b\) disgustos\(b\), como se desee. Así que a cada mayordomo de la ciudad no le gusta.
Esta prueba ciertamente no es válida, sin embargo. Dejar no\(b = \text{Jimmy}\) hace\(b\) un mayordomo arbitrario; más bien, hace\(b\) un mayordomo muy especial, el que a todos no les gusta. En este caso, las conclusiones sobre las que son ciertas no\(b\) son necesariamente ciertas sobre los demás mayordomos.
Otro punto que debe enfatizarse es que un miembro arbitrario de un conjunto no es lo mismo que un miembro aleatorio de un conjunto. Si queremos demostrar que todos los mayordomos han visto la aurora, no basta con elegir un mayordomo al azar, preguntar si vio la aurora y sacar una conclusión sobre todos los mayordomos en base a esa única respuesta. Es sólo si podemos determinar mediante deducción lógica que no importa qué mayordomo escojamos, esa persona vio la aurora, que podemos concluir que todos los mayordomos vieron la aurora.
¿Cuál de las reglas\(4\) del cuantificador ilustra cada deducción?
- Todos los que comían ayer en la cafetería están enfermos hoy. ¡Oh, no! Susie comió en la cafetería — ¡debe estar enferma!
- Susie comió ayer en la cafetería, así que estoy seguro que alguien comió ayer en la cafetería.
- Sin saber cuál de los atletas era, me di cuenta de que debió haber comido ayer en la cafetería. La única manera que puede ser cierto es si cada atleta comió ayer en la cafetería.
- Nuestro reportero de comida dice que una mujer derribó una caja grande de frijoles lima mientras comía ayer en la cafetería. Quienquiera que sea, llamémosla “Sra. Clumy”. Entonces el titular de esta mañana puede ser “¡La señora Clumy derramó los frijoles!”