论文标题
可数图中匹配的计算强度
The computational strength of matchings in countable graphs
论文作者
论文摘要
在1977年的一篇论文中，Steffens确定了一个优雅的标准，用于确定何时可数图具有完美的匹配。在本文中，我们将研究该结果和相关定理的证明理论强度。我们表明，这些定理的许多自然变体与“反向数学的``五巨头''子系统）相等或密切相关。 本文的结果通过展示对单个图理论原理的特定变化影响相应的证明理论强度的特定变化的方式来探讨图理论与逻辑之间的关系。综上所述，本文的结果和问题表明，可数图中的匹配存在为更广泛地理解反向数学提供了丰富的背景。
In a 1977 paper, Steffens identified an elegant criterion for determining when a countable graph has a perfect matching. In this paper, we will investigate the proof-theoretic strength of this result and related theorems. We show that a number of natural variants of these theorems are equivalent, or closely related, to the ``big five'' subsystems of reverse mathematics. The results of this paper explore the relationship between graph theory and logic by showing the way in which specific changes to a single graph-theoretic principle impact the corresponding proof-theoretical strength. Taken together, the results and questions of this paper suggest that the existence of matchings in countable graphs provides a rich context for understanding reverse mathematics more broadly.
