Topics in the Foundations of Mathematics

这个项目将继续弗里德曼的工作，建立一些简单和基本的组合陈述的独立于通常的数学公理(即，具有选择公理的Zermelo-Frankel集合论)。这些断言涉及有限图和树的顺序构造，在每个阶段，构造的一个特征被最小化。这与计算机科学中所谓的“贪婪”结构有某种相似之处。这些断言告诉我们，这样的构造可以以这样的方式执行，即所得到的对象具有与Ramsey理论(组合学的一个分支)相关的强而自然的组合性质。这些组合陈述可以从某些重大的基本假设中得到证明，但不能从通常的数学公理中得到证明。在这方面，以前NSF支持的结果被用作加州大学圣迭戈分校计算机系本科课程的组成部分。此外，在以前的NSF支持下，Friedman发现了一种新的关于有限字母表序列的初等约束。对于每个有限字母表，满足这一约束的任何序列的长度都有很多。在一个字母中，最长的长度是3。在两个字母中，这个最长的长度是11。在三个或更多的字母中，这个最长的长度明显地巨大得令人无法理解，并且与数理逻辑和组合学中的各种主题密切相关。这些主题包括快速增长函数、可证明递归函数、Peano算法片段和证明论序数。去年夏天，芝加哥大学的天才高中生探索了这个话题，学生们用11个字母写出了两个字母。弗里德曼将继续他对这一问题和其他相关问题的调查，这些问题涉及到这样简单的限制。在这方面，弗里德曼已经开始与兰迪·多尔蒂进行卓有成效的合作，其中包括大量的计算机探索。弗里德曼已经成功地建立了一些非常具体的组合陈述的数学公理的独立性，这些组合陈述涉及到构造受一定约束的有限数学对象。这些断言告诉我们，这样的构造可以被执行，从而得到的对象具有在组合学中通常研究的那种性质。在这方面，以前NSF支持的结果被用作加州大学圣地亚哥分校计算机科学系本科课程的组成部分。此外，在以前的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.***