Proving Non-Conditional Statements

If and only if, existence, and disproof

Published

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 outline of an “if and only if” proof;
the outline of an existence proof that names an element;
proving that several propositions are equivalent with a cycle of conditionals;
the constructive example of half of a positive number;
the non-constructive example of an irrational power of an irrational number;
disproving a proposition by proving its negation.

The exercises are new.

1 Proving if and only if

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

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{}. \]

Proof

Proof. By the definitions of if and only if, implies and and, the truth table is:

\(P\)	\(Q\)	\(P \Rightarrow Q\)	\(Q \Rightarrow P\)	\((P \Rightarrow Q) \land (Q \Rightarrow P)\)	\(P \Leftrightarrow Q\)
T	T	T	T	T	T
T	F	F	T	F	F
F	T	T	F	F	F
F	F	T	T	T	T

The last two columns match in every row, so the two propositions are logically equivalent.

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.

If \(n\) is even, then \(n = 2k\) for some integer \(k\) (Definition: Even integer), so \(n + 2 = 2k + 2 = 2(k + 1)\), and \(k + 1\) is an integer (Remark: Facts about integers used without proof). So \(n + 2\) is even.
If \(n + 2\) is even, then \(n + 2 = 2m\) for some integer \(m\), so \(n = 2m - 2 = 2(m - 1)\), and \(m - 1\) is an integer. So \(n\) is even.

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.

Proof

Proof. There are two cases.

None of \(P_1, \ldots, P_k\) is true. Then all of them are false, so they all have the same truth value.
Some \(P_i\) is true. By the definition of implies, for any \(P\) and \(Q\), if \(P \Rightarrow Q\) and \(P\) are both true, then \(Q\) is true. So \(P_i \Rightarrow P_{i+1}\) makes \(P_{i+1}\) true, then \(P_{i+1} \Rightarrow P_{i+2}\) makes \(P_{i+2}\) true, and so on around the cycle, with \(P_k \Rightarrow P_1\) carrying the truth of \(P_k\) back to \(P_1\). After at most \(k - 1\) steps, every proposition in the list is true.

Example 2 (Three ways to say “odd”) Let \(n\) be an integer, and consider

\(P_1\): \(n\) is odd;
\(P_2\): \(n + 1\) is even;
\(P_3\): \(n - 1\) is even.

By Theorem 2, three conditionals show that all three have the same truth value.

\(P_1 \Rightarrow P_2\): if \(n = 2k + 1\) (Definition: Odd integer), then \(n + 1 = 2k + 2 = 2(k + 1)\).
\(P_2 \Rightarrow P_3\): if \(n + 1 = 2m\), then \(n - 1 = 2m - 2 = 2(m - 1)\).
\(P_3 \Rightarrow P_1\): if \(n - 1 = 2j\), then \(n = 2j + 1\).

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.

2 Proving existence

Exercise 2 (A solution in integers) Show that there are integers \(x\) and \(y\) with \(5x + 3y = 1\).

Solution 2

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.

3 Disproof

Exercise 3 (Prove or disprove) Prove or disprove: for every real number \(x\), if \(x^2 > 1\), then \(x > 1\).

Solution 3

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.

If \(n\) is \(-1\), \(0\) or \(1\), then \(n^2\) is \(1\), \(0\) or \(1\), which is not \(2\).
Otherwise \(n \le -2\) or \(n \ge 2\), so \(\mathopen{}\left|n\right|\mathclose{} \ge 2\), and \(n^2 = \mathopen{}\left|n\right|\mathclose{}^2 \ge 2^2 = 4\), so \(n^2 \ne 2\).

Exercise 4 (An equation with a solution) Prove or disprove: there are integers \(m\) and \(n\) with \(6m + 4n = 2\).

Solution 4

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

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\).

Definitions on this page

Definition 1 (Constructive proof)
Definition 2 (Non-constructive proof)
Definition 3 (Disproof)

References

Wikipedia contributors. 2026. Constructive Proof — Wikipedia, the Free Encyclopedia. https://en.wikipedia.org/wiki/Constructive_proof.