Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Gödel and the limits of logic (2006)

plus.maths.org

Post reply on HN
Print view View original

21–30 of 41 posts

Re: Gödel and the limits of logic (2006)

#21

Post by sillysaurus3 »

laxd wrote: post #20
jpt4 wrote: post #17

Earlier quoted context omitted.

Yablo's Paradox [0], possibly [1]. Regarding [1], "circularity" in an uncountably infinite context seems different than "self-referential", though the latter is usually geometrically analogized as the former. I tentatively consider Yablo's Paradox to demonstrate that an ineradicable cycle of alternating truth-assignments is equivalent to an infinite (>= aleph-one) regression of alternating truth-assignments, and thus…

Not trying to argue here, just learn more. This Yablo's paradox seem self referential to me. The statements are making claims about a series of statements of which they themselves are part of. I see the statements only making claims about subsequent statements... but still. How about, rather that banning "self references", you have a more carefull phrasing requiring all structures to be fully and independently define…

It depends what you mean by a Godelish paradox. Godel proved that there are statements which are true, but unprovable. To me, that's quite a paradox, and there's no escaping it.

Re: Gödel and the limits of logic (2006)

#23

Post by brianberns »

sillysaurus3 wrote: post #21
laxd wrote: post #20

Earlier quoted context omitted.

Not trying to argue here, just learn more. This Yablo's paradox seem self referential to me. The statements are making claims about a series of statements of which they themselves are part of. I see the statements only making claims about subsequent statements... but still. How about, rather that banning "self references", you have a more carefull phrasing requiring all structures to be fully and independently define…

It depends what you mean by a Godelish paradox. Godel proved that there are statements which are true, but unprovable. To me, that's quite a paradox, and there's no escaping it.

I think the point of the question is that perhaps we could escape it by banishing all self-referential statements?

Re: Gödel and the limits of logic (2006)

#24

Post by laxd »

sillysaurus3 wrote: post #21
laxd wrote: post #20

Earlier quoted context omitted.

Not trying to argue here, just learn more. This Yablo's paradox seem self referential to me. The statements are making claims about a series of statements of which they themselves are part of. I see the statements only making claims about subsequent statements... but still. How about, rather that banning "self references", you have a more carefull phrasing requiring all structures to be fully and independently define…

It depends what you mean by a Godelish paradox. Godel proved that there are statements which are true, but unprovable. To me, that's quite a paradox, and there's no escaping it.

By Goedelish I mean all the stuff that are really just concretizations and corollaries of incompleteness.

You can escape incompleteness with less powerfull axiomatic systems. But then you can't define the set of integers. (correct me if I'm wrong).

Re: Gödel and the limits of logic (2006)

#25

Post by [deleted] »

brianberns wrote: post #23
sillysaurus3 wrote: post #21

Earlier quoted context omitted.

It depends what you mean by a Godelish paradox. Godel proved that there are statements which are true, but unprovable. To me, that's quite a paradox, and there's no escaping it.

I think the point of the question is that perhaps we could escape it by banishing all self-referential statements?

[deleted]

Re: Gödel and the limits of logic (2006)

#26

Post by laxd »

laxd wrote: post #24
sillysaurus3 wrote: post #21

Earlier quoted context omitted.

It depends what you mean by a Godelish paradox. Godel proved that there are statements which are true, but unprovable. To me, that's quite a paradox, and there's no escaping it.

By Goedelish I mean all the stuff that are really just concretizations and corollaries of incompleteness. You can escape incompleteness with less powerfull axiomatic systems. But then you can't define the set of integers. (correct me if I'm wrong).

Hmm, maybe I just answered my own question. You can't define the set of integers without using elements of the set of integers. Like Peano's successor function. And if you have that power, you can state paradoxes. Like the above mentioned Yablo's paradox. ?

Re: Gödel and the limits of logic (2006)

#27

Post by pvg »

sillysaurus3 wrote: post #21
laxd wrote: post #20

Earlier quoted context omitted.

Not trying to argue here, just learn more. This Yablo's paradox seem self referential to me. The statements are making claims about a series of statements of which they themselves are part of. I see the statements only making claims about subsequent statements... but still. How about, rather that banning "self references", you have a more carefull phrasing requiring all structures to be fully and independently define…

It depends what you mean by a Godelish paradox. Godel proved that there are statements which are true, but unprovable. To me, that's quite a paradox, and there's no escaping it.

What is (inescapably) paradoxical about that?

Re: Gödel and the limits of logic (2006)

#28

Post by mmarx »

laxd wrote: post #26
laxd wrote: post #24

Earlier quoted context omitted.

By Goedelish I mean all the stuff that are really just concretizations and corollaries of incompleteness. You can escape incompleteness with less powerfull axiomatic systems. But then you can't define the set of integers. (correct me if I'm wrong).

Hmm, maybe I just answered my own question. You can't define the set of integers without using elements of the set of integers. Like Peano's successor function. And if you have that power, you can state paradoxes. Like the above mentioned Yablo's paradox. ?

Presburger arithmetic[0] is powerful enough to describe the natural numbers with addition, yet still consistent and complete. On the other hand, Robinson arithmetic[1] lacks induction, but axiomatizes addition and multiplication, and that is sufficient to make it incomplete. Thus, the problem is not that you can describe the set of natural numbers, or induction, but the interaction between addition and multiplication.

[0] https://en.wikipedia.org/wiki/Presburger_arithmetic [1] https://en.wikipedia.org/wiki/Robinson_arithmetic

Re: Gödel and the limits of logic (2006)

#29

Post by Animats »

mmarx wrote: post #28
laxd wrote: post #26

Earlier quoted context omitted.

Hmm, maybe I just answered my own question. You can't define the set of integers without using elements of the set of integers. Like Peano's successor function. And if you have that power, you can state paradoxes. Like the above mentioned Yablo's paradox. ?

Presburger arithmetic[0] is powerful enough to describe the natural numbers with addition, yet still consistent and complete. On the other hand, Robinson arithmetic[1] lacks induction, but axiomatizes addition and multiplication, and that is sufficient to make it incomplete. Thus, the problem is not that you can describe the set of natural numbers, or induction, but the interaction between addition and multiplication…

There are a few ways around undecidability. One is finiteness. If you have an upper bound, or addition cycles around to zero, there are a finite number of states. Halting is decidable for deterministic machines with finite memory - eventually it must either halt or repeat a state.

(An amusing practical solution to the halting problem is to run two interpreters in parallel, with one running twice as fast as the other. If their states match after starting, the program is in a loop. This trick was sometimes used in the batch computing era to catch beginner student programs that were in a loop before they wasted much CPU time. Programs with long cycles wouldn't be caught, but that was usually not the problem with beginner programs.)

Re: Gödel and the limits of logic (2006)

#30

Post by mmarx »

Animats wrote: post #29
mmarx wrote: post #28

Earlier quoted context omitted.

Presburger arithmetic[0] is powerful enough to describe the natural numbers with addition, yet still consistent and complete. On the other hand, Robinson arithmetic[1] lacks induction, but axiomatizes addition and multiplication, and that is sufficient to make it incomplete. Thus, the problem is not that you can describe the set of natural numbers, or induction, but the interaction between addition and multiplication…

There are a few ways around undecidability. One is finiteness. If you have an upper bound, or addition cycles around to zero, there are a finite number of states. Halting is decidable for deterministic machines with finite memory - eventually it must either halt or repeat a state. (An amusing practical solution to the halting problem is to run two interpreters in parallel, with one running twice as fast as the other.…

Decidability (as a property of decision problems like the halting problem) is a different notion, though: In the context of incompleteness, an undecidable statement is a statement that cannot be proven or disproved in that system. Decidability of a decision problem is concerned with an effective procedure that, for every instance of the problem, answers yes/no. Specifically for a logical theory, decidability of this theory is deciding for any formula in the same language whether it follows from the theory as a logical consequence.

Neither incompleteness nor undecidability imply the other[0].

[0] https://en.wikipedia.org/wiki/Decidability_(logic)#Relations...

Post reply on HN