ON WELL-QUASI-ORDERINGS

Date Issued:: 2013
Abstract/Description:: 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.

Title:	ON WELL-QUASI-ORDERINGS.	33 views 18 downloads
Name(s):	Thurman, Forrest, Author Brennan, Joseph, Committee Chair University of Central Florida, Degree Grantor
Type of Resource:	text
Date Issued:	2013
Publisher:	University of Central Florida
Language(s):	English
Abstract/Description:	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.
Identifier:	CFH0004455 (IID), ucf:45082 (fedora)
Note(s):	2013-05-01 B.S. Sciences, Dept. of Mathematics Bachelors This record was generated from author submitted information.
Subject(s):	well-quasi-orderings Higman's Lemma buchberger's algorithm
Persistent Link to This Record:	http://purl.flvc.org/ucf/fd/CFH0004455
Restrictions on Access:	public
Host Institution:	UCF

In Collections