Coding Truth and Satisfaction

I just got back from a week visiting the Canada/USA Mathcamp, where I spent a few days teaching a class on Gödel’s theorems. I only got to the incompleteness theorems on the last day, when I introduced Gödel numbering, showed that some syntactic relations were definable, suggested that provability was therefore definable, and showed that truth (in the standard interpretation) is not definable. Thus, I didn’t get to anything like the full incompleteness theorems, but just showed that there is no recursive set of axioms such that truth in the standard interpretation corresponds to provability from those axioms.

The thing about showing that truth is not definable is that you normally go through satisfaction instead. Given the fact that syntactic relations are definable, we can define functions (which returns the code number for the numeral expressing ) and (which takes as the code of a formula with one free variable, and substitutes in the term that is the code of, and returns the code of the resulting sentence). Then (which says that is the code of a formula satisfied by number ) can be defined in terms of by .

Then, it’s fairly straightforward to show that is not definable. If it were, then we could define , which would have some code number . But then would be true iff didn’t satisfy , which is a contradiction. Therefore, is not definable.

Afterwards, someone pointed out that this proof of the undefinability of doesn’t make any assumption about how the coding works, which seems somewhat surprising. After all, I could take highly non-effective codings, and the undefinability of would still hold. This is surprising, because can be defined under certain encodings. One such encoding is just to separate the sentences into true and false ones, and code them respectively by even and odd numbers, using some sort of lexicographic ordering. Then, since being even and being odd are both definable, truth would be definable as well. But it turns out that no trick like this is going to let satisfaction be definable, because of the diagonalization argument I gave above.

My guess for why this is is because satisfaction requires something like a coding of some of the syntactic structure as well as some of the semantic structure. Standard codings make the syntax definable, but then the semantics fails. Certain bizarre codings let the semantics be definable, but they make the syntax fail. But since the syntax and semantics aren’t recursive in terms of each other, there’s no way to make them both recursive, the way satisfaction seems to require. (Of course, you could probably choose some awful coding that makes both sets of relations undefinable, but why would you want to do that?)

Anyway, going back to camp is always great for precisely this sort of reason – I get to try to teach something new and interesting that I haven’t taught before, and people ask questions that also help me understand the material in a new way.

Advertisements

Back from Australia

I’m back from spending three weeks in Australia again – as usual, it was a very productive trip. It was also nice to get to attend the workshops on Norms and Analysis and Probability that went on last week. There were a lot of interesting talks there, so I won’t go through very many of them. Overall, I think the most interesting was Peter Railton’s talk in the first workshop, where he seemed to be supporting a framework for metaethics and reasons that is broadly compatible with the framework of decision theory. However, he brought in lots of empirical work in psychology to show that for both degree of belief and degree of desire, there seem to be two distinct systems at work – one more immediately regulating behavior, while the other being more responsive to feedback and generally regulating the first. It reminded me somewhat of what Daniel Kahneman was talking about in a lecture here at Berkeley a few months ago. But not being an expert in any of this stuff, I can’t say too much more than that.

Another particularly thought-provoking talk was Roy Sorensen’s in the Norms and Analysis workshop. He presented a situation in which you are the detective in a library. You just saw Tom steal a book, so you know that he’s guilty. However, before you punish him, the defense presents an envelope that may either contain nothing, or may contain exculpatory evidence (something like, “Tom has an identical twin brother in town”, or “The librarians have done a count and it seems that no books are missing”, which would make you give up your belief that Tom was guilty). Given that you know Tom is guilty, should you open the envelope or not? On the one hand, it seems you should, because you should make maximally informed decisions. On the other hand, it seems you shouldn’t, because either the envelope contains nothing, or it contains information you know is misleading, and in either case it’s no good.

Sorensen was arguing that you shouldn’t open the envelope, but I don’t think he succeeded in convincing any of the audience. But I think the puzzle sheds interesting light on what it takes to know that evidence is misleading, and how apparent evidence or the lack thereof really plays out when you know other background facts about where the evidence is coming from.