Definable sets

How do we describe a piece of a mathematical universe? The answer, found in the heart of mathematical logic, is both simple and profound: we write a sentence. The concept of a ​​definable set​​ formalizes the idea that we can carve out subsets of a structure—be it the integers, the real numbers, or more exotic worlds—using the precise language of first-order logic. This fundamental tool allows us to ask deep questions about the nature of mathematical reality itself: What are the possible shapes that can exist in a given universe? What makes some structures geometrically "tame" and predictable, while others are "wild" and chaotic?

This article serves as a guide to the elegant world of definable sets, exploring the deep connections between logic, geometry, and computation. We will journey through two main chapters.

First, in ​​Principles and Mechanisms​​, we will unpack the foundational machinery of definability. We will explore how the choice of logical language and the underlying mathematical structure determines what can be defined. We will then encounter the miraculous simplifying property of quantifier elimination and see how it forces definable sets to take on beautiful geometric forms.

Next, in ​​Applications and Interdisciplinary Connections​​, we will witness the surprising power of this concept outside of pure logic. We will see how definability builds a Rosetta Stone between logic and algebraic geometry, how it tames the infinite complexities of the real numbers to solve problems in number theory, and how it connects to the very nature of computation.

Imagine you have a cosmic box of building blocks—say, all the numbers. Your task is to pick out a very specific collection of these blocks. How do you do it? You write a set of instructions. Perhaps the instruction is simple: "Pick any block labeled with a number greater than zero." Or perhaps it's more complex: "For every block you see, search the entire box to see if there is another block that, when added to the first, equals zero."

In the world of mathematics and logic, this is precisely the idea behind a ​​definable set​​. The "instructions" are a formula written in a precise logical language, and the "box of blocks" is a mathematical universe, called a ​​structure​​. A definable set is simply the collection of all elements in that universe that satisfy the instructions laid out by the formula. This simple idea, it turns out, is one of the most powerful lenses we have for understanding the structure of mathematical reality itself. It allows us to ask: What are the possible shapes that can be built in a given universe? And what makes some universes "tame" and others "wild"?

The first surprise is that the outcome of your instructions depends critically on two things: the language you're allowed to use, and the universe you're working in.

Think of the ​​language​​ as the set of symbols and operations you can write in your blueprint. Suppose you're working with numbers, and your language is the language of rings, $\mathcal{L}_{\text{ring}} = \{+, \cdot, 0, 1\}$. You can talk about addition and multiplication, but you don't have a symbol for "less than" ($$). How, then, could you possibly write the instruction "Pick all numbers greater than 0"? You can't, at least not directly. If you want to talk about order, you need a language that includes a symbol for it, like the language of ordered rings, $\mathcal{L}_{\text{ord-ring}} = \{+, \cdot, 0, 1, \}$. The language you choose determines the very concepts you can express.

Now, let's say you fix the instructions. The set you build still depends entirely on the ​​universe​​, or structure, you're applying them to. Consider the simple instruction given by the formula $\varphi(x) \equiv \exists y \, (x \cdot y = 1)$. This formula defines the set of elements that have a multiplicative inverse—the "units".

• In the universe of ​​integers​​ ($\mathbb{Z}$), where division is a tricky business, the only numbers that satisfy this are $1$ and $-1$. So the definable set is just $\{1, -1\}$.

• In the universe of ​​rational numbers​​ ($\mathbb{Q}$), where every number except zero has an inverse, this very same formula defines the vast set of all non-zero rational numbers, $\mathbb{Q} \setminus \{0\}$.

The blueprint is identical, but the raw materials—the properties of the integers versus the rationals—yield wildly different structures. The same principle applies to order. The instruction $\exists y \, (y x)$ asks for all elements that have something smaller than them. In the universe of natural numbers $\mathbb{N} = \{0, 1, 2, \dots\}$, this defines every number except the smallest one, $0$. But in the universe of all integers $\mathbb{Z}$, where there is no smallest number, this formula defines every single integer. Definability is a dance between the formula and the structure.

The most complex instructions in our logical language involve ​​quantifiers​​: the symbols $\forall$ ("for all") and $\exists$ ("there exists"). These are search commands. A formula like $\exists y \, \varphi(x,y)$ asks, "For a given $x$, does there exist a $y$ somewhere in the universe that makes $\varphi(x,y)$ true?" A formula like $\forall y \, \varphi(x,y)$ asks if $\varphi(x,y)$ is true for every single possible $y$.

In an infinite universe, these searches can be infinitely complex. Verifying a "for all" statement seems to require an impossible, exhaustive check of every element. This is where a miraculous simplifying property comes in, known as ​​quantifier elimination (QE)​​. A theory (a set of axioms governing a universe) has quantifier elimination if every formula, no matter how tangled with nested quantifiers, is equivalent to a simple, quantifier-free formula.

Having QE means that every complex search can be replaced by a local, direct check. It's like replacing the task of searching the entire planet for someone who has the key to a lock with a simple, local check: "Is the serial number on this lock even?" If the answer is yes, a key exists; if no, it doesn't. You never have to leave the lock.

This idea has a beautiful geometric interpretation. An existential quantifier, $\exists y$, corresponds to taking a projection—like casting a shadow. Imagine a set $S$ in 3D space defined by a simple, quantifier-free formula involving $x, y, z$. Its projection onto the $(x,z)$-plane is the set of points $(a,c)$ such that $\exists b$ with $(a,b,c) \in S$. A theory has quantifier elimination if and only if the "shadow" of any simply-defined set is also simply-defined. It ensures that complexity doesn't spontaneously appear when you project a shape.

So, if a theory has quantifier elimination, what do these "simple" definable sets actually look like? The answer is one of the most beautiful instances of unity in mathematics, where logic gives birth to geometry.

Consider the universe of ​​algebraically closed fields​​, of which the complex numbers $\mathbb{C}$ are the most famous example. The theory of these fields (ACF) has quantifier elimination in the language of rings $\mathcal{L}_{\text{ring}}$. A quantifier-free formula here is just a combination of polynomial equations $p(x_1, \dots, x_n) = 0$ and inequations $q(x_1, \dots, x_n) \neq 0$. A fundamental result by Tarski tells us that every definable set in this universe, no matter how complex the defining formula, is a ​​constructible set​​: a finite union and intersection of sets defined by polynomial equations. This is a stunning result. It means that the only shapes that can be "defined" in this universe are the familiar objects of algebraic geometry. You cannot, for instance, define a fractal. The logic of the field axioms constrains its geometry. It is this same algebraic structure that prevents such a field from ever being ordered; the existence of an element $i$ with $i^2 = -1$ is fundamentally incompatible with the axiom that all squares must be non-negative.

Now let's turn to the ​​real numbers​​ $\mathbb{R}$, which form a real closed field (RCF). Here, the story has a twist. In the pure language of rings, the theory of RCF is not blessed with quantifier elimination. For instance, the set of non-negative numbers, $\{x \mid x \ge 0\}$, is definable by the formula $\exists y \, (x = y^2)$, which requires a quantifier. A quantifier-free formula in this language can only define finite or co-finite sets, and the set of non-negative numbers is neither.

But if we add the order symbol $$ to our language, a miracle happens: the theory of RCF does have quantifier elimination in $\mathcal{L}_{\text{ord-ring}}$! Here, the simple, quantifier-free statements are combinations of polynomial equations and inequalities ($p(x) = 0$, $q(x) > 0$). The definable sets are called ​​semialgebraic sets​​. In one dimension, this means every definable set is just a finite union of points and intervals. This property, called ​​o-minimality​​, is a powerful form of "tameness". It guarantees that in the universe of real numbers, you cannot define monstrous, infinitely complex sets. Everything definable has a simple, finite geometric description. This tameness is preserved even when you add new constants to your language, for instance, by giving a name to $\pi$. The new definable sets are still just finite unions of points and intervals. This property has had a revolutionary impact on fields from robotics to economics, as it guarantees that optimization problems over definable functions behave predictably.

The journey doesn't end with quantifier elimination. Logic provides even more subtle tools to probe the texture of reality.

What if your universe isn't tame? Can we still measure the "complexity" of a definable set? The answer is yes, using a tool called ​​Morley Rank​​. It assigns a kind of dimension to a definable set. A set has rank 0 if it's a collection of isolated points. A set has rank $\geq 1$ if it contains an infinite, disjoint collection of rank 0 sets. A set has rank $\geq 2$ if it contains an infinite, disjoint collection of rank 1 sets, and so on, up through the transfinite ordinals. This provides a beautiful, inductive way to classify the complexity of definable shapes. Theories where every definable set has a finite (ordinal) rank are called ​​$\omega$-stable​​, representing a different, but equally important, kind of tameness.

Finally, we come to a truly profound abstraction. We have been using elements from our universe as "parameters" to define sets. Can we flip this on its head? Can a set itself be treated as a single "point" in a new, larger universe? The theory of ​​imaginaries​​ provides a resounding yes. By formally adding "canonical parameters" for every definable set, we can construct an expanded universe, denoted $M^{\text{eq}}$, where sets become citizens. In this world, we can study the geometry of the space of sets itself. This framework allows us to assign a unique code, or name, to each definable set, capturing its essence in a single object. It even allows us to give names to abstract concepts like "definable types," which are like ultimate blueprints for points yet to be realized.

From simple instructions to geometric shapes, from taming infinity with quantifier elimination to assigning dimensions and names to sets themselves, the study of definable sets is a journey into the fundamental relationship between language, logic, and the structure of reality. It reveals a hidden unity, where the rules of logical deduction sculpt the very fabric of the mathematical worlds we can imagine.

We have spent some time exploring the logical machinery of definable sets, but to what end? Is this merely a formal game played by logicians, a peculiar way of classifying subsets of a structure? The answer, you will not be surprised to hear, is a resounding no. The concept of definability is not a sterile abstraction; it is a powerful lens, a pair of spectacles that, once worn, reveals a hidden layer of unity and profound structure running through disparate fields of mathematics. To ask "What can be described simply?" is to pose one of the most fruitful questions in science. The study of definable sets is the mathematical formalization of this question, and the answers it provides are often breathtaking in their scope and elegance.

Let us embark on a journey to see how this one idea—the notion of a set carved out by a finite logical formula—connects to geometry, tames the infinite complexities of the continuum, illuminates the nature of computation, and ultimately addresses the limits of what is knowable.

Perhaps the most stunning and immediate application of definability is the bridge it builds to the world of geometry. Imagine an algebraically closed field, such as the complex numbers $\mathbb{C}$. This is the natural playground for algebraic geometry, a subject concerned with the study of shapes defined by polynomial equations ($p(x_1, \dots, x_n) = 0$). These shapes are called algebraic varieties or, more generally, Zariski closed sets.

Now, let's put on our logician's spectacles. What are the definable sets in such a field, using the basic language of rings $\{+, \cdot, 0, 1\}$? A famous result, the Chevalley-Tarski theorem, gives a beautifully simple answer: the definable subsets of $K^n$ for an algebraically closed field $K$ are precisely the ​​constructible sets​​ of algebraic geometry. A constructible set is just a finite combination of Zariski closed sets using unions, intersections, and complements. This means a statement in the language of first-order logic corresponds directly to a geometric object built from polynomial equations and inequalities. A logical formula is a geometric blueprint.

This correspondence is a kind of Rosetta Stone, allowing us to translate between the languages of logic and geometry. For instance, the logical operation of existential quantification—projecting a set—has a direct geometric meaning. If you take a closed set like the hyperbola defined by $xy=1$ in the plane and project it onto the $x$-axis, you get the set of all $x$ for which there exists a $y$ such that $xy=1$. This is, of course, the punctured line $x \neq 0$, a set that is open, not closed.

The dictionary goes even deeper. Geometers have a notion of dimension for varieties, known as Krull dimension, which captures their intuitive size. Logicians, working in a subfield called stability theory, developed their own notion of dimension called ​​Morley rank​​, which measures the complexity of a definable set. The miracle is that for algebraically closed fields, these two notions of dimension perfectly coincide. For example, the Morley rank of a simple parabola defined by $y=x^2$ is exactly $1$, matching its geometric dimension as a curve. The Morley degree, a measure of how many "irreducible pieces" of maximal dimension a set has, also matches its geometric counterpart.

This is no mere curiosity. This deep connection between logical simplicity (definability) and geometric structure is so strong that it forces the entire theory of algebraically closed fields to be incredibly well-behaved. It leads to the profound result of ​​uncountable categoricity​​: any two uncountable algebraically closed fields of the same characteristic are isomorphic if they have the same size. The simple nature of its definable sets dictates the global structure of the entire mathematical universe it describes.

Let us now turn our attention from the algebraic to the ordered, from fields like $\mathbb{C}$ to the real number line $\mathbb{R}$. What happens if we demand that our definable sets are "simple" in an ordered setting? This leads to the idea of ​​o-minimality​​. A structure expanding the real numbers is o-minimal if every definable subset of the line $\mathbb{R}$ is just a finite collection of points and open intervals. No more, no less [@problem_id:2978142, 3050317].

This simple-sounding axiom has staggering consequences. It acts as a kind of "cosmic speed limit" on complexity. In an o-minimal world, you cannot define "wild" sets. The set of rational numbers $\mathbb{Q}$, with its infinitely many gaps, is not definable. Fractal "dusts" like the Cantor set are not definable. Every definable set, in any dimension, must be decomposable into a finite number of simple, well-behaved pieces called cells. Crucially, every definable set must have a finite number of connected components and a boundary of lower dimension. Definability imposes a beautiful "tameness" on the topology.

For a long time, this was considered a beautiful piece of pure logic. But then came one of the most spectacular applications of model theory to another field: the ​​Pila-Wilkie theorem​​. The theorem addresses a classic problem in number theory: counting rational points on sets. For algebraic curves, we have good tools. But what if a curve is defined by a "transcendental" function, like the graph of $y = \exp(x)$? How many rational points of a given "height" (a measure of the size of the numerators and denominators) can lie on such a curve?

The Pila-Wilkie strategy provides a stunning answer using o-minimality. The graph of the exponential function, while not algebraic, is definable in an o-minimal structure. The "tameness" guaranteed by o-minimality allows geometers to break down any such transcendental set into a finite number of "patches." On each patch, the set is incredibly well-behaved—it's smooth and its curvature is under control. Using an analytic argument, one can show that such a "tame" patch cannot contain too many rational points unless it is secretly part of an algebraic curve. The theorem essentially says that a transcendental set can only contain many rational points if those points are clustered on algebraic curves hiding within the set. O-minimality provides the uniform geometric control needed for the number-theoretic argument to work, a truly remarkable interplay between fields.

So far, we have seen definability connect to the continuous worlds of geometry and topology. But what about the discrete world of natural numbers and computation? Here, in the setting of Peano Arithmetic (PA), the notion of definability reveals its connection to the very foundations of computer science.

A fundamental insight, going back to Kurt Gödel, is that the language of arithmetic is expressive enough to describe computation itself. Any set of numbers that can be recognized by an algorithm—what we call a ​​computable set​​—is also a definable set in the standard model of arithmetic $\mathbb{N}$. The logical operations of the language can mimic the step-by-step process of a Turing machine. This dictionary between computability and definability is the bedrock upon which Gödel built his famous incompleteness theorems. It shows that questions about the limits of algorithms can be translated into questions about truth in arithmetic.

In this context, we also see a crucial feature of definability: the power of having names. In arithmetic, every number $n$ has a unique name in the language, the numeral $\overline{n}$ (the term $S(S(...S(0)...))$). This means that using specific numbers as parameters in a formula doesn't actually increase our descriptive power; we can always just build the numeral for that parameter directly into the formula, resulting in a new, parameter-free formula that defines the same set.

This power of description can be used to achieve one of the great goals of logic: proving the decidability of a theory. A theory is decidable if there exists an algorithm that can determine, for any given sentence, whether it is true or false. While Gödel showed PA is undecidable, other complex theories are not. Consider the theory of ​​algebraically closed valued fields​​ (ACVF), which combines the structures of algebra and a valuation (a way of measuring size, as with the p-adic numbers). By using a sophisticated three-sorted language—one for the field, one for the value group, and one for the residue field—logicians showed that this theory has a property called relative quantifier elimination. This means any statement can be broken down into a combination of statements purely about the value group and purely about the residue field. Since the theories of those component parts are known to be decidable, one can build an algorithm to decide the truth of any statement in the full, complex theory of ACVF. Understanding the structure of definable sets was the key to unlocking this algorithmic understanding.

Our journey has taken us from the varieties of algebraic geometry to the tame landscapes of o-minimal structures, and from the computable sets of arithmetic to the decidable nature of valued fields. The common thread weaving through all these stories is the concept of a definable set.

What, then, is the ultimate nature of definability? Perhaps the most fundamental insight comes from its connection to symmetry. In any mathematical structure, its symmetries (or automorphisms) are transformations that preserve all its essential properties. A beautiful theorem states that the most basic, "atomic" building blocks of definable sets are precisely the ​​automorphism orbits​​—the sets of elements that are indistinguishable from one another under every possible symmetry of the structure. Every parameter-free definable set is just a union of these orbits.

This brings us full circle. To study what can be described with a simple logical formula is to study the intrinsic symmetries and fundamental regularities of the mathematical universe. It is a testament to the profound unity of mathematics that this single, simple idea can reveal so much about the shape of space, the nature of infinity, and the power of computation.