Principal Investigator: Justin T. Moore
The proposed research concerns applying new techniques in set theory and infinite combinatorics to basis problems in topology, graph theory, and order theory. In each case, the goal is to prove a classification theorem for the uncountable objects in a certain category. Three such categories are topological spaces, bipartite graphs, and linear orders. The goal is to use forcing axioms to prove that the category has a finite basis of classical examples. The techniques employed in analyzing such problems are often Ramsey theoretic and frequently draw upon results and motivation which arise in analyzing Cantor's continuum problem and Suslin's classification problem for the real line. The proposed research seeks to expand our understanding of forcing axioms and their impact upon basis problems and the continuum problem. The PI has already proved that the Proper Forcing Axiom implies that the uncountable linear orders have a five element basis, answering one of the central problems of the proposal. The proof involved new techniques in infinite combinatorics which are likely relevant to completing the rest of the proposal. At the crux is the PI's notion of set mapping reflection which was formulated in relation to his results on the Proper Forcing Axiom and the size of the continuum. Conspicuous in the solution is the need for a strong axiom of infinity to obtain the consistency of a five element basis. This was quite unexpected and may serve both to explain past difficulties and fuel future research on the relationship between very large sets and combinatorics associated with the smallest uncountable cardinal.
The proposed research represents an analysis of fundamental mathematical objects - graphs, orders, and topologies - using a generalized version of the probabilistic method which Paul Erdos pioneered in his study of networks, packings, prime numbers, and circuit complexity. The apothegm of the probabilistic method is: "If an object occurs with positive probability, it exists." For finite probability spaces, this is a fact. For infinite spaces and their generalizations - known as forcing notions - it requires additional axiomatic assumptions - known as forcing axioms. The PI has recently shown, for instance, under such assumptions that any linear order which cannot be represented as a collection of rational numbers must contain one of five critical orders. While at the present this would seem to represent a theoretical accomplishment with little practical significance, the style of argument may inspire real world applications in the future. A recent example of such a success in set theory is Laver's algorithm for comparing braids. An important question which arises in a number of areas of mathematics and science - from particle physics to genetics - is when two braids can be made to look the same without cutting or breaking the strands. Laver used ideas from the theory of large infinite sets to devise a fast algorithm for comparing braids. The previous algorithm was exponentially slow. Current algorithms based on Laver's idea run in quadratic time (fast). Hence the study of infinite sets can provide practical applications to much more down to earth objects. The proposed research may some day have applications in the traditional finitary probabilistic method or less foreseeable impact as with with Laver's work.
