Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

To derive arithmatic from logic

  1. Jan 20, 2012 #1
    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.
     
  2. jcsd
  3. Jan 20, 2012 #2
    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!
     
  4. Jan 21, 2012 #3
    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.
     
    Last edited: Jan 21, 2012
  5. Jan 21, 2012 #4
    Does this mean there IS NO derivation of math from logic? For if there were, then math would be complete as logic, right?
     
  6. Jan 21, 2012 #5
    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.
     
  7. Jan 21, 2012 #6
    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.
     
    Last edited: Jan 21, 2012
  8. Jan 21, 2012 #7
    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.
     
  9. Jan 21, 2012 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
  10. Jan 21, 2012 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
  11. Jan 22, 2012 #10

    Deveno

    User Avatar
    Science Advisor

    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".
     
  12. Jan 22, 2012 #11
    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.
     
    Last edited: Jan 22, 2012
  13. Jan 22, 2012 #12

    Can you recommend a book about all this for someone without a math degree? Thanks.
     
  14. Jan 22, 2012 #13
    No math degree is required for the proof that 1+1=2. It's based on the definition of the number 2.
     
    Last edited: Jan 22, 2012
  15. Jan 22, 2012 #14

    Deveno

    User Avatar
    Science Advisor

    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.
     
  16. Jan 23, 2012 #15
    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 [itex] \forall, \exists, \vee, \wedge,[/itex] ~, 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}[itex]\cup[/itex]{1}={2}?? I think {1}[itex]\cup[/itex]{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).
     
    Last edited: Jan 23, 2012
  17. Jan 23, 2012 #16
    "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.
     
    Last edited: Jan 23, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook