Strength (mathematical logic)

In mathematical logic, the term "strength" refers to the comparative expressiveness or deductive power of different logical systems, theories, or axioms. A stronger system, theory, or axiom is one that can prove more statements or establish a greater range of conclusions than a weaker one. The notion of strength is typically defined relative to a specific domain or a set of questions under consideration.

There are several ways to compare the strength of logical systems:

• Expressive strength: This refers to the ability of a logical system to express different concepts or properties. A logic with greater expressive strength can formulate a wider range of statements. For example, second-order logic is more expressively powerful than first-order logic because it allows quantification over sets of individuals, enabling the formulation of statements that cannot be expressed in first-order logic.

• Deductive strength: This refers to the ability of a logical system to derive new statements from a given set of axioms or premises. A logic with greater deductive strength can prove more theorems or derive more consequences. If theory T1 proves all theorems provable in theory T2, and possibly more, then T1 is deductively stronger than T2.

• Relative Interpretability: This is a more formal notion of strength. Theory T1 is interpretable in theory T2 if there is a translation of the language of T1 into the language of T2 such that, for any sentence φ in the language of T1, if φ is provable in T1, then its translation is provable in T2. If T1 is interpretable in T2, we say T2 is at least as strong as T1. If, additionally, T2 is interpretable in T1, then T1 and T2 are said to be of equal strength. Otherwise, if T1 is interpretable in T2 but T2 is not interpretable in T1, then T2 is strictly stronger than T1.

• Consistency Strength: Related to the ordinal numbers that measure the proof-theoretic ordinal of a theory, a theory's consistency strength is measured by the least ordinal that cannot be proven well-ordered by the theory. If Theory A can prove the consistency of Theory B, then Theory A is typically considered to have a higher consistency strength.

Comparing the strength of logical systems is crucial for understanding the limitations and capabilities of different formal frameworks. It helps researchers choose the appropriate logic for a particular task and provides insights into the relationships between different branches of mathematics and computer science. For instance, understanding the strength of various set theories is vital in setting the foundations of mathematics. The strength of theories also plays a role in areas such as automated theorem proving, knowledge representation, and formal verification.