Disguising induction : Proofs of the pigeonhole principle for trees
Disguising induction : Proofs of the pigeonhole principle for trees
复制标题
伪装归纳法：树的鸽巢原理的证明
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Hirst
中科院分区：
文献类型：
--
作者：
J. Hirst
我们研究了树的鸽子洞原理和归纳法之间的关系。这种分析是在逆向数学的框架内进行的，利用哈维·弗里德曼制定的公理系统的层次结构。设2<N表示所有0和1的有限序列的集合。我们经常用σ来表示有限序列和相关的有限函数，所以σ（0）是序列的第一个元素，σ（lh（σ）− 1）是最后一个元素。如果τ由σ和附加元素组成，我们记为σ <$τ，当τ是σ的真扩张时记为σ <$τ。把2<N看作是一个由n关系排序的偏序，我们可以把2<N的任何子集看作是一个子树。一个子集S 2<N和2<N之间保持扩张的双射是一个序同构。使用这个术语，我们可以在二叉树上制定以下鸽子洞原则。TT（1）：设f：2<N → n，其中n ∈ N.则存在一个子树S <$2 <N阶同构于2<N且a c < n使得对每个σ ∈ S，f（σ）= c.这个鸽子洞原理直接从Hindman定理的一个版本得出。如果我们让FIN表示N的所有非空有限子集的集合，那么Hindman定理[9]的熟悉的有限和形式等价于下面的陈述。(See[1]）HT：设f：FIN→ n，其中n ∈ N.然后有一个FIN元素的序列<$Xi <$i∈N，并且c < n使得·如果i < j，则max（Xi）< min（Xj），并且1这篇文章的发表部分是通过约翰·邓普顿基金会的资助（ID# 20800）而成为可能的。本出版物中表达的观点是作者的观点，不一定反映约翰邓普顿基金会的观点。
We examine the relationship between a pigeonhole principle for trees and induction on Σ2 formulas. This analysis is carried out in the framework of reverse mathematics utilizing a hierarchy of axiom systems formulated by Harvey Friedman. Let 2<N denote the set of all finite sequences of zeros and ones. We often use σ to denote both a finite sequence and the associated finite function, so σ(0) is the first element of the sequence, and σ(lh(σ)− 1) is the last. If τ consists of σ with appended elements we write σ ⊆ τ , and write σ ⊂ τ when τ is a proper extension of σ. Viewing 2<N as a partial order ordered by the ⊆ relation, we can think of any subset of 2<N as a subtree. A bijection between a subset S ⊆ 2<N and 2<N that preserves extension is an order isomorphism. Using this terminology, we can formulate the following pigeonhole principle on binary trees. TT(1): Suppose f : 2<N → n for some n ∈ N. Then there is a subtree S ⊆ 2<N order isomorphic to 2<N and a c < n such that f(σ) = c for every σ ∈ S. This pigeonhole principle follows immediately from a version of Hindman’s theorem. If we let FIN denote the collection of all nonempty finite subsets of N, then the familiar finite sum form of Hindman’s theorem [9] is equivalent to the following statement. (See [1].) HT: Suppose f : FIN→ n for some n ∈ N. Then there is a sequence 〈Xi〉i∈N of elements of FIN and a c < n such that • if i < j then max(Xi) < min(Xj), and 1This publication was made possible in part through the support of a grant (ID# 20800) from the John Templeton Foundation. The opinions expressed in this publication are those of the author and do not necessarily reflect the views of the John Templeton Foundation.