Are the fundamental mathematical assumptions on which all mathematical proofs rest unproven or unprovable?

January 22, 2004 8:04 AM

Mathematicians! I was told that there are fundamental mathematical assumptions (maybe 6, or 7) on which all mathematical proofs rest, but which themselves are unproven. Or maybe they're unprovable. I seem to recall that one is that ab always=ba and another than a+b = b+a. What are the others? Are they unproven, or unprovable? If either, where does that leave every other mathematical proof? Are there any more assumptions waiting to be discovered?

Caveat: I'm a mathophobe lit grad who happens to have just finished reading "Fermat's Last theroum", so be gentle with me, please egg-heads.
posted by Pericles to education (24 comments total)

I should mention that, when I say "read" Fermat's Last theorum, I really mean "enjoyed the biographies of the people and the detective story, but was baffled by the numbery bits". I'm *that* stupid.
posted by Pericles at 8:08 AM on January 22, 2004

I beleve that its more that they cant be broken down into simpler proofs. I can easily prove that a+b = b+a. Take three apples, add another 4 apple to them, count your apples. Now take four apples, add another 3 to them and count. they are the building blocks on which all other proofs are derived, i dont remember them all but they include a=a(reflexive, defines what the = means), a+b = b+a (communitive), ab=ba.,... and my memory runs out at that point
posted by Davidicus at 8:15 AM on January 22, 2004

Yes, they're called axioms. There's a distinction, though, between the ones you mention (commutativity of multiplication and addition, respectively) and the ones on which all mathematical proofs rest.

The examples you give might be called "Axioms of Arithmetic", or more precisely, axioms of real numbers. (Real numbers are the ones you know and love: decimals.) It's true that any (true) statement you care to make about real numbers, or integers, or rational numbers, can be derived from a half-dozen basic assumptions. There's a long history of trying to put this on a sound philosophical foundation (see Frege, Russell, Whitehead, Wittgenstein, and ask yourself, "What do I mean when I say `one'?"), mostly successful, sometimes not.

There are similar things in geometry, where they're usually called "Postulates". You've probably heard of Euclidean geometry (what you usually think of when you say the word 'geometry', and you may have heard of Riemannian and Lobachevskian geometry. The differences between them are in the postulates. In Euclidean geometry, we assume that given any line L and any point P not on L, there's a unique line through P that doesn't intersect L. This matches up well with what we experience in day-to-day life. But it's an assumption. It's just as internally consistent (and, more interestingly, just as useful) to assume either (1) there are no lines through P that don't intersect L, or (2) there are infinitely many. They are just as kosher, but they give different geometries.

Similarly, one of the things that I do (in my research) is to consider number systems that don't necessarily satisfy ab=ba. For example, consider the set of all functions from the real numbers to itself. Define a multiplication on this set by composition: given two functions f and g, the product fg is: first apply g, then apply f. This is what's called a "ring", which just means "a place where you can multiply and add stuff." But it's not commutative: if f(x) = x² and g(x)=x+1 (the squaring function and the adding-one function, respectively), then the result of first doing f and then g is different from the result of first doing g and then doing f.

If you want to talk about axioms "on which all mathematical proofs rest", then you're really talking about the laws of logical inference: things like "given P ==> Q, and given P, then conclude Q."
posted by gleuschk at 8:28 AM on January 22, 2004

What you're referring to are what mathematicians call "axioms": things that are taken as true in a given subfield, on which all other proofs in the field are built. For example, Euclidean geometry is built on a set of five axioms. By changing the last one of these axioms, one can define entirely new types of geometry (where, for example, the sum of the angles of a triangle is always greater than 180 degrees.)

I'm not sure if anyone has sat down and written down a comprehensive set of all axioms used to build up mathematics as we know it. I have a vague, nagging notion that everything can be built up from set theory, but hopefully someone more knowledgeable will be along soon to correct me.

Oh, and no discussion of the nature of axioms would be complete without a tip of the hat to Kurt Gödel and his infamous Incompleteness Theorem.

On preview: Dagnabit, gleuschk beat me to the punch.
posted by Johnny Assay at 8:32 AM on January 22, 2004

I can easily prove that a+b = b+a. Take three apples, add another 4 apple to them, count your apples. Now take four apples, add another 3 to them and count.

You have proven that 3+4 = 4+3. You have not proven that a+b = b+a. To do that, you'd have to perform your experiment for every possible quantity of apples, including partial apples.

That's obviously impossible, and that's why it's an axiom.
posted by kindall at 8:39 AM on January 22, 2004

(derail - hey, Simon Singh's 'The Code Book' is much more fun to read you might want to pick that up.)
posted by dabitch at 8:41 AM on January 22, 2004

OK, Kindall. But it would not be possibe to test Pythagoras law about hypotenuses for every conceivable lengths, but wiser people that me tell me that it has been proven that h2=a2+o2 (and using the axioms to do it). Is it not possible to prove that for every number a+b = b+a?

The code book was more fun. Though almost as number-infested ;-)
posted by Pericles at 8:47 AM on January 22, 2004

And just to add an odd tangent, Raymond Smullyan has an interesting essay in his book The Tao is Silent which posits the question are all systems of morals finitely axiomatizable.

The last two words have to do with what you're asking: given any logical system (and mathematics and geometry are logical systems), can the system be reduced to a finite number of axioms.

Smullyan claims that all moral systems can be reduced to precisely one axiom--but read the book. He covers it well, and the notion of a professional logician writing about the Tao (which is anything but logical), is delightful.
posted by plinth at 9:42 AM on January 22, 2004

Pericles: the question is not whether it's possible to prove that a+b=b+a, but what you get to use to prove it. If you let me assume enough stuff, I can prove anything you like. (For a radical example, if you let me assume that x+y=0 for every x and y, I can easily prove a+b=b+a.)

Maybe the issue is the use of the word "prove". Mathematicians have a very precise meaning in mind when they say it, which isn't quite the same as the usual usage. In mathematics, to prove something is to derive it from whatever axioms you're starting with, by using the logical laws of inference you've agreed upon. Checking the statement in special cases, as you're suggesting, doesn't really enter into it.

For example, 43 proofs of the Pythagorean theorem (including one by President James A. Garfield). They're pictorial, but they can be made precise, by which I mean: they show that the statement, "for any right triangle with legs a and b, and hypotenuse h, the square of the length of h is equal to the sum of the squares of a and b" follows from the Euclidean Postulates and applications of the laws of inference.

(sorry if this is repetitive: AskMe was down for a little while, and I had to go to a seminar.)
posted by gleuschk at 10:16 AM on January 22, 2004

you can (probably) base all (or at least a large chunk) of maths on set theory.

for example, for integers you represent zero as the empty set; one as the set with a single member, which is the empty set; two as the set with a single member which is the set representing one; etc... then you can start to define addition, multiplication, what have you from the axioms of set theory.

the idea is that you take all the different areas of maths and, by basing them on a single theory, rely only on the axioms of that single base theory. which saves you from worrying so much about contradictions between the axioms of algebra and geometry, for example.

the flip side of this is that the axioms of set theory come under very heavy scrutiny. and there's more than one way to frame set theory - you can pick different axioms and start building theories on top of them.

so the big question is - what's the best set of axioms for set theory? current received wisdom is that zfc set theory is the way to go.

so most mathematicians would probably say that the axioms of mathematics are the axioms of zfc set theory.

doing all this is fairly recent maths - see here for a history. people kept screwing up and getting inconsistent theories that led to contradictions... (also, it wasn't clear whether some of the axioms were really independent)

this seems like a good starting point for more reading. it includes the axioms of zfc
posted by andrew cooke at 10:17 AM on January 22, 2004

ps in case it's not obvious, it is, therefore, those axioms of zfc on which "all of mathematics rests" (and there are 7, but the last one is (was?) a bit controversial).
posted by andrew cooke at 10:20 AM on January 22, 2004

Pericles: right. Theorems are not proved by simply plugging in every legal value for the variables in question and simply verifying that the theorem holds.

Mathematical Induction is usually used to prove that if something holds for a value x, and you can prove that it holds for a value x+1, then it holds for all values of x. That's one huge shortcut that is often used. There are others (such as Reductio Ad Absurdum), but I won't get into them here.

Also look up Peano's Axioms some time, if you're interested in reading further.
posted by bshort at 10:22 AM on January 22, 2004

. But it would not be possibe to test Pythagoras law about hypotenuses for every conceivable lengths, but wiser people that me tell me that it has been proven that h2=a2+o2 (and using the axioms to do it). Is it not possible to prove that for every number a+b = b+a?

Proofs of Pythagoras' theorem assume the axioms are true. An axiom is typically a statement that seems intuitively true but would be impossible to prove. Basically it provides a starting point. "Let's assume this is true and see where it gets us." Well, given the success of arithmetic, it gets us a long way.

The commutativity of addition is as much a definition of addition as it is a statement about the properties of numbers. "Addition has the characteristic that it yields the same result regardless of the order of the numbers being added." If we get a different answer depending on the order of the numbers, then we know we're not adding.
posted by kindall at 10:45 AM on January 22, 2004

In reference to the 3+4 = 4+3 does not equate a+b = b+a, I think you can use matrices to prove that. I can do a proof to prove that (a+b)i,j = (b+a)i,j for all i,j.
Just as an example, the proof goes:
(A+B)i,j =(by def of matrix add) Ai,j + Bi,j
=(cummulative law of addition over the reals) Bi,j+Ai,j
=(by def of matrix add) (B+A)i,j
therefore, for all i,j by the definition of equality, A+B=B+A
Of course, this also assumes commulative law of addition and matrix addition, so I dunno if that helps.
posted by jmd82 at 11:23 AM on January 22, 2004

You're proving the commutative law of addition by assuming the commutative law of addition?

Which is actually technically correct, and ties in well with the whole discussion of axioms and proofs. If you take the commutative law of addition as axiomatic, then it is trivial to "prove" (scare quotes because it is a 100% valid proof in the mathematical sense, but not in the common usage of the word) the commutative law of addition. Not terribly interesting to do so, but entirely valid.
posted by DevilsAdvocate at 12:18 PM on January 22, 2004

That was "kind of" the point, DA...I was attempting to take the idea that a+b!=b+a in all cases, as simply saying a+b=b+a may not necessarily be true in all cases (as in, it needs to be proven to be valid for all cases). So I was trying to say that by simply invoking matrices, you can in fact show that a+b=b+a for all instances. Then again, I am just a product of my senile linear algebra and discrete math classes where a matrix is the end-all, be-all of mathematics, so who knows.
posted by jmd82 at 1:32 PM on January 22, 2004

jmd82, I think you're missing DA's point.

You have addition over matrices (which you've defined offscreen), then you did some elementary algebra to show that your definition was "correct." All you did was prove a tautology.
posted by bshort at 2:01 PM on January 22, 2004

I can't believe nobody's mentioned Principia Mathematica (shorter Wikipedia entry).
posted by languagehat at 6:45 PM on January 22, 2004

Here's a stab at answering this question for non-mathematicians (warning -- oversimplification ahead):

Mathematicians and philosophers are still arguing about the logical basis of what mathematics is. The basic process of mathematics is that you start by assuming a few basic fundamental truths. These are called axioms. These axioms often just amount to a definition of the concepts and symbols you are using. Then you use logic to derive new truths (theorems) from your axioms. Some mathematics consists of deriving new theorems from axioms that are already widely accepted. Other mathematics consists of inventing new systems of axioms and seeing what kinds of theorems you can prove with them.

In some ways, this means that all mathematical theorems are just very elaborate tautologies. The statement "1+1=2" depends on your definition of what "1", "+", and "=" mean. There are some things that make a system of axioms good. You want to assume as little as possible, so you don't want to be able to prove one of your axioms based on the others. That ensures that your axioms are not redundant. You also don't want your axioms to be contradictory. If you can use a set of axioms to prove both some particular statement and also prove the contrary of that statement, then somewhere in your axioms you've got a hidden contradiction.

This process of assuming some things and then using the assumptions to prove other things was established by the ancient Greeks. That's why they teach geometry in high school, because it's an excellent example of the basic process of mathematical reasoning.

One of Euclid's geometry axioms was the "parallel postulate", but it seemed for a long time that it was not such an obvious and intuitive thing to assume. Mathematicians tried for centuries to find a way to prove the parallel postulate from the other axioms, but they always failed. Finally in the 19th century mathematicians said "what if the parallel postulate really is an irreducible assumption?" And so they tried to see what would happen if they invented a geometry based on dropping Euclid's parallel postulate and replacing it with some other axiom that assumed the contrary. To the surprise of many, that led to a consistent set of axioms that could be used to prove weird geometrical theorems, different from Euclid's geometry. That non-Euclidean geometry at the time was just an intellectual exercise, but it later turned out to be useful for Einstein's theory of relativity. So you can have different sets of axioms that lead to different mathematical theories, and those contradictory theories can each be useful in their own way.

In the late 19th and early 20th century, mathematicians tried very hard to discover the most fundmental set of axioms that could serve as a basis for deriving all of mathematics. Set theory seemed like it was going to succeed, but people like Bertrand Russell who devoted their lives to the effort unfortunately kept discovering problems and contradictions in the theories.

Godel eventually proved that there is a real underlying problem with trying to find the one perfect set of axioms for arithmetic (integers, addition, multiplication). He showed that any system of axioms that was powerful enough to prove the basics of arithmetic is either inconsistent (i.e., contains hidden contradictions), or incomplete (i.e., there are statements about arithmetic that are true but that are impossible to prove from your axioms).

People are still arguing about what Godel's Theorem really means, but it's pretty clear that the project of defining a single set of fundamental assumptions that provide the basis for all mathematics now lies in ruins. That's "postmodern mathematics": you pick your fundamental truths and then see what kind of mathematics you can create from them.
posted by fuzz at 12:37 AM on January 23, 2004

Thanks fuzz, and everyone else. What I'm understanding from this is that axioms don't necessarily define numbers, so much as operations: eg, a+b = b+a doesn't say "numbers are such that they can be added together either way" as "addition is an operation which always produces the same result in whichever order the numbers are operated on".

I'm also getting the idea that axioms are like quarks, irreducible but the base of everything else. They can't be "proved" because you'd need more basic axioms from which to prove them and so on, ad infinitum. In short: mathematics can't be proven with mathematics; arithmatic is a very very useful technique, but fundamentally it's based on assumptions that we all believe to be true, but can't be shown to be so .(How many assumptions is the minimum you need for arithmetic, and can it be shown that we won't need any more at some point)

Or should I go back to poesy and aestheting around composing sonnets to flowers?
posted by Pericles at 1:56 AM on January 23, 2004

your second bit is bang on (about axioms being what we believe but can't prove).

your first bit is probably better phrased as mathematics isn't about numbers, as much as operations.

you can't prove that we will never need more axioms (at least, i have no idea how to), but people generally believe that the axioms of zfc provide a basis for most of mathematics (and there are 7 of them).

languagehat - well, i referred to it, with my "people kept screwing up and getting inconsistent theories that led to contradictions..." ;o)
posted by andrew cooke at 2:54 AM on January 23, 2004

Very well said, fuzz and andrew. Thanks. And yes, Pericles, you're on it now.

(languagehat: the thread is chock-full of oblique references to PM! I mentioned Russell and Whitehead way up there at the beginning. :) )
posted by gleuschk at 6:34 AM on January 23, 2004

you can't prove that we will never need more axioms

Actually, Godel discovered something much stronger than that: you will always need more axioms. There will always be true statements that you can't prove with your axioms. Worse than that, there's a vicious infinite regress: If you add those true but unprovable statements as new axioms (i.e., you just assume what you can't prove), then there are still more truths that you won't be able to prove.

It's probably worth noting that the very end of andrew's link about ZFC says that you can either assume that the Axiom of Choice is true, or assume that it's not true, and either way you get a consistent set of axioms. So there's more than one mathematical system of set theory, depending on what you decide to assume.

It's also worth noting that the Axiom of Regularity in ZFC is basically designed to outlaw an entire category of contradictions and paradoxes that doomed Russell and Whitehead's Principia Mathematica. So ZFC is a set of axioms that works well partly because it assumes that the difficult questions are not allowed. That's basically a way for mathematicians to throw up their hands and give up on unraveling the paradoxes. Maybe one day someone will come up with a mathematical theory that gives us a better understanding of those difficult questions, so it's entirely wrong to think that ZFC represents the only set of fundamental axioms of mathematics.
posted by fuzz at 6:57 AM on January 23, 2004

blimey. you lot are bright. thanks. Now, anyone want a lyrical ballad?
posted by Pericles at 7:35 AM on January 23, 2004