Pseudo-Finiteness of Combinatorial Theories

组合理论的伪有限性

• 批准号: 1800506
• 负责人: Cameron Hill
• 金额: $ 15万
• 依托单位: Wesleyan University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1800506&HistoricalAwards=false
• 关键词: Pseudo; Finiteness; Combinatorial; Theories

Model theory is a branch of mathematical logic in which one can exploit the linguistic/formal description of a mathematical object to study the object itself. This object might be a single algebraic structure or a class of structures that share a common description (theory). In this project, the PI will study the phenomenon of pseudo-finiteness, in which every (finite) fragment of the description of an infinite object also describes a finite object -- even while the full description captures only infinite structures. In recent years, pseudo-finiteness has been exploited to prove theorems in finitary discrete mathematics and additive combinatorics. On the other hand, pseudo-finiteness has only been completely characterized in a small number of settings. Ax's characterization of pseudo-finite fields is probably the best known. Here, the PI intends to give such a characterization of pseudo-finiteness for theories that are "purely non-algebraic" -- theories that arise from classes of structures that are specifically of interest in discrete mathematics, such as classes of graphs and regular hypergraphs. In the very long term, one might expect to see applications of this research in network analysis, treating very large networks (i.e. graphs) like the internet and the human brain.Here are some more technical details. The project provides a detailed study of the phenomenon of pseudo-finiteness in what is called "combinatorial theories" -- countably-categorical theories with quantifier elimination and trivial algebraic closure operation. Such theories correspond immediately to commonly studied classes of finite structures from discrete mathematics, such as graphs (directed and undirected) and regular hypergraphs. In practice, it is quite difficult, if not impossible, to construct pseudo-finite combinatorial theories without appealing to probability theory in apparently essential ways: either the constructed theory is itself obtained from a 0,1-law or it is some sort of limit of such theories. Upon determining exactly what the appropriate limit processes are, the PI plans to show that this is, in fact, the only way to construct pseudo-finite combinatorial theories. A proof of this sort of claim will require a more or less complete understanding of 0,1-laws in this setting -- especially, connections and equivalences between conditional independence and higher amalgamation properties in classes of finite structures. In turn, this analysis seems to require deep exploration of connections between model theory, on one hand, and (for example) functional analysis and measure-theoretic probability on the other. Capturing pseudo-finite theories as limits of almost-sure theories will require development of an extensive technology for selecting/extracting well-behaved sub-classes inside of a given class of finite structures.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

模型论是数理逻辑的一个分支，它可以利用数学对象的语言/形式描述来研究对象本身。这个对象可以是一个单一的代数结构，也可以是一类共享一个公共描述（理论）的结构。在这个项目中，PI将研究伪有限性现象，其中描述无限对象的每个（有限）片段也描述了有限对象-即使完整的描述只捕获无限结构。近年来，伪有限性被用来证明有限离散数学和加法组合数学中的定理。另一方面，伪有限性只在少数情况下得到了完全的刻画。AX对伪有限域的刻画可能是最著名的。在这里，PI打算给出这样一个伪有限性的表征理论是“纯粹的非代数”-理论产生的结构类，特别是在离散数学的兴趣，如类的图形和正则超图。从长远来看，人们可能会期望看到这项研究在网络分析中的应用，处理像互联网和人脑这样的大型网络（即图形）。该项目提供了一个所谓的“组合理论”-具有量词消除和平凡代数闭包运算的可数范畴理论-中伪有限性现象的详细研究。这些理论直接对应于离散数学中常见的有限结构类，如图（有向和无向）和正则超图。在实践中，如果不是不可能的话，在不诉诸于概率论的情况下构造伪有限组合理论是相当困难的：所构造的理论本身要么是从0，1-定律得到的，要么是这类理论的某种极限。在确定了什么是适当的极限过程后，PI计划表明这实际上是构造伪有限组合理论的唯一方法。这种说法的证明将需要或多或少地完全理解在这种情况下的0，1-定律-特别是，有限结构类中条件独立性和更高合并性质之间的联系和等价性。反过来，这种分析似乎需要深入探索模型理论与（例如）泛函分析和测度论概率之间的联系。捕获伪有限理论作为几乎确定的理论的限制将需要开发一种广泛的技术，用于选择/提取有限结构的给定类内的行为良好的子类。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。