Worked Examples: From Claims to Evidence

A complete proof with its boundary

Claim: if integers a,b are odd, a+b is even. By definition, a=2j+1 and b=2k+1 for integers j,k. Then a+b=2(j+k+1), an integer multiple of 2. The witnesses j,k may differ; writing a=b=2k+1 would accidentally assume equal inputs. Transfer: prove a−b is even. A proof of this arithmetic identity does not establish that a fixed-width addition instruction avoids overflow.

Preimage preserves an intersection

For f:A→B and U,V⊆B, choose arbitrary x∈A. Then x∈f⁻¹(U∩V) iff f(x)∈U∩V, iff f(x)∈U and f(x)∈V, iff x∈f⁻¹(U)∩f⁻¹(V). This chain proves both inclusions. No injectivity assumption is used. Transfer: try the analogous image statement; the collision f(−1)=f(1) for squaring explains why it can fail.

From a definition to a counterexample certificate

Transitivity means every x,y,z satisfy (xRy and yRz) implies xRz. Its negation is the existence of x,y,z with xRy, yRz and not xRz. For R={(0,1),(1,2)} on {0,1,2}, the triple (0,1,2) is a complete failure certificate. The pair (0,2) alone is insufficient: the missing conclusion must be connected to true premises. Transfer: add (0,2). The result is transitive but still not reflexive.

A recursive equation becomes a proof

For a full binary tree, define I(leaf)=0 and I(node(l,r))=1+I(l)+I(r). Define L(leaf)=1 and L(node(l,r))=L(l)+L(r). The leaf satisfies L=I+1. Assuming the identity for both children gives L(node)=(I(l)+1)+(I(r)+1)=I(node)+1. The grammar has no other constructors. Transfer: add a unary constructor and identify exactly which algebraic step fails. See practice feedback for the corrected identity.