Learn & Review: Mathematical Logic, Lecture 1

Mathematical Logic (MATH 220A): Introduction to First-Order Logic

This course introduces the fundamentals of First-Order Logic (FOL), a standard method for formalizing mathematics. Examples include Peano Arithmetic (PAA) for number theory and Zermelo-Fraenkel Set Theory (ZFC) for set theory.

1. Syntax vs. Semantics in FOL

FOL has two main aspects:

• Syntax: This deals with the formal construction of statements using symbols.

  • It involves defining variables, terms, and formulas.
  • Formal logical deduction rules are defined to derive new statements from axioms through formal proofs.
  • Constructions are purely symbolic, without inherent meaning.

• Semantics: This involves interpreting the symbols within structures (also called models).

  • Structures are sets where terms and formulas can be interpreted.
  • This allows for determining the validity or satisfaction of formulas within a given structure.

2. Gödel's Completeness Theorem

The first major result of the course is Gödel's Completeness Theorem. It establishes an equivalence between syntax and semantics:

• A formula with no free variables can be formally deduced from a set of axioms if and only if it is valid in every structure that satisfies those axioms.
• This theorem justifies the choice of syntactic rules and formal language, showing that different choices ultimately lead to the same results.

3. First-Order Languages

Statements in FOL are sequences of symbols from a fixed, finite alphabet. A first-order language (L) is a set of symbols composed of two disjoint subsets:

• Auxiliary and Logical Symbols (Common to all languages):

  • Parentheses: ( and )
  • Logical Symbols:
    • Variables: A countable set, denoted by V (e.g., v_0, v_1, ...).
    • Equality Symbol: =
    • Connectives: Negation (¬, "not") and Conjunction (∧, "and").
    • Quantifier: Existential quantifier (∃, "there exists").

• Signature of L (Non-logical Symbols, specific to the language):

  • Constant Symbols: C_L (e.g., 0, 1).
  • Function Symbols: A sequence F_n,L for n ≥ 1, where elements are n-ary function symbols (e.g., +, *, s for successor).
  • Relation Symbols (Predicates): A sequence R_n,L for n ≥ 1, where elements are n-ary relation symbols (e.g., <, "belongs to").

• Note: While names suggest interpretations, at this stage, no meaning is attached to these symbols. The language L is the disjoint union of these sets. Languages are always infinite, and the logical part is countable. Often, the language L is identified with its signature Σ_L.

Examples of Languages:

• Empty Language (L_∅): Contains only logical symbols, no non-logical symbols.
• Ring Language (L_ring): Constants 0, 1; binary functions +, -, *.
• Order Language (L_ord): Binary relation <.
• Ordered Ring Language (L_ordered_rings): Union of L_ring and L_ord.
• Set Theory Language (L_set): Binary relation ∈ ("belongs to").
• Group Language (L_groups): Binary function *; unary function ⁻¹ (inverse); constant 1.
• Graph Language (L_graphs): Binary relation E ("edge").
• Arithmetic Language (L_arith): Constant 0; unary function s (successor); binary functions +, *; binary relation <.

4. L-Structures (Models)

An L-structure A for a language L consists of:

• A non-empty set A called the base set or domain.
• For each constant symbol c in L, an element c^A ∈ A.
• For each n-ary function symbol f in L, a function f^A: A^n → A.
• For each n-ary relation symbol r in L, a subset r^A ⊆ A^n.

The object z^A (where z is a non-logical symbol) is the interpretation of z in the structure A.

Examples of Structures:

• Natural Numbers (M) in L_arith:
  • Base set: ℕ (natural numbers).
  • Interpretations: 0^M = 0, s^M(x) = x+1, +^M is standard addition, *^M is standard multiplication, <^M is standard order.
• Complex Numbers (C) in L_ring:
  • Base set: ℂ (complex numbers).
  • Interpretations: 0^C = 0, 1^C = 1, +^C, -^C, *^C are standard operations.
• Real Numbers (R) in L_ordered_rings:
  • Base set: ℝ (real numbers).
  • Interpretations: 0^R = 0, 1^R = 1, +^R, -^R, *^R, <^R are standard operations and order.

5. Isomorphism of L-Structures

Two L-structures A and B are isomorphic (A ≅ B) if there exists a bijection F: A → B (where A and B are the base sets) that commutes with the interpretations of all non-logical symbols in L. This means:

• F(c^A) = c^B for all constant symbols c.
• F(f^A(a_1, ..., a_n)) = f^B(F(a_1), ..., F(a_n)) for all n-ary function symbols f.
• (a_1, ..., a_n) ∈ r^A if and only if (F(a_1), ..., F(a_n)) ∈ r^B for all n-ary relation symbols r.

A function F satisfying these conditions (without being a bijection) is called a morphism. If F is injective, it's an embedding.

6. Terms and Formulas

• Words: A finite string of symbols from a given alphabet (set E). E* denotes the set of all words over E.

• L-Terms: The set T_L of L-terms is the smallest set of words over the alphabet of L such that:

  • Variables and constant symbols of L are L-terms.
  • If f is an n-ary function symbol in L and t_1, ..., t_n are L-terms, then f t_1 ... t_n is an L-term.
  • Terms can be defined recursively:
    • T_0(L) = Variables ∪ Constant Symbols
    • T_{n+1}(L) = T_n(L) ∪ {f t_1 ... t_k | f is k-ary in L, t_i ∈ T_n(L)}

• Unique Readability of Terms: Any term t is uniquely either a variable, a constant symbol, or of the form f t_1 ... t_n for a unique function symbol f and unique terms t_1, ..., t_n.

• Notation: f(t_1, ..., t_n) is often used instead of f t_1 ... t_n. For binary functions, infix notation like t_1 + t_2 might be used.

• Height of a Term (ht(t)): The minimum k such that t ∈ T_k(L). ht(f t_1 ... t_n) = 1 + max(ht(t_i)).

• L-Formulas:

  • Atomic Formulas:
    • t_1 = t_2, where t_1, t_2 are L-terms.
    • r t_1 ... t_n, where r is an n-ary relation symbol in L and t_1, ..., t_n are L-terms.
  • The set FML(L) of L-formulas is the smallest set of words over the alphabet of L containing all atomic formulas and closed under the following rules:
    • If φ is a formula, then ¬φ is a formula.
    • If φ and ψ are formulas, then φ ∧ ψ is a formula.
    • If φ is a formula and x is a variable, then ∃x φ is a formula.
  • Formulas can also be defined recursively:
    • FML_0(L) = Atomic Formulas
    • FML_{n+1}(L) = FML_n(L) ∪ {¬φ | φ ∈ FML_n(L)} ∪ {φ ∧ ψ | φ, ψ ∈ FML_n(L)} ∪ {∃x φ | x is a variable, φ ∈ FML_n(L)}

The lecture concludes by emphasizing that all concepts discussed so far (languages, terms, formulas) are purely syntactic. The next lecture will introduce semantics to give meaning to these symbols.