RUI: Combinatorial Set Theory

摘要奖：DMS-0401893主要研究者：Justin T. MooreThe拟议的研究涉及应用新技术在集合论和无限组合学的基础问题在拓扑学，图论和秩序理论。 在每一种情况下，目标是证明一个分类定理的不可数对象在某个类别。 三个这样的范畴是拓扑空间，二分图，和线性序。 我们的目标是使用强迫公理来证明范畴具有经典例子的有限基。在分析这些问题所采用的技术往往是拉姆齐理论和经常借鉴的结果和动机，出现在分析康托的连续问题和Suslin的分类问题的真实的线。 拟议的研究旨在扩大我们的理解力公理和它们的影响基础问题和连续性问题。 PI已经证明了适当的强制公理意味着不可数的线性顺序有一个五元素的基础，回答了该提案的中心问题之一。证明涉及无限组合学的新技术，这些技术可能与完成提案的其余部分有关。 在关键是PI的概念集映射反射wasformulated关系到他的结果正确的强迫公理和规模的连续。 在解决方案中显而易见的是，需要一个强无穷公理来获得五元素基的一致性。 这是完全出乎意料的，可能有助于解释过去的困难，并为未来关于非常大的集合和与最小的不可数基数相关的组合学之间的关系的研究提供燃料。拟议的研究代表了对基本数学对象--图、序和拓扑--的分析，使用的是保罗·埃尔多安在他的网络、包装、素数研究中提出的概率方法的广义版本，和电路复杂度。 概率方法的格言是：“如果一个对象以正概率出现，它就存在。“对于有限的概率空间，这是一个事实。 对于无限空间和它们的推广--被称为强迫概念--它需要额外的公理化假设--被称为强迫公理。 例如，PI最近证明，在这样的假设下，任何不能阿萨有理数集合表示的线性序必须包含五个临界序之一。 虽然在目前看来，这似乎代表了一个理论上的成就，没有什么实际意义，但这种论证风格可能会激发未来真实的世界应用。 集合论中这种成功的最近例子是拉弗比较辫子的算法。 从粒子物理学到遗传学，数学和科学领域的一个重要问题是，什么时候可以让两条辫子看起来一样，而不需要切断或折断。 拉弗利用大无限集理论的思想设计了一种比较辫子的快速算法，以前的算法是指数级的慢。 基于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.