Bi-implication

The Bi-implication Connective

A bi-implication is a statement of the form ”$P$ if and only if $Q$”, written $P \Leftrightarrow Q$ or ”$P$ iff $Q$”.

Truth Table

$P$	$Q$	$P \Leftrightarrow Q$
T	T	T
T	F	F
F	T	F
F	F	T

$P \Leftrightarrow Q$ is true exactly when $P$ and $Q$ have the same truth value.

Logical Equivalence

$P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$

This decomposition is crucial for proofs.

Proof Strategy for Bi-implication

To prove $P \Leftrightarrow Q$, you must prove both directions:

1. Forward direction: Prove $P \Rightarrow Q$
2. Reverse direction: Prove $Q \Rightarrow P$

These two proofs are typically separate and may use different techniques.

Example

Statement: An integer $n$ is even if and only if $n^2$ is even.

Proof:

$(\Rightarrow)$ If $n$ is even, then $n^2$ is even:

• If $n$ is even, then $n = 2k$ for some integer $k$
• So $n^2 = 4k^2 = 2(2k^2)$
• Since $2k^2$ is an integer, $n^2$ is even

$(\Leftarrow)$ If $n^2$ is even, then $n$ is even:

• By contrapositive: if $n$ is odd, then $n^2$ is odd
• If $n = 2k + 1$ for some integer $k$
• Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$
• This is odd, so by contrapositive the claim holds

Therefore $n$ is even if and only if $n^2$ is even.

Alternative Proofs

Sometimes both directions can be proved simultaneously using logical equivalences.

Example

Statement: $P \Rightarrow Q$ is logically equivalent to $\neg P \lor Q$.

Proof:

Compare truth tables:

$P$	$Q$	$\neg P$	$P \Rightarrow Q$	$\neg P \lor Q$
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

Since both columns are identical, $P \Rightarrow Q \Leftrightarrow \neg P \lor Q$.

Chain of Bi-implications

For a chain of equivalences:

$P_1 \Leftrightarrow P_2 \Leftrightarrow P_3 \Leftrightarrow \cdots \Leftrightarrow P_n$

you can prove:

$P_1 \Rightarrow P_2 \Rightarrow P_3 \Rightarrow \cdots \Rightarrow P_n \Rightarrow P_1$

This proves all pairwise equivalences by transitivity.

Example

Statement: $x = 1 \Leftrightarrow x^2 = 1$ (for real $x$).

This is false! Check: $x = -1$ gives $x^2 = 1$ but $x \neq 1$.

Correct statement: For real $x \geq 0$, $x = 1 \Leftrightarrow x^2 = 1$.

Common Pitfalls

Proving Only One Direction

Trap: Proving $P \Rightarrow Q$ does not prove $P \Leftrightarrow Q$.

You must prove both directions separately.

Assuming Equivalence

Trap: Do not assume $P \Leftrightarrow Q$ before proving it.

If you use logical equivalences in scratch work, verify each step is truly an equivalence.

Missing Cases

Trap: A bi-implication over a domain may fail for certain values.

Always check the domain: ”$n$ is prime” $\Leftrightarrow$ ”$n$ has exactly two divisors” fails for $n = 1$.

---

Summary

• $P \Leftrightarrow Q$ means ”$P$ if and only if $Q$”
• Equivalent to $(P \Rightarrow Q) \land (Q \Rightarrow P)$
• Prove both directions separately
• Check that the domain is correct for the equivalence to hold