8.2 Expressive power and limitations of second-order logic

Second-order logic packs a punch in the world of mathematical reasoning. It can express complex ideas like the natural numbers and real numbers uniquely, something first-order logic can't do. This added power comes with trade-offs though.

While second-order logic is more expressive, it loses some nice properties of first-order logic. It's not compact and doesn't have the Löwenheim-Skolem theorems. But it can categorically define important mathematical structures, making it a powerful tool for formalizing mathematics.

Fundamental Theorems

Completeness and Compactness

Top images from around the web for Completeness and Compactness

• 

  Second Order Logic: Existential could be expressed as a universal quantifier. - Mathematics ... View original

  Is this image relevant?

• 

  Jacob Silterra | Page 2 View original

  Is this image relevant?

• 

  Second Order Logic: Existential could be expressed as a universal quantifier. - Mathematics ... View original

  Is this image relevant?

• 

  Jacob Silterra | Page 2 View original

  Is this image relevant?

1 of 2

Top images from around the web for Completeness and Compactness

• 

  Second Order Logic: Existential could be expressed as a universal quantifier. - Mathematics ... View original

  Is this image relevant?

• 

  Jacob Silterra | Page 2 View original

  Is this image relevant?

• 

  Second Order Logic: Existential could be expressed as a universal quantifier. - Mathematics ... View original

  Is this image relevant?

• 

  Jacob Silterra | Page 2 View original

  Is this image relevant?

1 of 2

• Completeness theorem states that every valid formula in second-order logic is provable from the axioms and rules of inference
  • Ensures that second-order logic is a sound and complete system
  • Guarantees that any logical consequence of a set of axioms can be formally derived within the system
• Compactness theorem does not hold for second-order logic
  • In first-order logic, compactness states that if every finite subset of a set of formulas is satisfiable, then the entire set is satisfiable
  • Lack of compactness in second-order logic means that there can be infinite sets of formulas where every finite subset is satisfiable, but the entire set is not

Löwenheim-Skolem Theorems and Categoricity

• Löwenheim-Skolem theorems do not hold for second-order logic
  • In first-order logic, these theorems state that if a theory has an infinite model, then it has models of every infinite cardinality
  • Second-order logic allows for categorical axiomatizations, meaning a theory can have a unique model up to isomorphism
• Categoricity is possible in second-order logic
  • A theory is categorical if it has a unique model up to isomorphism
  • Second-order logic can express concepts like "the natural numbers" or "the real numbers" categorically
  • Categoricity is not possible in first-order logic due to the Löwenheim-Skolem theorems

Arithmetic and Induction

Peano Arithmetic in Second-Order Logic

• Peano arithmetic can be fully axiomatized in second-order logic
  • Includes axioms for the successor function, addition, multiplication, and the induction axiom
  • Second-order induction axiom captures the full strength of mathematical induction
  • Categorically defines the structure of the natural numbers
• Second-order Peano arithmetic is categorical
  • Has a unique model up to isomorphism, the standard model of the natural numbers
  • Avoids non-standard models that exist in first-order Peano arithmetic (models with "infinite" natural numbers)

Induction Axiom and Its Consequences

• Second-order induction axiom is more powerful than first-order induction
  • Allows induction over predicates and sets, not just properties definable by formulas
  • Enables proofs of statements that are not provable in first-order Peano arithmetic (Goodstein's theorem)
• Induction axiom implies the well-ordering of the natural numbers
  • Every non-empty subset of the natural numbers has a least element
  • Crucial for proving many fundamental properties of the natural numbers (every non-zero natural number has a unique predecessor)

Set Theory and Continuum Hypothesis

Expressive Power of Second-Order Logic

• Second-order logic can express many concepts not definable in first-order logic
  • Finiteness, countability, uncountability, connectedness of graphs, well-foundedness
  • Allows for categorical axiomatizations of structures like the real numbers or the power set of the natural numbers
• Second-order logic is powerful enough to express most of classical mathematics
  • Can formalize set theory, analysis, topology, abstract algebra
  • Provides a foundation for mathematics alternative to first-order set theory (ZFC)

Continuum Hypothesis and Its Independence

• Continuum hypothesis states that there is no set whose cardinality is strictly between that of the natural numbers and the real numbers
  • Can be formulated in second-order logic using the power set operation and the concept of bijection
  • Remains independent of the axioms of second-order ZFC (Zermelo-Fraenkel set theory with the axiom of choice)
• Independence of the continuum hypothesis from second-order ZFC
  • Proven by Cohen's forcing method, building on Gödel's constructible universe
  • Shows that the continuum hypothesis can neither be proved nor disproved from the axioms of second-order ZFC
  • Highlights the limitations of second-order logic in resolving certain fundamental questions in set theory