TREE函数 - 版本历史

2025年8月20日 (三) 08:17 Z

2025-08-20T08:17:39Z

←上一版本		2025年8月20日 (三) 16:17的版本
第75行：		第75行：
	${\rm tree(n)}\sim\varphi(1@\omega)$		${\rm tree(n)}\sim\varphi(1@\omega)$
	== 参考资料 ==		== 参考资料 ==
	<references />		<references />{{默认排序:相关问题}}
	[[分类:记号]]		[[分类:记号]]

Tabelog：修正参考资料

2025-07-30T05:54:55Z

修正参考资料

←上一版本		2025年7月30日 (三) 13:54的版本
第61行：		第61行：
	右图是 <math>\rm TREE(3)</math> 序列可能的前几项。		右图是 <math>\rm TREE(3)</math> 序列可能的前几项。

	HypCos 在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了 <math>\rm TREE(3)</math> 的一个下界：		HypCos 在这篇回答<ref>HypCos (2019). 从数学原理上说一说，葛立恒数、tree(3) 等数为什么那么大？[From a mathematical point of view, why are Graham's constants, tree(3) and other numbers so big?]. ''(EB/OL), Zhihu''. https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了 <math>\rm TREE(3)</math> 的一个下界：

	${\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})$（其中 H 为[[增长层级#哈代层级\|哈代层级]]，下同）		${\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})$（其中 H 为[[增长层级#哈代层级\|哈代层级]]，下同）

	==== tree(4) ====		==== tree(4) ====
	~~2025年5月24日，HypCos~~ 在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了 <math>\rm tree(4)</math> 的一个下界：<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>		2025 年 5 月 24 日，HypCos 在这篇回答<ref>HypCos (2025). 大数问题：tree(4)有多大？[Googology problem: How big is tree(4)?]. ''(EB/OL), Zhihu''. https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了 <math>\rm tree(4)</math> 的一个下界：<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>

	=== 增长率 ===		=== 增长率 ===

2025年7月29日 (二) 11:34 Tabelog

2025-07-29T11:34:42Z

←上一版本		2025年7月29日 (二) 19:34的版本
第1行：		第1行：
	'''~~TREE函数~~'''~~是由数理逻辑学家Harvey Friedman提出的图论函数。~~		'''TREE 函数'''是由数理逻辑学家 Harvey Friedman 提出的图论函数。

	== 定义 ==		=== 定义 ===

	=== 树的嵌入 ===		==== 树的嵌入 ====
	[[文件:树的嵌入.png\|缩略图]]		[[文件:树的嵌入.png\|缩略图]]
	给定两棵树~~<math>~~A~~</math>~~和~~<math>B</math>，我们称<math>~~A~~</math>~~能嵌入到~~<math>~~B~~</math>~~中，如果~~<math>~~B~~</math>~~能通过有限次以下操作得到~~<math>A</math>：~~		给定两棵树 A 和 B，我们称 A 能嵌入到 B 中，如果 B 能通过有限次以下操作得到 A：

	* 删除一个叶子节点。		* 删除一个叶子节点。
第11行：		第11行：
	例如，图中右边的两棵树均能嵌入到左边的树中，但它们不能互相嵌入。		例如，图中右边的两棵树均能嵌入到左边的树中，但它们不能互相嵌入。

	=== TREE(n) ===		==== TREE(n) ====
	~~TREE函数研究的是一类特殊的树，其每个顶点被赋予一个值，称为该点的“颜色”。~~		TREE 函数研究的是一类特殊的树，其每个顶点被赋予一个值，称为该点的“颜色”。

	~~给定正整数n，~~<math>\rm TREE(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：		给定正整数 n，<math>\rm TREE(n)</math> 被定义为满足以下条件的“树列”<math>\{T_n\}</math> 的最大长度：

	# 所有树的顶点至多有<math>n</math>种不同的颜色；		# 所有树的顶点至多有 <math>n</math> 种不同的颜色；
	# <math>T_k</math>至多有<math>k</math>个顶点；		# <math>T_k</math> 至多有 <math>k</math> 个顶点；
	# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。		# 对于正整数 <math>k<l</math>，<math>T_k</math> 不能嵌入到 <math>T_l</math> 中。

	=== tree(n) ===		==== tree(n) ====
	<math>\rm tree(n)</math>(注意大小写)被称为'''弱tree函数'''，它研究的不是染色树，而是普通树。		<math>\rm tree(n)</math>(注意大小写)被称为'''弱tree函数'''，它研究的不是染色树，而是普通树。

第28行：		第28行：
	# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。		# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

	== 有限性证明 ==		=== 有限性证明 ===
	<math>\rm TREE(n)</math>和<math>\rm tree(n)</math>~~的序列总是有限的，这可由Kruskal树定理保证。~~		<math>\rm TREE(n)</math> 和 <math>\rm tree(n)</math> 的序列总是有限的，这可由 Kruskal 树定理保证。

	我们首先要引入'''~~良拟序(Well~~-quasi-~~ordering)~~'''的概念，它可以看成[[良序]]在一般[[良序#偏序集\|偏序集]]上的推广。		我们首先要引入'''良拟序（Well-quasi-ordering）'''的概念，它可以看成[[良序]]在一般[[良序#偏序集\|偏序集]]上的推广。

	设<math>(X,\le)</math>为一偏序集，若对于<math>X</math>中任意无穷序列<math>x_0,x_1,x_2,\cdots</math>，总存在<math>i<j</math>使得<math>x_i\le x_j</math>，则称<math>\le</math>为集合<math>X</math>上的一个良拟序。		设 <math>(X,\le)</math> 为一偏序集，若对于 <math>X</math> 中任意无穷序列 <math>x_0,x_1,x_2,\cdots</math>，总存在 <math>i<j</math> 使得 <math>x_i\le x_j</math>，则称 <math>\le</math> 为集合 <math>X</math> 上的一个良拟序。

	换句话说，若偏序集中不存在“无穷降链”，也不存在“无穷不可比较链”，则称该偏序为一个良拟序。		换句话说，若偏序集中不存在“无穷降链”，也不存在“无穷不可比较链”，则称该偏序为一个良拟序。

	~~Kruskal树定理说明，树的嵌入关系是一个良拟序。~~		Kruskal 树定理说明，树的嵌入关系是一个良拟序。

	~~也就是说，任意无限棵树构成的序列中，必存在两棵树，前面的树能嵌入到后面的树中。这就证明了<math>\rm tree(n)</math>的有限性。~~

	~~== 取值 ==~~		也就是说，任意无限棵树构成的序列中，必存在两棵树，前面的树能嵌入到后面的树中。这就证明了 <math>\rm tree(n)</math> 的有限性。

	=== ~~n较小时~~ ===		=== 取值 ===
	~~对于<math>\rm TREE(n)</math>，有：~~

	<math>\rm TREE(1)=1</math>		==== n 较小时 ====
			对于 <math>\rm TREE(n)</math>，有：

	<math>\rm TREE(2)=3</math>		* <math>\rm TREE(1)=1</math>
			* <math>\rm TREE(2)=3</math>

	对于<math>\rm tree(n)</math>，有：		对于<math>\rm tree(n)</math>，有：

	<math>\rm tree(1)=2</math>		# <math>\rm tree(1)=2</math>
			# <math>\rm tree(2)=5</math>
	<math>\rm tree(2)=5</math>		# <math>{\rm tree(3)\geq844,424,930,131,960}</math>

	<math>{\rm tree(3)\geq844,424,930,131,960}</math>

	=== TREE(3) ===		==== TREE(3) ====
	[[文件:TREE(3).jpg\|缩略图]]		[[文件:TREE(3).jpg\|缩略图]]
	和<math>\rm TREE(1)</math>、<math>\rm TREE(2)</math>仅有一位数的取值相比，<math>\rm TREE(3)</math>的值出现了“暴涨”，其远远超过了[[葛立恒数]]和[[Kirby-Paris Hydra\|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。		和 <math>\rm TREE(1)</math>、<math>\rm TREE(2)</math> 仅有一位数的取值相比，<math>\rm TREE(3)</math> 的值出现了“暴涨”，其远远超过了[[葛立恒数]]和 [[Kirby-Paris Hydra\|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。

	右图是<math>\rm TREE(3)</math>序列可能的前几项。		右图是 <math>\rm TREE(3)</math> 序列可能的前几项。

	~~HypCos在这篇回答~~<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>的一个下界：		HypCos 在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了 <math>\rm TREE(3)</math> 的一个下界：

	${\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})$~~(其中H为~~[[增长层级#哈代层级\|哈代层级]]~~，下同)~~		${\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})$（其中 H 为[[增长层级#哈代层级\|哈代层级]]，下同）

	=== tree(4) ===		==== tree(4) ====
	~~2025年5月24日，HypCos在这篇回答~~<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>		2025年5月24日，HypCos 在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了 <math>\rm tree(4)</math> 的一个下界：<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>

	== 增长率 ==		=== 增长率 ===
	通过对树的嵌入关系进行编序(此处等待进一步说明)，我们可以得到<math>\rm TREE(n)</math>和<math>\rm tree(n)</math>的增长率分别为		通过对树的嵌入关系进行编序(此处等待进一步说明)，我们可以得到 <math>\rm TREE(n)</math> 和 <math>\rm tree(n)</math> 的增长率分别为

	${\rm TREE(n)}\sim\varphi(\omega@\omega)$		${\rm TREE(n)}\sim\varphi(\omega@\omega)$

2025年7月17日 (四) 20:02 Apocalypse

2025-07-17T20:02:49Z

←上一版本		2025年7月18日 (五) 04:02的版本
第56行：		第56行：
	<math>\rm tree(2)=5</math>		<math>\rm tree(2)=5</math>

	<math>{\rm tree(3)~~>844~~,424,930,131,960}</math>		<math>{\rm tree(3)\geq844,424,930,131,960}</math>

	=== TREE(3) ===		=== TREE(3) ===
第71行：		第71行：
	2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>		2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>

			== 增长率 ==
			通过对树的嵌入关系进行编序(此处等待进一步说明)，我们可以得到<math>\rm TREE(n)</math>和<math>\rm tree(n)</math>的增长率分别为

			${\rm TREE(n)}\sim\varphi(\omega@\omega)$

			${\rm tree(n)}\sim\varphi(1@\omega)$
	== 参考资料 ==		== 参考资料 ==
	<references />		<references />
	[[分类:记号]]		[[分类:记号]]

2025年7月17日 (四) 09:41 GaoKao

2025-07-17T09:41:00Z

←上一版本		2025年7月17日 (四) 17:41的版本
第4行：		第4行：

	=== 树的嵌入 ===		=== 树的嵌入 ===
			[[文件:树的嵌入.png\|缩略图]]
	给定两棵树<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>：		给定两棵树<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>：

	* 删除一个叶子节点。		* 删除一个叶子节点。
	* 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成一条)。		* 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成一条)。
			例如，图中右边的两棵树均能嵌入到左边的树中，但它们不能互相嵌入。

	=== TREE(n) ===		=== TREE(n) ===
			TREE函数研究的是一类特殊的树，其每个顶点被赋予一个值，称为该点的“颜色”。

	给定正整数n，<math>\rm TREE(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：		给定正整数n，<math>\rm TREE(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

第23行：		第27行：
	# <math>T_k</math>至多有<math>n+k</math>个顶点；		# <math>T_k</math>至多有<math>n+k</math>个顶点；
	# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。		# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

			== 有限性证明 ==
			<math>\rm TREE(n)</math>和<math>\rm tree(n)</math>的序列总是有限的，这可由Kruskal树定理保证。

			我们首先要引入'''良拟序(Well-quasi-ordering)'''的概念，它可以看成[[良序]]在一般[[良序#偏序集\|偏序集]]上的推广。

			设<math>(X,\le)</math>为一偏序集，若对于<math>X</math>中任意无穷序列<math>x_0,x_1,x_2,\cdots</math>，总存在<math>i<j</math>使得<math>x_i\le x_j</math>，则称<math>\le</math>为集合<math>X</math>上的一个良拟序。

			换句话说，若偏序集中不存在“无穷降链”，也不存在“无穷不可比较链”，则称该偏序为一个良拟序。

			Kruskal树定理说明，树的嵌入关系是一个良拟序。

			也就是说，任意无限棵树构成的序列中，必存在两棵树，前面的树能嵌入到后面的树中。这就证明了<math>\rm tree(n)</math>的有限性。

	== 取值 ==		== 取值 ==
第42行：		第59行：

	=== TREE(3) ===		=== TREE(3) ===
			[[文件:TREE(3).jpg\|缩略图]]
	和<math>\rm TREE(1)</math>、<math>\rm TREE(2)</math>仅有一位数的取值相比，<math>\rm TREE(3)</math>的值出现了“暴涨”，其远远超过了[[葛立恒数]]和[[Kirby-Paris Hydra\|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。		和<math>\rm TREE(1)</math>、<math>\rm TREE(2)</math>仅有一位数的取值相比，<math>\rm TREE(3)</math>的值出现了“暴涨”，其远远超过了[[葛立恒数]]和[[Kirby-Paris Hydra\|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。

	HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>~~、的一个下界：~~		右图是<math>\rm TREE(3)</math>序列可能的前几项。

			HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>的一个下界：

	${\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})$(其中H为[[增长层级#哈代层级\|哈代层级]]，下同)		${\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})$(其中H为[[增长层级#哈代层级\|哈代层级]]，下同)

	=== tree(4) ===		=== tree(4) ===
	2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：		2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>

	~~<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>~~		== 参考资料 ==
	<references />		<references />
	[[分类:记号]]		[[分类:记号]]

2025年7月17日 (四) 03:52 Z

2025-07-17T03:52:46Z

←上一版本		2025年7月17日 (四) 11:52的版本
第52行：		第52行：

	<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>		<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>
			<references />
			[[分类:记号]]

GaoKao：/* TREE(3) */

2025-07-15T15:20:48Z

TREE(3)

←上一版本		2025年7月15日 (二) 23:20的版本
第46行：		第46行：
	HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>、的一个下界：		HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>、的一个下界：

	${\rm TREE(3)}>H_{\varphi(1\omega,3)\cdot\varphi(1\omega)}({\rm tree(tree(3)+1)})$(其中H为[[增长层级#哈代层级\|哈代层级]]，下同)		${\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})$(其中H为[[增长层级#哈代层级\|哈代层级]]，下同)

	=== tree(4) ===		=== tree(4) ===

GaoKao：创建页面，内容为“'''TREE函数'''是由数理逻辑学家Harvey Friedman提出的图论函数。 == 定义 == === 树的嵌入 === 给定两棵树 $A$ 和 $B$ ，我们称 $A$ 能嵌入到 $B$ 中，如果 $B$ 能通过有限次以下操作得到 $A$ ： * 删除一个叶子节点。 * 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成…”

2025-07-15T15:20:11Z

创建页面，内容为“'''TREE函数'''是由数理逻辑学家Harvey Friedman提出的图论函数。 == 定义 == === 树的嵌入 === 给定两棵树<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>： * 删除一个叶子节点。 * 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成…”

新页面

'''TREE函数'''是由数理逻辑学家Harvey Friedman提出的图论函数。

== 定义 ==

=== 树的嵌入 ===
给定两棵树<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>：

* 删除一个叶子节点。
* 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成一条)。

=== TREE(n) ===
给定正整数n，<math>\rm TREE(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

# 所有树的顶点至多有<math>n</math>种不同的颜色；
# <math>T_k</math>至多有<math>k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

=== tree(n) ===
<math>\rm tree(n)</math>(注意大小写)被称为'''弱tree函数'''，它研究的不是染色树，而是普通树。

给定正整数n，<math>\rm tree(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

# <math>T_k</math>至多有<math>n+k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

== 取值 ==

=== n较小时 ===
对于<math>\rm TREE(n)</math>，有：

<math>\rm TREE(1)=1</math>

<math>\rm TREE(2)=3</math>

对于<math>\rm tree(n)</math>，有：

<math>\rm tree(1)=2</math>

<math>\rm tree(2)=5</math>

<math>{\rm tree(3)>844,424,930,131,960}</math>

=== TREE(3) ===
和<math>\rm TREE(1)</math>、<math>\rm TREE(2)</math>仅有一位数的取值相比，<math>\rm TREE(3)</math>的值出现了“暴涨”，其远远超过了[[葛立恒数]]和[[Kirby-Paris Hydra|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。

HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>、的一个下界：

${\rm TREE(3)}>H_{\varphi(1\omega,3)\cdot\varphi(1\omega)}({\rm tree(tree(3)+1)})$(其中H为[[增长层级#哈代层级|哈代层级]]，下同)

=== tree(4) ===
2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：

<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>