Abstract | Keywords | Export | Availability | Bookmark

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

In an effort to make abstraction of different algebraic objects, mathematicians have developed so-called model theory to describe how certain sets (translated into ‘structures’) behave if we attach different operators, an order relation, etc. In model theory, a formula always defines sets of ‘solutions’ – called definable sets – not unlike the solutions of a quadratic equation. This thesis now discusses how complex these definable sets get for a particular type of structure. The complexity is measured in terms of the VC density, which roughly speaking indicates how much information can be distilled from a given ambient space using the sets. More specifically, if we are given some infinitely large set X, it can be very difficult to fully describe X. But we can use the aforementioned definable sets to see how much information can be drawn from finite subsets of X (of course in terms of the size of these finite subsets). Similarly to how quadratic equations have coefficients that determine their solutions, formulas always have some parameters where the number of parameters in a formula governs the complexity of its definable sets. The central result of this text shows that in the specific setting of o-minimal structures, the VC density of classes of definable sets is exactly equal to the number of parameters, meaning that definable sets in o-minimal structures are not at all complex when compared to other structures. We approach the proof of this result in four steps. The first two chapters of this dissertation describe the fundamental concepts from model theory and VC theory (i.e. the theory dealing with VC density) and also show that they interact well. Then o-minimal structures are properly defined and studied and finally we prove the central result. We conclude by also stating two similar results for different settings, without going into the proof.