Premium
On the strength of marriage theorems and uniformity
Author(s) -
Fujiwara Makoto,
Higuchi Kojiro,
Kihara Takayuki
Publication year - 2014
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201300021
Subject(s) - mathematics , reverse mathematics , computable number , matching (statistics) , computable function , context (archaeology) , pure mathematics , discrete mathematics , computable analysis , statistics , geometry , paleontology , biology , axiom
Kierstead showed that every computable marriage problem has a computable matching under the assumption of computable expanding Hall condition and computable local finiteness for boys and girls. The strength of the marriage theorem reaches WKL 0 or ACA 0 if computable expanding Hall condition or computable local finiteness for girls is weakened. In contrast, the provability of the marriage theorem is maintained in RCA even if local finiteness for boys is completely removed. Using these conditions, we classify the strength of variants of marriage theorems in the context of reverse mathematics. Furthermore, we introduce another condition that also makes the marriage theorem provable in RCA 0 , and investigate the sequential and Weihrauch strength of marriage theorems under that condition.