Existence and Uniqueness Proofs

Existence-and-uniqueness theorems are the backbone of differential equations: the Picard–Lindelöf theorem proves both existence and uniqueness of solutions to an initial value problem $y' = f(t,y),\ y(t_0)=y_0$ under a Lipschitz condition on $f$, and the two halves genuinely require different arguments (a fixed-point/contraction-mapping construction for existence, a Grönwall-inequality estimate for uniqueness). In linear algebra, a system $Ax=b$ has existence of solutions governed by whether $b$ lies in the column space of $A$, and uniqueness governed by whether $\ker A = \{0\}$ — two independent rank conditions. In number theory, the Fundamental Theorem of Arithmetic is itself an existence-and-uniqueness statement about prime factorizations, with existence proved by strong induction (foreshadowing Mathematical Induction) and uniqueness proved using Euclid's Lemma. In computer science, existence proofs for algorithms (a solution exists) are routinely nonconstructive via counting or probabilistic arguments (the probabilistic method), while cryptographic protocols often need the unique-existence of a decryption key or discrete logarithm to guarantee correctness and security. In statistics, the existence and uniqueness of a maximum-likelihood estimator is a standard prerequisite check before any inference is trusted, typically established via convexity (uniqueness) and compactness or boundary behavior (existence).

:::quiz[Suppose $\neg \exists x\, P(x)$ over some domain. What is the truth value of $\forall x\,\forall y\,[(P(x)\wedge P(y))\to x=y]$?]

• False, since no solutions means uniqueness cannot hold
• True, vacuously, since the antecedent is always false ✓
• Undefined, because $P$ has no witnesses
• It depends on whether $D$ is finite

Ask the tutor: Can you show me how the existence and uniqueness proofs work together in the Picard–Lindelöf theorem for differential equations?

Think of $P(x)$ as a "test" that elements of $D$ either pass or fail. Existence asks: is the set of passers nonempty? Uniqueness asks: does the set of passers have at most one element? These are orthogonal questions about the size of the solution set $S = \{x \in D : P(x)\}$. Existence says $|S| \geq 1$; uniqueness says $|S| \leq 1$; unique existence says $|S| = 1$. Phrasing it this way makes clear why the two halves need separate proofs: knowing $|S| \leq 1$ tells you nothing about whether $|S| = 0$ or $|S|=1$, and knowing $|S|\geq 1$ tells you nothing about whether $S$ might have two, three, or infinitely many elements. The uniqueness template deserves a picture of its own logical shape. To show $|S|\le 1$ directly by counting is often impossible (you cannot enumerate an infinite domain), so instead one uses the indirect but non-contradictory device: pick two arbitrary elements of $S$ and prove algebraically that they coincide. This converts a statement about counting solutions into a statement about equality of two named objects, which is exactly the kind of statement ordinary algebra and logic are built to handle.

This lemma is the formal justification for the warning given in the overview: a correct uniqueness proof, by itself, proves nothing about existence, and can even be true "for free" when the solution set is empty. Every complete existence-and-uniqueness theorem must therefore discharge (E) as a genuinely separate obligation.

Example 1 (Nonconstructive existence + algebraic uniqueness): a real root of $f(x) = x^3 - 4x^2 + 2$. Claim: there is a unique real number $r$ with $f(r) = 0$ and $r < 0$; moreover we prove this $r$ is the only negative root even though we never compute its decimal value. Existence, nonconstructive. $f$ is a polynomial, hence continuous on all of $\mathbb R$. Compute

Since $f$ is continuous on $[-1,0]$ and $f(-1) < 0 < f(0)$, the Intermediate Value Theorem guarantees some $r \in (-1,0)$ with $f(r) = 0$. This is nonconstructive: we know $r$ exists and lies strictly between $-1$ and $0$, but the IVT gives no formula or algorithm for $r$ beyond this argument (extracting more decimal digits requires further bisection, which is a separate constructive refinement, not part of this existence claim). Uniqueness on the interval $(-1,0)$. We show $f$ has at most one root there by showing $f$ is strictly increasing on $(-1,0)$, which forces injectivity. Compute the derivative:

For $x \in (-1,0)$ we have $x < 0$ and $3x - 8 < 0$ (since $3x < 0 < 8$), so $f'(x) = x(3x-8)$ is a product of two negative numbers, hence $f'(x) > 0$ on $(-1,0)$. A function with strictly positive derivative on an interval is strictly increasing there (a standard consequence of the Mean Value Theorem: if $x_1 < x_2$ in $(-1,0)$, then $f(x_2)-f(x_1) = f'(c)(x_2-x_1) > 0$ for some $c$ between them). A strictly increasing function is injective: if $r_1 \ne r_2$ in $(-1,0)$ with $r_1 < r_2$, then $f(r_1) < f(r_2)$, so they cannot both equal $0$. This is exactly the uniqueness template: assume $r_1, r_2 \in (-1,0)$ both satisfy $f = 0$; strict monotonicity rules out $r_1 \ne r_2$, so $r_1 = r_2$. Combining: there exists a root in $(-1,0)$ (IVT, nonconstructive), and any two roots there must coincide (monotonicity, direct algebraic/analytic argument). Hence there is a unique root of $f$ in $(-1,0)$. (Global uniqueness over all of $\mathbb R$ is a separate, stronger claim — $f$ in fact has three real roots in total, one in $(-1,0)$, one in $(0,3)$, one in $(3,4)$, illustrating that uniqueness claims must always specify their domain.)

Example 2 (Constructive existence + template uniqueness): additive inverses in a group. Let $(G, *, e)$ be a group with identity $e$ (associativity holds, $e$ is a two-sided identity, and every element has some two-sided inverse — this is the group axiom set). Claim: for every $a \in G$, there is a unique $b \in G$ with $a * b = e$ and $b * a = e$. Existence, constructive. This is immediate from the group axioms themselves: the axiom "every element has an inverse" literally asserts $\exists b\, (a*b = e \wedge b*a=e)$. No further work is needed; the object is handed to us by definition — but it is worth noting explicitly that this existence clause is a hypothesis of the theorem (a group axiom), not something derived from nothing. If we only assumed $G$ were a monoid (associative with identity, no inverse axiom), existence could fail: in the monoid $(\mathbb{N}, +, 0)$, the element $a=3$ has no $b \in \mathbb N$ with $3+b=0$. Uniqueness, by template. Suppose $b_1, b_2 \in G$ both satisfy the defining property for an inverse of $a$:

We must show $b_1 = b_2$. Compute, using associativity and the identity axiom at each step:

Each equality is justified: $b_1 * e = b_1$ (identity axiom); $e = a*b_2$ (hypothesis on $b_2$); $b_1*(a*b_2) = (b_1*a)*b_2$ (associativity); $b_1 * a = e$ (hypothesis on $b_1$); $e * b_2 = b_2$ (identity axiom). Hence $b_1 = b_2$, proving uniqueness. This is the purest instance of the uniqueness template: name two candidates, use only the defining equations they are each assumed to satisfy, and algebraically force them to coincide — no analysis, no monotonicity, purely equational reasoning. It is this fact — every element of a group has a unique inverse — that licenses the notation $a^{-1}$ as a well-defined function of $a$, since a notation naming "the" inverse presupposes there is exactly one object to name.