Topics in the Foundations of Mathematics

9970459弗里德曼这个项目将继续弗里德曼的工作，建立独立于通常的数学公理（即，Zermelo-Frankel集合论与选择公理）的一些简单和基本的组合语句。这些断言涉及有限图和树的序列构造，其中在每个阶段，构造的特征被最小化。这与计算机科学中所谓的“贪婪”结构有些类似。这些断言告诉我们，这样的构造可以以这样一种方式进行，即所得到的对象具有与拉姆齐理论（组合学的一个分支）相关的强而自然的组合属性。这些组合陈述可以从某些大的基数假设中证明，但不能从通常的数学公理中证明。在这方面的成果，从以前的NSF支持wereused作为一个不可分割的一部分，本科课程在计算机科学系在加州大学圣地亚哥分校。此外，在NSF的支持下，Friedman发现了一种新的有限字母表序列的初等约束。对于每一个有限字母表，满足这个约束的任何序列的长度都是丰富的。在一封信中，最长的长度是3。在两封信中，最长的是11封。在三个或三个以上的字母中，这个最长的长度显然是无法理解的巨大，并且与数学逻辑和组合学中的各种主题密切相关。这些主题包括快速增长函数，可证明递归函数，Peanoarithmetic的片段和证明理论序数。去年夏天，芝加哥大学的天才高中生们探索了这个话题，学生们用11个字母写出了两个字母。弗里德曼将继续他的调查，这和其他相关问题，涉及这样的简单约束。在这方面，弗里德曼已经开始了富有成效的合作与兰迪Doughnut，涉及大量的计算机探索。弗里德曼已经成功地建立了一些非常具体的组合陈述的数学公理的独立性，这些陈述涉及到受某些约束的有限数学对象的构造。这些断言告诉我们，这样的构造可以被执行，使得结果对象具有在组合学中不被正常研究的性质。在这方面的结果从priorNSF的支持被用来作为一个不可分割的一部分，本科课程在计算机科学系在加州大学圣地亚哥分校。此外，在先验NSF的支持下，Friedman从有限字母表中发现了一类新的初等约束序列.受此约束的序列的最长长度（对于三个字母的字母表）显然是不可理解的巨大，并且与数学逻辑和组合学中的各种主题密切相关。1988年夏天，在芝加哥大学，一些有天赋的高中生对这个问题进行了探索，学生们想出了两个字母组成的字母表的正确数字11。弗里德曼将继续他的调查这一点和其他相关的问题，涉及这种简单的约束。在这方面，弗里德曼已经开始了与兰迪·道格拉斯的富有成效的合作，包括大量的计算机探索。

9970459Friedman This project will continue Friedman's work establishing theindependence from the usual axioms of mathematics (i.e.,Zermelo-Frankel set theory with the axiom of choice) of some simpleand basic combinatorial statements. These assertions involvesequential constructions of finite graphs and trees, where at eachstage a feature of the construction is minimized. This is in someanalogy with the so called ``greedy'' constructions in computerscience. The assertions tell us that such constructions can beperformed in such a way that the resulting object has strong andnatural combinatorial properties related to Ramsey theory (a branch ofcombinatorics). These combinatorial statements are provable fromcertain large cardinal assumptions, but not from the usual axioms ofmathematics. Results in this connection from prior NSF support wereused as an integral part of an undergraduate course in the computerscience department at UCSD. In addition, under prior NSF support,Friedman has discovered a new kind of elementary constraint onsequences from a finite alphabet. For each finite alphabet, there is abound on the length of any sequence satisfying this constraint. In oneletter, this longest length is 3. In two letters, this longest lengthis 11. In three or more letters, this longest length is demonstrablyincomprehensibly enormous, and is closely connected to various topicsin mathematical logic and combinatorics. These topics include fastgrowing functions, provably recursive functions, fragments of Peanoarithmetic, and proof theoretic ordinals. This topic was explored bygifted high school students this past summer at the University ofChicago, where students came up with 11 for two letters. Friedman willcontinue his investigation of this and other related problemsinvolving such simple constraints. In this connection, Friedman hasbegun a fruitful collaboration with Randy Dougherty that involvessubstantial computer exploration. Friedman has managed to establish the independence from the usualaxioms of mathematics of some remarkably concrete combinatorial statements.These involve the construction of finite mathematical objects subject tocertain constraints. The assertions tell us that such constructions can beperformed so that the resulting object has properties of a kind that arenormally studied in combinatorics. Results in this connection from priorNSF support were used as an integral part of an undergraduate course inthe computer science department at UCSD. In addition, under prior NSFsupport, Friedman has discovered a new kind of elementary constrainton sequences from a finite alphabet. The longest length of a sequencesubject to this constraint (for a three-letter alphabet) isdemonstrably incomprehensibly enormous, and is closely connected tovarious topics in mathematical logic and combinatorics. This topic wasexplored by gifted high school students during the summer of 1988 at theUniversity of Chicago, where students came up with the correct numberof 11 for an alphabet of two letters. Friedman will continue hisinvestigation of this and other related problems involving such simpleconstraints. In this connection, Friedman has begun a fruitfulcollaboration with Randy Dougherty that involves substantial computerexploration.***