Direct application of a counterexample: Gödels incompleteness theorem and the halting problem
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Gödels incompleteness theorem is proven with the statement I am not a theorem of <theory> is never a theorem but always true.
The halting problem is proven because it can't be predicted if the program if I halt then loop forever halts.
In both cases you find a counter-example to "there is a consistent, complete theory" and "there is a computable halting function" respectively. It is very useful to prove the negations of those statements but does the disproven statement ever have a direct application?
We don't actually care about statements which imply there own non-theoremhood in our theories. If we could find a theory which is complete except for these statement we would still be satisfied. Likewise we don't care about programs which contradict there own halting a function, checking if any other program halts would still be very useful.
In a way we haven't learned anything we directly care about, we could still have a theory that predicts everything "useful" or a function which checks every "useful" program for halting.
Are there cases when this is not the case? When we find a counter-example we actually care very much about?
To clarify: I'm not questioning the usefulness of these proofs because statements like "There is no consistent and complete theory" or "The halting problem is undecidable" are still very useful. I am more asking if there can be direct applications of the disproved statement because it feels like you can always form a less general statement.
logic soft-question
asked Sep 6 at 10:26
fejfo
23519
 |Â
show 3 more comments
up vote
1
down vote
favorite
Gödels incompleteness theorem is proven with the statement I am not a theorem of <theory> is never a theorem but always true.
The halting problem is proven because it can't be predicted if the program if I halt then loop forever halts.
In both cases you find a counter-example to "there is a consistent, complete theory" and "there is a computable halting function" respectively. It is very useful to prove the negations of those statements but does the disproven statement ever have a direct application?
We don't actually care about statements which imply there own non-theoremhood in our theories. If we could find a theory which is complete except for these statement we would still be satisfied. Likewise we don't care about programs which contradict there own halting a function, checking if any other program halts would still be very useful.
In a way we haven't learned anything we directly care about, we could still have a theory that predicts everything "useful" or a function which checks every "useful" program for halting.
Are there cases when this is not the case? When we find a counter-example we actually care very much about?
To clarify: I'm not questioning the usefulness of these proofs because statements like "There is no consistent and complete theory" or "The halting problem is undecidable" are still very useful. I am more asking if there can be direct applications of the disproved statement because it feels like you can always form a less general statement.
logic soft-question
asked Sep 6 at 10:26
fejfo
23519
I don't agree when you say "Gödels incompleteness theorem is proven with the statement 'I am not a theorem of <theory>' is never a theorem but always true". What do you mean by "always true"? Do you know the existence of the completeness theorem for first-order logic, proven by Gödel himself?
– Taroccoesbrocco
Sep 6 at 10:44
1
Welcome to the club! I also wanted to know a proof of the undecidability of the halting problem WITHOUT a self-reference included. Noone could give me a satisfactionable answer. However, examples for concrete undecidabilities DO exist : $(1)$ The Goodstein-theorem is not provable in PA, but in ZFC, it can be proven $(2)$ There are diophantic equations that have no integer solutions and it cannot be proven in ZFC that there are none.
– Peter
Sep 6 at 10:45
1
So, clearly the limits of decidability are not purely artificial, although in most cases, there is very little impact of the incompleteness theorem. It is possible that big open conjectures cannot be proven in principle (including Goldbach's conjecture, Riemann hypothesis , Collatz's conjecture , Twin prime conjecture and so on).
– Peter
Sep 6 at 10:51
@Taroccoesbrocco I read the book "Gödel, Escher, Bach" and I thought that statement was a good summary of the proof outlined there since the proof it self is not really at the core of my question. I'm meant with always true that the statement is true for every consistent theory because if it wasn't, it would be a theorem which would lead to a contradiction.
– fejfo
Sep 6 at 11:40
@Peter My question isn't really about the proofs but the statements with the counter example removed you automatically think off after seeing one of those proofs. (but one without self-reference would be nice). I don't know to much about your other examples but maybe I should look them up.
– fejfo
Sep 6 at 11:43
 |Â
show 3 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Gödels incompleteness theorem is proven with the statement I am not a theorem of <theory> is never a theorem but always true.
The halting problem is proven because it can't be predicted if the program if I halt then loop forever halts.
In both cases you find a counter-example to "there is a consistent, complete theory" and "there is a computable halting function" respectively. It is very useful to prove the negations of those statements but does the disproven statement ever have a direct application?
We don't actually care about statements which imply there own non-theoremhood in our theories. If we could find a theory which is complete except for these statement we would still be satisfied. Likewise we don't care about programs which contradict there own halting a function, checking if any other program halts would still be very useful.
In a way we haven't learned anything we directly care about, we could still have a theory that predicts everything "useful" or a function which checks every "useful" program for halting.
Are there cases when this is not the case? When we find a counter-example we actually care very much about?
To clarify: I'm not questioning the usefulness of these proofs because statements like "There is no consistent and complete theory" or "The halting problem is undecidable" are still very useful. I am more asking if there can be direct applications of the disproved statement because it feels like you can always form a less general statement.
logic soft-question
asked Sep 6 at 10:26
fejfo
23519
Gödels incompleteness theorem is proven with the statement I am not a theorem of <theory> is never a theorem but always true.
The halting problem is proven because it can't be predicted if the program if I halt then loop forever halts.
In both cases you find a counter-example to "there is a consistent, complete theory" and "there is a computable halting function" respectively. It is very useful to prove the negations of those statements but does the disproven statement ever have a direct application?
We don't actually care about statements which imply there own non-theoremhood in our theories. If we could find a theory which is complete except for these statement we would still be satisfied. Likewise we don't care about programs which contradict there own halting a function, checking if any other program halts would still be very useful.
In a way we haven't learned anything we directly care about, we could still have a theory that predicts everything "useful" or a function which checks every "useful" program for halting.
Are there cases when this is not the case? When we find a counter-example we actually care very much about?
To clarify: I'm not questioning the usefulness of these proofs because statements like "There is no consistent and complete theory" or "The halting problem is undecidable" are still very useful. I am more asking if there can be direct applications of the disproved statement because it feels like you can always form a less general statement.
logic soft-question
logic soft-question
asked Sep 6 at 10:26
fejfo
23519
asked Sep 6 at 10:26
fejfo
23519
asked Sep 6 at 10:26
fejfo
23519
asked Sep 6 at 10:26
fejfo
23519
asked Sep 6 at 10:26
fejfo
23519
23519
I don't agree when you say "Gödels incompleteness theorem is proven with the statement 'I am not a theorem of <theory>' is never a theorem but always true". What do you mean by "always true"? Do you know the existence of the completeness theorem for first-order logic, proven by Gödel himself?
– Taroccoesbrocco
Sep 6 at 10:44
1
Welcome to the club! I also wanted to know a proof of the undecidability of the halting problem WITHOUT a self-reference included. Noone could give me a satisfactionable answer. However, examples for concrete undecidabilities DO exist : $(1)$ The Goodstein-theorem is not provable in PA, but in ZFC, it can be proven $(2)$ There are diophantic equations that have no integer solutions and it cannot be proven in ZFC that there are none.
– Peter
Sep 6 at 10:45
1
So, clearly the limits of decidability are not purely artificial, although in most cases, there is very little impact of the incompleteness theorem. It is possible that big open conjectures cannot be proven in principle (including Goldbach's conjecture, Riemann hypothesis , Collatz's conjecture , Twin prime conjecture and so on).
– Peter
Sep 6 at 10:51
@Taroccoesbrocco I read the book "Gödel, Escher, Bach" and I thought that statement was a good summary of the proof outlined there since the proof it self is not really at the core of my question. I'm meant with always true that the statement is true for every consistent theory because if it wasn't, it would be a theorem which would lead to a contradiction.
– fejfo
Sep 6 at 11:40
@Peter My question isn't really about the proofs but the statements with the counter example removed you automatically think off after seeing one of those proofs. (but one without self-reference would be nice). I don't know to much about your other examples but maybe I should look them up.
– fejfo
Sep 6 at 11:43
 |Â
show 3 more comments
I don't agree when you say "Gödels incompleteness theorem is proven with the statement 'I am not a theorem of <theory>' is never a theorem but always true". What do you mean by "always true"? Do you know the existence of the completeness theorem for first-order logic, proven by Gödel himself?
– Taroccoesbrocco
Sep 6 at 10:44
1
Welcome to the club! I also wanted to know a proof of the undecidability of the halting problem WITHOUT a self-reference included. Noone could give me a satisfactionable answer. However, examples for concrete undecidabilities DO exist : $(1)$ The Goodstein-theorem is not provable in PA, but in ZFC, it can be proven $(2)$ There are diophantic equations that have no integer solutions and it cannot be proven in ZFC that there are none.
– Peter
Sep 6 at 10:45
1
So, clearly the limits of decidability are not purely artificial, although in most cases, there is very little impact of the incompleteness theorem. It is possible that big open conjectures cannot be proven in principle (including Goldbach's conjecture, Riemann hypothesis , Collatz's conjecture , Twin prime conjecture and so on).
– Peter
Sep 6 at 10:51
@Taroccoesbrocco I read the book "Gödel, Escher, Bach" and I thought that statement was a good summary of the proof outlined there since the proof it self is not really at the core of my question. I'm meant with always true that the statement is true for every consistent theory because if it wasn't, it would be a theorem which would lead to a contradiction.
– fejfo
Sep 6 at 11:40
@Peter My question isn't really about the proofs but the statements with the counter example removed you automatically think off after seeing one of those proofs. (but one without self-reference would be nice). I don't know to much about your other examples but maybe I should look them up.
– fejfo
Sep 6 at 11:43
I don't agree when you say "Gödels incompleteness theorem is proven with the statement 'I am not a theorem of <theory>' is never a theorem but always true". What do you mean by "always true"? Do you know the existence of the completeness theorem for first-order logic, proven by Gödel himself?
– Taroccoesbrocco
Sep 6 at 10:44
I don't agree when you say "Gödels incompleteness theorem is proven with the statement 'I am not a theorem of <theory>' is never a theorem but always true". What do you mean by "always true"? Do you know the existence of the completeness theorem for first-order logic, proven by Gödel himself?
– Taroccoesbrocco
Sep 6 at 10:44
1
1
Welcome to the club! I also wanted to know a proof of the undecidability of the halting problem WITHOUT a self-reference included. Noone could give me a satisfactionable answer. However, examples for concrete undecidabilities DO exist : $(1)$ The Goodstein-theorem is not provable in PA, but in ZFC, it can be proven $(2)$ There are diophantic equations that have no integer solutions and it cannot be proven in ZFC that there are none.
– Peter
Sep 6 at 10:45
Welcome to the club! I also wanted to know a proof of the undecidability of the halting problem WITHOUT a self-reference included. Noone could give me a satisfactionable answer. However, examples for concrete undecidabilities DO exist : $(1)$ The Goodstein-theorem is not provable in PA, but in ZFC, it can be proven $(2)$ There are diophantic equations that have no integer solutions and it cannot be proven in ZFC that there are none.
– Peter
Sep 6 at 10:45
1
1
So, clearly the limits of decidability are not purely artificial, although in most cases, there is very little impact of the incompleteness theorem. It is possible that big open conjectures cannot be proven in principle (including Goldbach's conjecture, Riemann hypothesis , Collatz's conjecture , Twin prime conjecture and so on).
– Peter
Sep 6 at 10:51
So, clearly the limits of decidability are not purely artificial, although in most cases, there is very little impact of the incompleteness theorem. It is possible that big open conjectures cannot be proven in principle (including Goldbach's conjecture, Riemann hypothesis , Collatz's conjecture , Twin prime conjecture and so on).
– Peter
Sep 6 at 10:51
@Taroccoesbrocco I read the book "Gödel, Escher, Bach" and I thought that statement was a good summary of the proof outlined there since the proof it self is not really at the core of my question. I'm meant with always true that the statement is true for every consistent theory because if it wasn't, it would be a theorem which would lead to a contradiction.
– fejfo
Sep 6 at 11:40
@Taroccoesbrocco I read the book "Gödel, Escher, Bach" and I thought that statement was a good summary of the proof outlined there since the proof it self is not really at the core of my question. I'm meant with always true that the statement is true for every consistent theory because if it wasn't, it would be a theorem which would lead to a contradiction.
– fejfo
Sep 6 at 11:40
@Peter My question isn't really about the proofs but the statements with the counter example removed you automatically think off after seeing one of those proofs. (but one without self-reference would be nice). I don't know to much about your other examples but maybe I should look them up.
– fejfo
Sep 6 at 11:43
@Peter My question isn't really about the proofs but the statements with the counter example removed you automatically think off after seeing one of those proofs. (but one without self-reference would be nice). I don't know to much about your other examples but maybe I should look them up.
– fejfo
Sep 6 at 11:43
 |Â
show 3 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2907310%2fdirect-application-of-a-counterexample-g%25c3%25b6dels-incompleteness-theorem-and-the-ha%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I don't agree when you say "Gödels incompleteness theorem is proven with the statement 'I am not a theorem of <theory>' is never a theorem but always true". What do you mean by "always true"? Do you know the existence of the completeness theorem for first-order logic, proven by Gödel himself?
– Taroccoesbrocco
Sep 6 at 10:44
1
Welcome to the club! I also wanted to know a proof of the undecidability of the halting problem WITHOUT a self-reference included. Noone could give me a satisfactionable answer. However, examples for concrete undecidabilities DO exist : $(1)$ The Goodstein-theorem is not provable in PA, but in ZFC, it can be proven $(2)$ There are diophantic equations that have no integer solutions and it cannot be proven in ZFC that there are none.
– Peter
Sep 6 at 10:45
1
So, clearly the limits of decidability are not purely artificial, although in most cases, there is very little impact of the incompleteness theorem. It is possible that big open conjectures cannot be proven in principle (including Goldbach's conjecture, Riemann hypothesis , Collatz's conjecture , Twin prime conjecture and so on).
– Peter
Sep 6 at 10:51
@Taroccoesbrocco I read the book "Gödel, Escher, Bach" and I thought that statement was a good summary of the proof outlined there since the proof it self is not really at the core of my question. I'm meant with always true that the statement is true for every consistent theory because if it wasn't, it would be a theorem which would lead to a contradiction.
– fejfo
Sep 6 at 11:40
@Peter My question isn't really about the proofs but the statements with the counter example removed you automatically think off after seeing one of those proofs. (but one without self-reference would be nice). I don't know to much about your other examples but maybe I should look them up.
– fejfo
Sep 6 at 11:43