Abstract

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.

Notes

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

Thesis Completion

2013

Semester

Spring

Advisor

Brennan, Joseph

Degree

Bachelor of Science (B.S.)

College

College of Sciences

Degree Program

Mathematics

Subjects

Dissertations, Academic -- Sciences;Sciences -- Dissertations, Academic

Format

PDF

Identifier

CFH0004455

Language

English

Access Status

Open Access

Length of Campus-only Access

None

Document Type

Honors in the Major Thesis

Download

Included in

Mathematics Commons

Share

COinS