A quasi-order is a relation on a set which is both reflexive and transitive, while a well-quasi-order has the additional property that there exist no infinite strictly descending chains nor infinite antichains. Well-quasi-orderings have many interesting applications to a variety of areas which includes the strength of certain logical systems, the termination of algorithms, and the classification of sets of graphs in terms of excluded minors. My thesis explores how well-quasi-orderings are related to these topics through examples of four known well-quasi-orderings which are given by Dickson's Lemma, Higmans's Lemma, Kruskal's Tree Theorem, and the Robertson-Seymour Theorem. The well-quasi-ordering conjecture for matroids is also discussed, and an original proof of Higman's Lemma is presented.
| Identifer | oai:union.ndltd.org:ucf.edu/oai:stars.library.ucf.edu:honorstheses1990-2015-2473 |
| Date | 01 May 2013 |
| Creators | Thurman, Forrest |
| Publisher | STARS |
| Source Sets | University of Central Florida |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | HIM 1990-2015 |
Page generated in 0.0738 seconds