logic walkabout

the power of modus ponens or 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.)

+ + +

It would be neat if the universe were a set of mathematical structures

Below are some quotations from various authors expressing this grand idea

Pythagoras and his followers believed that in some sense it must be true that 'All is Number'. This was their way of saying that the universe is a mathematical structure. The Pythagoreans recognised the mathematical nature of music and believed in some sort of mystical numerical harmony of the universe.
To Pythagoras and his followers we must attribute the deep insight, "that space can be a mathematical abstraction, and, just as important, that the abstraction can apply to many different circumstances." Euclid's Window: The Story of Geometry from Parallel Lines to Hyperspace, Leonard Mlodinow, Allen Lane Penguin, 2001. So in some interpretation, for the Pythagoreans, the stuff of the universe was numbers and geometry.

+ + +

Galileo Galilei wrote; "Philosophy is written in this grand book - I mean the Universe - which stands continually open to our gaze, but it cannot be understood unless one first learns to comprehend the language and interpret the characters in which it is written. It is written in the language of mathematics, and its characters are triangles, circles and other geometrical figures, without which it is humanly impossible to understand a single word of it."
"Mathematics is the language with which God has written the universe."

+ + +

Gödel believed that what makes mathematics true is that it's descriptive of an abstract reality. Mathematical intuition is like sense perception. In the abstract Platonic world we can see mathematical and logical truths which must be true. See Gödel's paper: "What Is Cantor's Continuum Hypothesis?" for an elaboration of what we can deduce through pure reason. Gödel's Platonism is the view that there exists "a non-sensual reality, which exists independently both of the acts and the dispositions of the human mind and is only perceived, and probably perceived very incompletely, by the human mind" ("Some basic theorems on the foundations of mathematics and their philosophical implications." p.323. (1951) Reproduced in Gödel. Collected Works, vol. 3. Feferman, S., Dawson, J., Goldfarb, W., Parsons, C., Solovay, R., and van Heijenoort, J. (eds.). 1995 Oxford: Oxford University Press.

+ + +

Max Tegmark continues the grand tradition of universal abstraction. Max Tegmark is a precision cosmologist, that is someone who combines theoretical work with new measurements to place sharp constraints on cosmological models and their free parameters.
In The Mathematical Universe Max Tegmark argues that given the physics implications of the External Reality Hypothesis (ERH) that there exists an external physical reality completely independent of us humans; and assuming a broad definition of mathematics, ERH implies the Mathematical Universe Hypothesis (MUH) that our physical world is an abstract mathematical structure.

An overview map of the delightfully abstract landscape of maths by Max Tegmark

Relationships between various basic mathematical structures. The arrows generally indicate addition of new symbols or axioms. Arrows that meet indicate the combination of structures - for instance, an algebra is a vector space that is also a ring, and a Lie group is a group that is also a manifold.
The map is used with permission from prof. Max Tegmark. It was used in M. Tegmark, Is 'the theory of everything' merely the ultimate ensemble theory? arxiv:gr-qc/9704009 and subsequently in Which Mathematical Structure is Isomorphic to our Universe? in the print edition of the New Scientist. http://space.mit.edu/home/tegmark/toe_frames.html

+ + +

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!"


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 (exclusive) 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.


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


+ + +

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



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...