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

Interested. Not in london.

Interested, but I can't make the proposed dates this week.

Hey, I would love to go, but only if it's in-person.

My personal experience is that trying to understand something in a group works a lot better in-person, plus I'd like to get to know more people in London.

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!