By way of contradiction May 5, 2013Posted by Ezra Resnick in Logic, Math.
An indirect proof (or proof by contradiction) establishes the truth of a proposition by showing that the proposition’s negation implies a contradiction. For example, we can indirectly prove that the square root of 2 is irrational (i.e., it cannot be expressed as a ratio a/b where a and b are integers) by assuming the opposite — that √2 can be expressed as a ratio of integers — and showing that such an assumption leads to a contradiction (e.g., that b is both even and odd).
Some people find indirect proofs unsatisfying, or even a bit suspicious: it feels like we’ve been cheated out of understanding why the proposition is true. Direct proofs seem more intuitive and dependable. This raises the question: Does every proposition that can be proved indirectly have a direct proof as well? Or are there propositions that can be proved indirectly, for which no direct proof exists?
Before attempting to answer that question, let us first consider this humble proposition:
(p) This proposition cannot be proved directly.
We can prove proposition p is true — indirectly. Start by assuming the opposite, that is, assume there exists a direct proof of p. In particular, that means p is true. But p states that there is no direct proof of p — contradicting our assumption. So our assumption must be false; hence p is true.
Let us now attempt to prove the following proposition:
(q) Not all propositions that can be proved indirectly can also be proved directly.
We shall prove the truth of proposition q (you guessed it) indirectly. Assume the opposite: that is, assume any proposition that can be proved indirectly can also be proved directly. Then, since p can be proved indirectly (as demonstrated above), there must also exist a direct proof of p. However, the existence of such a proof contradicts (the proven) proposition p! So our assumption must be false — and q is true.
Ah, but the question remains: Can q be proved directly?
Conflicting messages August 13, 2011Posted by Ezra Resnick in Language, Logic.
add a comment
I came across this somewhat paradoxical signpost in Cambridge, Massachusetts:
A logician in hell (the prequel) July 23, 2011Posted by Ezra Resnick in Logic.
add a comment
I was arrested for breaking the laws of logic — accused of poisoning a well (while also intending to drink from it). The trial was held in an old circus tent, before a random jury. The prosecutor delivered the following speech:
“Ladies and gentlemen of the jury: let me begin by pointing out that the defendant is extremely ugly.
“You should also know that I have been chief prosecutor for over 100 years, and am well-respected as a leading authority on all criminal matters.
“Believe me, therefore, when I tell you that the defendant’s guilt in this case is quite certain: not only does he have no alibi for the time of the crime, he has offered no alternative suspect whatsoever — claiming that he ‘doesn’t know’ who did it! Surely, such a shameless admission of abject ignorance speaks for itself.
“As if that weren’t enough, there is solid statistical evidence against the defendant as well: meticulous studies performed over many years have consistently shown that a majority of those indicted for similar crimes were, in fact, guilty. Moreover, the last five suspects we arrested turned out to be innocent, so for this defendant to be innocent as well would be unlikely in the extreme.
“Finally, I ask you to consider the consequences of finding the defendant not guilty. First of all, such an outcome would imply that those responsible for upholding the law around these parts are incompetent — and who among you would want to live in such a society? Additionally: be assured that if this case does not end in conviction, very soon we will be unable to convict any criminals at all, so that murderers and rapists will walk our streets with impunity.
“In conclusion, ladies and gentlemen of the jury: let me remind you that the defendant is really very ugly, and smells bad, too. Thank you for your attention.”
The jury applauded and the prosecutor took a bow. Just as I stood up to speak in my own defense, the jury left for lunch. Upon their return, it was announced that the jury had reached a decision: my guilt would be determined by the outcome of three sporting contests to be held between the prosecutor and myself.
In the first contest, each of us had to fight our way through an army of dummy soldiers. But while my dummies were made of iron, the prosecutor’s were made of straw. He finished first.
Next was an archery contest. I aimed carefully, and my arrow lodged only slightly below the center of the target. But when I looked over at my opponent’s attempt, I saw that he had shot at a blank wall — where a young boy was now quickly painting a target around his arrow.
For the final contest, we had to hit a ball between designated goalposts. The prosecutor succeeded with no trouble; but whenever I swung, the goalposts (which were actually flamingos) moved out of the ball’s way.
Back in court, I was asked if I had anything to say for myself; but all I could do was beg the question. Shortly thereafter, I was informed that I had been found guilty. I was sentenced to be hanged unexpectedly within the week…
If by whiskey July 17, 2011Posted by Ezra Resnick in Equality, Logic, Religion.
add a comment
Richard Elliot Friedman and Shawna Dolansky have written a book called The Bible Now, reviewed by Adam Kirsch for The New Republic:
They have set out to explain “what the Bible has to say about the major issues of our time,” in particular “five current controversial matters: homosexuality, abortion, women’s status, capital punishment, and the earth.”
What, for instance, does the Bible have to say about homosexuality? Leviticus (20:13) seems pretty clear: “And if a man lie with mankind, as with womankind, both of them have committed abomination: they shall surely be put to death: their blood shall be upon them.” Well, that’s what it says, but what does it really mean?
Friedman and Dolansky use [other ancient Near Eastern texts] to establish “the wider cultural context” of Leviticus, from which it follows that “what the authors of Leviticus … may be prohibiting is not homosexuality as we would construe the category today but, rather, an act that they understood to rob another man of his social status by feminizing him.” Why, then, does Leviticus, uniquely among ancient Near Eastern law codes, prescribe death for both partners in homosexual acts? Friedman and Dolansky argue, quoting another Bible scholar, that it is because Leviticus “emphasizes the equality of all. It does not have the class distinctions that are in the other cultures’ laws.”
This is a remarkable performance. Before you know it, a law that unambiguously prescribes death for gay men has been turned into an example of latent egalitarianism. Friedman and Dolansky imply that it was not homosexuality the Bible wanted to condemn, but the humiliation of the passive partner. And since we no longer think of consensual sex acts as humiliating, surely the logic of the Bible itself means that homosexuality is no longer culpable: “The prohibition in the Bible applies only so long as male homosexual acts are perceived to be offensive.”
But of course, one of the main reasons why people still perceive male homosexual acts as offensive is because the Bible declares them an abomination. Though I’m sure that will now change, as soon as “the wider cultural context” is more widely known…
Speaking of controversial matters: in 1952, Mississippi lawmaker Noah S. “Soggy” Sweat gave a speech on the floor of his state legislature, explicating his position on the prohibition of alcoholic beverages:
My friends, I had not intended to discuss this controversial subject at this particular time. However, I want you to know that I do not shun controversy. On the contrary, I will take a stand on any issue at any time, regardless of how fraught with controversy it might be. You have asked me how I feel about whiskey. All right, here is how I feel about whiskey:
If when you say whiskey you mean the devil’s brew, the poison scourge, the bloody monster, that defiles innocence, dethrones reason, destroys the home, creates misery and poverty, yea, literally takes the bread from the mouths of little children; if you mean the evil drink that topples the Christian man and woman from the pinnacle of righteous, gracious living into the bottomless pit of degradation, and despair, and shame and helplessness, and hopelessness, then certainly I am against it.
But, if when you say whiskey you mean the oil of conversation, the philosophic wine, the ale that is consumed when good fellows get together, that puts a song in their hearts and laughter on their lips, and the warm glow of contentment in their eyes; if you mean Christmas cheer; if you mean the stimulating drink that puts the spring in the old gentleman’s step on a frosty, crispy morning; if you mean the drink which enables a man to magnify his joy, and his happiness, and to forget, if only for a little while, life’s great tragedies, and heartaches, and sorrows; if you mean that drink, the sale of which pours into our treasuries untold millions of dollars, which are used to provide tender care for our little crippled children, our blind, our deaf, our dumb, our pitiful aged and infirm; to build highways and hospitals and schools, then certainly I am for it.
This is my stand. I will not retreat from it. I will not compromise.
(via Why Evolution is True)
A logician in hell June 14, 2011Posted by Ezra Resnick in Logic.
1 comment so far
The following is true.
I was arrested for breaking the laws of logic, and sentenced to be hanged unexpectedly within the week.
As I sat in my cell trying to reason my way out of my predicament, I saw the local executioner passing by. He looked like a logical fellow (and rather familiar), so I attempted to strike up a conversation: I asked whether he hanged all the condemned outlaws around these parts. “All those who don’t hang themselves,” he answered grimly. (I decided not to ask what would happen if he himself were sentenced to be hanged…)
I tried to bribe my way to freedom by offering the executioner a heap of gold coins; but he was not persuaded by my argument that zero coins constitute a heap.
Instead, he offered to set me free if I could guess the natural number he was thinking of. After an uncountable number of incorrect guesses, I gave up. (It turned out that he was thinking of the smallest natural number not definable in under eleven words.)
When the guards came (unexpectedly!) to take me to the gallows, I protested that I was insane and therefore unfit to be executed; but the executioner pointed out that insanity defenses are never accepted because anyone pleading for his own life must be sane.
As the rope was placed around my neck, I broke down and told the executioner that due to time travel gone wrong, I was actually his grandfather — so by killing me he would be undoing his own birth.
“I sure hope it works this time,” he said, and pulled the lever.
By the way, the first sentence of this post is false.
Yeti or square circle? March 18, 2011Posted by Ezra Resnick in Logic, Philosophy, Religion.
1 comment so far
Is evidence for the existence of God even possible? Biologist Jerry Coyne has published an email exchange with philosopher Anthony C. Grayling on this question. While both are atheists, Coyne maintains that the existence of God is an empirical question, and that it is conceivable (though highly unlikely) that convincing evidence for God might turn up some day. Grayling thinks not, because the very concept of God is incoherent:
on the standard definition of an infinite, omniscient, omnipotent, benevolent etc being — on inspection such a concept collapses into contradiction and absurdity; as omnipotent, god can eat himself for breakfast…as omniscient it knows the world it created will cause immense suffering through tsunamis and earthquakes, and therefore has willed that suffering, which contradicts the benevolence claim…etc etc…to say nothing of local suspension of the laws of nature for arbitrary reasons e.g. in answer to personal prayer, which makes a nonsense of the idea that the world or the deity is rationally comprehensible: and if either or both are non-rational then there is nothing to talk about anyway…
The point is that ‘god’ is not like ‘ether’ — it is not amenable to empirical investigation, and does not occupy a slot in some systematic framework of thinking about the world that might be improved on in the light of better theory or observation. It does no work because it purportedly does all work; like a contradiction it entails anything whatever; it is consistent with all evidence and none. These considerations constitute the proof that it is an empty concept. — If you treat the word ‘god’ as a name for a putative entity that might or might not exist and such that something might count as evidence for or against its existence, as you do, then you are committed to agnosticism about everything that can be given an apparent name. But ‘god’ is not like ‘yeti’ (which might — so to say: yet? — be found romping about the Himalayas), it is like ‘square circle’. Trying to explain to someone who thinks that ‘god’ is like ‘yeti’ (namely, you) let alone to someone who thinks ‘god’ is like ‘Barack Obama’ (names an actual being, as Christians and Muslims do) that it is actually not like ‘yeti’ but like ‘square circle’ and that nothing can count as evidence for square circles, is harder work for ‘god’ than ‘square circle’ only because religious folk have been squaring the circle for so long!
Coyne disagrees in principle:
I reject Anthony’s assertion that God is not amenable to empirical investigation, since one can empirically investigate claims about how God interacts with the world. The efficacy of prayer is one of these. I believe Grayling is referring here to a deistic god, since theistic gods need not be “consistent with all evidence.” The existence of earthquakes, for example, is not consistent with a benevolent theistic god. I still maintain that if one claims that a god interacts with the world in certain ways, then those claims can be investigated empirically. To me the existence of a deity is not a matter that can be ruled out by philosophy or logic from the get-go; it’s a matter for empirical observation and testing.
While I find this discussion interesting, I must admit that I don’t find it especially consequential. Even if the God concept can be made coherent, no remotely convincing evidence for the existence of a God has ever been offered, and there is no reason to expect it ever will (as Coyne would agree). The God hypothesis is dead. The existence of such an entity (certainly one that meets the description of any of our obviously man-made religions) is about as plausible as the existence of witches or the belief that suicide bombers really get 72 virgins in the afterlife.
Furthermore: religious people seem to think that if God does exist, then it’s obvious that we ought to obey his every command — but that doesn’t follow. Whether God is a yeti or a square circle, nothing can absolve us of the responsibility to think for ourselves, and to rationally decide how we ought to live our lives.
Cognitive misers November 7, 2010Posted by Ezra Resnick in Logic, Puzzles, Reason.
add a comment
Jack is looking at Anne, while Anne is looking at George. Jack is married, while George is not. Is there a married person looking at an unmarried person?
(a) Yes; (b) No; (c) It cannot be determined.
Make your choice before reading on.
According to psychologist Keith Stanovich (in an article by Kurt Kleiner), more than 80 percent of people answer this question incorrectly. It seems as though we need to know whether Anne is married; but a bit of further thought shows that it doesn’t matter. If she’s unmarried, then a married person (Jack) is looking at an unmarried person (Anne). And if she is married, then a married person (Anne) is looking at an unmarried person (George). So the answer is Yes in any case.
The solution is obvious once we think it through, so why did we get it wrong to begin with? According to Stanovich,
We are all “cognitive misers” who try to avoid thinking too much. This makes sense from an evolutionary point of view. Thinking is time-consuming, resource intensive and sometimes counterproductive. If the problem at hand is avoiding the charging sabre-toothed tiger, you don’t want to spend more than a split second deciding whether to jump into the river or climb a tree.
So we’ve developed a whole set of heuristics and biases to limit the amount of brainpower we bear on a problem. These techniques provide rough and ready answers that are right a lot of the time — but not always.
For the vast majority of decisions we face nowadays, it would clearly be better to spend a few more minutes thinking in order to avoid incorrect conclusions. To that end, it’s important to remember how our intuition can fail us, even in easy cases.
36 (bad) arguments for the existence of God August 12, 2010Posted by Ezra Resnick in Logic, Religion.
In the appendix to her novel 36 Arguments for the Existence of God, Rebecca Newberger Goldstein patiently rebuts all three dozen of them — from The Cosmological Argument to The Argument from the Abundance of Arguments. The fun part is identifying the various logical fallacies underlying the arguments — without a doubt, the best place to find logical fallacies is on the topic of God.
The most common fallacy is that of Using One Mystery to Explain Another (featured in The Cosmological Argument, The Argument from the Hard Problem of Consciousness, The Argument from the Improbable Self, The Argument from Free Will, and The Argument from Mathematical Reality). Unfortunately, merely proclaiming that “God did it!” when faced with a mysterious phenomenon does not dispel the mystery, and adds nothing to our understanding of the universe. Putting a label on something does not mean you have explained it. Such a non-explanation is actually worse than no explanation at all, because it causes people to think they know something that they really don’t (How does consciousness arise? God did it!) — so there’s no motivation for doing the hard work required to actually expand our knowledge.
A related fallacy is that of Arguing from Ignorance: reasoning that since we currently have no explanation for some puzzling phenomenon, it must be attributed to God. The classic example is The Argument from Design — before Darwin, no one could think of a way for complex creatures (such as ourselves) to have come about without a creator. God is still invoked as the default solution to some of today’s mysteries, as in The Argument from the Hard Problem of Consciousness and The Argument from Prodigious Genius. But just as the puzzle of biological complexity has been given a naturalistic solution, there is every reason to expect that we will one day have a much better understanding of many phenomena that now baffle us. In any case, the fact that we do not currently have a natural explanation for something doesn’t mean that there must be a supernatural one.
A slightly more subtle fallacy is that of Wishful Thinking. It’s amazing how many people think that since they wouldn’t want to live in a universe where their existence wasn’t part of some master plan (The Argument from the Intolerability of Insignificance), or where evil deeds go forever unpunished (The Argument from Perfect Justice), or where innocent people suffer for no purpose (The Argument from Suffering) — it somehow follows that the universe cannot be that way. The appropriate response: Grow up.
By the way, it’s important to notice that the vast majority of arguments for the existence of God do not deal with the specific God of any particular religion, and even those few that do (like The Argument from Miracles and The Argument from Holy Books) can be used to support many contradictory religions. So even if one of the arguments did work, religious people would still have all their work ahead of them if they wish to justify the belief that God wrote some particular book, or that he cares what we eat or whom we sleep with. Furthermore, even if the universe was created by a God who continues to take an interest in our affairs, it would not follow that we ought to worship him and obey his every command (e.g., executing homosexuals). For explaining how things are, God is superfluous, and for determining how things ought to be, God is irrelevant: no miracle or magic book can absolve us from the responsibility of thinking for ourselves. As Goldstein writes in response to The Argument from the Upward Curve of History (crediting God for the spread of democracy, freedom and human rights despite natural selection’s favoring “survival of the fittest”):
Though our species has inherited traits of selfishness and aggression, we have inherited capacities for empathy, reasoning, and learning from experience as well. We have also developed language, and with it a means to pass on the lessons we have learned from history. And so humankind has slowly reasoned its way toward a broader and more sophisticated understanding of morality, and more effective institutions for keeping peace. We make moral progress as we do scientific progress, through reasoning, experimentation, and the rejection of failed alternatives.
Primary among those failed alternatives are magical thinking and dogmatic adherence to tradition — which encourage people to accept bad arguments.