Declare the domains before judging the sentence
An expression with unspecified inputs is a predicate. It becomes a statement when its variables are assigned values or quantified over declared sets. For example, the equation has a real solution for each nonnegative real , but not for every real . Changing the domain changes the statement without changing the displayed equation.
For , the assertion that is onto is . The input witness may depend on the output already selected. Injectivity is . An input pair with different outputs does not disprove injectivity; a counterexample must make the premise true and the conclusion false.
An implication fails exactly when is true and false. Therefore its negation is . Its contrapositive has the same truth value as the original. Its converse is a separate claim. This truth-value rule does not allow us to infer merely because is false.
Witnesses may use earlier inputs, not later ones
The statement permits a new after each is specified. The statement requires one common before an arbitrary is considered. The second implies the first, but the first need not imply the second. Over the reals, for example, a tolerance can depend on the point under consideration without being a single tolerance valid at every point.
Theorem 1.3.1
(A common witness gives pointwise witnesses)
For every predicate on , if then .
Proof
(Reuse the common witness for every input)
Let be a common witness, so that holds for every . Given an arbitrary , the element is an output satisfying . Hence for every . If is empty, the conclusion is true without any argument.
The converse implication is the one that fails, and one concrete instance shows why.
Counterexample mode
Pointwise witnesses need not be one common witness
Claim: if then . Take and let mean . The first statement is true: for each the output works. The second is false: for any proposed common , for example , the input gives , which is false. In general defeats . The repair is to keep the one-way implication of the previous theorem, or to add a hypothesis that actually supplies a uniform witness.
A proof of a universal claim takes an arbitrary input, records its assumptions and proves the conclusion without giving it any extra favorable property. A proof of an existential claim supplies an object in the required domain and verifies the defining condition. Writing down a candidate is not the verification. If division or a square root occurs in that candidate, its existence must be checked too.
Concept lensAlgorithmic
Quantifiers as a game between a prover and a refuter
Read a quantified sentence as moves in a game. In the Refuter names and the Prover then answers with ; the sentence is true when the Prover can always answer so that holds. In the Prover must commit to first, and the Refuter then tries every . Quantifier order is the order of moves. Negation swaps the roles, which is why the quantifiers keep their order while their kinds change.
For arbitrary infinite sets, the assertion that each input has at least one admissible output should not silently be replaced by the existence of a simultaneously selected witness function. An explicit formula supplies such a selection when it works; a general selection principle is a separate topic. For finite sets the choices can be made one at a time.
Negate the scopes in their original order
Negating a universal statement produces an existential counterexample; negating existence requires every candidate to fail. For a binary predicate,
The counterexample input defeats every output offered for it. Negating instead gives . Here a counter-input may depend on the proposed common output. The variable order is retained, not reversed.
Theorem 1.3.2
(Negation of nested quantifiers)
For every predicate on ,
Proof
(Negate one quantifier at a time, from the outside in)
Write for the statement . Then is equivalent to , and , that is , is equivalent to . This gives the first equivalence. For the second, write for : then is , and is . At each step the quantifiers keep their order and only their kinds change.
Common mistake
(Negating only the last quantifier)
It is tempting to negate as . For meaning over , the original is false (take ), but the proposed negation is also false (take , , since ). A statement and its negation cannot both be false, so this negation is wrong. The correct negation is , witnessed by .
The same method handles eventual assertions. If means that for every some controls every , its negation is
One fixed tolerance fails arbitrarily late. A bad early term is insufficient, and a sequence of increasingly tiny errors need not defeat convergence. At a fixed tolerance, the weak inequality is the exact negation of the strict one. A strict inequality can express the same full nonconvergence property after a separate tolerance argument: an error at least is greater than , while an error greater than is also at least . This is an equivalence using the existential tolerance, not pointwise negation.
Empty domains keep these equivalences consistent. A universal claim over an empty set has no counterexample and is true; an existential claim over it has no witness and is false. In particular, when is empty, is true even if is empty, whereas is false when is empty. Nonemptiness must not be smuggled into an implication between the two forms.
Existence and uniqueness are two obligations
Definition 1.3.3
(Exactly one solution)
For a predicate on a set , the statement means that both of the following hold: (existence) , and (uniqueness) for all , if and then .
For a fixed input, exactly one solution means that a solution exists and any two solutions are equal. A valid existence proof does not establish uniqueness, and a proof that any two solutions coincide may still leave the possibility of no solution.
Theorem 1.3.4
(How exactly-one existence can fail)
The statement is false if and only if either no satisfies , or there are two distinct that both satisfy .
Proof
(Negate the conjunction)
The negation of a conjunction is a disjunction: either existence fails or uniqueness fails. Failure of existence says no satisfies . Failure of uniqueness says that it is not true that all pairs of solutions are equal, so some pair of solutions has . Thus a claim can fail at an input with no output or at one with several outputs, and checking only one kind of failure is incomplete.
Worked example 1.3.5
(Solving the equation ay=b)
For example, solving by writing assumes . With that assumption, substitution proves existence and nonzero cancellation proves uniqueness. If , there is no solution when and every real is a solution when . The formula alone omits both cases. Proof auditing identifies the first unjustified step; it is more informative than merely observing that the final answer looks wrong.
Common mistake
(Treating existence as uniqueness, or the reverse)
The equation has the real solution , but not only that one: also works, so existence holds and uniqueness fails. Conversely, any two real solutions of coincide, because there are none, so uniqueness holds vacuously while existence fails. Each obligation must be proved on its own.
Worked examples
Worked example 1.3.6
(The same quadratic under three quantifier patterns)
Fix and let mean , with . Classify the parameter values for , for , and for .
Solution. Completing the square gives . If , the right side is nonnegative for every real , and the real-root existence theorem supplies . These are verified candidates. If , gives a negative square requirement. The first assertion therefore holds exactly when .
For a common , the equation at gives , and the equation at gives . Subtraction forces , and then . Conversely, satisfies the equation for every . The second assertion holds exactly at . When , the first statement is true and the second false, so the distinction is substantive.
The third assertion never holds. If , there is no solution at zero. If , zero has the two distinct roots . The only remaining parameter is , but at the equation has the distinct roots zero and two. At this parameter a uniform witness exists, yet uniqueness for every input fails. A common witness and a unique witness are different requirements.
Worked example 1.3.7
(How many finite relations separate the quantifiers?)
Let and represent by a three-by-three grid of zeroes and ones. Find the smallest number of ones for which is true but is false, and count all grids achieving that minimum.
Solution. Each row needs a one, so at least three ones are necessary. Three suffice: place them on the diagonal. Every row then has a witness, but no column works for all rows. With exactly three ones, there is exactly one per row. Such a grid specifies a function from three rows to three columns, so there are possibilities. A universal column occurs exactly when all three selected columns are the same. There are three such constant functions. Thus precisely minimal grids have the requested properties.
The negation of the first assertion would be an entirely empty row. The negation of the second requires every column to have at least one zero, with the defeating row allowed to differ by column. The latter does not require one row containing only zeroes. In the diagonal example every column has a counterexample, but every row still contains a one. This is why exchanging quantifiers changes what a counterexample must do.
Finite witness grids
In the table below a relation on fixed nonempty three-element sets is recorded as a grid of zeroes and ones, a one marking a related pair. An all-zero relation is not an empty domain. Such finite checks illustrate the statements and do not verify a theorem over all real numbers.
Here are four main assertions in five completely specified states. “One column” means all three ones are in the first column; “one row” means all three are in the first row.
| Relation | ||||
|---|---|---|---|---|
| Diagonal ones only | True | False | True | False |
| First column only | True | True | False | False |
| First row only | False | False | True | True |
| All zeroes | False | False | False | False |
| All ones | True | True | True | True |
Audit an argument before accepting its conclusion
A useful proof audit checks the domain, permitted witness dependence, existence of constructed expressions and the direction of each implication. It also separates a necessary condition from a sufficient one: finding a condition all solutions satisfy does not prove every object satisfying that condition is a solution. Substitute the candidate back, and prove the converse when a full classification is claimed. The preceding chapters' locus and quotient examples give concrete applications of this habit.
Exercises
Quick check
(Write the negation of and decide which of the statement and its negation is true.)
Negate the quantifiers from the outside in, then look for a real with no square root.
Solution · Answer
The negation is . It is true: take , since no real has . So the original statement is false.
Quick check
(Over , decide the truth of and of .)
Compare a witness that may depend on with one that may not.
Solution · Answer
The first is true: given , take . The second is false: for any proposed , the input gives .
Quick check
(Is true? Compare with .)
Prove existence and uniqueness separately.
Solution · Answer
It is true. Existence: works. Uniqueness: if then , because cubing is strictly increasing on . For the statement fails, since has no solution and has the two solutions .