Proof depth: auditing arguments, dependence and uniqueness

1. Audit the dependency graph, not just the last line

For each claimed proof, ask:

1. What exactly is quantified, over which domain, and in what order?
2. Which facts are assumptions, and which are the conclusion being sought?
3. Does every constructed expression exist on the stated domain?
4. Does each inference follow from an earlier established fact?
5. If a candidate is obtained, has it been substituted back to prove existence?
6. If uniqueness is claimed, what counts as the same object: literal equality, order-independent factors, or an equivalence class?

A counterexample disproves a claim, while locating the first invalid inference diagnoses a proof. Both are useful, but they answer different questions. A true claim can have an invalid proof; finding a faulty argument does not itself make its conclusion false.

Worked audit: circular parity reasoning. To prove “if $n^2$ is even, then $n$ is even,” a student writes, “Let $n=2k$; then $n^2=4k^2$, so the assertion follows.” The first line assumes the conclusion: an arbitrary integer with even square has not yet been shown to equal twice an integer. The calculation proves the reverse implication, even $n$ implies even square.

A valid repair uses the contrapositive. If $n$ is odd, $n=2k+1$ for an integer $k$, so $n^2=2(2k^2+2k)+1$ is odd. This rules out odd $n$ when its square is even. The representation now follows from the stated assumption rather than from the desired conclusion.

Worked audit: solving is not constructing. From $ax=b$, division formally suggests $x=b/a$. That gives a candidate only when $a\ne0$; substitution then proves it solves the equation. To prove uniqueness, if $ax=ay=b$, subtract to obtain $a(x-y)=0$, and cancel nonzero $a$. If $a=0$, the conclusion splits: no solution when $b\ne0$, every real number a solution when $b=0$. A derivation that silently divides by $a$ misses both cases.

2. Witness dependence is mathematical content

For real numbers, $\forall x\exists y:y>x$ allows the witness $y=x+1$ to depend on $x$. It does not prove $\exists y\forall x:y>x$. A useful audit draws arrows from earlier choices to later permitted choices. An existential witness may use already selected inputs but not variables that are quantified only afterwards.

A less immediate example. Let $A=(0,1]$ and for each positive integer $n$ define $f_n(x)=n$ if $x=1/n$, and zero otherwise. For each fixed $n$, the function is bounded by $n$. For each fixed $x$, the numbers $f_n(x)$ are also bounded as $n$ varies: at most one is nonzero. Yet there is no bound valid for every $n$ and every $x$, since $f_n(1/n)=n$.

Thus both statements $\forall n\exists M_n\forall x:|f_n(x)|\le M_n$ and $\forall x\exists M_x\forall n:|f_n(x)|\le M_x$ are true, while $\exists M\forall n\forall x:|f_n(x)|\le M$ is false. Taking a supremum without proving it finite would hide precisely the missing uniformity. Continuity is not assumed or needed in this logical example.

3. Induction needs every transition, not just a plausible pattern

Consider the false assertion “every finite nonempty set of real numbers has all its elements equal.” A purported induction says: the one-element case is true; for an $(n+1)$-element set, remove one element to get $n$ equal elements, remove a different one to get another $n$ equal elements, and use their overlap to make the two common values agree.

For $n\ge2$, the two $n$-element subsets do overlap. But in the crucial first step $n=1$, the two singleton subsets of a two-element set have empty intersection. There is no shared element to connect their values. The induction implication was not proved for every required $n\ge1$. The counterexample $\{0,1\}$ confirms falsity, while the empty overlap identifies the exact failed transition.

This is different from strong induction, where assuming all smaller cases is legitimate inside the step. Strong induction still requires a valid base and a proof covering every next index. A recursive construction must decrease to an established base; merely invoking “smaller” without specifying a decreasing positive integer does not prove termination.

4. Normalization and prime factors

Here $\mathbb N=\{0,1,2,\ldots\}$.

Theorem

Division algorithm

Let $a,b\in\mathbb Z$ with $b\ne0$. Then there exist unique integers $q$ and $r$ such that

$$a=bq+r,\qquad 0\le r\lt|b|.$$

The integer $q$ is the quotient and $r$ is the remainder.

The condition $0\le r\lt|b|$ is not decoration. It is what makes the remainder unique. For example,

$$17=5\cdot3+2$$

has an allowed remainder $2$, while

$$17=5\cdot2+7$$

does not count as the division algorithm because $7$ is not smaller than $5$.

For existence, first take $a\ge0$ and $b>0$. The set

$$S=\{a-bn:n\in\mathbb N,\ a-bn\ge0\}$$

contains $a$, so well-ordering supplies a least member $r=a-bq$. If $r\ge b$, then $r-b=a-b(q+1)$ would be a smaller nonnegative member. Hence $0\le r\lt b$. If $a\lt0$ and $b>0$, the integer $A=a+(-a)b=(-a)(b-1)$ is nonnegative. Divide $A=bQ+r$ by the case just proved; rearranging gives $a=b(Q+a)+r$ with the same allowed remainder. For $b\lt0$, divide by $B=|b|>0$ and replace the resulting quotient $Q$ by $-Q$. Thus no sign case requires a negative remainder.

For uniqueness, suppose $a=bq+r=bq'+r'$ with both remainders in range. Then $b(q-q')=r'-r$, but $|r'-r|\lt|b|$. A nonzero integer multiple of $b$ has absolute value at least $|b|$, so $r'=r$. Since $b\ne0$, the remaining equality forces $q'=q$. The strict upper bound proves uniqueness; merely requiring a nonnegative remainder would not.

Theorem

Gcd step

If $a=bq+r$, then

$$\gcd(a,b)=\gcd(b,r).$$

Proof: Preserve the entire set of common divisors

The target is equality of two gcds. A stronger intermediate statement makes the proof direct: an integer $h$ divides both $a,b$ exactly when it divides both $b,r$. In the forward direction use $r=a-bq$; in the reverse direction use $a=bq+r$. Both steps use closure under integer linear combinations.

The two divisor sets therefore have the same greatest element when the inputs are not both zero. If $a=b=0$, then $r=0$ and both gcds equal $0$ by convention. The identity itself does not need a remainder bound; the bound is needed to make the algorithm progress.

Concept lensAlgorithmic

An invariant and a decreasing computation

The gcd is the quantity preserved by each replacement $(a,b)\mapsto(b,r)$. The remainder is the quantity made smaller. These serve different purposes: preservation proves that the final answer is the original gcd, while strict decrease proves that a final step will occur. Start with absolute values, swap to put the larger positive input first, and stop immediately if the other input is zero. In every remaining division the divisor is positive.

The algorithm must terminate because the remainders form a strictly decreasing sequence of nonnegative integers:

$$r_1>r_2>r_3>\cdots\ge0.$$

A strictly decreasing sequence of nonnegative integers cannot continue forever.

Back-substitution can also be organized forward. For positive inputs put $r_0=a$, $r_1=b$, and keep coefficients $r_k=s_ka+t_kb$, starting with $(s_0,t_0)=(1,0)$ and $(s_1,t_1)=(0,1)$. If $r_{k+2}=r_k-q_{k+1}r_{k+1}$, then

$$s_{k+2}=s_k-q_{k+1}s_{k+1},\qquad t_{k+2}=t_k-q_{k+1}t_{k+1}.$$

Substituting the two known linear combinations proves this update. Every coefficient remains integral, and the row for the last nonzero remainder supplies the required coefficients of the gcd.

Theorem

Bézout's identity

For any integers $a,b$, there exist integers $x,y$ such that

$$\gcd(a,b)=ax+by.$$

For signed nonzero inputs, compute using $|a|,|b|$ and absorb their signs into the resulting coefficients. If one input is zero, use $|a|=a\operatorname{sgn}(a)$ or its counterpart for $b$; for $(0,0)$ use $x=y=0$. This proves all cases of the identity.

When the inputs are not both zero, the gcd is also the smallest positive integer linear combination. It is such a combination by the identity, and every positive combination is a positive multiple of the gcd, hence at least as large. For $(0,0)$ there is no positive combination.

Theorem

Euclid's lemma

Let $p$ be prime. If $p\mid ab$, then $p\mid a$ or $p\mid b$.

If $p\nmid a$, then $\gcd(a,p)=1$, so there exist integers $m,n$ with

$$am+pn=1.$$

Multiplying by $b$ gives

$$abm+pbn=b.$$

Since $p\mid ab$, both terms on the left are divisible by $p$, so $p\mid b$.

Theorem

Fundamental theorem of arithmetic

Every positive integer greater than $1$ can be written as a product of primes, and this product is unique up to the order of the factors.

Existence follows from the same least-counterexample strategy used earlier. If there were a least integer greater than $1$ that could not be written as a product of primes, it would not be prime, so it would split into smaller factors, and those smaller factors would already have prime factorizations.

Uniqueness uses Euclid's lemma. If

$$p_1p_2\cdots p_r=q_1q_2\cdots q_s,$$

then $p_1$ divides the right-hand product, so $p_1$ must divide one of the prime factors $q_j$. Hence $p_1=q_j$. Cancel and repeat.

Repeating Euclid's lemma reduces divisibility of a finite product to one factor. Cancellation cannot exhaust only one prime list: that would leave $1$ equal to a nonempty product of primes, which is greater than $1$. Thus the lists have the same length and the same factors with multiplicity.

For negative nonzero integers, include an overall factor $-1$ and factor the positive magnitude. The number one has an empty prime product, and zero has no prime factorization of this type. These cases belong to the theorem's domain, not to hidden exceptions.

5. Uniqueness of reduced rational representation

Suppose integers $a,c$ and positive integers $b,d$ satisfy $a/b=c/d$, with $\gcd(a,b)=\gcd(c,d)=1$. Then $a=c$ and $b=d$.

Proof. Cross multiplication gives $ad=bc$. Since $\gcd(a,b)=1$, Bezout supplies $u,v$ with $ua+vb=1$. Multiply by $d$: $d=uad+vbd=ubc+vbd$, showing $b\mid d$. Reversing the two fractions similarly gives $d\mid b$. As both denominators are positive, they must be equal. The cross-product equality then gives equal numerators. This argument handles numerator zero: coprimality forces its positive denominator to be one.

Existence is a separate argument. From any integer fraction with nonzero denominator, first make the denominator positive, then divide numerator and denominator by their positive gcd. The quotient integers exist because the gcd divides both, the value is preserved, and no common factor remains. Only after this construction does the uniqueness theorem justify the phrase “the reduced fraction.”

Graded proof tasks

1. Direct and converse. Prove for integers $n$ that $n$ is odd if and only if $n^2\equiv1\pmod8$.
2. Repair. Audit “if $ab=ac$, divide by $a$ to get $b=c$” over real numbers. State a correct theorem, prove it, and classify the exceptional case.
3. Uniformity. For the functions $f_n$ above, write the negation of a common bound and exhibit witnesses in the required order.
4. Existence versus uniqueness. Explain why the prime-factor uniqueness argument alone does not prove that every $n\ge2$ has a prime factorization. Supply the strong-induction existence argument in full.
5. Normalization. What fails in reduced-fraction uniqueness if denominators may be negative? State and prove the appropriate corrected uniqueness description.
6. One-sided inverse. If $f\circ g$ is the identity on $Y$, prove $f$ is onto $Y$ and $g$ is injective. Must $f$ be injective and $g$ be onto their other declared sets? Give a verified counterexample.

Full solutions

1. If $n=2k+1$, then $n^2=4k(k+1)+1$. One of consecutive integers $k,k+1$ is even, so $8\mid4k(k+1)$ and $n^2\equiv1$. Conversely that congruence makes $n^2$ odd. An even integer has even square, so $n$ cannot be even and is odd. Each direction is explicit.
2. The division requires $a\ne0$. Under that assumption multiplication by $1/a$ proves $b=c$. If $a=0$, the premise becomes $0=0$ and places no restriction on $b,c$; for example $b=0,c=1$ disproves the unrestricted assertion. The first invalid step is division by an unverified nonzero number.
3. The negation is $\forall M>0\exists n\ge1\exists x\in(0,1]:|f_n(x)|>M$. Given $M$, choose an integer $n>M$, then choose $x=1/n$. This produces $|f_n(x)|=n>M$. The integer depends on the proposed bound, and the point depends on that integer; no fixed point must defeat all bounds.
4. Uniqueness starts with two already supplied factorizations and cannot create either one. For existence, use base $n=2$, prime itself. Suppose every integer from two through $n-1$ is a prime product. If $n$ is prime, stop. Otherwise $n=ab$ with $2\le a,b<n$. The hypothesis supplies prime products for both, whose concatenation factors $n$. Every recursive argument uses smaller positive integers, and strong induction proves all cases.
5. Even with coprime numerator and denominator, $a/b=(-a)/(-b)$ gives two sign choices, such as $1/2=(-1)/(-2)$. Normalizing each denominator to positive yields the unique normalized pair by the theorem. Therefore without the sign convention the two pairs must be equal or simultaneous negatives. Conversely simultaneous negation always preserves the rational value and coprimality, proving that exact ambiguity description.
6. For any $y\in Y$, $y=f(g(y))$, so $f$ is onto. If $g(y_1)=g(y_2)$, applying $f$ gives $y_1=y_2$, so $g$ is injective. The other conclusions need not hold: let $f:\mathbb R\to[0,\infty)$ be $f(x)=x^2$ and $g:[0,\infty)\to\mathbb R$ be $g(y)=\sqrt y$. Then $f\circ g$ is the identity, but $f(1)=f(-1)$ and $g$ never takes negative values. Thus $f$ is not injective and $g$ is not onto $\mathbb R$.

Summary and terms

A circular argument assumes what it is meant to prove. A dependency records which earlier data a choice may use. A normalization removes an allowed ambiguity, such as factor order or denominator sign. Uniqueness up to reordering differs from uniqueness of an ordered list. Audit the first invalid inference, then repair the precise missing condition or construction; a persuasive last line is not a substitute for those steps.