Binary relational structures having only countably many nonisomorphic substructures
Binary relational structures having only countably many nonisomorphic substructures
复制标题
仅具有可数个非同构子结构的二元关系结构
DOI：
10.2307/2275056
复制
发表时间：
1991
影响因子：
0.6
通讯作者：
J. Schmerl
中科院分区：
文献类型：
--
作者：
D. Macpherson;J. Schmerl
对于结构，令 φ() 为 的非同构、可数无限子结构的数量。 M. Pouzet 提出，这里考虑的问题是表征那些 φ() ≤ ℵ0 的可数。在本文中，我们将专门处理有限二元关系语言 L 中的结构。定理 3 中给出了那些 φ() ≤ ℵ0（结果等于 ）的 L 结构的表征。它是三步过程的顶峰。第一步得出定理 1，表明对于可数稳定的 L 结构 ，当且仅当是元胞结构时， φ() ≤ ℵ0 。 （参见定义 0.1。）在第二步中，我们考虑线性有序集 = (A, ≤ ℵ0)，并在定理 2 中描述 φ() ≤ ℵ0 的有序类型。最后，在定理 3 中，我们合并定理 1 和定理 2，得到 φ() ≤ ℵ0 的所有可数 L 结构的分类。我们理解Zs。 Nagy 独立地在可数图 Γ 上获得了结果，其中 .固定有限关系语言 L 并令 为 L 结构。对于 a 0, a 1,…, a n−1 ∈ A，<a 0, a 1,…,a n−1> 的类型用 tp(a 0,a 1,…,a n−1) 表示，是无量词 L-公式 φ(x 0,x 1,…,x n−1) 的集合，其中 ⊨ φ(a 0,a 1,…,a n−1)。更一般地，如果 X ⊆ A，则 X 上的 <a 0,a 1,…, a n−1> 的类型定义为 tp(a 0,a 1,…,a n−1/X) = {φ()： φ() 是一个无量词 (L ∪ X) 公式，使得 ⊨ φ(ā)}。
For a structure let φ() be the number of nonisomorphic, countably infinite substructures of . The problem considered here, suggested by M. Pouzet, is that of characterizing those countable for which φ() ≤ ℵ0. In this paper we will deal exclusively with structures in a finite, binary relational language L. The characterization of those L-structures for which φ() ≤ ℵ0 (which turns out to be equivalent to ) is given in Theorem 3. It is the culmination of a three-step process. The first step, resulting in Theorem 1, shows that for a countable stable L-structure , φ() ≤ ℵ0 iff is cellular. (See Definition 0.1.) In the second step we consider linearly ordered sets = (A, ≤ ℵ0), and characterize in Theorem 2 the order types of those for which φ() ≤ ℵ0. Finally, in Theorem 3, we amalgamate Theorems 1 and 2 to get the classification of all countable L-structures for which φ() ≤ ℵ0. We understand that Zs. Nagy independently has obtained results on countable graphs Γ for which . Fix a finite relational language L and let be an L-structure. For a 0, a 1,…, a n−1 ∈ A, the type of 〈a 0, a 1,…,a n−1〉, denoted by tp(a 0,a 1,…,a n−1), is the set of quantifier-free L-formulas φ(x 0,x 1,…,x n−1) for which ⊨ φ(a 0,a 1,…,a n−1). More generally, if X ⊆ A, then the type of 〈a 0,a 1,…, a n−1〉 over X is defined to be tp(a 0,a 1,…,a n−1/X) = {φ(): φ() is a quantifier-free (L ∪ X)-formula such that ⊨ φ(ā)}.