Reverse mathematics and marriage problems with finitely many solutions

被引：0
作者：
Jeffry L. Hirst
Noah A. Hughes
机构：
[1] Appalachian State University,Department of Mathematical Sciences
[2] University of Connecticut,Department of Mathematics
来源：
Archive for Mathematical Logic | 2016年 / 55卷
关键词：
Reverse mathematics; WKL; ACA; Marriage; Transversal; Bipartite; Graph; Matching; 03B30; 03F35; 05D15;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We analyze the logical strength of theorems on marriage problems with a fixed finite number of solutions via the techniques of reverse mathematics. We show that if a marriage problem has k solutions, then there is a finite set of boys such that the marriage problem restricted to this set has exactly k solutions, each of which extend uniquely to a solution of the original marriage problem. The strength of this assertion depends on whether or not the marriage problem has a bounding function. We also answer three questions from our previous work on marriage problems with unique solutions.
引用
收藏
页码：1015 / 1024
页数：9
相关论文
共 4 条
[1]  
Friedman Harvey(1976)Abstracts: systems of second order arithmetic with restricted induction, I and II J. Symb. Logic 41 557-559
[2]  
Hirst Jeffry L(2007)Representations of reals in reverse mathematics Bull. Pol. Acad. Sci. Math 55 303-316
[3]  
Hirst Jeffry L(2015)Reverse mathematics and marriage problems with unique solutions Arch. Math. Logic 54 49-57
[4]  
Hughes Noah A(undefined)undefined undefined undefined undefined-undefined
1