Mixing
Is set theory used in proofs of theorems in logic?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Is set theory used in proofs of theorems in logic ? For example, is set theory used in Gödel's incompleteness theorem ? If yes, than does it mean that if we use other from ZFC set theory or even other theory (I mean not set-theory) as foundation than this theorem will not hold ?
logic set-theory foundations
asked Jul 28 at 11:20
îріù ïрþш
981513
add a comment |Â
up vote
3
down vote
favorite
Is set theory used in proofs of theorems in logic ? For example, is set theory used in Gödel's incompleteness theorem ? If yes, than does it mean that if we use other from ZFC set theory or even other theory (I mean not set-theory) as foundation than this theorem will not hold ?
logic set-theory foundations
asked Jul 28 at 11:20
îріù ïрþш
981513
Goedels incompleteness theorem is not only about ZFC. It states that every sufficient strong system (PA is enough) is either inconsistent or incomplete.
– Peter
Jul 28 at 11:31
There are statements provable in ZFC, but not in PA , the most famous example is the statement that every Goodstein-sequence eventually terminates.
– Peter
Jul 28 at 11:33
3
@Peter I think the question is asking about the theory in which, not about which, these results are proved.
– Noah Schweber
Jul 28 at 12:47
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Is set theory used in proofs of theorems in logic ? For example, is set theory used in Gödel's incompleteness theorem ? If yes, than does it mean that if we use other from ZFC set theory or even other theory (I mean not set-theory) as foundation than this theorem will not hold ?
logic set-theory foundations
asked Jul 28 at 11:20
îріù ïрþш
981513
Is set theory used in proofs of theorems in logic ? For example, is set theory used in Gödel's incompleteness theorem ? If yes, than does it mean that if we use other from ZFC set theory or even other theory (I mean not set-theory) as foundation than this theorem will not hold ?
logic set-theory foundations
asked Jul 28 at 11:20
îріù ïрþш
981513
asked Jul 28 at 11:20
îріù ïрþш
981513
asked Jul 28 at 11:20
îріù ïрþш
981513
asked Jul 28 at 11:20
îріù ïрþш
981513
981513
Goedels incompleteness theorem is not only about ZFC. It states that every sufficient strong system (PA is enough) is either inconsistent or incomplete.
– Peter
Jul 28 at 11:31
There are statements provable in ZFC, but not in PA , the most famous example is the statement that every Goodstein-sequence eventually terminates.
– Peter
Jul 28 at 11:33
3
@Peter I think the question is asking about the theory in which, not about which, these results are proved.
– Noah Schweber
Jul 28 at 12:47
add a comment |Â
Goedels incompleteness theorem is not only about ZFC. It states that every sufficient strong system (PA is enough) is either inconsistent or incomplete.
– Peter
Jul 28 at 11:31
There are statements provable in ZFC, but not in PA , the most famous example is the statement that every Goodstein-sequence eventually terminates.
– Peter
Jul 28 at 11:33
3
@Peter I think the question is asking about the theory in which, not about which, these results are proved.
– Noah Schweber
Jul 28 at 12:47
Goedels incompleteness theorem is not only about ZFC. It states that every sufficient strong system (PA is enough) is either inconsistent or incomplete.
– Peter
Jul 28 at 11:31
Goedels incompleteness theorem is not only about ZFC. It states that every sufficient strong system (PA is enough) is either inconsistent or incomplete.
– Peter
Jul 28 at 11:31
There are statements provable in ZFC, but not in PA , the most famous example is the statement that every Goodstein-sequence eventually terminates.
– Peter
Jul 28 at 11:33
There are statements provable in ZFC, but not in PA , the most famous example is the statement that every Goodstein-sequence eventually terminates.
– Peter
Jul 28 at 11:33
3
3
@Peter I think the question is asking about the theory in which, not about which, these results are proved.
– Noah Schweber
Jul 28 at 12:47
@Peter I think the question is asking about the theory in which, not about which, these results are proved.
– Noah Schweber
Jul 28 at 12:47
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
13
down vote
accepted
Yes, set theory is used in some theorems (e.g. the completeness theorem), but not in the incompleteness theorem.
When Gödel proved his incompleteness theorem he worked very hard on proving it using only Peano axioms of the natural numbers, since those were "indisputable" compared to the set theoretic axioms which were still being scrutinized by some people. This was later improved by various mathematician and we know now that you only need a much weaker theory for incompleteness to kick in.
On the other hand, the completeness theorem speaks about models, which are inherently sets. So of course that set theory comes into play there. In fact, the general statement of the completeness theorem for first-order logic is equivalent to the Boolean Prime Ideal theorem, and is therefore not provable without the axiom of choice. It should be remarked that if the language is countable, then choice is not needed.
We can talk about completeness in theories like Peano arithmetic, which provides us with weaker results, though. There the notion of a model becomes slightly less natural than the one in set theory.
answered Jul 28 at 11:33
Asaf Karagila
291k31402732
2
+1. Two comments for the OP: first of all, the completeness theorem holds without choice as long as the language is well-orderable; even countability isn't necessary. Moreover, ZF is (provably in a very weak base theory) equiconsistent with ZFC, so we shouldn't be too skeptical of adding choice, and indeed the "concrete" consequences of ZF and ZFC are (again, provably in a weak theory) the same. (cont'd)
– Noah Schweber
Jul 28 at 12:40
1
Second, and more significantly I think, doing model theory in PA (or any theory of first-order arithmetic - that is, numbers only) is inherently difficult since PA doesn't seem to have a way to talk directly about infinite structures (whereas finite structures, in a finite language at least, can be coded by natural numbers). There are ways around this, and in particular you may be interested in the [arithmetized completeness theorem](), but the difficulty is significant enough in my opinion that it's worth explicitly mentioning.
– Noah Schweber
Jul 28 at 12:44
3
Good comments, Noah. I think you missed a link there at the second comment. :)
– Asaf Karagila
Jul 28 at 13:03
add a comment |Â
up vote
8
down vote
Yes, changing the "background theory" can lead to alternate proof/model theories. However, in order to get really meaningful differences (that is, differences at the "basic level" like the incompleteness theorem) you need to do significant damage to the background, to the point that it doesn't seem to hold much interest. I believe Hajek and Pudlak's book goes into proving basic proof theoretic results in weak theories of arithmetic, and I recommend it highly.
That said, violence is certainly entertaining! Visser's lovely paper Oracle bites theory shows how bad things can get once we kill arithmetic thoroughly enough (in particular, he shows that over a truly feeble base theory the set of consequences of a consistent theory need not be a consistent theory!), and Visser's other papers are probably also of interest to you.
Basically, in order to be skeptical of the incompleteness theorem we need to already be skeptical as such basic arithmetical principles as the totality of exponentiation. This is why from a foundational point of view the possibility has not received serious attention, though it may be of technical interest (I wouldn't know, I'm not an expert in the relevant area). This is similar to the situation with Cantor's diagonal argument, where the amount of set theory you have to break to make it non-applicable is so great that it's hardly worth doing, and certainly not foundationally compelling (so far as I know).
answered Jul 28 at 12:56
Noah Schweber
110k9139260
1
I seem to remember that Ed Nelson was sceptical about totality of exponentiation.
– Lord Shark the Unknown
Jul 28 at 14:28
add a comment |Â
up vote
3
down vote
The main point about Gödel's Theorem is the method of proof. This shows that if the model or theory being used is rich enough, then it contains within it the resources to encode its own limitations in that it will either be inconsistent or incomplete (in the sense that there will be true statements which are unprovable within the system or model).
There are systems which escape Gödel's method, but they do so by being deliberately limited, rather than being too strong to fail.
answered Jul 28 at 11:34
Mark Bennet
76.4k773170
2
I don't think this really answers the question - I think the OP is asking about the theory in which, not about which, Godel's theorem is proved.
– Noah Schweber
Jul 28 at 12:47
@NoahSchweber I put this in as an answer because there seemed to me to be an implicit question "can I find a theory which avoids Gödel's Theorem?" and it seemed to be worth more than a comment.
– Mark Bennet
Jul 28 at 15:32
1
"can I find a theory which avoids Gödel's Theorem?" can mean two things: "is there a theory to which GT doesn't apply" or "is there a (reasonable) theory which thinks that GT isn't true?" (e.g. which is consistent and thinks that PA is complete). I think it's clear from the question that the latter is meant.
– Noah Schweber
Jul 28 at 15:56
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
13
down vote
accepted
Yes, set theory is used in some theorems (e.g. the completeness theorem), but not in the incompleteness theorem.
When Gödel proved his incompleteness theorem he worked very hard on proving it using only Peano axioms of the natural numbers, since those were "indisputable" compared to the set theoretic axioms which were still being scrutinized by some people. This was later improved by various mathematician and we know now that you only need a much weaker theory for incompleteness to kick in.
On the other hand, the completeness theorem speaks about models, which are inherently sets. So of course that set theory comes into play there. In fact, the general statement of the completeness theorem for first-order logic is equivalent to the Boolean Prime Ideal theorem, and is therefore not provable without the axiom of choice. It should be remarked that if the language is countable, then choice is not needed.
We can talk about completeness in theories like Peano arithmetic, which provides us with weaker results, though. There the notion of a model becomes slightly less natural than the one in set theory.
answered Jul 28 at 11:33
Asaf Karagila
291k31402732
2
+1. Two comments for the OP: first of all, the completeness theorem holds without choice as long as the language is well-orderable; even countability isn't necessary. Moreover, ZF is (provably in a very weak base theory) equiconsistent with ZFC, so we shouldn't be too skeptical of adding choice, and indeed the "concrete" consequences of ZF and ZFC are (again, provably in a weak theory) the same. (cont'd)
– Noah Schweber
Jul 28 at 12:40
1
Second, and more significantly I think, doing model theory in PA (or any theory of first-order arithmetic - that is, numbers only) is inherently difficult since PA doesn't seem to have a way to talk directly about infinite structures (whereas finite structures, in a finite language at least, can be coded by natural numbers). There are ways around this, and in particular you may be interested in the [arithmetized completeness theorem](), but the difficulty is significant enough in my opinion that it's worth explicitly mentioning.
– Noah Schweber
Jul 28 at 12:44
3
Good comments, Noah. I think you missed a link there at the second comment. :)
– Asaf Karagila
Jul 28 at 13:03
add a comment |Â
up vote
13
down vote
accepted
Yes, set theory is used in some theorems (e.g. the completeness theorem), but not in the incompleteness theorem.
When Gödel proved his incompleteness theorem he worked very hard on proving it using only Peano axioms of the natural numbers, since those were "indisputable" compared to the set theoretic axioms which were still being scrutinized by some people. This was later improved by various mathematician and we know now that you only need a much weaker theory for incompleteness to kick in.
On the other hand, the completeness theorem speaks about models, which are inherently sets. So of course that set theory comes into play there. In fact, the general statement of the completeness theorem for first-order logic is equivalent to the Boolean Prime Ideal theorem, and is therefore not provable without the axiom of choice. It should be remarked that if the language is countable, then choice is not needed.
We can talk about completeness in theories like Peano arithmetic, which provides us with weaker results, though. There the notion of a model becomes slightly less natural than the one in set theory.
answered Jul 28 at 11:33
Asaf Karagila
291k31402732
2
+1. Two comments for the OP: first of all, the completeness theorem holds without choice as long as the language is well-orderable; even countability isn't necessary. Moreover, ZF is (provably in a very weak base theory) equiconsistent with ZFC, so we shouldn't be too skeptical of adding choice, and indeed the "concrete" consequences of ZF and ZFC are (again, provably in a weak theory) the same. (cont'd)
– Noah Schweber
Jul 28 at 12:40
1
Second, and more significantly I think, doing model theory in PA (or any theory of first-order arithmetic - that is, numbers only) is inherently difficult since PA doesn't seem to have a way to talk directly about infinite structures (whereas finite structures, in a finite language at least, can be coded by natural numbers). There are ways around this, and in particular you may be interested in the [arithmetized completeness theorem](), but the difficulty is significant enough in my opinion that it's worth explicitly mentioning.
– Noah Schweber
Jul 28 at 12:44
3
Good comments, Noah. I think you missed a link there at the second comment. :)
– Asaf Karagila
Jul 28 at 13:03
add a comment |Â
up vote
13
down vote
accepted
up vote
13
down vote
accepted
Yes, set theory is used in some theorems (e.g. the completeness theorem), but not in the incompleteness theorem.
When Gödel proved his incompleteness theorem he worked very hard on proving it using only Peano axioms of the natural numbers, since those were "indisputable" compared to the set theoretic axioms which were still being scrutinized by some people. This was later improved by various mathematician and we know now that you only need a much weaker theory for incompleteness to kick in.
On the other hand, the completeness theorem speaks about models, which are inherently sets. So of course that set theory comes into play there. In fact, the general statement of the completeness theorem for first-order logic is equivalent to the Boolean Prime Ideal theorem, and is therefore not provable without the axiom of choice. It should be remarked that if the language is countable, then choice is not needed.
We can talk about completeness in theories like Peano arithmetic, which provides us with weaker results, though. There the notion of a model becomes slightly less natural than the one in set theory.
answered Jul 28 at 11:33
Asaf Karagila
291k31402732
Yes, set theory is used in some theorems (e.g. the completeness theorem), but not in the incompleteness theorem.
When Gödel proved his incompleteness theorem he worked very hard on proving it using only Peano axioms of the natural numbers, since those were "indisputable" compared to the set theoretic axioms which were still being scrutinized by some people. This was later improved by various mathematician and we know now that you only need a much weaker theory for incompleteness to kick in.
On the other hand, the completeness theorem speaks about models, which are inherently sets. So of course that set theory comes into play there. In fact, the general statement of the completeness theorem for first-order logic is equivalent to the Boolean Prime Ideal theorem, and is therefore not provable without the axiom of choice. It should be remarked that if the language is countable, then choice is not needed.
We can talk about completeness in theories like Peano arithmetic, which provides us with weaker results, though. There the notion of a model becomes slightly less natural than the one in set theory.
answered Jul 28 at 11:33
Asaf Karagila
291k31402732
answered Jul 28 at 11:33
Asaf Karagila
291k31402732
answered Jul 28 at 11:33
Asaf Karagila
291k31402732
answered Jul 28 at 11:33
Asaf Karagila
291k31402732
291k31402732
2
+1. Two comments for the OP: first of all, the completeness theorem holds without choice as long as the language is well-orderable; even countability isn't necessary. Moreover, ZF is (provably in a very weak base theory) equiconsistent with ZFC, so we shouldn't be too skeptical of adding choice, and indeed the "concrete" consequences of ZF and ZFC are (again, provably in a weak theory) the same. (cont'd)
– Noah Schweber
Jul 28 at 12:40
1
Second, and more significantly I think, doing model theory in PA (or any theory of first-order arithmetic - that is, numbers only) is inherently difficult since PA doesn't seem to have a way to talk directly about infinite structures (whereas finite structures, in a finite language at least, can be coded by natural numbers). There are ways around this, and in particular you may be interested in the [arithmetized completeness theorem](), but the difficulty is significant enough in my opinion that it's worth explicitly mentioning.
– Noah Schweber
Jul 28 at 12:44
3
Good comments, Noah. I think you missed a link there at the second comment. :)
– Asaf Karagila
Jul 28 at 13:03
add a comment |Â
2
+1. Two comments for the OP: first of all, the completeness theorem holds without choice as long as the language is well-orderable; even countability isn't necessary. Moreover, ZF is (provably in a very weak base theory) equiconsistent with ZFC, so we shouldn't be too skeptical of adding choice, and indeed the "concrete" consequences of ZF and ZFC are (again, provably in a weak theory) the same. (cont'd)
– Noah Schweber
Jul 28 at 12:40
1
Second, and more significantly I think, doing model theory in PA (or any theory of first-order arithmetic - that is, numbers only) is inherently difficult since PA doesn't seem to have a way to talk directly about infinite structures (whereas finite structures, in a finite language at least, can be coded by natural numbers). There are ways around this, and in particular you may be interested in the [arithmetized completeness theorem](), but the difficulty is significant enough in my opinion that it's worth explicitly mentioning.
– Noah Schweber
Jul 28 at 12:44
3
Good comments, Noah. I think you missed a link there at the second comment. :)
– Asaf Karagila
Jul 28 at 13:03
2
2
+1. Two comments for the OP: first of all, the completeness theorem holds without choice as long as the language is well-orderable; even countability isn't necessary. Moreover, ZF is (provably in a very weak base theory) equiconsistent with ZFC, so we shouldn't be too skeptical of adding choice, and indeed the "concrete" consequences of ZF and ZFC are (again, provably in a weak theory) the same. (cont'd)
– Noah Schweber
Jul 28 at 12:40
+1. Two comments for the OP: first of all, the completeness theorem holds without choice as long as the language is well-orderable; even countability isn't necessary. Moreover, ZF is (provably in a very weak base theory) equiconsistent with ZFC, so we shouldn't be too skeptical of adding choice, and indeed the "concrete" consequences of ZF and ZFC are (again, provably in a weak theory) the same. (cont'd)
– Noah Schweber
Jul 28 at 12:40
1
1
Second, and more significantly I think, doing model theory in PA (or any theory of first-order arithmetic - that is, numbers only) is inherently difficult since PA doesn't seem to have a way to talk directly about infinite structures (whereas finite structures, in a finite language at least, can be coded by natural numbers). There are ways around this, and in particular you may be interested in the [arithmetized completeness theorem](), but the difficulty is significant enough in my opinion that it's worth explicitly mentioning.
– Noah Schweber
Jul 28 at 12:44
Second, and more significantly I think, doing model theory in PA (or any theory of first-order arithmetic - that is, numbers only) is inherently difficult since PA doesn't seem to have a way to talk directly about infinite structures (whereas finite structures, in a finite language at least, can be coded by natural numbers). There are ways around this, and in particular you may be interested in the [arithmetized completeness theorem](), but the difficulty is significant enough in my opinion that it's worth explicitly mentioning.
– Noah Schweber
Jul 28 at 12:44
3
3
Good comments, Noah. I think you missed a link there at the second comment. :)
– Asaf Karagila
Jul 28 at 13:03
Good comments, Noah. I think you missed a link there at the second comment. :)
– Asaf Karagila
Jul 28 at 13:03
add a comment |Â
up vote
8
down vote
Yes, changing the "background theory" can lead to alternate proof/model theories. However, in order to get really meaningful differences (that is, differences at the "basic level" like the incompleteness theorem) you need to do significant damage to the background, to the point that it doesn't seem to hold much interest. I believe Hajek and Pudlak's book goes into proving basic proof theoretic results in weak theories of arithmetic, and I recommend it highly.
That said, violence is certainly entertaining! Visser's lovely paper Oracle bites theory shows how bad things can get once we kill arithmetic thoroughly enough (in particular, he shows that over a truly feeble base theory the set of consequences of a consistent theory need not be a consistent theory!), and Visser's other papers are probably also of interest to you.
Basically, in order to be skeptical of the incompleteness theorem we need to already be skeptical as such basic arithmetical principles as the totality of exponentiation. This is why from a foundational point of view the possibility has not received serious attention, though it may be of technical interest (I wouldn't know, I'm not an expert in the relevant area). This is similar to the situation with Cantor's diagonal argument, where the amount of set theory you have to break to make it non-applicable is so great that it's hardly worth doing, and certainly not foundationally compelling (so far as I know).
answered Jul 28 at 12:56
Noah Schweber
110k9139260
1
I seem to remember that Ed Nelson was sceptical about totality of exponentiation.
– Lord Shark the Unknown
Jul 28 at 14:28
add a comment |Â
up vote
8
down vote
Yes, changing the "background theory" can lead to alternate proof/model theories. However, in order to get really meaningful differences (that is, differences at the "basic level" like the incompleteness theorem) you need to do significant damage to the background, to the point that it doesn't seem to hold much interest. I believe Hajek and Pudlak's book goes into proving basic proof theoretic results in weak theories of arithmetic, and I recommend it highly.
That said, violence is certainly entertaining! Visser's lovely paper Oracle bites theory shows how bad things can get once we kill arithmetic thoroughly enough (in particular, he shows that over a truly feeble base theory the set of consequences of a consistent theory need not be a consistent theory!), and Visser's other papers are probably also of interest to you.
Basically, in order to be skeptical of the incompleteness theorem we need to already be skeptical as such basic arithmetical principles as the totality of exponentiation. This is why from a foundational point of view the possibility has not received serious attention, though it may be of technical interest (I wouldn't know, I'm not an expert in the relevant area). This is similar to the situation with Cantor's diagonal argument, where the amount of set theory you have to break to make it non-applicable is so great that it's hardly worth doing, and certainly not foundationally compelling (so far as I know).
answered Jul 28 at 12:56
Noah Schweber
110k9139260
1
I seem to remember that Ed Nelson was sceptical about totality of exponentiation.
– Lord Shark the Unknown
Jul 28 at 14:28
add a comment |Â
up vote
8
down vote
up vote
8
down vote
Yes, changing the "background theory" can lead to alternate proof/model theories. However, in order to get really meaningful differences (that is, differences at the "basic level" like the incompleteness theorem) you need to do significant damage to the background, to the point that it doesn't seem to hold much interest. I believe Hajek and Pudlak's book goes into proving basic proof theoretic results in weak theories of arithmetic, and I recommend it highly.
That said, violence is certainly entertaining! Visser's lovely paper Oracle bites theory shows how bad things can get once we kill arithmetic thoroughly enough (in particular, he shows that over a truly feeble base theory the set of consequences of a consistent theory need not be a consistent theory!), and Visser's other papers are probably also of interest to you.
Basically, in order to be skeptical of the incompleteness theorem we need to already be skeptical as such basic arithmetical principles as the totality of exponentiation. This is why from a foundational point of view the possibility has not received serious attention, though it may be of technical interest (I wouldn't know, I'm not an expert in the relevant area). This is similar to the situation with Cantor's diagonal argument, where the amount of set theory you have to break to make it non-applicable is so great that it's hardly worth doing, and certainly not foundationally compelling (so far as I know).
answered Jul 28 at 12:56
Noah Schweber
110k9139260
Yes, changing the "background theory" can lead to alternate proof/model theories. However, in order to get really meaningful differences (that is, differences at the "basic level" like the incompleteness theorem) you need to do significant damage to the background, to the point that it doesn't seem to hold much interest. I believe Hajek and Pudlak's book goes into proving basic proof theoretic results in weak theories of arithmetic, and I recommend it highly.
That said, violence is certainly entertaining! Visser's lovely paper Oracle bites theory shows how bad things can get once we kill arithmetic thoroughly enough (in particular, he shows that over a truly feeble base theory the set of consequences of a consistent theory need not be a consistent theory!), and Visser's other papers are probably also of interest to you.
Basically, in order to be skeptical of the incompleteness theorem we need to already be skeptical as such basic arithmetical principles as the totality of exponentiation. This is why from a foundational point of view the possibility has not received serious attention, though it may be of technical interest (I wouldn't know, I'm not an expert in the relevant area). This is similar to the situation with Cantor's diagonal argument, where the amount of set theory you have to break to make it non-applicable is so great that it's hardly worth doing, and certainly not foundationally compelling (so far as I know).
answered Jul 28 at 12:56
Noah Schweber
110k9139260
answered Jul 28 at 12:56
Noah Schweber
110k9139260
answered Jul 28 at 12:56
Noah Schweber
110k9139260
answered Jul 28 at 12:56
Noah Schweber
110k9139260
110k9139260
1
I seem to remember that Ed Nelson was sceptical about totality of exponentiation.
– Lord Shark the Unknown
Jul 28 at 14:28
add a comment |Â
1
I seem to remember that Ed Nelson was sceptical about totality of exponentiation.
– Lord Shark the Unknown
Jul 28 at 14:28
1
1
I seem to remember that Ed Nelson was sceptical about totality of exponentiation.
– Lord Shark the Unknown
Jul 28 at 14:28
I seem to remember that Ed Nelson was sceptical about totality of exponentiation.
– Lord Shark the Unknown
Jul 28 at 14:28
add a comment |Â
up vote
3
down vote
The main point about Gödel's Theorem is the method of proof. This shows that if the model or theory being used is rich enough, then it contains within it the resources to encode its own limitations in that it will either be inconsistent or incomplete (in the sense that there will be true statements which are unprovable within the system or model).
There are systems which escape Gödel's method, but they do so by being deliberately limited, rather than being too strong to fail.
answered Jul 28 at 11:34
Mark Bennet
76.4k773170
2
I don't think this really answers the question - I think the OP is asking about the theory in which, not about which, Godel's theorem is proved.
– Noah Schweber
Jul 28 at 12:47
@NoahSchweber I put this in as an answer because there seemed to me to be an implicit question "can I find a theory which avoids Gödel's Theorem?" and it seemed to be worth more than a comment.
– Mark Bennet
Jul 28 at 15:32
1
"can I find a theory which avoids Gödel's Theorem?" can mean two things: "is there a theory to which GT doesn't apply" or "is there a (reasonable) theory which thinks that GT isn't true?" (e.g. which is consistent and thinks that PA is complete). I think it's clear from the question that the latter is meant.
– Noah Schweber
Jul 28 at 15:56
add a comment |Â
up vote
3
down vote
The main point about Gödel's Theorem is the method of proof. This shows that if the model or theory being used is rich enough, then it contains within it the resources to encode its own limitations in that it will either be inconsistent or incomplete (in the sense that there will be true statements which are unprovable within the system or model).
There are systems which escape Gödel's method, but they do so by being deliberately limited, rather than being too strong to fail.
answered Jul 28 at 11:34
Mark Bennet
76.4k773170
2
I don't think this really answers the question - I think the OP is asking about the theory in which, not about which, Godel's theorem is proved.
– Noah Schweber
Jul 28 at 12:47
@NoahSchweber I put this in as an answer because there seemed to me to be an implicit question "can I find a theory which avoids Gödel's Theorem?" and it seemed to be worth more than a comment.
– Mark Bennet
Jul 28 at 15:32
1
"can I find a theory which avoids Gödel's Theorem?" can mean two things: "is there a theory to which GT doesn't apply" or "is there a (reasonable) theory which thinks that GT isn't true?" (e.g. which is consistent and thinks that PA is complete). I think it's clear from the question that the latter is meant.
– Noah Schweber
Jul 28 at 15:56
add a comment |Â
up vote
3
down vote
up vote
3
down vote
The main point about Gödel's Theorem is the method of proof. This shows that if the model or theory being used is rich enough, then it contains within it the resources to encode its own limitations in that it will either be inconsistent or incomplete (in the sense that there will be true statements which are unprovable within the system or model).
There are systems which escape Gödel's method, but they do so by being deliberately limited, rather than being too strong to fail.
answered Jul 28 at 11:34
Mark Bennet
76.4k773170
The main point about Gödel's Theorem is the method of proof. This shows that if the model or theory being used is rich enough, then it contains within it the resources to encode its own limitations in that it will either be inconsistent or incomplete (in the sense that there will be true statements which are unprovable within the system or model).
There are systems which escape Gödel's method, but they do so by being deliberately limited, rather than being too strong to fail.
answered Jul 28 at 11:34
Mark Bennet
76.4k773170
answered Jul 28 at 11:34
Mark Bennet
76.4k773170
answered Jul 28 at 11:34
Mark Bennet
76.4k773170
answered Jul 28 at 11:34
Mark Bennet
76.4k773170
76.4k773170
2
I don't think this really answers the question - I think the OP is asking about the theory in which, not about which, Godel's theorem is proved.
– Noah Schweber
Jul 28 at 12:47
@NoahSchweber I put this in as an answer because there seemed to me to be an implicit question "can I find a theory which avoids Gödel's Theorem?" and it seemed to be worth more than a comment.
– Mark Bennet
Jul 28 at 15:32
1
"can I find a theory which avoids Gödel's Theorem?" can mean two things: "is there a theory to which GT doesn't apply" or "is there a (reasonable) theory which thinks that GT isn't true?" (e.g. which is consistent and thinks that PA is complete). I think it's clear from the question that the latter is meant.
– Noah Schweber
Jul 28 at 15:56
add a comment |Â
2
I don't think this really answers the question - I think the OP is asking about the theory in which, not about which, Godel's theorem is proved.
– Noah Schweber
Jul 28 at 12:47
@NoahSchweber I put this in as an answer because there seemed to me to be an implicit question "can I find a theory which avoids Gödel's Theorem?" and it seemed to be worth more than a comment.
– Mark Bennet
Jul 28 at 15:32
1
"can I find a theory which avoids Gödel's Theorem?" can mean two things: "is there a theory to which GT doesn't apply" or "is there a (reasonable) theory which thinks that GT isn't true?" (e.g. which is consistent and thinks that PA is complete). I think it's clear from the question that the latter is meant.
– Noah Schweber
Jul 28 at 15:56
2
2
I don't think this really answers the question - I think the OP is asking about the theory in which, not about which, Godel's theorem is proved.
– Noah Schweber
Jul 28 at 12:47
I don't think this really answers the question - I think the OP is asking about the theory in which, not about which, Godel's theorem is proved.
– Noah Schweber
Jul 28 at 12:47
@NoahSchweber I put this in as an answer because there seemed to me to be an implicit question "can I find a theory which avoids Gödel's Theorem?" and it seemed to be worth more than a comment.
– Mark Bennet
Jul 28 at 15:32
@NoahSchweber I put this in as an answer because there seemed to me to be an implicit question "can I find a theory which avoids Gödel's Theorem?" and it seemed to be worth more than a comment.
– Mark Bennet
Jul 28 at 15:32
1
1
"can I find a theory which avoids Gödel's Theorem?" can mean two things: "is there a theory to which GT doesn't apply" or "is there a (reasonable) theory which thinks that GT isn't true?" (e.g. which is consistent and thinks that PA is complete). I think it's clear from the question that the latter is meant.
– Noah Schweber
Jul 28 at 15:56
"can I find a theory which avoids Gödel's Theorem?" can mean two things: "is there a theory to which GT doesn't apply" or "is there a (reasonable) theory which thinks that GT isn't true?" (e.g. which is consistent and thinks that PA is complete). I think it's clear from the question that the latter is meant.
– Noah Schweber
Jul 28 at 15:56
add a comment |Â
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%2f2865180%2fis-set-theory-used-in-proofs-of-theorems-in-logic%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
Goedels incompleteness theorem is not only about ZFC. It states that every sufficient strong system (PA is enough) is either inconsistent or incomplete.
– Peter
Jul 28 at 11:31
There are statements provable in ZFC, but not in PA , the most famous example is the statement that every Goodstein-sequence eventually terminates.
– Peter
Jul 28 at 11:33
3
@Peter I think the question is asking about the theory in which, not about which, these results are proved.
– Noah Schweber
Jul 28 at 12:47