RUI: Combinatorial Set Theory

项目负责人：Justin T. moore提出的研究内容是将集合论和无限组合学中的新技术应用于拓扑、图论和序理论中的基问题。在每种情况下，目标都是证明不可数对象在特定类别中的分类定理。这三个范畴是拓扑空间、二部图和线性顺序。目标是使用强制公理来证明范畴具有经典例子的有限基础。在分析这类问题时所采用的技术通常是拉姆齐理论，并经常借鉴在分析康托的连续统问题和苏斯林的实线分类问题时所产生的结果和动机。提出的研究旨在扩大我们对强迫公理及其对基问题和连续问题的影响的理解。PI已经证明了适当强迫公理意味着不可数线性阶有一个五元基，回答了该提议的一个中心问题。证明涉及到无限组合的新技术，这些技术可能与完成提案的其余部分有关。关键是PI的集合映射反射的概念，这个概念是根据他关于适当强迫公理的结果和连续体的大小来表述的。在解中明显的是需要一个强无穷公理来获得五元基的一致性。这是相当出乎意料的，可能有助于解释过去的困难，并推动未来对与最小不可数基数相关的非常大集合和组合之间关系的研究。提出的研究代表了对基本数学对象的分析-图，顺序和拓扑-使用概率方法的广义版本，保罗·埃尔多斯皮在他的网络，包装，素数和电路复杂性的研究中首创。概率方法的格言是：“如果一个物体以正概率出现，它就存在。”对于有限概率空间，这是一个事实。对于无限空间和它们的概括——被称为强迫概念——它需要额外的公理假设——被称为强迫公理。例如，PI最近表明，在这样的假设下，任何不能表示为有理数集合的线性顺序必须包含五个临界顺序中的一个。虽然目前看来，这似乎是一项没有什么实际意义的理论成就，但这种论证方式可能会在未来启发现实世界的应用。最近在集合理论中取得成功的一个例子是Laver的比较辫子的算法。从粒子物理学到遗传学，在数学和科学的许多领域都出现了一个重要的问题，即在不剪断或折断两根辫子的情况下，怎样才能使两根辫子看起来一样。Laver利用大无穷集理论的思想设计了一种快速的辫子比较算法。之前的算法是指数级的慢。目前基于Laver思想的算法在二次时间内运行（快）。因此，无限集的研究可以为更多的地面物体提供实际应用。这一研究也许有一天会在传统的有限概率方法中得到应用，或者像Laver的工作那样产生不可预见的影响。

AbstractAward: DMS-0401893Principal Investigator: Justin T. MooreThe proposed research concerns applying new techniques in settheory and infinite combinatorics to basis problems in topology,graph theory, and order theory. In each case, the goal is toprove a classification theorem for the uncountable objects in acertain category. Three such categories are topological spaces,bipartite graphs, and linear orders. The goal is to use forcingaxioms to prove that the category has a finite basis of classicalexamples. The techniques employed in analyzing such problems areoften Ramsey theoretic and frequently draw upon results andmotivation which arise in analyzing Cantor's continuum problemand Suslin's classification problem for the real line. Theproposed research seeks to expand our understanding of forcingaxioms and their impact upon basis problems and the continuumproblem. The PI has already proved that the Proper Forcing Axiomimplies that the uncountable linear orders have a five elementbasis, answering one of the central problems of the proposal.The proof involved new techniques in infinite combinatorics whichare likely relevant to completing the rest of the proposal. Atthe crux is the PI's notion of set mapping reflection which wasformulated in relation to his results on the Proper Forcing Axiomand the size of the continuum. Conspicuous in the solution isthe need for a strong axiom of infinity to obtain the consistencyof a five element basis. This was quite unexpected and may serveboth to explain past difficulties and fuel future research on therelationship between very large sets and combinatorics associatedwith the smallest uncountable cardinal.The proposed research represents an analysis of fundamentalmathematical objects - graphs, orders, and topologies - using ageneralized version of the probabilistic method which Paul Erdospioneered in his study of networks, packings, prime numbers, andcircuit complexity. The apothegm of the probabilistic method is:"If an object occurs with positive probability, it exists." Forfinite probability spaces, this is a fact. For infinite spacesand their generalizations - known as forcing notions - itrequires additional axiomatic assumptions - known as forcingaxioms. The PI has recently shown, for instance, under suchassumptions that any linear order which cannot be represented asa collection of rational numbers must contain one of fivecritical orders. While at the present this would seem torepresent a theoretical accomplishment with little practicalsignificance, the style of argument may inspire real worldapplications in the future. A recent example of such a successin set theory is Laver's algorithm for comparing braids. Animportant question which arises in a number of areas ofmathematics and science - from particle physics to genetics - iswhen two braids can be made to look the same without cutting orbreaking the strands. Laver used ideas from the theory of largeinfinite sets to devise a fast algorithm for comparing braids.The previous algorithm was exponentially slow. Currentalgorithms based on Laver's idea run in quadratic time (fast).Hence the study of infinite sets can provide practicalapplications to much more down to earth objects. The proposedresearch may some day have applications in the traditionalfinitary probabilistic method or less foreseeable impact as withwith Laver's work.