Cuantificador universal
Sea E un conjunto y p(x) una proposición que depende de una variable x∈E.
Podemos crear la proposición:
∀x∈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:
- ∀x∈R,x2=1⇒(x=1∨x=−1) es verdadera
- ∀x∈R,x2=1⇒x=1 es falsa
- ∀x∈N,x2=1⇒x=1 es verdadera
Cuantificador existencial
Es posible igualmente crear la proposición:
∃x∈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:
- ∃x∈R,x2=−1 es falsa
- ∃x∈C,x2=−1 es verdadera
Negación de cuantificadores
¬(∀x∈E,p(x))⇔(∃x∈E,¬p(x))
(Si no es cierto que todos los matemáticos son antipáticos, hay al menos uno que es simpático)
¬(∃x∈E,p(x))⇔(∀x∈E,¬(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:
¬(∀n∈N,∃m∈N,m=n−1)⇔(∃n∈N,∀m∈N,m≠n−1)
Cuantificadores en el conjunto vacio
En el caso particular de que E sea el conjunto vacio, toda proposición de la forma ∃x∈E,p(x) es falsa y toda proposición de la forma ∀x∈E,p(x) es verdadera.
Siempre que E no sea el conjunto vacio, la proposición:
(∀x∈E,p(x))⇒(∃x∈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:
(∀x∈E∀y∈Fp(x,y))⇔(∀y∈F∀x∈Ep(x,y))
(∃x∈E∃y∈Fp(x,y))⇔(∃y∈F∃x∈Ep(x,y))
No obstante, a veces no resulta posible cambiar el orden:
∀x∈R,∀y∈[x,+∞[...
Cuando se cambia el orden de dos cuantificadores de tipos diferentes, puede cambiar el valor de la proposición global. Por ejemplo, tenemos:
(∃x∈E∀y∈Fp(x,y))⇒(∀y∈F∃x∈Ep(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.
(∃x∈R∀y∈Rxy=0)⇒(∀y∈R∃x∈Rxy=0) (Ambas son verdaderas)
(∃x∈R∀y∈Rxy=1)⇒(∀y∈R∃x∈Rxy=1) (Ambas son falsas)
(∃x∈R∗∀y∈R∗xy=1)⇒(∀y∈R∗∃x∈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:
{¬p⇒q¬p⇒¬q
sean verdaderas, entonces p es verdadera.
En particular, si una propiedad p es tal que ¬p⇒p entonces p es verdadera.
Inducción simple
Si una proposición p que depende de una variable n∈N verifica:
{p(0) es verdadera∀n∈Np(n)⇒p(n+1)
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∈N verifica:
{p(0) y p(1) son verdaderas∀n∈Np(n)∧p(n+1)⇒p(n+2)
entonces p es verdadera para todos los naturales.
Ejemplo:
Sea (un)n∈N la serie definida por:
{u0=1,u1=2∀n∈N,un+2=6un−un+1
Determinar un para todo natural n.
Inducción completa
Si una proposición p que depende de una variable n∈N verifica:
{p(0) es verdadera∀n∈N,(∀k∈{0,..n},p(k))⇒p(n+1)
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∈N tal que n≥2.
Supongamos que todo natural k∈N tal que 2≤k≤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≤d≤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