Syntax vs. Semantics in Formal Systems

Hello! Welcome back to our study of the foundations of mathematics.

In our last lesson, you constructed Cantor's diagonal argument, a powerful proof that demonstrates the uncountability of the real numbers. We noted that the argument works by highlighting a mismatch between a list of numbers (a syntactic object, a sequence of symbols) and the set of all numbers (a semantic object, a collection of mathematical values). This distinction is one of the most fundamental concepts in modern logic and is the absolute key to unlocking the work of Kurt Gödel.

Today, we will formalize this crucial idea. Your learning outcome is to explain the distinction between syntax and semantics in the context of formal systems. We will explore how logicians separate the rules for manipulating symbols from the assignment of meaning and truth, a separation that brings immense clarity and power to philosophical and mathematical analysis.

1. The Two Faces of Logic: Proof vs. Truth

At its core, the distinction between syntax and semantics is about separating form from content.

• Syntax refers to the formal rules of a language, the "grammar" that dictates how symbols can be arranged and manipulated. In logic, this is the domain of proof theory. It deals with axioms, well-formed formulas, and rules of inference. Syntactic questions are about derivability: can a certain formula be proven from a given set of axioms by following the rules? It is a game of symbol manipulation, where the meaning of the symbols is irrelevant.

• Semantics refers to the meaning or interpretation of those symbols. This is the domain of model theory. It deals with how formulas relate to a particular mathematical structure or state of affairs. Semantic questions are about truth: is a certain formula true in a given interpretation?

The following video provides an excellent introduction to this distinction and introduces the crucial symbols that logicians use to keep the two ideas separate.

As the video explained, we have two different ways of thinking about an argument:

1. Syntactic Consequence (⊢): We write Γ ⊢ φ (read: "φ is provable from Γ") to state that the formula φ can be derived from the set of premises Γ using only the axioms and inference rules of our system. This is a claim about the existence of a formal proof.

2. Semantic Consequence (⊨): We write Γ ⊨ φ (read: "φ is a logical consequence of Γ" or "Γ entails φ") to state that in every possible interpretation (or model) where all the formulas in Γ are true, the formula φ is also true. This is a claim about truth preservation across all relevant cases.

The fundamental question of metalogic is: how do ⊢ and ⊨ relate? We'll return to this at the end of the lesson. First, let's make the distinction more concrete.

2. A Concrete Example: Propositional Logic

To see syntax and semantics in action, we can build a simple formal language from the ground up. The following resource does exactly this for the language of propositional logic, which it calls L₁.

Let's summarize the key ideas from the text, which perfectly illustrate the division:

The Syntax of L₁

The syntax tells us what counts as a grammatically correct sentence. It is defined recursively:

• Vocabulary: The allowed symbols are sentence letters (P, Q, R, ...), connectives (¬, ∧, ∨, →, ↔), and brackets ((, )).
• Formation Rules:
  1. (Base case) Any sentence letter is a sentence.
  2. (Recursive step) If φ and ψ are sentences, then so are ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and (φ ↔ ψ).
  3. (Closing clause) Nothing else is a sentence.

This gives us a precise, mechanical way to check if a string of symbols is a "well-formed formula" (WFF). For example, (P → ¬Q) is a WFF, whereas P→Q¬ is not.

The Semantics of L₁

The semantics tells us what the sentences mean, which in propositional logic boils down to their truth conditions.

• Interpretation (L₁-structure): An interpretation is an assignment of a truth-value (T or F) to every sentence letter. For example, one interpretation A might be: |P|A = T, |Q|A = F, |R|A = T, ...
• Truth Conditions (Truth Tables): The meanings of the connectives are defined by how they determine the truth-value of a complex sentence based on the values of its parts. For instance, |(φ ∧ ψ)|A = T if and only if |φ|A = T and |ψ|A = T.

With these two components, we can take any WFF and any interpretation and calculate the sentence's truth-value.

3. Tarski and the Metalanguage

Notice that when we discussed the formation rules, we used the Greek letters φ and ψ. These are not part of the language L₁; they are variables in our language (English, augmented with logical symbols) that we use to talk about the sentences of L₁. This introduces a critical distinction, formalized by the logician and mathematician Alfred Tarski, between the object language and the metalanguage.

• Object Language: The language being studied (e.g., L₁).
• Metalanguage: The language used to study the object language (e.g., English + math symbols like φ, ψ, |...|, = T).

Tarski's key insight was that a rigorous definition of truth for an object language can only be given in a richer metalanguage. This move brilliantly dissolves paradoxes like the Liar Paradox ("This sentence is false"). In Tarski's framework, a sentence can never talk about its own truth; it can only be assessed from "one level up" in the metalanguage.

The following video explains Tarski's solution and his "semantic conception of truth," which forms the basis of all modern model theory.

Tarski's most famous example of a truth definition in the metalanguage is:

The sentence "snow is white" is true if and only if snow is white.

This might seem trivial, but it's profound. It shows how the metalanguage (English) connects a name for a sentence in the object language (the quoted part) to the actual state of the world (the unquoted part). This structure is what allows us to define truth formally, by mapping symbols to objects and relations in a mathematical structure, a concept at the heart of model theory. For an infinite language, Tarski showed how this could be done recursively, starting with basic predicates and defining truth for complex sentences in terms of the simpler parts, much like the truth tables we saw for L₁.

4. Soundness and Completeness: Bridging the Divide

Now we can return to our central question: how do ⊢ (syntactic provability) and ⊨ (semantic truth) relate? For a given logical system, we hope for two properties:

1. Soundness (If ⊢ then ⊨): A system is sound if whatever can be proven syntactically is also semantically true. That is, if Γ ⊢ φ, then Γ ⊨ φ. This is a basic requirement for any useful logic; we do not want our rules of proof to lead us from true premises to a false conclusion.

2. Completeness (If ⊨ then ⊢): A system is complete if every semantic truth is also syntactically provable. That is, if Γ ⨨ φ, then Γ ⊢ φ. This means our proof system is powerful enough to derive every logical truth.

The first video you watched sets this up perfectly.

Propositional logic and standard first-order logic are both sound and complete. This was a major achievement, showing that for these systems, the syntactic and semantic notions of consequence perfectly coincide. You can prove it if and only if it's true in all models.

However, as the video mentions, this beautiful correspondence breaks down for more powerful systems. This is exactly what Gödel showed.

Conclusion

In this lesson, we have dissected logical systems into their two fundamental components, giving you the conceptual toolkit for the next stage of our journey.

Key Takeaways:

• Syntax concerns the formal rules of a language, governing the manipulation of symbols without regard to their meaning. In logic, this is proof theory, and its notion of consequence is provability (⊢).
• Semantics concerns the interpretation and meaning of symbols, assigning truth-values within a given structure or model. In logic, this is model theory, and its notion of consequence is entailment (⊨).
• Tarski's object/metalanguage distinction is a crucial device for providing a rigorous, non-paradoxical definition of truth for formal languages.
• Soundness and completeness are properties that bridge the syntactic/semantic divide, stating that a system proves only truths and all truths, respectively.

Preview of the Next Lesson:
With this firm grasp of the syntax/semantics distinction, you are now ready to tackle one of the most significant intellectual achievements of the 20th century. In our next lesson, we will explore the core ideas of Gödel's First Incompleteness Theorem. Gödel's genius was to use the syntax of arithmetic to construct a sentence that, under its semantic interpretation, asserts its own unprovability, forever shattering the dream of a complete and consistent foundation for all of mathematics.