Practice Solutions and Feedback

Open after an attempt. Equivalent valid proofs and alternative witnesses receive credit. These are explanations for P1–P20, not a substitute for writing your own.

P1–P5: Logic and proof construction

P1. ∀x∈Z ∃y∈Z: y>x is true by y=x+1. Its negation is ∃x∈Z ∀y∈Z: y≤x, false by the same construction. The swapped claim ∃y∈Z ∀x∈Z: y>x is false: choose x=y after the proposed y. Its negation is ∀y∈Z ∃x∈Z: y≤x, true by x=y. If both domains are empty, the first original claim is true and the second false. The first witness may depend on x; the swapped witness must be chosen before x.

P2. In row order FF, FT, TF, TT, implication has values T,T,F,T and its contrapositive has the same values. The converse differs on FT (and TF). There are two independent Boolean variables, each with two values: four rows cover the entire declared domain. This does not enumerate arbitrary integers.

P3. Write the odd integers as 2a+1 and 2b+1, with a,b integers. Their sum is 2(a+b+1), hence even. For the square claim, prove the contrapositive: if n=2k then n²=2(2k²), even. Every integer is exactly one of even or odd, so an odd square excludes even n and forces odd n.

P4. A proposed greatest integer m is contradicted by the larger integer m+1. No least-counterexample principle is needed. For the product, n=2k gives n(n+1)=2k(n+1); n=2k+1 gives n+1=2(k+1). Either way an integer factor of 2 is present. The parity cases cover all integers, including negatives and zero.

P5. a=0,b=1 disproves the conclusion b=0. Dividing by a requires a≠0; without it the correct conclusion over the integers/reals is a=0 or b=0. For requests, specify observed outputs, external effects, state and ordering. Read-only shared memory alone excludes neither external I/O nor time-dependent results. Under deterministic pure total functions on a fixed input snapshot, independent evaluations do not alter each other's inputs; their results can be associated with requests regardless of evaluation order. That is the narrower claim.

P6–P9: Sets and functions

P6. Let x belong to the left side. Then x∈A, x∉B and x∉C, so x belongs to both A∖B and A∖C. Conversely, membership in those two differences implies x∈A and x belongs to neither B nor C; hence x∈A∖(B∪C). Both inclusions hold. P(∅)={∅}; P({∅})={∅,{∅}}. The sets ∅ and {∅} have zero and one element.

P7. R→R squaring is neither injective (−1 and 1 collide) nor surjective (−1 has no real preimage). Restricted to nonnegative reals it is injective: equal squares give (x−y)(x+y)=0; either x=y or both are zero. It is onto by the nonnegative square root of each nonnegative output. The empty map to an empty codomain is bijective; to a nonempty codomain it is injective but not onto. There is no total map from a nonempty domain to the empty codomain.

P8. x is in f⁻¹(U∩V) iff f(x)∈U and f(x)∈V, iff x is in both preimages. For the example, f(S∩T)=∅ while f(S)∩f(T)={1}. The forward image inclusion always holds. For its reverse under injectivity, take y=f(s)=f(t), s∈S,t∈T. Injectivity gives s=t, hence y∈f(S∩T). For a particular pair, equality may hold without injectivity; equality for every pair characterizes it.

P9. If f(a)=f(b), applying g gives equal composite outputs. Composite injectivity yields a=b. But take A={0}, B={1,2}, C={9}, f(0)=1 and g(1)=g(2)=9: g∘f is injective while g is not. Composition needs every output in f(A) to lie in g's domain; matching the entire intermediate declared set is a convenient sufficient convention, not the only possible typing arrangement.

P10–P12: Relations, quotients and orders

P10. Reflexive: all three diagonals occur. Not symmetric: (1,2) lacks (2,1). Not antisymmetric: 0 and 1 relate both ways. Not transitive: 0R1 and 1R2 but not 0R2. S∘R={(1,3)} with middle witness 2; the reversed composition is not even typed on the declared three carriers.

P11. Reflexivity uses a−a=0=3·0. Symmetry negates the integer witness. Transitivity adds witnesses: if a−b=3j and b−c=3k then a−c=3(j+k). Every a lies in its own class. If two classes share x, symmetry/transitivity show each member of either belongs to the other; therefore they are equal. Classes are nonempty and cover Z, so the distinct classes partition Z. [a]↦a fails since [0]=[3] but 0≠3. The remainder rule is well-defined: integers differing by a multiple of 3 have the same remainder in {0,1,2}.

P12. Pairs: (2,2),(3,3),(6,6),(2,6),(3,6). Covers: (2,6),(3,6). Minimal: 2,3; maximal and greatest: 6; no least element. Neither 2 divides 3 nor 3 divides 2. Adding 1 adds its pairs to every element and makes it least; covers become (1,2),(1,3),(2,6),(3,6). The incomparable pair remains.

P13–P17: Induction and invariants

P13. Base n=0 gives 0=0². Assume the first n odd numbers sum to n². Adding the next, 2n+1, gives n²+2n+1=(n+1)². By induction the claim holds for all nonnegative integers. The hypothesis concerns n terms, not n+1 terms.

P14. Bases: 12=4·3, 13=4·2+5, 14=4+5·2, 15=5·3. For n≥16, n−4≥12 and n−4<n. By the strong hypothesis n−4=4a+5b; then n=4(a+1)+5b. Both coefficients remain nonnegative. A base only at 12 cannot initiate this step for 13,14,15.

P15. Suppose a counterexample exists and choose the least n≥2. It is not prime (otherwise n itself is a prime factor), so n=ab with 2≤a,b<n. By minimality a has a prime factor p; since p divides a and a divides n, p divides n, a contradiction. Halving a positive real yields an infinite decreasing sequence that stays positive; strict decrease alone is insufficient.

P16. A leaf has L=1,I=0,N=1. At a binary node, the two hypotheses give L=Lleft+Lright=(Ileft+1)+(Iright+1)=I+1. Also N=I+L=2L−1. A unary node above one leaf has L=1,I=1,N=2, refuting both original identities when I counts all internal nodes. With U unary and B binary nodes, induction gives L=B+1 and N=2L+U−1: a unary constructor adds one U and one N, no leaves.

P17. Use the prefix invariant and n−k measure in Proof and Model Contracts. A loop stopping before the last position fails on [1]: returns 0 instead of 1. Empty input alone does not expose that bug. If the list changes during iteration, the prefix/count and fixed-length assumptions need revision; the original proof no longer applies.

P18–P20: Executable evidence

P18. “0R1 and 1R2 but not 0R2” names a transitivity failure. Diagonal pairs on {0,1} are reflexive there, but the same pairs fail reflexivity on {0,1,2}. The carrier is part of the input contract.

P19. Empty-to-empty is bijective; all four empty-carrier relation properties are true; a zero-variable constant formula has one assignment, {}. A missing variable, a partial function graph, an out-of-carrier pair or a unary tree node is invalid input under this API. A valid nontransitive relation is valid input to the property reporter, but invalid input to the equivalence-class function.

P20. For reversed implication use P=false,Q=true. For antisymmetry versus asymmetry use a singleton diagonal (antisymmetric but not asymmetric). For a false least element use divisibility on {2,3,6}. For sharing, use leaf=('leaf',0); tree=('node',leaf,leaf): L=2,I=1,N=3 although only two distinct tuple objects are used. Your regression must fail on the fault and pass after repair.