To derive arithmatic from logic

[friend]

I guess it was Whitehead and Russell who tried to prove that all of math could be derived from the principles of basic logic. Where is that effort today? I'd rather not read a 3 volume set to understand how 1+1=2 can be derived from logic. Is there a more modern text on the subect? Is it still accepted as a valid proof? Thanks.

 

[Rayquesto]

Gosh man. I know what you mean. My teacher is approaching our calculus 1 class using number theory and set theory principles and I feel like I don't know anything half the time, since what he proves makes the process of proving look to simple. I could spend a lot less energy applying 1+1=2 than spending hours understanding why 1+1=2 using a standard of validity. As interesting as it is, I haven't found myself so frustrated to applying logic to prove these type of statements. Even the calculus subject is much easier to some degree. But I'll get through it. Apparently, this guy only teaches this stuff the first week before getting into the real calculus. WHEW!

 

[SW VandeCarr]

I guess it was Whitehead and Russell who tried to prove that all of math could be derived from the principles of basic logic. Where is that effort today? I'd rather not read a 3 volume set to understand how 1+1=2 can be derived from logic. Is there a more modern text on the subect? Is it still accepted as a valid proof? Thanks.

There are many texts and online discussions on the foundations of mathematics. Logic, as expressed in the ZFC axioms of Set Theory together with Peano's Axioms are not sufficient to deduce all results in arithmetic. Goedel showed there cannot be an axiomatic foundation for arithmetic that is complete. That is, there will always be the possibility of contradictions in any formal system and statements known to be true may not be provable in a formal system.

As far as I know, the natural numbers may be constructed up to any arbitrary n using Set Theory , but cannot be deduced by the usual methods of formal logic. That is, we cannot deduce that 1+1=2. In Boolean arithmetic 1+1=1.

 

[friend]

There are many texts and online discussions on the foundations of mathematics. Logic, as expressed in the ZFC axioms of Set Theory together with Peano's Axioms are not sufficient to deduce all results in arithmetic. Goedel showed there cannot be an axiomatic foundation for arithmetic that is complete. That is, there will always be the possibility of contradictions in any formal system and that statements known to be true may not be provable in a formal system.

Does this mean there IS NO derivation of math from logic? For if there were, then math would be complete as logic, right?

 

[SW VandeCarr]

Does this mean there IS NO derivation of math from logic? For if there were, then math would be complete as logic, right?

No. It means that no one has found a way, using deductive logic. I don't know what you mean by a complete logic. Complete with respect to what? With respect to arithmetic, apparently not, if you accept Goedel's proof. Logical systems can be made up at will. But useful logical systems like ZFC cannot be proven to be consistent or complete.

 

[SteveL27]

No. It means that no one has found a way, using deductive logic. I don't know what you mean by a complete logic. Complete with respect to what? With respect to arithmetic, apparently not, if you accept Goedel's proof. Logical systems can be made up at will. But useful logical systems like ZFC cannot be proven to be consistent or complete.

Just to be pedantic ... ZFC can be proven to be consistent or complete. If it can be proven consistent, it's not complete. And if it can be proven complete, it's not consistent. So taking your "or" literally, it's a fact that ZFC is either consistent or complete.

At least that's my understanding of how this works. Let me outline my understanding, and perhaps someone can straighten me out if I've got this wrong.

If ZFC is inconsistent, then ALL statements would be provable; in particular all the true statements would be provable; hence if ZFC is inconsistent, then it's complete.

On the other hand, Godel showed that if ZFC is consistent, then it's incomplete.

So ZFC is provably either consistent or complete, but not both.

 

[friend]

No. It means that no one has found a way, using deductive logic. I don't know what you mean by a complete logic. Complete with respect to what?

I don't know how you could possibly get 1,2,3... from True and False. I don't know how you could possibly get 1,2,3... from Some, None, or All. It seems at some point you're going to end up counting something, which seems to be a totally different procedure from considering the true or false of propositions or the some, none, or all of predicate logic.

So I'm not sure what kind of logic that Whitehead and Russell proved 1+1=2. I think it was set theory, is that right? Then perhaps the incompleteness of arithmatic can be trace to the incompleteness of set theory.

 

[micromass]

As far as I know, the natural numbers may be constructed up to any arbitrary n using Set Theory , but cannot be deduced by the usual methods of formal logic. That is, we cannot deduce that 1+1=2. In Boolean arithmetic 1+1=1.

Uuuuh, what?? That's not true at all. The natural numbers can be constructed in ZFC. That's the whole point of ZFC.

And that 1+1=2 is actually just the definition of 2 in this case, so it can be proven.

 

[micromass]

Just to be pedantic ... ZFC can be proven to be consistent or complete. If it can be proven consistent, it's not complete. And if it can be proven complete, it's not consistent. So taking your "or" literally, it's a fact that ZFC is either consistent or complete.

At least that's my understanding of how this works. Let me outline my understanding, and perhaps someone can straighten me out if I've got this wrong.

If ZFC is inconsistent, then ALL statements would be provable; in particular all the true statements would be provable; hence if ZFC is inconsistent, then it's complete.

On the other hand, Godel showed that if ZFC is consistent, then it's incomplete.

So ZFC is provably either consistent or complete, but not both.

Notice that Godel has two theorems. They are (simplified to ZFC since that interests us)

Theorem 1: ZFC is not both consistent and complete.

Theorem 2: It cannot be proven within ZFC that ZFC is consistent.

 

[Deveno]

a proof of the slightly more interesting proposition that 2+2 = 4 can be found here:

http://us.metamath.org/mpegif/2p2e4.html

note that this is in fact, a "meta-proof", which uses several other proofs that are found in their own links on that page.

the simpler 1+1 = 2 can be found as a link on the page:

http://us.metamath.org/mpegif/df-2.html

indicating it is, indeed, merely a definition.

note that this work builds up the set of complex numbers constructively. the crucial definitions are:

http://us.metamath.org/mpegif/df-c.html (the complex numbers)

(of special interest are the definitions of complex addition:

http://us.metamath.org/mpegif/df-plus.html

and complex multiplication:

http://us.metamath.org/mpegif/df-mul.html)

http://us.metamath.org/mpegif/df-np.html (defining a positive real as a dedekind cut of the positive rationals)

explicit construction of the positive rationals from the natural numbers: http://us.metamath.org/mpegif/df-nq.html

definition of the natural numbers as {1,1+1,1+1+1,...,etc.}: http://us.metamath.org/mpegif/df-n.html

note that any set with the cardinality of the natural numbers (and the axiom of infinity guarantees at least one such set) can be turned into something we call the "natural numbers" by introducing a suitable ordering, and using this ordering to define a successor function. it really does not matter if the elements of such a set are denoted by vertical strokes (or tallies), dots, asterisks, or any other symbol you're happy with. there are 2 "obvious" candidates for such a set:

Ø, {Ø}, {{Ø}}, {{{Ø}}}, etc.
Ø, {Ø, {Ø}}, {{Ø, {Ø}}, {{Ø, {Ø}}}}, {{{Ø, {Ø}}, {{Ø, {Ø}}}}, {{{Ø, {Ø}}, {{Ø, {Ø}}}}}}, etc. (the {x U {x}} construction).

it is largely a matter of taste whether one includes 0 as a natural number or not.

the site i have linked to attempts to present Russell and Whitehead's Principia in "piece-by-piece" form, based on ZF set theory. the home page does a reasonably good job of explaining "how the pieces fit together".

 

[SW VandeCarr]

As far as I know, the natural numbers may be constructed up to any arbitrary n using Set Theory , but cannot be deduced by the usual methods of formal logic. That is, we cannot deduce that 1+1=2. In Boolean arithmetic 1+1=1.

Uuuuh, what?? That's not true at all. The natural numbers can be constructed in ZFC. That's the whole point of ZFC.

And that 1+1=2 is actually just the definition of 2 in this case, so it can be proven.

What's not true at all? I said the the natural numbers can be constructed using Set Theory. But construction is not the same as deduction. Definitions are not deduction. The OP is about deriving arithmetic from (first order) logical deduction.

 

[friend]

a proof of the slightly more interesting proposition that 2+2 = 4 can be found here:

http://us.metamath.org/mpegif/2p2e4.html

note that this is in fact, a "meta-proof", which uses several other proofs that are found in their own links on that page.

the simpler 1+1 = 2 can be found as a link on the page:

http://us.metamath.org/mpegif/df-2.html

Can you recommend a book about all this for someone without a math degree? Thanks.

 

[SW VandeCarr]

Can you recommend a book about all this for someone without a math degree? Thanks.

No math degree is required for the proof that 1+1=2. It's based on the definition of the number 2.

 

[Deveno]

No math degree is required for the proof that 1+1=2. It's based on the definition of the number 2.

to put it in somewhat more lay terms:

"+" (plus, or addition in the USUAL definition) is defined in such a way, that "+1" means the very next "counting number".

1 is defined as the smallest number that can be counted.

so 1+1 IS (equals) "the very next (counting) number after 1", which we have dignified with a special name, 2.

 

[SW VandeCarr]

to put it in somewhat more lay terms:

"+" (plus, or addition in the USUAL definition) is defined in such a way, that "+1" means the very next "counting number".

1 is defined as the smallest number that can be counted.

so 1+1 IS (equals) "the very next (counting) number after 1", which we have dignified with a special name, 2.

I think I agree with this. I interpreted the OP to mean the original intent of Russell and Whitehead to derive mathematics using standard deductive formal logic based on a few simple axioms. By standard logic I mean the system based the concepts like \forall, \exists, \vee, \wedge, ~, etc . Set Theory was just beginning to be accepted by mathematicians at that time. It seems clear that ^ is not the same as +. To say 1 ^ 1 is not sufficient to deduce 1+1, is it? Even using Set Theory, can we say {1}\cup{1}={2}?? I think {1}\cup{1}={1,1}. If it were that simple, I don't think the actual method of constructing the natural numbers from nested iterations of the empty set would have been attempted. In any case, the construction of 2 doesn't allow for the deduction of 1+1=2. So we simply define 2 as equal to (1+1).

 

[friend]

Notice that Godel has two theorems. They are (simplified to ZFC since that interests us)

Theorem 1: ZFC is not both consistent and complete.

Theorem 2: It cannot be proven within ZFC that ZFC is consistent.

to put it in somewhat more lay terms:

"+" (plus, or addition in the USUAL definition) is defined in such a way, that "+1" means the very next "counting number".

1 is defined as the smallest number that can be counted.

so 1+1 IS (equals) "the very next (counting) number after 1", which we have dignified with a special name, 2.

"dignified with a special name, 2"? It seems counting numbers, 1,2,3,... is beyond the scope of the quantifiers of some, none, or all of first order logic. I mean, the definition of union, intersection, and complement are independent of how many elements there are in any set. I think it must have been an ad-hoc add-on to define 2 or 3 as the number of times a process is incremented. That's why ZFC may not be both complete and consistent.

It seems some, none, or all, unions intersections, or complements, 1,2,or 3... are outside the concern of true and false. As I understand it, propositional logic is not concerned with what method is employed to discern the truthvalue of any particular statement. Deductive logic is only concerned with the validity of arguments, and explores the methods of deriving valid argument forms. So when you consider higher forms of logic that consider the quantifiers or the numbers, they cannot be derived strictly from propositional logic. Their axioms and theorems may be true but not derivable from propositional logic alone. Is this the heart of Godels incompleteness theorems? Systems that cannot be derived from true and false may not have the ability to prove some of its statement that may nevertheless be true? In other words, true and false are outside the axioms those systems and is imposed by an outside user of the system.