论文标题
从积极信息中枚举的关系
Relations enumerable from positive information
论文作者
论文摘要
我们从列举可降低的角度研究了可数的结构。由于枚举可降低性仅基于正面信息，因此在这种情况下，考虑其正原子图给出的结构是自然的 - 结构所有关系的可计算连接。修复结构$ \ MATHCAL {a} $，在这种情况下，自然的关系是$ r $，以至于$ r^{\ hat {\ mathcal {a}}} $可在$ \ hatcal {a}} $ for $ \ hat {a} a} $ { \ Mathcal {a} $ - 相对本质上枚举（R.I.P.E.）关系。我们证明了R.I.P.E.关系正是$σ^p_1 $公式可以定义的关系，这是无限$σ^0_1 $公式的子类。然后，我们引入了一个新的自然概念，即结构的跳跃，并研究其与其他跳跃概念的相互作用。最后，我们证明了据枚举的函子，这是Csima，Rossegger和Yu研究的概念，相当于使用$σ^p_1 $公式的解释性概念。
We study countable structures from the viewpoint of enumeration reducibility. Since enumeration reducibility is based on only positive information, in this setting it is natural to consider structures given by their positive atomic diagram -- the computable join of all relations of the structure. Fixing a structure $\mathcal{A}$, a natural class of relations in this setting are the relations $R$ such that $R^{\hat{\mathcal{A}}}$ is enumeration reducible to the positive atomic diagram of $\hat{\mathcal{A}}$ for every $\hat{ \mathcal{A}}\cong \mathcal{A}$ -- the relatively intrinsically positively enumerable (r.i.p.e.) relations. We show that the r.i.p.e. relations are exactly the relations that are definable by $Σ^p_1$ formulas, a subclass of the infinitary $Σ^0_1$ formulas. We then introduce a new natural notion of the jump of a structure and study its interaction with other notions of jumps. At last we show that positively enumerable functors, a notion studied by Csima, Rossegger, and Yu, are equivalent to a notion of interpretability using $Σ^p_1$ formulas.
