Topics in the Foundations of Mathematics

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

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.***