Cuantificador universal
Sea \(E\) un conjunto y \(p(x)\) una proposición que depende de una variable \(x\in E\).
Podemos crear la proposición:
\[\forall x \in E,\;p(x) \]
La cual será por definición verdadera si y sólo si \(p(x)\) es verdadera para todos los valores de \(x\) en \(E\).
Ejemplos:
- \(\forall x \in \mathbb{R},\; x^{2}=1\Rightarrow (x=1 \vee x=-1)\) es verdadera
- \(\forall x \in \mathbb{R},\; x^{2}=1\Rightarrow x=1\) es falsa
- \(\forall x \in \mathbb{N},\; x^{2}=1\Rightarrow x=1\) es verdadera
Cuantificador existencial
Es posible igualmente crear la proposición:
\[\exists x \in E,\;p(x) \]
La cual será por definición verdadera si y sólo si \(p(x)\) es verdadera para al menos un valor de \(x\) en \(E\).
Ejemplos:
- \(\exists x \in \mathbb{R},\; x^{2}=-1\) es falsa
- \(\exists x \in \mathbb{C},\; x^{2}=-1\) es verdadera
Negación de cuantificadores
\[\neg (\forall x \in E, \; p(x)) \Leftrightarrow (\exists x \in E,\;\neg p(x))\]
(Si no es cierto que todos los matemáticos son antipáticos, hay al menos uno que es simpático)
\[\neg (\exists x \in E, \; p(x)) \Leftrightarrow (\forall x \in E,\;\neg (p(x)))\]
(Si no es cierto que existe un matemático simpático, es que todos ellos son antipáticos)
En caso de que existan varios cuantificadores, para obtener la negación hay que cambiar cada uno de ellos y se cambia la propiedad final por su negación:
\[ \neg (\forall n\in \mathbb{N}, \exists m\in\mathbb{N}, \; m=n-1) \Leftrightarrow (\exists n\in \mathbb{N}, \forall m\in\mathbb{N}, \; m\neq n-1)\]
Cuantificadores en el conjunto vacio
En el caso particular de que \(E\) sea el conjunto vacio, toda proposición de la forma \(\exists x \in E, \; p(x)\) es falsa y toda proposición de la forma \(\forall x \in E, \; p(x)\) es verdadera.
Siempre que \(E\) no sea el conjunto vacio, la proposición:
\[(\forall x\in E,\;p(x))\Rightarrow (\exists x\in E,\;p(x)) \]
es verdadera.
Orden de los cuantificadores
Cuando resulta factible un cambio en el orden de dos cuantificadores succesivos del mismo tipo, dicho cambio no afecta al valor de la proposición global.
Ejemplos:
\[(\forall x\in E\;\forall y\in F\; p(x,y))\Leftrightarrow(\forall y\in F\;\forall x\in E\;p(x,y))\]
\[(\exists x\in E\;\exists y\in F\; p(x,y))\Leftrightarrow(\exists y\in F\;\exists x\in E\;p(x,y))\]
No obstante, a veces no resulta posible cambiar el orden:
\[\forall x\in\mathbb{R}, \forall y\in [x,+\infty[ \;...\]
Cuando se cambia el orden de dos cuantificadores de tipos diferentes, puede cambiar el valor de la proposición global. Por ejemplo, tenemos:
\[(\exists x\in E\;\forall y\in F\; p(x,y))\Rightarrow(\forall y\in F\;\exists x\in E\;p(x,y))\]
En la primera de las dos proposiciones \(x\) es independiente de \(y\) y normalmente dicha proposición resulta mas "útil" o mas dificil de demostrar que la segunda en la cual \(x\) puede depender de \(y\). De hecho, la primera implica la segunda.
\((\exists x\in \mathbb{R}\;\forall y\in \mathbb{R}\; xy=0)\Rightarrow(\forall y\in \mathbb{R}\;\exists x\in \mathbb{R}\;xy=0)\) (Ambas son verdaderas)
\((\exists x\in \mathbb{R}\;\forall y\in \mathbb{R}\; xy=1)\Rightarrow(\forall y\in \mathbb{R}\;\exists x\in \mathbb{R}\;xy=1)\) (Ambas son falsas)
\((\exists x\in \mathbb{R}^{*}\;\forall y\in \mathbb{R}^{*}\; xy=1)\Rightarrow(\forall y\in \mathbb{R}^{*}\;\exists x\in \mathbb{R}^{*}\;xy=1)\) (La primera es falsa y la segunda es verdadera)
Razonamiento por el absurdo
Si una proposición \(p\) es tal que existe una proposición \(q\) tal que las proposiciones:
\[\left\{\begin{matrix} \neg p \Rightarrow q\\ \neg p \Rightarrow \neg q\end{matrix}\right.\]
sean verdaderas, entonces \(p\) es verdadera.
En particular, si una propiedad \(p\) es tal que \(\neg p \Rightarrow p\) entonces \(p\) es verdadera.
Inducción simple
Si una proposición \(p\) que depende de una variable \(n \in \mathbb{N}\) verifica:
\[\left\{\begin{align} &p(0) \text{ es verdadera} \\ &\forall n\in \mathbb{N}\; p(n)\Rightarrow p(n+1)\end{align}\right.\]
entonces \(p\) es verdadera para todos los naturales.
Si fueramos a demostrar que una proposición \(p(n)\) es verdadera para todo natural \(n\), será necesario:
- Definir claramente la proposición \(p(n)\)
- Realizar la verificación inicial, \(p(0)\) es verdadera
- Demostrar la implicación
- Concluir
Inducción doble
Si una proposición \(p\) que depende de una variable \(n \in \mathbb{N}\) verifica:
\[\left\{\begin{align} &p(0) \text{ y } p(1) \text{ son verdaderas} \\ &\forall n\in \mathbb{N}\; p(n) \wedge p(n+1) \Rightarrow p(n+2)\end{align}\right.\]
entonces \(p\) es verdadera para todos los naturales.
Ejemplo:
Sea \((u_{n})_{n\in \mathbb{N}}\) la serie definida por:
\[\left\{\begin{align} &u_{0}=1,\;u_{1}=2 \\ &\forall n\in \mathbb{N},\; u_{n+2}=6u_{n}-u_{n+1}\end{align}\right.\]
Determinar \(u_{n}\) para todo natural \(n\).
Inducción completa
Si una proposición \(p\) que depende de una variable \(n \in \mathbb{N}\) verifica:
\[\left\{\begin{align}
&p(0) \text{ es verdadera} \\ &\forall n\in \mathbb{N},\;(\forall k\in \{0,..n\}, p(k)) \Rightarrow p(n+1)\end{align}\right.\]
entonces \(p\) es verdadera para todos los naturales.
Ejemplo:
Demostrar por inducción completa que todo natural igual o superior a 2 admite un divisor primo.
Solución:
Recordemos que un número primo es un natural igual o superior a 2 que sólo admite como divisores 1 y sí mismo.
2 admite un divisor primo que 2.
Sea \(n\in \mathbb{N}\) tal que \(n\geq2\).
Supongamos que todo natural \(k\in \mathbb{N}\) tal que \(2\leq k\leq n\) admite un divisor primo.
Si \(n+1\) es primo, admite un divisor primo que es \(n+1\). Si no lo es, admite un divisor \(d\) tal que \(2\leq d\leq n\). Usamos la hipótesis de inducción, \(d\) admite un divisor primo que también es divisor primo de \(n+1\). En ambos casos \(n+1\) admite un divisor primo.
Por inducción completa, ha quedado demostrado que todo natural igual o superior a 2 admite un divisor primo.
Inicio