Pardon my ignorance, but isn't TREE(3) a finite number?
$begingroup$
Pardon my ignorance, but isn't TREE(3) a finite number? -Dylan Thurston
It is my understanding as well that TREE(3) is finite (Proof that TREE(n) where n >= 3 is finite?).
However, I have seen statements such as:
TREE(3) is known to exceed the $Gamma_0$-level, which is much higher than the $epsilon_0$-level. -Source
It is also my understanding that $omega < epsilon_0 < Gamma_0$ (where $omega$, $epsilon_0$ & $Gamma_0$ are transfinite).
If $Gamma_0<TREE(3)$, wouldn't that imply TREE(3) is transfinite?
ordinals trees fixed-point-theorems transfinite-recursion
edited Dec 19 '18 at 1:48
Martin Sleziak
44.8k10118272
asked Dec 18 '18 at 22:08
meowzzmeowzz
91212
$endgroup$
|
show 3 more comments
$begingroup$
Pardon my ignorance, but isn't TREE(3) a finite number? -Dylan Thurston
It is my understanding as well that TREE(3) is finite (Proof that TREE(n) where n >= 3 is finite?).
However, I have seen statements such as:
TREE(3) is known to exceed the $Gamma_0$-level, which is much higher than the $epsilon_0$-level. -Source
It is also my understanding that $omega < epsilon_0 < Gamma_0$ (where $omega$, $epsilon_0$ & $Gamma_0$ are transfinite).
If $Gamma_0<TREE(3)$, wouldn't that imply TREE(3) is transfinite?
ordinals trees fixed-point-theorems transfinite-recursion
edited Dec 19 '18 at 1:48
Martin Sleziak
44.8k10118272
asked Dec 18 '18 at 22:08
meowzzmeowzz
91212
$endgroup$
2
$begingroup$
I think this refers not to the size of $operatorname{TREE}(3)$ itself, but of the power of the formal system required to show that the expression “$operatorname{TREE}(3)$” is meaningfully defined. Recall that the definition of $operatorname{TREE}$ begins “the maximum value such that…”. In general there may not be such a maximum value; its existence requires a proof, typically an inductive proof. Some axiomatic systems are only strong enough to provide induction over a set of size $epsilon_0$; others, more powerful, can induct over larger sets.
$endgroup$
– MJD
Dec 18 '18 at 22:14
1
$begingroup$
I have no idea!
$endgroup$
– MJD
Dec 19 '18 at 0:29
1
$begingroup$
The claim is made in the context of a specific fast growing hierarchy of functions $f_alpha!:mathbb Ntomathbb N$. I assume that what they mean is that $f_{Gamma_0}(3)<mathrm{TREE}(3)$.
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:05
1
$begingroup$
(The question on MO linked to at the beginning explains this for a different $alpha$.)
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:09
1
$begingroup$
@AndrésE.Caicedo I think your comments are very nearly the answer to the question, so feel free to expand them to an answer.
$endgroup$
– Mark S.
Dec 19 '18 at 2:42
|
show 3 more comments
$begingroup$
Pardon my ignorance, but isn't TREE(3) a finite number? -Dylan Thurston
It is my understanding as well that TREE(3) is finite (Proof that TREE(n) where n >= 3 is finite?).
However, I have seen statements such as:
TREE(3) is known to exceed the $Gamma_0$-level, which is much higher than the $epsilon_0$-level. -Source
It is also my understanding that $omega < epsilon_0 < Gamma_0$ (where $omega$, $epsilon_0$ & $Gamma_0$ are transfinite).
If $Gamma_0<TREE(3)$, wouldn't that imply TREE(3) is transfinite?
ordinals trees fixed-point-theorems transfinite-recursion
edited Dec 19 '18 at 1:48
Martin Sleziak
44.8k10118272
asked Dec 18 '18 at 22:08
meowzzmeowzz
91212
$endgroup$
Pardon my ignorance, but isn't TREE(3) a finite number? -Dylan Thurston
It is my understanding as well that TREE(3) is finite (Proof that TREE(n) where n >= 3 is finite?).
However, I have seen statements such as:
TREE(3) is known to exceed the $Gamma_0$-level, which is much higher than the $epsilon_0$-level. -Source
It is also my understanding that $omega < epsilon_0 < Gamma_0$ (where $omega$, $epsilon_0$ & $Gamma_0$ are transfinite).
If $Gamma_0<TREE(3)$, wouldn't that imply TREE(3) is transfinite?
ordinals trees fixed-point-theorems transfinite-recursion
ordinals trees fixed-point-theorems transfinite-recursion
edited Dec 19 '18 at 1:48
Martin Sleziak
44.8k10118272
asked Dec 18 '18 at 22:08
meowzzmeowzz
91212
edited Dec 19 '18 at 1:48
Martin Sleziak
44.8k10118272
asked Dec 18 '18 at 22:08
meowzzmeowzz
91212
edited Dec 19 '18 at 1:48
Martin Sleziak
44.8k10118272
edited Dec 19 '18 at 1:48
Martin Sleziak
44.8k10118272
edited Dec 19 '18 at 1:48
Martin Sleziak
44.8k10118272
44.8k10118272
asked Dec 18 '18 at 22:08
meowzzmeowzz
91212
asked Dec 18 '18 at 22:08
meowzzmeowzz
91212
asked Dec 18 '18 at 22:08
meowzzmeowzz
91212
91212
2
$begingroup$
I think this refers not to the size of $operatorname{TREE}(3)$ itself, but of the power of the formal system required to show that the expression “$operatorname{TREE}(3)$” is meaningfully defined. Recall that the definition of $operatorname{TREE}$ begins “the maximum value such that…”. In general there may not be such a maximum value; its existence requires a proof, typically an inductive proof. Some axiomatic systems are only strong enough to provide induction over a set of size $epsilon_0$; others, more powerful, can induct over larger sets.
$endgroup$
– MJD
Dec 18 '18 at 22:14
1
$begingroup$
I have no idea!
$endgroup$
– MJD
Dec 19 '18 at 0:29
1
$begingroup$
The claim is made in the context of a specific fast growing hierarchy of functions $f_alpha!:mathbb Ntomathbb N$. I assume that what they mean is that $f_{Gamma_0}(3)<mathrm{TREE}(3)$.
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:05
1
$begingroup$
(The question on MO linked to at the beginning explains this for a different $alpha$.)
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:09
1
$begingroup$
@AndrésE.Caicedo I think your comments are very nearly the answer to the question, so feel free to expand them to an answer.
$endgroup$
– Mark S.
Dec 19 '18 at 2:42
|
show 3 more comments
2
$begingroup$
I think this refers not to the size of $operatorname{TREE}(3)$ itself, but of the power of the formal system required to show that the expression “$operatorname{TREE}(3)$” is meaningfully defined. Recall that the definition of $operatorname{TREE}$ begins “the maximum value such that…”. In general there may not be such a maximum value; its existence requires a proof, typically an inductive proof. Some axiomatic systems are only strong enough to provide induction over a set of size $epsilon_0$; others, more powerful, can induct over larger sets.
$endgroup$
– MJD
Dec 18 '18 at 22:14
1
$begingroup$
I have no idea!
$endgroup$
– MJD
Dec 19 '18 at 0:29
1
$begingroup$
The claim is made in the context of a specific fast growing hierarchy of functions $f_alpha!:mathbb Ntomathbb N$. I assume that what they mean is that $f_{Gamma_0}(3)<mathrm{TREE}(3)$.
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:05
1
$begingroup$
(The question on MO linked to at the beginning explains this for a different $alpha$.)
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:09
1
$begingroup$
@AndrésE.Caicedo I think your comments are very nearly the answer to the question, so feel free to expand them to an answer.
$endgroup$
– Mark S.
Dec 19 '18 at 2:42
2
2
$begingroup$
I think this refers not to the size of $operatorname{TREE}(3)$ itself, but of the power of the formal system required to show that the expression “$operatorname{TREE}(3)$” is meaningfully defined. Recall that the definition of $operatorname{TREE}$ begins “the maximum value such that…”. In general there may not be such a maximum value; its existence requires a proof, typically an inductive proof. Some axiomatic systems are only strong enough to provide induction over a set of size $epsilon_0$; others, more powerful, can induct over larger sets.
$endgroup$
– MJD
Dec 18 '18 at 22:14
$begingroup$
I think this refers not to the size of $operatorname{TREE}(3)$ itself, but of the power of the formal system required to show that the expression “$operatorname{TREE}(3)$” is meaningfully defined. Recall that the definition of $operatorname{TREE}$ begins “the maximum value such that…”. In general there may not be such a maximum value; its existence requires a proof, typically an inductive proof. Some axiomatic systems are only strong enough to provide induction over a set of size $epsilon_0$; others, more powerful, can induct over larger sets.
$endgroup$
– MJD
Dec 18 '18 at 22:14
1
1
$begingroup$
I have no idea!
$endgroup$
– MJD
Dec 19 '18 at 0:29
$begingroup$
I have no idea!
$endgroup$
– MJD
Dec 19 '18 at 0:29
1
1
$begingroup$
The claim is made in the context of a specific fast growing hierarchy of functions $f_alpha!:mathbb Ntomathbb N$. I assume that what they mean is that $f_{Gamma_0}(3)<mathrm{TREE}(3)$.
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:05
$begingroup$
The claim is made in the context of a specific fast growing hierarchy of functions $f_alpha!:mathbb Ntomathbb N$. I assume that what they mean is that $f_{Gamma_0}(3)<mathrm{TREE}(3)$.
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:05
1
1
$begingroup$
(The question on MO linked to at the beginning explains this for a different $alpha$.)
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:09
$begingroup$
(The question on MO linked to at the beginning explains this for a different $alpha$.)
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:09
1
1
$begingroup$
@AndrésE.Caicedo I think your comments are very nearly the answer to the question, so feel free to expand them to an answer.
$endgroup$
– Mark S.
Dec 19 '18 at 2:42
$begingroup$
@AndrésE.Caicedo I think your comments are very nearly the answer to the question, so feel free to expand them to an answer.
$endgroup$
– Mark S.
Dec 19 '18 at 2:42
|
show 3 more comments
1 Answer
1
active
oldest
votes
$begingroup$
This is indeed a confusing bit of language. $TREE(3)$ is indeed finite. I think the later comment by Peter clears things up:
"For example, Graham's number is approximately $f_{omega+1}(64)$, so we say that Graham's number is at level $f_{omega+1}$, or [for] short at the $omega+1$-level."
Basically, we want to say that a number is "at level $kappa$" if it is $f_kappa(s)$ for some "small" $s$ (e.g. here $64$ is considered small). Note that this is a subjective distinction - what's the least non-small number? :P - but it still gives a sense of the size of the number involved. The point, roughly, is to say: $TREE(3)$ is so huge that, even with a special symbol for $f_{Gamma_0}$, it is still infeasible to express $TREE(3)$.
There are various precise versions of this - e.g. the statement "$f_{Gamma_0}(3)<TREE(3)$" (per Andres) is a perfectly precise statement, and (I believe) is known to be true - but I think it's better to view this as a general piece of descriptive language
answered Dec 19 '18 at 3:16
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
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%2f3045770%2fpardon-my-ignorance-but-isnt-tree3-a-finite-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is indeed a confusing bit of language. $TREE(3)$ is indeed finite. I think the later comment by Peter clears things up:
"For example, Graham's number is approximately $f_{omega+1}(64)$, so we say that Graham's number is at level $f_{omega+1}$, or [for] short at the $omega+1$-level."
Basically, we want to say that a number is "at level $kappa$" if it is $f_kappa(s)$ for some "small" $s$ (e.g. here $64$ is considered small). Note that this is a subjective distinction - what's the least non-small number? :P - but it still gives a sense of the size of the number involved. The point, roughly, is to say: $TREE(3)$ is so huge that, even with a special symbol for $f_{Gamma_0}$, it is still infeasible to express $TREE(3)$.
There are various precise versions of this - e.g. the statement "$f_{Gamma_0}(3)<TREE(3)$" (per Andres) is a perfectly precise statement, and (I believe) is known to be true - but I think it's better to view this as a general piece of descriptive language
answered Dec 19 '18 at 3:16
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
$begingroup$
This is indeed a confusing bit of language. $TREE(3)$ is indeed finite. I think the later comment by Peter clears things up:
"For example, Graham's number is approximately $f_{omega+1}(64)$, so we say that Graham's number is at level $f_{omega+1}$, or [for] short at the $omega+1$-level."
Basically, we want to say that a number is "at level $kappa$" if it is $f_kappa(s)$ for some "small" $s$ (e.g. here $64$ is considered small). Note that this is a subjective distinction - what's the least non-small number? :P - but it still gives a sense of the size of the number involved. The point, roughly, is to say: $TREE(3)$ is so huge that, even with a special symbol for $f_{Gamma_0}$, it is still infeasible to express $TREE(3)$.
There are various precise versions of this - e.g. the statement "$f_{Gamma_0}(3)<TREE(3)$" (per Andres) is a perfectly precise statement, and (I believe) is known to be true - but I think it's better to view this as a general piece of descriptive language
answered Dec 19 '18 at 3:16
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
$begingroup$
This is indeed a confusing bit of language. $TREE(3)$ is indeed finite. I think the later comment by Peter clears things up:
"For example, Graham's number is approximately $f_{omega+1}(64)$, so we say that Graham's number is at level $f_{omega+1}$, or [for] short at the $omega+1$-level."
Basically, we want to say that a number is "at level $kappa$" if it is $f_kappa(s)$ for some "small" $s$ (e.g. here $64$ is considered small). Note that this is a subjective distinction - what's the least non-small number? :P - but it still gives a sense of the size of the number involved. The point, roughly, is to say: $TREE(3)$ is so huge that, even with a special symbol for $f_{Gamma_0}$, it is still infeasible to express $TREE(3)$.
There are various precise versions of this - e.g. the statement "$f_{Gamma_0}(3)<TREE(3)$" (per Andres) is a perfectly precise statement, and (I believe) is known to be true - but I think it's better to view this as a general piece of descriptive language
answered Dec 19 '18 at 3:16
Noah SchweberNoah Schweber
125k10150287
$endgroup$
This is indeed a confusing bit of language. $TREE(3)$ is indeed finite. I think the later comment by Peter clears things up:
"For example, Graham's number is approximately $f_{omega+1}(64)$, so we say that Graham's number is at level $f_{omega+1}$, or [for] short at the $omega+1$-level."
Basically, we want to say that a number is "at level $kappa$" if it is $f_kappa(s)$ for some "small" $s$ (e.g. here $64$ is considered small). Note that this is a subjective distinction - what's the least non-small number? :P - but it still gives a sense of the size of the number involved. The point, roughly, is to say: $TREE(3)$ is so huge that, even with a special symbol for $f_{Gamma_0}$, it is still infeasible to express $TREE(3)$.
There are various precise versions of this - e.g. the statement "$f_{Gamma_0}(3)<TREE(3)$" (per Andres) is a perfectly precise statement, and (I believe) is known to be true - but I think it's better to view this as a general piece of descriptive language
answered Dec 19 '18 at 3:16
Noah SchweberNoah Schweber
125k10150287
answered Dec 19 '18 at 3:16
Noah SchweberNoah Schweber
125k10150287
answered Dec 19 '18 at 3:16
Noah SchweberNoah Schweber
125k10150287
answered Dec 19 '18 at 3:16
Noah SchweberNoah Schweber
125k10150287
125k10150287
add a comment |
add a comment |
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%2f3045770%2fpardon-my-ignorance-but-isnt-tree3-a-finite-number%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
2
$begingroup$
I think this refers not to the size of $operatorname{TREE}(3)$ itself, but of the power of the formal system required to show that the expression “$operatorname{TREE}(3)$” is meaningfully defined. Recall that the definition of $operatorname{TREE}$ begins “the maximum value such that…”. In general there may not be such a maximum value; its existence requires a proof, typically an inductive proof. Some axiomatic systems are only strong enough to provide induction over a set of size $epsilon_0$; others, more powerful, can induct over larger sets.
$endgroup$
– MJD
Dec 18 '18 at 22:14
1
$begingroup$
I have no idea!
$endgroup$
– MJD
Dec 19 '18 at 0:29
1
$begingroup$
The claim is made in the context of a specific fast growing hierarchy of functions $f_alpha!:mathbb Ntomathbb N$. I assume that what they mean is that $f_{Gamma_0}(3)<mathrm{TREE}(3)$.
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:05
1
$begingroup$
(The question on MO linked to at the beginning explains this for a different $alpha$.)
$endgroup$
– Andrés E. Caicedo
Dec 19 '18 at 2:09
1
$begingroup$
@AndrésE.Caicedo I think your comments are very nearly the answer to the question, so feel free to expand them to an answer.
$endgroup$
– Mark S.
Dec 19 '18 at 2:42