Logical Strength

logic

Definition

Logical Strength

Logical strength is a measure of the informative power of a statement. It is formally defined via the entailment relation and the subset relation of models.

Let $\mathcal{L}$ be a formal language (e.g. propositional or first-order logic). Let $\varphi ,\psi$ be formulas in $\mathcal{L}$.

We say that $\varphi$ is logically stronger than $\psi$ iff $\varphi$ entails $\psi$:

$$\varphi \models \psi$$

If $\varphi \models \psi$, the truth of $\varphi$ guarantees the truth of $\psi$.

Strictly Stronger: If $\varphi \models \psi$, but $\psi /\models \varphi$, then $\varphi$ is strictly stronger than $\psi$.

Equivalence: If $\varphi \models \psi$ and $\psi \models \varphi$, then $\varphi$ and $\psi$ are logically equivalent.

Logical strength acts as a constraint on the universe of possible worlds. The strength of a formula is inversely proportional to the number of models (interpretations) that satisfy it.

Let $\mathcal{M}(\varphi )=\{M\mid M\models \varphi \}$ be the set of models where $\varphi$ is true.

$$\varphi \text{ is stronger than }\psi ⟺\mathcal{M}(\varphi )\subseteq \mathcal{M}(\psi )$$

• Intuition: A stronger statement is harder to satisfy (fewer cases), so its set of models is smaller (a subset).
• Weakest Element: The formula True ($\top$) is the weakest possible statement. $\mathcal{M}(\top )=\text{Universe}$ (satisfied by all cases).
• Strongest Element: The formula False ($\perp$) is the strongest possible statement. $\mathcal{M}(\perp )=\varnothing$ (satisfied by no cases).

Square Subset Notation

In some contexts (e.g., lattice theory or abstract semantics), logical strength is denoted using “square subset” notation to emphasise the ordering of cases:

$$\varphi ⊑\psi ⟺\mathcal{M}(\varphi )\subseteq \mathcal{M}(\psi )$$

• $\varphi ⊑\psi$: $\varphi$ is stronger than (or equal to) $\psi$.
• $\varphi ⊏\psi$: $\varphi$ is strictly stronger than $\psi$.
• $\varphi ⊒\psi$: $\varphi$ is weaker than (or equal to) $\psi$.

Examples

1. Example:
   • $C_1:=x=y$
   • $C_2:=x\le y$
   • $C_1⊑C_2$ since equality implies order ($=$ entails $\le$), meaning every case where $x=y$ is also a case where $x\le y$.
2. Example:
   • $C_1:=x\le y$
   • $C_2:=(x=y)\wedge b$
   • $C_2⊏C_1$ since $C_2$ is more restrictive; it requires equality and the condition $b$, whereas $C_1$ accepts any case where $x<y$.
3. Example:
   • $C_1:=x\le y$
   • $C_2:=(x=y)\vee b$
   • incomparable since $C_1$ holds when $x<y$ (violating $C_2$ if $\neg b$), but $C_2$ holds when $b$ is true (violating $C_1$ if $x>y$).
4. Example:
   • $C_1:=x=y$
   • $C_2:=(x\le y)\wedge (x\ge y)$
   • $C_1⟺C_2$ since by the property of anti-symmetry, satisfying both $\le$ and $\ge$ is mathematically identical to equality.