Practise: How to Know a Claim Is True

The values run 41, 43, 47, 53 and so on, all prime through $n=39$. At $n=39$ the value is $1521+39+41=1601$, and no prime up to $\sqrt{1601}\approx 40$ divides it, so 1601 is prime. At $n=40$ the value is $1600+40+41=1681$, and $1681=41\times 41$. The smallest witness is therefore 40 and the factorisation is $41\times 41$. One failing case ends the universal claim, and the forty prime values below it do not survive as evidence for the claim.

Write the claim as $\forall L\exists TF(L,T)$, where $F$ says that learner $L$ fails on task $T$. Negate from the outside in. The first step gives $\exists L\neg \exists TF(L,T)$, and the second gives $\exists L\forall T\neg F(L,T)$. In words: there is a learner that succeeds on every task. That is option B. Option A is $\exists T\forall LF(L,T)$, the swapped reading that section 3.1 warns about; it is a stronger and different sentence. Option C is $\forall L\forall TF(L,T)$, which says more than the negation. Option D is $\forall T\exists L\neg F(L,T)$, which says less. A negation is mechanical, and the mechanics fixes which word moves first.

For each $n$ from 1 to 10, $n^2$ is even exactly when $n$ is even, because an odd number squares to an odd number. The five even values 2, 4, 6, 8 and 10 make the hypothesis true, and in each of those the conclusion also holds, so the checker records no failure. The five odd values 1, 3, 5, 7 and 9 make the hypothesis false, and a conditional with a false hypothesis is true without saying anything about its conclusion. Those five cases test nothing, the five remaining cases test the implication, and the ten cases together still say nothing about the whole numbers the claim covers. Section 3.2 makes the same point about a hypothesis that never holds: the claim is true and entirely empty.

Each of the five inputs chooses one of three outputs, so there are $3^5=243$ functions. A function that misses at least one output never lands on that output, so all five inputs choose among the other two: that gives $2^5=32$ functions for each missed output, and $3\times 32=96$ pairs of function and missed output. A function that lands on one output only misses two outputs, and it has been counted twice in the 96, so inclusion and exclusion adds back the $3$ constant functions once. The count is $243-96+3=150$. The check adds up: 3 constant functions miss two outputs, $3\times (32-2)=90$ miss exactly one, and $3+90+150=243$. None of the 243 is injective, because five inputs and three outputs force two arrows into one output.

A string of length 1 is one character: 2 strings. A string of length 2 is two independent choices: $2\times 2=4$. A string of length 3 is three independent choices: $2\times 2\times 2=8$. The three groups are disjoint because a string has exactly one length, so the total is $2+4+8=14$. Section 3.5 uses this count on an unbounded alphabet and unbounded length: list all strings of length one, then all of length two, then all of length three, and every program appears at some finite position. The same scheme gives 8 bit strings of length three, which is the section's opening count.

The diagonal reads bit 1 of row 1, which is 1; bit 2 of row 2, which is 0; bit 3 of row 3, which is 1; and bit 4 of row 4, which is 1. The diagonal is 1011, and flipping every bit gives 0100. Compare the result with each row: it differs from 1100 at position 1, from 1010 at position 2, from 0110 at position 3 and from 0001 at position 4. So it differs from row 3 at position 3, and it differs from every row somewhere. The construction uses the position of each row and never counts the rows, which is why it works on a list of any length, including a list with no end.

The announced constants are 1, 2, 4, 8, 16, 32, 64, 128, so the first value above 100 arrives after seven steps, $2^7=128$. Six steps give 64, which is still below the target. The arithmetic is correct at every line and the conclusion is false: the constant changed during the argument, so there was never a single $c$ that bounded every $2^n$. This is the fourth error of section 3.6, and the claim $2^n\le c$ for all $n$ is false for every fixed $c$.

The recurrence says the transfer of $n$ disks consists of moving the top $n-1$ disks aside, moving the largest disk once, and moving the top $n-1$ disks back: $2T(n-1)+1$. Iterating from $T(0)=0$ gives 0, 1, 3, 7, 15, 31, 63, 127, 255, 511 and 1023. The closed form $2^n-1$ agrees at every one of those steps, and section 3.3 proves the agreement by induction: the base case is $2^0-1=0$, and the step gives $2T(n-1)+1=2(2^{n-1}-1)+1=2^n-1$. The answer is $2^{10}-1=1023$. The eleven values computed by hand are a check on the algebra, not the proof of it.