# Is Principia Mathematica outdated?

1. Dec 27, 2009

### 1qaz2wsx3edc

Hi,

I'm currently in Physics graduate school, so I don't know much about mathematical logic. I got through an undergraduate degree in physics + maths. But I'm not entirely satisfied with my math, ever since I did the course on set theory. I want that kind of rigor in all the mathematical proofs I do. I want to build up a structured system of mathematics beginning from basic axioms (yeah, I won't be finished even when I die, I know. But at least I want to start)

I was thinking of starting with Reading Principia Mathematica by Russel - Whitehead. But I remember reading online sometime ago that it's outdated. Is it? I mean, will all my effort in reading it be wasted?

Any other websites, forums(specialized), books that might help? Any help is appreciated.

2. Dec 28, 2009

### wildman

Read "Godel, Escher, Bach, an Eternal Golden Braid" by Hofstadter. Basically Godel proved that absolute rigor is impossible. It is impossible for a logical system of sufficient strength to be both complete and consistent. Sorry.

3. Dec 28, 2009

### Hurkyl

Staff Emeritus
I don't see the connection between the fact "given a choice of axioms* there exists a statement** which can be neither proven nor disproven"*** and the claim that "absolute rigor is impossible".

*: a recursively enumerable set of axioms capable of encoding integer arithmetic, if you care about the details
**: I should clarify that I mean a statement in the particular formal language of interest
***: This is what "complete" means

As an aside there do exist complete and consistent theories. Useful ones, even. The first-order theory of Euclidean geometry comes to mind.

4. Dec 28, 2009

### 1qaz2wsx3edc

So it is possible to construct a system that is 'consistent' but 'incomplete'? For example, can all of real analysis be constructed from a set of axioms, using only first order logic as the 'language'? (Usually what we see in books has English as 'language')

5. Dec 28, 2009

### 1qaz2wsx3edc

Hurkyl, if a complete and consistent theory exists as you say so, doesn't that mean that Godel's Incompleteness Theorems are false?

6. Dec 28, 2009

### D H

Staff Emeritus
Godel's Incompleteness Theorems only pertain to mathematical structures of sufficient complexity. Simple ones, e.g. the previously cited Euclid's geometry, are immune. Induction and operations akin to addition and multiplication are needed.

7. Dec 28, 2009

### robert Ihnot

To answer for Hurkyl, (oops I see now that he did answer it!) that is completely ridiculous. Simple systems can be shown, such as a logic set that generates tautologies, to be consistent and complete: which is to say that by following the rules and playing with axioms one could in time come up with any tautology possible, and the system will not lead to a contradiction. It was Hilbert who added to the axioms of Euclidean Geometry to develop a consistent and complete system.

The system of arithmetic, is much more difficult in its ramifications, which include Number Theory--where there are today many unsolved problems.. and which a problem like Fermat's Last Theorem took 300 years to solve. But no one yet has figured out whether there is an odd perfect number. In a complete system those problems could be handled fully, at least when fed to a computer running long enough, no more real thinking would be required.

8. Dec 28, 2009

### Hurkyl

Staff Emeritus
You're making things too complicated.

Consider the trivial theory on any language: the one with no axioms at all. The only statements it can prove are tautologies. The only statements it can disprove are contradictions. Every other statement is undecided in this theory.

Other useful theories are similar. The language of an Abelian group consists of the constant symbol '0', the unary negation operator '-' and the binary addition operator '+'. The theory of an Abelian group consists of the axioms
$$\forall a,b,c: a + (b + c) = (a + b) + c$$
$$0 + a = a$$
$$a + b = b + a$$
$$a + (-a) = 0$$​

This theory is purposely incomplete -- there are all sorts of things we want to study as Abelian groups: the (additive) group of integers, of rationals, of reals. The modular groups like Z5. The group of translations on Euclidean space.

So it would be a bad thing of this was a complete theory -- a statement like
$$\forall x \exists y: y + y = x$$​
should be undecided, because it's false in some Abelian groups (e.g. the integers) and true in other Abelian groups (e.g. the rationals)

But sometimes we want categorical axioms -- axioms so that there is only one model -- because we want to talk about something like THE Euclidean plane.

Actually, it turns out we can't get that: our theories always have nonstandard models. (And sometimes that's a really good thing -- e.g. nonstandard analysis)

So, if we can't have categorical axioms, we might settle for a complete set of axioms -- such as the first-order theory of Euclidean geometry has.

The surprise of Gödel's incompleteness theorem was that we often can't get completeness either, without taking drastic measures. (See next post)

9. Dec 28, 2009

### Hurkyl

Staff Emeritus
Maybe it's too much, but I feel I should add that Gödel's theorem only applies to a (wide) range of strengths -- there is an upper bound on how strong a theory can be.

The set of axioms has to be "recursively enumerable". Any finite set is such. An infinite set can be "recursively enumerable" if, roughly speaking, one can write a computer program that outputs* the list of axioms one at a time.

An equivalent description is that there exists a computer program that, when presented a given statement, will answer "yes that is an axiom" whenever that is the correct answer. However, if that statement is not an axiom, it will either say "no that is not an axiom" or it will run forever without giving an answer.

There exist complete axiomatizations of integer arithmetic. However, since they cannot be recursively enumerable, they cannot really be worked with directly** -- their existence is mainly for theoretical purposes.

*: Of course, this program can't finish. But for any particular axiom, it will be printed sometime.
**: Barring either an "oracle", or some fundamental oversight in the theory of computability

10. Dec 28, 2009

### 1qaz2wsx3edc

Please excuse my lack of knowledge in the subject. I am aware that there are a lot of things I have to learn, but I want to ask these anyway. I'll learn the technical terms as I go along.

The reason I wanted to reduce some system to first order logic is because first order logic is simple and unambiguous. Making a system as simple as possible seems to me to be the first step one should take if one wants to make some sort of algorithm, which, given the initial axioms, is capable of deriving any 'theorem' in the system. (I believe this was the aim of 'Hilbert's Program'?) Is it possible to make a computer program that can check the proof of theorems this way? It seems to me that that is what software like "Metamath"[/URL] do.

If it is possible, have people tried to formalize (or computerize) systems that are in everyday use such as Number theory? As robert Ihnot said in his post, if we run such a program for a long enough time, a computer will show whether a proof is true or false.

Finally, about educating myself; Is this the order of the subjects that I should learn, to satisfy my curiosities?

1. Mathematical Logic
2. Model Theory
3. Proof Theory
4. Computability
5. Set Theory
... and so on.

If not could you give me a list of subjects in the order that I should learn them? Could you give me a list of textbooks that I should go through one after the other?

Thanks.

Last edited by a moderator: Apr 24, 2017
11. Dec 28, 2009

### Hurkyl

Staff Emeritus
There is an algorithm that produces every theorem: simply iterate through every possible proof one at a time.

A naïve way to do that is to simply iterate through every possible string of symbols one at a time, and keep only those strings of symbols that represent a valid proof.

An 'efficient' algorithm that automatically derives interesting theorems is a much, much more difficult task.

Of course, this algorithm cannot tell you if a statement is not a theorem. You might try to devise a more sophisticated algorithm -- but the incompleteness theorem says that decision algorithms are impossible*. For any algorithm, there exists an input where either the algorithm runs forever without answering, or gives the wrong answer.

The nail in the coffin for Hilbert's program, I believe, is not Gödel's first incompleteness theorem, but the second incompleteness theorem: no (recursively enumerable, first-order, consistent) theory capable of encoding integer arithmetic is capable of proving itself consistent.

Incidentally, I believe that people have devised weaker systems that are capable of proving themselves consistent, but I know nothing about that beyond this sentence.

Gödel had a completeness theorem too, BTW. This theorem states that, for a statement P in a (consistent) first-order theory, the following are equivalent:
• P is provable
• P is true in every set-theoretic model

*: Unless the theory is inconsistent

12. Dec 28, 2009

### farful

Hi eric,

First of all, PM is a wonderful book, and if you have the time and patience you ought to read it.

As for your dilemma concerning mathematical logic...
It seems to me that as you're a physics grad student, you want to learn physics through a reductionist/mechanistic approach ( http://en.wikipedia.org/wiki/Reductionism / http://en.wikipedia.org/wiki/Mechanistic ). Instead, I suggest you not concern yourself with this, and learn through a Holistic ( http://en.wikipedia.org/wiki/Holistic ) approach. I believe most of physics has gone in this direction for the past few decades.

If I'm completely wrong, and you want to learn mathematical logic anyway (as it is fascinating!), the order in which you take courses isn't too important - just take whatever interests you. You should also check out your philosophy department. You ought to know that trying to "build up a structured system of mathematics beginning from basic axioms" doesn't make too much sense... Lots of different beautiful mathematics can be derived depending on which axiom(s) to include/not include.

If you want a good/standard mathematical logic book to read, I recommend Boolos and Jeffrey's Computability and Logic 3rd edition (there's also a 4th/5th edition, but as much as I love Burgess, I think the third edition is much better, and there are also some blatant errors in the latter editions as Burgess redefines certain things, but forgets to make changes everywhere).
I also recommend https://www.amazon.com/Complexity-Guided-Tour-Melanie-Mitchell/dp/0195124413 for light reading (more to do with the holistic thing)

Last edited by a moderator: Apr 24, 2017
13. Dec 28, 2009

### wildman

What I meant by absolute rigor not being possible is that you can't prove everything. That no matter what is done something will always be something left unprovable. What Russel was trying to do in Principia Mathematica (as far as I can see) was to try to set up a system that can prove everything. Godel showed that this wasn't possible (right?).

As a nonmathematician, I probably should be careful using technical terms like rigor since I don't really understand the common meanings (right?).

14. Dec 29, 2009

### Hurkyl

Staff Emeritus
More or less by definition, any consistent system should must have unprovable statements -- the contradictions!

Gödel's incompleteness theorem is often filtered through some additional notion, leading to the common (mis)statement
There exists a true statement that cannot be proven​
Such a statement might come from someone who adheres to mathematical Platonism, or maybe someone who asserts that the finite cardinal numbers constitute the One True System of natural numbers.

I can easily imagine someone adopting such a philosophical position might consider Gödel's first incompleteness theorem a proof of the failure of rigorous methods.

15. Dec 29, 2009

### Staff: Mentor

Correct me if I am wrong, but I have a feeling we've lost the OP question about books...

16. Dec 29, 2009

### kakaz

I cannot catch the point: why unproved statements has to lead to contradictions?

The meaning of Goedel theorem is quite opposite: You may state whatever You like, about Your Unprovable Theorem of Choice, for example that is is true or false and You always find model in which Your Choice will be proper one, and not led to contradiction. Of course there may be other models when it lead to contradiction. This is exactly what is incompleteness theorem about: You cannot prove something which is true at least in one model and false in other one.

As this theorems are not contradictions, what they are? They are choices of freedom: When You are trying to describe natural numbers You choose some axioms ( for example Peano axioms) and then construct some objects: natural numbers. But from Gödel Theorem follows that this is not enough: some of properties of such objects are not defined! You may choice whatever You like when You take into such property. So You may add new axiom, or use different models to check what are consequences of your choice.

It is not connected to Platonism at all ( although Gödel was Platonist, declared one). When You talking about truth, You are taking about something which is completely different than provability. For example take famous Paris Harrington theorem http://en.wikipedia.org/wiki/Paris–Harrington_theorem. There are sentences about natural numbers which are true for each N, and can be proved for every N You choose. But there is no way in Peano Arithmetic, to prove it for general N. You have to use second order theory, or set theory etc. What is mean? It is meaning exactly opposite You wrote: truth is quite distinct thing than provability. Truth is defined in metatheory.

There is similar Tarski theorem about undefinability of Truth which states that You cannot define truth within given theory. You need metatheory, metalanguage etc. It is much more important in my opinion that famous Gödel results, which only states that some sets are not recurrence enumerable.

Of course it was! You do not need to be Platonist to see that conception of use mechanical procedure cannot produce all mathematical truths. Then historically Gödel theorems closes Hilbert mathematical program called formalism. And at the end it also point that constructionism has some limitations.

17. Dec 29, 2009

### Hurkyl

Staff Emeritus
You misread -- I said that, in a consistent theory, the contradictions are unprovable statements.

An obvious fact to be sure, but the point of explicitly stating it was to get wildman thinking about what he really means.

The correct corollary to Gödel's theorem is "Relative to any particular semantics, there exists a true statement that cannot be proven". I was offering Platonism as a reason why one might believe in an absolute semantics, and thus consider Gödel's theorem equivalent to the absolute version "there exists a true statement that cannot be proven".

If you show me a "mathematical truth" that cannot be proven, then I'll show you a statement whose veracity I doubt. :tongue:

18. Dec 29, 2009

### kakaz

Ok, now I accept. Sorry for disturbing.

Of course You may suppose whatever You like about Platonism. But Gödel theorem refer to systems with countable number of axioms. It has also form first level theory which is rather limitation in context of whole Platonism. relation between Platonism and Gödel Theorem are not so simply as You probably states ( do You?).
First od all: in Platonism You state that mathematical objects exists really. That means that there should be no contrary in any proper axiomatization, because axioms states about existing objects. Notice subtle difference: You do not need to prove nothing about proper choice of axioms: if they describe real objects they cannot lead to contrary.
next thing: sentence "there has to be mathematical sentence which is true and is not provable" (You probably mean: in any theory) is nonsense. Why? because even if You are Platonist, You have conception of meta-theory, theories of higher orders, other theories than first one, which may be bigger, and may give You Your sentence as its part etc. This facts ( Platonism, and unprovability) are completely not connected. So someone may made some mistakes in understanding Gödel Theorem - thats obvious, but I will not relate it to Platonism.
Thanks
Kazek

19. Dec 29, 2009

### JSuarez

I won't comment on Gödel's theorem; I read somewhere that standing in a lightning storm holding a metal rod could be harmful to your health. I'm just going to say this: every logician under the sun consider the said theorem a mainstream result and does not endorse ANY of the overblown claims about it that people from other fields sometimes do.

But Borek has made a very valid remark; there's someone who requested measured advice, and it's getting preciously little of that.

So, as a professional logician, here is my advice:

(1) First, you should be aware that Mathematical Logic is a highly technical field, that is very difficult to study on its own (believe me, I've been there; I did a PhD on it with very bad guidance and, sometimes, it was very, very painful).

(2) You should also be aware that, if you expect that mainstream ML is somewhat more rigorous than average math, you'll likely be disappointed. There is an effort to do lay down the concepts involved carefully and to watch out to hidden assumptions, but the proofs of the theorems (the sometimes called "metatheorems", because they are about logical systems) are not, on the average, more rigorous than other theorems in mathematics. Rigour is a complex concept, that involves distinctions between object languages and metalaguages, ambient theories, etc.

(3) But for study, I would definitely recommend that you should start by a general introduction to ML; I particularly recommend Herb Enderton's book "A mathematical introduction to Logic" (there's another famous book, by Elliot Mendelson, "Introduction to Mathematical Logic", but it's somewhat harder to read than Enderton's book); if may complement those by a more recent (and wide-scoped) introduction; here I recommend Peter Hinman's "Fundamentals of Mathematical Logic". These are purely personal recommendations.

(4) After that, I would suggest Set Theory or, at least, a few selected topics of it (the books above already contain brief introductions); the reason is that both Proof and Model Theory depend substantially on a good knowledge of Set Theory. Here, I would recommend that you start by a small, but very good, book by Keith Devlin, "The joy of sets" and complement it with selections from Thomas Jech's book "Set Theory" (it's massive). I would say that a good understanding of ordinals, cardinals and the Von Neumann universe are the essential starting points.

(5) Next comes Computable Function Theory (perhaps even before set theory). A few notions of computability and complexity are essencial, because they deeply intertwine with some of the main results you study in ML (Gödel's first incompletness theorem is one of them). Cutland's "Computability" is the standart (and superbly written) introduction here.

(6) Regarding Model theory, "A shorter model theory", by Wilfred Hodges is probably the best place to start; while for proof theory Troelstra and Schwitchenberg's "Proof Theory" is also a good starting point; but note that these are more advanced fields of ML. In fact, there are very few logicians that are fully fluent on both, and most people in the area usually makes an option between them. There are older books (Takeuti, for PT, Chang and Keisler for MT), but they are now considered too difficult.

But also note that, despite having a common core, ML is a field where specialization is as high as in any other, and there are many areas within it that i didn't even mention (and don't it's humanly possible) so if you intend to proceed with your studies in this field, you'll also have to specialize.

20. Dec 30, 2009

### g_edgar

The introductory material in *Principia* is great. But no one just "reads" the whole thing. Some question whether even Whitehead did.