There exists, and there is exactly one
You want to say that at least one number works, without saying which, or that exactly one does. How do you say each exactly, and what does it take to prove it?
Where you are 4 in Quantifiers
Why this exists
Pierre de Fermat believed that every number of the form 2^{2^n} + 1 is prime. The first five, 3, 5, 17, 257 and 65537, are. The sixth is 2^{32} + 1 = 4294967297, and for almost a century nobody knew whether it was prime. In 1732 Leonhard Euler settled the question by showing a single number:
He did not need to list every divisor, or say anything about the other numbers of that form. One divisor was enough to prove that a divisor exists, and so that the number is not prime.
Many questions in mathematics have this shape: is there a solution, is there a case where the rule breaks? English asks them with loose words like “some”, which carry hints (“some students passed” suggests that not all did). A proof needs one exact meaning for “at least one”, and a symbol.
There is a second problem. A sentence such as x^2 = 2 is not true and not false: it depends on what x is. It is not yet a statement. Saying “there is an x for which this holds” turns it into one.
And there is a stronger claim hiding in a very small word. “The solution of 3x - 6 = 0 is x = 2.” The word “the” is a promise: it says a solution exists, and it says there is only one, so that naming it with a single number is not misleading. “There exists” makes only the first half of that promise. {\exists x \in \mathbb{R},\ x^2 = 4} is true, but nobody should write “the solution of x^2 = 4”, because there are two of them, 2 and -2, and neither is entitled to the definite article. Mathematics is full of objects introduced with “the”: the midpoint of a segment, the additive inverse of a number, the remainder when you divide by 7. Each of those phrases carries a claim that could be false, and before “the” is allowed someone has to check that exactly one object earns it, neither zero nor two. That claim gets its own symbol too.
Definition
Start with a collection of objects D, called the domain, and a sentence P(x) about x that becomes true or false as soon as x is replaced by a member of D. A sentence like that is called a predicate.
The statement “there exists an x in D such that P(x)” is true when at least one member of D makes P(x) true. It is false when no member of D does. In symbols:
The symbol \exists is a backwards E, for “exists”, and it is called the existential quantifier. A member a of D for which P(a) is true is called a witness to the statement.
“At least one” is meant exactly. One witness is enough, several are fine, and every member of D being a witness is fine too. “There is”, “for some”, “at least one”, “some” and “we can find” all become \exists.
The letter x is only a placeholder. {\exists n \in \mathbb{Z},\ n^2 = 49} and {\exists k \in \mathbb{Z},\ k^2 = 49} are the same statement, and once the quantifier is in front it makes no sense to ask “what is n?” The statement does not name a number; it claims that a suitable number is out there. Here \mathbb{Z} is the set of integers, and later \mathbb{Q}, \mathbb{R} and \mathbb{C} are the rational, real and complex numbers, and \mathbb{Z}^+ is the positive integers.
Its partner is the universal quantifier \forall, which claims that every member of D makes P(x) true. The two together are the quantifiers.
There is exactly one
The statement “there exists exactly one x in D such that P(x)” is true when two separate things both hold:
- Existence. At least one member of D makes P(x) true.
- Uniqueness. Any two members of D that both make P(x) true are in fact the same member.
In symbols, the backwards E with an exclamation mark:
read “there exists exactly one x in D such that P(x)”, or “there is a unique such x in D”. This is called unique existence. Spelled out using only \exists and \forall, the same statement is
which reads: there is some x that works, and every y that works is that very same x. A member of D that makes P true is still called a witness; unique existence says there is one witness and no others. “One and only one”, “there is a unique” and “there is exactly one” all become \exists!.
Intuition
Think of the domain as a room full of objects and the predicate as a test each object passes or fails. The statement {\exists x \in D,\ P(x)} is a bet that the search of the room succeeds at least once.
To win that bet you hold up one object that passes; nobody needs to see the rest of the room. To lose it, somebody has to show that every object fails. That lopsidedness is the character of “there exists”: it is proved by one example and refuted only by an argument that covers everything.
It also means the hard part of a proof is often finding the witness, not checking it. Checking that 641 \times 6700417 = 4294967297 takes a few minutes by hand. Finding 641 took Euler.
When the room is small you can list it. If D = \{1, 2, 3\}, then “some member of D passes” means “1 passes, or 2 passes, or 3 passes”, which is one long or statement.
Exactly one: two jobs
{\exists! x \in D,\ P(x)} is a stronger bet: the test succeeds exactly once in the room, no more and no fewer. That is really two separate jobs, and they usually take different tools. Finding one object that passes is a search or a construction, the same work as before. Ruling out a second winner is a different kind of argument: instead of testing more objects, you argue in general that whichever two objects pass, they have to be the same one.
For an equation f(x) = c the picture is a graph. Every point where the horizontal line y = c meets the curve y = f(x) is a witness, so unique existence says the line meets the curve exactly once.
When the room has only finitely many objects, both jobs collapse into one count: check every object, tally how many pass, and \exists! is true exactly when that tally is 1.
Results
Proof by witness. If a is a member of D and P(a) is true, then the existential statement is true.
On a finite domain it is an “or”. If D = \{a_1, a_2, \ldots, a_n\}, then {\exists x \in D,\ P(x)} says the same as
Over an empty domain it is false. {\exists x \in \varnothing,\ P(x)} is false, whatever P is.
A larger domain can only help. If every member of D is also a member of E, and {\exists x \in D,\ P(x)} is true, then {\exists x \in E,\ P(x)} is true. The reverse can fail.
It passes through “or” but not through “and”.
{\exists x,\ \big(P(x) \lor Q(x)\big)} says the same as
{\exists x,\ \big(P(x) \land Q(x)\big)} guarantees
but the second does not guarantee the first.
Results for exactly one
Exactly one implies at least one, not the other way round. If {\exists! x \in D,\ P(x)} is true, then {\exists x \in D,\ P(x)} is true. The reverse fails whenever there is more than one witness: {\exists x \in \mathbb{R},\ x^2 = 4} is true with two witnesses, but {\exists! x \in \mathbb{R},\ x^2 = 4} is false.
Two different witnesses refute it. If {a \ne b} are both members of D with P(a) and P(b) true, then {\exists! x \in D,\ P(x)} is false, whatever else is true about D or P. One pair beats any amount of searching.
On a finite domain it is a count. If D = \{a_1, a_2, \ldots, a_n\}, then {\exists! x \in D,\ P(x)} is true exactly when exactly one of P(a_1), P(a_2), \ldots, P(a_n) is true, where plain existence asks only that at least one is. For two members this is the exclusive or of P(a_1) and P(a_2). For three or more it is not a chain of exclusive ors: P(a_1) \oplus P(a_2) \oplus P(a_3) is true when all three statements are true, because a chain of exclusive ors only tracks whether the number of true statements is odd.
Its negation has two branches. Unique existence fails when existence fails or when uniqueness fails: {\lnot\, \exists! x \in D,\ P(x)} is equivalent to
(no witness at all) or
(two different witnesses).
Why it is true
Every one of the results for “there exists” comes straight from “at least one member makes P true”.
Proof by witness. a is a member of D that makes P true, so at least one member does.
Finite domain. “At least one of a_1, \ldots, a_n makes P true” and “P(a_1) or P(a_2) or ... or P(a_n)” are the same sentence, because an “or” of several statements is true exactly when at least one of them is.
Empty domain. The empty set has no members at all, so it has no member that makes P true.
Larger domain. A witness in D is also in E, so it is a witness there too. The reverse fails because the witness may live only in the larger set: {\exists x \in \mathbb{R},\ x^2 = 2} is true with \displaystyle x = \sqrt{2}, but {\exists x \in \mathbb{Z},\ x^2 = 2} is false.
“Or”. If a is a witness for the left side, then P(a) or Q(a) holds, so a is a witness for {\exists x,\ P(x)} or for {\exists x,\ Q(x)}. Going back, a witness b for either claim on the right makes P(b) \lor Q(b) true, so b is a witness for the left side.
“And”. A witness a with P(a) \land Q(a) is a witness for P and for Q at once. The reverse fails because the two separate claims may use different witnesses: on the integers, “there is an even number” (take 2) and “there is an odd number” (take 3) are both true, but no integer is both.
Why the results for exactly one are true
Exactly one implies at least one. Dropping the second half of a claim that both halves hold still leaves the first half true.
Two witnesses refute it. This is the uniqueness clause read backwards: uniqueness says any two witnesses coincide, so two that do not coincide are exactly a failure of that clause, and a failure of either clause makes the whole statement false.
The finite-domain count. If none of P(a_1), \ldots, P(a_n) is true, existence already fails. If exactly one, say P(a_k), is true, then a_k is a witness (existence holds), and it is the only member of D making P true, so any two witnesses are both a_k and agree (uniqueness holds). If two or more are true, say P(a_i) and P(a_j) with a_i \ne a_j, those two witnesses refute uniqueness. So the count decides the matter, and \exists! holds exactly when it is 1.
The negation. \exists! is “existence and uniqueness”, and “not (A and B)” is “(not A) or (not B)”. Not existence is {\forall x \in D,\ \lnot P(x)}. Uniqueness is {\forall x, y \in D,\ \big((P(x) \land P(y)) \to x = y\big)}, and a “for all” with an “if ... then” inside is denied by one case where the “if” holds and the “then” fails: some x, y with P(x) and P(y) true but x \ne y. These are the rules of negating a quantified statement, applied to each half of the definition.
Worked examples
Reading and deciding
Write each statement in words and decide whether it is true.
(a) {\exists n \in \mathbb{Z},\ n^2 = 49}
(b) {\exists n \in \mathbb{Z},\ n^2 = 50}
(c) {\exists x \in \mathbb{R},\ x^2 + 1 = 0}
Solution(a) “There is an integer whose square is 49.” True: n = 7 is a witness, since 7^2 = 49. So is n = -7, but one witness is all the statement asks for.
(b) “There is an integer whose square is 50.” A negative integer has the same square as its positive partner, so it is enough to think about n \ge 0. If n \le 7 then n^2 \le 49, and if n \ge 8 then n^2 \ge 64. Every integer falls in one of those two cases, and 50 is in neither range, so no integer works. The statement is false.
Notice what that took. To show (a) true, one number was enough. To show (b) false, trying a few numbers would prove nothing; the argument had to cover every integer at once.
(c) “There is a real number x with x^2 + 1 = 0.” For every real x, x^2 \ge 0, so x^2 + 1 \ge 1, which is never 0. The statement is false.
The same sentence over different domains
Decide whether {\exists x \in D,\ x^2 = 2} is true when D is \mathbb{Z}, when it is \mathbb{Q}, and when it is \mathbb{R}.
SolutionOver \mathbb{R} it is true: \displaystyle x = \sqrt{2} is a witness, because \displaystyle \left(\sqrt{2}\right)^2 = 2 by the meaning of a square root.
Over \mathbb{Z} it is false. The squares of integers go 0, 1, 4, 9, \ldots, and they jump from 1 straight to 4: if |x| \le 1 then x^2 \le 1, and if |x| \ge 2 then x^2 \ge 4.
Over \mathbb{Q} it is also false. The only real numbers whose square is 2 are \displaystyle \sqrt{2} and \displaystyle -\sqrt{2}, and neither is a fraction, which is exactly the irrationality of \displaystyle \sqrt{2}.
The predicate never changed. Only the domain did, and it changed the answer.
Checking every member of a finite domain
Let D = \{1, 2, 3, 4, 5, 6\}. Decide whether each statement is true.
(a) {\exists x \in D,\ x^2 - 7x + 10 = 0}
(b) {\exists x \in D,\ x^2 - 7x + 12 < 0}
Solution(a) Try x = 2, which gives 4 - 14 + 10 = 0. So 2 is a witness and the statement is true. There is no need to look further, although x = 5 also works.
(b) The domain has only six members, so the statement says “P(1) or P(2) or ... or P(6)”, and it is false only if all six fail. Check every one:
No value is below 0, so the statement is false. Over \mathbb{R} it would be true: x^2 - 7x + 12 = (x - 3)(x - 4), and x = 3.5 gives (0.5)(-0.5) = -0.25. D just has no member strictly between 3 and 4.
A witness found by search
Show that there is a whole number n \ge 0 for which n^2 + n + 41 is not prime.
SolutionTrying small values is discouraging: n = 0, 1, 2 and 3 give 41, 43, 47 and 53, all prime, and in fact every value from n = 0 to n = 39 gives a prime. Forty successes in a row still settle nothing (a pattern is not a proof).
Instead of trying values, look for an n that makes the expression factor. If n = 40, then n^2 + n = n(n + 1) = 40 \times 41, and both pieces of the sum carry a factor of 41:
1681 = 41^2 is not prime, so n = 40 is a witness and the statement is true. (So is n = 41, which gives 41 \times 43.)
Check. 41 \times 41 = 1681, and 1600 + 40 + 41 = 1681.
One object doing two jobs
Decide whether each statement about real numbers is true.
(a) {\exists x \in \mathbb{R},\ \big(x^2 = 9 \land x < 0\big)}
(b) {\exists x \in \mathbb{R},\ \big(x^2 = 9 \land x > 5\big)}
(c) {\big(\exists x \in \mathbb{R},\ x^2 = 9\big)} \land {\big(\exists x \in \mathbb{R},\ x > 5\big)}
SolutionThe only real numbers with x^2 = 9 are x = 3 and x = -3.
(a) x = -3 has square 9 and is negative, so it does both jobs. True.
(b) A witness would have to be 3 or -3 to satisfy the first part, and neither is greater than 5. False.
(c) This is two separate claims joined by “and”. The first is true with witness 3, the second is true with witness 6. Both hold, so (c) is true.
Statements (b) and (c) are built from the same two pieces and get opposite answers. In (b) one number must do both jobs; in (c) each claim brings its own witness.
At least one, and exactly one, as conditions on a number
For which real numbers b is {\exists x \in \mathbb{R},\ x^2 + bx + 9 = 0} true? For which is {\exists! x \in \mathbb{R},\ x^2 + bx + 9 = 0} true?
SolutionFor each fixed b these are statements, true or false. The questions ask for every b that makes them true, which means asking when the quadratic x^2 + bx + 9 has a real root, and when it has exactly one.
A quadratic ax^2 + bx + c has a real root exactly when its discriminant b^2 - 4ac is at least 0 (the discriminant and the number of roots). Here a = 1 and c = 9:
So the first statement is true exactly when {b \le -6} or {b \ge 6}.
Check. For b = 6 the equation is x^2 + 6x + 9 = (x + 3)^2 = 0, with witness x = -3. For b = 10, x = -1 is a witness: 1 - 10 + 9 = 0. For b = 0 the equation is x^2 + 9 = 0, and {x^2 + 9 \ge 9} for every real x, so there is no witness, as the answer predicts.
For exactly one root, both halves must hold at once. By the quadratic formula the real roots are
When the discriminant is positive, the \pm gives two different real roots, so uniqueness fails. When it is negative there is no real root, so existence fails. Only when it is 0 do the two coincide, so b^2 = 36, which means b = 6 or b = -6.
Take b = 6, where the equation is (x + 3)^2 = 0. A real number squares to 0 only when the number itself is 0, so any solution has x + 3 = 0, which forces x = -3: that is uniqueness. And x = -3 does work, since (-3 + 3)^2 = 0: that is existence. Every step runs both ways, so one chain of reasoning delivers both halves. For b = -6 the same argument applies to x^2 - 6x + 9 = (x - 3)^2 = 0, with the single witness x = 3.
So the second statement is true exactly when b = 6 or b = -6: a discriminant of zero, one repeated root, never two different ones.
Proving exactly one, and refuting it
Decide whether each statement is true.
(a) {\exists! x \in \mathbb{R},\ 2x - 7 = 3}
(b) {\exists! x \in \mathbb{Z},\ x^2 = 9}
Solution(a) Existence. Solving the equation suggests a candidate:
and it passes the test, since 2(5) - 7 = 3. So x = 5 is a witness.
Uniqueness. Read the same chain again. It starts from “x is a solution” and ends at the line x = 5, and each arrow is allowed (add 7 to both sides, then divide both sides by 2), so every real solution must equal 5. Put in the two-witness form: if 2a - 7 = 3 and 2b - 7 = 3, subtracting the two equations gives 2a - 2b = 0, so a = b.
Both halves hold, so (a) is true, with x = 5 the one and only solution.
(b) Both x = 3 and x = -3 are integers satisfying x^2 = 9, and 3 \ne -3. That alone settles it: a single pair of different witnesses refutes uniqueness, and it makes no difference how many other integers were checked. So (b) is false, even though {\exists x \in \mathbb{Z},\ x^2 = 9} is true.
A parity statement, proved for every integer
Prove that for every integer n, there is exactly one r \in \{0, 1\} for which n - r is even.
SolutionFix an integer n; the domain here is the two-member set \{0, 1\}.
Existence. If n is even, take r = 0: then {n - r = n} is even. If n is odd, take r = 1: then {n - r = n - 1} is even, since an odd number minus 1 is even. Either way, some r in \{0, 1\} works.
Uniqueness. Suppose, for contradiction, that both r = 0 and r = 1 worked, meaning n and n - 1 were both even. Their difference {n - (n - 1) = 1} would then be a difference of two even numbers, hence even, but 1 is odd. That is impossible, so r = 0 and r = 1 cannot both work: assuming two witnesses and reaching something false shows at most one member of \{0, 1\} satisfies the condition.
Existence and uniqueness together give {\exists! r \in \{0, 1\},\ n - r \text{ is even}}, for every integer n. The same idea, splitting a number by its remainder, is carried out for any divisor, not only 2, in the division algorithm.
Why a real number has only one real cube root
Fix a real number c. That c has at least one real cube root is a fact about the real numbers that this example takes as given, not proves: it needs the completeness of \mathbb{R}, usually through the intermediate value theorem. Prove the other half, that c has at most one real cube root, so that {\exists! x \in \mathbb{R},\ x^3 = c} is true for every real c.
SolutionSuppose a and b are real numbers with a^3 = c and b^3 = c. The goal is a = b. Subtracting,
and the difference of two cubes factors, for any real a and b of any sign:
A product of two real numbers is 0 only when one of the factors is 0, so there are two cases.
Case 1: a - b = 0. Then a = b directly.
Case 2: a^2 + ab + b^2 = 0. Completing the square on a rewrites this factor as
a sum of two squares, neither of them negative. The sum is 0 only when both are 0: first b = 0, and then a + 0 = 0, so a = 0. That gives a = b = 0, so a = b in this case too (it is the case c = 0).
In both cases a = b, so no real number has two different real cube roots. Negative values need no separate treatment: the factorization and the completed square hold for every real a and b, which is why -8 has the single real cube root -2. Compare squares: there a^2 - b^2 = (a - b)(a + b), and the second factor is 0 whenever b = -a, which is exactly how 2 and -2 both square to 4 in the figure above.
With existence taken as given, {\exists! x \in \mathbb{R},\ x^3 = c} holds for every real c. This is what entitles \displaystyle \sqrt[3]{c} to mean “the” real cube root of c. Writing arguments like this one is the subject of uniqueness proofs.
Boundaries
The domain is part of the statement. {\exists x,\ x^2 = 2} is true or false depending on whether x ranges over \mathbb{R} or over \mathbb{Q} (Example 2). When the domain is left unsaid, it is being assumed, and it is worth saying out loud.
“Some” means at least one, not “some but not all”. “Some squares are rectangles” is true in mathematics even though every square is a rectangle. If you mean “some, but not all”, you are making two claims, and you have to make both.
An “if ... then” inside “there exists” says almost nothing. The statement {\exists x \in \mathbb{R},\ (x > 5 \to x^2 < 0)} is true, with witness x = 0: for that x the “if” part is false, and a conditional with a false “if” part counts as true. That is almost certainly not what the writer meant. “Some number greater than 5 has a negative square” is {\exists x \in \mathbb{R},\ (x > 5 \land x^2 < 0)}, which is false. As a rule of thumb, “there exists” is followed by “and”; it is “for all” that is followed by “if ... then”.
True is not the same as found. The statement is true when a witness exists, whether or not anyone can name it. Some proofs show a witness must exist without ever producing it; the pigeonhole principle is the classic tool for that.
Uniqueness alone never proves existence. {\exists! x \in \mathbb{Z},\ 2x = 7} is false: no integer solves 2x = 7, so existence already fails. Yet the uniqueness half, “any two integers solving 2x = 7 are equal”, is true here, only because there is nothing to compare. That is a vacuous truth, the same one that makes a “for all” statement over an empty domain true. “At most one” is a real and sometimes useful claim, but it is not \exists! until the existence half is proved as well.
Enlarging the domain can destroy unique existence. A bigger domain can only add witnesses to a plain existential statement, so {\exists x \in D,\ P(x)} stays true when D grows. Unique existence has no such guarantee: {\exists! x \in \mathbb{Z}^+,\ x^2 = 4} is true, with the single witness 2, but {\exists! x \in \mathbb{Z},\ x^2 = 4} is false, because the larger domain hands the predicate a second witness, -2.
Two \exists! in a row do not mean one pair. It is tempting to read {\exists! x\ \exists! y,\ P(x, y)} as “exactly one pair (x, y) makes P true”. It does not say that. Take the domain \{0, 1\} for both letters and P(x, y): “xy = 0”. For x = 0 both values of y work, so “exactly one y” fails; for x = 1 only y = 0 works, so it holds. Exactly one x passes, and the statement is true, yet three pairs, (0, 0), (0, 1) and (1, 0), make P true. “Exactly one pair” has to be written with one \exists! ranging over pairs.
Where this goes next
The most important use of “there exists” is in saying that “for all” is false. “Not every prime is odd” means “there exists a prime that is not odd”, and that is proved by holding up 2. A single counterexample is exactly a witness to an existential statement, and turning a negated “for all” into a “there exists” is the skill of negating a quantified statement.
Proving that something exists is its own family of proofs, from exhibiting the object, as Euler did, to showing it cannot fail to be there: existence proof. Proving that there is at most one, by taking two witnesses and showing they agree, is the other half of every “exactly one” claim, and writing it properly is uniqueness proof, which leans on proof by contradiction whenever assuming two different witnesses is the easiest way to reach something false.
When one quantifier sits inside another, as in “for every x there is a y with y > x”, the order of the two decides what is being said; that is nested quantifiers, and it is how the limit is finally made precise. Unique existence hides inside one of the most ordinary definitions of all: a function is a rule that assigns to every input in its domain exactly one output, {\forall x \in A,\ \exists! y \in B,\ (x, y) \text{ is in the rule}}. Example 9 had the same shape, {\forall c \in \mathbb{R},\ \exists! x \in \mathbb{R},\ x^3 = c}, and it is exactly what makes the cube root a function.
Exercises
Reading and writing
- Write in words, and decide whether it is true: {\exists n \in \mathbb{Z},\ n^2 = 16}.
- Write in symbols, and decide whether it is true: “Some real number is equal to its own square.”
- Write in symbols, and decide whether it is true: “There is a positive integer that is a multiple of both 4 and 6.” Use \mathbb{Z}^+ for the positive integers.
- Write in symbols, and decide whether it is true: “There is exactly one real number that equals its own negative.”
- Does each sentence say “at least one”, “exactly one” or “for all”? (a) Every square is a rectangle. (b) Some rectangles are squares. (c) There is at least one even prime. (d) A triangle has three sides. (e) The cubic has exactly one real root. (f) Every root of the cubic is real. Explain how you can tell.
- “At least one of the numbers 12, 15, 21 and 35 is prime.” Name the domain and the predicate, and decide whether the statement is true.
There exists: true or false
- {\exists x \in \mathbb{R},\ x^2 = -4}
- (a) {\exists z \in \mathbb{C},\ z^2 = -4}; (b) {\exists! z \in \mathbb{C},\ z^2 = -4}
- (a) {\exists n \in \mathbb{Z},\ 2n + 1 = 10}; (b) {\exists x \in \mathbb{Q},\ 2x + 1 = 10}
- D = \{1, 2, 3, 4, 5, 6, 7, 8\} and the statement is {\exists x \in D,\ x^2 - 9x + 20 = 0}.
- D = \{2, 3, 4, 5\} and the statement is “there is an x in D for which x^2 + 3 is a multiple of 5”.
- Is there an integer n \ge 2 with 2^n > n^3? If so, find the smallest one.
- Find a prime p for which 2^p - 1 is not prime.
Exactly one: true or false
- (a) {\exists! x \in \mathbb{R},\ x^3 = -8}; (b) {\exists! x \in \mathbb{Z},\ 3x = 7}
- {\exists! x \in \mathbb{R},\ x^4 = 16}
- D = \{1, 2, 3, 4, 5\} and the predicate is “x is prime”. Decide whether {\exists! x \in D,\ P(x)}.
- D = \{-1, 0, 1, 2, 3\} and the predicate P(x) is x^2 = 4. Decide whether {\exists! x \in D,\ P(x)}.
- D = \{5\} and the predicate is “x > 0”. Decide whether {\exists! x \in D,\ P(x)}, and explain why a domain with only one member makes this an easy case.
Domains, “and” and “or”
- The statement {\exists x,\ 3x = 1} is false in exactly one of the domains \mathbb{Z}, \mathbb{Q} and \mathbb{R}. Which one, and why?
- Decide each. (a) {\exists x \in \mathbb{R},\ x^2 + 4x + 7 < 3}; (b) {\exists x \in \mathbb{R},\ x^2 + 4x + 7 \le 3}.
- Decide each. (a) {\exists n \in \mathbb{Z},\ \big(n^2 = 25 \land n < 0\big)}; (b) {\exists n \in \mathbb{Z},\ \big(n^2 = 25 \land n > 5\big)}; (c) {\big(\exists n \in \mathbb{Z},\ n^2 = 25\big)} \land {\big(\exists n \in \mathbb{Z},\ n > 5\big)}.
- Give two predicates P(n) and Q(n) about integers for which {\exists n,\ P(n)} and {\exists n,\ Q(n)} are both true but {\exists n,\ \big(P(n) \land Q(n)\big)} is false.
Conditions on a coefficient
- For which real numbers c is {\exists x \in \mathbb{R},\ x^2 - 6x + c = 0} true?
- For which value of c is {\exists! x \in \mathbb{R},\ 2x^2 + 12x + c = 0} true?
- For which value of b > 0 is {\exists! x \in \mathbb{R},\ x^2 + bx + 4 = 0} true?
Proving exactly one
- Prove that every real number r has exactly one additive inverse: {\exists! y \in \mathbb{R},\ r + y = 0}.
- Let D be the set of nonzero real numbers, and fix a nonzero real number r. Prove that {\exists! y \in D,\ ry = 1}.
- Prove that for every integer n, there is exactly one r \in \{0, 1, 2\} for which n - r is a multiple of 3.
Reasoning
- A classmate says “{\exists n \in \mathbb{Z},\ n^2 = 3n + 1} is false, because I tried n = 0, 1, 2, 3 and 4 and none of them worked.” Is the conclusion right, and is the reason good enough? Explain.
- Let D be the set of integers n with n^2 < 0. (a) Is {\exists x \in D,\ x = x} true? The predicate x = x is true of every number, so explain carefully. (b) Is {\exists! x \in D,\ x = x} true? Explain why its uniqueness half is nonetheless true.
- Show that if D has at least one member and {\forall x \in D,\ P(x)} is true, then {\exists x \in D,\ P(x)} is true. Why is “at least one member” needed?
- Prove that {\exists! x \in D,\ P(x)} always forces {\exists x \in D,\ P(x)} to be true, and give a domain and predicate for which the second is true and the first is false.
- Explain why a true statement {\exists x \in \mathbb{Z},\ P(x)} forces {\exists x \in \mathbb{R},\ P(x)} to be true, and give a predicate for which the second is true and the first is false.
- Give a predicate P and domains D \subset E for which {\exists! x \in D,\ P(x)} is true but {\exists! x \in E,\ P(x)} is false. Explain in one sentence why enlarging the domain caused the change.
- A student writes {\exists n \in \mathbb{Z},\ (n > 10 \to n^2 < 50)} to mean “some integer greater than 10 has a square less than 50”. Explain why the symbols are true while the sentence is false, and correct the symbols.
- A classmate says, “I showed that any two solutions of this equation must be equal, so it has exactly one solution.” Give an equation with zero real solutions for which “any two solutions are equal” is nonetheless true, and explain what the classmate’s argument is missing.
- Let both x and y range over \{0, 1\}. Decide whether {\exists! x\ \exists! y,\ x \le y} is true, count the pairs (x, y) with x \le y, and explain why the two answers do not contradict each other.
Answers
- True. “There is an integer whose square is 16.” A witness is n = 4, since 4^2 = 16 (n = -4 also works).
- {\exists x \in \mathbb{R},\ x^2 = x}. True, with witness x = 1, since 1^2 = 1. (x = 0 works too: x^2 = x means x(x - 1) = 0.)
- {\exists n \in \mathbb{Z}^+,\ (4 \mid n \land 6 \mid n)}, where 4 \mid n is read “4 divides n”. True, with witness n = 12 = 4 \times 3 = 6 \times 2.
- {\exists! x \in \mathbb{R},\ x = -x}. True: x = -x gives 2x = 0, so x = 0 is the only possibility, and it does work.
- “At least one”: (b) and (c). “Exactly one”: (e). “For all”: (a), (d) and (f). (a) is about every square. (d) begins with “a”, but it means every triangle; “a” can go either way in English, which is one reason for the symbols. (e) claims a root exists and adds that there is no second one. (f) is a claim about all the roots, not about whether any exist at all.
- The domain is \{12, 15, 21, 35\} and the predicate is “x is prime”. The statement is false: 12 = 2 \times 6, 15 = 3 \times 5, 21 = 3 \times 7 and 35 = 5 \times 7, so no member is prime.
- False. For every real x, x^2 \ge 0, so x^2 is never -4.
- (a) True, with witness z = 2i: (2i)^2 = 4i^2 = -4. (b) False: {z = 2i} and {z = -2i} are two different witnesses, since (-2i)^2 = -4 as well.
- (a) False. The only number with 2n + 1 = 10 is \displaystyle n = \frac{9}{2}, which is not an integer. (Also, 2n + 1 is always odd and 10 is even.) (b) True, with witness \displaystyle x = \frac{9}{2}, which is a fraction: \displaystyle 2 \cdot \frac{9}{2} + 1 = 10. Same predicate, different domain, different answer.
- True. x^2 - 9x + 20 = (x - 4)(x - 5), so {x = 4} is a witness (and so is x = 5), and both are in D.
- False. The values of x^2 + 3 are 7, 12, 19 and 28, and none is a multiple of 5. With only four members, checking all four settles it.
- Yes, and the smallest is n = 10: 2^{10} = 1024 > 1000 = 10^3. For n = 2 to 9 the powers of 2 are 4, 8, 16, 32, 64, 128, 256, 512 and the cubes are 8, 27, 64, 125, 216, 343, 512, 729, and each power is smaller.
- p = 11: 2^{11} - 1 = 2047 = 23 \times 89. (The smaller primes 2, 3, 5, 7 give 3, 7, 31, 127, which are all prime.)
- (a) True. x = -2 is a witness, since (-2)^3 = -8, and by Example 9 no real number has two different real cube roots. (b) False, and this time it is existence that fails: the only number with 3x = 7 is \displaystyle x = \frac{7}{3}, which is not an integer, so there is no witness at all.
- False. x = 2 and x = -2 are two different real witnesses, since 2^4 = 16 and (-2)^4 = 16.
- False. The primes in D are 2, 3 and 5, three different witnesses.
- True. Of the five members only x = 2 has x^2 = 4; the other real number with that square, -2, is not in D. The count of witnesses is exactly 1.
- True. The only candidate is 5, and 5 > 0 is true, so it is a witness; with only one member in D to begin with, uniqueness is automatic, since there is no second member to disagree.
- \mathbb{Z}. The only solution of 3x = 1 is \displaystyle x = \frac{1}{3}, which is rational and real but not an integer.
- (a) False, (b) true. Completing the square, x^2 + 4x + 7 = (x + 2)^2 + 3, which is at least 3 for every x, so it is never below 3; it equals 3 at x = -2, which is a witness for (b).
- (a) True, witness n = -5. (b) False, since only 5 and -5 square to 25 and neither is greater than 5. (c) True: 5 is a witness for the first claim and 6 for the second.
- For example P(n) is n < 0 and Q(n) is n > 0. Each has a witness (-1 and 1), but no integer is both negative and positive. Any two predicates that each hold somewhere but never hold together will do.
- c \le 9. There is a real root exactly when the discriminant 36 - 4c \ge 0. For example c = 9 gives (x - 3)^2 = 0 with witness x = 3.
- c = 18. The discriminant 144 - 8c must be 0, and then 2x^2 + 12x + 18 = 0 simplifies to (x + 3)^2 = 0, giving the single witness x = -3.
- b = 4. The discriminant b^2 - 16 must be 0, so b = 4 or b = -4, and only b = 4 satisfies b > 0; then x^2 + 4x + 4 = (x + 2)^2 = 0 gives the single witness x = -2.
- Existence: y = -r satisfies r + y = r + (-r) = 0. Uniqueness: suppose r + y_1 = 0 and r + y_2 = 0. Subtracting gives y_1 - y_2 = 0, so y_1 = y_2. Both halves hold, so r has exactly one additive inverse.
- Existence: \displaystyle y = \frac{1}{r} is nonzero (since r is nonzero) and satisfies \displaystyle ry = r \cdot \frac{1}{r} = 1. Uniqueness: suppose ry_1 = 1 and ry_2 = 1. Then ry_1 = ry_2, and since r \ne 0, dividing both sides by r gives y_1 = y_2.
- Existence: by the division algorithm, {n = 3q + r} for some integer q and some r \in \{0, 1, 2\}, so n - r = 3q is a multiple of 3. Uniqueness: suppose r and r' are both in \{0, 1, 2\} and {n - r} and {n - r'} are both multiples of 3. Their difference {(n - r) - (n - r') = r' - r} is then a multiple of 3 too, and since r, r' \in \{0, 1, 2\}, r' - r lies between -2 and 2; the only multiple of 3 in that range is 0, so r = r'.
- The conclusion is right but the reason is not. Trying five values cannot show that no integer works. A full argument: the solutions of {n^2 - 3n - 1 = 0} are \displaystyle n = \frac{3 \pm \sqrt{13}}{2}, and since 13 is not a perfect square these are not integers.
- (a) False. No integer has a negative square, so D is empty. A witness has to be a member of D, and there are none, so it does not matter how easy the predicate is to satisfy. (b) Also false, for the same reason: existence fails before uniqueness is ever needed. The uniqueness half, “any two members of D with x = x are equal”, is true only because there are no members to compare, the same vacuous truth that makes a “for all” over the empty domain true. A vacuous uniqueness proves nothing about existence.
- Let a be a member of D. Since P(x) holds for every member, P(a) holds, so a is a witness. Without a member there is nothing to pick: over \varnothing every “for all” is true and every “there exists” is false.
- If {\exists! x \in D,\ P(x)} is true, then in particular some member of D makes P true, which is exactly what {\exists x \in D,\ P(x)} claims. For the other direction: with D = \mathbb{R} and P(x) the predicate {x^2 = 4}, {\exists x \in D,\ P(x)} is true (two witnesses, 2 and -2), but {\exists! x \in D,\ P(x)} is false.
- A witness is an integer, and every integer is a real number, so the same witness works over \mathbb{R}. For example P(x): “2x = 1” is true over \mathbb{R} with witness \displaystyle \frac{1}{2} and false over \mathbb{Z}, since \displaystyle \frac{1}{2} is its only solution.
- One answer: P(x): “x^3 = 1”, D = \mathbb{R}, E = \mathbb{C}. Over \mathbb{R} the only witness is 1 (Example 9), so {\exists! x \in D,\ P(x)} is true. Over \mathbb{C}, x^3 - 1 = (x - 1)(x^2 + x + 1), and {x^2 + x + 1 = 0} adds the two witnesses \displaystyle x = \frac{-1 \pm i\sqrt{3}}{2}, so {\exists! x \in E,\ P(x)} is false. Enlarging the domain can only add candidates, so new witnesses can appear and break uniqueness.
- Take n = 0. Then “n > 10” is false, and a conditional with a false “if” part is true, so 0 is a witness and the symbols are true. The sentence means {\exists n \in \mathbb{Z},\ (n > 10 \land n^2 < 50)}, which is false: an integer greater than 10 is at least 11, so its square is at least 121.
- x^2 + 1 = 0 over the real numbers has zero solutions, and “any two solutions are equal” is true of it anyway, vacuously, since there are no solutions to compare. The classmate proved only the uniqueness half; without also showing that some solution exists, “any two solutions are equal” fits there being none at all.
- True, and there are three pairs. For x = 0, both y = 0 and y = 1 satisfy 0 \le y, so “exactly one y” fails; for x = 1, only y = 1 works, so it holds. Exactly one x, namely 1, passes, so {\exists! x\ \exists! y,\ x \le y} is true. The pairs with x \le y are (0, 0), (0, 1) and (1, 1). No contradiction: the statement says exactly one x has exactly one partner y, not that exactly one pair works; the pairs (0, 0) and (0, 1) belong to an x that failed the inner test.