## Algorithms and logic

Philosophical, mathematical and computational logic, linguistics, formal argument, game theory, fallacies, paradoxes, puzzles and other related issues.

### Algorithms and logic

What is the relationship between algorithms and logic?

Can all of logic or at least logical processes be modelled by a set of algorithms?

Is there any logic that cannot necessarily be modelled by algorithms?

My viewpoint is that all of logical processes CAN be modelled using algorithms.

Does anyone disagree?

A_Seagull
Member

Posts: 120
Joined: 29 Apr 2017

### Re: Algorithms and logic

A_Seagull » February 14th, 2018, 3:14 pm wrote:What is the relationship between algorithms and logic?

Can all of logic or at least logical processes be modelled by a set of algorithms?

Is there any logic that cannot necessarily be modelled by algorithms?

My viewpoint is that all of logical processes CAN be modelled using algorithms.

Does anyone disagree?

We know we can not fully model the arithmetic of the positive integers with any consistent set of axioms. No algorithmic procedure can decide all questions of number theory.

So if you include the arithmetic of the positive integers in the category of logic, that would be a counterexample to your claim.

However, I can see how one would reject including arithmetic inside logic.

someguy1
Member

Posts: 753
Joined: 08 Nov 2013

### Re: Algorithms and logic

someguy1 » February 15th, 2018, 2:43 pm wrote:
A_Seagull » February 14th, 2018, 3:14 pm wrote:What is the relationship between algorithms and logic?

Can all of logic or at least logical processes be modelled by a set of algorithms?

Is there any logic that cannot necessarily be modelled by algorithms?

My viewpoint is that all of logical processes CAN be modelled using algorithms.

Does anyone disagree?

We know we can not fully model the arithmetic of the positive integers with any consistent set of axioms.

Do you have a reference or evidence for this?

No algorithmic procedure can decide all questions of number theory.

Questions about logical systems are not necessarily a part of logic.

So if you include the arithmetic of the positive integers in the category of logic, that would be a counterexample to your claim.

I would certainly include maths as a logical system. But I am not sure your 'counter examples' are actually counter examples.

However, I can see how one would reject including arithmetic inside logic.

Computers are logical machines. So far as I can tell they are capable of modelling and producing conclusions with regard to any form of logic. Yet the programs and software by which all computers operate invariably originated as a set of algorithms.

A_Seagull
Member

Posts: 120
Joined: 29 Apr 2017

### Re: Algorithms and logic

A_Seagull » February 14th, 2018, 10:32 pm wrote:
Do you have a reference or evidence for this?

https://en.wikipedia.org/wiki/G%C3%B6de ... s_theorems

If as you say you "include mathematics as a logical system," your claim stands refuted.

But like I say, this depends crucially on exactly what you mean by logic.
someguy1
Member

Posts: 753
Joined: 08 Nov 2013

### Re: Algorithms and logic

someguy1 » February 15th, 2018, 4:35 pm wrote:
A_Seagull » February 14th, 2018, 10:32 pm wrote:
Do you have a reference or evidence for this?

https://en.wikipedia.org/wiki/G%C3%B6de ... s_theorems

If as you say you "include mathematics as a logical system," your claim stands refuted.

But like I say, this depends crucially on exactly what you mean by logic.

LOL Why didn't you say you were talking about Gödel's theorems!

I don't think Gödel's theorems are applicable in this case as they rely upon the assumption that mathematics is 'complete' and that every 'mathematical statement' can be ascribed the tag of either true od false.

Such assumptions are not necessary for the logical processes of mathematics to be applied.

A_Seagull
Member

Posts: 120
Joined: 29 Apr 2017

### Re: Algorithms and logic

A_Seagull » February 15th, 2018, 1:58 pm wrote:
LOL Why didn't you say you were talking about Gödel's theorems!

Why didn't you recognize the statement?

If I said that every particle of mass in the universe attracts every other particle with a force proportional to the product of their masses and the inverse square of the distance between them, would you demand a reference? Or would you immediately recognize Newton's law of gravity? Since you are making a claim about mathematical logic, I wonder why you did not recognize the first incompleteness theorem when I stated it. You seem to have heard the words but not understood the meaning.

A_Seagull » February 15th, 2018, 1:58 pm wrote:I don't think Gödel's theorems are applicable in this case as they rely upon the assumption that mathematics is 'complete'

That is not true. On the contrary, Gödel's first incompleteness theorem shows that any axiomatic system powerful enough to model the arithmetic of the natural numbers must be incomplete. There is no assumption of completeness at all.

A_Seagull » February 15th, 2018, 1:58 pm wrote:and that every 'mathematical statement' can be ascribed the tag of either true od false.

No such assumption is necessary. Nor are the incompleteness theorems about truth. They're about provability. Truth is a semantic notion; provability is syntactic.

A_Seagull » February 15th, 2018, 1:58 pm wrote:Such assumptions are not necessary for the logical processes of mathematics to be applied.

Nor are any such assumptions made.
Last edited by someguy1 on February 15th, 2018, 5:23 pm, edited 4 times in total.
someguy1
Member

Posts: 753
Joined: 08 Nov 2013

### Re: Algorithms and logic

double post
someguy1
Member

Posts: 753
Joined: 08 Nov 2013

### Re: Algorithms and logic

someguy1 » February 16th, 2018, 9:11 am wrote:
A_Seagull » February 15th, 2018, 1:58 pm wrote:
LOL Why didn't you say you were talking about Gödel's theorems!

Why didn't you recognize the statement?

Because "We know we can not fully model the arithmetic of the positive integers with any consistent set of axioms." is not the same as what Gödel proved!

If I said that every particle of mass in the universe attracts every other particle with a force proportional to the product of their masses and the inverse square of the distance between them, would you demand a reference? Or would you immediately recognize Newton's law of gravity? Since you are making a claim about mathematical logic, I wonder why you did not recognize the first incompleteness theorem when I stated it. You seem to have heard the words but not understood the meaning.

A_Seagull » February 15th, 2018, 1:58 pm wrote:I don't think Gödel's theorems are applicable in this case as they rely upon the assumption that mathematics is 'complete'

That is not true. On the contrary, Gödel's first incompleteness theorem shows that any axiomatic system powerful enough to model the arithmetic of the natural numbers must be incomplete. There is no assumption of completeness at all.

Godels theorem requires the presumption that arithmetic is 'complete' and then shows this to be false.
A_Seagull » February 15th, 2018, 1:58 pm wrote:and that every 'mathematical statement' can be ascribed the tag of either true od false.

No such assumption is necessary. Nor are the incompleteness theorems about truth. They're about provability. Truth is a semantic notion; provability is syntactic.

It is generally considered that if a thorem is provable within a logical systemthat is is therefore 'true' within that system

.
[/quote]

A_Seagull
Member

Posts: 120
Joined: 29 Apr 2017

### Re: Algorithms and logic

A_Seagull » February 15th, 2018, 5:54 pm wrote:Because "We know we can not fully model the arithmetic of the positive integers with any consistent set of axioms." is not the same as what Gödel proved!

That's exactly what Gödel proved. The fact that you're thrown off by a simple restatement/reframing of the theorem is a clue that your knowledge in this area is not up to snuff. You should take note of that yourself. Apply some introspection, don't just toss out weak objections. Either that, or explain why you think I've got it wrong. If you did that, then I'd learn something. If you don't, you haven't made your point.

A_Seagull » February 15th, 2018, 1:58 pm wrote:
Godels theorem requires the presumption that arithmetic is 'complete' and then shows this to be false.

You are confusing proof by contradiction, which Gödel's proof isn't; with contrapositive. If every complete system is inconsistent, then no consistent system is complete. Once again you're weakening your argument by pretending to understand more than you do. I'll recommend some better tactics in a moment.

A_Seagull » February 15th, 2018, 1:58 pm wrote:
It is generally considered that if a thorem is provable within a logical systemthat is is therefore 'true' within that system

Generally considered? Not something subject to investigation or proof? Gödel proved the completeness of first-order predicate logic. That is, in first-order predicate logic, a proposition is provable if and only if it's true in every model. That's his slightly less famous completeness theorem. https://en.wikipedia.org/wiki/G%C3%B6de ... ss_theorem. It may have been "generally considered," but I doubt anyone regarded that as the last word on the matter, absent proof.

What's the difference between first-order predicate logic and number theory? Number theory has induction. Once you have induction, you lose either completeness or consistency. Logicism is busted. A lot of people were very upset about this in 1931, but most of them have gotten over it by now.

You've convinced me -- absent your specific, detailed, point-by-point refutation of my remarks -- that you're weak on the incompleteness theorem and the meaning and context of the subject in general.

But there's no shame in that. The problem is that doubling down on your misunderstanding is a poor tactic. What you should do here (IMO of course) is to gracefully retreat. Admit that yes, if we include the whole of number theory under logic, then your thesis is false. Gödel proved that, and there's no point in your objecting that it's a proof by contradiction or that I phrased it differently than it was expressed in the original German. No win possible for you there, you need to retreat.

A much better strategy would be to agree that (as Gödel showed) math isn't logic; but that certain special cases of your thesis are much more tenable.

For example if by logic you mean basic propositional logic, the Boolean logic of AND, OR, and NOT, then your thesis is entirely correct. A computer can easily do propositional logic. Computers are based on propositional logic. We all know this.

Now the question is, what other realms can you extend your thesis to? What about modal logic, paraconsistent logic, and all the other arcane logics studied by the specialists. That's why I asked you what you mean by logic. Or more accurately what you mean by "logical processes," which is how you put it.

I thought you would go in that sensible direction: admitting that you can't apply your thesis to math as a whole; but that you can restrict your thesis to more defensible domains. That might be a productive discussion.
someguy1
Member

Posts: 753
Joined: 08 Nov 2013