Revolution in Mathematics: What Happened 100 Years Ago and Why It Matters [pdf]
ams.org
ams.org
David Hilbert wanted to redo mathematics from square one, basing everything on set theory, axioms, and rigorous proofs. In 1900, Hilbert gave his famous address where he stated the Hilbert Problems. One of these was to prove that mathematics is "complete" in the sense that every possible statement is either provable or disprovable from the axioms.
In an effort to solve this problem, Alan Turing wrote his famous paper "On Computable Numbers" where he conceived for the first time his "Turing Machines". Although his approach didn't work to solve the Hilbert problem, it greatly inspired Von Nueman who at the time was pretty much working on pure mathematics.
Godel came along and proved that mathematics is not "complete", because there are some statements about natural numbers which cannot be proved or disproved from the axioms, but rather are undecidable.
Von Nueman was so upset by Godel's result that he decided he no longer wanted to work in pure mathematics, because if it's not complete then whats the point anyway. Instead he decided to work on applied math and physics. Since he loved the work of Turing, he wanted to build a physical Turing Machine to help out with computations, and he figured there would probably be a lot of other uses for such a machine that no one had thought of yet, and that would only become apparent once the machine was built.
While at the Institute for Advanced Study, Von Nueman fought a hard political fight to secure funding and permission to build the first computers, the MANIAC and the ENIAC, to the horror of the faculty at the time, including Einstein.
Since I am posting this at 4:30am in a thread that is 12 hours old, I will be happy if someone reads it :P
[1] http://books.google.com/books/about/Turing_s_Cathedral.html?...
Turing's Cathedral has a ton of really interesting historical details about the history of computers, and LOTS of details about the political fight Von Nueman waged to even be allowed to work on the first computers at IAS. I didn't realize how big a role he actually played, and I would encourage people to read that book because its pretty good.
> In an effort to solve this problem, Alan Turing wrote his famous paper "On Computable Numbers" where he conceived for the first time his "Turing Machines".
Whoa -- you completely skipped Gödel's Incompleteness Theorems. Gödel's Theorems answered Hilbert's inquiry, not Turing. It's true that the Turing halting problem and Gödel's Theorems are deeply connected, but the historical sequence is Hilbert, Gödel, then Turing. You can't leave Gödel out.
http://en.wikipedia.org/wiki/G%C3%B6dels_incompleteness_theo...
At the turn of the 1900s, the field of mathematics was changing. The old school relied of physical intuition as a means of proof. The new school found that an adherence to formal logic led to more reliable findings.
Most Relevent Sections:
In brief, traditionalists lost the battle in the professional community but won in education. The failure of “new math” in the 1960s and 70s is taken as further confirmation that modern mathematics is unsuitable for children. This was hardly a fair test of the methodology because it was very poorly conceived, and many traditionalists were determined that it would succeed only over their dead bodies. However, the experience reinforced preexisting antagonism, and opposition is now a deeply embedded article of faith.
Many scientists and engineers depend on mathematics, but its reliability makes it transparent rather than appreciated, and they often dismiss core mathematics as meaningless formalism and obsessive-compulsive about details. This is a cultural attitude that reflects feelings of power in their domains and world views that include little else, but it is encouraged by the opposition in elementary education and philosophy.
In fact, hostility to mathematics is endemic in our culture. Imagine a conversation:
A: What do you do?
B: I am a ———.
A: Oh, I hate that.
Ideally this response would be limited to such occupations as “serial killer”, “child pornographer”, and maybe “politician”, but “mathematician” seems to work. It is common enough that many of us are reluctant to identify ourselves as mathematicians. Paul Halmos is said to have told outsiders that he was in “roofing and siding”!from page 33-34.
Core methods such as completely precise definitions (via axioms) and careful logical arguments are well known, but many educators, philosophers, physicists, engineers, and many applied mathematicians reject them as not really necessary.
from page 34
Why It Matters:
The sciences are at risk in the reckless implementation of maths.
Education methods are weakened by the philosophical divide.
Philosophically, aren't divides (ie. the presence and consideration of multiple perspectives or approaches) exactly what real (ie. non domain-linked) education needs?
I have nothing to add.
We're at a very exiting point in time where we know basic mathematics to be wrong. It predicts a great many things, but there's problems that make it thoroughly unsatisfactory. In a way it's like physics in the beginning of the 20th century, with the black body radiation problem. Of course, we have been in this less-than-satisfactory state for ~70-80 years now, and no Einstein in sight ...
Godel's theorem means that there's an infinite set of empirical truths (ie. simple experiments you can try out with marbles and bags) that are completely unexplained by mathematics - and thus by every science built on top of it.
Worse : this is not a fixable problem. Sure we can fix it for specific problems. Wherever we see an obvious leak (say the birthday problem, or large cardinal number problems) it can be plugged with a new well-chosen (or -more often- ill-chosen, like choice) axiom, but there's infinitely many leaks and the proof means that there's no plug that will stop any significant number of them.
So right now in the set of all empirically observable events, there's a set that's explainable by science, and there's a set unexplained by science. The unexplained set is at least as large as the explainable set (and keep in mind that's because both sets have been proven to have a cardinality of at least the largest known cardinal number, given the actual definitions of those 2 sets I'd say the unexplained set is going to turn out to be bigger).
There seems to be a great danger in the prevailing overemphasis on the deductive-postulational character of mathematics. True, the element of constructive invention, of directing and motivating intuition, is apt to elude a simple philosophical formulation; but it remains the core of any mathematical achievement, even in the most abstract fields. If the crystallized deductive form is the goal, intuition and construction are at least the driving forces. A serious threat to the very life of science is implied in the assertion that mathematics is nothing but a system of conclusions drawn from definitions and postulates that must be consistent but otherwise may be created by the free will of the mathematician. If this description were accurate, mathematics could not attract any intelligent person. It would be a game with definitions, rules, and syllogisms, without motive or goal. The notion that the intellect can create meaningful postulational systems at its whim is a deceptive half-truth. Only under the discipline of responsibility to the organic whole, only guided by intrinsic necessity, can the free mind achieve results of scientific value…To establish once again an organic union between pure and applied science and a sound balance between abstract generality and colourful individuality may well be the paramount task of mathematics in the immediate future.
The thesis in the linked article is that we need to emphasise the importance of purely abstract formalisms, not only in the context of possible applications.
There is also a nice lecture [1] from Vladimir Arnold, who was very much on the side of intuition, where he raises an interesting point that is related: in todays mathematics all the praise goes to the people who prove theorems, where perhaps the person who first _stated_ an theorem that is interesting and relevant deserves at least as much credit.
[1] http://www.msri.org/web/msri/online-videos/-/video/showVideo...
[1] http://plato.stanford.edu/entries/brouwer
[2] http://en.wikipedia.org/wiki/Errett_Bishop
'Sparse' would be an understatement & poor old Errett got such wonderfully backhanded reviews as:
> "Even those who are not willing to accept Bishop's basic philosophy must be impressed with the great analytical power displayed in his work."
and
> Bishop's historical commentary is "more vigorous than accurate".
Algebra and number theory are both heavily reliant on modern mathematical thinking. Abstract algebra is practically the defining example of it.
How does one create Mathematica and Maple without modern mathematical thinking? Indeed, formal logic is rather closely involved in computing generally.
How does a precollege mathematics system that is based on a 19th century style of mathematics pay more attention to 19th century style mathematics?
I find your confident dismissal of modern mathematics to be vexing and oddly misaimed.
Although we've invented a number of algorithmic methods to find bugs in software, the long-term trend is to find "better axioms" to define the program against, which reduce both the code size and complexity - that's the goal otherwise known as "programming language design." We don't want people to code in 19th century fashion, because it sucks.
This kind of rings a bell for me here concerning Formal Verification methods (i.e. proofs), possibly more popular with functional programming techniques.
Schrodinger's cat was originally proposed by Schrodinger to ridicule the many word's extrapolation of quantum mechanics. Now it is often used to support it. Scientists create multiple dimensions, universes, etc. based on very little real world data.
Von Neumann thought he proved that hidden variables were impossible, but In the 1970's, John Bell introduced Bell's Inequality, and showed us that hidden variables can only be used to explain Quantum entanglement if one gives up on naive locality.
Things get hairier from there when you try to combine non-local theories (such as Bohm's) with relativity.
It's complicated.
The law of the excluded middle says that for every x, either x or not x is true. Proof by contradiction says that if given not x you can derive a contradiction, then x is true.
The first controversy occurred early in Hilbert’s career and concerned his vigorous use of the "law of the excluded middle" (proof by contradiction).
I don't see how you can interpret that as not implying that the law of the excluded middle and proof by contradiction are not one and the same thing.
if you do not accept the law of excluded middle than proof by contradiction ceases to be a valid proof method.
I don't believe that this is true, because that would imply that you can derive the law of the excluded middle from proof by contradiction.
X and (not X) == False for any sentence X
If you start with a sentence y, and then via the proof methods arrive at a sentence (not y), this is the same as saying
(y -> (not y)) == True
Which is equivalent to:
((not y) or (not y)) == True
Which is equivalent to:
(not y) == True
Now, if you accept the law of non-contradiction this implies that:
y == False
If you do not accept it, y can both True and False at the same time and the proof method is not valid anymore. Hence the proof method of reductio ad absurdum, or "proof by contradiction" as you call it, is valid if and only if this law holds.
For instance, paraconsistent logic has the law of excluded middle but not ex falso quodlibet.
https://en.wikipedia.org/wiki/Principle_of_explosion
https://en.wikipedia.org/wiki/Paraconsistent_logic
--
addendum
Specifically, notice that in classical logic the axioms law of excluded middle and law of non-contradiction can be substituted for one another (they are equivalent). However, that is not the case for all semantics.
(x->(~x))->(~x)
Law of excluded middle is:
x | ~x
Proof follows:
(x->(~x))->(~x)
From definition of implication is equivalent to:
(~x) | ~(x->(~x))
From definition of implication is equivalent to:
(~x) | ~((~x) | (~x))
From de Morgans law is equivalent to:
(~x) | (x & x)
From identity law is equivalent to:
~x | x
I am not a logician and I might not have gotten all the details right, but I certainly think this is possible. I also have quite a good proof by authority ;) in form of an article by Alonzo Church:
http://www.ams.org/journals/bull/1928-34-01/S0002-9904-1928-...
Actually, at first I thought it was incorrect because you used De Morgan's law, which I mistakenly thought was invalid in intuitionistic logic. However, I looked it up and apparently only ~(p & q) |- ~p v ~q is invalid in IL.
It's possible to create reductio ad absurdum in Coq:
Definition reductioAdAbsurdum (X:Prop) (f : (X -> (X -> False))) (x:X) : False := f x x.
But not the law of the excluded middle.Edit: It's much clearer in Idris:
reductioAdAbsurdum : (x -> (x -> _|_)) -> (x -> _|_)
reductioAdAbsurdum f x = f x xIn propositional logic, material implication is a valid rule of replacement which is an instance of the connective of the same name. It is the rule that states that "P implies Q" is logically equivalent to "not-P or Q".
Nice flame, eot.
Arguably, the common sense definition of 'A -> B' is simply modus ponens. That is 'Given A and A->B, it follows that B'. It's then no longer obvious that A -> B is equivalent to ~A v B.
Indeed, implication in IL is different from material implication even though IL has modus ponens.
((~x) -> x) -> x
or: ((x -> _|_) -> x) -> x
Which is not constructible in Coq/Idris.* although there are logics in which this does not hold, but that's probably not what you are talking about here
deriveExcludedMiddle : ((x:Type) -> ((x -> _|_) -> x) -> x) -> Either y (y -> _|_)
So, perhaps I am relying on one of those logics where it doesn't hold.And shouldn't the quantification over x:Type be separately over each part?
I wanted:
(forall x. ((~x) -> x) -> x) -> (forall y. y \/ (~y))
Rather than: (forall x. (((~x) -> x) -> x) -> x \/ (~x)) LEM = (x:Type) -> Either x (x -> _|_)
DN = (x:Type) -> ((x -> _|_) -> _|_) -> x
We first constructively prove not not LEM: notnotLEMproof : (x:Type) -> ((LEM x) -> _|_) -> _|_
notnotLEMproof x f = f (Right (\a -> f (Left a))
Now we can use double negation to obtain a proof for LEM: DNimpliesLEM : DN -> LEM
DNimpliesLEM dn x = dn (LEM x) (notnotLEMproof x)
I hope this is correct, since I don't know Idris syntax. If Idris supports implicit parameters, you would not need the x's: notnotLEM f = f (Right (\a -> f (Left a))
DNimpliesLEM dn = dn LEM notnotLEMproof LEM : (x:Type) -> Type
LEM x = Either x (x -> _|_)
DN : (x:Type) -> Type
DN x = ((x -> _|_) -> _|_) -> x
notnotLEMproof : {x:Type} -> ((LEM x) -> _|_) -> _|_
notnotLEMproof {x} f = f (Right (\a => f (Left a)))
DNimpliesLEM : ((x:Type) -> DN x) -> LEM y
DNimpliesLEM {y} dn = dn (LEM y) notnotLEMproofI find the last one slightly clearer if you change the argument order:
DNimpliesLEM : ((x:Type) -> DN x) -> ((y:Type) -> LEM y)
DNimpliesLEM dn y = dn (LEM y) (notnotLEMproof y)
Although with the original formulation you could prove the slightly stronger version: DNimpliesLEM : (x:Type) -> DN (LEM x) -> LEM x
DNimpliesLEM x dn = dn (notnotLEMproof x)
so that you don't need DN z to be true for all z, but just on the z you need (i.e. z = LEM x). It was an interesting exercise, and I learned a lot. First I tried proving (((x:Type) -> LEM x) -> _|_ ->) _|_ to then apply double negation directly to this, but this is actually not possible (as far as I can see). The double negation needs to be inside the quantifier.Maybe you can even write it simply like this with implicit parameters:
DNimpliesLEM : DN (LEM x) -> LEM x
DNimpliesLEM dn = dn notnotLEMproofHe then went on to prove new things with it.
And he started out as an engineer.
The example given at the end is fractions, you can think of fractions in terms of pies and pizzas, but it's much more effective to ignore any of that when it comes to actually perform computations with that and simply focus on the "meaningless" symbols and manipulations that you do with them.
It's a pity that you tl;dr'ed this.
It makes a good point in how the changes initiated by Weierstrass and Cantor, by throwing away Geometry as a requirement to think in mathematics, ultimately lead the way to us to think in axioms and algorithms that's basically is how we do mathematics today. (The part about Cantor and Weierstrass is not stressed in the paper though).