Reverse mathematics and marriage problems with unique solutions

详细信息    查看全文

• 作者：Jeffry L. Hirst (1)
  Noah A. Hughes (1)
  
  1. Department of Mathematical Sciences ; Appalachian State University ; Boone ; NC ; 28608 ; USA
  
• 关键词：Reverse mathematics ; Combinatorics ; Marriage theorems ; Transversal ; SDR ; Unique matching ; 3B30 ; 03F35 ; 05D15 ; 05C70
• 刊名：Archive for Mathematical Logic
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：54
• 期：1-2
• 页码：49-57
• 全文大小：180 KB
• 参考文献：1. Chang G.J.: On the number of SDR of a ( / t, / n)-family. Eur. J. Combin. lass="a-plus-plus">10(3), 231鈥?34 (1989). doi:an class="a-plus-plus non-url-ref">10.1016/S0195-6698(89)80056-3 <a class="external" href="http://dx.doi.org/10.1016/S0195-6698(89)80056-3" target="_blank" title="It opens in new window">CrossRefa>
  2. Hall M. Jr.: Distinct representatives of subsets. Bull. Am. Math. Soc. lass="a-plus-plus">54(10), 922鈥?26 (1948). doi:an class="a-plus-plus non-url-ref">10.1090/S0002-9904-1948-09098-X <a class="external" href="http://dx.doi.org/10.1090/S0002-9904-1948-09098-X" target="_blank" title="It opens in new window">CrossRefa>
  3. Hall P.: On representatives of subsets. J. Lond. Math. Soc. lass="a-plus-plus">10, 26鈥?0 (1935). doi:an class="a-plus-plus non-url-ref">10.1112/jlms/s1-10.37.26
  4. Hirst, J.L.: Marriage theorems and reverse mathematics. In: Logic and computation (Pittsburgh, PA, 1987), Contemp. Math., vol. 106, pp. 181鈥?96. Am. Math. Soc., Providence, RI (1990). doi:an class="a-plus-plus non-url-ref">10.1090/conm/106/1057822
  5. Simpson, S.G.: Subsystems of Second Order Arithmetic. Perspectives in Logic, 2nd edn. Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY (2009). doi:an class="a-plus-plus non-url-ref">10.1017/CBO9780511581007
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematical Logic and Foundations
  Mathematics
  Algebra
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1432-0665

文摘

We analyze the logical strength of theorems on marriage problems with unique solutions using the techniques of reverse mathematics, restricting our attention to problems in which each boy knows only finitely many girls. In general, these marriage theorems assert that if a marriage problem has a unique solution then there is a way to enumerate the boys so that for every m, the first m boys know exactly m girls. The strength of each theorem depends on whether the underlying marriage problem is finite, infinite, or bounded.