the power of modus ponens (a.k.a. detachment)
For thousands of years students of logic were tortured by having to memorize the different kinds of valid and invalid syllogisms handed down by Aristotle and the logicians who succeeded him. Even as late as the 1960's and 1970's logic students at major South African universities were forced to do syllogisms.
Modern mathematical logic - [ which came down to us from George Boole, Giuseppe Peano (1858- 1932), Alfred North Whitehead and Bertrand Russell (who used some of Peano's ideas from Peano Arithmetic in Principia Mathematica without giving proper scholarly attribution to Peano), David Hilbert, Ernst F.F. Zermelo (1871- 1953), Abraham Fraenkel (1891- 1965), Thoraf Skolem (1887- 1963), Kurt Godel, Alonzo church, Alan Turing, Haskell Curry, Gerhard Gentzen, E.W. Beth, Stephen Kleene, A. Mostowski, Alfred Tarski, Jaakko Hintikka, A. Robinson, George Kreisler, J.B. Rosser, Dana Scott, Raymond Smullyan, Yannis Moschovakis and many others] - demonstrated that all the valid Aristotelian syllogisms (a subset of the 64 syllogism moods) could be proved by repeated applications of one rule of inference, namely modus ponens (detachment).
Below is an example of repeated correct applications of modus ponens.
On reading M.H. Lob's proof of Lob's Theorem, Leon Henkin came up with the following proof that Santa Claus exists.
Let "SC" abbreviate "Santa Claus exists."
Let Sam be the sentence "if Sam is true, SC." Assume that Sam is true; then "if Sam is true, SC" is true; thus if Sam is true, SC; and so SC by modus ponens. Thus we have shown that SC on the assumption that Sam is true, and have therefore shown outright that if Sam is true, SC. But then "If Sam is true, SC" is true, i.e. Sam is true, and by modus ponens again, SC.
(see The Logic of Provability, George Boolos, pp. 54 -58, Cambridge Univ. Press, 1993.)
_______________________
Proof- in Dr Seus' style - of the undecidability of the halting problem
- An elementary proof of the undecidability of the halting problem
by Geoffrey K. Pullum, University of Edinburgh
~ ~ ~
Scooping the Loop Snooper
+++
No program can say what another will do.
Now, I won’t just assert that, I’ll prove it to you:
I will prove that although you might work til you drop,
you can’t predict whether a program will stop.
Imagine we have a procedure called P
that will snoop in the source code of programs to see
there aren’t infinite loops that go round and around;
and P prints the word “Fine!” if no looping is found.
You feed in your code, and the input it needs,
and then P takes them both and it studies and reads
and computes whether things will all end as they should
(as opposed to going loopy the way that they could).
Well, the truth is that P cannot possibly be,
because if you wrote it and gave it to me,
I could use it to set up a logical bind
that would shatter your reason and scramble your mind.
Here’s the trick I would use – and it’s simple to do.
I’d define a procedure – we’ll name the thing Q -
that would take any program and call P (of course!)
to tell if it looped, by reading the source;
And if so, Q would simply print “Loop!” and then stop;
but if no, Q would go right back to the top,
and start off again, looping endlessly back,
til the universe dies and is frozen and black.
And this program called Q wouldn’t stay on the shelf;
I would run it, and (fiendishly) feed it itself.
What behaviour results when I do this with Q?
When it reads its own source, just what will it do?
If P warns of loops, Q will print “Loop!” and quit;
yet P is supposed to speak truly of it.
So if Q’s going to quit, then P should say, “Fine!” -
which will make Q go back to its very first line!
No matter what P would have done, Q will scoop it:
Q uses P’s output to make P look stupid.
If P gets things right then it lies in its tooth;
and if it speaks falsely, it’s telling the truth!
I’ve created a paradox, neat as can be -
and simply by using your putative P.
When you assumed P you stepped into a snare;
Your assumptions have led you right into my lair.
So, how to escape from this logical mess?
I don’t have to tell you; I’m sure you can guess.
By reductio, there cannot possibly be
a procedure that acts like the mythical P.
You can never discover mechanical means
for predicting the acts of computing machines.
It’s something that cannot be done. So we users
must find our own bugs; our computers are losers!
______________________________
In the ECONOMIST(22 November, 2001) there is a book review of MATHEMATICAL MOUNTAINTOPS which is about "proving the five most famous theorems of all time"; the five include Fermat's Last Theorem and the Four Colour Map theorem.
In the review they quote the reply the logician Julia Robinson gave to the Personnel Dept. at The University of California, Berkley, who wanted to know how she spent her working day during an average week.
Her reply:
"Monday: tried to prove theorem Tues: tried to prove theorem Weds: tried to prove theorem Thurs: tried to prove theorem Fri: theorem false!"
______________________________
Bertrand Russell pointed out to an audience that if you allow a contradiction into your system then any conclusion can be proved in that system.
Heckler to Bertrand Russell; "O.K. if 1 equals 2 prove that you are the Pope.
Russell's reply;
"The Pope and I are 2 therefore the Pope and I are 1".
______________________________
On a bad day, dragon howl in logical head.
On a good day, you write Q.E.D. at the end of your proof.
- Zak Van Straaten (1988)
______________________________
If I feel unhappy, I do mathematics to become happy. If I am happy, I do mathematics to keep happy.
- Alfred Renyi
______________________________
Numbers written on bills within the confines of restaurants do not follow the same mathematical laws as numbers written on any other pieces of paper in any other parts of the universe."
-Douglas Adams (Restaurant at the end of the Universe, 1982)
______________________________
According to W. Quine,
Whose views on quotation are fine,
Boston names Boston,
and Boston names Boston,
But 9 doesn't designate 9.
George Boolos in Logic, Logic and Logic says that Richard Cartwright used to assign to MIT graduate students in philosophy the exercise of supplying quotation marks to the above under punctuated limerick.
One solution is to put pairs of single quotes around the first and fourth occurrences of 'Boston' and a pair of quotes within quotes around the third.
Another solution is to put single quotes around the second and third occurrences of 'Boston' and quotes within quotes around the first. ( Logic, Logic and Logic p. 392)
______________________________
Godel believed that there is a "NOT" laid up in heaven
Bertrand Russell, Autobiography 1914 - 1944
______________________________
Hinton married a daughter of the logician George Boole. Unfortunately, having failed to grasp the concept of an either / or proposition, he was convicted of bigamy.
-Steven Eisenbach (The First Pitching Machine on the www.)
______________________________
A figure with curves always offers a lot of interesting angles
-Mae West (The Wit and Wisdom of Mae West, Putnam, New York 1967 p. 3)
______________________________
A mathematician is a machine for turning coffee into theorems.
- Paul Erdos
______________________________
Crime is common. Logic is rare.
Sherlock Holmes (in The Adventures of the Copper Beeches) - Arthur Conan Doyle.
______________________________
Statistics is the physics of numbers
- Persi Diaconis
______________________________
Women's studies students are now being taught that LOGIC is a tool of domination
- Daphne Petan & Noretta Koertge in Professing Feminism: Cautionary Tales from the World of Women's Studies
______________________________
Set Theory can be viewed as a form of exact theology
- Rudy Rucker
______________________________
+ + +
Biologists think they are biochemists
Biochemists think they are physical chemists
Physical chemists think they are Physicists
Physicists think they are gods
And the gods think they are mathematicians
-Anon
______________________________
Mathematics is the part of science you could continue to do if you woke up tomorrow and discovered the universe was gone
- Dave Rusin
______________________________
The notion of analytic truth is inherently obscure, and the attempt to delimit a class of statements that are true a priori should be abandoned as misguided.
- Carl G. Hempel (in the Encyclopedia Brittanica (1981) summarising the view of W.V. Quine) (from the entry on Carnap, Rudolf (which is positioned just before the entry on Carnivora !)
If this view is correct then the grand ideals, ideas and hopes of Carnap's foundationalism would have to crash. First there was Godel's fatal mortar attack (even arithmetic doesn't have proper foundations ! ) then this...