30

If I say that $A$ is stronger than $B$, do I mean that $A \Rightarrow B$, or that $B \Rightarrow A$? (Or something else?)

I feel like I have seen both usages in literature, which is confusing.

Thoughts based on intuition:

$A \Rightarrow B$ means $A$ is a special case of $B$ -- $B$ is more general. This would seem to imply that $B$ is "stronger". (Example: $n$ is an integer implies $n$ is a real number.)

$A \Rightarrow B$ also means that whenever $A$ holds, $B$ must hold. This would seem to imply that $A$ is "stronger".

Asaf Karagila
  • 393,674
usul
  • 3,724
  • 10
    A stronger theorem is one which has a weaker hypothesis and/or a stronger conclusion. – GEdgar Jul 25 '11 at 17:54
  • 1
    In your example "n is an integer implies n is a real number", you are thinking of the predicates involved. The integers are a proper subset of the real numbers. That might be the source of your confusion. When logicians talk about A being stronger than B, they're talking about A and B as distinct statements without regard to the predicates they contain, as Asaf explains. – MikeC Jul 25 '11 at 18:25
  • Thanks for the explanations. So when I say "A is stronger than B", precisely what can A and B be? Only theorems? Logical sentences? – usul Jul 25 '11 at 21:41
  • @bo1024: It means $A$ implies more sentences, then $B$. This is equivalent to $A \Rightarrow B$ because $\Rightarrow$ is a preorder. – beroal Jul 26 '11 at 20:36

2 Answers2

27

If $A\Rightarrow B$, then for every $C$, if $B\Rightarrow C$ we have that $A\Rightarrow C$. Therefore $A$ implies at least the same propositions that $B$ implies.

We have two options from here:

  1. $B\Rightarrow A$, in which case $A$ is equivalent to $B$, and they imply the same things.
  2. $B\nRightarrow A)$, that is $B$ does not imply $A$. We have if so that $A$ is stronger than $B$ since $A\implies A$, but $B$ does not.

In essence "$A$ is stronger than $B$" is when $\{C\mid B\Rightarrow C\}\subsetneq\{C\mid A\Rightarrow C\}$, and equivalent is when the sets are equal.

Asaf Karagila
  • 393,674
20

Let's make the simplifying assumption that $\lnot(B \implies A)$.

Then $A \implies B$ can be informally expressed as "$A$ is (strictly) stronger than $B$."

It is certainly possible that in this situation, at some time, someone has instead written "$B$ is stronger than $A$." Stuff happens. We all have written $x<y$ when we meant $y<x$. And interchange of "necessary condition" and "sufficient condition" happens so (relatively) often that it may be best to avoid these terms.

But "$A$ is stronger than $B$" has only one correct interpretation in terms of the direction of the implication (with disagreement, possibly, in the case of equivalence.)

However, suppose that we have proved theorem $X$, $\:$(a) under the assumption $A$, and $\:$(b) under the assumption $B$. Then the result (b) is considered to be a stronger result than the result (a). That is perfectly consistent with the ordinary meaning of "stronger," since $$(B \implies X) \implies (A\implies X).$$

André Nicolas
  • 507,029