Standard Semantics

How do we connect abstract symbols on a page to concrete meaning and truth? The sentence "The sky is blue" is true or false depending on the world we observe, but creating a formal, mathematical system to capture this relationship is one of modern logic's greatest challenges. This problem—of building a rigorous bridge between formal languages and the worlds they describe—was definitively solved by the work of Alfred Tarski. His framework, known as standard or Tarskian semantics, provides a precise machine for evaluating the truth of a statement relative to a given interpretation. It forms the foundation of how we understand logical validity, mathematical structures, and the limits of formal reasoning itself.

This article delves into the core of standard semantics, exploring both its foundational principles and its profound consequences. By dissecting this framework, we can understand not just how logic works, but also why it works the way it does. The following chapters will guide you through this powerful theory. In "Principles and Mechanisms," we will open up the Tarskian machine to examine its components: the models, domains, and recursive rules that give meaning to symbols. Then, in "Applications and Interdisciplinary Connections," we will see how this abstract machinery powers fields from computer science to philosophy, shaping our understanding of everything from automated reason to the nature of infinity and the inherent limits of knowledge.

Imagine you have a language. It might be a simple language, with nouns for objects, verbs for actions, and adjectives for properties. How do you connect this language to reality? How do you decide if a sentence like "The red ball is rolling" is true? You need two things: a context (the "world" you are talking about) and a dictionary that links your words to things in that world. If you're in a room with a blue cube that is stationary, the sentence is false. If you're on a playground with a rolling red ball, it's true.

The monumental achievement of the logician Alfred Tarski was to formalize this simple intuition into a rigorous mathematical theory of truth. This framework, known as ​​Tarskian semantics​​, is the bedrock of modern logic. It doesn't tell us what is true in the absolute sense, but it gives us a precise machine for determining the truth of a sentence relative to a specific, chosen world. This chapter is about opening up that machine and seeing how its gears turn.

Before we can speak of truth, we must first define the "world" our language describes. In logic, we call this a ​​structure​​ or a ​​model​​. Think of your formal language as a set of blueprints. A structure is the actual, tangible building constructed from those blueprints. And just as the same blueprint can be used to build a house, a school, or a skyscraper, the same logical language can be used to describe vastly different worlds.

So, what are the components of a structure, $\mathcal{M}$? It’s surprisingly simple. A structure consists of just two fundamental parts:

1. A ​​domain of discourse​​, often written as $|\mathcal{M}|$. This is simply a collection of "things" we want to talk about. It could be the set of all natural numbers, $\mathbb{N} = \{0, 1, 2, \dots\}$, the set of all people in a room, or even a hypothetical set of characters in a novel. The only rule for this collection, as we'll see, is that it cannot be empty.

2. An ​​interpretation function​​, often written as $I$ or as a superscript $^{\mathcal{M}}$. This is our "dictionary." It systematically links the non-logical symbols of our language—the names, functions, and predicates—to actual objects, functions, and relations within the domain.

Let's say our language has a constant symbol $c$, a unary (one-place) function symbol $f$, and a binary (two-place) relation symbol $R$. A structure $\mathcal{M}$ for this language must provide the following:

• For the constant symbol $c$, it gives us a specific object $c^{\mathcal{M}}$ from the domain $|\mathcal{M}|$. The symbol $c$ is just ink on a page; $c^{\mathcal{M}}$ is the real thing it points to.
• For the function symbol $f$, it gives us an actual function $f^{\mathcal{M}}: |\mathcal{M}| \to |\mathcal{M}|$. This function takes one object from the domain and returns another object in the domain.
• For the relation symbol $R$, it gives us an actual relation $R^{\mathcal{M}} \subseteq |\mathcal{M}|^2$. A binary relation is just a set of ordered pairs of objects from the domain. The relation $R^{\mathcal{M}}$ tells us which pairs of objects in the world actually stand in that relation to each other.

For instance, if our domain is the natural numbers $\mathbb{N}$, we could interpret $c$ as the number $0$, $f$ as the successor function ($f(n) = n+1$), and $R$ as the "less than" relation (which is the set of all pairs $(n,m)$ where $n \lt m$). This gives us the structure we call "the natural numbers with successor and less than." We could just as easily use the same language but interpret the domain as people, $c$ as 'Socrates', $f$ as 'the teacher of', and $R$ as 'is older than'. The language is abstract; the structure makes it concrete.

Now, there are two crucial, almost hidden, requirements here that are essential for the whole enterprise to work. First, the interpretation of a function symbol must be a ​​total function​​. This means it must be defined for every object in the domain. Why? Because we want every name we can construct in our language to actually refer to something. If $f$ were a partial function, a term like $f(c)$ might be undefined. If that happened, how could we determine the truth of a sentence like $R(f(c), c)$? The entire mechanism for evaluating truth would grind to a halt. By insisting on total functions, we ensure there are no "truth-value gaps." Every well-formed term has a denotation.

The second requirement is even more fundamental: the domain of discourse cannot be empty. This might seem odd. Surely we can talk about nothing? But in logic, allowing for an empty world leads to some very strange and undesirable paradoxes.

Why do we ban the empty set as a domain of discourse? The reason is a beautiful example of how logicians make pragmatic choices to preserve the elegance and consistency of their systems. Let’s perform a thought experiment and imagine a structure $\mathcal{M}$ with an empty domain, $|\mathcal{M}| = \emptyset$.

Consider a universally quantified statement, like "All things have property $\varphi$," written as $\forall x \, \varphi(x)$. To check if this is true, we must check that every object $a$ in the domain has the property. But in our empty world, there are no objects to check! A statement that is "for all" objects in an empty collection is said to be ​​vacuously true​​. So, $\forall x \, \varphi(x)$ would be true.

Now consider an existentially quantified statement, "There exists something with property $\varphi$," written as $\exists x \, \varphi(x)$. To check if this is true, we must find at least one object $a$ in the domain that has the property. In our empty world, we can't find any objects at all. So, $\exists x \, \varphi(x)$ must be false.

Here's the problem: in standard logic, the formula $\forall x \, \varphi(x) \to \exists x \, \varphi(x)$ is a logical theorem. It can be proven from the basic axioms. It essentially says, "If everything has a property, then surely something has that property." But in our empty structure, the antecedent ($\forall x \, \varphi(x)$) is true and the consequent ($\exists x \, \varphi(x)$) is false. An implication "true $\to$ false" is false. So, a provable theorem of our logic would be false in this structure. This would mean our proof system is ​​unsound​​—it proves falsehoods!

Rather than cripple our proof systems, logicians made a simple, elegant choice: they outlawed empty domains by definition. Any "structure" must have a non-empty domain. This convention, among other things (like being unable to interpret constant symbols, which must point to something in the domain), preserves the harmony between what is provable (syntax) and what is true (semantics).

With our structures properly defined, we are ready to build Tarski's machine for truth. The goal is to determine whether a formula $\varphi$ is true in a structure $\mathcal{M}$, a relationship we write as $\mathcal{M} \models \varphi$. The genius of Tarski's approach is that it is ​​recursive​​. It defines the truth of complex formulas in terms of the truth of their simpler parts.

The process starts with the simplest possible expressions and builds up from there. For propositional logic, this is very straightforward. The connectives like and ($\land$) and or ($\lor$) are ​​truth-functional​​. This means the truth of a compound sentence like $\varphi \land \psi$ depends only on the truth values of $\varphi$ and $\psi$, not on their internal structure or meaning. This is why we can use simple truth tables to evaluate them.

First-order logic is trickier because of variables. What does a formula like $x > 0$ mean? Its truth depends on what $x$ refers to. To handle this, Tarski introduced the idea of a ​​variable assignment​​, $s$, which is a temporary mapping from variables to objects in the domain. Think of it as a guide telling us, "for this evaluation, let's say $x$ refers to the number 5."

Now, the Tarskian machine can run. Given a structure $\mathcal{M}$ and an assignment $s$, it proceeds in steps:

1. ​​Interpret Terms:​​ First, we find the denotation of every term (a name for an object). If a term is a constant $c$, it denotes $c^{\mathcal{M}}$. If it's a variable $x$, it denotes $s(x)$. If it's a compound term like $f(t_1, t_2)$, we first find the denotations of $t_1$ and $t_2$, say $a_1$ and $a_2$, and then the term's denotation is the result of applying the function $f^{\mathcal{M}}$ to them: $f^{\mathcal{M}}(a_1, a_2)$.

2. ​​Evaluate Atomic Formulas:​​ These are the simplest claims, like $R(t_1, t_2)$. We find the objects that $t_1$ and $t_2$ denote, say $a_1$ and $a_2$. The formula is true if the pair $(a_1, a_2)$ is in the set that interprets the relation $R$, i.e., $(a_1, a_2) \in R^{\mathcal{M}}$.

3. ​​Evaluate Connectives:​​ This works just like in propositional logic. For example, $\mathcal{M}, s \models \varphi \land \psi$ if and only if both $\mathcal{M}, s \models \varphi$ and $\mathcal{M}, s \models \psi$ are true.

4. ​​Evaluate Quantifiers:​​ This is Tarski's masterstroke. How do you check $\forall x \, \varphi(x)$ in an infinite domain? You can't check every object one by one. Tarski's solution is brilliantly elegant: $\mathcal{M}, s \models \forall x \, \varphi$ is true if and only if the subformula $\varphi$ remains true no matter which object $a$ from the domain we choose to assign to $x$. Formally, for all $a \in |\mathcal{M}|$, it must be that $\mathcal{M}, s[x \mapsto a] \models \varphi$, where $s[x \mapsto a]$ is a new assignment that's just like $s$ except it maps $x$ to $a$. This transforms a potentially infinite problem into a single, precise logical condition.

For a sentence—a formula with no free variables—the truth value doesn't depend on the initial assignment $s$ at all. So we can simply write $\mathcal{M} \models \varphi$ if it's true in $\mathcal{M}$ for any (and thus all) assignments.

There is one symbol that holds a special place in this system: the equality symbol, $=$. Unlike other relation symbols, its meaning is not up for grabs. In any structure $\mathcal{M}$ you can imagine, the formula $t_1 = t_2$ is defined to be true if and only if the terms $t_1$ and $t_2$ denote the exact same object in the domain. The interpretation of $=$ is always fixed as the identity relation.

Why this rigidity? Because the rules of reasoning we hold most dear depend on it. One of the most basic principles of logic is the ​​substitution of identicals​​: if you know $a=b$, and you know that "a has property P", you should be able to conclude that "b has property P".

Let's imagine for a moment that we allowed $=$ to be interpreted as some other relation, say, "has the same color as." Now consider a structure with two objects: a red ball (object 1) and a red cube (object 2). Let $P$ be the property "is a ball".

• Is $1=2$ true? In our new interpretation, yes, because they have the same color.
• Is $P(1)$ true? Yes, object 1 is a ball.
• By the substitution rule, we should conclude $P(2)$. But this is false; object 2 is a cube!

Our logical system would be ​​unsound​​; it would lead us from true premises to a false conclusion. To prevent this catastrophic failure, standard first-order logic insists that $=$ always means true identity. This ensures that when we substitute equals for equals, we are always talking about the very same thing, and our deductions remain truth-preserving.

The Tarskian framework for first-order logic is incredibly powerful, but it has limits. There are some concepts, like "finiteness" or "countability," that cannot be expressed. To capture them, we must climb to ​​second-order logic​​. Here, we gain the ability to quantify not just over individual objects ($x, y, \dots$), but also over relations ($X, Y, \dots$) and functions ($F, G, \dots$). We can now say things like "There exists a relation $X$ that is a linear ordering..."

Under the ​​full standard semantics​​ for second-order logic, this new power is interpreted in the most expansive way possible. When we say "for all relations $X$," we mean for all possible relations. For an $n$-ary relation variable $X$ on a domain $M$, the quantifier $\forall X$ ranges over the entire power set of $M^n$, which is the set of all subsets of $M^n$.

This leap grants immense expressive power. With a single second-order sentence, one can uniquely characterize the natural numbers (the Peano axioms), something impossible in first-order logic. However, this power comes at a great cost. The beautiful symmetry of first-order logic, enshrined in Gödel's Completeness Theorem—that every semantic truth has a syntactic proof ($\models$ implies $\vdash$)—is lost. In the world of full second-order semantics, there are truths that no formal proof system can ever hope to capture. The bridge between truth and provability becomes a one-way street. We gain the ability to say more, but we lose the certainty that we can prove everything we can say. This trade-off between expressiveness and completeness is one of the most profound discoveries in modern logic.

Having journeyed through the principles and mechanisms of standard semantics, one might be left with the impression of a beautiful but abstract clockwork, a formal game of symbols and structures. But this machinery is far from a mere intellectual curiosity. It is the very engine that powers our understanding of reason, the blueprint for artificial intelligence, the language of modern mathematics, and a lens through which we can glimpse the profound limits of knowledge itself. In this chapter, we will explore how the simple, elegant rules of Tarskian truth blossom into a rich tapestry of applications and deep interdisciplinary connections.

At its most fundamental level, logic is the science of correct reasoning. But what does it mean for an argument to be "correct"? Before Tarski, this question lingered in the realm of intuition. Standard semantics provides a beautifully simple and rigorous answer: an argument is valid if its conclusion is true in every possible world—every structure—where its premises are true.

Consider a simple argument: "All logicians are thinkers. There exists at least one logician. Therefore, there exists at least one thinker." We can formalize this with predicates $P(x)$ for "$x$ is a logician" and $Q(x)$ for "$x$ is a thinker". The argument becomes: from the premises $\forall x (P(x) \rightarrow Q(x))$ and $\exists x P(x)$, can we conclude $\exists x Q(x)$? Semantically, we test this by imagining every possible universe. In any universe where the premises hold, the second premise tells us there must be some individual, let's call her 'Ada', for whom $P(\text{Ada})$ is true. The first premise says the rule $P(x) \rightarrow Q(x)$ applies to everyone, so it must apply to Ada. Since $P(\text{Ada})$ is true, the implication forces $Q(\text{Ada})$ to be true as well. And if there is at least one individual who is a thinker, the conclusion $\exists x Q(x)$ must be true. The argument holds not because of some linguistic convention, but because the very structure of truth, as defined by standard semantics, guarantees it. This method of evaluating arguments against all possible structures is the bedrock of logical verification.

This power to certify truth is not just for human philosophers. It is a cornerstone of computer science and artificial intelligence. A key goal in AI is to build automated theorem provers—machines that can reason. For a machine to work efficiently, it helps to simplify logical formulas. One powerful technique is "Skolemization," a clever trick for eliminating existential quantifiers. If a formula says $\forall x \exists y \, R(x,y)$ ("for every number $x$, there exists a number $y$ that is greater than it"), we can invent a function, let's call it $f(x)$, that chooses such a $y$ for each $x$. We can then rewrite the formula as $\forall x \, R(x, f(x))$ ("for every number $x$, the number given by $f(x)$ is greater than it"). The new formula isn't logically equivalent to the old one—it makes a stronger claim by positing a specific function—but it is equisatisfiable. That is, one formula has a model if and only if the other one does. This transformation, which is invaluable for computational logic, is justified entirely by the principles of standard semantics.

Of course, the power of these tools depends crucially on the rules of the game. Standard semantics typically assumes that every "universe" or domain we consider is non-empty. What happens if we relax this and allow an empty universe? Suddenly, some of our trusted tools can break. A transformation like Skolemization, which might introduce a constant symbol to witness an existential claim, could inadvertently make a satisfiable formula unsatisfiable, because a constant must name something, and in an empty universe, there is nothing to name. This demonstrates that equisatisfiability can fail when we stray from standard semantics, revealing how deeply our logical machinery depends on these foundational assumptions.

First-order logic, where we quantify only over individuals ($x, y, z, \dots$), is the workhorse of mathematics. Yet, some of the most fundamental concepts seem to elude its grasp. It's surprisingly difficult, for instance, for a first-order theory to say "my domain is finite" or "this ordering has no gaps." To paint these richer concepts, we need a more powerful brush: second-order logic with standard semantics.

Second-order logic (SOL) expands our language by allowing quantification not just over individuals, but over properties of individuals—that is, over sets and relations. When interpreted with standard semantics, the quantifier $\forall P$ means "for all possible subsets of the domain." This seemingly small change has explosive consequences for expressive power.

Properties that are impossible to define in first-order logic become straightforward in SOL.

• ​​Finiteness​​: How can we say a domain is finite? In SOL, we can state: "Every injective function from the domain to itself is also surjective." This is a hallmark of finite sets, and SOL can express it in a single sentence. Because first-order logic is "compact" (a property we will discuss soon), it can be proven that no such single sentence exists in FOL.
• ​​Completeness​​: What makes the real number line $\mathbb{R}$ continuous, unlike the rational number line $\mathbb{Q}$ which is full of holes (like $\sqrt{2}$)? It's the property of Dedekind completeness: every non-empty set of numbers that has an upper bound has a least upper bound. This definition begins with "every...set," a phrase that immediately signals the need for second-order quantification. SOL can state this directly, capturing the essence of continuity that first-order logic can only approximate. Any first-order theory that tries to capture completeness will inevitably have "gappy" models like the rationals, a consequence of a limitation known as the Löwenheim-Skolem theorem.

The crowning achievement of standard second-order semantics is its ability to characterize, uniquely, the structure of the natural numbers. The first-order Peano Axioms (PA) are a powerful description of arithmetic, but by the Compactness Theorem, they admit strange "non-standard models"—bizarre number lines containing infinitely large numbers that still manage to satisfy all the axioms. However, the second-order Peano Axioms ($\mathrm{PA}_2$), which replace the induction schema with a single axiom quantifying over all subsets, are categorical. This means that any model satisfying these axioms must be isomorphic to the standard natural numbers $\mathbb{N}$. Standard second-order semantics is so powerful that it can pin down the structure of arithmetic absolutely, eliminating the weird non-standard worlds that haunt first-order logic.

This incredible descriptive power does not come for free. In one of the most profound trade-offs in the history of logic, the expressive strength of standard second-order semantics is paid for with the loss of the beautiful metatheoretic properties that make first-order logic so "tame."

First-order logic is ​​compact​​: if a conclusion follows from an infinite set of premises, it must follow from some finite subset of them. It is also ​​complete​​: there exists a proof system that can, in principle, derive all valid formulas. Standard second-order logic is neither. The very fact that SOL can characterize an infinite structure like $\mathbb{N}$ up to isomorphism is a proof that it cannot be compact. If it were, one could construct models of $\mathrm{PA}_2$ of any infinite size, contradicting its categoricity. Furthermore, as a consequence of Gödel's work, the set of all valid SOL sentences is not effectively enumerable. There can be no machine, no formal proof system, that is guaranteed to find a proof for every second-order truth. The price of speaking with such precision is that the realm of truth becomes vaster than the realm of proof.

This trade-off forces a fundamental choice upon mathematicians and philosophers. Do we prefer the expressive power of standard semantics, or the well-behaved nature of a complete, compact logic? This question has given rise to alternative semantics.

• ​​Henkin Semantics​​: Leon Henkin found a brilliant way to have his cake and eat it too, albeit a different cake. In Henkin semantics, the quantifier "for all sets $P$" is re-interpreted to mean "for all sets $P$ in a pre-specified collection." A Henkin model explicitly states which sets the quantifiers are allowed to range over. This move brilliantly recasts second-order logic as a many-sorted first-order logic, which immediately restores compactness and completeness. The cost? The expressive power is diminished. Under Henkin semantics, $\mathrm{PA}_2$ is no longer categorical, and the specter of non-standard models returns.
• ​​Intuitionistic Semantics​​: Other alternatives challenge even more fundamental assumptions. Classical logic, underpinned by standard Tarskian semantics, assumes the Law of the Excluded Middle: every statement is either true or false. Intuitionistic logic, formalized by Kripke semantics, rejects this. In a Kripke model, truth is "earned" over time across a series of evolving states of knowledge. A formula like $\lnot\lnot\varphi \to \varphi$ ("if it's not not-true, then it's true") is a classical tautology but fails to be valid in intuitionistic logic. There can be a state where we know $\varphi$ can never be refuted, but we haven't yet constructed a proof of $\varphi$ itself. This shows that our very notion of what constitutes a "logical law" is a direct consequence of how we choose to define truth.

We have seen how standard semantics gives us the power to define reason, build mathematics, and even characterize the infinite. But there is a final, humbling lesson. The very tools of formal language and semantics that give us this power also reveal their own inherent limits.

The ancient Liar's Paradox—"This statement is false"—can be reconstructed with mathematical rigor. The key is Gödel's insight that a language rich enough for arithmetic can talk about its own sentences via coding (Gödel numbering). Using this, the ​​Fixed-Point Lemma​​ shows that for any property you can write down, say $\theta(x)$, there is a sentence $\tau$ that effectively says, "I have property $\theta$."

Now, suppose for the sake of contradiction that we could define "truth" within first-order arithmetic. That is, suppose there were a formula $Tr(x)$ such that $Tr(\ulcorner\varphi\urcorner)$ is true if and only if the sentence $\varphi$ is true. Let's apply the Fixed-Point Lemma to the property $\neg Tr(x)$. It gives us a sentence $\tau$—the Liar sentence—such that $\tau$ is provably equivalent to $\neg Tr(\ulcorner\tau\urcorner)$. This sentence asserts its own untruth.

What is the status of $\tau$?

• By the definition of our hypothetical truth predicate, $Tr(\ulcorner\tau\urcorner)$ is true if and only if $\tau$ is true.
• By the construction of $\tau$, $\tau$ is true if and only if $\neg Tr(\ulcorner\tau\urcorner)$ is true.

Combining these, we find that $\tau$ is true if and only if $\tau$ is not true. This is a flat contradiction. Our initial assumption—that a truth predicate $Tr(x)$ could be defined within the language of arithmetic—must be false. This is ​​Tarski's Undefinability of Truth Theorem​​. It tells us that no language, if powerful enough to describe its own syntax, can define its own concept of truth. Truth for a language $\mathcal{L}_1$ can only be defined in a richer metalanguage $\mathcal{L}_2$, whose truth, in turn, can only be defined in a yet richer $\mathcal{L}_3$, and so on, creating an infinite "Tarskian hierarchy."

This leads us to a final, profound philosophical reflection. When we use the powerful standard semantics for second-order logic, we casually quantify over "all" subsets of an infinite domain. The truth of our statements can hinge on the existence of fantastically complex and indescribable sets. To accept these semantics at face value seems to commit us to a robust form of Platonism, or ​​realism about sets​​. We must believe that the power set $\mathcal{P}(\mathbb{N})$ exists as a completed, definite totality. The choice of Henkin semantics, in contrast, allows for a more deflationary or agnostic stance, as it relativizes the domains of quantification to each model.

And so our journey ends where it began: with meaning. Standard semantics provides a powerful, precise, and astonishingly fruitful framework for defining truth. But in doing so, it not only clarifies the foundations of logic and mathematics but also illuminates the boundaries of what can be known, what can be said, and what, perhaps, must be believed.