Is Principia Mathematica outdated?

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

 

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

 

[Hurkyl]

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.

 

[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')

 

[1qaz2wsx3edc]

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

 

[D H]

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.

 

[robert Ihnot]

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

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.

 

[Hurkyl]

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')

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 Z₅. 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)

 

[Hurkyl]

Godel's Incompleteness Theorems only pertain to mathematical structures of sufficient complexity.

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

 

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

 

[Hurkyl]

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

 

[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/dp/0195124413/?tag=pfamazon01-20 for light reading (more to do with the holistic thing)

 

[wildman]

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.

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

 

[Hurkyl]

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.

 

[Borek]

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

 

[kakaz]

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

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.

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.

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.

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.

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.

 

[Hurkyl]

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

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.

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.

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

You do not need to be Platonist to see that conception of use mechanical procedure cannot produce all mathematical truths.

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

 

[kakaz]

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.

Ok, now I accept. Sorry for disturbing.

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

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 - that's obvious, but I will not relate it to Platonism.
Thanks
Kazek

 

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

 

[g_edgar]

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

 

[disregardthat]

You're making things too complicated.
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)

Wouldn't the undecidability in this case only be cause by the lack of specification? The very statement is rather ambiguous, for it does not state which set x and y are picked from. If this set was specified, and thus the group, wouldn't the undecidability fade away (at least in most/some cases)?

 

[Hurkyl]

If this set was specified, and thus the group, wouldn't the undecidability fade away (at least in most/some cases)?

Sure. But group theory is a more interesting subject than, say, Z/3 theory.

 

[disregardthat]

Sure. But group theory is a more interesting subject than, say, Z/3 theory.

I see your point, but are you saying that this kind of undecidability has anything to do with genuinely undecidable statements, as in not provable by first order logic in ZFC?

 

[g_edgar]

"ZFC" is a system of axioms. There are propositions P (for example CH) for which: there are models of ZFC where P holds, and there are other models of ZFC where P fails.

Isn't that exactly the same situation as a proposition that holds in some groups and not others, and thus we conclude the set of axioms for groups is not complete?

 

[Tac-Tics]

The Principia Mathematica is an excellent study in rigor. But you're probably better off learning to program. The level of rigor is the same.

 

[disregardthat]

"ZFC" is a system of axioms. There are propositions P (for example CH) for which: there are models of ZFC where P holds, and there are other models of ZFC where P fails.

Isn't that exactly the same situation as a proposition that holds in some groups and not others, and thus we conclude the set of axioms for groups is not complete?

I don't know, is it? Is an ambiguous statement considered a statement at all? I would never call an ambiguous statement a well-defined statement (which a genuine mathematical proposition is required to be). Do you propose that CH is undecidable because of the lack of specification, or something isomorphic to a lack of specification? I have always thought that CH was (at least supposed to, ignoring the debate) be a well-defined genuine mathematical proposition. Gödel's incompleteness theorem states (at least essentially) that there exists well-defined statements (in a sufficiently powerful axiomatic system of first order logic) which are undecidable, and they are not undecidable because of internal ambiguity.

 

[Hurkyl]

Is an ambiguous statement considered a statement at all?

Ambiguous is not the word you're looking for. The correct word is "abstract", I think.

$\forall x$ and $\exists x$ are unbound quantifiers -- x's domain is the entire universe of the theory. $\forall x \exists y: y + y = x$ is a "genuine" proposition of the "theory of a group", at with the English usage of "genuine".



You are thinking of semantics -- in particular the idea of a (set-theoretic) model. If you choose a particular set, and a nullary, unary, and binary operation on that set which satisfy the statements of the "theory of a group", then you have formed a model of that theory". But such things are things that we can do with theories, not part of the theories themselves.


I should point out that even complete theories -- such as first-order Euclidean geometry -- usually don't have unique models up to isomorphism; if there is an infinite model, then "nonstandard" models of all larger cardinalities exist too.



Incidentally, while group theory is primarily interested in the relationships between different models of "the theory of a group" -- i.e. is studying semantics -- other subjects like Euclidean geometry is often more interested in dealing with the theorems of the theory -- i.e. is studying syntax.

 

[disregardthat]

$\forall x$ and $\exists x$ are unbound quantifiers -- x's domain is the entire universe of the theory. $\forall x \exists y: y + y = x$ is a "genuine" proposition of the "theory of a group", at with the English usage of "genuine".

I agree that it is a "genuine" and meaningful statement within a specified theory, but I'd say that the statement is ambiguous if stated outside the context of any specified or assumed theory - leaving $\forall x$ and $\exists x$ as quantifiers of some unspecified sets. I see a large difference between a statement stated outside a specified context, and a statement state inside a specified context. Perhaps is this distinction illusionary, and if so, is the statement equivalent in "form of undecidability" (undecidable in the same sense) to a theorem like CH?

Perhaps there is no way of deciding in general whether a statement is properly specified? (in an intuitive interpretation of the word "specification")

 

[Hurkyl]

All (quantified) statements of ZFC involve unbound quantifiers, so I really can't figure out what you're thinking.

 

[Jimmy Snyder]

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

I've heard it said that no one has ever read it through. Whitehead didn't read all of what Russell wrote and Russell didn't read all of what Whitehead wrote.

 

[disregardthat]

All (quantified) statements of ZFC involve unbound quantifiers, so I really can't figure out what you're thinking.

If undecidability is not unprovability, but merely the lack of a specific context, then I wouldn't treat statements involving unbound quantifiers as equivalent in type to statements involving bound quantifiers or no quantifiers at all, because of our inability to judge their truth value. I agree with that they are meaningful, but I can not see how they can possesses any truth value in general independent of context - and is thus merely statements, not theorems.

I interpreted undecidable as equivalent to unprovable in the beginning, but I see now that it does not make sense.

 

[Hurkyl]

If undecidability is not unprovability

The very definition of "P is undecidable" is that neither "P" nor "not P" is provable.

I can not see how they can possesses any truth value in general independent of context - and is thus merely statements, not theorems.

Statements don't have truth values, not even tautologies. "Truth" is a matter of semantics -- e.g. each set-theoretic interpretation yields a truth valuation: a function that maps the set of statements to the set {true, false}. (and a model of a theory is one in which each of its theorems map to true)

 

[disregardthat]

The very definition of "P is undecidable" is that neither "P" nor "not P" is provable.

Then, as I previously asked: is it true that any unprovable statement is unprovable merely because of the lack of context? Is, for example, CH undecidable because of the lack of some specific theory in which CH is treated?

 

[Hurkyl]

Oh! It just struck me that maybe you don't know that semantics is a technical term.

In formal logic, the syntax, heuristically speaking, deals with form -- languages, grammar, provability, theories, and the like.

Semantics, heuristically speaking, deals with meaning -- studies models of theories, truth valuations on languages, and the like.

 

[Hurkyl]

Then, as I previously asked: is it true that any unprovable statement is unprovable merely because of the lack of context? Is, for example, CH undecidable because of the lack of some specific theory in which CH is treated?

What precisely do you mean by context?

CH is undecided in ZFC because it is neither provable nor disprovable. CH is, of course, provable in ZFC+CH.

For any particular (classical) model of ZFC, the truth value of CH is either true or false.