Ken Binmore & Hyun Song Shin. Algorithmic knowledge and game theory. (Chapter 9 of Knowledge, Belief, and Strategic Interaction by Cristina Bicchieri.)
EDIT: Actually, I’d be pretty happy to see any paper containing both the phrases “common knowledge” and “Löb’s theorem”. This particular paper is probably not the only one.
Thank you.
Can you elaborate on this?
You are right that I used the inflammatory t-word because CooperateBot submitters are probably not trying to win. I certainly expected to see DefectBots (or CliqueBots from optimists), and agree that the competition should have been seeded with both CooperateBots and DefectBots.
But I don’t understand this at all:
But I find this a poor excuse. (It’s why I always give the maximum possible number whenever I play “guess 2/3rds of the average.”)
To me, this looks like t-wording the people who play 0.
Are we thinking of the same game, where the payout is constant?
I was a bit irritated that no fewer than three players submitted CooperateBot, as I cooperated with it in hopes of tricking bots like submission B.
EDIT: More offense was taken at my use of the word “trolls” than was intended.
Of course, when you ignore the payoff matrix, the argument is no longer really about the Prisoner’s Dilemma (and so I don’t know that it’s fair to accuse the barber paradox of having a lot of extra cruft not present in the PD formulation).
But I agree that this is a cute presentation of diagonal arguments in culturally relevant terms. A fun read.
I’m glad you bring this up. I have two comments:
(1) The absoluteness argument shows that intermediate uses of Choice don’t matter. They happen (definably) in L, and the conclusion reflects back up to V.
(2) As you suspect, you don’t really need Choice for compactness of the Hilbert cube. Given a sequence in it, I can define a convergent subsequence by repeatedly pigeonholing infinitely many points into finitely many holes. I believe sequential compactness is what is needed for the Kakutani theorem.
Variants of open cover compactness are derivable from sequential compactness without Choice in Polish spaces, in case something like that is needed. Or if you somehow really need full open cover compactness… well, return to point (1), I guess.
I gave this paper a pretty thorough read-through, and decided that the best way to really see what was going on would be to write it all down, expanding the most interesting arguments and collapsing others. This has been my main strategy for learning math for a while now, but I just decided recently that I ought to start a blog for this kind of thing. Although I wrote this post mainly for myself, it might be helpful for anyone else who’s interested in reading the paper.
Towards the end, I note that the result can be made “constructive”, in the sense of avoiding the Axiom of Choice by absoluteness arguments. Basically by Shoenfield’s absoluteness theorem, but I went through the argument by hand because I was not aware of that theorem until I went to Wikipedia to find something to link for absoluteness.
The computability problem is due to the unbounded ability of P to reason about theorems in the base theory (so that would be a necessary point of relaxation). A computable total function can’t even assign values > 1⁄2 to all the theorems of PA and values < 1⁄2 to all the sentences refuted by PA.
The set A is convex because the convex combination (t times one plus (1-t) times the other) of two coherent probability distributions remains a coherent probability distribution. This in turn is because the convex combination of two probability measures over a space of models (cf. definition 1) remains a probability distribution over the space of models.
I think, but am not sure, that your issue is looking at arbitrary points of [0,1]^{L’}, rather than the ones which correspond to probability measures.
Not only is PA not finitely axiomatizable, but any consistent extension of PA isn’t (I think this is true, the same proof that works for PA should go through here, but I haven’t checked the details)
Well if we had this, we would know immediately that Q + Con(PA) is not an extension of PA (which is what we originally wanted), because it certainly is finitely axiomatizable. I know there are several proofs that PA is not finitely axiomatizable, but I have not read any of them, so can’t comment on the strengthened statement, though it sounds true.
Ah, so my question was more along the line: does finite axiomatizability of a stronger (consistent) theory imply finite axiomatizability of the weaker theory? (This would of course imply Q + Con(PA) is not stronger than PA, Q being the usual symbol for Robinson arithmetic.)
On the model theoretic side, I think I can make something work, but it depends on distorting the specific definition of Con(PA) in a way that I’m not really happy about. In any case, I agree that your example is trivial to state and trivial to believe correct, but maybe it’s less trivial to prove correct.
Here’s what I was thinking:
Consider the predicate P(x) which says “if x != Sx, then x does not encode a PA-proof of 0=1”, and let ConMinus(PA) say for all x, P(x). Now, I think one could argue that ConMinus is a fair definition of (or substitute for?) Con, in that qualifying a formula with “if x != Sx” does not change its meaning in the standard model. Alternately, you could push this “if x != Sx” clause deeper, into basically every formula you would use to define the primitive recursive functions needed to talk about consistency in the first place, and you would not change the meanings of these formulas in the standard model. (I guess what I’m saying is that “the” formula asserting the consistency of PA is poorly specified.)
Also, PA is smart enough to prove that numbers are not their own successors, so PA believes in the equivalence of Con and ConMinus. In particular, PA does not prove ConMinus(PA), so PA is not stronger than Q + ConMinus(PA).
On the other hand, let M be the non-negative integers, together with one additional point omega. Put S(omega) = omega, put omega + anything = omega = anything + omega, and similarly for multiplication (except 0 * omega = omega * 0 = 0). I am pretty sure this is a model of Q.
Q is smart enough about its standard integers that it knows none of them encode PA-proofs of 0=1 (the “proves” predicate being Delta_0). Thus the model M satisfies Q + ConMinus(PA). But now we can see that Q + ConMinus(PA) is not stronger than PA, because PA proves “for all x, x is not equal to Sx”, yet this statement fails in a model of Q + ConMinus(PA).
EDIT: escape characters for *.
Your post confused me for a moment, because Robinson + Con(PA) is of course not weaker than PA. It proves Con(PA), and PA doesn’t.
I see now that your point is that Robinson arithmetic is sufficiently weak compared to PA that PA should not be weaker than Robinson + Con(PA). Is there an obvious proof of this?
(For example, if Robinson + Con(PA) proved all theorems of PA, would this contradict the fact that PA is not finitely axiomatizable?)
Since December, I’ve been persuing a “remedial computer science education”, for the sake of both well-roundedness and employability. My background is in the purest of pure math (Ph. Dropout from a well-ranked program), so I feel I can move fairly quickly here, though the territory is new.
My biggest milestone to date has been solving the first 100 Project Euler problems in Python (no omissions!). I had had a bit of Python experience before, and I picked 100 as the smallest number that sounded impressive (to me).
Second biggest milestone: following a course outline, I wrote an interpreter for a very limited subset of Scheme/Racket. This really helped de-mystify programming languages for me. (Although rather than learn OCaML like the course wanted, I just hacked it together in Python so that I could move on to a new project sooner.)
In the same vein, I’m currently reading and working through SICP, still using Racket. I’m in Chapter 3 of 5, though I’m often peeking ahead to Chapter 4 because it looks pretty exciting.
Of course, I won’t be a true LISP wizard without understanding macros, so the next (or concurrent) project is to go through the relevant Racket Docs tutorial.
I have some other likely future projects in mind, though I’m actually trying not to plan too far ahead lest it all appear more daunting.
Forcing myself through some C, to build character. This was explicitly recommended by a software engineer friend as a more “useful” way to spend my time than learning to LISP.
An algorithms course, possibly using this book
Registered.
From Kahneman’s Thinking, Fast and Slow (p 325):
The probability of a rare event is most likely to be overestimated when the alternative is not fully specified… [Researcher Craig Fox] asked [participants] to estimate the probability that each of the eight participating teams would win the playoff; the victory of each team in turn was the focal event.
… The result: the probability judgments generated sucessively for the eight teams added up to 240%!
Do you (r_claypool) have reason to suspect that Christianity is much more likely to be true than other, (almost-) mutually exclusive supernatural worldviews like, say, Old Norse Paganism? If not, then 5% for Christianity is absurdly high.
But orthonormal, your example displays hindsight bias rather than confirmation bias!
I interpret billswift’s comment to mean:
GlaDOS, you should not just seek confirmation of the legitimacy of the text; you should also seek refutation.
(Or possibly it was meant the other way around?)
In any case, I agree that billswift’s comment is off-base, because GLaDOS’ comment does not actually show confirmation bias.
I am currently reading Kahneman’s book, and about 100 pages in I realized I was going to cache a lot more of the information if I started mapping out some of the dependencies between ideas in a directed graph. Example: I’ve got an edge from {Substitution} to {Affect heuristic}, labeled with the reminder “How do I feel about it? vs. What do I think about it?”. My goal is not to write down everything I want to remember, rather to (1) provide just enough to jog my memory when I consult this graph in the future, and (2) force me to think critically about what I’m reading when deciding whether or not add more nodes and edges.
Grognor, I don’t think it’s fair to insinuate that you may have learned a wrong lesson here. If it’s wrong (I actually doubt that it is), then it’s up to you to try to resist learning it.
As regards walking readers into a trap to teach them lessons, one of my all-time favorite LW posts does exactly this, but is very forthcoming about it. By contrast, I think thomblake overestimates the absurdity of the examples here: I thought they seemed plausible, and that “Frodo Baggins” was just poor reasoning. The comments show I’m not alone here. This level of subtlety may be appropriate on April 1st, but by April 3rd, it’s dated. I would recommend editing in a final line after the conclusion but before the references indicating that this post was an April Fool’s joke.
I really, really dislike April Fool’s jokes like this. Somebody will stumble onto this post at a later date, read it quickly, and come away misinformed.
I’ll grant that the obviously horrible “Frodo Baggins” example should leave a bad taste in rationalists’ mouths, but a glance at the comments shows that several readers initially took the post seriously, even on April 1st.
Yes, and I agree with this. I’m familiar with Straw Vulcanism and accept that guessing incorrectly is my mistake, not others’.
It seems anger and frustration were read into my comment, when in fact I was merely surprised, so I’ve edited out the offending t-word.