We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Reverse mathematics and marriage problems with finitely many solutions.
- Authors
Hirst, Jeffry; Hughes, Noah
- Abstract
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.
- Subjects
REVERSE mathematics; MATHEMATICS theorems; MODULES (Algebra); SECRETARY problem (Probability theory); MATHEMATICAL functions; NUMERICAL analysis
- Publication
Archive for Mathematical Logic, 2016, Vol 55, Issue 7/8, p1015
- ISSN
0933-5846
- Publication type
Article
- DOI
10.1007/s00153-016-0509-4