Classification-Theoretic Complexity of the Random Partial Order
Rehana Patel, Mathematics and Computer Science, St. John’s College of Liberal Arts and Sciences
Abstract
Saharon Shelah's Classification Theory is a system of categorization of first order mathematical theories. In this system, mathematical structures are said to be either 'simple' or 'non-simple,' according to whether or not their first order theories satisfy certain properties. Simple theories are thought to be better behaved than non-simple ones, and within the class of non-simple theories there is an increasing hierarchy of complexity, culminating in theories that have the so-called 'strict order property'. The paradigmatic theory possessing the strict order theory is that of the countably infinite generic partial order, into which every finite partial order embeds isomorphically. Now, although finite partial orders may in general have arbitrarily long chains, Kevin Compton has shown that under a natural probabilistic interpretation, 'almost every' finite partial order has maximum chain length 3 and can be embedded into a countably infinite partial order called the random partial order. I will show that the theory of the random partial order is simple, making its classification-theoretic complexity dramatically less than that of the generic partial order.