Existence, Uniqueness and Counterexamples

"For every integer $x$ there is an integer $y$ with $y > x$" is true: given $x$, take $y = x + 1$ (the $y$ may depend on $x$). "There is an integer $y$ such that for every integer $x$, $y > x$" is false: whatever $y$ is proposed, the choice $x = y$ breaks it. The same words in a different order make a different claim, and the second one says that a largest integer exists.

Claim: $n^2 + n + 41$ is prime for every natural number $n$. It is prime for $n = 0, 1, \ldots, 39$. At $n = 40$: $40^2 + 40 + 41 = 40\cdot41 + 41 = 41^2$. False. One case suffices; forty successes did not.

Claim: for every $n$ there are $n$ consecutive composite numbers. Proof: $(n + 1)! + 2, (n + 1)! + 3, \ldots, (n + 1)! + (n + 1)$ are $n$ consecutive numbers, and $(n + 1)! + j$ is divisible by $j$ for each $j$ from $2$ to $n + 1$ (both terms are), while being larger than $j$. $\blacksquare$

Claim: the sum of two irrational numbers is irrational. Counterexample: $\sqrt2$ and $-\sqrt2$ are both irrational, and their sum is $0$, which is rational. The boundary case — numbers that cancel — was the place to look.

Claim: if $p$ is prime, then $2^p - 1$ is prime. The small cases agree: $p = 2, 3, 5, 7$ give $3, 7, 31, 127$, all prime. But $p = 11$ gives $2^{11} - 1 = 2047 = 23\cdot89$. False. Four confirmations were a reason to look harder, not a proof.

Put $n$ points on a circle in general position and join every pair; count the regions inside. For $n = 1, 2, 3, 4, 5$ the counts are $1, 2, 4, 8, 16$ — surely $2^{n-1}$? For $n = 6$ there are $31$. The correct count, $\binom n4 + \binom n2 + 1$, agrees with $2^{n-1}$ up to $n = 5$ and then falls behind. Five cases fitted a false pattern.

Claim: $3x - 7 = 11$ has exactly one real solution. Existence: $x = 6$ works, since $18 - 7 = 11$. Uniqueness: if $3x - 7 = 11$ and $3y - 7 = 11$, then $3x = 3y$, so $x = y$. $\blacksquare$

In any group, the identity is unique: if $e$ and $e'$ are both identities, then $e = ee' = e'$ (the first equality because $e'$ is an identity, the second because $e$ is). $\blacksquare$

An integer is divisible by $4$ iff its last two digits form a number divisible by $4$. Write $n = 100a + b$ with $0 \le b < 100$. Since $4 \mid 100a$, $4 \mid n$ iff $4 \mid b$ — one line, both directions, because "$4 \mid 100a + b \iff 4 \mid b$" is a genuine equivalence. $\blacksquare$

If $a < b$ are rational, then $\dfrac{a + b}{2}$ is rational (a sum of rationals divided by $2$) and lies strictly between them, since $a = \dfrac{a + a}{2} < \dfrac{a + b}{2} < \dfrac{b + b}{2} = b$. Constructive: the number is named.

At a party of $n \ge 2$ people, two have the same number of friends at the party. Each count is one of $0, 1, \ldots, n - 1$. But $0$ and $n - 1$ cannot both occur: someone friends with everyone rules out someone friends with no one. So the $n$ counts take at most $n - 1$ values, and two coincide. $\blacksquare$ We know two such people exist; the proof does not say who.

There exist irrational $a, b$ with $a^b$ rational. Consider $\sqrt2^{\sqrt2}$. If it is rational, take $a = b = \sqrt2$. If it is irrational, take $a = \sqrt2^{\sqrt2}$ and $b = \sqrt2$: then $a^b = \sqrt2^{\sqrt2\cdot\sqrt2} = \sqrt2^{\,2} = 2$. One of the two cases holds, so such $a, b$ exist. $\blacksquare$

Claim: every positive integer $n$ can be written as $n = 2^a m$ with $a \ge 0$ and $m$ odd, in exactly one way. Existence: divide $n$ by $2$ as long as the result is even; this stops, because the quotients are positive integers that keep decreasing. If it stops after $a$ divisions at the odd number $m$, then $n = 2^a m$. Uniqueness: suppose $2^a m = 2^b m'$ with $m, m'$ odd and, say, $a < b$. Dividing by $2^a$ gives $m = 2^{b-a}m'$, which is even — contradiction. So $a = b$, and then $m = m'$. $\blacksquare$