Today, I’m going to give you a short, simple proof of Godel’s First Incompleteness Theorem — the one that says there are true statements in arithmetic that can’t be proven. The proof is due to Gregory Chaitin, and it is far far simpler than Godel’s original proof. A bright high-schooler can grasp it instantly. And it’s wonderfully concrete. At the end, we’ll have an infinite list of statements, all easy to understand, and none of them provable — but almost all of them true (though we won’t know which ones).
Author Archive for Steve Landsburg
This is a tale of three paradoxes and why they matter.
- First, the ancient Liar Paradox: “This sentence is false”. If this sentence is true, it must be false. If it’s false, it must be true.
- Next, the century-old Berry Paradox: Call a phrase “short” if it contains fewer than 13 words. The English language contains a finite number of words, and hence a finite number of short phrases. Hence there must be some natural numbers that can’t be described by any short phrase. Among these natural numbers, there must be a smallest. What is that natural number? Why, it’s the smallest natural number that can’t be described by any short phrase, of course. Except that this number is in fact described by the short phrase in boldface.
- Finally, the more modern Paradox of the Surprise Examination (or the Unexpected Hanging), which we discussed yesterday.
The paradoxes are slippery, because they are stated in the imprecise language of English. But each of them has inspired a precise mathematical counterpart that is central to a brilliant argument in mathematical logic.
If you’re the sort of person who reads this blog, you’re likely to be familiar with the paradox of the unexpected hanging, which has been floating around since 1943 but achieved popular notoriety around 1969 through the writing of Martin Gardner. But you’re less likely to be aware that the unexpected hanging plays a central role in a wonderful new piece of serious mathematics related to algorithmic complexity, Godel’s theorems, and the gap between truth and provability.
The unexpected hanging might as well be a surprise examination, and that’s the form in which I present this paradox to my students every year: In a class that meets every weekday morning, the professor announces that there will be an exam one day next week, but that students won’t know exactly which day until the exams are handed out.
The students, of course, immediately start trying to guess the day of the exam. One student (call him Bob) observes that the quiz can’t be on Friday — because if it is, the students will know that by Thursday afternoon. After all, if Monday, Tuesday, Wednesday and Thursday mornings have all passed by, only Friday remains. A Friday exam can’t be a surprise exam.
A more thoughtful student (call her Carol) observes that this means the quiz must be on one of Monday, Tuesday, Wednesday or Thursday — and that if it’s on Thursday, they’ll know that by Wednesday night. After all, Friday’s ruled out, so if Monday, Tuesday and Wednesday have passed by, then only Thursday remains. That rules out a surprise exam on Thursday.
Another student (call him Ted) observes that thanks to Bob and Carol, we know the exam must be on one of the first three days of the week — which means that if it’s not on Monday or Tuesday, it must be on Wednesday. Therefore if it’s on Wednesday, they’ll know this by Tuesday night. Scratch Wednesday from the list of possibilities.
Now Ted’s girlfriend Alice points out that the exam can’t be on Tuesday either. Whereupon Bob concludes that the exam must be on Monday. But wait a minute! Carol points out that if they know the exam will be on Monday, it can’t be a surprise. Therefore no surprise exam is possible.
The students, relieved, decide not to study. But they’re awfully surprised when they show up in class the following Tuesday and the professor hands out an exam.
Last weekend, while I was in Boston, my fellow aerial arts students put on a show!
I’d have been there if I could have. Thankfully, we live in an age of instant video, so I still get to see the highlights. Congratulations to Caitlin, Celeste, Chris, Erika, Jacki, Maddie, Maia, Mairi, and Maya for a job beautifully done. You can leave compliments for them here or at the YouTube page. Or both!
Here’s proof (which I’ve posted before) that I can do something similar. But maybe not quite as gracefully as some of these other people:
Yesterday I had the pleasure of attending a very good talk by Yale’s Gary Gorton on the origins of the financial crisis.
Gorton’s story is that this was a bank run, not substantially different from the bank runs that have always plagued capitalist economies. In this case, the run took place in the repo market, which is an unregulated (and largely unmonitored) industry roughly equal in size to the standard banking industry. The repo market serves large institutions (e.g. Fidelity Investments or state governments) with a lot of cash on hand that they want to stash in an interest-bearing account for a day or two. So Fidelity deposits, say, a half-billion dollars at, say, Bear Stearns, just as you might deposit five hundred dollars at your local bank. One difference, though, is that your account at your local bank is insured, whereas Fidelity’s account at Bear Stearns is not — so Fidelity, unlike you, demands collateral for its deposit. Bear Stearns complies by handing over a half-billion dollars worth of bonds, of which Fidelity takes physical possession. The next morning, Fidelity withdraws its money and returns the bonds.
The problem comes in when rumors begin to spread that some bonds might be riskier than they appear, and Fidelity starts to worry that maybe Bear Stearns is picking particularly risky bonds to hand over. Therefore Fidelity demands more than a half-billion in bonds to guarantee its half-billion dollar deposit. If there’s, say, a 10% discrepancy between the deposit and the collateral, we say that Bear Stearns has taken a half-billion dollar haircut.
Because Bear Stearns has a fixed quantity of bonds on hand, and because all of its depositors are demanding haircuts, Bear Stearns can now accept fewer deposits than before. This means that Bear Stearns has less cash on hand. This makes depositors even more worried about the security of their deposits, which means they demand larger haircuts. The effects snowball until Bear Stearns collapses. Like so:
|
Travel and other projects have kept me absent for a couple of weeks, but I’m hoping to be back on a regular blogging schedule very soon now. Meanwhile, here is the video of the Gosnell Lecture that I recently gave at the Rochester Institute of Technology, titled “More Sex is Safer Sex and Other Surprises”.
One of the surprises turned out to be that the audiovisual equipment didn’t work, so I didn’t get to show my prepared slides. But I think things went pretty well anyway.
Slightly higher quality video is here.
I’m off to Jamaica, where I’ll be giving two talks on the theory and practice of economics. Expect blog-silence for
the next few days at least.
Meanwhile: Given that I plan not to travel far from Kingston, what are the things that I must see and do?
Here is my op-ed on deficit reduction from this morning’s Wall Street Journal (subscription required). For those without subscriptions, the thrust (which won’t be new to long-time readers of this blog) is that raising taxes can’t convert fiscally irresponsible spending to fiscally responsible spending.
If your household is over budget, you can address that problem either by spending less or by earning more income. It is tempting to fall into the trap of thinking that by analogy, the government can address its budget problems either by spending less or by raising taxes. But the analogy fails because raising taxes is not like earning more income; it’s more like visiting the ATM.
The government is an agent of the taxpayers. Raising taxes to pay for government spending depletes our assets just as visiting the ATM to pay for household spending depletes our assets. That’s not at all like earning income, which adds to our assets.
So insofar as the supercommittee relies on tax increases to address issues of “fiscal irresponsibility”, it will have failed.
From Jonathan Gelbord, research associate in astrophysics at Penn State:
We always knew that Penn State football was like a religion. Now we know which religion.
I am filling out an online recommendation form for a student who is applying to graduate school at Berkeley. One of the questions is: “Rate the applicant in comparison to others you have known in a similar capacity.” My choices are:
(This is an actual screen capture from the actual form.)
Unless I select one of the options, I am unable to submit the form.
I find myself at a loss for snarky words. What ought to have been the title of this post?
This post is a first attempt to rank the efficiency of the Republican candidates’ tax plans, concentrating on six dimensions:
1) The tax rate on wages and/or consumption. A wage tax and a consumption tax are pretty much interchangeable; you can tax the money as it comes in or you can tax it as it goes out. So I’m treating this as one category. The “right” level for this tax depends on your forecasts for future government spending.
2,3,4,5 and 6) The tax rates on dividends, interest, capital gains, corporate incomes and estates. I believe these tax rates should all be zero. That is not a statement about how progressive the tax system should be. A wage tax and/or a consumption tax can be as progressive (or regressive) as you like. It is instead a statement that while all taxes discourage both work and risk-taking, capital taxes have the added disadvantage that the discourage saving. This simple intuition is confirmed by much of the public finance literature of the past 25 years. (Here is a good example.)
My personal preference is for a system substantially less progressive than the one we’ve got, but for purposes of this exercise I won’t penalize candidates whose preferences differ from mine. For the record, Romney, Huntsman and Santorum are the three who (as far as I can tell) want to maintain substantial progressivity, with Romney, uniquely among the candidates, preferring even more progressivity than we currently have.
Here, then, is a chart, with candidates ranked roughly in order of their willingness to exempt capital income from taxation. I prepared this chart with a few quick Google searches (this is a blog post, not a journal article) and it probably contains errors. I’ll be glad for (documentable) corrections and will update the chart as they come in. Asterisks refer to further explanations, which you’ll find below the fold.
If we care about efficiency, we’re looking for zeroes in the last five columns. On the face of it, Johnson is the clear winner. But Cain’s 9/9/9 plan has two arguments in its favor that don’t appear on this chart. First of all, people are a lot less likely to bother evading one of three 9% taxes than a single 23% tax; therefore we’d have a lot fewer evasion problems under Cain than under Johnson. Second, it’s pretty easy to imagine Congress raising a 23% tax to 24% or 25% or 26%, but it’s a little harder to break the psychological barrier of single-digit tax rates, so Cain’s 9/9/9 might be more politically stable than Johnson’s 23. Therefore I’m calling this a tie between Johnson and Cain.
But the top six are all pretty good, except maybe for Paul, who hasn’t revealed his key number. Santorum is bad, Romney is atrocious, and Bachmann (who, as far as I can tell, has not bothered to release a tax plan) is an enigma.
Some explanations:
Happy birthday to our 7 billionth fellow earthling, who, according to most estimates, is due to be born today.
Welcome to the earth. Congratulations on being born in the 21st century, where the odds are excellent that you’ll live a richer, more prosperous and more fulfilling life than almost any of the 100 billion or so who preceded you — and paved the way for your prosperity with their investments and their inventions. Would that there had been more of them.
As you go through life, you will almost assuredly contribute to the world’s stock of ideas, diversity and love in ways your parents never contemplated — which is why the rest of us are a little sad that you might be their last child.
There’s certainly such a thing as a population that’s too large. Nobody disputes that. The interesting question is: Given the incentives faced by parents, it the population size we actually get too large or too small? And there are good reasons to think it’s too small.
In fact, population growth is a lot like pollution in reverse. Polluters don’t care about the damage they impose on strangers, so they pollute too much. Parents and potential parents don’t care about they joy and prosperity their chidren bring to strangers, so they reproduce too little.
Here is my piece on the death tax in this morning’s Wall Street Journal (subscription probably required); viewers of this video will find the arguments eerily familiar.
Here’s the one passage the WSJ didn’t have room for; one day our children will look back in wonder on an age when the length of an argument was constrained by anything so archaic it could be measured in square inches:
I know you’ve heard it said that spending is good for the economy. That might be true during a recession, if you subscribe to a broadly Keynesian view of the world. But the death tax encourages overspending year in and year out, which is not a good thing no matter what your point of view.
By way of background: Obama says that Republicans favor dirtier air and water. Paul Ryan calls that a petty characterization of an honest policy disagreement. Paul Krugman says that some Republican policies would lead to dirtier air and water (presumably in exchange for some offsetting benefits) and Ryan ought to be man enough to say so.
This is a fair point, I think. There is nothing dishonorable about believing that under current regulations we overclean our air and water, and if that’s Ryan’s view he should own it. Though perhaps Ryan would prefer to respond — also fairly — that he and/or the GOP favors different kinds of regulation that might not leave the air and water dirtier after all.
In any event, Krugman can never be fair for long. Here he is complaining about Ryan’s rhetorical style and defending his own:
If I say that Paul Ryan’s mother was a hamster and his father smelt of elderberries, that’s ad hominem. If I say that his plan would hurt millions of people and that he’s not being honest about the numbers, that’s harsh, but not ad hominem.
And you really have to be somewhat awed when people who routinely accuse Obama of being a socialist get all weepy over him saying that eliminating protections against pollution would lead to more pollution.
Except that, you see, at least as far as I can tell (and do correct me if I’m wrong) Paul Ryan (whose “weepiness” is the primary subject of Krugman’s blogpost) has never accused Obama of being a socialist. So (unless I’m mistaken) what Krugman’s engaging in here is best characterized as neither harsh nor ad hominem but, well, lying.
Two points:
Your inability to construct a functional website does not fill me with confidence about your ability to fly me across the Atlantic Ocean.
Today is the 200th birthday of Evariste Galois, who did not live to celebrate his 21st, but found time in his short 20 years to develop a circle of ideas that permeate modern mathematics. We know of these ideas because Galois spent the night of May 30, 1832 scribbling them furiously in a letter to a friend, in advance of the fatal duel he would fight the following morning. According to the great mathematician Hermann Weyl, “This letter, if judged by the novelty and profundity of ideas it contains, is perhaps the most substantial piece of writing in the whole literature of mankind.”
(If this were a less serious post, I might suggest that this famous letter was the first example of a Galois Correspondence.)
Now, two centuries later, every first year graduate student in mathematics spends a semester studying Galois Theory, and many devote their subsequent careers to its extensions and applications. Many of the greatest achievements of modern mathematics (for example, the solution to Fermat’s Last Theorem) are, at their core, elucidations of Galois’s 200-year-old insight.
Herewith my remarks about the estate tax (with particular reference to its effects on the very rich, and why we should care) to Congressional staffers, presented a couple of days ago under the auspices of the American Family Business Institute. Here is higher quality video. Here is the even higher quality YouTube version. Here is video of the entire event. I particularly recommend the first talk, by Stephen Entin.
Note that all of my remarks apply equally well to all forms of capital taxation. Entin did a better job of focusing on the particular shortcomings of the estate tax.
With a hat tip to our occasional commenter Ron….
Remember those faster-than-light neutrinos? The ones that threatened to overturn relativity, and along with it everything we think we know about how the universe works?
Well, it turns out that maybe they weren’t faster than light after all — they might have only appeared to be faster than light because their arrival time was mismeasured. The mismeasurement was (it seems) caused by the researchers’ failure to account for the effects of ….. relativity!
I hear an echo of the great ongoing debate between Einstein and Bohr on the foundations of quantum mechanics. Continue reading ‘Relatively Speaking’
So Mitt Romney wants to exempt capital gains from taxation — but only for taxpayers who earn less than $200,000 a year. In Tuesday night’s debate, Newt Gingrich asked him (I’m paraphrasing) “Why the cap?”. Romney’s answer — that he’s looking out for the middle class because “the rich can take care of themselves” — was as incoherent as anything I’ve heard this election year.
Here’s why:
I interpret Romney’s answer to mean that he wants to cut capital gains rates not on efficiency grounds, not on supply side grounds, and not on philosophical grounds, but on redistributionist grounds. Well, okay, I myself don’t think very much of redistribution as a primary driver of tax policy, but Romney and I can disagree on that one. But where the incoherence comes in is this: If your goal is to redistribute from the rich to the middle class, why on earth would you do it by cutting the capital gains tax, as opposed to lowering income tax rates in the middle and raising them at the top?
To put this another way: If you care about efficiency, you’ll want to cut the capital gains rate to zero for everyone. If you care about fairness, and if you believe fairness mitigates against double/triple/quadruple taxation, you’ll still want to cut the capital gains rate to zero for everyone. If you care about redistribution, you’ll want to juggle the tax brackets. But I can’t think of a single thing you could care about that would lead you to laser in on cutting capital gains rates for middle income taxpayers only.
Now it might be that somewhere in Romney’s 59 point economic plan there’s an answer to this. If so, Herman Cain was surely right when he intimated that Romney himself can’t be terribly familiar with the contents of that plan. Because, when asked a simple question about the justification, Romney wasn’t able to come anywhere close to making sense.
The IS-LM model is the simplest version of the “old Keynesian” approach to macroeconomics. You don’t hear much about IS-LM in the research literature these days, but it’s been coming up a lot on the blogs. Tyler Cowen tells us what he doesn’t like about the model; Brad DeLong and Paul Krugman rise to its defense; Stephen Williamson takes up the gauntlet, and Scott Sumner weighs in.
None of them, in my opinion, has touched the main issue, which is that IS-LM provides absolutely no framework for policy analysis because it makes no assumptions, and draws no conclusions, about what people are trying to accomplish. If you don’t know what people are trying to do, you can’t possibly know how best to help them.
Suppose, for example, that, as Paul Krugman believes, the current state of the economy is being driven by a “liquidity trap”, which means that people are hoarding money instead of spending it, and therefore consuming less, which is why employment is so low. Two weeks ago on this blog, I posed the following question to the IS-LMers:
Why aren’t you thrilled with the current state of the economy? … Why, as the stock of money continues to grow, shouldn’t the joy of hoarding eventually compensate for the annoyance of not having food on the table?
The IS-LM model provides no answer to that question. A model that can’t decide whether the current US economy is in a state of Nirvana is not a useful model for policy evaluation.
Continue reading ‘IS-LMic Extremism (With a Postscript on the Nobel Prize)’
Incidentally, Paul Krugman made an incisive point last week when he wrote:
Here’s a question I haven’t seen asked: If fear of future regulations and taxes is holding business back, as everyone on the right asserts, why didn’t the Republican victory in the midterms set off a surge in employment?
After all, if you really believed that fears of Obamanite socialism were the key factor depressing employment, the GOP victory — with the clear possibility that the party will take the Senate and maybe the White House next year — should greatly reduce those fears. So, where’s the hiring surge?
I even set out to write a blogpost citing this argument with approval — but around the time I was composing it, Krugman followed up with this bit of idiocy, to which a response seemed more urgent.
Now that that’s out of the way, I can come back to the bit about the missing Boehner Boom. It’s a more-than-fair question. How would you respond to it?
Last week, the highly distinguished Princeton Professor Ed Nelson announced a proof that the Peano axioms for arithmetic are inconsistent — and hence so is arithmetic itself. If true, this would be much bigger news than faster-than-light neutrinos. It would be bigger news than a discovery that the South had won the American Civil War. It would be far, far bigger news than a discovery that all life on Earth was intelligently designed.
There are, after all, multiple proofs that Peano Arithmetic (that is, the fragment of arithmetic described by the Peano axioms) is consistent. Among those, the simplest and most convincing (to the overwhelming majority of mathematicians) is this: The axioms of Peano Arithmetic, and therefore the theorems of Peano Arithmetic, are all true statements about the natural numbers — and a set of true statements cannot contradict itself.
Ed Nelson rejects that argument because (exempting himself from that overwhelming majority) he doesn’t believe in the set of natural numbers — or perhaps even in individual numbers when those numbers are very large. (How do you know that 810000 exists? Have you ever counted to it?)
Paul Krugman’s latest venture into self-parody starts with a recent paper on the cost of air pollution, which finds that said costs are big and heavily concentrated in a few industries. Krugman then links to a New York Times article surveying Rick Perry’s past clashes with the EPA. With no further argument, he concludes that
Today’s American right doesn’t believe in externalities, or correcting market failures; it believes that there are no market failures, that capitalism unregulated is always right. Faced with evidence that market prices are in fact wrong, they simply attack the science.
Where to begin?
MathOverflow turns two years old this week — a milestone in the transformation of mathematical research into a massively collaborative endeavor. It’s happening on blogs, it’s happening on mailing lists, and it’s happening in a big way on MathOverlow, where mathematicians ask and answer the sorts of questions that might come up in the faculty lounge — if the faculty lounge were populated by hundreds of experts pooling their expertise.
If you’re interested in mathematics at the research level, MathOverflow is a place to learn something new and fascinating every single day. (If you are not doing mathematics at a research level, feel free to read but please don’t feel free to join the fray; questions at anything below about a second-year graduate level should be directed to MathStackExchange, another massively collaborative site aimed, roughly, at the college level — which reminds me that it’s not just mathematical research, but also mathematical education, that is being revolutionized before our eyes.)
Well, it took embarrassingly long for me to see this but there’s really a very simple resolution to the quandary I posted Monday. The key point is this:
In a flexible price world, anybody can supply money at a social cost of zero. In a fixed price world, only the government can.
To be more precise: I currently hold $11. Suppose I agree to hold a twelfth. In a flexible-price world, I can get this dollar from the government (which prints it up at zero cost) or I can get it from my friend Jeeter, whereupon the price level adjusts and the rest of the world’s real balances (including Jeter’s) are restored to their original level. No social cost either way. In a fixed-price world, I can get this dollar from the government (which prints it up at zero cost) or I can get it from my friend Jeeter, whereupon prices don’t move and the rest of the world’s real balances are reduced. Zero social cost one way, positive social cost the other way.
Last week I blogged about my perplexity regarding the Keynesian notion of a liquidity trap.
In thinking about this harder, I’ve come to realize that a good part of my confusion has nothing to do with liquidity traps. It comes down to a very specific question about sticky-price models in general.
I expect this discussion will be interesting only to the most wonkish of my readers. The non-wonkish are invited to ask for clarifications, but please don’t jump in claiming to have “definitive” answers unless you’ve got a good grasp of the basics. I’d like to keep this discussion on track, and I’d like to learn something from it. Uninformed noise will be counterproductive.
For what it’s worth, I’ve discussed this offline, at considerable length, with several very good macroeconomists who eventually pronounced themselves as confused as I am. I really am hoping somebody with the right insight will pop up here and set us all straight.
Scientists at CERN have found apparent evidence that neutrinos can travel faster than light.
Suppose that tomorrow historians at Harvard find apparent evidence that the South won the American Civil War — not in some metaphorical “they accomplished their goals” sense, but in the literal sense that it was actually Grant who handed his sword to Lee at Appomatox and not the other way around.
Question: Of which conclusion would you be more skeptical?
Of course your answer might depend on exactly what this new “apparent evidence” consists of. So let me reword: As of this moment, which do you think is more likely — that neutrinos can travel faster than light, or that the South won the Civil War?