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.
If this is your Honors thesis, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu
Bachelor of Science (B.S.)
College of Sciences
Dissertations, Academic -- Sciences;Sciences -- Dissertations, Academic
Length of Campus-only Access
Honors in the Major Thesis
Thurman, Forrest, "On well-quasi-orderings" (2013). HIM 1990-2015. 1474.