Zorn’s Lemma, Reverse Mathematics, and Applications in Combinatorics

Source abstract

We present two hierarchies of versions of Zorn’s lemma that can be used directly in reverse mathematical analyses just as the original is used in standard mathematical arguments. We show that at the first two levels these versions are reverse mathematically equivalent (over RCA0) to Πk1-CA0 for k=1,2 and at higher levels to known choice axioms not provable in Z2. We give several examples of how they could be used in known proofs and a new reverse mathematical analysis of some theorems about injective choice functions (matchings) for countable families (of sets of numbers). These include a couple of unusual situations. One principle (MCSF) can be proven in Π21-CA0 using our version of Zorn’s lemma at Π21. It is a Π41 statement and perhaps might be equivalent to Π21-CA0. Another (MRSF) is just a Π31 statement and so cannot imply even Δ21-CA0 but its known proofs all use even more than Π21-CA0 (Π21-CA0+). Both of these principles are shown to imply Π11-CA0. These results suggest several interesting reverse mathematical questions. We also briefly discuss some connections to similar work of Flood, Jura, Levin, and Markkanen on matchings in general graphs.