= 27d567bc2d48d9f40e9ccc20ea370b15)
Godel's Completeness and Incompleteness Theorems
Followup to: Standard and Nonstandard Numbers
So... last time you claimed that using first-order axioms to rule out the existence of nonstandard numbers - other chains of numbers besides the 'standard' numbers starting at 0 - was forever and truly impossible, even unto a superintelligence, no matter how clever the first-order logic used, even if you came up with an entirely different way of axiomatizing the numbers.
"Right."
How could you, in your finiteness, possibly know that?
"Have you heard of Godel's Incompleteness Theorem?"
Of course! Godel's Theorem says that for every consistent mathematical system, there are statements which are true within that system, which can't be proven within the system itself. Godel came up with a way to encode theorems and proofs as numbers, and wrote a purely numerical formula to detect whether a proof obeyed proper logical syntax. The basic trick was to use prime factorization to encode lists; for example, the ordered list <3, 7, 1, 4> could be uniquely encoded as:
23 * 37 * 51 * 74
And since prime factorizations are unique, and prime powers don't mix, you could inspect this single number, 210,039,480, and get the unique ordered list <3, 7, 1, 4> back out. From there, going to an encoding for logical formulas was easy; for example, you could use the 2 prefix for NOT and the 3 prefix for AND and get, for any formulas Φ and Ψ encoded by the numbers #Φ and #Ψ:
¬Φ = 22 * 3#Φ
Φ ∧ Ψ = 23 * 3#Φ * 5#Ψ
It was then possible, by dint of crazy amounts of work, for Godel to come up with a gigantic formula of Peano Arithmetic [](p, c) meaning, 'P encodes a valid logical proof using first-order Peano axioms of C', from which directly followed the formula []c, meaning, 'There exists a number P such that P encodes a proof of C' or just 'C is provable in Peano arithmetic.'
Godel then put in some further clever work to invent statements which referred to themselves, by having them contain sub-recipes that would reproduce the entire statement when manipulated by another formula.
And then Godel's Statement encodes the statement, 'There does not exist any number P such that P encodes a proof of (this statement) in Peano arithmetic' or in simpler terms 'I am not provable in Peano arithmetic'. If we assume first-order arithmetic is consistent and sound, then no proof of this statement within first-order arithmetic exists, which means the statement is true but can't be proven within the system. That's Godel's Theorem.
"Er... no."
No?
"No. I've heard rumors that Godel's Incompleteness Theorem is horribly misunderstood in your Everett branch. Have you heard of Godel's Completeness Theorem?"
Is that a thing?
"Yes! Godel's Completeness Theorem says that, for any collection of first-order statements, every semantic implication of those statements is syntactically provable within first-order logic. If something is a genuine implication of a collection of first-order statements - if it actually does follow, in the models pinned down by those statements - then you can prove it, within first-order logic, using only the syntactical rules of proof, from those axioms."
= 783df68a0f980790206b9ea87794c5b6)
Standard and Nonstandard Numbers
Followup to: Logical Pinpointing
"Oh! Hello. Back again?"
Yes, I've got another question. Earlier you said that you had to use second-order logic to define the numbers. But I'm pretty sure I've heard about something called 'first-order Peano arithmetic' which is also supposed to define the natural numbers. Going by the name, I doubt it has any 'second-order' axioms. Honestly, I'm not sure I understand this second-order business at all.
"Well, let's start by examining the following model:"
"This model has three properties that we would expect to be true of the standard numbers - 'Every number has a successor', 'If two numbers have the same successor they are the same number', and '0 is the only number which is not the successor of any number'. All three of these statements are true in this model, so in that sense it's quite numberlike -"
And yet this model clearly is not the numbers we are looking for, because it's got all these mysterious extra numbers like C and -2*. That C thing even loops around, which I certainly wouldn't expect any number to do. And then there's that infinite-in-both-directions chain which isn't corrected to anything else.
"Right, so, the difference between first-order logic and second-order logic is this: In first-order logic, we can get rid of the ABC - make a statement which rules out any model that has a loop of numbers like that. But we can't get rid of the infinite chain underneath it. In second-order logic we can get rid of the extra chain."
Logical Pinpointing
Followup to: Causal Reference, Proofs, Implications and Models
The fact that one apple added to one apple invariably gives two apples helps in the teaching of arithmetic, but has no bearing on the truth of the proposition that 1 + 1 = 2.
-- James R. Newman, The World of Mathematics
Previous meditation 1: If we can only meaningfully talk about parts of the universe that can be pinned down by chains of cause and effect, where do we find the fact that 2 + 2 = 4? Or did I just make a meaningless noise, there? Or if you claim that "2 + 2 = 4"isn't meaningful or true, then what alternate property does the sentence "2 + 2 = 4" have which makes it so much more useful than the sentence "2 + 2 = 3"?
Previous meditation 2: It has been claimed that logic and mathematics is the study of which conclusions follow from which premises. But when we say that 2 + 2 = 4, are we really just assuming that? It seems like 2 + 2 = 4 was true well before anyone was around to assume it, that two apples equalled two apples before there was anyone to count them, and that we couldn't make it 5 just by assuming differently.
Speaking conventional English, we'd say the sentence 2 + 2 = 4 is "true", and anyone who put down "false" instead on a math-test would be marked wrong by the schoolteacher (and not without justice).
But what can make such a belief true, what is the belief about, what is the truth-condition of the belief which can make it true or alternatively false? The sentence '2 + 2 = 4' is true if and only if... what?
In the previous post I asserted that the study of logic is the study of which conclusions follow from which premises; and that although this sort of inevitable implication is sometimes called "true", it could more specifically be called "valid", since checking for inevitability seems quite different from comparing a belief to our own universe. And you could claim, accordingly, that "2 + 2 = 4" is 'valid' because it is an inevitable implication of the axioms of Peano Arithmetic.
And yet thinking about 2 + 2 = 4 doesn't really feel that way. Figuring out facts about the natural numbers doesn't feel like the operation of making up assumptions and then deducing conclusions from them. It feels like the numbers are just out there, and the only point of making up the axioms of Peano Arithmetic was to allow mathematicians to talk about them. The Peano axioms might have been convenient for deducing a set of theorems like 2 + 2 = 4, but really all of those theorems were true about numbers to begin with. Just like "The sky is blue" is true about the sky, regardless of whether it follows from any particular assumptions.
So comparison-to-a-standard does seem to be at work, just as with physical truth... and yet this notion of 2 + 2 = 4 seems different from "stuff that makes stuff happen". Numbers don't occupy space or time, they don't arrive in any order of cause and effect, there are no events in numberland.
Meditation: What are we talking about when we talk about numbers? We can't navigate to them by following causal connections - so how do we get there from here?
Causal Diagrams and Causal Models
Suppose a general-population survey shows that people who exercise less, weigh more. You don't have any known direction of time in the data - you don't know which came first, the increased weight or the diminished exercise. And you didn't randomly assign half the population to exercise less; you just surveyed an existing population.
The statisticians who discovered causality were trying to find a way to distinguish, within survey data, the direction of cause and effect - whether, as common sense would have it, more obese people exercise less because they find physical activity less rewarding; or whether, as in the virtue theory of metabolism, lack of exercise actually causes weight gain due to divine punishment for the sin of sloth.
 |
vs. |
 |
The usual way to resolve this sort of question is by randomized intervention. If you randomly assign half your experimental subjects to exercise more, and afterward the increased-exercise group doesn't lose any weight compared to the control group [1], you could rule out causality from exercise to weight, and conclude that the correlation between weight and exercise is probably due to physical activity being less fun when you're overweight [3]. The question is whether you can get causal data without interventions.
For a long time, the conventional wisdom in philosophy was that this was impossible unless you knew the direction of time and knew which event had happened first. Among some philosophers of science, there was a belief that the "direction of causality" was a meaningless question, and that in the universe itself there were only correlations - that "cause and effect" was something unobservable and undefinable, that only unsophisticated non-statisticians believed in due to their lack of formal training:
"The law of causality, I believe, like much that passes muster among philosophers, is a relic of a bygone age, surviving, like the monarchy, only because it is erroneously supposed to do no harm." -- Bertrand Russell (he later changed his mind)
"Beyond such discarded fundamentals as 'matter' and 'force' lies still another fetish among the inscrutable arcana of modern science, namely, the category of cause and effect." -- Karl Pearson
The famous statistician Fisher, who was also a smoker, testified before Congress that the correlation between smoking and lung cancer couldn't prove that the former caused the latter. We have remnants of this type of reasoning in old-school "Correlation does not imply causation", without the now-standard appendix, "But it sure is a hint".
This skepticism was overturned by a surprisingly simple mathematical observation.
The bias shield
A friend asked me to get her Bill O'Reilly's new book Killing Lincoln for Christmas. I read its reviews on Amazon, and found several that said it wasn't as good as another book about the assassination, Blood on the Moon. This seemed like a believable conclusion to me. Killing Lincoln has no footnotes to document any of its claims, and is not in the Ford's Theatre national park service bookstore because the NPS decided it was too historically inaccurate to sell. Nearly 200 books have been written about the Lincoln assassination, including some by professional Lincoln scholars. So the odds seemed good that at least one of these was better than a book written by a TV talk show host.
But I was wrong. To many people, this was not a believable conclusion.
(This is not about the irrationality of Fox network fans. They are just a useful case study.)
[Link] A gentle video introduction to game theory
In this article I invite LessWrong users to learn the very basic math of something that is useful to both our community's goal of making better thinkers as well as many of the unrelated discussions that we often have here. I also present resources for further study to those interested. I made it based on the karma feedback given to this post in the monthly open thread.
Recently there has been a series of contributions made in main that serve more as introductory and logistic material than novel contributions. Because of this and because I hope It will grab more attention from newer members, I posted this in main rather than discussion section.
What is "game theory"?
Wikipedia's take: 
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others. More formally, it is "the study of mathematical models of conflict and cooperation between intelligent rational decision-makers." An alternative term suggested "as a more descriptive name for the discipline" is interactive decision theory.
LessWrongWiki's more succinct alternative:
Game theory attempts to mathematically capture behaviour in strategic situations, in which an individual's success in making choices depends on the choices of others.
From both definitions it should be clear how this relates to the art of refining human rationality. Besides the general admonition that rationalist should win, for us humans being the social animals that we are, there few things in our lives that do not depend at least partially on the choices of others. Game theory is extensively used in and connected to fields as disparate as economics, psychology, political science, logic, sports and evolutionary biology.
As many have argued before, it is an important part of the map of the real world:
Again and again, I’ve undergone the humbling experience of first lamenting how badly something sucks, then only much later having the crucial insight that its not sucking wouldn’t have been a Nash equilibrium.
You may not know it yet, but it is impossible to read this site for a extended period of time without running into concepts that are intimately tied to this field of study. Nash equilibrium, Pareto optimal, Prisoners Dilemma, non-zero sum, zero sum, the Decision theory talk that breaks out every now and then,...
You can take the concepts one at a time, reading up on a few lines from a dictionary like definition and trying to assimilate them without doing any of the connected mathematics. I wouldn't want to discourage you from that, its better than guessing! But this approach has its limitations, one risks misunderstanding something or even more subtly just failing to appreciate nuance and running into practical difficulties when trying to apply this knowledge in the real world. At the very least guessing the teachers password is a problem. Those of you that looked up these phrases and concepts on-line probably realized that they fit into a wider framework, a framework I hope you can now begin to explore with simple math, even if only with just a few tentative steps.
So what are the videos I should watch?
This fall (2011) there has been an ongoing class offered by two Stanford professors, Sebastian Thrun and Peter Norvig called "Introduction to Artificial intelligence". It has been talked about extensively on LW in several threads here, here and here. Many LWers have showed interest, quite a few signed up and several of us are now preparing for its final exam. Among the material covered is a introduction to game theory. I've been on live lectures about the subject and even watched some recorded ones and in comparison this is one of the better short introductions I've seen so far. I especially like how each of the videos is a self-contained unit just a few minutes in length. Instead of having to commit to watching a 40 or 60 minutes lecture, you just need to commit 2-5 minutes at a time.
The relevant Units of the material that cover this are 13. Games and 14. Game Theory. These units are presented by Peter Norvig. They are not recordings of a professor presenting something to a class in front of a blackboard, but rather aim towards the feeling of having a private tutor sitting down with you and explaining a few things with the help of a pen and a few pieces of paper (reminiscent of the style seen on Khan Academy). Currently you can still go directly to the site and view these videos logged in as a visitor (recommended). But just to avoid a trivial inconvenience and in case the youtube videos outlast the current state of the website I'm going to link directly to the youtube videos and write down any relevant comments and missing information as well. Unit 13 especially, assumes some previous knowledge you probably don't have, it deals primarily with complexity of games and how computationally demanding it is to find solutions. It can be useful for getting to know some terminology, but is otherwise skippable.
Don't worry. If you look up or feel you know what an agent or player is and what utility is, the missing exotic stuff (ala POMDPs) that isn't explained as you go along doesn't matter much for our purposes.
13. Games (optional)
- Introduction
- Technologies Question ? (Solution) [One choice per row]
- Games Question ? (Solution) [Multiple choice per row]
- Single Player Game
- Two Player Game
- Two Player Function
- Time Complexity Question ? (Solution)
- Space Complexity Question ? (Solution)
- Chess Question ? (Solution)
- Complexity Reduction Question ? (Solution)
- Review Question ? (Solution)
- Reduce B
- Reduce B Question ? (Solution)
- Reduce M
- Computing State Values
- Complexity Reduction Benefits
- Pacman Question ? (Solution)
- Chance
- Chance Question ? (Solution)
- Terminal State Question ? (Solution)
- Game Tree Question 1 ? (Solution)
- Game Tree Question 2 ? (Solution)
- Conclusion
14. Game Theory
- Introduction
- Dominant Strategy Question ? (Solution) [This is where you learn about the famous Prisoners dilemma!]
- Pareto Optimal Question ? (Solution) [rot13 after solving: Gur dhvm vapbeerpgyl vqragvsvrf bayl gur obggbz evtug bhgpbzr nf Cnergb bcgvzny, ohg obgu gur hccre evtug naq obggbz yrsg ner nyfb Cnergb bcgvzny. Va gur hccre evtug ab bgure bhgpbzr vf zber cersreerq ol O. Yvxrjvfr sbe gur ybjre yrsg ab bgure bhgpbzr vf zber cersreerq ol N.]
- Equilibrium Question ? (Solution)
- Game Console Question 1 ? (Solution)
- Game Console Question 2 ? (Solution)
- 2 Finger Morra
- Tree Question ? (Solution)
- Mixed Strategy
- Solving the Game
- Mixed Strategy Issues
- 2x2 Game Question 1 ? (Solution) [Please enter probabilities and not percentages.]
- 2x2 Game Question 2 ? (Solution)
- Geometric Interpretation
- Poker
- Game Theory Strategies
- Fed vs Politicians Question ? (Solution)
- Mechanism Design
- Auction Question ? (Solution)
At any point feel free to ask questions here in the comment section, I'm sure someone will gladly help you. Also the AI class reddit may be a good resource. Once you are done with the short series of lectures test your knowledge with these assignments.
- Max Min Question ? (Solution)
- Game Tree Question ? (Solution) [Unit 13 material. You should check children of pruned nodes as being pruned as well.]
- Strategy Question ? (Solution)
Note: I present this material in the form of a link to the video, followed by a "?" question mark if there is an answerable question that has a solution video posted. The link to the solution are posted as "(Solution)". Any additional comments made as corrections to the videos or some information that may be otherwise missing in this format, will be added in square brackets "[...]". I encourage people who are solving this via the links rather than the site to not watch the solutions straight away but first work out what they think the answer should be, don't worry if you get it wrong, sometimes the questions are unlikely to be answered correctly with the knowledge you have at that point, their role is to make you better remember and engage the material, not gauge your performance. The exception to this are the videos that come after Unit 14.
"I don't get it." or "It's not working." or "I didn't bother to watch more than a few."
First off for those who didn't for whatever reason like the lectures given here or find them dull or over your head, don't despair! If you feel you don't understand something, ask questions, I can guarantee that either me or someone else will answer it. To those of you who feel they are understanding the material but just don't like the videos or the lecturer, don't worry there are several other ways to approach the field. To just point you on your way here is a wide variety of quality alternatives, some of which may have approaches you prefer:
- Academic Earth site has several related classes, including an introductory one. They include additional non-video material.
- 2012 Game Theory online Stanford class (one of the many interesting classes inspired by "Introduction to AI")
I will keep this list updated and add any quality recommendations proposed by fellow LWers.
Unfortunately for those wanting just the introduction and most basic approach, many of these are more in depth and longer (this is also fortunate for those wanting a bit more). So if you just watch, comprehend and learn to use the information presented in the first lecture or two in one of these recommendations, you have done as much or more as someone who completed Unit 13 and 14. If you don't like video format in general and learn better from written material or live interaction... well this is mostly the wrong article for you. But I do present some additional non-video material in the next section you may find useful.
I watched the lectures and I think I understood them, where do I go from here?
Cool! Well check out some of the alternative videos and classes listed above, most of them are quite extensive. Try to complete one! If you'd like and try to take one ask around the comment section, maybe enough people would be interested to start a study group. Also MIT open course-ware has some material you may be interested even if you don't feel like doing the full classes.
A good AI textbook might be something you would like to explore. LessWrong has a great article with recommendations for a variety of textbooks for several interesting subjects (all recommendations must be made by people who've read at least two other titles on the subject)... but none for game theory. :/
In the thread Bgesop requested a recommendation:
Unfortunately it was the plea went unanswered. I'd love to just recommend you the textbook I first learned the subject from, but most readers are probably English speakers, so that's a no go. I'm not familiar with that many of them. I did skim Game Theory 2nd edition by Guillermo Owen, and it seemed ok. Hopefully me pointing this out will prompt someone to come up with a good recommendation. When they do I'll update this post accordingly, and lukeprog's great list can get another good textbook.
How to pick your categories
Note: this is intended to be a friendly math post, so apologies to anyone for whom this is all old hat. I'm deliberately staying elementary for the benefit of people who are new to the ideas. There are no proofs: this is long enough as it is.
Related: Where to Draw the Boundary, The Cluster Structure of Thingspace, Disguised Queries.
Here's a rather deep problem in philosophy: how do we come up with categories? What's the difference between a horror movie and a science fiction movie? Or the difference between a bird and a mammal? Are there such things as "natural kinds," or are all such ideas arbitrary?
We can frame this in a slightly more mathematical way as follows. Objects in real life (animals, moving pictures, etc.) are enormously complicated and have many features and properties. You can think of this as a very high dimensional space, one dimension for each property, and each object having a value corresponding to each property. A grayscale picture, for example, has a color value for each pixel. A text document has a count for every word (the word "flamingo" might have been used 7 times, for instance.) A multiple-choice questionnaire has an answer for each question. Each object is a point in a high-dimensional featurespace. To identify which objects are similar to each other, we want to identify how close points are in featurespace. For example, two pictures that only differ at one pixel should turn out to be similar.
We could then start to form categories if the objects form empirical clusters in featurespace. If some animals have wings and hollow bones and feathers, and some animals have none of those things but give milk and bear live young, it makes sense to distinguish birds from mammals. If empirical clusters actually exist, then there's nothing arbitrary about the choice of categories -- the categories are appropriate to the data!
There are a number of mathematical techniques for assigning categories; all of them are basically attacking the same problem, and in principle should all agree with each other and identify the "right" categories. But in practice they have different strengths and weaknesses, in computational efficiency, robustness to noise, and ability to classify accurately. This field is incredibly useful -- this is how computers do image and speech recognition, this is how natural language processing works, this is how they sequence your DNA. It also, I hope, will yield insights into how people think and perceive.
Clustering techniques
These techniques attempt to directly find clusters in observations. A common example is the K-means algorithm. The goal here is, given a set of observations x1...xn, to partition them into k sets so as to minimize the within-cluster sum of squared differences:
The role of mathematical truths
Related to: Math is subjunctively objective, How to convince me that 2+2=3
Elaboration of points I made in these comments: first, second
TL;DR Summary: Mathematical truths can be cashed out as combined claims about 1) the common conception of the rules of how numbers work, and 2) whether the rules imply a particular truth. This cashing-out keeps them purely about the physical world and eliminates the need to appeal to an immaterial realm, as some mathematicians feel a need to.
Background: "I am quite confident that the statement 2 + 3 = 5 is true; I am far less confident of what it means for a mathematical statement to be true." -- Eliezer Yudkowsky
This is the problem I will address here: how should a rationalist regard the status of mathematical truths? In doing so, I will present a unifying approach that, I contend, elegantly solves the following related problems:
- Eliminating the need for a non-physical, non-observable "Platonic" math realm.
- The issue of whether "math was true/existed even when people weren't around".
- Cashing out the meaning of isolated claims like "2+2=4".
- The issue of whether mathematical truths and math itself should count as being discovered or invented.
- Whether mathematical reasoning alone can tell you things about the universe.
- Showing what it would take to convince a rationalist that "2+2=3".
- How the words in math statements can be wrong.
Probability Space & Aumann Agreement
The first part of this post describes a way of interpreting the basic mathematics of Bayesianism. Eliezer already presented one such view at http://lesswrong.com/lw/hk/priors_as_mathematical_objects/, but I want to present another one that has been useful to me, and also show how this view is related to the standard formalism of probability theory and Bayesian updating, namely the probability space.
The second part of this post will build upon the first, and try to explain the math behind Aumann's agreement theorem. Hal Finney had suggested this earlier, and I'm taking on the task now because I recently went through the exercise of learning it, and could use a check of my understanding. The last part will give some of my current thoughts on Aumann agreement.
Rationality advice from Terry Tao
Via a link on IRC, I stumbled upon the blog of the mathematician Terry Tao. I noticed that several of his posts contain useful rationality advice, part of it overlapping with content that has been covered here. Most of the posts remind us of things that are kind of obvious, but I don't think that's necessarily a bad thing: we often need reminders of the things that are obvious.
Advance warning: the posts are pretty well interlinked, in Wikipedia/TVTropes fashion. I currently have 15 tabs open from the site.
Some posts of note:
Be sceptical of your own work. If you unexpectedly find a problem solving itself almost effortlessly, and you can’t quite see why, you should try to analyse your solution more sceptically. Most of the time, the process for solving a major problem is a lot more complex and time-consuming.
Use the wastebasket. Not every idea leads to a success, and not every first draft forms a good template for the final draft. Know when to start over from scratch, know when you should be persistent, and do keep copies around of even the failed attempts.
Learn the limitations of your tools. Knowing what your tools cannot do is just as important as knowing what they can do.
Learn and relearn your field. Simply learning the statement and proof of a problem doesn't guarantee understanding: you should test your understanding, using methods such as finding alternate proofs and trying to generalize the argument.
Write down what you've done. Write down sketches of any interesting arguments you come across - not necessarily at a publication level of quality, but detailed enough that you can forget about the details and reconstruct them later on.
= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
= f037147d6e6c911a85753b9abdedda8d){kind=logo}