Axiomatic strengths of certain mathematical statements
Reverse mathematics is primarily interested in what set existence axioms are necessary in a proof of a theorem. Much work has been done in classifying graph colouring theorems, studying k-regular graphs, k-chromatic graphs and forests. This report takes inspiration from an old paper by Bean and stud...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project |
| Language: | English |
| Published: |
Nanyang Technological University
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/144834 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | Reverse mathematics is primarily interested in what set existence axioms are necessary in a proof of a theorem. Much work has been done in classifying graph colouring theorems, studying k-regular graphs, k-chromatic graphs and forests. This report takes inspiration from an old paper by Bean and studies graph colouring theorems restricted to planar graphs. The report shows that for any n, the n-colouring theorem of planar graphs is equivalent to wkl. Further analysis of related principles, obtained by restricting the planar graphs in question to be connected, or with computable planar drawings also yield similar results. However, many of the proofs of equivalence are non-uniform; utilising tools of Weihrauch reducibility, this report also proves that in many instances, such non-uniformity is necessary. |
|---|