A Growing Tree of Theories
$begingroup$
Gödel' Incompleteness Theorem (GIT) states that certain theories $T$ (formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent, and effectively axiomatized) e.g. Peano Arithmetic, are incomplete, i.e. there are statements $S_k$ that can't be proven right or wrong within the theory, by which I mean composing the axioms of the theory.
The way out is to accept the unprovable statement $S_1$ either as true or false, which by GIT leads to another theory that is again incomplete. In fact even two theories! Let's choose "false" for the moment and I'll write $lnot S_1$ for that. If we go on (turning coffee into theorems), we'll reach the next unprovable statement $S_2$ (which might depend on $S_1$ being false) and are left with another decision, whether to accept this as true or false. Now we already have five(!) theories:
- $T_0$
$T_0cup{S_1}$
$T_0cup{lnot S_1)}$
$T_0cup{lnot S_1,S_2}$
$T_0cup{lnot S_1,lnot S_2}$
This approach can be continued. Our resulting (incomplete) theory is described by a sequence of unprovable, but as true or false accepted, statements. Properly arranged this looks like a tree graph.
What is known about this tree? Does it have loops? (No loops, see Alex' comments)
I'm also looking for references...
incompleteness
asked Jan 23 at 19:39
draks ...draks ...
11.5k644131
$endgroup$
|
show 1 more comment
$begingroup$
Gödel' Incompleteness Theorem (GIT) states that certain theories $T$ (formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent, and effectively axiomatized) e.g. Peano Arithmetic, are incomplete, i.e. there are statements $S_k$ that can't be proven right or wrong within the theory, by which I mean composing the axioms of the theory.
The way out is to accept the unprovable statement $S_1$ either as true or false, which by GIT leads to another theory that is again incomplete. In fact even two theories! Let's choose "false" for the moment and I'll write $lnot S_1$ for that. If we go on (turning coffee into theorems), we'll reach the next unprovable statement $S_2$ (which might depend on $S_1$ being false) and are left with another decision, whether to accept this as true or false. Now we already have five(!) theories:
- $T_0$
$T_0cup{S_1}$
$T_0cup{lnot S_1)}$
$T_0cup{lnot S_1,S_2}$
$T_0cup{lnot S_1,lnot S_2}$
This approach can be continued. Our resulting (incomplete) theory is described by a sequence of unprovable, but as true or false accepted, statements. Properly arranged this looks like a tree graph.
What is known about this tree? Does it have loops? (No loops, see Alex' comments)
I'm also looking for references...
incompleteness
asked Jan 23 at 19:39
draks ...draks ...
11.5k644131
$endgroup$
$begingroup$
"What is known about this tree?" Isn't it obviously just a complete binary tree? By asking about loops, I guess you're wondering if two theories in the tree might be equivalent? The answer is no, since every node in the tree is a consistent theory, and given any two theories $T$ and $T'$ in the tree, either one properly extends the other (i.e. $T'$ is below $T$ in the tree, so it contains a sentence which is not provable from $T$), or $T$ and $T'$ disagree about the truth of some sentence (the sentence $S$ chosen by incompleteness for the greatest common ancestor of $T$ and $T'$ in the tree).
$endgroup$
– Alex Kruckman
Jan 23 at 19:52
$begingroup$
@AlexKruckman what about a theory that has two unprovable statements, and accepting the first also proves the second, but denying it has no consequence on the second. Is this possible? If, then the binary tree wouldn't be complete...
$endgroup$
– draks ...
Jan 23 at 20:02
$begingroup$
Oh, maybe I misunderstood how you are constructing the tree. I thought you picked $S_2$ (in the example in your question) to be independent from $T_0cup {lnot S_1}$. Then in the other branch, you would pick a sentence $S_2'$ independent from $T_0cup {S_1}$, giving 4 theories: $T_0cup {S_1,S_2'}$, $T_0cup {S_1, lnot S_2'}$, $T_0cup {lnot S_1, S_2}$, and $T_0cup {lnot S_1, lnot S_2}$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:05
4
$begingroup$
If instead you start with some fixed enumeration $S_1, S_2, S_2, dots$ of sentences independent of $T_0$, then the structure of the tree will of course depend heavily on the particular enumeration of the $S_n$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:06
$begingroup$
@Alex do you think the case of Peano arithmetics is properly invertigated? Any idea where to look?
$endgroup$
– draks ...
Jan 24 at 22:11
|
show 1 more comment
$begingroup$
Gödel' Incompleteness Theorem (GIT) states that certain theories $T$ (formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent, and effectively axiomatized) e.g. Peano Arithmetic, are incomplete, i.e. there are statements $S_k$ that can't be proven right or wrong within the theory, by which I mean composing the axioms of the theory.
The way out is to accept the unprovable statement $S_1$ either as true or false, which by GIT leads to another theory that is again incomplete. In fact even two theories! Let's choose "false" for the moment and I'll write $lnot S_1$ for that. If we go on (turning coffee into theorems), we'll reach the next unprovable statement $S_2$ (which might depend on $S_1$ being false) and are left with another decision, whether to accept this as true or false. Now we already have five(!) theories:
- $T_0$
$T_0cup{S_1}$
$T_0cup{lnot S_1)}$
$T_0cup{lnot S_1,S_2}$
$T_0cup{lnot S_1,lnot S_2}$
This approach can be continued. Our resulting (incomplete) theory is described by a sequence of unprovable, but as true or false accepted, statements. Properly arranged this looks like a tree graph.
What is known about this tree? Does it have loops? (No loops, see Alex' comments)
I'm also looking for references...
incompleteness
asked Jan 23 at 19:39
draks ...draks ...
11.5k644131
$endgroup$
Gödel' Incompleteness Theorem (GIT) states that certain theories $T$ (formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent, and effectively axiomatized) e.g. Peano Arithmetic, are incomplete, i.e. there are statements $S_k$ that can't be proven right or wrong within the theory, by which I mean composing the axioms of the theory.
The way out is to accept the unprovable statement $S_1$ either as true or false, which by GIT leads to another theory that is again incomplete. In fact even two theories! Let's choose "false" for the moment and I'll write $lnot S_1$ for that. If we go on (turning coffee into theorems), we'll reach the next unprovable statement $S_2$ (which might depend on $S_1$ being false) and are left with another decision, whether to accept this as true or false. Now we already have five(!) theories:
- $T_0$
$T_0cup{S_1}$
$T_0cup{lnot S_1)}$
$T_0cup{lnot S_1,S_2}$
$T_0cup{lnot S_1,lnot S_2}$
This approach can be continued. Our resulting (incomplete) theory is described by a sequence of unprovable, but as true or false accepted, statements. Properly arranged this looks like a tree graph.
What is known about this tree? Does it have loops? (No loops, see Alex' comments)
I'm also looking for references...
incompleteness
incompleteness
asked Jan 23 at 19:39
draks ...draks ...
11.5k644131
asked Jan 23 at 19:39
draks ...draks ...
11.5k644131
edited Jan 24 at 22:08
draks ...
asked Jan 23 at 19:39
draks ...draks ...
11.5k644131
asked Jan 23 at 19:39
draks ...draks ...
11.5k644131
asked Jan 23 at 19:39
draks ...draks ...
11.5k644131
11.5k644131
$begingroup$
"What is known about this tree?" Isn't it obviously just a complete binary tree? By asking about loops, I guess you're wondering if two theories in the tree might be equivalent? The answer is no, since every node in the tree is a consistent theory, and given any two theories $T$ and $T'$ in the tree, either one properly extends the other (i.e. $T'$ is below $T$ in the tree, so it contains a sentence which is not provable from $T$), or $T$ and $T'$ disagree about the truth of some sentence (the sentence $S$ chosen by incompleteness for the greatest common ancestor of $T$ and $T'$ in the tree).
$endgroup$
– Alex Kruckman
Jan 23 at 19:52
$begingroup$
@AlexKruckman what about a theory that has two unprovable statements, and accepting the first also proves the second, but denying it has no consequence on the second. Is this possible? If, then the binary tree wouldn't be complete...
$endgroup$
– draks ...
Jan 23 at 20:02
$begingroup$
Oh, maybe I misunderstood how you are constructing the tree. I thought you picked $S_2$ (in the example in your question) to be independent from $T_0cup {lnot S_1}$. Then in the other branch, you would pick a sentence $S_2'$ independent from $T_0cup {S_1}$, giving 4 theories: $T_0cup {S_1,S_2'}$, $T_0cup {S_1, lnot S_2'}$, $T_0cup {lnot S_1, S_2}$, and $T_0cup {lnot S_1, lnot S_2}$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:05
4
$begingroup$
If instead you start with some fixed enumeration $S_1, S_2, S_2, dots$ of sentences independent of $T_0$, then the structure of the tree will of course depend heavily on the particular enumeration of the $S_n$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:06
$begingroup$
@Alex do you think the case of Peano arithmetics is properly invertigated? Any idea where to look?
$endgroup$
– draks ...
Jan 24 at 22:11
|
show 1 more comment
$begingroup$
"What is known about this tree?" Isn't it obviously just a complete binary tree? By asking about loops, I guess you're wondering if two theories in the tree might be equivalent? The answer is no, since every node in the tree is a consistent theory, and given any two theories $T$ and $T'$ in the tree, either one properly extends the other (i.e. $T'$ is below $T$ in the tree, so it contains a sentence which is not provable from $T$), or $T$ and $T'$ disagree about the truth of some sentence (the sentence $S$ chosen by incompleteness for the greatest common ancestor of $T$ and $T'$ in the tree).
$endgroup$
– Alex Kruckman
Jan 23 at 19:52
$begingroup$
@AlexKruckman what about a theory that has two unprovable statements, and accepting the first also proves the second, but denying it has no consequence on the second. Is this possible? If, then the binary tree wouldn't be complete...
$endgroup$
– draks ...
Jan 23 at 20:02
$begingroup$
Oh, maybe I misunderstood how you are constructing the tree. I thought you picked $S_2$ (in the example in your question) to be independent from $T_0cup {lnot S_1}$. Then in the other branch, you would pick a sentence $S_2'$ independent from $T_0cup {S_1}$, giving 4 theories: $T_0cup {S_1,S_2'}$, $T_0cup {S_1, lnot S_2'}$, $T_0cup {lnot S_1, S_2}$, and $T_0cup {lnot S_1, lnot S_2}$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:05
4
$begingroup$
If instead you start with some fixed enumeration $S_1, S_2, S_2, dots$ of sentences independent of $T_0$, then the structure of the tree will of course depend heavily on the particular enumeration of the $S_n$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:06
$begingroup$
@Alex do you think the case of Peano arithmetics is properly invertigated? Any idea where to look?
$endgroup$
– draks ...
Jan 24 at 22:11
$begingroup$
"What is known about this tree?" Isn't it obviously just a complete binary tree? By asking about loops, I guess you're wondering if two theories in the tree might be equivalent? The answer is no, since every node in the tree is a consistent theory, and given any two theories $T$ and $T'$ in the tree, either one properly extends the other (i.e. $T'$ is below $T$ in the tree, so it contains a sentence which is not provable from $T$), or $T$ and $T'$ disagree about the truth of some sentence (the sentence $S$ chosen by incompleteness for the greatest common ancestor of $T$ and $T'$ in the tree).
$endgroup$
– Alex Kruckman
Jan 23 at 19:52
$begingroup$
"What is known about this tree?" Isn't it obviously just a complete binary tree? By asking about loops, I guess you're wondering if two theories in the tree might be equivalent? The answer is no, since every node in the tree is a consistent theory, and given any two theories $T$ and $T'$ in the tree, either one properly extends the other (i.e. $T'$ is below $T$ in the tree, so it contains a sentence which is not provable from $T$), or $T$ and $T'$ disagree about the truth of some sentence (the sentence $S$ chosen by incompleteness for the greatest common ancestor of $T$ and $T'$ in the tree).
$endgroup$
– Alex Kruckman
Jan 23 at 19:52
$begingroup$
@AlexKruckman what about a theory that has two unprovable statements, and accepting the first also proves the second, but denying it has no consequence on the second. Is this possible? If, then the binary tree wouldn't be complete...
$endgroup$
– draks ...
Jan 23 at 20:02
$begingroup$
@AlexKruckman what about a theory that has two unprovable statements, and accepting the first also proves the second, but denying it has no consequence on the second. Is this possible? If, then the binary tree wouldn't be complete...
$endgroup$
– draks ...
Jan 23 at 20:02
$begingroup$
Oh, maybe I misunderstood how you are constructing the tree. I thought you picked $S_2$ (in the example in your question) to be independent from $T_0cup {lnot S_1}$. Then in the other branch, you would pick a sentence $S_2'$ independent from $T_0cup {S_1}$, giving 4 theories: $T_0cup {S_1,S_2'}$, $T_0cup {S_1, lnot S_2'}$, $T_0cup {lnot S_1, S_2}$, and $T_0cup {lnot S_1, lnot S_2}$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:05
$begingroup$
Oh, maybe I misunderstood how you are constructing the tree. I thought you picked $S_2$ (in the example in your question) to be independent from $T_0cup {lnot S_1}$. Then in the other branch, you would pick a sentence $S_2'$ independent from $T_0cup {S_1}$, giving 4 theories: $T_0cup {S_1,S_2'}$, $T_0cup {S_1, lnot S_2'}$, $T_0cup {lnot S_1, S_2}$, and $T_0cup {lnot S_1, lnot S_2}$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:05
4
4
$begingroup$
If instead you start with some fixed enumeration $S_1, S_2, S_2, dots$ of sentences independent of $T_0$, then the structure of the tree will of course depend heavily on the particular enumeration of the $S_n$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:06
$begingroup$
If instead you start with some fixed enumeration $S_1, S_2, S_2, dots$ of sentences independent of $T_0$, then the structure of the tree will of course depend heavily on the particular enumeration of the $S_n$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:06
$begingroup$
@Alex do you think the case of Peano arithmetics is properly invertigated? Any idea where to look?
$endgroup$
– draks ...
Jan 24 at 22:11
$begingroup$
@Alex do you think the case of Peano arithmetics is properly invertigated? Any idea where to look?
$endgroup$
– draks ...
Jan 24 at 22:11
|
show 1 more comment
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3084960%2fa-growing-tree-of-theories%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3084960%2fa-growing-tree-of-theories%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
"What is known about this tree?" Isn't it obviously just a complete binary tree? By asking about loops, I guess you're wondering if two theories in the tree might be equivalent? The answer is no, since every node in the tree is a consistent theory, and given any two theories $T$ and $T'$ in the tree, either one properly extends the other (i.e. $T'$ is below $T$ in the tree, so it contains a sentence which is not provable from $T$), or $T$ and $T'$ disagree about the truth of some sentence (the sentence $S$ chosen by incompleteness for the greatest common ancestor of $T$ and $T'$ in the tree).
$endgroup$
– Alex Kruckman
Jan 23 at 19:52
$begingroup$
@AlexKruckman what about a theory that has two unprovable statements, and accepting the first also proves the second, but denying it has no consequence on the second. Is this possible? If, then the binary tree wouldn't be complete...
$endgroup$
– draks ...
Jan 23 at 20:02
$begingroup$
Oh, maybe I misunderstood how you are constructing the tree. I thought you picked $S_2$ (in the example in your question) to be independent from $T_0cup {lnot S_1}$. Then in the other branch, you would pick a sentence $S_2'$ independent from $T_0cup {S_1}$, giving 4 theories: $T_0cup {S_1,S_2'}$, $T_0cup {S_1, lnot S_2'}$, $T_0cup {lnot S_1, S_2}$, and $T_0cup {lnot S_1, lnot S_2}$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:05
4
$begingroup$
If instead you start with some fixed enumeration $S_1, S_2, S_2, dots$ of sentences independent of $T_0$, then the structure of the tree will of course depend heavily on the particular enumeration of the $S_n$.
$endgroup$
– Alex Kruckman
Jan 23 at 20:06
$begingroup$
@Alex do you think the case of Peano arithmetics is properly invertigated? Any idea where to look?
$endgroup$
– draks ...
Jan 24 at 22:11