About Rationally Speaking


Rationally Speaking is a blog maintained by Prof. Massimo Pigliucci, a philosopher at the City University of New York. The blog reflects the Enlightenment figure Marquis de Condorcet's idea of what a public intellectual (yes, we know, that's such a bad word) ought to be: someone who devotes himself to "the tracking down of prejudices in the hiding places where priests, the schools, the government, and all long-established institutions had gathered and protected them." You're welcome. Please notice that the contents of this blog can be reprinted under the standard Creative Commons license.

Monday, December 24, 2012

The (complicated) relationship between math and logic


i.telegraph.co.uk
by Massimo Pigliucci

Ever since reading my first book on the philosophy of mathematics I've gotten more and more interested in the relationship between math and logic (not to mention, of course, in the idea of mathematical Platonism). That relationship is charmingly explored in the highly entertaining Logicomix, featuring Bertrand Russell as the main hero of an unusual comic book adventure.

More recently, I read two interesting short essays on the topic, one by mathematician Peter Cameron, the other by Sharon Berry, a philosophy PhD student at Harvard. Both essays date from 2010, but good writing is always stimulating, so let’s take a look (besides, this isn’t a field in which progress is made at lightening speed, exactly).

According to Cameron, there are two roles that logic plays in mathematics. The first deals with providing the foundations on which the mathematical enterprise is built. As he puts it: “No mathematician ever writes out a long complicated argument by going back to the notation and formalism of logic; but every mathematician must have the confidence that she could do so if it were demanded.” The second role is played by logic as a branch of mathematics, on the same level as, say, number theory. Here, according to Cameron (and who am I to disagree) logic “develops by using the common culture of mathematics, and makes its own rather important contributions to this culture.”

Of course, you just can’t talk about this stuff without — sooner rather than later — stumbling upon Gödel’s famous “incompleteness” theorems (there is two of ‘em), but before getting there Cameron reminds his readers of the difference (in math) between a sound and a complete system: “A system is sound if all its theorems are logically valid [i.e., are true on every interpretation], and is complete if all its logically valid formulae are theorems.” Cameron says that a common misunderstanding of Gödel’s results is that he proved that no mathematical system can be sound and complete at the same time. On the contrary, Cameron reminds his readers that two important systems have been proven to be both sound and complete: propositional (Boolean) logic and first-order logic. The latter is particularly important because it is the type of formalism in which most (but not all!) math is actually framed.

So, to recap our progress so far: Cameron tells us that the relationship between logic and math is not along the lines of one being a branch of the other, exactly. Rather, certain logical systems can be deployed inside mathematics, while others are in an interesting sense outside of it, meaning that they provide (logical) justification for math. At least, that’s if I understand Cameron correctly, I’d be happy to be shown the error of my ways if need be.

Berry’s essay approaches the issue of the relationship between logic and math in a more comprehensive and systematic manner. She states that the answer to the question depends (surprise, surprise!) on what one means by “logic.” In particular, she provides a useful classification of five meanings one might have in mind when using the word:

1. First order logic (see above).
2. Fully general principles of good reasoning.
3. A collection of fully general principles which a person could learn and apply.
4. Principles of good reasoning that aren’t ontologically committal.
5. Principles of good reasoning that no sane person could doubt.

[We will not get into a discussion of what constitutes sanity insofar as possibility #5 is concerned. Another time, perhaps.]

Berry’s first point is that we know that it is not possible to program a computer to produce all and only the truths of number theory, but it is possible to program such computer to produce all the truths of first order logic. Which means that math is not the same as logic if one understands the latter to be the first order stuff (option #1 above). Berry immediately adds that if we make the further assumption that human reasoning can be modeled in a computer program (which, personally, I don’t actually think has been established), then logic doesn’t capture all of math also in cases #3 and #5 above.

What about #2, then? To quote Berry: “If by ‘logic’ you just mean ... fully general principles of reasoning that would be generally valid (whether or not one could pack all of these principles into some finite human brain) — then we have no reason to think that math isn’t logic.” I am very sympathetic to this broader reading of logic, but we are still left with option #4 above.

Apropos of that Berry reminds her readers that standard math is reducible to set theory, and that the latter in turn has been shown to be reducible to second-order logic, thus implying that mathematics is, after all, a branch of logic. [I will leave it to the reader to dig into Berry’s issue about “ontological commitments,” which hinges on the relationship between the ontology of abstract objects and the inferential rules we deploy while using said objects. It makes for light reading after dinner...]

Berry’s conclusion is that “it is fully possible to say ... that math is the study of ‘logic’ in the sense of generally valid patterns of reasoning. However, if you say this, you must then admit that ‘logic’ is not finitely axiomatizable [because of Gödel’s theorems!], and there are logical truths which are not provable from the obvious via obvious steps (indeed, plausibly ones which we can never know about). ... What Incompleteness shows [then] is that not all logical truths can be gotten from the ones that we know about.” You’ve got to love this stuff! Or am I just weird?
Posted by at
Labels: , , ,

24 comments:

  1. Jeffrey ShallitDecember 24, 2012 4:46 PM

    I don't think it is at all surprising that there are mathematical truths that have no proofs. On the contrary, it is more surprising that we can prove as much as we can! There are very likely statements that are going to be true for "random" reasons. Freeman Dyson gives the following example: there is no power of 2 (say 2^n with n >= 1) whose reverse (that is the reversal of its base-10 expansion) is a power of 5. This seems very likely to be true simply because both sequences are sparse and "unrelated", and it might have no proof.

    ReplyDelete
    Replies
    1. UnknownDecember 25, 2012 11:24 AM

      Jeffrey,

      But the idea is that in a deductive system one should be able to prove truths, since there is nothing that is truly "unrelated." Another way to put it is that math is not about empirical facts, so that the concept of stochasticity shouldn't apply. Worse, the incompleteness theorems prove (logically) that some truths within certain kinds of systems cannot be proven. It's a bit more mind boggling than Dyson seems to think.

      Delete
    2. AnonymousDecember 25, 2012 6:04 PM

      But the idea is that in a deductive system ...

      I don't see mathematics as a deductive system. Yes, we make deductions from axioms. But coming up with useful axioms is also part of mathematics.

      I see mathematics as more of a modeling system.

      Another way to put it is that math is not about empirical facts, so that the concept of stochasticity shouldn't apply.

      I'm pretty sure that's why Jeffrey put "random" in scare quotes.

      Worse, the incompleteness theorems prove (logically) that some truths within certain kinds of systems cannot be proven.

      The way that I look at it, the incompleteness theorems show that mathematics is interesting.

      Mathematicians don't look at the incompleteness theorems the way that philosophers do. Those of us who are not working in mathematical logic (and that is most mathematicians) tend to see it as an esoteric part of mathematical logic with little or no relevance to the kind of mathematics that they do.

      Delete
    3. peteDecember 25, 2012 9:28 PM

      I definitely agree with Massimo's description of the relation between math and logic, and claiming that it is reducible to second order logic and is thus a branch of logic makes perfect sense. As far as nwrickert's points on mathematics, I agree that mathematics is a modeling system insofar as many things (quite possibly everything) in reality can be decomposed and understood by mathematics, but that fact in itself also lends strong support for thinking of math and logic as fundamental in a very deep sense. As far as the incompleteness theorem, its good to point out the misconception that the theorem suddenly makes math faulty or inadequate in some way. To make things clear, the second incompleteness theorem simply maintains that if a powerful enough system is consistent, then it can never be complete. ZFC set theory, or any of the several other similar alternative foundational set theories, are all thought to be totally consistent, and everything that can be deduced from them is still absolutely true. The incompleteness theorem simply suggests that the body of axioms has to be expanded if we want to prove more mathematical statements. With our mathematical knowledge ever expanding, it seems perfectly reasonable to assume that we could add more axioms and over time expose more and more of the vast ocean of mathematics that Godel proved will forever be there for us to explore.

      Delete
    4. FinitowilliamsDecember 08, 2013 10:11 AM

      Yes, but incompleteness also suggests that if your working on a math problem, you can't rely on the set of statements that rest in front of you - you have to look outside of the box, and find your answers in separate set of axioms. The relevance of this, is in establishing the importance of creative type thinking in math - the process of coming up with theorems and proving them via parralel axioms, depend heavily on associtive/heuristic type thinking. However, creativity is not required in a logical system, because it is self-coherent. Logic cannot describe math, without depending on math.

      Also, second order axioms of logic, are weaker desciptions of Peona arithimetic (in themselves depend on Peona axioms) . Only if one wants to make tautological assumptions, is logic part of math. However, logic does have one true role in math, when it comes to a type of inductive process (9th axiom)

      Delete
  2. RichardDecember 25, 2012 6:15 PM

    I have a question.

    What does it mean to say "first order logic is complete" (in the sense of Godel's first incompleteness theorem)? I never thought of first order logic as an axiomatic system, but as a logical system in which axiomatic systems (e.g. number theory) can be developed. For example, it might be that the twin prime conjecture is not decidable, but it is a statement of first order logic, is it not?

    Perhaps I'm missing something.

    ReplyDelete
  3. Philip ThriftDecember 26, 2012 7:49 AM

    The meaning of "complete" in Godel's completeness and incompleteness theorems are different.
    See: [ http://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem#Relationship_to_the_incompleteness_theorem ]

    Putting the two together means there is a "non-standard" model of Peano Arithmetic. One example: [ http://en.wikipedia.org/wiki/Hypernatural ].

    Bottom line: I don't think a distinction between logic and mathematics can be made (at least an argument based on "completeness").

    ReplyDelete
  4. UnknownDecember 26, 2012 8:51 AM

    nwrickert,

    > I don't see mathematics as a deductive system. Yes, we make deductions from axioms. But coming up with useful axioms is also part of mathematics. <

    True enough, but axioms are posited, they do not come from empirical evidence (as in the case of science), so math and logic are still deductive forms of reasoning, though they need to start somewhere (the axioms).

    > I see mathematics as more of a modeling system. <

    Modeling of what? (Apart from the obvious case of math applied to science.)

    > Those of us who are not working in mathematical logic (and that is most mathematicians) tend to see it as an esoteric part of mathematical logic with little or no relevance to the kind of mathematics that they do. <

    “Relevance” is a treacherous word here. Much of what mathematicians, logicians and even scientists do is not “relevant.” But mathematical logic is obviously pertinent if the question is that of the relationship between math and logic.

    Richard,

    > it might be that the twin prime conjecture is not decidable, but it is a statement of first order logic, is it not? <

    My understanding is, as I wrote in the post, that math is not the same as first order logic, because - according to Berry - while it’s possible to program a computer to derive all the truths of first order logic, it is not possible to so with all mathematical truths. Remember that the difference between first and higher order logics is that in the latter predicates have other predicates of functions as arguments. Another way to put it (if it helps!) is that predicates in first order logic can be interpreted as sets, while predicates in higher order logics can be interpreted as sets of sets.

    pete,

    thanks, that was helpful!

    Philip,

    > I don't think a distinction between logic and mathematics can be made (at least an argument based on "completeness") <

    Well, again, that depends on whether one thinks of “logic” as first order, second order, or any of the other ways listed by Berry.

    ReplyDelete
  5. RichardDecember 26, 2012 1:16 PM

    Philip: Understood -- but I don't think it answers my question. Take my example of the TPC -- if it is undecidable, then either it, or its negation, is a case of a true statement that can't be proven true -- and so an example of the incompleteness of arithmetic. Yet it is a statement in the domain of first-order logic, if I understand the meaning of the phrase.

    AFAIK, non-standard arithmetics shouldn't change the truth value of the TPC. My question is really about why first-order logic, which isn't an axiomatic theory, can be classified according to completeness (or if in fact it can be).

    Massimo: "while it’s possible to program a computer to derive all the truths of first order logic, it is not possible to so with all mathematical truths" -- Again I'm not satisfied. Are there "truths of first order logic", beyond the rules of inference themselves? Or are you just saying that the rules of inference can be derived by such a computer program? I don't really see rules of inference as axioms in the sense of Peano arithmetic axioms or ZFC axioms. I thought the first incompleteness theorem limited the extent to which statements of a formal language can be partitioned into true and false by applying the rules of inference to a set of axioms, so you need axioms for the theorem to have meaning. Perhaps it's just a problem of semantics that I am having.

    As you can probably guess from what I have said, I see logic as something underlying mathematics, something more fundamental, so that logic is not simply a branch of math.

    ReplyDelete
  6. Philip ThriftDecember 26, 2012 3:30 PM

    Richard: It could be (I think) that TPC is true but unprovable in PA, like Goldstein's Theorem ("a 'natural' example of a true statement that is unprovable in Peano arithmetic").
    [ http://en.wikipedia.org/wiki/Goodstein%27s_theorem ]

    ReplyDelete
  7. = MJADecember 27, 2012 3:50 AM

    Mathematics = Philosophy at an immeasurably infinite point of truth. Einstein couldn't find the solution,
    Can you?

    =



    ReplyDelete
  8. ZalDecember 27, 2012 8:08 AM

    Richard: First order logic is both complete (Gödel 1929) and undecidable (Church 1936). The former says that there exists a proof for every true proposition, the latter that there does not exist a general procedure for deciding whether a given proposition is true or false. This of course does not say that undecidable propositions exist, only that they may.

    ReplyDelete
  9. Paul PaoliniDecember 28, 2012 2:47 AM

    From the OP: "Apropos of that Berry reminds her readers that standard math is reducible to set theory, and that the latter in turn has been shown to be reducible to second-order logic, thus implying that mathematics is, after all, a branch of logic."

    This view seems a consequence of some questionable definitional choices, if not question-begging. In particular, it involves choosing to call the ancient method of formal development (AMFD) (i.e., the definition/ axiom/ proof/ theorem method) associated with the mathematical tradition "logic" (where 'logic' means mathematical logic), and restricting 'mathematics' to something more narrow than the AMFD, i.e., to a numbery, geometrical, sort of thing that from the point of view of "logic" is just one realm of formalizable theories among others.

    An alternative view, one that I think is fairer to the mathematical tradition, and generally makes more sense, is that mathematical logic is just the mathematical treatment of logic in a more basic sense. On this view, mathematical logic is just another branch of mathematics, and the relation between it and the rest of mathematics is a matter internal to mathematics, though such might be of interest to philosophers of mathematics and metaphysicians (though I don't see why in the latter case).

    An apparent assumption of the above-quoted view is that logic just is mathematical logic, as opposed to something more basic than its mathematical development. This assumption has odd consequences, such as that logic did not exist until there were formal systems of logic, that use of the word 'logic' and its cognates always alludes to formal systems, and that it is nonsense to speak of aspects of logic that have not yet been formalized (for logic just is formalization).

    The view I favor regarding what logic most basically is is that it is an aspect of natural language. In particular, it is natural language seen as an instrument for making true/false claims about the world. To illustrate, the notion of logical form arises from parsing language into units conceived as significant to truth-value. Two sentences may differ under such parsings, i.e., in logical structure, but have the same logical form at some level of respective structure. Generally, truth conditions are the reference point for conceptions of logical structure, and logic might be conceived generally as language from the point of view truth-values. Any parsing of language made on the basis of truth-significance is a logical parsing, which is why we call 'and', 'all', 'every', and so on, logical words. All this exists in language prior to symbolization, axiomization, and so on; those are just mathematical artifices. Now, in this more basic sense of logic, I don't think logic has any special relation to mathematics.

    ReplyDelete
    Replies
    1. UnknownDecember 28, 2012 12:16 PM

      Paul,

      I'm a bit confused. You are seriously arguing that logic and math have *no relation* at all? Yet your argument seems to imply at the least Berry's #4, and even if you prefer #3 or #5 it still doesn't follow that the two are unrelated.

      I grant you that for the argument that math is part of (second order) logic one does have to restrict one's definition of math, though I'm not so sure that a lot of mathematicians themselves would object.

      Finally, she is talking about the relationship between (broadly construed) math and logic, not just focusing on mathematical logic, which is a well defined subset of logic.

      Delete
    2. Paul PaoliniDecember 28, 2012 3:50 PM

      Massimo,

      I'm saying that logic broadly construed has no *special* relation to mathematics (rather than *no relation at all*), while mathematical logic is a branch of mathematics.

      Regarding the definition of 'logic broadly construed' I don't think Berry's suggestion in terms of "good reasoning principles" works. (I was going to mention this above but I was already going on too long.) The problem with such principles is that it's not clear why e.g., ontological non-committal should make a principle a part of logic. I think by the time this is explained it will be clear that such principles are consequential to the nature of logic rather than definitive of it.

      It seems to me that if logic (broadly construed) must be identified with a set, the best candidate would be the set of logical truths, where such are conceived as expressible in either natural or formal languages, but arising principally from natural language. Logical truths of course are statements that are true simply in virtue of their logical structure. Any valid deduction or deductive pattern can be transformed into a logical truth; a valid deduction is essentially just an entailment statement (one formed with the intensional 'entails') that is true simply in virtue of its logical structure.

      This view makes good sense of what it means to think illogically; to think illogically is to think inconsistently with logical truths, i.e., logic.

      Delete
    3. UnknownDecember 28, 2012 7:48 PM

      Paul,

      yes, actually that clarifies things. I'll need to cogitate on this a bit more...

      Delete
  10. AnonymousDecember 28, 2012 9:29 PM

    Which means that math is not the same as logic if one understands the latter to be the first order stuff (option #1 above).

    I don't understand. So first order Peano arithmetic, since it is sound, consistent and complete due to the existence of non-standard numbers, is not math, but second order Peano arithmetic is math because it is incomplete? It's a strange claim.

    if we make the further assumption that human reasoning can be modeled in a computer program (which, personally, I don’t actually think has been established)

    I'm surprised that you are still of this opinion. In your debate with Yudkowsky, he specifically asked you whether you have a proof that Church-Turing thesis is false. You said no. Then you go ahead and say machines won't be conscious. Of course you can do that. But then you have to bite the bullet and admit philosophical zombies are possible. You don't want to do that either.

    I mean it's really simple. Either you should deny Church-Turing thesis, or you should admit that philosophical zombies are possible, if you want to hold on to your opinion that machines acting just like humans and say "I think therefore I am" are not conscious.



    ReplyDelete
    Replies
    1. UnknownDecember 29, 2012 8:19 AM

      brainoil,

      I think you confused the meaning of that sentence:

      > So first order Peano arithmetic, since it is sound, consistent and complete due to the existence of non-standard numbers, is not math, but second order Peano arithmetic is math because it is incomplete? <

      All of math, according to that author, can be interpreted as logic *if* by logic we mean the second order stuff. But it cannot if we mean first order logic. First and second order here refer to logic, not math, or arithmetic.

      > I'm surprised that you are still of this opinion. In your debate with Yudkowsky, he specifically asked you whether you have a proof that Church-Turing thesis is false. <

      This is a side point here, so I will likely come back to this in a future post, but I find the constant throwing into the equation of the C-T thesis to be largely irrelevant, for at the least the following reasons:

      * The thesis cannot be proven formally. Yes, it is broadly accepted in the computational community, but hardly an unquestionable piece of knowledge.

      * The notion of what it means to be a calculable function according to thesis is vague and intuitive.

      * It is still an open question whether there are deterministic physical processes that elude a Turing machine.

      * It is, crucially, an open question whether the processes working inside a human brain are all of the type that can be calculated by a Turing machine.

      * It remains to be established that the brain works solely (or even largely) by computable algorithms.

      So, yes, at the moment I can still eat my zombies and not have to go with Turing...

      Delete
  11. AnonymousDecember 29, 2012 10:21 AM

    Not being a native English speaker, I really could be confused about the meaning of that sentence, but if that is the case, it's not obvious to me.

    What Berry is saying is this (as I understand it). First order logic is completely computable. Number theory is not. So math is not the same as logic if we consider logic only means first order logic.

    It is trivially true, but it's arbitrary. It's like saying not all women are women if by women we only mean blondes. What is number theory was completely computable? Would that be evidence that all of math in fact can be interpreted as logic? It doesn't seem like that to me.

    This is why I brought up Peano arithmetic. The kind of PA we use is incomplete because we rule out non-standard numbers using second-order logic. But if we don't use second order logic, and use only first order logic, we'd be left with non-standard numbers in Peano arithmetic and this PA would be completely computable. It wouldn't have any effect on our practical affairs, although your second favorite Singularitarian Yudkowsky thinks that non-standard numbers would mean that Turing machines would halt at a time T (I don't know why). So in that case, would we consider that it Peano arithmetic can be interpreted as logic?

    ***

    About the side point, at least your newer position is consistent, unlike the position you held during your debate with Yudkowsky. In the debate Yudkowsky asked "Do you claim to know that Church Turing thesis is false?" and you replied "No, I don't. I'm just not convinced that it is relevant to what we are talking about." Then you said that machines won't be conscious. This would mean that there would be machines that behave exactly the same way that humans behave (write philosophy papers about morality etc.), but still won't be conscious, which means that the machine is a philosophical zombie.

    ReplyDelete
    Replies
    1. UnknownDecember 29, 2012 12:26 PM

      brainoil,

      I don't think your blondes/women analogy works here. But I obviously can't explain it any better, so you may want to read Berry's original post, linked in the main article.

      > at least your newer position is consistent, unlike the position you held during your debate with Yudkowsky. <

      I disagree, it's the same position, though perhaps better articulated. When I told Yudkowsky that I didn't think the C-T thesis was relevant I meant what I explained in this thread. And when I say that machines won't (likely) be conscious what I mean is that they will (likely) not have the type of consciousness we humans have, if indeed the latter depends on certain biophysical substrates. But that should be uncontroversial, really. It's like saying that you won't have carbon-type chemistry if you substitute carbon atoms with silicon ones. Of course you won't.

      Delete
    2. AnonymousDecember 29, 2012 9:01 PM

      I don't think my blonde analogy is perfect either, but it says what I want to say. I think the distinction Berry draws is true, but arbitrary, unless there's a significant proportion of mathematicians and logicians who think logic is composed only of first order logic (you better have a rock solid reason to believe that).

      Richard above makes a very important point. It doesn't make a lot of sense to compare number theory and first order logic in terms of whether they can be completely computed because it is really like comparing blonde-ness and woman-ness. On one hand you have number theory, an axiomatic system in which Godel's statement is true. On the other hand you have first order logic which you use to make axiomatic systems like first order Peano arithmetic. It doesn't make a lot of sense the same way comparing humans with human DNA doesn't make sense.

      ***

      That may be true. Most serious people are more articulate in writing than in speaking. I don't want to talk about it here anymore because this is not relevant to the topic. Just a quick question. Are you completely against functionalism?

      Delete
    3. UnknownDecember 30, 2012 8:55 AM

      brainoil,

      I don't really have a bone in this fight, I'm just an interested outside observer. I tend to think that logic and math are deeply related, and at the very least that they are two examples of general deductive formalize reasoning.

      > Are you completely against functionalism? <

      I guess so. I would need a form of limited functionalism grounded in biophysics. My best guess at this point is that there likely are multiple ways of realizing consciousness, but that these are not (entirely) substrate dependent. What range of substrates can support consciousness is an open empirical question, but I think anyone who thinks substrates don't matter doesn't take biology seriously enough (and is guilty of a form of implied dualism).

      Delete
  12. FinitowilliamsDecember 08, 2013 9:52 AM

    Math depends on a distinct set of axioms than logic. Second order logical axioms can only weakly define Peano arithmetic. However, the 9th Peona axiom, induction, does depend on logic. But math is about discovering ways to model reality, far more-so, than processes involving deduction/induction (which is a method involved in proofs). For that reason, tests of math aptitude should focus on a sense of equational reasoning (for example equation balancing), calculatory ability, and associative learning (which is some gauge of a person's general 'intuitive' ability). In essence, (and with respect to incompleteness), math requires proving things by looking outside of a system. It is more complex than logic, but not as self-coherent. Math ability is limited by logic, just as much as it is by the equational sense, and associative type thinking. Math can tap into truths that logic is blind to, but formal proofs may come long afterwards.

    ReplyDelete

Note: Only a member of this blog may post a comment.

Subscribe to: Post Comments (Atom)