STEP-BY-STEP LESSON · §3.3

Statements with Multiple Quantifiers

Understand dependent choices with multiple quantifiers.

How to build an argument: methods and reasons

Before writing: assumptions, goals and established facts (§4.2)

Assumption: a stated hypothesis or an explicitly temporary premise. Identify its domain.
Goal: what remains to be shown. It is not available as a reason for a later step.
Established: a statement derived from hypotheses, definitions, earlier steps or an applicable theorem. Name that reason.
Introduce witnesses when their existence is justified; give different arbitrary quantities different variables. Finish by matching the result to the original goal.

Writing a proof · §4.2

Example: constructing the witness for an odd product

Assumption
$m=2a+1,\ n=2b+1,\quad a,b\in\mathbb Z$
Take arbitrary odd integers m and n.
Reason: Their representations follow from the definition of odd.
Goal
$\exists s\in\mathbb Z:\ mn=2s+1$
This is the goal, not something already known.
Reason: An existential conclusion requires constructing a witness.
Established
$mn=(2a+1)(2b+1)=4ab+2a+2b+1$
Expand before introducing s.
Reason: Substitution and the distributive law.
Established
$s=2ab+a+b\in\mathbb Z,\quad mn=2s+1$
The constructed integer s proves the product odd.
Reason: Closure of integers and the definition of odd; the goal was not assumed.

Direct proof

When to choose: Choose it when definitions turn the hypothesis into usable equations or properties.

For every x in D: P(x) implies Q(x). Given: an arbitrary x in D satisfying P. Goal: Q for that same x.

Start: Introduce the objects and their domains; assume only the stated hypotheses. Expand the relevant definition.

Finish: State Q and explain why arbitrariness gives the universal claim. Never use Q as a premise.

Worked example with reasons

Assumption
$a,b\in\mathbb Z,\quad a>0,\ b>0,\ a\mid b$
Take arbitrary positive integers a and b with a dividing b.
Reason: These are the hypotheses, not conclusions.
Goal
$a\le b$
We must establish this inequality.
Reason: Writing a goal does not establish it.
Established
$b=aq,\quad q\in\mathbb Z$
Introduce an integer q witnessing divisibility.
Reason: Definition of a dividing b; a is nonzero.
Established
$q=\frac ba>0$
The quotient is positive.
Reason: Both b and a are positive; division by a is allowed.
Established
$q\ge1$
A positive integer cannot lie strictly between 0 and 1.
Reason: This uses q being an integer, not positivity alone.
Established
$aq\ge a,\quad b\ge a$
Replace aq by b to obtain the goal.
Reason: Multiplication by a positive a preserves the inequality; b=aq was established above.

Source concepts · approved book access required

PDF 198 · p. 174, PDF 215 · p. 191

Counterexample

When to choose: Use it to refute a universal claim. A failed proof attempt alone does not refute anything.

To refute every x in D satisfying P also satisfies Q, find one x in D with P true and Q false.

Start: Write the exact claim and choose a permitted test object. Verify its hypotheses.

Finish: Show explicitly which conclusion fails; one valid counterexample refutes the universal claim.

Worked example with reasons

Goal
$\forall n\in\mathbb Z\ (n>1\Rightarrow \operatorname{Prime}(n))$
Test the claim that every integer greater than 1 is prime.
Reason: A universal statement can be disproved by one permitted instance.
Established
$n=9,\quad9\in\mathbb Z,\quad9>1$
The chosen value satisfies the domain and hypothesis.
Reason: A counterexample must meet every hypothesis.
Established
$9=3\cdot3,\quad1<3<9$
Nine has a positive divisor other than 1 and itself, so it is not prime.
Reason: Definition of prime. Composite means nonprime only within integers greater than 1.

Source concepts · approved book access required

PDF 185 · p. 161, PDF 198 · p. 174

Proof by cases

When to choose: Choose cases when a definition or remainder changes the calculation. First show the cases cover every allowed object.

Given P, cover all possibilities C₁,…,Cₖ and prove Q in each.

Start: Derive the case split from a definition or theorem; do not merely list convenient examples.

Finish: Conclude Q because every allowed object belongs to a handled case.

Worked example with reasons

Assumption
$n\in\mathbb Z,\quad 2\nmid n$
Let n be an arbitrary odd integer.
Reason: The hypothesis fixes the domain but does not yet provide the required m.
Goal
$n^2=8m+1\quad m\in\mathbb Z$
We need to construct an integer m.
Reason: The conclusion is existential: both the equation and integrality must be shown.
Established
$n=4q+r,\quad q\in\mathbb Z,\quad r\in\{0,1,2,3\}$
Only r=1 or r=3 is possible for odd n.
Reason: Quotient–remainder theorem 4.5.1; residues 0 and 2 make n even. This proves completeness.
Established
$(4q+1)^2=16q^2+8q+1=8(2q^2+q)+1$
Case 1: set m=2q²+q.
Reason: Expand the square and factor 8. Sums and products of integers are integers.
Established
$(4q+3)^2=16q^2+24q+9=8(2q^2+3q+1)+1$
Case 2: set m=2q²+3q+1.
Reason: Expansion, 9=8+1, then factor 8; the constructed m is an integer.
Established
$\exists m\in\mathbb Z:\ n^2=8m+1$
Both possible cases give the required integer; it may depend on the case.
Reason: Exhaustive cases establish the original claim for arbitrary odd n.

Source concepts · approved book access required

PDF 230 · p. 206, PDF 231 · p. 207

Contraposition

When to choose: Use it when negating the conclusion gives a more useful starting definition.

To prove P⇒Q, prove ¬Q⇒¬P. Given ¬Q; goal ¬P.

Start: Write the contrapositive and introduce an arbitrary object satisfying ¬Q.

Finish: Establish ¬P, then invoke equivalence with the original implication.

Worked example with reasons

Goal
$2\mid n^2\Rightarrow 2\mid n$
Prove the statement for every integer n.
Reason: This is Proposition 4.7.4.
Assumption
$2\nmid n$
Instead prove: if n is odd, then n² is odd.
Reason: P⇒Q is equivalent to ¬Q⇒¬P. For integers, not even means odd. We do not assume n² even here.
Established
$n=2k+1,\quad k\in\mathbb Z$
Introduce an integer k.
Reason: Definition of odd.
Established
$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$
The square is odd.
Reason: Algebra and closure of integers show 2k²+2k is an integer; then use the definition of odd.
Established
$2\mid n^2\Rightarrow 2\mid n$
The original implication follows from the proved contrapositive.
Reason: Logical equivalence of a conditional and its contrapositive.

Source concepts · approved book access required

PDF 246 · p. 222, PDF 247 · p. 223, PDF 248 · p. 224

Contradiction

When to choose: Use it when the negation creates incompatible established facts.

Assume the hypotheses and the negation of the desired conclusion; derive a contradiction.

Start: State exactly what is temporarily assumed for contradiction.

Finish: Name the conflicting statements and discharge the assumption.

Worked example with reasons

Goal
$2\mid n^2\Rightarrow 2\mid n$
Prove the statement for every integer n.
Reason: This is Proposition 4.7.4.
Assumption
$2\mid n^2,\quad 2\nmid n$
Assume a counterexample: n² is even but n is not even.
Reason: Negating the universal conditional gives one integer satisfying the hypothesis and negating the conclusion. Every integer is either even or odd.
Established
$n=2k+1,\quad k\in\mathbb Z$
Introduce an integer k.
Reason: Definition of odd.
Established
$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$
The square is odd.
Reason: Algebra and closure of integers show 2k²+2k is an integer; then use the definition of odd.
Established
$2\mid n^2\ \land\ 2\nmid n^2$
This is impossible; the assumed counterexample cannot exist.
Reason: No integer is both even and odd (Theorem 4.7.2). Discharging the contradictory assumption proves the original claim.

Source concepts · approved book access required

PDF 246 · p. 222, PDF 247 · p. 223, PDF 248 · p. 224

Mathematical induction

When to choose: Use it for a claim indexed by every integer n from a starting value, when the next case relates to the previous one.

Prove P(n₀). For arbitrary k≥n₀, assume P(k) and derive P(k+1).

Start: State the indexed property and starting value; check the base without using the induction hypothesis.

Finish: Invoke induction only after both the base and the implication are established.

Worked example with reasons

Goal
$1+3+\cdots+(2n-1)=n^2,\quad n\ge1$
Prove the sum formula for every positive integer n.
Reason: The domain and indexed property specify what induction must cover.
Established
$n=1:\quad1=1^2$
The first case holds.
Reason: Direct evaluation establishes the base.
Assumption
$1+3+\cdots+(2k-1)=k^2,\quad k\ge1$
Fix an arbitrary integer k and assume only its case.
Reason: This temporary induction hypothesis is permitted to prove the implication P(k)⇒P(k+1).
Established
$1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1$
Separate the next term and replace the old sum by k².
Reason: This is the exact point where the induction hypothesis is used.
Established
$k^2+2k+1=(k+1)^2$
This is the required case k+1.
Reason: Algebra proves the implication. The base and induction principle now give all integers n≥1.

Source concepts · approved book access required

PDF 304 · p. 280

Negating quantified statements

When to choose: Use it to identify precisely what would make a quantified claim false, especially before a counterexample or contradiction.

Negate one outer quantifier at a time, preserving variable order, domains and the scope of the predicate.

Start: Mark the scope of each quantifier; move the negation inward one rule at a time.

Finish: Read the final statement and check that it describes failure of the original claim. Equivalence does not by itself prove either statement true.

Worked example with reasons

Goal
$\neg\forall x\in D\ \exists y\in E\ P(x,y)$
Rewrite the negation without changing its meaning.
Reason: The domains D and E remain fixed throughout.
Established
$\exists x\in D\ \neg\exists y\in E\ P(x,y)$
There is an x for which the inner existential statement fails.
Reason: Negation of a universal quantifier: ¬∀x R(x) ⇔ ∃x ¬R(x).
Established
$\exists x\in D\ \forall y\in E\ \neg P(x,y)$
For that same x, every y fails P.
Reason: Negation of an existential quantifier: ¬∃y P(x,y) ⇔ ∀y ¬P(x,y). The order ∃x∀y is preserved.

Source concepts · approved book access required

PDF 164 · p. 140

Theorem, proposition, lemma and corollary

Theorem / proposition

Both are statements established by proof. The name often signals how a text organizes or emphasizes a result, not a different degree of truth.

Lemma

A proved auxiliary result used in another argument. For example, −|r|≤r≤|r| for real r supports later bounds. If r≥0, |r|=r and −r≤r; if r<0, |r|=−r and r≤−r. These cases cover every real r.

Lemma 4.5.4, printed p. 207 / PDF 231

Corollary

A result derived from an established theorem. If r is rational, r+r is rational by closure of rational numbers under addition (Theorem 4.3.2); because 2r=r+r, its double is rational.

Example 4.3.4, printed p. 187 / PDF 211; printed box: Corollary 4.2.3

Keep the domain conditions

With Epp’s definition, d divides 0 for every nonzero integer d: 0=d·0. Do not omit d≠0.

Prime and composite classifications here concern integers n>1. “Not prime” alone does not make 0, 1 or a negative integer composite.

Before you begin

Predicates and Quantified Statements II

Negating “all have the property” means “some object lacks it”. It does not mean that all lack it.

¬∀x∈D P(x) ≡ ∃x∈D ¬P(x)

Negating the existence of a suitable object means every object fails the condition.

¬∃x∈D P(x) ≡ ∀x∈D ¬P(x)

To refute “for every x, if P(x) then Q(x)”, find x satisfying P(x) but not Q(x).

¬∀x(P(x)→Q(x)) ≡ ∃x(P(x)∧¬Q(x))

Symbols

∀x∃y: for every x there exists y
∃y∀x: there is one y for every x

Definitions and notation for this topic

Unique existence

∃!x∈D P(x)

Asserts that exactly one object satisfies the condition.

The value is x=2; other possible values must also be ruled out.

Separate glossary example

∃!x∈ℤ: x+1=3

Open glossary card

Free / bound variable

(∀x∈D P(x)) ∧ Q(x)

An occurrence of a variable is bound when it lies in the scope of a quantifier that binds it; otherwise that occurrence is free.

The same printed variable name can have both kinds of occurrence. Parentheses delimit the quantifier’s scope; this formula still depends on the free x.

Separate glossary example

In (∀x∈D P(x)) ∧ Q(x), the x in P(x) is bound; the x in Q(x) is free.

∀x P(x,y)

Open glossary card

Quantifier order

∀x∈ℤ ∃y∈ℤ (y>x); ∃y∈ℤ ∀x∈ℤ (y>x)

In ∀x∃y, the choice of y may depend on the previously chosen x.

In the first statement choose y=x+1 after x is given. The second asks for one integer larger than every integer; choosing x=y disproves that possibility.

Separate glossary example

∀x∈ℤ ∃y∈ℤ (y>x) is true; ∃y∈ℤ ∀x∈ℤ (y>x) is false.

∀x∈ℤ ∃y∈ℤ: y>x

Open glossary card

Negating quantifiers

¬(∀x∈D P(x)) ≡ ∃x∈D ¬P(x); ¬(∃x∈D P(x)) ≡ ∀x∈D ¬P(x)

Negating a quantified statement switches ∀ and ∃ and negates the complete predicate in their scope. Keep the same domain.

With several quantifiers, apply the rule successively without reordering variables. Negate the whole predicate: ¬(P∧Q) becomes ¬P∨¬Q, not ¬P∧¬Q.

Separate glossary example

¬(∀x∈ℤ (x≥0)) ≡ ∃x∈ℤ (x<0). Also ¬(∃x∈ℤ (x²=−1)) ≡ ∀x∈ℤ (x²≠−1).

¬(∀x P(x)) ≡ ∃x ¬P(x)

Open glossary card

Step by step

Step 1 / 6

Read from left to right

In ∀x∃y, x is given first, then a suitable y may be selected. y may change with x.

∀x∈ℤ ∃y∈ℤ: x+y=0

The rule y=−x supplies an answer for each x.

Worked example

On D={0,1}, compare ∀x∈D∃y∈D(y=x) with ∃y∈D∀x∈D(y=x).

For the first statement, x=0 permits y=0 and x=1 permits y=1. Every row has a witness.
For the second statement, candidate y=0 fails at x=1. Candidate y=1 fails at x=0.
These are all candidates in D, so no single y works for every x. The first statement is true and the second false.

Optional self-check

What is equivalent to ¬∃y∀x P(x,y)?

Show answer

∀y∃x ¬P(x,y), preserving the domains.

Source / textbook · approved access required

Open source: printed p. 131 · PDF 155