Great post! For anyone reading this who isn’t familiar with model theory, by the way, the bit about
sentence G ⇔ P(‘G’)<1. Then
may not be obvious. That is, we want a sentence G which is true iff P(‘G’) < 1 is true. The fact that you can do this is a consequence of the diagonal lemma, which says that for any reasonable predicate ‘f’ in a sufficiently powerful language, you can find a sentence G such that G is true iff f(G) is true. Hence, defining f(x) := P(‘x’) < 1, the lemma gives us the existence of G such that G holds iff f(G) holds, ie, iff P(‘G’) < 1 as desired.
Mostly I bring this up because the diagonal lemma is among the most interesting results in early model theory. It has a simple statement and is how self-reference is constructed, which is what gives us the incompleteness theorems. If anyone is interested in getting in to model theory, looking up the proof and background for the proof would be a great place to start.
Great post! For anyone reading this who isn’t familiar with model theory, by the way, the bit about
may not be obvious. That is, we want a sentence G which is true iff P(‘G’) < 1 is true. The fact that you can do this is a consequence of the diagonal lemma, which says that for any reasonable predicate ‘f’ in a sufficiently powerful language, you can find a sentence G such that G is true iff f(G) is true. Hence, defining f(x) := P(‘x’) < 1, the lemma gives us the existence of G such that G holds iff f(G) holds, ie, iff P(‘G’) < 1 as desired.
Mostly I bring this up because the diagonal lemma is among the most interesting results in early model theory. It has a simple statement and is how self-reference is constructed, which is what gives us the incompleteness theorems. If anyone is interested in getting in to model theory, looking up the proof and background for the proof would be a great place to start.