Upward Löwenheim-Skolem Theorem

How can a finite set of rules, written in a formal language, describe an infinite universe? This question strikes at the heart of mathematical logic and our ability to formalize reality. If our logical systems are powerful enough to conceive of one infinite structure, what prevents them from describing other, vastly larger infinities? The Upward Löwenheim-Skolem theorem provides a startling answer, revealing a fundamental "relativity of size" inherent in first-order logic. It suggests that our finite descriptions of the infinite are far more flexible—and far less specific—than we might intuitively believe. This article navigates the profound consequences of this theorem. The first section, "Principles and Mechanisms," will unpack the theorem's logic, demonstrating how logicians use the Compactness Theorem to construct ever-larger universes that satisfy the same set of axioms. Subsequently, "Applications and Interdisciplinary Connections" will explore the theorem's deep impact on mathematics and philosophy, from the existence of bizarre "non-standard" numbers to the famous Skolem's Paradox, which challenges our very notion of infinity.

Imagine you are a physicist, or a philosopher, trying to write down the fundamental laws of a universe. You have a formal language—the language of first-order logic—which allows you to make precise statements using symbols for objects, properties, and relations. Your language is your toolkit. Each statement, or axiom, you write down is a finite string of symbols. Now, a fascinating question arises: can a finite set of rules truly describe an infinite universe? And if it can, what does that imply about the kinds of universes that are possible?

This is where our journey into the Löwenheim-Skolem theorem begins. It’s a journey that reveals a strange and beautiful property of logical systems, a kind of "relativity of size" that is built into the very fabric of mathematical description.

Let's try to pin down the concept of "infinity." Your first instinct might be to write a single, grand axiom that says, "This universe is infinite." But in first-order logic, this is impossible. Every sentence you can write is a finite string of symbols, and it turns out that any such sentence that is true in some infinite universe will also be true in some (possibly very large) finite one. Infinity, it seems, is too slippery for any single finite statement to grasp.

So, how do logicians do it? They use a wonderfully clever trick. Instead of one axiom, they use an infinite collection of axioms. Imagine a "staircase to infinity." For the first step, we write an axiom $\psi_2$ that says, "There exist at least two distinct things." For the next, we write $\psi_3$: "There exist at least three distinct things." And so on, for every natural number $n$:

No single axiom demands infinity, but the entire infinite collection, taken together, does. Any universe that satisfies all of these axioms cannot be finite, because for any finite number $k$, it would fail to satisfy the axiom $\psi_{k+1}$.

But this raises a new problem. How can we be sure that this infinite set of axioms is consistent? How do we know there's any universe that can satisfy all of them simultaneously? The answer lies in one of the most powerful tools in a logician's arsenal: the ​​Compactness Theorem​​.

The ​​Compactness Theorem​​ is like a magical bridge between the finite and the infinite. It tells us that if every finite collection of axioms from our set has a model, then the entire infinite set of axioms must also have a model. For our staircase to infinity, this is easy to check. Any finite handful of our axioms, say $\{\psi_2, \psi_5, \psi_{100}\}$, is satisfied by any universe with at least 100 things. Since we can always imagine such a universe, every finite subset is satisfiable. Therefore, by compactness, the whole infinite set is satisfiable. We have successfully forced our universe to be infinite!

So, we have a theory $T$ and we know it has at least one infinite model. This means our laws are consistent with an infinite reality. The Upward Löwenheim-Skolem theorem now asks a breathtakingly ambitious question: If one infinite universe is possible, what about a bigger one? An unimaginably bigger one?

The theorem's answer is a resounding "yes." If your theory allows for one infinite model, it allows for models of every possible infinite size above a certain threshold. It’s a "paradox of scale": the same finite set of laws can govern a countably infinite universe of stars and an uncountably vast universe of universes, all without a single change to the rulebook.

How is this possible? The proof is another piece of logical artistry. Let's say we have our theory $T$ with an infinite model, and we want to build a new model of some enormous infinite size, let's call it $\kappa$.

The strategy is bold: we simply postulate the existence of $\kappa$ distinct things. We do this by expanding our language. We invent a huge set of new names, or ​​constant symbols​​, $\{c_i : i \kappa\}$, one for each element we want. Then, we add to our theory $T$ a new list of axioms, a very long list, stating that all these new names refer to different objects:

We now have a massive new theory. Does it have a model? Once again, we turn to our hero, the ​​Compactness Theorem​​. We only need to check if every finite part of this new theory is satisfiable. A finite part will only contain axioms from $T$ and a finite number of these new distinctness axioms, say $c_1 \neq c_2$, $c_7 \neq c_{42}$, etc. Since our original model of $T$ was infinite, we can always find enough distinct elements within it to serve as interpretations for this finite list of new names. So, every finite subset has a model.

By compactness, the entire enormous theory has a model! And by its very construction, this model must contain at least $\kappa$ distinct elements. We have successfully built a universe of at least size $\kappa$.

This power to create arbitrarily large universes seems almost too good to be true. Is there a catch? Yes, there is a subtle but crucial condition: you can build a model of any infinite size $\kappa$, as long as $\kappa$ is at least as large as the ​​cardinality of your language​​, denoted $|\mathcal{L}|$.

The cardinality of your language is, simply put, the number of non-logical symbols you have—the number of "words" in your specialized vocabulary for describing the universe (the constants, functions, and relation symbols). This number, $|\mathcal{L}|$, acts as a kind of cosmic speed limit in reverse; it sets a minimum scale for the universes you can guarantee to build.

Why should your vocabulary limit the size of your universe? Imagine a theory that includes an axiom for every symbol in your language, forcing each one to represent something unique. For instance, if your language had $\aleph_{17}$ distinct constant symbols, and your theory stated they were all pairwise different, no model of that theory could possibly have a size smaller than $\aleph_{17}$.

The more formal reason emerges from the fine print of the proof. The compactness trick gives us a model of size at least $\kappa$. To get a model of exactly size $\kappa$, we need a second tool: the ​​Downward Löwenheim-Skolem theorem​​. This theorem allows us to take a huge model and carve out a smaller, but still complete, elementary substructure from within it. However, the size of the substructure we can carve out is itself limited by the size of our language. To guarantee we can shrink our universe down to exactly size $\kappa$, we need to ensure that $\kappa$ is already greater than or equal to the language's cardinality. This beautiful interplay between the upward and downward theorems reveals the profound connection between the language we use and the worlds we can describe.

We've built a new, bigger universe $N$ that follows the same laws $T$ as our original universe $M$. But what is the relationship between them? Is $N$ a completely alien world, or is it a true extension of $M$?

The strongest form of the Upward Löwenheim-Skolem theorem gives us the more powerful result: we can construct $N$ to be an ​​elementary extension​​ of $M$, written $M \preccurlyeq N$. This means that $N$ doesn't just obey the same general laws; it contains a perfect, indistinguishable copy of the original universe $M$. Any statement you could make about $M$, even using its own inhabitants as points of reference, remains true when interpreted in the grander context of $N$. It's like discovering our universe is just one galaxy in a supercluster, but in a way that perfectly preserves all our local physics.

How do we achieve this? We enhance our compactness proof. Instead of just starting with the axioms of $T$, we start with the complete "logbook" of our universe $M$. This is the ​​elementary diagram​​ of $M$, denoted $\mathrm{Diag_{el}}(M)$, which is the set of every single true sentence about $M$, including sentences that name its specific inhabitants. By applying the compactness trick to this incredibly detailed theory, the new model we build is guaranteed to be an elementary extension.

Finally, it's just as important to understand what the Löwenheim-Skolem theorem doesn't say.

• It does ​​not​​ require a theory to be ​​complete​​. A theory is complete if, for any sentence $\varphi$, it proves either $\varphi$ or its negation $\neg\varphi$. Most interesting theories are incomplete. The LS theorems work just fine as long as there is at least one infinite model to start with; the proofs depend on the existence of a model, not the syntactic properties of the theory.

• It does ​​not​​ mean all models of the same size are identical (isomorphic). A theory can have many structurally different models that all happen to have the same cardinality. For a complete theory, all its models are elementarily equivalent—they satisfy the same sentences—but they can still be non-isomorphic. Two universes can follow the same laws and have the same number of galaxies, but those galaxies can be arranged in fundamentally different ways.

The Upward Löwenheim-Skolem theorem is a profound statement about the relationship between syntax and semantics, between our finite descriptions and the infinite realities they can model. It tells us that for first-order logic, the notion of "size" is surprisingly fluid. Once a theory opens the door to infinity, it cannot close it; it must admit a whole spectrum of infinities, a dazzling array of possible worlds, all obeying the same handful of rules.

Now that we have grappled with the machinery of the Upward Löwenheim-Skolem theorem, a natural question arises: So what? Is this theorem just a curious piece of logical acrobatics, a trick pulled from a mathematician's hat? Or does it tell us something deep and essential about the world of mathematics and the language we use to explore it? The answer, perhaps unsurprisingly, is that its consequences are profound, rippling through algebra, number theory, and even the philosophical foundations of mathematics itself. It is not merely a statement in logic; it is a statement about the nature of logic and the structures it purports to describe.

Let's begin our journey in a familiar land: linear algebra. We all learn the axioms of a vector space. They seem simple enough—rules for adding vectors and scaling them. If we add axioms stating that our space is infinite-dimensional (for any number $n$, we can always find $n$ linearly independent vectors), we have a first-order theory for infinite-dimensional vector spaces. What kinds of objects satisfy these rules? We can think of spaces of functions or sequences. But the Löwenheim-Skolem theorems tell us a much grander story. If there is one infinite-dimensional vector space over a countable field (like the rational numbers $\mathbb{Q}$), then there must be one for every infinite cardinality. There is a countably infinite one, one the size of the real numbers, and on and on, a veritable zoo of vector spaces spawned by a few simple logical rules.

This isn't just an abstract guarantee; it reveals a beautiful harmony between the logical description and the algebraic reality. For these spaces built over a countable field, the theorem forces a stunningly simple relationship: any model of cardinality $\kappa$ greater than countable must have a basis of that same cardinality $\kappa$. The logic doesn't just predict the existence of these vast, exotic spaces; it also constrains their fundamental structure.

The situation becomes even more startling when we turn to what we believe is the most solid ground in mathematics: the natural numbers $\mathbb{N} = \{0, 1, 2, \dots\}$. We can write down a list of axioms in first-order logic, known as Peano Arithmetic (PA), that attempts to capture the essence of these numbers. The standard numbers, $\mathbb{N}$, form a perfectly good model of these axioms. Since this model is infinite, the Upward Löwenheim-Skolem theorem kicks in with relentless force. It guarantees that there must be other models of PA of every infinite cardinality—uncountably many models that all satisfy the same first-order rules of arithmetic as our familiar numbers.

What could such a model possibly look like? An uncountable model of arithmetic is necessarily a bizarre and fascinating creature. It must contain all the standard numbers we know and love, but it must also contain "non-standard" numbers—entities that are larger than any standard natural number, yet still obey the laws of arithmetic. There are numbers in these models that you can add, multiply, and compare, but which you could never reach by starting at 0 and counting. The theorem doesn't just build these strange new worlds; it proves they are an inescapable consequence of describing arithmetic using first-order logic.

This ability of logic to create models of different sizes leads to one of the most mind-bending results in the foundations of mathematics, often called "Skolem's Paradox." While our focus is the upward theorem, its sibling, the downward theorem, plays a key role here. The downward theorem states that if a first-order theory (in a countable language) has a model, it must have a countable one.

Now, consider the axioms of modern set theory, Zermelo-Fraenkel with Choice (ZFC). This theory is our foundation for all of mathematics. It proves the existence of uncountable sets, like the set of real numbers $\mathbb{R}$. Yet, by the Downward Löwenheim-Skolem theorem, if ZFC is consistent, it must have a countable model. This seems like a flat contradiction. How can a model whose entire collection of elements is countable nonetheless satisfy a theorem which says "the set of real numbers is uncountable"?

The resolution is a profound lesson in the relativity of mathematical truth. The statement "the set of real numbers is uncountable" means "there exists no bijection from this set to the set of natural numbers." When this statement is interpreted inside the countable model, it means no such bijection can be found among the objects that constitute the model. The bijection that proves the set is truly countable exists outside, in the larger universe where we are observing the model. The model itself is blind to it. "Uncountability," and indeed size itself, is not an absolute concept but is relative to the model of set theory one is in. The Löwenheim-Skolem theorems force us to abandon a naive, absolute view of infinity and accept that our formal descriptions are always from a particular point of view.

So far, we have used the theorem to understand mathematical structures. But its most important application may be turning the lens back on logic itself. What do the Löwenheim-Skolem theorems reveal about the very nature of first-order logic?

They reveal that first-order logic has a fundamental "blind spot": it is incapable of distinguishing between different infinite cardinalities. If a first-order theory permits one infinite model, it is forced to permit a model of every infinite size. It cannot pin down a unique infinite structure. This is not a flaw but a defining characteristic. This "weakness" is also a strength, as it gives rise to a rich model theory and powerful tools.

We can see this limitation in sharp relief by comparing it to a more powerful system: Second-Order Logic (SOL). In SOL, we are allowed to quantify not just over individual elements, but over sets of elements. This added power allows one to write an axiom (the "principle of induction") that is so strong it completely specifies the natural numbers. The second-order theory of arithmetic is categorical: its only model is, up to isomorphism, the standard natural numbers $\mathbb{N}$. There are no non-standard models, no uncountable models. The Löwenheim-Skolem theorems fail for SOL. This contrast teaches us that the strange world of non-standard models and relative infinities is a direct consequence of the specific expressive power of first-order logic.

This brings us to a truly magnificent conclusion, a capstone result known as Lindström's Theorem. We have seen two key properties of first-order logic: the Compactness Theorem (what is possible in every finite case is possible as a whole) and the Löwenheim-Skolem property. Lindström's theorem proves that these two properties are the essence of first-order logic. Any regular logic that extends first-order logic and possesses both of these properties can be no more expressive than first-order logic itself.

This means that the "blind spot" of the Löwenheim-Skolem property is not an accident; it is inextricably tied to the power of compactness. Any logic enjoying both cannot express concepts like "finiteness" or "well-ordering" with a single sentence, because first-order logic cannot. The Upward Löwenheim-Skolem theorem is not just some isolated curiosity. It is part of the very fingerprint of first-order logic, the most widely used logical system for formalizing mathematics. It is a fundamental feature of the world as seen through the lens we have chosen to use. It shows us that every description is a doorway to an infinite spectrum of possibilities, a testament to the boundless creativity inherent in the mathematical universe.