Expressivity

In any language, from human speech to the code that runs our world, two questions are paramount: What range of ideas can be expressed? And how clearly can they be conveyed? This fundamental concept of descriptive power is known as ​​expressivity​​. It serves as a unifying thread that connects the seemingly disparate worlds of biology, mathematical logic, and artificial intelligence, offering a yardstick to measure and compare the power of our descriptive systems. The central challenge this article addresses is understanding how this power is defined, what its limits are, and the inherent trade-offs that come with seeking greater expressivity.

This article will guide you through this powerful idea in two parts. First, in "Principles and Mechanisms," we will dissect the core concepts, exploring how expressivity manifests in the variable traits of organisms, the formal hierarchies of mathematical logic, and the explanatory power of statistical models. Next, in "Applications and Interdisciplinary Connections," we will witness these principles in action, seeing how the quest for greater expressivity drives scientific progress in chemistry, evolutionary biology, and the development of cutting-edge AI, ultimately revealing the deep connection between computation, logic, and the very act of scientific explanation.

Imagine you have a language. It could be English, it could be the language of mathematics, or it could be the silent, intricate language of our own DNA. With any language, two fundamental questions always arise: What are all the things you can say? And for the things you can say, how clearly and with what variation can you say them? This, in a nutshell, is the heart of ​​expressivity​​. It's a concept that stretches from the messy, beautiful world of biology to the pristine, abstract realms of logic and computer science. It’s a measure of descriptive power.

Let's begin our journey not with equations, but with a fruit fly. In the world of genetics, the concepts of ​​penetrance​​ and ​​expressivity​​ are old friends. Imagine we are studying a particular genetic mutation in Drosophila. This mutation, a tiny deletion in the fly's DNA, is supposed to cause a change in one of its abdominal segments, making it look like a segment from further down its body—a "homeotic transformation".

We breed thousands of these flies, all carrying the exact same genetic alteration. What do we see? Well, the first surprise is that not every fly with the mutation shows the transformation. Some look perfectly normal! The percentage of flies that do show the trait, any at all, is called the ​​penetrance​​. It’s a binary question: does the gene "speak" or does it stay silent? If 80 out of 100 flies show the trait, we say the penetrance is $0.8$. It's the probability that the genotype manifests as a phenotype at all.

But that’s not the whole story. Among the 80 flies that do show the transformation, the effect is not uniform. Some have a tiny, almost imperceptible change. Others have a moderate transformation. A few have a complete, dramatic change in the segment's identity. This range of variation, the degree of the phenotype among those who show it, is its ​​expressivity​​. Penetrance is a yes/no affair; expressivity is the volume control. It's the difference between a whisper and a shout.

Why the variation? The world inside a cell is a noisy, bustling place. Even with the same genetic blueprint, tiny random fluctuations in the number of molecules, the local environment, and interactions with thousands of other genes can nudge development down slightly different paths. So, when we talk about the expressivity of a gene, we are really talking about the distribution of possible outcomes that a single instruction can produce in the complex, stochastic theater of a living organism.

This idea of a language's power isn't confined to biology. Mathematicians and logicians have been obsessed with it for over a century. How do you formally compare the "power" of two languages, say, First-Order Logic (the language of "for all $x$," "there exists $y$") and Second-Order Logic (which can also quantify over properties, e.g., "for all possible properties $P$")?

The answer is beautifully simple in principle. A logic's expressive power is measured by the collections of "things" it can define. Imagine all possible mathematical worlds, or "structures"—things like the natural numbers with addition, or all possible graphs, or geometric spaces. A sentence in a given logic carves out a subset of these worlds: the ones in which that sentence is true. For example, a sentence might define the class of all graphs that have no cycles. Another might define all sets that are finite.

A logic $L_2$ is said to be more expressive than a logic $L_1$ if it can define all the same classes of structures as $L_1$, plus at least one more. This gives us a formal yardstick. We can now create a hierarchy of logics based on their expressive power. For instance, ​​Second-Order Logic (SOL)​​ is vastly more expressive than ​​First-Order Logic (FOL)​​. With SOL, you can write a single sentence that is true only in structures that are finite, something famously impossible in standard FOL.

But this increased power comes at a steep price. First-order logic, while less expressive, has some wonderfully convenient properties. It is ​​compact​​, meaning that if a contradiction arises from a set of axioms, it must arise from a finite number of them. It also has a ​​complete​​ proof system: a machine can be built that will eventually prove every true statement in the language.

Second-order logic loses both of these properties. Its immense expressive power makes it wild and untamable. There can be no machine that will churn out all its truths, and it is not compact. The great ​​Lindström’s Theorem​​ formalizes this trade-off: it proves that First-Order Logic is the most expressive logic possible that still retains both compactness and another related property (the Löwenheim–Skolem property). If you want more expressive power, you must sacrifice one of these cherished properties. It’s a fundamental "no free lunch" theorem at the heart of logic.

This reveals a subtle but crucial distinction. There's the power to express any idea, and then there's the power to reason systematically about the ideas you can express. The logician distinguishes between a language being ​​truth-functionally complete​​ (can it express every possible logical function?) and a proof system for that language being ​​proof-theoretically complete​​ (can it prove every valid statement expressible in that language?). You can have a perfectly "complete" proof system for a language that is, itself, quite weak in its expressive power. The two concepts are independent.

The race for expressivity isn't always about finding the most powerful language. Often, the more interesting science happens when we study languages with constraints. What can you say if you have a limited vocabulary, or if you don't have a complete map of the world you're describing?

Consider what happens if you are only allowed to use a fixed number of variables, say, $k=3$ variables $\{x, y, z\}$. This creates the language fragment known as $FO^3$. In this language, you can say things like "there exists an $x$, a $y$, and a $z$ that are all different." But you cannot express "there exist four different things," because you would run out of variables to hold their distinct identities! This simple constraint on vocabulary fundamentally limits the language's expressive power.

Now for an even more subtle constraint: the importance of having a pre-existing "order" on the world. The celebrated ​​Immerman–Vardi theorem​​ connects the expressivity of a logic to computational difficulty. It states that on ordered structures (like a list of numbers, where there's a clear first, second, third...), the logic FO(LFP) can express exactly those properties that can be computed in Polynomial Time (PTIME).

But what if the structure is unordered, like a generic bag of points in a graph? The vertices are just there, with no inherent "first" or "next" vertex. It turns out the expressive power of the same logic shrinks dramatically. For example, the simple property "Is the number of vertices in this graph even?" is trivially computable in polynomial time. So, by the Immerman-Vardi theorem, it is expressible in FO(LFP) on an ordered graph. However, it is famously not expressible in FO(LFP) on the class of general, unordered graphs. Without a way to line up the vertices and count them off, the logic is simply unable to express the concept of parity. The context in which a language is used is as important as the language itself.

Another way to boost expressive power is to allow our language to "point" at specific things in the world. In logic, this is done with ​​parameters​​. Imagine the structure of the rational numbers with their usual order, $(\mathbb{Q}, <)$. Using standard first-order logic, you can define sets like "all numbers greater than 0" or "all numbers between 10 and 20." But you cannot define the set $\{x \in \mathbb{Q} \mid x < \pi\}$, because the number $\pi$ isn't a rational number and there's nothing in the language of just < that can single it out.

But if we extend our language to allow parameters—if we can just point to a specific number, say $1.5$, and use it in our formulas—we can suddenly define new things. The formula $x < 1.5$ now defines a set that was previously undefinable. Allowing parameters is equivalent to adding names for specific individuals into our language, and it almost always expands the universe of what we can describe.

This abstract notion of expressivity has a very concrete cousin in the world of statistics and data science. When we build a statistical model to explain, say, the price of a house, we use variables like its size, number of bedrooms, and location. A natural question is: how much unique "explanatory power" does each variable bring to the table?

This is the same question as before, just in a different guise. The "language" is our regression model, and the "expressivity" is its ability to account for the variation in the data. There are elegant mathematical tools, like the ​​QR decomposition​​ of the data matrix, that can precisely measure this. The magnitude of certain numbers in this decomposition ($r_{ii}$) tells us exactly how much of the variation in one variable (say, house size) is new information and not just redundant information already provided by the other variables it's being compared against. A specific metric, $\frac{r_{ii}^2}{\lVert x_i \rVert_2^2}$, gives us a number between 0 and 1 that represents the fraction of a variable's variance that is unique—its true expressive contribution to the model.

So, we see the same theme playing out everywhere. From a fly's wing, to the grand edifice of mathematical logic, to the economist's spreadsheet, the notion of expressivity is a unifying thread. It challenges us to think deeply about the relationship between our descriptions and reality, forcing us to confront the inherent limits, trade-offs, and surprising power of the languages we use to make sense of the universe.

If you were to describe a symphony to someone who has never heard music, what words would you use? You might talk about "loud" and "soft," "fast" and "slow." You could capture a part of the experience, but the soul of the music—the harmony, the melody, the texture—would be lost. Your language would lack the necessary expressivity. In the previous chapter, we explored the principles of expressivity. Now, we embark on a journey across the scientific landscape to see this idea in action. We will discover that the challenge of science, in many ways, is the challenge of finding the right language to describe reality.

This is not a mere philosophical game. The choice of a scientific model is the choice of a language, and this choice has profound consequences. A powerful language can reveal hidden truths, predict the future, and unify disparate phenomena. A weak language can mislead us, obscure the facts, and trap us in a dead end. Let’s see how scientists navigate this crucial choice, from the inner workings of a flower to the very foundations of logic and computation.

Often in science, we are faced with several competing "stories," or models, that all seem to explain the same phenomenon. How do we choose? We act like a good detective, or perhaps a literary critic. We ask: Which story is the most convincing? Which one explains not just the "what" but the "why"? Which one does so without inventing unnecessary phantoms and ghosts?

Consider the strange case of "hypervalent" molecules in chemistry, where a central atom seems to break the sacred octet rule by bonding to more than four other atoms. For decades, students were taught a simple story involving $\text{sp}^3\text{d}$ or $\text{sp}^3\text{d}^2$ hybrid orbitals. This language neatly matched the observed molecular shapes predicted by VSEPR theory. It was a simple, tidy story. But was it true?

Modern evidence from spectroscopy and high-level computations tells a different tale. These experiments act like an interrogation, and they reveal that the central atom’s $d$-orbitals are almost complete bystanders in the bonding; their participation is negligible. The old story, while simple on the surface, invoked characters—the participating $d$-orbitals—that were essentially ghosts. A more sophisticated language, based on delocalized Molecular Orbitals (MO theory) and concepts like the three-center, four-electron (3c-4e) bond, tells a more accurate story. It explains not only the shape but also the subtle differences in bond lengths and the results of spectroscopic experiments, all without invoking energetic ghosts. In this case, the model with greater explanatory power and parsimony—the one that makes fewer unsupported assumptions—is the clear winner, even if it seems more complex at first glance.

This theme of evolving our language to tell a better story echoes throughout biology. Take the development of a flower. The classical ABC model provides a simple code: gene A makes sepals, A+B makes petals, and so on. This model works, but it’s more of a correlation than an explanation. A newer model, the ABCDE model, adds a crucial character to the story: the E-class genes. It turns out these genes are necessary co-factors; you can’t make a petal with just A and B, you need the combination A+B+E. This expanded language allows us to explain things the old one couldn't, like how some plants evolve petal-like sepals by simply switching on B-class genes in the outermost whorl. The ABCDE model has greater explanatory power because it provides a deeper, more mechanistic account of how a flower is built. Science progresses by refining its language to be more expressive.

The language we choose doesn't just describe individual phenomena; it shapes how we organize the world. The act of classification, of putting things into categories, is one of the most fundamental acts of science. But where do we draw the lines?

In evolutionary biology, the "species problem" is a classic example. What is a species? Should we group organisms based on what they look like (the Morphological Species Concept), who they are related to (the Phylogenetic Species Concept), or what they do (the Ecological Species Concept)? The fascinating answer is: it depends.

Imagine you have three different sets of evidence for the same group of organisms. In one scenario, you have clear, distinct morphological differences, but the genetic data is a mess. In another, you have a beautifully resolved family tree from genomics, but the organisms look identical. In a third, you find that different groups are exquisitely adapted to different habitats, but they look similar and their genes are still mixing. As one might formalize with a framework of epistemic virtues, the "best" species concept—the one with the most explanatory power for that situation—changes with the data. There is no one-size-fits-all language for carving up the tree of life. The expressivity of a concept is not absolute; it is judged by its ability to create a coherent and powerful narrative from the available evidence.

The idea of expressivity finds its most formal and powerful application in the world of computer science and artificial intelligence. Here, it is not an analogy but a mathematical property of a model.

We are living in an age where we can build models of staggering complexity. Consider a Neural Ordinary Differential Equation (Neural ODE), a type of neural network designed to learn the laws of motion of a dynamic system directly from data. A stunning theoretical result, the universal approximation theorem, states that a sufficiently large Neural ODE has the theoretical capacity to approximate any continuous dynamic system to any desired accuracy. This is a statement of almost breathtaking expressivity. It suggests that, in principle, we could discover the complex feedback loops governing a cell or an ecosystem without writing down a single equation by hand.

But we must be careful, as a good physicist always is! This theorem guarantees what is possible, not what is easy. It proves the language is rich enough, but it doesn't guarantee we can find the right "words" (the network parameters) through training, nor that the resulting "sentence" will be understandable to a human.

Furthermore, not all AI models are created equal. The very architecture of a model defines its language and its limits. A Graph Neural Network (GNN), which is fantastically successful at predicting properties of molecules, operates by passing messages between neighboring atoms in a graph. It has been proven that this message-passing mechanism imposes a fundamental ceiling on the network's expressive power. A standard GNN can be no better at distinguishing two different molecular graphs than a classic, simple computer science algorithm known as the 1-dimensional Weisfeiler-Leman (1-WL) test. This is a profound insight: the network's "view" of the world is constrained by its local, iterative nature. It cannot express concepts about graph structure that the 1-WL test cannot see. The model's power comes from what it can say, but its reliability and efficiency also come from what it cannot.

A language, no matter how expressive, is useless without something to talk about. The power of our models is inextricably linked to the quality and nature of our data.

Imagine trying to understand the social dynamics of a city by interviewing a random sample of citizens who have been teleported to a lecture hall. You could learn about the demographics, the average opinions, the different "types" of people. But you would have no idea about neighborhoods, about who talks to whom, about the flow of influence through the social network.

This is precisely the difference between dissociated single-cell RNA sequencing and modern spatial transcriptomics. In the former, a tissue is ground up, and the gene expression of each individual cell is read out—it's a "bag of cells." In the latter, the cells are analyzed in situ, preserving their spatial relationships. By retaining this spatial context, we can build models with vastly greater explanatory power. We can ask questions about how a cell's fate is determined by its neighbors. We can test specific hypotheses about signaling pathways that are simply impossible to address with the dissociated data. The act of dissociation destroys information, and in doing so, it cripples the expressive power of any model we might build. The richness of our data determines the richness of the stories we can tell.

Even subtle changes in our data can change a model's dialect. In finance, the classic Fama-French three-factor model seeks to explain stock returns using a "language" of three factors: the market as a whole, a factor for company size, and a factor for value. If we change the definition of the "market factor" from a value-weighted index to an equal-weighted index, we are subtly changing one of the words in our language. This new word overlaps more with the "size" factor, since small companies get more weight. The result is that the model's overall explanatory power ($R^2$) changes very little, but its ability to describe certain stocks (especially small ones) may be slightly altered. This is a beautiful microcosm of the scientific process: fine-tuning our descriptive language to better capture the nuances of reality.

We end our journey at the most fundamental level, in the abstract realms of mathematical logic and the theory of computation. Here, expressivity is not just a useful concept; it is the central object of study.

Logicians have discovered that different formal languages have different, and sometimes incomparable, powers. For example, a logic called FO(LFP) can express the property of CONNECTIVITY in a graph—a concept involving paths of arbitrary length. Another logic, FO+C, can express properties about the number of nodes, like EVEN_CARDINALITY. Astonishingly, FO(LFP) cannot talk about evenness, and FO+C cannot talk about connectivity. They are like two alien languages, each capable of expressing profound truths that are utterly unsayable in the other.

This leads us to two of the deepest results in all of science. The first concerns the famous P vs NP problem. This question, which asks whether every problem whose solution can be checked efficiently can also be solved efficiently, can be completely reframed as a question about logical expressivity. Fagin's Theorem tells us that NP corresponds precisely to the properties expressible in Existential Second-Order Logic (SO-E). The Immerman-Vardi Theorem tells us that P corresponds to properties expressible in First-Order Logic with a Least Fixed-Point operator (FO(LFP)). The P = NP question is therefore equivalent to asking: do these two logical languages have exactly the same expressive power? A question about the limits of practical computation is, at its heart, a question about the limits of logical expression.

Finally, we arrive at Lindström's Theorem, a result of breathtaking scope and beauty. It provides a characterization of first-order logic (FO)—the familiar logic of "for all" and "there exists" that underpins most of mathematics. The theorem states that FO is the absolute strongest (most expressive) logic possible that still retains two very desirable properties: Compactness and the downward Löwenheim-Skolem property. If you try to invent a new logic that can say something FO cannot (for example, a sentence that is true only in finite structures), you are forced to break one of these two elegant properties. Lindström's Theorem reveals a fundamental trade-off at the heart of logic itself. It explains why first-order logic occupies such a perfect "sweet spot" in the universe of possible languages—it is poised at the maximal point of expressivity before the logical world begins to unravel into strangeness.

From the color of a petunia to the fate of the universe, and from the stock market to the foundations of mathematics, the challenge is always the same: to find a language that is rich enough to tell the truth, yet simple enough to be understood. The quest for knowledge is a quest for more expressive power, a journey to find the words to describe the poetry of the real world.