Notes from second meeting
Answer to exercise "What's the sentence you get from the diagonal lemma, L iff 'L has length less-than-or-equal-to 1000'?": len("replace('len(x) <= 1000", 'x' -> "replace('len(x) <= 1000', 'x' -> x)")") <= 1000. I think.
We went through the Smullyan paper and got up to the moment before "The Stability Predicament". The point of the paper turns out to be "if we interpret the box modality as 'belief', then a bunch of English sentences sound weird". The real moral of the paper is that it's awfully hard to be a knight or a knave on a knights-and-knaves island! (Making any statement about my beliefs involves extrapolating my entire future mind-state, for example, so only an extremely powerful knight or knave can make such a statement.) A bunch of the paper only requires that the reasoner believe the island to be a knight-knave island, but the reasoner is thereby making an extremely strong assumption.
Brief aside where I got confused about whether a symmetry argument meant we could never distinguish between knights and knaves: of course we can, because a knight can prove knighthood by saying "0 = 0".
After some thought, we eventually decided that Smullyan's "you will never believe I'm a knight" is equally well served by "you will eventually believe I'm a knave", although this wasn't obvious. The former is a statement about all of time; the latter is a statement only about an instant in time. The reasoner is assumed to never believe a false statement, though, so in fact once they believe something, it must be true.
General consensus that the notation of "type 1/2/3/4" is deeply annoying. I consistently refer to Type 1 as "deductively closed", and then types 2/3/4 are precisely adding one each of the Hilbert-Bernays properties.
Question about what the semantics are, if "belief" (= proof) is the syntax. Answer which I was mostly satisfied with at the time: we've got a sequence of statements from numbered knight-or-knaves, and then we freeze the world and get to reason about which speaker has what property, eventually assigning them a boolean "is-knight" label.
Identification of typo in paper: p348 "if there is a proposition q such that he believes q~(Bq implies q), then he will believe p"; that should read "… q~(Bq implies p)…".
Considerable confusion about why the self-fulfilling belief required the presence of a knight-or-knave at all, to say "If you ever believe I'm a knight, then the cure will work". Why couldn't the reasoner simply imagine this sentence to start off with? Answer: actually a later section makes explicit the condition under which the reasoner can imagine this sentence and hence perform all the reasoning of this sentence without a knight-or-knave: this is the "reflexive" property, that for every p there is q such that the reasoner believes q = (Bq implies p). This is of course true of PA, but that's a heavy-duty fact that requires the diagonal lemma or an extremely inspired quine.
We stopped before section 5 due to lack of time, but I at least had a lot of fun, and our waiter said it sounded very interesting!
Homework:
- We weren't instantly convinced about the Remarks after "Reflexive Reasoners". It was not at all obvious to me that statements 2, 3, or 4 in fact would have kicked off the Löb reasoning (that is, that they are suitable as Löb sentences). Prove that they do in fact work!
- What is the status of all of this stuff if you reject excluded middle? A whole lot of stuff concludes "not A, or not-not-A", and deduces "not A, or A". Does Löb's theorem even hold without LEM, for example? (Not at all obvious to me that it should! How could I magic up a member of A given only an interpretation function SyntaxTree(A) -> A?)
Interesting tidbits:
- PA (if consistent) can never prove any statement to be unprovable! Indeed, if PA proves "provable(A) -> False", then by explosion, PA proves "provable(A) -> A", and hence by Löb PA proves A. Hence by one of the Hilbert-Bernays rules, PA proves provable(A), and hence PA proves False by modus ponens. So, for example, PA can't even prove "not(provable(0=1))"! Though it can prove "provable(not(0=1))". Which is very weird, and I still feel like we must have made some mistake!
Notes from first meeting
Summary: we haven't actually got to the meat of Löb's theorem yet.
We went over:
- first-order logic
- enough model theory to observe that "truth" is a property of a sentence applied to a model, whereas "provability" is a property of a sentence applied to a theory
- mentioned Gödel's completeness theorem (that "provable" = "true in all models")
- mentioned the Löwenheim-Skolem theorems which guarantee that there are nonstandard models of Peano arithmetic (in fact, nonstandard models of arbitrarily large cardinality), and handwaved what the smallest [countable] nonstandard model looks like (but my memory is very poor on this, and I might have got that model wrong)
- observed that Gödel's [first] incompleteness theorem can be sloppily stated as "there is a sentence S which is true but not provable" (or more precisely, there are models of Peano arithmetic in which S evaluates to false, but in the standard model \mathbb{N} S evaluates to true)
- observed the diagonal lemma, and disagreed on whether it's obvious; I believe it's extremely nonobvious and indeed mind-bending and it took me several hours to reliably be able to write a quine, but perhaps I simply haven't read Gödel, Escher, Bach recently enough.
Assuming the existence of an "is-provable" operation which can be coded up with primitive-recursive functions on the naturals and which satisfies three particular axiom [schema]s (the Hilbert-Bernays provability conditions, though I didn't give them that name), we observed that the proof Yudkowsky gives in the Cartoon Guide is in fact correct, but we haven't yet talked about what it means. (I noted that I dislike the cartoon guide, because it's so… big.)
I also did a bit of fanboying about the Curry-Howard correspondence.
Interesting tidbits:
- I claimed that "there's only one axiom [schema] of first-order logic which makes the False symbol special, and that's the Law of Excluded Middle". Without LEM, no axiom schema mentions the symbol False, so the principle of explosion ("False implies everything") follows a rather curious path: induction on proofs. If you've got a proof whose final line is False, then you could perform exactly the same proof but instead replace all instances of False with some fixed but arbitrary A, and then at the end rather than proving False you've produced a proof of A. Once we add LEM, this reasoning no longer works, because it's no longer valid to substitute the occurrences of the symbol False within usages of LEM; so we need some other reason for explosion to be true. It follows from LEM thus: from False, deduce (A -> False) -> False, by "true things are implied by everything" (strictly, this is from the P -> (Q -> P) axiom schema). Then by LEM and modus ponens, conclude A.
- Homework: Yudkowsky explicitly stated the Löb sentence, a specific sentence L such that PA proves "L iff (Provable(L) implies P)". This sentence is what you get when you run the usual proof of a much more general theorem, the Diagonal Lemma, on the syntactic manipulation "turn L into the statement 'Provable(L) implies P'". Exercise: perform the diagonal lemma ("quining") construction on the syntactic manipulation "turn L into the statement 'len(L) <= 1000'". Note that the number 1000 is very long - more than 1000 characters long, it's SSSSS…SSS0 - so we expect this construction to result in a false L (by contrast with the use in Löb's theorem, where it results in an L that is true under the Löb hypothesis). I haven't yet done this, and it might be rather hard, I don't know!
I am just about to put up my notes from the first session and to announce the next one! I'm intending Friday 23rd, again at Notes Trafalgar Square, 7pm.
I organised the first one at too short notice, so there were just two of us there, but there are several more people with "yes but give me more notice" status. Since there were only two of us, we went over groundwork in advance of the theorem itself. Still plenty of time for people to come in at the beginning!
OK, I'm finally both not on holiday and not on the support rota at work.
Date and time of first meeting
Friday 16th August, 7pm. Location: Notes, St Martin's Lane (Trafalgar Square), should be open til 9pm. I'll have a crew cut and will be wearing a Doge t-shirt. If it all goes wrong, in an emergency we can go and have nibbles at Prezzo instead.
Agenda: don't know how far we'll get, but I ambitiously hope we can fully grok Löb's theorem itself by the end of this. You should first refresh your knowledge of first-order logic and Peano arithmetic if you need to.
An ideal venue would have whiteboards/blackboards, but I can't rustle one of those up completely trivially. (Sorry to the remote people and people who couldn't do Fridays.)
Bring writing implements and paper if you possibly can, and something to read the Internet with.
Once we're there we can make a WhatsApp group. If you're in the London Rationalish WhatsApp group, you already have my number in the meantime.
See https://doodle.com/meeting/participate/id/epXrAqme to vote for times and places! Hack: I'm using "midday" to mean "7-9pm, but remote rather than in person". I intend meetings to be weekly until we (I) run out of joy or things to talk about. Up front I'm leaning fairly strongly towards in-person (e.g. because I expect a bunch of shared whiteboarding stuff that I've always found a bit painful over e.g. Jamboard).
Post for people to register time zone preference. No guarantees that I won't end up just saying "urgh organisational tsouris is raising the activation energy too high, so this group is happening in-person in London after all", but if we do end up remote, I'll consider time zones in this thread!
I vote for a time compatible with the evening of London UK, or a time compatible with the afternoon on Sundays. I declare the cadence to be weekly by default.
By the way, as an extremely verbally-fluent nondyslexic person who was also an excellent choral singer, I can confirm the superpowers of singing versus talking. For example:
- I can recite some Maori, Zulu, and a bunch of Hebrew, with only a vague idea what it means (I'm sure I once knew), because of a singing it in a variety of songs. (And like many singers I can recite large tracts of Christian liturgy in Latin; in fact to recite it in English I usually have to translate on the fly from Latin.)
- I memorised about 140 digits of pi just by having Hard 'n' Phirm's Pi Song on in the background and singing it; it took less than a week and almost no effort, if I recall correctly (and however many digits of tau 6.2831853071795864769252867665590 is took literally no effort, that was lodged in my memory after maybe two listens of Vi Hart's Tau and I wasn't even trying).
- Similarly there were some tedious mathematical formulae (the line element for differentiating in spherical polar coordinates, for example) which I "drilled" into my head by making up some nonsense tune for them and then repeating it about three times.
Thoroughly underused technique for minimal effort parroting.
If you have the power to change the Google form, by the way, one of its questions is "What dose did you take (in mg)? 0.5, 1, 1.5, 2+"
Presumably this should read "(in g)", and it would also help if it were explicitly stated as being "per day".
1This isn't necessarily something you have to be tricked by a third party into. Be more Gwern! If there are two brands of cola you've not tried before, one stevia and one not, you can do a blinded trial by decanting them or similar. It'll certainly be easier with a third party, but one could do this solo.
Date and time of second meeting
Friday 23rd August, 7pm. Location: Notes, St Martin's Lane (Trafalgar Square), open til 9pm. I'll have a crew cut and will be wearing a Doge t-shirt.
Agenda: I'd like to understand Smullyan's paper about Löbian reasoning on the island where people either always tell the truth or always lie. See the previous session's notes for what we've done so far (I've summarised with a lot of jargon; I don't expect attendees to be fluent with jargon, so don't be too daunted by the summary.)
Bring writing implements and paper if you possibly can, and something to read the Internet with.
@Adam Newgas @LukasM @kapslock @philh