Proof-theoretic strength of the stable marriage theorem and other problems
Douglas Cenzer, Jeffrey B. Remmel · Cambridge University Press eBooks · 2017
We study the proof theoretic strength of several infinite versions of finite combinatorial theorem with respect to the standard Reverse Mathematics hierarchy of systems of second order arithmetic. In particular, we study three infinite extensions of the stable marriage theorem of Gale and Shapley. Other theorems studied include some results on partially ordered sets due to Dilworth and to Dushnik and Miller.