Guía de Demostración

Referencia rápida de los métodos de demostración presentados en estas notas.

Para demostrar $P \Rightarrow Q$

Definición 1 — Método directo

Suponer $P$ . Deducir $Q$ mediante pasos justificados.

Justificación: definición semántica de $\Rightarrow$ .

Definición 2 — Contrarrecíproco

Suponer $\neg Q$ . Deducir $\neg P$ .

Justificación: $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$ .

Definición 3 — Contradicción (para implicaciones)

Suponer $P$ y $\neg Q$ . Derivar una contradicción ( $R \land \neg R$ ).

Justificación: $\neg(P \Rightarrow Q) \equiv P \land \neg Q$ .

Para demostrar $P$

Definición 4 — Contradicción (para proposiciones)

Suponer $\neg P$ . Derivar una contradicción.

Justificación: $(\neg P \Rightarrow \bot) \equiv P$ .

Definición 5 — Análisis de casos

Encontrar $P_1, P_2, \ldots, P_n$ tales que $P_1 \lor P_2 \lor \cdots \lor P_n \equiv \top$ .

Demostrar $P_i \Rightarrow R$ para cada $i$ .

Justificación: $(P_i \Rightarrow R \text{ para todo } i)$ y $(P_1 \lor \cdots \lor P_n) \equiv \top$ implican $R$ .

Para demostrar $P \Leftrightarrow Q$

Definición 6 — Doble implicación

Demostrar $P \Rightarrow Q$ y $Q \Rightarrow P$ por separado.

Justificación: $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ .

Definición 7 — Cadena de equivalencias

Demostrar $P \equiv R_1 \equiv R_2 \equiv \cdots \equiv Q$ .

Justificación: transitividad de $\equiv$ .

Para demostrar $A \subseteq B$

Definición 8 — Subconjunto

Tomar $x \in A$ arbitrario. Deducir $x \in B$ .

Justificación: $A \subseteq B \equiv \forall x : x \in A \Rightarrow x \in B$ .

Para demostrar $A = B$ (conjuntos)

Definición 9 — Igualdad de conjuntos (doble inclusión)

Demostrar $A \subseteq B$ y $B \subseteq A$ .

Justificación: $A = B \equiv A \subseteq B \land B \subseteq A$ .

Definición 10 — Igualdad de conjuntos (bicondicional)

Demostrar $x \in A \Leftrightarrow x \in B$ para $x$ arbitrario.

Para demostrar $\exists x : P(x)$

Definición 11 — Existencia constructiva

Exhibir un valor $a$ y verificar que $P(a)$ es verdadero.

Definición 12 — Existencia no constructiva

Suponer $\neg \exists x : P(x)$ (es decir, $\forall x : \neg P(x)$ ) y derivar una contradicción.

Para demostrar $\exists! x : P(x)$

Definición 13 — Unicidad

Existencia: demostrar $\exists x : P(x)$ .
Unicidad: suponer $P(a)$ y $P(b)$ , deducir $a = b$ .

Para demostrar $\forall n \in \mathbb{N} : P(n)$

Definición 14 — Inducción

Base: demostrar $P(0)$ (o $P(n_0)$ ).
Paso inductivo: suponer $P(n)$ (hipótesis inductiva) y deducir $P(n+1)$ .

Justificación: principio de inducción, derivado de la buena ordenación de $\mathbb{N}$ .

Definición 15 — Inducción fuerte

Hipótesis inductiva: suponer $P(k)$ para todo $k < n$ .

Paso inductivo: deducir $P(n)$ .

No requiere caso base separado (está incluido en el caso $n = 0$ donde la hipótesis es vacua).

Definición 16 — Inducción múltiple

Para enunciados con dos variables naturales $\forall m, n : P(m, n)$ : hacer inducción sobre una variable con la otra fija.

Inducción exterior (sobre $m$ ): demostrar $\forall n : P(0, n)$ y $\forall n : P(m, n) \Rightarrow \forall n : P(m+1, n)$ .
Cada paso puede requerir una inducción interior sobre $n$ .

Para demostrar equivalencias ecuacionales

Definición 17 — Demostración ecuacional

Transformar una expresión en otra equivalente paso a paso, justificando cada transformación con un axioma, teorema o regla de inferencia.

$E_0 \equiv \langle \text{justificación} \rangle \equiv E_1 \equiv \cdots \equiv E_n$

Definición 18 — Equivalencia circular

Para demostrar que $P_1, \ldots, P_n$ son todas equivalentes, demostrar la cadena $P_1 \Rightarrow P_2 \Rightarrow \cdots \Rightarrow P_n \Rightarrow P_1$ .

Para refutar $\forall x : P(x)$

Definición 19 — Contraejemplo

Exhibir un valor $a$ tal que $\neg P(a)$ .

Justificación: $\neg(\forall x : P(x)) \equiv \exists x : \neg P(x)$ .

Consejos prácticos

Leer la estructura del enunciado. Antes de intentar demostrar, identificar la forma lógica: ¿es una implicación?, ¿un bicondicional?, ¿un cuantificador universal?, ¿existencial?
Elegir el método según la estructura.
- $P \Rightarrow Q$ : intentar primero el método directo. Si la hipótesis no da suficiente información, considerar el contrarrecíproco o la contradicción.
- $P \Leftrightarrow Q$ : demostrar ambas direcciones.
- $\forall n : P(n)$ con $n \in \mathbb{N}$ : considerar inducción.
- $\exists x : P(x)$ : buscar un candidato explícito.
Escribir la hipótesis y la meta explícitamente. Al comenzar una demostración, escribir claramente qué se está suponiendo y qué se quiere demostrar.
Usar las definiciones. Muchas demostraciones se desbloquean al reemplazar un concepto por su definición formal.
Trabajar desde ambos extremos. A veces conviene manipular tanto la hipótesis como la conclusión hacia una forma intermedia común.
Si un enfoque no funciona, cambiar de método. No hay vergüenza en abandonar el método directo y probar por contradicción, o viceversa.
Las demostraciones se descubren "hacia atrás" y se escriben "hacia adelante". Es normal explorar la estructura del problema antes de redactar la demostración limpia.

Guía de Demostración

Para demostrar P⇒QP \Rightarrow QP⇒Q

Para demostrar PPP

Para demostrar P⇔QP \Leftrightarrow QP⇔Q

Para demostrar A⊆BA \subseteq BA⊆B

Para demostrar A=BA = BA=B (conjuntos)

Para demostrar ∃x:P(x)\exists x : P(x)∃x:P(x)

Para demostrar ∃!x:P(x)\exists! x : P(x)∃!x:P(x)

Para demostrar ∀n∈N:P(n)\forall n \in \mathbb{N} : P(n)∀n∈N:P(n)