If and only if, existence, and disproof
Last modified: 2026-11-06 16:28:53 (PST)
Source
Adapted from Kameron Decker Harris’s Fall 2026 lecture notes “Proving Non-Conditional Statements, Disproof”, which are typed transcriptions of Scott Wehrwein’s Spring 2025 handwritten lecture notes. These come from those notes:
The exercises are new.
Exercise 1 (A sum of squares equal to zero) Let \(x\) and \(y\) be real numbers. Prove: \(x^2 + y^2 = 0\) if and only if \(x = 0\) and \(y = 0\) (Definition: If and only if).
Hint: prove the two directions one at a time.
Solution 1. If \(x = 0\) and \(y = 0\), then \(x^2 + y^2 = 0\). Suppose \(x = 0\) and \(y = 0\). Then \(x^2 + y^2 = 0^2 + 0^2 = 0\).
If \(x^2 + y^2 = 0\), then \(x = 0\) and \(y = 0\). Suppose \(x^2 + y^2 = 0\). A square of a real number is never negative, so \(y^2 \ge 0\), and
\[ \begin{aligned} x^2 &= -y^2 && \text{(subtract } y^2 \text{ from both sides of } x^2 + y^2 = 0 \text{)} \\&\le 0. && \text{(} y^2 \ge 0 \text{)} \end{aligned} \]
Also \(x^2 \ge 0\), so \(x^2 = 0\), and so \(x = 0\). The same steps with \(x\) and \(y\) swapped give \(y = 0\).
Theorem 1 (A biconditional is two conditionals) For propositions \(P\) and \(Q\),
\[ (P \Leftrightarrow Q) \equiv \mathopen{}\left((P \Rightarrow Q) \land (Q \Rightarrow P)\right)\mathclose{}. \]
Example 1 (Proving both directions) Claim: let \(n\) be an integer. Then \(n\) is even if and only if \(n + 2\) is even.
By Theorem 1, it is enough to prove two conditionals.
Remark 1 (The shape of an “if and only if” proof). A proof of “\(P\) if and only if \(Q\)” has two parts:
(\(\Rightarrow\)) Suppose \(P\).
\(\vdots\)
Therefore \(Q\).
(\(\Leftarrow\)) Suppose \(Q\).
\(\vdots\)
Therefore \(P\).
Each part is a proof of a conditional, so each can be a direct proof (Definition: Direct proof), a proof by contrapositive (Definition: Proof by contrapositive), or a proof by contradiction (Definition: Proof by contradiction), and the two parts need not use the same method.
Theorem 2 (A cycle of conditionals) Let \(P_1, P_2, \ldots, P_k\) be propositions. If \(P_1 \Rightarrow P_2\), \(P_2 \Rightarrow P_3\), \(\ldots\), \(P_{k-1} \Rightarrow P_k\) and \(P_k \Rightarrow P_1\) are all true, then \(P_1, \ldots, P_k\) all have the same truth value.
Example 2 (Three ways to say “odd”) Let \(n\) be an integer, and consider
By Theorem 2, three conditionals show that all three have the same truth value.
In each step the new multiplier, \(k + 1\), \(m - 1\) or \(j\), is an integer (Remark: Facts about integers used without proof). Proving all six conditionals between pairs would have taken twice as many steps.
Exercise 2 (A solution in integers) Show that there are integers \(x\) and \(y\) with \(5x + 3y = 1\).
Solution 2. Take \(x = 2\) and \(y = -3\). Then \(5x + 3y = 5 \cdot 2 + 3 \cdot(-3) = 10 - 9 = 1\). So integers with \(5x + 3y = 1\) exist (Definition: Existential quantifier). Other pairs work too, such as \(x = -1\) and \(y = 2\).
Definition 1 (Constructive proof) A constructive proof (Wikipedia contributors 2026) of a proposition \(\exists x \in S,\ P(x)\) with an existential quantifier names a particular element of \(S\) and shows that \(P\) is true of it.
Remark 2 (Several existential quantifiers). A proposition can open with several existential quantifiers. A constructive proof of it names one element for each quantifier. For example, a constructive proof of “there are integers \(m\) and \(n\) with \(m + n = 1\)” names one value of \(m\) and one of \(n\).
Example 3 (Half of a positive number) Claim: for every positive real number \(x\), there is a positive real number \(y\) with \(y < x\).
Let \(x\) be a positive real number. We give a constructive proof of “there is a positive real number \(y\) with \(y < x\)” for this \(x\): take \(y = \frac{x}{2}\). Then \(y > 0\), because \(x > 0\), and
\[ \begin{aligned} x - y &= x - \frac{x}{2} && \text{(substitute } y = \tfrac{x}{2} \text{)} \\&= \frac{x}{2} && \text{(arithmetic)} \\&> 0, && \text{(} x > 0 \text{)} \end{aligned} \]
so \(y < x\). The element named, \(\frac{x}{2}\), depends on \(x\), which a “for every \(x\), there is a \(y\)” statement allows.
The solution to Exercise 2 is also a constructive proof: it names the integers \(2\) and \(-3\).
Definition 2 (Non-constructive proof) A non-constructive proof (Wikipedia contributors 2026) of a proposition \(\exists x \in S,\ P(x)\) shows that it is true without naming any element \(x\) of \(S\) for which \(P(x)\) is true. It is a proof that is not a constructive proof.
Example 4 (An irrational power of an irrational number) Claim: there are irrational numbers \(x\) and \(y\) (Definition: Irrational numbers) for which \(x^y\) is rational (Definition: Rational numbers).
The number \(\sqrt{2}\) is irrational (Theorem: \(\sqrt{2}\) is irrational). Consider \(\sqrt{2}^{\sqrt{2}}\), and take two cases (Definition: Proof by cases, proof by exhaustion).
Case 1: \(\sqrt{2}^{\sqrt{2}}\) is rational. Then \(x = \sqrt{2}\) and \(y = \sqrt{2}\) work.
Case 2: \(\sqrt{2}^{\sqrt{2}}\) is irrational. Then take \(x = \sqrt{2}^{\sqrt{2}}\) and \(y = \sqrt{2}\), both irrational, and
\[ \begin{aligned} x^y &= \mathopen{}\left(\sqrt{2}^{\sqrt{2}}\right)\mathclose{}^{\sqrt{2}} && \text{(substitute } x \text{ and } y \text{)} \\&= \sqrt{2}^{\sqrt{2} \cdot\sqrt{2}} && \text{(a power of a power multiplies the exponents)} \\&= \sqrt{2}^{2} && \text{(} \sqrt{2} \cdot\sqrt{2} = 2 \text{)} \\&= 2, \end{aligned} \]
which is rational, since \(2 = \frac{2}{1}\).
Every number is rational or irrational, so one of the cases holds, and the claim is true. The proof does not say which case holds, so it does not name a pair \(x, y\) that works.
Exercise 3 (Prove or disprove) Prove or disprove: for every real number \(x\), if \(x^2 > 1\), then \(x > 1\).
Solution 3. The proposition is false. Take \(x = -2\). Then \(x^2 = 4 > 1\), but \(x > 1\) is false. So \(x = -2\) makes “if \(x^2 > 1\), then \(x > 1\)” false (Definition: Implies), and so it is a counterexample (Definition: Counterexample) to the proposition.
Definition 3 (Disproof) A disproof of a proposition \(P\) is a proof of its negation, \(\neg P\).
Example 5 (No integer squares to two) Claim to disprove: there is an integer \(n\) with \(n^2 = 2\).
By Theorem: De Morgan’s laws for quantifiers, its negation is “for every integer \(n\), \(n^2 \ne 2\)”. We prove the negation by cases (Definition: Proof by cases, proof by exhaustion). Let \(n\) be an integer.
Exercise 4 (An equation with a solution) Prove or disprove: there are integers \(m\) and \(n\) with \(6m + 4n = 2\).
Solution 4. The proposition is true. Take \(m = 1\) and \(n = -1\). Then \(6m + 4n = 6 - 4 = 2\).
Exercise 5 (An equation without a solution) Prove or disprove: there are integers \(m\) and \(n\) with \(6m + 4n = 3\).
Solution 5. The proposition is false. Applying Theorem: De Morgan’s laws for quantifiers to each of its two quantifiers in turn, its negation is “for all integers \(m\) and \(n\), \(6m + 4n \ne 3\)”, and we prove that. Let \(m\) and \(n\) be integers. Then \(6m + 4n = 2(3m + 2n)\), and \(3m + 2n\) is an integer (Remark: Facts about integers used without proof), so \(6m + 4n\) is even (Definition: Even integer). But \(3 = 2 \cdot 1 + 1\) is odd (Definition: Odd integer), and no integer is both even and odd (Remark: Facts about integers used without proof), so \(6m + 4n \ne 3\).