Model Theory and the Expressiveness Limits of Neural Nets

The expressiveness of neural networks is fundamentally constrained by their inability to instantiate the logical structures that model theory takes as primitive.

This is not a statement about depth, width, or training dynamics. It is a statement about what these architectures can represent at all, regardless of scale or optimization. The gap between what neural networks can compute and what symbolic mathematics requires is not a engineering problem waiting for the next breakthrough. It is a structural incompatibility that becomes visible the moment you examine what model-theoretic reasoning actually demands.

Consider what happens when a neural network attempts to solve a problem in first-order logic. The network processes continuous transformations of weighted inputs. At no point in this process does it construct an explicit model—a concrete assignment of truth values to propositions under a specific interpretation. Model theory, by contrast, is built on the notion that logical validity means truth across all possible models. A formula is valid if and only if it holds in every interpretation that satisfies its axioms. This is not metaphorical. It is the definition.

A neural network can learn to approximate the behavior of a logical reasoner. It can be trained to produce outputs consistent with valid inferences. But approximation is not instantiation. When a network learns to output "true" for a valid formula, it has learned a statistical pattern. It has not constructed the set of all models in which that formula must hold. It cannot enumerate them, cannot verify them, cannot reason about their structure. The network has no internal representation of what a model is.

This matters because symbolic mathematics—the kind that matters in formal verification, theorem proving, and rigorous computer science—depends entirely on this model-theoretic apparatus. When you prove that a program is correct, you are not showing that a neural network assigns high probability to correctness. You are showing that the program's behavior is consistent with a formal specification across all possible execution states. You are reasoning about models.

The expressiveness problem runs deeper than the familiar limitations of feedforward architectures. Even recurrent networks, transformers, and other sophisticated designs face the same fundamental constraint. These architectures can approximate functions. They cannot construct logical structures. They cannot maintain the kind of discrete, verifiable, compositional semantics that model theory requires.

Consider a concrete example: the satisfiability problem for first-order logic. A neural network might learn to classify many instances correctly. But it cannot solve the general problem because solving it requires exploring the space of possible models—a space that is often infinite, always discrete, and fundamentally symbolic in nature. The network has no mechanism for this exploration. Its operations are continuous. Model construction is discrete.

This is where the literature often becomes confused. Papers demonstrate that neural networks can learn to solve logical problems on specific datasets. This proves nothing about expressiveness. It proves only that networks can memorize or interpolate patterns. The expressiveness question asks: what can the architecture represent in principle, not what can it learn from examples?

The implications are not pessimistic—they are clarifying. Neural networks excel at tasks where continuous approximation suffices: pattern recognition, function approximation, statistical inference. Symbolic mathematics requires something different. It requires discrete, verifiable, model-theoretic reasoning. These are not weaknesses in neural networks. They are fundamental differences in what these systems are designed to do.

The path forward is not to force neural networks to do symbolic work. It is to recognize that some problems require symbolic methods, and some require neural methods, and the most interesting problems require both. The expressiveness limits revealed by model theory are not obstacles to overcome. They are boundaries that clarify where each approach belongs.