8.2 Expressive power and limitations of second-order logic
3 min read•august 7, 2024
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
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
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
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
can be fully axiomatized in second-order logic
Includes axioms for the successor function, addition, multiplication, and the 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 ()
Induction axiom implies the
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 , analysis, topology, abstract algebra
Provides a foundation for mathematics alternative to first-order set theory (ZFC)
Continuum Hypothesis and Its Independence
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