In short, do you feel comfortable with the proof now?
> [...] divisors which in turn are either prime or have divisors etc. None of these divisors are an initial prime, because then they would also be divisors of p+1
Let me put it this way: I think I'd score 100% on an exam on this, but I don't "get" it.
The divisors of 18 are also divisors of 36, because 36 = 18 * 2. Could use a theorem here, that a divisor of a divisor (of x) is also a divisor (of x).
A way to put it: p+1 can't be divided by any initial primes; and, if we keep dividing divisors, we eventually can't divide any more, and that's the definition of prime (indivisible "atoms"!).
I like seeing the overall process as: each time you find a new prime, it could fill in a gap between primes in the list, or be greater than any of them. Or, be smaller than any of them:
3*5 +1 = 16 -> 2
\tangent
In contrast, the purpose of a proof is to convince me that it's true. Sure, if I accept the theorems, and I accept the proof given those theorems, then I accept the proof. But this means that in order to be convinced that the proof is true, I have to be convinced of all the levels.
The difference isn't code vs proof in themselves, but in their purpose. I demand a lot more of a proof!
\idea
You "run" the proof to check it; you can "step into" theorems (like a debugger or some theorem websites which hyperlink them), or collapse/hide them.
It would be set-based, and so fundamental in that sense. I'm not sure if it would actually create sets and operate like an algorithm on them; or if it would use theorems about sets. I think the latter is necessary for "proof", but it wouldn't be as convincing... Generating examples would be helpful, to show it "working". hmmm... some proofs work kind of "by example", but with variables. What makes it a "proof" is that it works for the full range of values needed. So emphasising that approach might help.
The language would enable you to divide up an issue into possibilities in various ways, and automatically check that each limb is addressed (this is the basis of proof to my mind: you divide up the issue, and show that this covers all possibilities; then handle each limb. e.g. the predicate "is prime" or not). You can nest divisions. Not far from pattern matching, as in ML/haskell.
The actual proof part would be chains of implies: given x, y is true. These can be theorems/libraries: in the stdlib, or a third-party library, or your own "app" (or, the language's built-in axioms and theorems). So you can't just magically go from one step to the next; you have to specify a theorem for that step (call it). Perhaps the most basic ones would be implicit (like implicit casts), to avoid too much tedium. You can then "step into" these calls, or collapse them. Actually, just defining a new theorem is a way to collapse it (debugger "step into", collapsable tree and hyperlinks are just UI choices - vim ^] is another way to navigate calls, conceptually expanding/collapsing).
A key convention here would be that it's not enough to be correct if it's a complex, confusing, tedious "spaghetti proof". You want clear proofs, that ideally formalize intuitive notions. You build libraries that might not be the most concise, but that give you theorems that "make sense" and are useful for building convincing proofs. Libraries can compete etc for the "best" formalisms.
That is: unlike mathematicians, we don't aim at brevity or elegance, but at being convincing, intuitive, easy to understand. Accessible to ordinary people - pop-proofs, like pop-science, pop-psychology, pop-art etc. And I wouldn't be doing this magnanimously, for the poor ignorant masses, but because I need it myself!
It wouldn't be doing anything very clever, just easing the cognitive burden of complex proofs:
record the detail (just document management alone is helpful); hide/reveal one part at a time; automatic checks; affordances whose existance guides you to sensible operations (e.g. divide it up; implies; implicit theorems). There's also the fundamental aid of helping you formally defining the problem in the first place... which can be hardest part of proving it.
\implementation
In a way this is bad, because you're having to explicitly type so much... in a regular program, you just call a function, and you don't need to show the returned result - it's hidden in the execution. We could do that here, but it would be less clear:
This unclear version would look like: a starting expression, then a sequence of transformation theorems/calls (specifying exactly how they're applied). You'd run it to see the sequence of expressions as it was transformed.
A problem is we'd have to specify tediously what we want. For example, given expression a and b and operator ->, it couldn't know whether we want a (or b) - or something else, because many things are implied. So the operations would to be very precise. Like, extract the first operand; extract the second operand. It's similar for trivial operations like commut/associate a and b and c - we must specify precisely which ones to permute. I guess we could have a "permute" rule that operates at a higher level (i.e. actually a theorem...); or even have an "operator" that specifies the operation via the result... so it's no longer really an operator, but a kind of declarative system that I first mentioned.
One option is some "live" editing environment, so we can get the result of the call automatically. A couple of problems: we might not want the literal result, but an implicitly transformed version (e.g. trivially, like re-ordered terms). We'd also have to specify exactly how the theorem was applied - this might be a problem anyway (if it's to be automated).
I'm thinking that the engine works out how to apply the theorem to transform the starting expression into the resulting expression... but that might be too hard; we may need to tell it exactly how to apply it (like positional arguments to a function).
But... I guess it might even be a good rule of thumb, that if we can't mechanically work out what the step is, it's too complex! And if the user really wants it as a single step, they can write a theorem, that breaks it down enough into smaller steps simple enough for the compiler to understand. That seems to serve our goal, of convincing... at least, in principle. It might be tedious in practice.
For implict theorems, it seems commutativity/associativity would be OK; maybe distributivity - but if a big change, might be hard to follow.
Inference: We might allow any theorem to be implicit, provided the engine can infer not just how to apply the theorem, but what the theorem actually is (i.e. find some way to justify the step). This is quickly heading towards an automatic theorem prover, at least for very simple proofs. A problem with this is that the step might be less clear - that is, although the engine can work it out, the user might not be able to. This could easily happen in practice, even if the engine isn't very clever, by it having a library of very advanced theorems that the user doesn't even know about (this might be partially mitigated in an active environment, where the engine suggests the theorem - like a tooltip, google suggest, autocompletion).
Two kinds of transform, equational (an equal expression) and implies (not equal, but some aspect of it e.g. a and b -> a)
The easy answer is for the user to only allow libraries that they've accepted.
I was thinking we might have an automatic check, that we never use a theorem which is stronger than the whole thing we're trying to prove - that is, which implies our whole proof). But that seems hard to check automatically (maybe undecidable in general).