i.telegraph.co.uk |

*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.”

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

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.

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

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

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.

ReplyDeleteJeffrey,

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

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

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.

DeleteYes, 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.

DeleteAlso, 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)

I have a question.

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

The meaning of "complete" in Godel's completeness and incompleteness theorems are different.

ReplyDeleteSee: [ 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").

nwrickert,

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

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.

ReplyDeleteAFAIK, 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.

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

ReplyDelete[ http://en.wikipedia.org/wiki/Goodstein%27s_theorem ]

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

ReplyDeleteCan you?

=

The solution to which problem?

DeleteRichard: 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.

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

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

Paul,

DeleteI'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.

Massimo,

DeleteI'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.

Paul,

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

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

brainoil,

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

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.

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

brainoil,

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

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

DeleteRichard 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

useto 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?

brainoil,

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

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