RUI: Combinatorial Set Theory

摘要奖：DMS-0401893首席研究员：贾斯汀·T·摩尔拟议的研究涉及将集合论和无限组合中的新技术应用于拓扑学、图论和序论中的基本问题。在每种情况下，目标都是证明某一范畴中不可数对象的一个分类定理。三个这样的范畴是拓扑空间、二部图和线性序。我们的目的是使用强制公理来证明范畴有一个有限的经典例子的基础。用来分析这类问题的技术通常是拉姆齐理论，并且经常利用在分析康托尔的连续体问题和苏斯林的实线分类问题时产生的结果和动机。这项拟议的研究旨在扩大我们对强制公理及其对基本问题和连续性问题的影响的理解。PI已经证明了真强迫公理意味着不可数线性级有五个元素的基，回答了建议的核心问题之一。证明涉及无限组合中的新技术，这些技术可能与完成建议的其余部分相关。其核心是圆周率关于集合映射反射的概念，它是根据他关于真强迫公理和连续体大小的结果而形成的。该解的明显之处在于需要一个强大的无穷大公理来获得五元素基的一致性。这是完全出乎意料的，可能有助于解释过去的困难，并推动未来关于超大型集合与与最小不可数基数相关的组合学之间的关系的研究。拟议的研究代表了对基本数学对象--图形、顺序和拓扑--的分析，使用保罗·埃尔多斯在他的网络、包装、素数和电路复杂性研究中开创的概率方法的一般化版本。概率方法的格言是：“如果一个物体以正概率出现，它就存在。”对于有限概率空间，这是一个事实。对于无限空间及其推广--称为强迫概念--它需要额外的公理假设--称为强迫公理。例如，PI最近表明，在这样的假设下，任何不能表示为有理数集合的线性顺序都必须包含五个临界顺序中的一个。虽然目前这似乎代表着一项理论成就，但实践意义不大，但这种论证风格可能会在未来启发现实世界的应用。集合论中最近成功的一个例子是拉弗比较辫子的算法。在许多数学和科学领域--从粒子物理学到遗传学--出现的一个重要问题是，何时可以在不切断或折断辫子的情况下使两条辫子看起来相同。拉弗利用大无限集论的思想设计了一种比较辫子的快速算法，以前的算法是指数级的慢。目前基于Laver思想的算法运行在二次时间内(FAST)，因此对无限集的研究可以为更真实的物体提供实际应用。所提出的研究有朝一日可能会在传统的有限概率方法中得到应用，或者像拉弗的工作那样产生不可预见的影响。

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.