A proof has to meet the exact claim being made. “Every” asks for an argument that handles an arbitrary input. “There exists” asks us to establish that a suitable object exists. “If” lets us assume a hypothesis, while “if and only if” asks for two directions. Reading that structure first tells us what we may assume, what we can choose, and what we still need to show.

These proof methods build on predicates and quantifiers.

Quantifier order and dependence

Consider these two statements over the real numbers, written $\mathbb R$:

$$\forall x\in\mathbb R\;\exists y\in\mathbb R\;(x+y=0),$$ $$\exists y\in\mathbb R\;\forall x\in\mathbb R\;(x+y=0).$$

The equation is the same, but the order changes what is being claimed.

• The first says that each real number $x$ has some additive inverse $y$: a number that adds to $x$ to give zero. We may choose a different $y$ for each $x$.
• The second says that one fixed real number $y$ adds to zero with every real number $x$.

The first is true. Given any $x\in\mathbb R$, choose $y=-x$. This is a real number, and

$$x+y=x+(-x)=0.$$

The second is false. Whatever real number $y$ is proposed, choose $x=1-y$. Then

$$x+y=(1-y)+y=1\ne0.$$

This defeats every proposed $y$, not just one particular choice. In general, we cannot swap a universal and an existential quantifier and expect the statement to keep its meaning.

Game semantics

Game semantics makes this dependence explicit by imagining two players reading a quantified statement from left to right:

• Adam chooses the value at each universal quantifier, $\forall$.
• Eve chooses the value at each existential quantifier, $\exists$.
• Each value must belong to the quantifier's domain. A choice may depend on earlier moves, but not on moves that have not happened yet.

For the two formulas above, the players evaluate the equation after choosing both values. Eve wins if it is true; Adam wins if it is false.

A winning strategy is a rule that guarantees a win against every legal choice by the other player. Winning one play is not enough. In this quantifier game, a true statement gives Eve a winning strategy, while a false statement gives Adam one.

For $\forall x\,\exists y\,(x+y=0)$, Adam moves first and Eve responds with $y=-x$. For $\exists y\,\forall x\,(x+y=0)$, Eve must commit first, and Adam responds with $x=1-y$. The order determines who can respond to whom.

This viewpoint is useful when writing a proof: describe a choice or argument that still works when the universally quantified inputs are arbitrary. It is not enough to show that a few convenient choices work.

When quantifier order does not matter

Two adjacent universal quantifiers can be swapped, as can two adjacent existential quantifiers. Here the quantifiers must range over fixed domains, each independent of the other variable. Let $A$ and $B$ be sets, and let $P(x,y)$ be a predicate with $x\in A$ and $y\in B$. Then

$$\bigl(\forall x\in A\;\forall y\in B\;P(x,y)\bigr) \equiv \bigl(\forall y\in B\;\forall x\in A\;P(x,y)\bigr),$$ $$\bigl(\exists x\in A\;\exists y\in B\;P(x,y)\bigr) \equiv \bigl(\exists y\in B\;\exists x\in A\;P(x,y)\bigr).$$

The two universal statements both require every pair to satisfy $P$. The two existential statements both require at least one pair to satisfy $P$. Reordering these same-type quantifiers does not change either requirement. In the game, the same player makes both choices: Adam for two universal quantifiers, Eve for two existential quantifiers.

For example, $\mathbb R^2$ is the set of ordered pairs of real numbers. These three statements all say that every real pair satisfies the given equation:

$$\begin{aligned} &\forall x\in\mathbb R\;\forall y\in\mathbb R\;(x^2+y^2=1),\\ &\forall y\in\mathbb R\;\forall x\in\mathbb R\;(x^2+y^2=1),\\ &\forall(x,y)\in\mathbb R^2\;(x^2+y^2=1). \end{aligned}$$

They are equivalent, and all three are false. Adam can choose $x=10$ and $y=4$, since

$$10^2+4^2=116\ne1.$$

One counterexample defeats a universal claim. This is different from exchanging $\forall$ with $\exists$, where the players' dependence on each other's choices can change the truth of the statement.

Let the statement guide the proof

A direct proof starts from the given assumptions and establishes the conclusion. Its steps follow the logical structure of the statement.

Let $U$ be the universe of objects under discussion, let $P(x)$ be a predicate on $U$, and let $p$ and $q$ be propositions. An object that makes an existential claim true is called a witness. The following are useful ways to approach different goals:

For a conjunction, both claims must stand up to a challenge: Adam could ask for either one. For a disjunction, Eve can choose which claim to establish; each of the two claims is called a disjunct. The connective $\lor$ is inclusive OR, so proving both is allowed, but not required.

These are proof strategies, not claims that there is only one possible method. For example, an existence claim can also be proved indirectly rather than by explicitly constructing a witness.

A conjecture is a claim whose truth we have not yet established. Once it is proved, it becomes a theorem. To investigate a conjecture, first make its assumptions and conclusion precise. Definitions often show what the proof needs to produce.

Example: the square of an odd integer

Write $\mathbb Z$ for the set of integers. For an integer $n$, the definitions of even and odd are

$$\begin{aligned} n\text{ is even} &\quad\Longleftrightarrow\quad \exists k\in\mathbb Z\;(n=2k),\\ n\text{ is odd} &\quad\Longleftrightarrow\quad \exists k\in\mathbb Z\;(n=2k+1). \end{aligned}$$

Every integer is exactly one of even or odd. Whether an integer is even or odd is its parity. This matters later: for integers, “not odd” means “even,” and “not even” means “odd.”

We want to prove:

If $n$ is an odd integer, then $n^2$ is odd.

Expanding the definition of odd makes the required witnesses visible:

$$\forall n\in\mathbb Z\; \left[ \left(\exists k\in\mathbb Z\;(n=2k+1)\right) \Rightarrow \left(\exists\ell\in\mathbb Z\;(n^2=2\ell+1)\right) \right].$$

The two witnesses have different roles. The assumption supplies an integer $k$ representing $n$. The conclusion asks us to produce an integer $\ell$ representing $n^2$.

Direct proof

Let $n\in\mathbb Z$ be arbitrary and assume $n$ is odd. Then $n=2k+1$ for some integer $k$. Our goal is to write $n^2=2\ell+1$ with $\ell\in\mathbb Z$.

Square the expression for $n$, then separate one from an even term:

$$\begin{aligned} n^2 &=(2k+1)^2\\ &=4k^2+4k+1\\ &=2(2k^2+2k)+1. \end{aligned}$$

Choose $\ell=2k^2+2k$. Because $k$ is an integer, its products and sums are integers too, so $\ell$ is an integer. We now have $n^2=2\ell+1$, which is exactly the definition of odd. This proves the claim for every odd integer $n$.

Notice which choices were available. We could not set $k$ to a convenient value: once $n$ was given, $k$ had to satisfy $n=2k+1$. We were free to construct $\ell$ using that $k$. Choosing a witness means meeting the required equation and domain, not choosing an arbitrary number.

Proving a disjunction

To prove $p\lor q$, it is enough to establish either disjunct. Sometimes neither one is guaranteed by itself, so we split according to whether $p$ is true:

• If $p$ is true, the disjunction is already true.
• If $p$ is false, prove $q$.

This is captured by the logical equivalence

$$p\lor q\equiv(\neg p\Rightarrow q).$$

So we may prove $p\lor q$ by assuming $\neg p$ and deriving $q$. This does not mean that we are allowed to prove $q$ only when $p$ is false. Either disjunct always suffices; the equivalence just gives a useful conditional strategy.

Example with a product bound

Let $a$, $b$, and $c$ be positive real numbers. We want to prove that if $ab\le c$, then

$$a\le\sqrt c\quad\text{or}\quad b\le\sqrt c.$$

The conclusion bounds at least one factor, not necessarily both. If the first factor is larger than $\sqrt c$, the product bound will force the second factor to be smaller than $\sqrt c$.

Let $a$, $b$, and $c$ be arbitrary positive real numbers, and assume $ab\le c$. If $a\le\sqrt c$, there is nothing more to prove. Otherwise,

$$\neg(a\le\sqrt c)\quad\Longleftrightarrow\quad a>\sqrt c.$$

Because $b>0$, multiplying this strict inequality by $b$ preserves its direction:

$$\sqrt c\,b<ab\le c.$$

Since $c>0$, we also have $\sqrt c>0$. We may therefore divide by $\sqrt c$ without reversing the inequality:

$$b<\frac{c}{\sqrt c}=\sqrt c.$$

In particular, $b\le\sqrt c$, which proves the other disjunct. The desired OR statement holds in either case.

There is also a shorter route through fractions. With a fixed positive numerator, increasing a positive denominator makes the fraction smaller. Since $ab\le c$ and $a>\sqrt c>0$, we can write

$$b\le\frac ca<\frac c{\sqrt c}=\sqrt c.$$

The first inequality comes from dividing the product bound by $a>0$; the second uses the larger denominator $a$.

Proof by contrapositive

For an implication $p\Rightarrow q$, distinguish two statements:

The contrapositive reverses the direction and negates both propositions. It is logically equivalent to the original implication:

$$(p\Rightarrow q)\equiv(\neg q\Rightarrow\neg p).$$

Both are false in exactly the same situation: $p$ is true and $q$ is false. A proof by contrapositive therefore proves the original implication by assuming $\neg q$ and deriving $\neg p$.

The converse merely reverses the direction. It is not generally equivalent to the original implication and needs its own proof. For example, when $p$ is false and $q$ is true, $p\Rightarrow q$ is true but $q\Rightarrow p$ is false.

Example: if the square is odd, the integer is odd

For an integer $n$, we now want to prove

$$n^2\text{ is odd}\quad\Longrightarrow\quad n\text{ is odd}.$$

This is the converse of the odd-square result proved above, so the earlier proof alone does not establish it.

A direct attempt begins with $n^2=2k+1$ for some integer $k$. Taking square roots gives

$$n=\pm\sqrt{2k+1}.$$

But this expression does not immediately exhibit an integer $\ell$ with $n=2\ell+1$. The contrapositive avoids square roots and gives an easier starting point:

$$n\text{ is not odd}\quad\Longrightarrow\quad n^2\text{ is not odd}.$$

Because both $n$ and $n^2$ are integers, this is the same as

$$n\text{ is even}\quad\Longrightarrow\quad n^2\text{ is even}.$$

Let $n\in\mathbb Z$ be arbitrary and assume it is even. Then $n=2k$ for some integer $k$, so

$$n^2=(2k)^2=4k^2=2(2k^2).$$

Choose $\ell=2k^2$. This is an integer, and $n^2=2\ell$, so $n^2$ is even. We have proved the contrapositive, and therefore the original claim: if an integer's square is odd, that integer is odd.

The integer assumption is essential. It is what allows us to replace “not odd” with “even.”

Combining both directions

We have now proved both implications needed for

$$n\text{ is odd}\quad\Longleftrightarrow\quad n^2\text{ is odd} \qquad(n\in\mathbb Z).$$

The forward direction came from expanding the square of an odd integer. The reverse direction came from proving that an even integer has an even square.

Negating both sides preserves a biconditional:

$$(p\Leftrightarrow q)\equiv(\neg p\Leftrightarrow\neg q).$$

Using the integer parity distinction gives the corollary, a consequence of the result we just proved:

$$n\text{ is even}\quad\Longleftrightarrow\quad n^2\text{ is even} \qquad(n\in\mathbb Z).$$

In short, an integer and its square have the same parity. The two directions are justified by the proofs, not just by checking examples.